Paper 2017/277

Minimizing the Complexity of Goldreich's Pseudorandom Generator

Alex Lombardi and Vinod Vaikuntanathan

Abstract

In the study of cryptography in ${\text{NC}}^0$, 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 $n^{1+ϵ}$ bits for some constant $ϵ>0$). The current standard candidate predicate for this setting is the ``tri-sum-and'' predicate $\text{TSA}(x)={\text{XOR}}_3\oplus {\text{AND}}_2(x)=x_1\oplus x_2\oplus x_3\oplus x_4{x}_5$, 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 ${\mathbb{F}}_2$-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.