|
=== 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|chapter=Improved algorithms for integer programming and related lattice problems |title=Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83|date=1983|chapter=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|s2cid=18181112}}</ref><ref name=":0" /><ref>{{Cite book|last1=Gama|first1=Nicolas|last2=Nguyen|first2=Phong Q.|last3=Regev|first3=Oded|title=Advances in Cryptology – EUROCRYPT 2010 |chapter=Lattice Enumeration Using Extreme Pruning |date=2010-05-30|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|s2cid=1938519 }}</ref> and random sampling reduction,<ref>{{Cite book|last=Schnorr|first=Claus Peter|date=2003-02-27|chapter=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|last1=Aono|first1=Yoshinori|last2=Nguyen|first2=Phong Q.|title=Advances in Cryptology – EUROCRYPT 2017 |chapter=Random Sampling Revisited: Lattice Enumeration with Discrete Pruning |date=2017-04-30|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|s2cid=39082279 |url=https://hal.inria.fr/hal-01502051/file/Eprint-155.pdf}}</ref> while the latter includes lattice sieving,<ref name=":1" /><ref>{{Cite book|last1=Micciancio|first1=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|doi=10.1137/1.9781611973075.119|isbn=9780898716986|s2cid=90084}}</ref><ref>{{Cite book|title=Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms|last1=Becker|first1=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|last1=Micciancio|first1=Daniele|last2=Voulgaris|first2=Panagiotis|date=2010|title=AProceedings Deterministicof Singlethe Exponentialforty-second TimeACM Algorithmsymposium foron MostTheory Latticeof Problemscomputing Based|chapter=A ondeterministic Voronoisingle Cellexponential Computations|journal=Proceedingstime ofalgorithm thefor Forty-Secondmost ACMlattice Symposiumproblems based on Theoryvoronoi ofcell Computingcomputations |date=2010|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|s2cid=2449948}}</ref> and discrete Gaussian sampling.<ref>{{Cite book|last1=Aggarwal|first1=Divesh|last2=Dadush|first2=Daniel|last3=Regev|first3=Oded|last4=Stephens-Davidowitz|first4=Noah|datetitle=2015Proceedings of the forty-seventh annual ACM symposium on Theory of Computing |titlechapter=Solving the Shortest Vector Problem in 2N2 <sup>n</sup> Time Using Discrete Gaussian Sampling: Extended Abstract|journaldate=Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing2015|series=STOC '15|___location=New York, NY, USA|publisher=ACM|pages=733–742|doi=10.1145/2746539.2746606|isbn=9781450335362|s2cid=10214330|url=https://ir.cwi.nl/pub/24057}}</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<sub>γ</sub> 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|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|last1=Schnorr|first1=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|s2cid=15386054|issn=0025-5610|url=http://publikationen.ub.uni-frankfurt.de/files/4259/schnorr.pdf}}</ref><ref>{{Cite book|last1=Chen|first1=Yuanmi|last2=Nguyen|first2=Phong Q.|title=Advances in Cryptology – ASIACRYPT 2011 |chapter=BKZ 2.0: Better Lattice Security Estimates |date=2011-12-04|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>.
|
