Cryptology ePrint Archive: Report 2017/301

Limits on the Locality of Pseudorandom Generators and Applications to Indistinguishability Obfuscation

Alex Lombardi and Vinod Vaikuntanathan

Abstract: Lin and Tessaro (ePrint 2017) recently proposed indistinguishability obfuscation (IO) and functional encryption (FE) candidates and proved their security based on two assumptions: a standard assumption on bilinear maps and a non-standard assumption on ``Goldreich-like'' pseudorandom generators. In a nutshell, their second assumption requires the existence of pseudorandom generators $G:[q]^n \rightarrow \{0,1\}^m$ for some $\mathsf{poly}(n)$-size alphabet $q$, each of whose output bits depend on at most two input alphabet symbols, and which achieve sufficiently large stretch. We show polynomial-time attacks against such generators, invalidating the security of the IO and FE candidates. Our attack uses tools from the literature on two-source extractors (Chor and Goldreich, SICOMP 1988) and efficient refutation of random $\mathsf{2}$-$\mathsf{XOR}$ instances (Charikar and Wirth, FOCS 2004).

Category / Keywords: Foundations, Local PRGs, Goldreich's PRG, Indistinguishability Obfuscation

Original Publication (with minor differences): IACR-TCC-2017

Date: received 6 Apr 2017, last revised 7 Oct 2017

Contact author: alexjl at mit edu

Available format(s): PDF | BibTeX Citation

Version: 20171008:013126 (All versions of this report)

Short URL: ia.cr/2017/301

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]