TY - GEN
T1 - Limits on the Locality of Pseudorandom Generators and Applications to Indistinguishability Obfuscation
AU - Lombardi, Alex
AU - Vaikuntanathan, Vinod
N1 - Funding Information:
A. Lombardi—Supported by an Akamai Presidential Fellowship and the grants of the second author. V. Vaikuntanathan—Research supported in part by NSF Grants CNS-1350619 and CNS-1414119, Alfred P. Sloan Research Fellowship, Microsoft Faculty Fellowship, the NEC Corporation, a Steven and Renee Finn Career Development Chair from MIT. This work was also sponsored in part by the Defense Advanced Research Projects Agency (DARPA) and the U.S. Army Research Office under contracts W911NF-15-C-0226 and W911NF-15-C-0236.
Publisher Copyright:
© 2017, International Association for Cryptologic Research.
PY - 2017
Y1 - 2017
N2 - 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 → {0,1}m for some poly(n) -size alphabet q, each of whose output bits depend on at most two in put 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 2-XOR instances (Charikar and Wirth, FOCS 2004).
AB - 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 → {0,1}m for some poly(n) -size alphabet q, each of whose output bits depend on at most two in put 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 2-XOR instances (Charikar and Wirth, FOCS 2004).
UR - http://www.scopus.com/inward/record.url?scp=85034266006&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85034266006&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-70500-2_5
DO - 10.1007/978-3-319-70500-2_5
M3 - Conference contribution
AN - SCOPUS:85034266006
SN - 9783319704999
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 119
EP - 137
BT - Theory of Cryptography - 15th International Conference, TCC 2017, Proceedings
A2 - Kalai, Yael
A2 - Reyzin, Leonid
PB - Springer Verlag
T2 - 15th International Conference on Theory of Cryptography, TCC 2017
Y2 - 12 November 2017 through 15 November 2017
ER -