eprint.iacr.org will be offline for approximately an hour
for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between
April 12 and April 14, and some authors have been notified that they need to resubmit their papers.
You are looking at a specific version 20080803:031603 of this paper.
See the latest version.
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
