The Library
Expander-based cryptography meets natural proofs
Tools
Tools
Tools
Oliveira, Igor C., Santhanam, Rahul and Tell, Roei (2018) Expander-based cryptography meets natural proofs. In: 10th Innovations in Theoretical Computer Science Conference (ITCS), San Diego, California, USA., 10-12 Jan 2019. Published in: Proceedings of the 33rd Computational Complexity Conference, 124 18:1-18:14. ISBN 9783959770958. ISSN 1868-8969. doi:10.4230/LIPIcs.ITCS.2019.18
|
PDF
WRAP-expander-based-cryptography-meets-natural-proof-Oliveira-2019.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (526Kb) | Preview |
Official URL: http://dx.doi.org/10.4230/LIPIcs.ITCS.2019.18
Abstract
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.
| Item Type: | Conference Item (Paper) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||
| Divisions: | Faculty of Science > Computer Science | |||||||||
| Library of Congress Subject Headings (LCSH): | Computational complexity, Cryptography, Random graphs, Random number generators | |||||||||
| Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||
| Journal or Publication Title: | Proceedings of the 33rd Computational Complexity Conference | |||||||||
| Publisher: | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik | |||||||||
| ISBN: | 9783959770958 | |||||||||
| ISSN: | 1868-8969 | |||||||||
| Official Date: | 2018 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 124 | |||||||||
| Page Range: | 18:1-18:14 | |||||||||
| DOI: | 10.4230/LIPIcs.ITCS.2019.18 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Open Access | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Conference Paper Type: | Paper | |||||||||
| Title of Event: | 10th Innovations in Theoretical Computer Science Conference (ITCS) | |||||||||
| Type of Event: | Conference | |||||||||
| Location of Event: | San Diego, California, USA. | |||||||||
| Date(s) of Event: | 10-12 Jan 2019 | |||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
