**Author:**Daniele Micciancio

SIAM Journal on computing, 34(1):118-169, 2004.

[BibTeX] [Postscript] [PDF] [ doi:10.1137/S0097539703433511]

**Abstract:** Lattices have received considerable attention
as a potential source of computational hardness to be used in cryptography,
after a breakthrough result of Ajtai (STOC 1996) connecting the average-case
and worst-case complexity of various lattice problems. The purpose of this
paper is twofold. On the expository side, we present a rigorous self
contained proof of results along the lines of Ajtai's seminal work. At the
same time, we explore to what extent Ajtai's original results can be
quantitatively improved. As a by-product, we define a random class of
lattices such that computing short nonzero vectors in the class with
non-negligible probability is at least as hard as approximating the length of
the shortest nonzero vector in *any* n-dimensional lattice within
worst-case approximation factors gamma(n)=n^{3}omega(sqrt{log n log log n}).
This improves previously known best connection factor gamma(n)=n^{4+epsilon}
(Cai and Nerurkar, FOCS 1997) by more that omega(n). We also show how our
reduction implies the existence of collision resistant cryptographic hash
functions based on the worst-case inapproximability of the shortest vector
problem within factors gamma(n)= n^{3} omega(sqrt{log n log log n}).

In the process we distill various new lattice problems that might be of independent interest, related to the covering radius, the bounded distance decoding problem, approximate counting of lattice points inside convex bodies, and the efficient construction of lattices with good geometric and algorithmic decoding properties. We also show how further investigation of these new lattice problems might lead to even stronger connections between the average-case and worst-case complexity of the shortest vector problem, possibly leading to connection factors as low as gamma(n)=n^{1.5} omega(log n)

**Preliminaty versions:**

Daniele Micciancio, Improved cryptographic hash functions with worst-case/average-case connection, Proceedings of the 34th Annual ACM Symposium on Theory of Computing - STOC 2002. May 19-21. Montreal, Canada. pp. 609-618.

Daniele Micciancio, Improved cryptographic hash functions with worst-case/average-case connection, IEEE Computational Complexity Conference - CCC 2002. May 21-23. Montreal, Canada. p. 5.