TY - GEN
T1 - Limits on the Locality of Pseudorandom Generators and Applications to Indistinguishability Obfuscation
AU - Lombardi, Alex
AU - Vaikuntanathan, Vinod
N1 - 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 -