ECCC-Report TR96-007https://eccc.weizmann.ac.il/report/1996/007Comments and Revisions published for TR96-007en-usThu, 08 Feb 1996 08:05:45 +0200
Comment 1
| Corrected Proof of Lemma 4. Comment on: TR96-007 |
Miklos Ajtai
https://eccc.weizmann.ac.il/report/1996/007#comment1It 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.
Thu, 08 Feb 1996 08:05:45 +0200https://eccc.weizmann.ac.il/report/1996/007#comment1
Paper TR96-007
| Generating Hard Instances of Lattice Problems |
Miklos Ajtai
https://eccc.weizmann.ac.il/report/1996/007 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.
Tue, 30 Jan 1996 08:16:20 +0200https://eccc.weizmann.ac.il/report/1996/007