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+\epsilon}$ bits for some constant $\epsilon>0$). The current standard candidate predicate for this setting is the ``trisumand'' predicate $\text{TSA}(x) = \text{XOR}_3 \oplus \text{AND}_2(x) = x_1\oplus x_2\oplus x_3\oplus x_4x_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 sumofsquares hierarchy. However, it was previously unknown if $\text{TSA}$ 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 $P$) and $\mathbb Q$degree (i.e., the degree of $P$ as a polynomial over $\mathbb Q$), 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 DTcomplexity or $\mathbb Q$degree less than $5$? We show that this is indeed possible: we give a candidate predicate for Goldreich's PRG with DTcomplexity $4$ and $\mathbb Q$degree $3$; 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 $\text{TSA}$, namely security against $\mathbb F_2$linear attacks and security against attacks from SDP hierarchies such as the Lasserre/Parrilo sumofsquares hierarchy. We also show that all predicates with either DTcomplexity less than $4$ or $\mathbb Q$degree less than $3$ yield insecure PRGs, so our candidate predicate simultaneously achieves the best possible locality, DTcomplexity, $\mathbb Q$degree, and $\mathbb F_2$degree according to all known attacks.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Contact author(s)
 alexjl @ mit edu
 History
 20170327: received
 Short URL
 https://ia.cr/2017/277
 License

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}, note = {\url{https://eprint.iacr.org/2017/277}}, url = {https://eprint.iacr.org/2017/277} }