Generating hard instances of lattice problems (extended abstract) 论文

摘要

. We give a random class of lattices in Z n 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 lattice in Z n 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 v is unique in the sense that any other vector whose length is at most n c kvk is parallel to v, where c is a sufficiently large absolute constant. (3) Find a basis b 1 ; :::; b n in the n-dimensional lattice L whose length, defined as max n i=1 kb i k, is the smallest possible up to a polynomial factor. A large number of the existing techniques of cryptography include the generation of a specific ins...