Kristiyan Haralambiev

Worst-case to Average-case Reductions based on Gaussian Measures

Daniele Micciancio and Oded Regev (SIAM J. Comput., 37(1):267–302, 
2007. Preliminary version in FOCS 2004.)

We show that finding small solutions to random modular linear equation
is at least as hard as approximating several lattice problems in the
worst case within a factor almost linear in the dimension of the
lattice. The lattice problems we consider are the shortest vector
problem, the shortest independent vectors problem, the covering radius
problem, and the guaranteed distance decoding problem (a variant of the
well known closest vector problem). The approximation factor we obtain
is n log^{O(1)}(n) for all three problems. This greatly improves on all
previous work on the subject starting from Ajtai's seminal paper [Quad.
Mat., 13 (2004), pp. 1-32], up to the strongest previously known results
by Micciancio [SIAM J. Comput., 34 (2004), pp. 118-169]. Our results
also bring us closer to the limit where the problems are no longer known
to be in NP intersected coNP.

Our main tools are Gaussian measures on lattices and the
high-dimensional Fourier transform. We start by defining a new lattice
parameter which determines the amount of Gaussian noise that one has to
add to a lattice in order to get close to a uniform distribution. In
addition to yielding quantitatively much stronger results, the use of
this parameter allows us to simplify many of the complications in
previous work.

Our technical contributions are two-fold. First, we show tight
connections between this new parameter and existing lattice parameters.
One such important connection is between this parameter and the length
of the shortest set of linearly independent vectors. Second, we prove
that the distribution that one obtains after adding Gaussian noise to
the lattice has the following interesting property: the distribution of
the noise vector when conditioning on the final value behaves in many
respects like the original Gaussian noise vector. In particular, its
moments remain essentially unchanged.