Worst-Case to Average-Case Reductions Based on Gaussian Measures

摘要: We show that finding small solutions to random modular linear equations is at least as hard approximating several lattice problems in the worst case within a factor almost dimension of lattice. The we consider are shortest vector problem, independent vectors covering radius and guaranteed distance decoding problem (a variant well-known closest problem). approximation obtain $n \log^{O(1)} n$ for all four problems. This greatly improves on previous work subject starting from Ajtai’s seminal paper [Generating instances problems, Complexity Computations Proofs, Quad. Mat. 13, Dept. Math., Seconda Univ. Napoli, Caserta, Italy, 2004, pp. 1-32] up strongest previously known results by Micciancio [SIAM J. Comput., 34 (2004), 118-169]. Our also bring us closer limit where no longer be NP intersect coNP. main tools Gaussian measures lattices high-dimensional Fourier transform. start defining new parameter which determines amount noise one has add order get close uniform distribution. In addition yielding quantitatively much stronger results, use this allows simplify many complications work. technical contributions twofold. First, tight connections between existing parameters. One such important connection length set linearly vectors. Second, prove distribution obtains after adding following interesting property: when conditioning final value behaves respects like original vector. particular, its moments remain essentially unchanged.