Paper 2018/633
New Methods for Indistinguishability Obfuscation: Bootstrapping and Instantiation
Shweta Agrawal
Abstract
Constructing indistinguishability obfuscation (iO) [BGI+01] is a central open question in cryptography. We provide new methods to make progress towards this goal. Our contributions may be summarized as follows: 1. {\textbf Bootstrapping}. In a recent work, Lin and Tessaro [LT17] (LT) show that iO may be constructed using i) Functional Encryption (FE) for polynomials of degree $L$ , ii) Pseudorandom Generators (PRG) with blockwise locality $L$ and polynomial expansion, and iii) Learning With Errors (LWE). Since there exist constructions of FE for quadratic polynomials from standard assumptions on bilinear maps [Lin17, BCFG17], the ideal scenario would be to set $L = 2$, yielding iO from widely believed assumptions. Unfortunately, it was shown soon after [LV17,BBKK17] that PRG with block locality $2$ and the expansion factor required by the LT construction, concretely $\Omega(n\cdot 2^{b(3+\epsilon)})$, where $n$ is the input length and $b$ is the block length, do not exist. In the worst case, these lower bounds rule out 2block local PRG with stretch $\Omega(n \cdot 2^{b(2+\epsilon)})$. While [LV17,BBKK17] provided strong negative evidence for constructing iO based on bilinear maps, they could not rule out the possibility completely; a tantalizing gap has remained. Given the current state of lower bounds, the existence of 2 block local PRG with expansion factor $\Omega(n\cdot 2^{b(1+\epsilon)})$ remains open, although this stretch does not suffice for the LT bootstrapping, and is hence unclear to be relevant for iO. In this work, we improve the state of affairs as follows. (a) Weakening requirements on PRGs: In this work, we show that the narrow window of expansion factors left open by lower bounds do suffice for iO. We show a new method to construct FE for $NC_1$ from i) FE for degree L polynomials, ii) PRGs of block locality $L$ and expansion factor $\Omega(n\cdot2^{b(2+\epsilon)})$, and iii) LWE (or RLWE). Our method of bootstrapping is completely different from all known methods and does not go via randomizing polynomials. This reopens the possibility of realizing iO from $2$ block local PRG, SXDH on Bilinear maps and LWE. (b) Broadening class of sufficient PRGs: Our bootstrapping theorem may be instantiated with a broader class of pseudorandom generators than hitherto considered for iO, and may circumvent lower bounds known for the arithmetic degree of iO sufficient PRGs [LV17,BBKK17]; in particular, these may admit instantiations with arithmetic degree $2$, yielding iO with the additional assumptions of SXDH on Bilinear maps and LWE. In more detail, we may use the following two classes of PRG: i) NonBoolean PRGs: We may use pseudorandom generators whose inputs and outputs need not be Boolean but may be integers restricted to a small (polynomial) range. Additionally, the outputs are not required to be pseudorandom but must only satisfy a milder indistinguishability property. We tentatively propose initializing these PRGs using the multivariate quadratic assumption (MQ) which has been widely studied in the literature [MI88,Wol05,DY09] and against the general case of which, no efficient attacks are known. We note that our notion of non Boolean PRGs is qualitatively equivalent to the notion of $\Delta$ RGs defined in the concurrent work of Ananth, Jain, Khurana and Sahai [AJKS18] except that $\Delta$ RG are weaker, in that they allow the adversary to win the game with $1/poly$ probability whereas we require that the adversary only wins with standard negligible probability. By relying on the security amplification theorem of [AJKS18] in a black box way, our construction can also make do with the weaker notion of security considered by [AJKS18]. ii) Correlated Noise Generators: We introduce an even weaker class of pseudorandom generators, which we call correlated noise generators (CNG) which may not only be nonBoolean but are required to satisfy an even milder (seeming) indistinguishability property. (c) Assumptions and Efficiency. Our bootstrapping theorems can be based on the hardness of the Learning With Errors problem (LWE) or its ring variant (RLWE) and can compile FE for degree $L$ polynomials directly to FE for $NC_1$. Previous work compiles FE for degree $L$ polynomials to FE for $NC_0$ to FE for $NC_1$ to iO [LV16,Lin17,AS17,GGHRSW13]. 2. Instantiating Primitives. In this work, we provide the first direct candidate of FE for constant degree polynomials from new assumptions on lattices. Our construction is new and does not go via multilinear maps or graded encoding schemes as all previous constructions. In more detail, let $\mathcal{F}$ be the class of circuits with depth $d$ and output length $\ell$. Then, for any $f \in \mathcal{F}$, our scheme achieves ${\sf Time({keygen})} = O\big(poly(\kappa, f)\big)$, and ${\sf Time({encrypt})} =O(\vecx\cdot 2^d \cdot \poly(\kappa))$ where $\kappa$ is the security parameter. This suffices to instantiate the bootstrapping step above. Our construction is based on the ring learning with errors assumption (RLWE) as well as new untested assumptions on NTRU rings. We provide a detailed security analysis and discuss why previously known attacks in the context of multilinear maps, especially zeroizing attacks and annihilation attacks, do not appear to apply to our setting. We caution that the assumptions underlying our construction must be subject to rigorous cryptanalysis before any confidence can be gained in their security. However, their significant departure from known multilinear map based constructions make them, we feel, a potentially fruitful new direction to explore. Additionally, being based entirely on lattices, we believe that security against classical attacks will likely imply security against quantum attacks. Note that this feature is not enjoyed by instantiations that make any use of bilinear maps even if secure instances of weak PRGs, as defined by the present work, the followup by Lin and Matt [LM18] and the independent work by Ananth, Jain, Khurana and Sahai [AJKS18] are found.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 indistinguishability obfuscationfunctional encryptionbootstrappingdirect constructionlatticesNTRU
 Contact author(s)
 shweta a @ gmail com
 History
 20180817: revised
 20180626: received
 See all versions
 Short URL
 https://ia.cr/2018/633
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/633, author = {Shweta Agrawal}, title = {New Methods for Indistinguishability Obfuscation: Bootstrapping and Instantiation}, howpublished = {Cryptology ePrint Archive, Paper 2018/633}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/633}}, url = {https://eprint.iacr.org/2018/633} }