Public Key Cryptography from Different Assumptions

Boaz Barak; Avi Wigderson

Paper 2008/335

Public Key Cryptography from Different Assumptions

Boaz Barak and Avi Wigderson

Abstract

We construct a new public key encryption based on two assumptions: 1) One can obtain a pseudorandom generator with small locality by connecting the outputs to the inputs using any sufficiently good unbalanced expander. 2) It is hard to distinguish between a random graph that is such an expander and a random graph where a (planted) random logarithmic-sized subset S of the outputs is connected to fewer than |S| inputs. The validity and strength of the assumptions raise interesting new algorithmic and pseudorandomness questions, and we explore their relation to the current state-of-art.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Contact author(s): boaz @ cs princeton edu
History: 2008-08-03: received
Short URL: https://ia.cr/2008/335
License: CC BY

BibTeX

@misc{cryptoeprint:2008/335,
      author = {Boaz Barak and Avi Wigderson},
      title = {Public Key Cryptography from Different Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2008/335},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/335}},
      url = {https://eprint.iacr.org/2008/335}
}