Expander-based cryptography meets natural proofs
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 con...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Published: |
Dagstuhl Publishing
2018
|