__
TR96-007 | 29th January 1996 00:00
__

#### Generating Hard Instances of Lattice Problems

**Abstract:**
We give a random class of n dimensional lattices so that, if

there is a probabilistic polynomial time algorithm which finds a short

vector in a random lattice with a probability of at least 1/2

then there is also a probabilistic polynomial time algorithm which

solves the following three lattice problems in every n dimensional

lattice with a probability exponentially close to one. (1) Find the

length of a shortest nonzero vector in an n-dimensional lattice,

approximately, up to a polynomial factor. (2) Find the shortest nonzero

vector in an n-dimensional lattice L where the shortest vector

is unique in the sense that any other vector whose length is only

a polynomial times longer, is parallel to it. (3) Find a basis in the

lattice L whose length is the smallest possible up to a polynomial

factor, where the length of a basis is the maximum of the lengths

of its elements.

__
Comment #1 to TR96-007 | 8th February 1996 08:05
__
#### Corrected Proof of Lemma 4. Comment on: TR96-007

**Abstract:**
It has been pointed out by several readers that the proof

of Lemma 4 is incorrect. A corrected version of the proof is given

here and the sketch of an alternative proof. The lemma states that

if there is a linearly independent set with maximal vector length M

then there is a basis of length nM.