In 2009, Bogdanov and Qiao studied a generalization of the foregoing construction in which unbalanced expanders are used (and so the function is stretching rather than length-preserving). They showed that in this regime (even with linear stretch), using a unbiased predicate is not secure (i.e., the corresponding function can be inverted). Needless to say, biased predicates are a must if one conjectures that the construction yields a pseudorandom generator.

Subsequent works have focused on the regime of constant locality and polynomial stretch, enlarged the set of (bad) predicates that should be avoided, and related the security of the construction as a one-way function to its security as a pseudorandom generator (see, e.g., a survey of Applebaum, which is already not updated, as well as a more recent work of Applebaum and Raykov).

In all of these works, the possibility that
the choice of the expander actually matters never arises.
Many of these works refer to a random expander,
but it seems that this is done in order to allow for their analysis.
Furthermore, the foregoing
work of Applebaum and Raykov formulates their discussion
by explicitly stating assumptions that refer to *any expander*
(i.e., only refer to its expansion parameters).
Also, the fact that they study polynomial stretch
and polynomial-time security does not seem crucial;
it is rather viewed as an adaptation of the standard conventions
of cryptographic and complexity theoretic research
(which focus on polynomials as archetypical slowly-growing functions).
(The only caveat is that the stretch should be significantly smaller
than the number of different $d$-subsets, where $d$ is the locality.)

(I still believe that the regime of length-preserving functions (i.e., no stretch) is different from the regime of linear (let alone polynomial) stretch, but that's besides the point: The regimes of polynomial and quasi-polynomial stretch are interesting per se. Furthermore, it is interesting to study whether there are actually similar or fundamentally different.)

(Let me also comment that prior results have indicated that the predicate should not be correlated with the XOR of few of its inputs (i.e., its ``low'' Fourier coefficients must be zero). Hence, predicates computed by relatively small AC0 circuits should be avoided for "structural"/"algebraic" reasons. In contrast, the notion of "low circuit complexity" that underlies the aforementioned result of the current paper refers to the size of AC0 circuits with parity gates (i.e., to predicates that are not necessarily correlated with the XOR of few of their inputs).)

We introduce new forms of attack on expander-based cryptography, and in particular on Goldreich's pseudorandom generator and one-way function. Our attacks exploit low circuit complexity of the underlying expander's neighbor function and/or of the local predicate. Our two key conceptual contributions are:We prove two types of technical results that support the above conceptual messages. First, we unconditionally break Goldreich's PRG when instantiated with a specific expander (whose existence we prove), for a class of predicates that match the parameters of the currently-best ``hard'' candidates, in the regime of quasi-polynomial stretch. Secondly, conditioned on the existence of expanders whose neighbor functions have extremely low circuit complexity, we present attacks on Goldreich's generator in the regime of polynomial stretch. As one corollary, conditioned on the existence of the foregoing expanders, we show that either the parameters of natural properties for several constant-depth circuit classes cannot be improved, even mildly; or Goldreich's generator is insecure in the regime of a large polynomial stretch, regardless of the predicate used.

- The security of Goldreich's PRG and OWF hinges, at least in some settings, on the circuit complexity of the underlying expander's neighbor function and of the local predicate. This sharply diverges from previous works, which focused on the expansion properties of the underlying expander and on the algebraic properties of the predicate.
- We uncover new connections between long-standing open problems: Specifically, we tie the security of Goldreich's PRG and OWF both to the existence of unbalanced lossless expanders with low-complexity neighbor function, and to limitations on circuit lower bounds (i.e., natural proofs).
In particular, our results further motivate the investigation of average-case lower bounds against DNF-XOR circuits of exponential size, and of the parameters that can be achieved by affine/local unbalanced expanders.

Back to list of Oded's choices.