Welcome to the resource topic for 2017/277
Title:
Minimizing the Complexity of Goldreich’s Pseudorandom Generator
Authors: Alex Lombardi, 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 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_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 sum-of-squares 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 DT-complexity or \mathbb Q-degree less than 5? We show that this is indeed possible: we give a candidate predicate for Goldreich’s PRG with DT-complexity 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 sum-of-squares hierarchy. We also show that all predicates with either DT-complexity less than 4 or \mathbb Q-degree less than 3 yield insecure PRGs, so our candidate predicate simultaneously achieves the best possible locality, DT-complexity, \mathbb Q-degree, and \mathbb F_2-degree according to all known attacks.
ePrint: https://eprint.iacr.org/2017/277
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .