Generating hard instances of lattice problems

Abstract

We give a random class of lattices in Zn whose elements can be generated together with a short vector in them 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 Zn 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 nc||ν|| is parallel to ν, where c is a sufficiently large absolute constant. (3) Find a basis b1,..., bn in the n-dimensional lattice L whose length, defined as max ni=1 is the smallest possible up to a polynomial factor. We get the following corollaries: if for any of the mentioned worst-case problems there is no polynomial time probabilistic solution then (a) there is a one-way function (b) for any fixed 1/2 > ∈ > 0 there is a polynomial time computable function r(m) with m∈ < log r(m) ≤ m2∈, so that the randomized subset sum problem: Σmi=1 aixi (mod r(m)), xi = 0,1 for i = 1,..., m, has no polynomial time probabilistic solution, where ai i = 1,..., n and b are chosen at random with uniform distribution from the interval [1, r(m)].