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