Paper 2017/277

Minimizing the Complexity of Goldreich's Pseudorandom Generator

Alex Lombardi and Vinod Vaikuntanathan

Abstract

In the study of cryptography in NC0, it was previously known that Goldreich's candidate pseudorandom generator (PRG) is insecure when instantiated with a predicate P in 4 or fewer variables, if one wants to achieve polynomial stretch (that is, stretching n bits to n1+ϵ bits for some constant ϵ>0). The current standard candidate predicate for this setting is the ``tri-sum-and'' predicate TSA(x)=XOR3AND2(x)=x1x2x3x4x5, yielding a candidate PRG of locality 5. Moreover, Goldreich's PRG, when instantiated with TSA as the predicate, is known to be secure against several families of attacks, including F2-linear attacks and attacks using SDP hierarchies such as the Lasserre/Parrilo sum-of-squares hierarchy. However, it was previously unknown if is an ``optimal'' predicate according to other complexity measures: in particular, decision tree (DT-)complexity (i.e., the smallest depth of a binary decision tree computing ) and -degree (i.e., the degree of as a polynomial over ), which are important measures of complexity in cryptographic applications such as the construction of an indistinguishability obfuscation scheme. In this work, we ask: Can Goldreich's PRG be instantiated with a predicate with DT-complexity or -degree less than ? We show that this is indeed possible: we give a candidate predicate for Goldreich's PRG with DT-complexity and -degree ; in particular, this candidate PRG therefore has the property that every output bit is a degree 3 polynomial in its input. Moreover, Goldreich's PRG instantiated with our predicate has security properties similar to what is known for , namely security against -linear attacks and security against attacks from SDP hierarchies such as the Lasserre/Parrilo sum-of-squares hierarchy. We also show that all predicates with either DT-complexity less than or -degree less than yield insecure PRGs, so our candidate predicate simultaneously achieves the best possible locality, DT-complexity, -degree, and -degree according to all known attacks.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Contact author(s)
alexjl @ mit edu
History
2017-03-27: received
Short URL
https://ia.cr/2017/277
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/277,
      author = {Alex Lombardi and Vinod Vaikuntanathan},
      title = {Minimizing the Complexity of Goldreich's Pseudorandom Generator},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/277},
      year = {2017},
      url = {https://eprint.iacr.org/2017/277}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.