Paper 2017/301
On the Non-Existence of Blockwise 2-Local PRGs with Applications to Indistinguishability Obfuscation
Alex Lombardi and Vinod Vaikuntanathan
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 \rightarrow \{0,1\}^m$ for some $\mathsf{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). Finally, we propose new ways to instantiate the Lin-Tessaro construction that do not immediately fall to our attacks. While we cannot say with any confidence that these modifications are secure, they certainly deserve further cryptanalysis.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Contact author(s)
- alexjl @ mit edu
- History
- 2017-10-08: revised
- 2017-04-09: received
- See all versions
- Short URL
- https://ia.cr/2017/301
- License
-
CC BY