Paper 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).

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in TCC 2017
Keywords
FoundationsLocal PRGsGoldreich's PRGIndistinguishability Obfuscation
Contact author(s)
alexjl @ mit edu
History
2017-10-08: revised
2017-04-09: received
See all versions
Short URL
https://ia.cr/2017/301
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/301,
      author = {Alex Lombardi and Vinod Vaikuntanathan},
      title = {Limits on the Locality of Pseudorandom Generators and Applications to Indistinguishability Obfuscation},
      howpublished = {Cryptology ePrint Archive, Paper 2017/301},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/301}},
      url = {https://eprint.iacr.org/2017/301}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.