Discrete Gaussian sampling reduces to CVP and SVP

DOI10.1137/1.9781611974331.CH121MaRDI QIDQ4575705zbMATH OpenOpenAlexFDO

Authors Noah Stephens-Davidowitz

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.07490

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Cryptography (94A60)

Abstract: The discrete Gaussian $D_{L-t,s}$ is the distribution that assigns to each vector $x$ in a shifted lattice $L-t$ probability proportional to $e^{-pi|x{|}^2/s^2}$. It has long been an important tool in the study of lattices. More recently, algorithms for discrete Gaussian sampling (DGS) have found many applications in computer science. In particular, polynomial-time algorithms for DGS with very high parameters $s$ have found many uses in cryptography and in reductions between lattice problems. And, in the past year, Aggarwal, Dadush, Regev, and Stephens-Davidowitz showed $2^{n+o(n)}$-time algorithms for DGS with a much wider range of parameters and used them to obtain the current fastest known algorithms for the two most important lattice problems, the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). Motivated by its increasing importance, we investigate the complexity of DGS itself and its relationship to CVP and SVP. Our first result is a polynomial-time dimension-preserving reduction from DGS to CVP. There is a simple reduction from CVP to DGS, so this shows that DGS is equivalent to CVP. Our second result, which we find to be more surprising, is a polynomial-time dimension-preserving reduction from centered DGS (the important special case when $t=0$) to SVP. In the other direction, there is a simple reduction from $gamma$-approximate SVP for any $gamma=Omega(sqrtn/logn)$, and we present some (relatively weak) evidence to suggest that this might be the best achievable approximation factor. We also show that our CVP result extends to a much wider class of distributions and even to other norms.

Recommendations

• Solving the shortest vector problem in 2ⁿ time using discrete Gaussian sampling (extended abstract)
• Sampling methods for shortest vectors, closest vectors and successive minima
• Gaussian sampling of lattices for cryptographic applications
• Sampling Methods for Shortest Vectors, Closest Vectors and Successive Minima
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures

Cited in

(11)

• Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
• Improved analysis of the reduction from BDD to uSVP
• Solving the shortest vector problem in 2ⁿ time using discrete Gaussian sampling (extended abstract)
• A note on discrete Gaussian combinations of lattice vectors
• Improved discrete Gaussian and Subgaussian analysis for lattice cryptography
• Hardness of bounded distance decoding on lattices in lp norms
• Just how hard are rotations of \(\mathbb{Z}^n\)? Algorithms and cryptography with the simplest lattice
• Revisiting the Sparsification Technique in Kannan’s Embedding Attack on LWE
• How to sample a discrete Gaussian (and more) from a random oracle
• Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all _p norms
• Gaussian sampling of lattices for cryptographic applications

This page was built for publication: Discrete Gaussian sampling reduces to CVP and SVP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575705)