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

Available format(s)
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
See all versions
Short URL
https://ia.cr/2017/301

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.