About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STOC 1996
Conference paper
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)].