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: | , , |
|---|---|
| 格式: | Conference item |
| 出版: |
Dagstuhl Publishing
2018
|
| _version_ | 1826257733355044864 |
|---|---|
| author | Oliveira, I Santhanam, R Tell, R |
| author_facet | Oliveira, I Santhanam, R Tell, R |
| author_sort | Oliveira, I |
| collection | OXFORD |
| description | 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: 1) We put forward the possibility that the choice of expander matters in expander-based cryptography. In particular, using expanders whose neighbour function has low circuit complexity might compromise the security of Goldreich's PRG and OWF in certain settings. 2) We show that the security of Goldreich's PRG and OWF is closely related to two other long-standing problems: Specifically, 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 affine/local unbalanced lossless expanders and of average-case lower bounds against DNF-XOR circuits. 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. |
| first_indexed | 2024-03-06T18:22:50Z |
| format | Conference item |
| id | oxford-uuid:06e7e7d9-67f3-4d81-9aba-44e0870a6ed9 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:22:50Z |
| publishDate | 2018 |
| publisher | Dagstuhl Publishing |
| record_format | dspace |
| spelling | oxford-uuid:06e7e7d9-67f3-4d81-9aba-44e0870a6ed92022-03-26T09:04:47ZExpander-based cryptography meets natural proofsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:06e7e7d9-67f3-4d81-9aba-44e0870a6ed9Symplectic Elements at OxfordDagstuhl Publishing2018Oliveira, ISanthanam, RTell, RWe 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: 1) We put forward the possibility that the choice of expander matters in expander-based cryptography. In particular, using expanders whose neighbour function has low circuit complexity might compromise the security of Goldreich's PRG and OWF in certain settings. 2) We show that the security of Goldreich's PRG and OWF is closely related to two other long-standing problems: Specifically, 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 affine/local unbalanced lossless expanders and of average-case lower bounds against DNF-XOR circuits. 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. |
| spellingShingle | Oliveira, I Santhanam, R Tell, R Expander-based cryptography meets natural proofs |
| title | Expander-based cryptography meets natural proofs |
| title_full | Expander-based cryptography meets natural proofs |
| title_fullStr | Expander-based cryptography meets natural proofs |
| title_full_unstemmed | Expander-based cryptography meets natural proofs |
| title_short | Expander-based cryptography meets natural proofs |
| title_sort | expander based cryptography meets natural proofs |
| work_keys_str_mv | AT oliveirai expanderbasedcryptographymeetsnaturalproofs AT santhanamr expanderbasedcryptographymeetsnaturalproofs AT tellr expanderbasedcryptographymeetsnaturalproofs |