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.

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 » « lessFree, publiclyaccessible full text available May 1, 2024

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

Although the definition of sequential equilibrium can be applied without change to games of imperfect recall, doing so leads to arguably inappropriate results. We redefine sequential equilibrium so that the definition agrees with the standard definition in games of perfect recall while still giving reasonable results in games of imperfect recall. The definition can be viewed as trying to capture a notion of ex ante sequential equilibrium. The picture here is that players choose their strategies before the game starts and are committed to it, but they choose it in such a way that it remains optimal even off the equilibrium path. A notion of interim sequential equilibrium is also considered.more » « less

We show the existence of indistinguishability obfuscators (iO) for general circuits assuming subexponential security of: (a) the Learning with Errors (LWE) assumption (with subexponential modulusto noise ratio); (b) a circular security conjecture regarding the Gentry SahaiWaters’ (GSW) encryption scheme and a Packed version of Regev’s encryption scheme. The circular security conjecture states that a notion of leakageresilient security, that we prove is satisfied by GSW assuming LWE, is retained in the presence of an encrypted keycycle involving GSW and Packed Regev.more » « less