Limits on the Locality of Pseudorandom Generators and Applications to Indistinguishability Obfuscation

Alex Lombardi, Vinod Vaikuntanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

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 → {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).

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 15th International Conference, TCC 2017, Proceedings
EditorsYael Kalai, Leonid Reyzin
PublisherSpringer Verlag
Pages119-137
Number of pages19
ISBN (Print)9783319704999
DOIs
StatePublished - 2017
Externally publishedYes
Event15th International Conference on Theory of Cryptography, TCC 2017 - Baltimore, United States
Duration: Nov 12 2017Nov 15 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10677 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other15th International Conference on Theory of Cryptography, TCC 2017
Country/TerritoryUnited States
CityBaltimore
Period11/12/1711/15/17

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Limits on the Locality of Pseudorandom Generators and Applications to Indistinguishability Obfuscation'. Together they form a unique fingerprint.

Cite this