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)