In this work, we study the question of what set of simpletostate assumptions suffice for constructing functional encryption and indistinguishability obfuscation (IO), supporting all functions describable by polynomialsize circuits. Our work improves over the stateoftheart work of Jain, Lin, Matt, and Sahai (Eurocrypt 2019) in multiple dimensions. New Assumption: Previous to our work, all constructions of IO from simple assumptions required novel pseudorandomness generators involving LWE samples and constantdegree polynomials over the integers, evaluated on the error of the LWE samples. In contrast, Boolean pseudorandom generators (PRGs) computable by constantdegree polynomials have been extensively studied since the work of Goldreichmore »
Indistinguishability obfuscation from wellfounded assumptions.
Indistinguishability obfuscation, introduced by [Barak et. al. Crypto2001], 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 wellfounded assumptions. We prove:
Informal Theorem: Let πβ (0,β), πΏβ (0,1), πβ (0,1) be arbitrary constants. Assume subexponential security of the following assumptions:
 the Learning With Errors (LWE) assumption with subexponential modulustonoise ratio 2^{π^π} and noises of magnitude polynomial in π,where π is the dimension of the LWE secret,
 the Learning Parity with Noise (LPN) assumption over general prime fields Zπ with polynomially many LPN samples and error rate 1/β^πΏ ,where β is the dimension of the LPN secret,
 the existence of a Boolean PseudoRandom Generator (PRG) in NC0 with stretch π^{1+π}, where π is the length of the PRG seed,
 the Decision Linear (DLIN) assumption on symmetric bilinear groups of prime order.
Then, (subexponentially secure) indistinguishability obfuscation for all polynomialsize circuits exists. Further, assuming only polynomial security more »
 Award ID(s):
 1936825
 Publication Date:
 NSFPAR ID:
 10255461
 Journal Name:
 STOC
 Sponsoring Org:
 National Science Foundation
More Like this


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.

In a traitor tracing (TT) system for n users, every user has his/her own secret key. Content providers can encrypt messages using a public key, and each user can decrypt the ciphertext using his/her secret key. Suppose some of the n users collude to construct a pirate decoding box. Then the tracing scheme has a special algorithm, called π³ππΊπΌπΎ , which can identify at least one of the secret keys used to construct the pirate decoding box. Traditionally, the trace algorithm output only the βindexβ associated with the traitors. As a result, to use such systems, either a central mastermore »

We study several strengthening of classical circular security assumptions which were recently introduced in four new latticebased constructions of indistinguishability obfuscation: BrakerskiDottlingGargMalavolta (Eurocrypt 2020), GayPass (STOC 2021), BrakerskiDottlingGargMalavolta (Eprint 2020) and WeeWichs (Eprint 2020). We provide explicit counterexamples to the 2circular shielded randomness leakage assumption w.r.t. the GentrySahaiWaters fully homomorphic encryption scheme proposed by GayPass, and the homomorphic pseudorandom LWE samples conjecture proposed by WeeWichs. Our work suggests a separation between classical circular security of the kind underlying unlevelled fullyhomomorphic encryption from the strengthened versions underlying recent iO constructions, showing that they are not (yet) on the same footing. Ourmore »

In this work, we study the fascinating notion of outputcompressing randomized encodings for Turing Machines, in a shared randomness model. In this model, the encoder and decoder have access to a shared random string, and the efficiency requirement is, the size of the encoding must be independent of the running time and output length of the Turing Machine on the given input, while the length of the shared random string is allowed to grow with the length of the output. We show how to construct outputcompressing randomized encodings for Turing machines in the shared randomness model, assuming iO for circuitsmore »