Welcome to the resource topic for 2017/301
Title:
Limits on the Locality of Pseudorandom Generators and Applications to Indistinguishability Obfuscation
Authors: Alex Lombardi, 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).
ePrint: https://eprint.iacr.org/2017/301
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .