Content deleted Content added
m task, replaced: Twenty-first → Twenty-First, twenty-eighth → Twenty-Eighth, twenty-ninth → Twenty-Ninth |
m →Algorithms for the Euclidean norm: clean up, replaced: Forty-s → Forty-S (2) |
||
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|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|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|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.|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|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=A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations|journal=Proceedings of the Forty-
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.|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>.
| |||