Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-097 | 8th October 2007 00:00

The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.

RSS-Feed




TR07-097
Authors: Miklos Ajtai, Cynthia Dwork
Publication: 11th October 2007 07:18
Downloads: 4527
Keywords: 


Abstract:

We describe a public-key cryptosystem with worst-case/average case
equivalence. The cryptosystem has an amortized plaintext to
ciphertext expansion of $O(n)$, relies on the hardness of the
$\tilde O(n^2)$-unique shortest vector problem for lattices, and
requires a public key of size at most $O(n^4)$ bits. The new
cryptosystem generalizes a conceptually simple modification of the
``Ajtai-Dwork'' cryptosystem. We provide a unified treatment of the
two cryptosystems.



ISSN 1433-8092 | Imprint