Oded's choices (Nr. 254)

Does the Choice of Expander Matter for Expander-Based One-way Function?

Comments on a paper by Igor Carboni Oliveira, Rahul Santhanam, and Roei Tell.

Brief background

In 2000, I proposed a family of candidate one-way functions based on expander graphs, where the expanders "are used to determine a sequence of small overlapping subsets of input bits, to which a hard-wired random predicate is applied" (sic). Hence, the conjectured difficulty of inverting such functions is rooted in the relation between these small subsets (specifically, the fact that the collection of subsets is expanding), whereas the predicate was only required to be ``non-degenerate'' (in an unspecified sense that certainly rules out being oblivious of some of its bits and being linear). Interpreting small as constant-size yields a function in NC0 (i.e., constant locality).

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 biased predicate is not secure (i.e., the corresponding function can be inverted). Needless to say, unbiased 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.)

The current paper

The work of Oliveira, Santhanam, and Tell puts forward the possibility that the choice of the expander does matter. They actually show that it is either the case that some expanders should be avoided or that predicates of relatively low circuit complexity should be avoided, where the latter possibility is also a novelty in this area (since the intuition was that the predicate should only avoid "structural"/"algebraic" weaknesses). The above holds in the regime of quasi-polynomial stretch, which is believed to be similar to the regime of polynomial stretch (although the fact that the authors cannot prove this result in the latter regime is a bit alarming and calls for subsequent research; note, however, that they do have conditional results for the latter regime).

(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).)

The original title and abstract

The forgoing paper appears as ECCC TR18-159 under the title Expander-Based Cryptography Meets Natural Proofs. The original abstract reads as follows.

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:

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).
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.
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.