International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Public Key Cryptography from Different Assumptions

Authors:
Boaz Barak
Avi Wigderson
Download:
URL: http://eprint.iacr.org/2008/335
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2008-18012,
  title={Public Key Cryptography from Different Assumptions},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography /},
  url={http://eprint.iacr.org/2008/335},
  note={ boaz@cs.princeton.edu 14093 received 2 Aug 2008},
  author={Boaz Barak and Avi Wigderson},
  year=2008
}