skip to main content


Title: The Local Forking Lemma and Its Application to Deterministic Encryption
We bypass impossibility results for the deterministic encryption of public-key-dependent messages, showing that, in this setting, the classical Encrypt-with-Hash scheme provides message-recovery security, across a broad range of message distributions. The proof relies on a new variant of the forking lemma in which the random oracle is reprogrammed on just a single fork point rather than on all points past the fork.  more » « less
Award ID(s):
1717640
NSF-PAR ID:
10200007
Author(s) / Creator(s):
Editor(s):
Steven D. Galbraith, Shiho Moriai
Date Published:
Journal Name:
Advances in Cryptology - {ASIACRYPT} 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8-12, 2019, Proceedings, Part III
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Cells rapidly respond to replication stress actively slowing fork progression and inducing fork reversal. How replication fork plasticity is achieved in the context of nuclear organization is currently unknown. Using nuclear actin probes in living and fixed cells, we visualized nuclear actin filaments in unperturbed S phase and observed their rapid extension in number and length upon genotoxic treatments, frequently taking contact with replication factories. Chemically or genetically impairing nuclear actin polymerization shortly before these treatments prevents active fork slowing and abolishes fork reversal. Defective fork remodeling is linked to deregulated chromatin loading of PrimPol, which promotes unrestrained and discontinuous DNA synthesis and limits the recruitment of RAD51 and SMARCAL1 to nascent DNA. Moreover, defective nuclear actin polymerization upon mild replication interference induces chromosomal instability in a PRIMPOL-dependent manner. Hence, by limiting PrimPol activity, nuclear F-actin orchestrates replication fork plasticity and is a key molecular determinant in the rapid cellular response to genotoxic treatments.

     
    more » « less
  2. null (Ed.)
    On shared-memory multicore machines, classic two-way recursive divide-and-conquer algorithms are implemented using common fork-join based parallel programming paradigms such as Intel Cilk+ or OpenMP. However, in such parallel paradigms, the use of joins for synchronization may lead to artificial dependencies among function calls which are not implied by the underlying DP recurrence. These artificial dependencies can increase the span asymptotically and thus reduce parallelism. From a practical perspective, they can lead to resource underutilization, i.e., threads becoming idle. To eliminate such artificial dependencies, task-based runtime systems and data-flow parallel paradigms, such as Concurrent Collections (CnC), PaRSEC, and Legion have been introduced. Such parallel paradigms and runtime systems overcome the limitations of fork-join parallelism by specifying data dependencies at a finer granularity and allowing tasks to execute as soon as dependencies are satisfied.In this paper, we investigate how the performance of data-flow implementations of recursive divide-and-conquer based DP algorithms compare with fork-join implementations. We have designed and implemented data-flow versions of DP algorithms in Intel CnC and compared the performance with fork-join based implementations in OpenMP. Considering different execution parameters (e.g., algorithmic properties such as recursive base size as well as machine configuration such as the number of physical cores, etc), our results confirm that a data-flow based implementation outperforms its fork-join based counter-part when due to artificial dependencies, the fork-join implementation fails to generate enough subtasks to keep all processors busy and does not have enough data locality to compensate for the lost performance. This phenomena happens when the input size of the DP algorithm is small or we have a huge number of compute cores in the system. As a result, with a fixed computation resource, moving from small input to larger input, fork-join implementation of DP algorithms outperforms the corresponding data-flow implementation. However, for a fixed size problem, moving the computation to a compute node with a larger number of cores, data-flow implementation outperforms the corresponding fork-join implementation. 
    more » « less
  3. Abstract

    BRCA1/2 proteins function in genome stability by promoting repair of double-stranded DNA breaks through homologous recombination and by protecting stalled replication forks from nucleolytic degradation. In BRCA1/2-deficient cancer cells, extensively degraded replication forks can be rescued through distinct fork recovery mechanisms that also promote cell survival. Here, we identified a novel pathway mediated by the E3 ubiquitin ligase RAD18, the E2-conjugating enzyme UBC13, the recombination factor PALB2, the E3 ubiquitin ligase RNF168 and PCNA ubiquitination that promotes fork recovery in BRCA1- but not BRCA2-deficient cells. We show that this pathway does not promote fork recovery by preventing replication fork reversal and degradation in BRCA1-deficient cells. We propose a mechanism whereby the RAD18–UBC13–PALB2–RNF168 axis facilitates resumption of DNA synthesis by promoting re-annealing of the complementary single-stranded template strands of the extensively degraded forks, thereby allowing re-establishment of a functional replication fork. We also provide preliminary evidence for the potential clinical relevance of this novel fork recovery pathway in BRCA1-mutated cancers, as RAD18 is over-expressed in BRCA1-deficient cancers, and RAD18 loss compromises cell viability in BRCA1-deficient cancer cells.

     
    more » « less
  4. null (Ed.)
    The claw is the graph $K_{1,3}$, and the fork is the graph obtained from the claw $K_{1,3}$ by subdividing one of its edges once. In this paper, we prove a structure theorem for the class of (claw, $C_4$)-free graphs that are not quasi-line graphs, and a structure theorem for the class of (fork, $C_4$)-free graphs that uses the class of (claw, $C_4$)-free graphs as a basic class. Finally, we show that every (fork, $C_4$)-free graph $G$ satisfies $\chi(G)\leqslant \lceil\frac{3\omega(G)}{2}\rceil$ via these structure theorems with some additional work on coloring basic classes. 
    more » « less
  5. Abstract

    Social media platforms like Twitter and Facebook provide risk communicators with the opportunity to quickly reach their constituents at the time of an emerging infectious disease. On these platforms, messages gain exposure through message passing (called “sharing” on Facebook and “retweeting” on Twitter). This raises the question of how to optimize risk messages for diffusion across networks and, as a result, increase message exposure. In this study we add to this growing body of research by identifying message‐level strategies to increase message passing during high‐ambiguity events. In addition, we draw on the extended parallel process model to examine how threat and efficacy information influence the passing of Zika risk messages. In August 2016, we collected 1,409 Twitter messages about Zika sent by U.S. public health agencies’ accounts. Using content analysis methods, we identified intrinsic message features and then analyzed the influence of those features, the account sending the message, the network surrounding the account, and the saliency of Zika as a topic, using negative binomial regression. The results suggest that severity and efficacy information increase how frequently messages get passed on to others. Drawing on the results of this study, previous research on message passing, and diffusion theories, we identify a framework for risk communication on social media. This framework includes four key variables that influence message passing and identifies a core set of message strategies, including message timing, to increase exposure to risk messages on social media during high‐ambiguity events.

     
    more » « less