Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Free, publiclyaccessible full text available November 27, 2024

Let Kt ( x ) denote the LevinKolmogorov Complexity of the string x , and let MKtP denote the language of pairs ( x , k ) having the property that Kt ( x ) ≤ k. We demonstrate that: • MKtP ∉ Heur neg BPP (i.e., MKtP is twosided error mildly averagecase hard) iff infinitelyoften OWFs exist. • MKtP ∉ Avg neg BPP (i.e., MKtP is errorless mildly averagecase hard) iff EXP ≠ BPP. Taken together, these results show that the only "gap" toward getting (infinitelyoften) OWFs from the assumption that EXP ≠ BPP is the seemingly "minor" technical gap between twosided error and errorless averagecase hardness of the MKtP problem.more » « less

Differential obliviousness (DO) is a privacy notion which guarantees that the access patterns of a program satisfies differential privacy. Differential obliviousness was studied in a sequence of recent works as a relaxation of full obliviousness. Earlier works showed that DO not only allows us to circumvent the logarithmicoverhead barrier of fully oblivious algorithms, in many cases, it also allows us to achieve polynomial speedup over full obliviousness, since it avoids “padding to the worstcase” behavior of fully oblivious algorithms. Despite the promises of differential obliviousness (DO), a significant barrier that hinders its broad application is the lack of composability. In particular, when we apply one DO algorithm to the output of another DO algorithm, the composed algorithm may no longer be DO (with reasonable parameters). Specifically, the outputs of the first DO algorithm on two neighboring inputs may no longer be neighboring, and thus we cannot directly benefit from the DO guarantee of the second algorithm. In this work, we are the first to explore a theory of composition for differentially oblivious algorithms. We propose a refinement of the DO notion called (ε, δ)neighborpreservingDO, or (ε,δ)NPDO for short, and we prove that our new notion indeed provides nice compositional guarantees. In this way, the algorithm designer can easily track the privacy loss when composing multiple DO algorithms. We give several example applications to showcase the power and expressiveness of our new NPDO notion. One of these examples is a result of independent interest: we use the com positional framework to prove an optimal privacy amplification theorem for the differentially oblivious shuffle model. In other words, we show that for a class of distributed differentially private mechanisms in the shufflemodel, one can replace the perfectly secure shuffler with a DO shuffler, and nonetheless enjoy almost the same privacy amplification enabled by a shuffler.more » « less

Many proofs of interactive cryptographic protocols (e.g., as in Universal Composability) operate by proving the protocol at hand to be observationally equivalent to an idealized specification. While pervasive, formal tool support for observational equivalence of cryptographic protocols is still a nascent area of research. Current mechanization efforts tend to either focus on diffequivalence, which establishes observational equivalence between protocols with identical control structures, or require an explicit witness for the observational equivalence in the form of a bisimulation relation. Our goal is to simplify proofs for cryptographic protocols by introducing a core calculus, IPDL, for cryptographic observational equivalences. Via IPDL, we aim to address a number of theoretical issues for cryptographic proofs in a simple manner, including probabilistic behaviors, distributed messagepassing, and resourcebounded adversaries and simulators. We demonstrate IPDL on a number of case studies, including a distributed coin toss protocol, Oblivious Transfer, and the GMW multiparty computation protocol. All proofs of case studies are mechanized via an embedding of IPDL into the Coq proof assistant.more » « less

We introduce the notion of a Succinct Parallelizable Argument of Knowledge (SPARK). This is an argument of knowledge with the following three efficiency properties for computing and proving a (nondeterministic, polynomial time) parallel RAM computation that can be computed in parallel time T with at most p processors: — The prover’s (parallel) running time is \( T + \mathrm{poly}\hspace{2.0pt}\log (T \cdot p) \) . (In other words, the prover’s running time is essentially T for large computation times!) — The prover uses at most \( p \cdot \mathrm{poly}\hspace{2.0pt}\log (T \cdot p) \) processors. — The communication and verifier complexity are both \( \mathrm{poly}\hspace{2.0pt}\log (T \cdot p) \) . The combination of all three is desirable, as it gives a way to leverage a moderate increase in parallelism in favor of nearoptimal running time. We emphasize that even a factor two overhead in the prover’s parallel running time is not allowed. Our main contribution is a generic construction of SPARKs from any succinct argument of knowledge where the prover’s parallel running time is \( T \cdot \mathrm{poly}\hspace{2.0pt}\log (T \cdot p) \) when using p processors, assuming collisionresistant hash functions. When suitably instantiating our construction, we achieve a fourround SPARK for any parallel RAM computation assuming only collision resistance. Additionally assuming the existence of a succinct noninteractive argument of knowledge (SNARK), we construct a noninteractive SPARK that also preserves the space complexity of the underlying computation up to \( \mathrm{poly}\hspace{2.0pt}\log (T\cdot p) \) factors. We also show the following applications of noninteractive SPARKs. First, they immediately imply delegation protocols with near optimal prover (parallel) running time. This, in turn, gives a way to construct verifiable delay functions (VDFs) from any sequential function. When the sequential function is also memoryhard, this yields the first construction of a memoryhard VDF.more » « less