Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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, Engineering and Medicine > 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:
DateEvent
2018Published
8 October 2018Accepted
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:
Project/Grant IDRIOXX Funder NameFunder ID
615075European Research Councilhttp://dx.doi.org/10.13039/501100000781
772839European Research Councilhttp://dx.doi.org/10.13039/501100000781
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:
  • Other Repository

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us