Lattice problem: Difference between revisions

Revision as of 01:13, 10 November 2020

Revision as of 20:57, 1 December 2020

Line 18:

=== Algorithms for the Euclidean norm ===

To solve the exact version of the SVP under the Euclidean norm, several different approaches are known, which can be split into two classes: algorithms requiring superexponential time (<math>2^{\omega(n)}</math>) and <math>\operatorname{poly}(n)</math> memory, and algorithms requiring both exponential time and space (<math>2^{\Theta(n)}</math>) in the lattice dimension. The former class of algorithms most notably includes lattice enumeration<ref>{{Cite book|last=Kannan|first=Ravi|date=1983|title=Improved Algorithms for Integer Programming and Related Lattice Problems|journal=Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing|series=STOC '83|___location=New York, NY, USA|publisher=ACM|pages=193–206|doi=10.1145/800061.808749|isbn=978-0897910996}}</ref><ref name=":0" /><ref>{{Cite book|last=Gama|first=Nicolas|last2=Nguyen|first2=Phong Q.|last3=Regev|first3=Oded|date=2010-05-30|title=Lattice Enumeration Using Extreme Pruning|journal=Advances in Cryptology – EUROCRYPT 2010|volume=6110|language=en|publisher=Springer, Berlin, Heidelberg|pages=257–278|doi=10.1007/978-3-642-13190-5_13|series=Lecture Notes in Computer Science|isbn=978-3-642-13189-9}}</ref> and random sampling reduction,<ref>{{Cite book|last=Schnorr|first=Claus Peter|date=2003-02-27|title=Lattice Reduction by Random Sampling and Birthday Methods|journal=Stacs 2003|volume=2607|language=en|publisher=Springer, Berlin, Heidelberg|pages=145–156|doi=10.1007/3-540-36494-3_14|isbn=978-3540364948|series=Lecture Notes in Computer Science|citeseerx=10.1.1.137.4293}}</ref><ref>{{Cite book|last=Aono|first=Yoshinori|last2=Nguyen|first2=Phong Q.|date=2017-04-30|title=Random Sampling Revisited: Lattice Enumeration with Discrete Pruning|journal=Advances in Cryptology – EUROCRYPT 2017|volume=10211|language=en|publisher=Springer, Cham|pages=65–102|doi=10.1007/978-3-319-56614-6_3|series=Lecture Notes in Computer Science|isbn=978-3-319-56613-9|url=https://hal.inria.fr/hal-01502051/file/Eprint-155.pdf}}</ref>, while the latter includes lattice sieving,<ref name=":1" /><ref>{{Cite book|last=Micciancio|first=Daniele|last2=Voulgaris|first2=Panagiotis|date=2010|title=Faster Exponential Time Algorithms for the Shortest Vector Problem|url=http://dl.acm.org/citation.cfm?id=1873601.1873720|journal=Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms|series=SODA '10|___location=Philadelphia, PA, USA|publisher=Society for Industrial and Applied Mathematics|pages=1468–1480|isbn=9780898716986}}</ref><ref>{{Cite book|title=Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms|last=Becker|first=A.|last2=Ducas|first2=L.|last3=Gama|first3=N.|last4=Laarhoven|first4=T.|date=2015-12-21|publisher=Society for Industrial and Applied Mathematics|series=Proceedings|pages=10–24|doi=10.1137/1.9781611974331.ch2|chapter = New directions in nearest neighbor searching with applications to lattice sieving|isbn = 978-1-61197-433-1}}</ref>, computing the Voronoi cell of the lattice,<ref name=":2" /><ref>{{Cite book|last=Micciancio|first=Daniele|last2=Voulgaris|first2=Panagiotis|date=2010|title=A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations|journal=Proceedings of the Forty-second ACM Symposium on Theory of Computing|series=STOC '10|___location=New York, NY, USA|publisher=ACM|pages=351–358|doi=10.1145/1806689.1806739|isbn=9781450300506|citeseerx=10.1.1.705.3304}}</ref>, and discrete Gaussian sampling.<ref>{{Cite book|last=Aggarwal|first=Divesh|last2=Dadush|first2=Daniel|last3=Regev|first3=Oded|last4=Stephens-Davidowitz|first4=Noah|date=2015|title=Solving the Shortest Vector Problem in 2N Time Using Discrete Gaussian Sampling: Extended Abstract|journal=Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing|series=STOC '15|___location=New York, NY, USA|publisher=ACM|pages=733–742|doi=10.1145/2746539.2746606|isbn=9781450335362}}</ref>. An open problem is whether algorithms for solving exact SVP exist running in single exponential time (<math>2^{O(n)}</math>) and requiring memory scaling polynomially in the lattice dimension.<ref>{{Cite web|url=http://cseweb.ucsd.edu/~daniele/LatticeLinks/SVP.html|title=Lattice Cryptography – Shortest Vector Problem|last=Micciancio|first=Daniele|date=2017-07-01}}</ref>.

To solve the γ-approximation version SVP_γ for <math>\gamma > 1</math> for the Euclidean norm, the best known approaches are based on using [[lattice basis reduction]]. For large <math>\gamma = 2^{\Omega(n)}</math>, the [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|Lenstra–Lenstra–Lovász (LLL) algorithm]] can find a solution in time polynomial in the lattice dimension. For smaller values <math>\gamma</math>, the Block Korkine-Zolotarev algorithm (BKZ)<ref>{{Cite journal|last=Schnorr|first=C. P.|date=1987-01-01|title=A hierarchy of polynomial time lattice basis reduction algorithms|url= |journal=Theoretical Computer Science|volume=53|issue=2|pages=201–224|doi=10.1016/0304-3975(87)90064-8|doi-access=free}}</ref><ref>{{Cite journal|last=Schnorr|first=C. P.|last2=Euchner|first2=M.|date=1994-08-01|title=Lattice basis reduction: Improved practical algorithms and solving subset sum problems|journal=Mathematical Programming|language=en|volume=66|issue=1–3|pages=181–199|doi=10.1007/bf01581144|issn=0025-5610|url=http://publikationen.ub.uni-frankfurt.de/files/4259/schnorr.pdf}}</ref><ref>{{Cite book|last=Chen|first=Yuanmi|last2=Nguyen|first2=Phong Q.|date=2011-12-04|title=BKZ 2.0: Better Lattice Security Estimates|journal=Advances in Cryptology – ASIACRYPT 2011|volume=7073|language=en|publisher=Springer, Berlin, Heidelberg|pages=1–20|doi=10.1007/978-3-642-25385-0_1|series=Lecture Notes in Computer Science|isbn=978-3-642-25384-3}}</ref> is commonly used, where the input to the algorithm (the blocksize <math>\beta</math>) determines the time complexity and output quality: for large approximation factors <math>\gamma</math>, a small block size <math>\beta</math> suffices, and the algorithm terminates quickly. For small <math>\gamma</math>, larger <math>\beta</math> are needed to find sufficiently short lattice vectors, and the algorithm takes longer to find a solution. The BKZ algorithm internally uses an exact SVP algorithm as a subroutine (running in lattices of dimension at most <math>\beta</math>), and its overall complexity is closely related to the costs of these SVP calls in dimension <math>\beta</math>.