Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-159 | 11th September 2018 19:14

Expander-Based Cryptography Meets Natural Proofs


Authors: Igor Carboni Oliveira, Rahul Santhanam, Roei Tell
Publication: 12th September 2018 00:03
Downloads: 111


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.

ISSN 1433-8092 | Imprint