Search for: All records

Indistinguishability obfuscation, introduced by [Barak et. al. Crypto’2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new cryptographic goals and beyond. However, constructions of indistinguishability obfuscation have remained elusive, with all other proposals relying on heuristics or newly conjectured hardness assumptions. In this work, we show how to construct indistinguishability obfuscation from subexponential hardness of four well-founded assumptions. We prove: Suppose there exists any set of constants\(\tau \in (0,\infty), \delta \in (0,1), \epsilon \in (0,1)\)such that the sub-exponential security of the following assumptions hold:—the Learning With Errors (\(\mathsf {LWE}\)) assumption with subexponential modulus-to-noise ratio\(2^{k^\epsilon }\)and noises of magnitude polynomial ink, wherekis the dimension of the\(\mathsf {LWE}\)secret,—the Learning Parity with Noise (\(\mathsf {LPN}\)) assumption over general prime fields\(\mathbb {Z}_p\)with polynomially many\(\mathsf {LPN}\)samples and error rate\(1/\ell ^\delta\), where\(\ell\)is the dimension of the\(\mathsf {LPN}\)secret,—the existence of a Boolean Pseudo-Random Generator (\(\mathsf {PRG}\)) in\(\mathsf {NC}^0\)with stretch\(n^{1+\tau }\), wherenis the length of the\(\mathsf {PRG}\)seed,—the Decision Linear (\(\mathsf {DLIN}\)) assumption on symmetric bilinear groups of prime order. Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists. Furthermore, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomial-size circuits. 

We give a public key encryption scheme that is provably secure against poly-size adversaries, assuming nlogαn hardness of the standard planted clique conjecture, for any α ∈ (0,1), and a relatively mild hardness conjecture about noisy k-LIN over expanders that is not known to imply public-key encryption on its own. Both of our conjectures correspond to natural average-case variants of NP-complete problems and have been studied for multiple decades, with unconditional lower bounds supporting them in a variety of restricted models of computation. Our encryption scheme answers an open question in a seminal work by Applebaum, Barak, and Wigderson [STOC’10]. 

We study several strengthening of classical circular security assumptions which were recently introduced in four new lattice-based constructions of indistinguishability obfuscation: Brakerski-Dottling-Garg-Malavolta (Eurocrypt 2020), Gay-Pass (STOC 2021), Brakerski-Dottling-Garg-Malavolta (Eprint 2020) and Wee-Wichs (Eprint 2020). We provide explicit counterexamples to the 2-circular shielded randomness leakage assumption w.r.t. the Gentry-Sahai-Waters fully homomorphic encryption scheme proposed by Gay-Pass, and the homomorphic pseudorandom LWE samples conjecture proposed by Wee-Wichs. Our work suggests a separation between classical circular security of the kind underlying un-levelled fully-homomorphic encryption from the strengthened versions underlying recent iO constructions, showing that they are not (yet) on the same footing. Our counterexamples exploit the flexibility to choose specific implementations of circuits, which is explicitly allowed in the Gay-Pass assumption and unspecified in the Wee-Wichs assumption. Their indistinguishabilty obfuscation schemes are still unbroken. Our work shows that the assumptions, at least, need refinement. In particular, generic leakage-resilient circular security assumptions are delicate, and their security is sensitive to the specific structure of the leakages involved.