Minimizing the Complexity of Goldreich's Pseudorandom Generator
Alex Lombardi and Vinod Vaikuntanathan
Abstract
In the study of cryptography in , it was previously known that Goldreich's candidate pseudorandom generator (PRG) is insecure when instantiated with a predicate in or fewer variables, if one wants to achieve polynomial stretch (that is, stretching bits to bits for some constant ). The current standard candidate predicate for this setting is the ``tri-sum-and'' predicate , yielding a candidate PRG of locality . Moreover, Goldreich's PRG, when instantiated with TSA as the predicate, is known to be secure against several families of attacks, including -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.