Revision #1 Authors: Miklos Ajtai, Cynthia Dwork

Accepted on: 7th May 1997 00:00

Downloads: 2270

Keywords:

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 ."

TR96-065 Authors: Miklos Ajtai, Cynthia Dwork

Publication: 13th December 1996 10:10

Downloads: 2113

Keywords:

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 #1 Authors: Miklos Ajtai, Cynthia Dwork

Accepted on: 9th May 1997 08:18

Downloads: 1712

Keywords:

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.