Vinod Vaikuntanathan, Massachusetts Institute of Technology

Abstract

Lin and Tessaro (Eprint 2017/250) recently proposed indistinguishability obfuscation and functional encryption candidates and proved their security based on a standard assumption on bilinear maps and a non-standard assumption on "Goldreich-like" pseudorandom generators (PRG). In a nutshell, they require the existence of pseudo-random generators G : Sigma^n to {0,1}^m for some poly(n)-size alphabet Sigma where each output bit depends on at most two input alphabet symbols, and which achieve sufficiently large stretch. We show a polynomial-time attack against such generators. Our attack uses tools from the literature on two-source extractors (Chor and Goldreich, SICOMP 1988) and efficient refutation of 2-CSPs over large alphabets (Allen, O'Donnell and Witmer, FOCS 2015).

Joint work with Alex Lombardi (MIT).

Slides    Video