Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR96-065 | 7th May 1997 00:00

A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence Revision of: TR96-065

RSS-Feed

Abstract:

We present a probabilistic public key cryptosystem which is
secure unless the following worst-case lattice problem can be solved in
polynomial time:
"Find the shortest nonzero vector in an n dimensional lattice
L where the shortest vector v is unique in the sense that any other
vector whose length is at most a constant power of n times the length
of v, is parallel to v ."


Paper:

TR96-065 | 13th December 1996 00:00

A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence


Abstract:

We present a probabilistic public key cryptosystem which is
secure unless the following worst-case lattice problem can be solved in
polynomial time:
"Find the shortest nonzero vector in an n dimensional lattice
L where the shortest vector v is unique in the sense that any other
vector whose length is at most a constant power of n times the length
of v, is parallel to v ."


Comment(s):

Comment #1 to TR96-065 | 9th May 1997 08:18

Correction Comment on: TR96-065





Comment #1
Authors: Miklos Ajtai, Cynthia Dwork
Accepted on: 9th May 1997 08:18
Downloads: 2264
Keywords: 


Abstract:

Shai Halevi has pointed out an error in the proof of
Lemma 3.1 in the first version of the paper. In the revised (second)
version we present a corrected proof.




ISSN 1433-8092 | Imprint