Indistinguishability Obfuscation from LPN over $$\mathbb {F}_p$$ , DLIN, and PRGs in NC $$^0$$

Indistinguishability Obfuscation from LPN over $$\mathbb {F}_p$$ , DLIN, and PRGs in NC $$^0$$

연구 분야: Analysis

학회: Annual International Conference on the Theory and Applications of Cryptographic Techniques

In this work, we study what minimal sets of assumptions suffice for constructing indistinguishability obfuscation ( ). We prove: Theorem(Informal): Assume sub-exponential security of the following assumptions: – the Learning Parity with Noise ( ) assumption over general prime fields with polynomially many samples and error rate , where k is the dimension of the secret, and is any constant; – the existence of a Boolean Pseudo-Random Generator ( ) in with stretch , where n is the length of the seed, and is any constant; – the Decision Linear ( ) assumption on symmetric bilinear groups of prime order. Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exists. Further, assuming only polynomial security of the aforementioned assumptions, there exists collusion resistant public-key functional encryption for all polynomial-size circuits. This removes the reliance on the Learning With Errors (LWE) assumption from the recent work of [Jain, Lin, Sahai STOC’21]. As a consequence, we obtain the first fully homomorphic encryption scheme that does not rely on any lattice-based hardness assumption. Our techniques feature a new notion of randomized encoding called Preprocessing Randomized Encoding (PRE), that essentially can be computed in the exponent of pairing groups. When combined with other new techniques, PRE gives a much more streamlined construction of while still maintaining reliance only on well-studied assumptions.