2013 · 26 citations · 25 references
ComputingComputer ScienceMathematicsCryptographyDiscrete MathematicsTheory Of ComputationApproximation AlgorithmsApproximation MethodsComputational Number TheoryCryptographic ComplexityLattice-based CryptographyAverage-case ComplexityGaussian DistributionsLattice ReductionWorst-case To Average-case Reductions
The smoothing parameter η <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ε</sub> (L) of a Euclidean lattice L, introduced by Micciancio and Regev (FOCS'04; SICOMP'07), is (informally) the smallest amount of Gaussian noise that “smooths out” the discrete structure of L (up to error ε). It plays a central role in the best known worst-case/average-case reductions for lattice problems, a wealth of lattice-based cryptographic constructions, and (implicitly) the tightest known transference theorems for fundamental lattice quantities. In this work we initiate a study of the complexity of approximating the smoothing parameter to within a factor γ, denoted γ-GapSPP. We show that (for ε = 1/ poly(n)): . (2+o(1))-GapSPP ∈ AM, via a Gaussian analogue of the classic Goldreich-Goldwasser protocol (STOC'98); . (1 + o(1))-GapSPP ∈ coAM, via a careful application of the Goldwasser-Sipser (STOC'86) set size lower bound protocol to thin shells in Rn; . (2 + o(1))-GapSPP E SZK ⊆ AM ∩ coAM (where SZK is the class of problems having statistical zero-knowledge proofs), by constructing a suitable instance-dependent commitment scheme (for a slightly worse o(1)-term); . (1 + o(1))-GapSPP can be solved in deterministic 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(n)</sup> polylog(1/ε) time and 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(n)</sup> space. As an application, we demonstrate a tighter worst-case to average-case reduction for basing cryptography on the worstcase hardness of the GapSPP problem, with Õ(√n) smaller approximation factor than the GapSVP problem. Central to our results are two novel, and nearly tight, characterizations of the magnitude of discrete Gaussian sums over L: the first relates these directly to the Gaussian measure of the Voronoi cell of L, and the second to the fraction of overlap between Euclidean balls centered around points of L.
25
Fully homomorphic encryption using ideal lattices
Craig Gentry · 2009 · 6.6K citations
Factoring polynomials with rational coefficients
A. K. Lenstra, H. W. Lenstra, László Lovász · Mathematische Annalen · 1982 · 4K citations · Full text
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · Journal of the ACM · 2009 · 2.2K citations
Efficient Fully Homomorphic Encryption from (Standard) LWE
Zvika Brakerski, Vinod Vaikuntanathan · 2011 · 1.5K citations