Lattice problem: Difference between revisions

Revision as of 05:18, 4 August 2022

Latest revision as of 10:52, 15 August 2025

(32 intermediate revisions by 17 users not shown)

Line 1:

{{Short description|Optimization problem in computer science}}

In [[computer science]], '''lattice problems''' are a class of [[Mathematical optimization|optimization]] problems related to mathematical objects called ''[[Lattice (group)|lattices]]''. The conjectured [[Intractable problem|intractability]] of such problems is central to the construction of secure [[Lattice-based cryptography|lattice-based cryptosystems]]: Latticelattice problems are an example of [[NP-hardness|NP-hard]] problems which have been shown to be [[Computational hardness assumption|average-case hard]], providing a test case for the security of cryptographic algorithms. In addition, some lattice problems which are worst-case hard can be used as a basis for extremely secure cryptographic schemes. The use of worst-case hardness in such schemes makes them among the very few schemes that are very likely secure even against [[quantum computers]]. For applications in such [[cryptosystems]], lattices over [[vector space|vector spaces]] (often <math>\mathbb{Q}^n</math>) or [[free module]]s (often <math>\mathbb{Z}^n</math>) are generally considered.

For all the problems below, assume that we are given (in addition to other more specific inputs) a [[Basis (linear algebra)|basis]] for the vector space ''V'' and a [[Norm (mathematics)|norm]] ''N''. The norm usually considered is the Euclidean norm [[Norm (mathematics)#Euclidean norm|''L''²]]. However, other norms (such as [[Norm (mathematics)#p-norm|''L''^''p'']]) are also considered and show up in a variety of results.<ref>{{cite journal |author-link=Subhash Khot |first=Subhash |last=Khot |title=Hardness of approximating the shortest vector problem in lattices |journal=J. ACM |volume=52 |issue=5 |year=2005 |pages=789–808 |doi=10.1145/1089023.1089027 |s2cid=13438130 }}</ref>

Throughout Letthis article, let <math>\lambda(L)</math> denote the length of the shortest non-zero vector in the lattice ''L'',: that is,

: <math>\lambda(L) = \min_{v \in L \smallsetminus \{\mathbf{0}\}} \|v\|_N.</math>

== Shortest vector problem (SVP) ==

[[File:SVP.svg|thumb|left|This is an illustration of the shortest vector problem (basis vectors in blue, shortest vector in red).]]

In the SVP, a [[Basis (linear algebra)|basis]] of a [[vector space]] ''V'' and a [[Norm (mathematics)|norm]] ''N'' (often [[Norm (mathematics)#Euclidean norm|''L''²]]) are given for a lattice ''L'' and one must find the shortest non-zero vector in ''V'', as measured by ''N'', in ''L''. In other words, the algorithm should output a non-zero vector ''v'' such that <math>N({{tmath|1= \{{!}}v)\{{!}}_N=\lambda(L)</math> }}.

In the γ-approximation version SVP_γ, one must find a non-zero lattice vector of length at most <math>\gamma \cdot \lambda(L)</math> for given <math>{{tmath|1= \gamma \geq 1</math> }}.

=== Hardness results ===

The exact version of the problem is only known to be [[NP-hard]] for randomized reductions.<ref name="ajtai" /><ref name="Ajtai 1998 10–19">{{cite book |first=Miklós |last=Ajtai |chapter=The shortest vector problem in ''L''₂'' is ''NP''-hard for randomized reductions |title=Proceedings of the thirtieth annual ACM symposium on Theory of computing |___location=Dallas, Texas, United States |publisher=ACM |year=1998 |pages=10–19 |doi=10.1145/276698.276705 |isbn=9780897919623978-0-89791-962-3 |s2cid=4503998 |chapter-url=http://portal.acm.org/citation.cfm?id=276705 }}</ref> By contrast, the corresponding problem with respect to the [[uniform norm]] is known to be [[NP-hard]].<ref name="vEB">{{cite journal |url=http://staff.science.uva.nl/~peter/vectors/mi8104c.html |first=Peter |last=van Emde Boas |year=1981 |title=Another NP-complete problem and the complexity of computing short vectors in a lattice |publisher=University of Amsterdam, Department of Mathematics, Netherlands |journal=Technical Report 8104 }}</ref>

By contrast, the corresponding problem with respect to the [[uniform norm]] is known to be [[NP-hard]].<ref name="vEB">{{cite journal |url=http://staff.science.uva.nl/~peter/vectors/mi8104c.html |first=Peter |last=van Emde Boas |year=1981 |title=Another NP-complete problem and the complexity of computing short vectors in a lattice |publisher=University of Amsterdam, Department of Mathematics, Netherlands |journal=Technical Report 8104 }}</ref>

=== 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 Algorithmsalgorithms for Integerinteger Programmingprogramming and Relatedrelated Latticelattice problems Problems|journaltitle=Proceedings of the Fifteenthfifteenth Annualannual ACM Symposiumsymposium on Theory of Computing|series=computing - STOC '83|date=1983|___location=New York, NY, USA|publisher=ACM|pages=193–206|doi=10.1145/800061.808749|isbn=978-08979109960-89791-099-6|s2cid=18181112}}</ref><ref name=":0" /><ref>{{Cite book|last1=Gama|first1=Nicolas|last2=Nguyen|first2=Phong Q.|last3=Regev|first3=Oded|datetitle=Advances in Cryptology – EUROCRYPT 2010-05-30 |titlechapter=Lattice Enumeration Using Extreme Pruning |journaldate=Advances in Cryptology – EUROCRYPT 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 |chapter-url=https://hal.science/hal-01083526 }}</ref> and random sampling reduction,<ref>{{Cite book|last=Schnorr|first=Claus Peter|title=Stacs 2003 |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-35403649483-540-36494-8|series=Lecture Notes in Computer Science|citeseerx=10.1.1.137.4293}}</ref><ref>{{Citecite book|last1=Aono|first1=Yoshinori|last2=Nguyen|first2=Phong Q.|datetitle=Advances in Cryptology – EUROCRYPT 2017-04-30 |titlechapter=Random Sampling Revisited: Lattice Enumeration with Discrete Pruning |journaldate=Advances in Cryptology – EUROCRYPT 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>{{Citecite bookconference|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|journalbook-title=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=9780898716986978-0-89871-698-6|s2cid=90084|doi-access=free|url-access=subscription}}</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|url=https://ir.cwi.nl/pub/23692 }}</ref> computing the Voronoi cell of the lattice,<ref name=":2" /><ref>{{Citecite 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=9781450300506978-1-4503-0050-6|citeseerx=10.1.1.705.3304|s2cid=2449948}}</ref> and discrete Gaussian sampling.<ref>{{Citecite 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 ⁿ 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=9781450335362978-1-4503-3536-2|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_γ for <math>\gamma > 1</math> for the Euclidean norm, the best known approaches are based on using [[lattice basis reduction]]. For large <math>{{tmath|1= \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.|datetitle=Advances in Cryptology – ASIACRYPT 2011-12-04 |titlechapter=BKZ 2.0: Better Lattice Security Estimates |journaldate=Advances in Cryptology – ASIACRYPT 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>{{tmath|1= \beta</math> }}.

==GapSVP==

The problem GapSVP_β consists of distinguishing between the instances of SVP in which the length of the shortest vector is at most <math>1</math> or larger than <math>{{tmath|1= \beta</math> }}, where <math>\beta</math> can be a fixed function of the dimension of the lattice <math>{{tmath|1= n</math> }}. Given a basis for the lattice, the algorithm must decide whether <math>\lambda(L) \leq 1</math> or <math>{{tmath|1= \lambda(L)>\beta</math> }}. Like other [[promise problem]]s, the algorithm is allowed to err on all other cases.

Yet another version of the problem is GapSVP_{ζ, γ} for some functions <math>\zeta,\gamma</math>ζ and γ. The input to the algorithm is a basis <math>B</math> and a number <math>d</math>. It is assured that all the vectors in the [[Gram–Schmidt orthogonalization]] are of length at least 1, and that <math>\lambda(L(B)) \leq \zeta(n) </math> and that <math>{{tmath|1= 1 \leq d \leq \zeta(n)/\gamma(n)</math> }}, where <math>n</math> is the dimension. The algorithm must accept if <math>{{tmath|1= \lambda(L(B)) \leq d</math> }}, and reject if <math>{{tmath|1= \lambda(L(B)) \geq \gamma(n). \cdot d</math> }}. For large <math>\zeta</math> (i.e. <math>{{tmath|1= \zeta(n)>2^{n/2}</math> }}), the problem is equivalent to GapSVP_γ because<ref>{{cite book |first=Chris |last=Peikert |chapter=Public-key cryptosystems from the worst-case shortest vector problem: extended abstract |title=Proceedings of the 41st annual ACM symposium on Theory of Computing |___location=Bethesda, MD, USA |publisher=ACM |year=2009 |pages=333–342 |doi=10.1145/1536414.1536461 |isbn=9781605585062978-1-60558-506-2 |s2cid=1864880 |url=https://drops.dagstuhl.de/opus/volltexte/2009/1892/ |chapter-url=http://portal.acm.org/citation.cfm?id=1536414.1536461 }}</ref> a preprocessing done using the [[LLL algorithm]] makes the second condition (and hence, <math>{{tmath|1= \zeta</math> }}) redundant.

== Closest vector problem (CVP) ==

[[File:CVP.svg|thumb|left|This is an illustration of the closest vector problem (basis vectors in blue, external vector in green, closest vector in red).]]

In CVP, a basis of a vector space ''V'' and a [[Metric (mathematics)|metric]] ''M'' (often [[Euclidean distance|''L''²]]) are given for a lattice ''L'', as well as a vector ''v'' in ''V'' but not necessarily in ''L''. It is desired to find the vector in ''L'' closest to ''v'' (as measured by ''M''). In the <math>\gamma</math>-approximation version CVP_γ, one must find a lattice vector at distance at most <math>\gamma</math>.

=== Relationship with SVP ===

The closest vector problem is a generalization of the shortest vector problem. It is easy to show that given an [[oracle machine|oracle]] for CVP_γ (defined below), one can solve SVP_γ by making some queries to the oracle.<ref>{{cite book |first1=Daniele |last1=Micciancio |author-link2=Shafi Goldwasser |first2=Shafi |last2=Goldwasser |title=Complexity of Lattice Problems |publisher=Springer |year=2002 }}</ref> The naive method to find the shortest vector by calling the CVP_γ oracle to find the closest vector to &nbsp;0 does not work because 0 is itself a lattice vector and the algorithm could potentially output &nbsp;0.

The reduction from SVP_γ to CVP_γ is as follows: Suppose that the input to the SVP_γ is the basis for lattice <math>B=[b_1,b_2,\ldots,b_n]</math>. Consider the basis <math>B^i=[b_1,\ldots,2b_i,\ldots,b_n]</math> and let <math>x_i</math> be the vector returned by {{nowrap|CVP_γ(''B''^''i'', ''b''_''i'')}}. The claim is that the shortest vector in the set <math>\{x_i-b_i\}</math> is the shortest vector in the given lattice.

=== Hardness results ===

Goldreich et al. showed that any hardness of SVP implies the same hardness for CVP.<ref>{{cite journal |first=O. |last=Goldreich |title=Approximating shortest lattice vectors is not harder than approximating closest lattice vectors |journal=Inf. Process. Lett. |volume=71 |issue=2 |year=1999 |pages=55–61 |doi=10.1016/S0020-0190(99)00083-6 |display-authors=etal}}</ref> Using [[Probabilistically checkable proof (complexity)|PCP]] tools, [[Sanjeev Arora|Arora]] et al. showed that CVP is hard to approximate within factor <math>2^{\log^{1-\epsilon}(n)}</math> unless <math>\operatorname{NP} \subseteq \operatorname{DTIME}(2^{\operatorname{poly}(\log n)})</math>.<ref>{{cite bookconference |first=Sanjeev |last=Arora |year=1993 |title=Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science |chapter=The hardness of approximate optima in lattices, codes, and systems of linear equations |journalbook-title=J. Comput. Syst. Sci. |volume=54 |issue=2 |year=1997 |pages=317–331 |doi=10.1109/SFCS.1993.366815 |display-authors=etal|isbn=978-0-8186-4370-5 |s2cid=44988406 }}</ref> Dinur et al. strengthened this by giving a NP-hardness result with <math>\epsilon=(\log \log n)^c</math> for <math>c<1/2</math>.<ref>{{cite journal |first=I. |last=Dinur |title=Approximating CVP to Within Almost-Polynomial Factors is NP-Hard |journal=Combinatorica |volume=23 |issue=2 |year=2003 |pages=205–243 |doi=10.1007/s00493-003-0019-y |s2cid=45754954 |display-authors=etal}}</ref>

=== Sphere decoding ===

Algorithms for CVP, especially the Fincke and Pohst variant,<ref name=":0">{{cite journal |last1=Fincke |first1=U. |last2=Pohst |first2=M. |title=Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis |journal=Math. Comp. |volume=44 |issue=170 |pages=463–471 |year=1985 |doi=10.1090/S0025-5718-1985-0777278-8 |doi-access=free }}</ref> have been used for data detection in multiple-input multiple-output ([[MIMO]]) wireless communication systems (for coded and uncoded signals).<ref>{{cite book |last1=Biglieri |first1=E. |last2=Calderbank |first2=R. |author-link3=Anthony G. Constantinides |first3=Anthony G. |last3=Constantinides |last4=Goldsmith |first4=A. |last5=Paulraj |first5=A. |last6=Poor |first6=H. V. |title=MIMO Wireless Communications |publisher=Cambridge U. P. |___location=Cambridge |year=2007 }}</ref><ref name=":2">{{cite journal |last1=Agrell |first1=E. |last2=Eriksson |first2=T. |last3=Vardy |first3=A. |last4=Zeger |first4=K. |title=Closest Point Search in Lattices |journal=IEEE Trans. Inf. Theory |volume=48 |issue=8 |pages=2201–2214 |year=2002 |doi=10.1109/TIT.2002.800499 |url=httpshttp://researchpublications.lib.chalmers.se/enrecords/publicationfulltext/14990/local_14990.pdf }}</ref> In this context it is called ''sphere decoding'' due to the radius used internal to many CVP solutions.<ref>{{cite journal |first1=Ping |last1=Wang |first2=Tho |last2=Le-Ngoc |title=A List Sphere Decoding Algorithm with Improved Radius Setting Strategies |journal=Wireless Personal Communications |year=2011 |volume=61 |issue=1 |pages=189–200 |doi=10.1007/s11277-010-0018-4 |s2cid=30919872 }}</ref>

It has been applied in the field of the integer ambiguity resolution of carrier-phase GNSS (GPS).<ref>{{cite journal |last1=Hassibi |first1=A. |last2=Boyd |first2=S. |title=Integer Parameter Estimation in Linear Models with Applications to GPS |journal=IEEE Trans. Sig. Proc. |volume=46 |issue=11 |pages=2938–2952 |year=1998 |doi=10.1109/78.726808 |bibcode=1998ITSP...46.2938H |citeseerx=10.1.1.114.7246 }}</ref> It is called the ''[[Peter J. G. Teunissen|LAMBDA method]]'' in that field. In the same field, the general CVP problem is referred to as ''Integer Least Squares''.

== GapCVP ==

This problem is similar to the GapSVP problem. For GapSVP_β, the input consists of a lattice basis and a vector <math>v</math>, and the algorithm must answer whether one of the following holds:

* there is a lattice vector such that the distance between it and <math>v</math> is at most 1., and

* every lattice vector is at a distance greater than <math>\beta</math> away from <math>v</math>.

The opposite condition is that the closest lattice vector is at a distance <math>1 < \lambda(L) \leq \beta</math>, hence the name ''Gap''CVP.

=== Known results ===

The problem is trivially contained in [[NP (complexity)|NP]] for any approximation factor.

[[Claus P. Schnorr|Schnorr]], in 1987, showed that deterministic polynomial time algorithms can solve the problem for <math>\beta=2^{O(n(\log \log n)^2/\log n)}</math>.<ref>{{cite book |first=C. P. |last=Schnorr |chapter=Factoring integers and computing [[discrete logarithm]]s via diophantine approximation |title=Advances in Cryptology: – Proceedings of Eurocrypt '91 }}</ref> Ajtai et al. showed that probabilistic algorithms can achieve a slightly better approximation factor of <math>\beta=2^{O(n \log \log n/\log n)}</math>.<ref name=":1">{{cite book |first1=Miklós |last1=Ajtai |first2=Ravi |last2=Kumar |first3=D. |last3=Sivakumar |chapter=A sieve algorithm for the shortest lattice vector problem |title=Proceedings of the thirty-third annual ACM symposium on Theory of computing |___location=Hersonissos, Greece |publisher=ACM |year=2001 |pages=601–610 |doi=10.1145/380752.380857 |isbn=15811334991-58113-349-9 |s2cid=14982298 |chapter-url=http://portal.acm.org/citation.cfm?doid=380752.380857 }}</ref>

In 1993, Banaszczyk showed that GapCVP_n is in <math>\mathsf{NP \cap coNP}</math>.<ref>{{cite journal |first=W. |last=Banaszczyk |title=New bounds in some transference theorems in the geometry of numbers |journal=[[Mathematische Annalen|Math. Ann.]] |volume=296 |year=1993 |issue=1 |pages=625–635 |doi=10.1007/BF01445125 |s2cid=13921988 }}</ref> In 2000, Goldreich and Goldwasser showed that <math>\beta=\sqrt{n/\log n}</math> puts the problem in both NP and [[coAM]].<ref>{{cite book |first1=Oded |last1=Goldreich |first2=Shafi |last2=Goldwasser |chapter=On the limits of non-approximability of lattice problems |title=Proceedings of the thirtieth annual ACM symposium on Theory of computing |___location=Dallas, Texas, United States |publisher=ACM |year=1998 |pages=1–9 |doi=10.1145/276698.276704 |isbn=08979196290-89791-962-9 |s2cid=3051993 |chapter-url=http://portal.acm.org/citation.cfm?id=276704 }}</ref> In 2005, Aharonov and Regev showed that for some constant <math>c</math>, the problem with <math>\beta=c\sqrt{n}</math> is in <math>\mathsf{NP \cap coNP}</math>.<ref>{{Cite journal| doi = 10.1145/1089023.1089025| volume = 52| issue = 5| pages = 749–765| last = Aharonov| first = Dorit|author2=Oded Regev | title = Lattice problems in NP <math>\cap</math> coNP| journal = J. ACM| year = 2005| citeseerx = 10.1.1.205.3730| s2cid = 1669286}}</ref>

For lower bounds, Dinur et al. showed in 1998 that the problem is NP-hard for <math>\beta=n^{o(1/\log{\log{n}})}</math>.<ref>{{cite book |first1=I. |last1=Dinur |first2=G. |last2=Kindler |first3=S. |last3=Safra |chapter=Approximating-CVP to within Almost-Polynomial Factors is NP-Hard |title=Proceedings of the 39th Annual Symposium on Foundations of Computer Science |publisher=IEEE Computer Society |year=1998 |pagespage=99 |isbn=978-0-8186-9172-0 |chapter-url=http://portal.acm.org/citation.cfm?id=796466 }}</ref>

== Shortest independent vectors problem (SIVP) ==

Given a lattice L of dimension ''n'', the algorithm must output ''n'' [[linearly independent]] <math>v_1, v_2, \ldots, v_n</math> so that <math>\max \|v_i\| \leq \max_B \|b_i\|</math>, where the right -hand side considers all bases <math>B=\{b_1,\ldots,b_n\}</math> of the lattice.

In the <math>\gamma</math>-approximate version, given a lattice L with dimension ''n'', one must find ''n'' [[linearly independent]] vectors <math>v_1, v_2,\ldots, v_n</math> of length <math>{{tmath| \max \|{{!}}v_i\|{{!}} \le \gamma \lambda_n(L)</math> }}, where <math>\lambda_n(L)</math> is the {{tmath| n }}<mathsup>nth</mathsup>'th successive minimum of <math>{{tmath| L</math> }}.

== Bounded distance decoding ==

This problem is similar to CVP. Given a vector such that its distance from the lattice is at most <math>\lambda(L)/2</math>, the algorithm must output the closest lattice vector to it.

== Covering radius problem ==

Given a basis for the lattice, the algorithm must find the largest distance (or in some versions, its approximation) from any vector to the lattice.

== Shortest basis problem ==

Many problems become easier if the input basis consists of short vectors. An algorithm that solves the Shortest Basis Problem (SBP) must, given a lattice basis <math>{{tmath|1= B</math> }}, output an equivalent basis <math>B'</math> such that the length of the longest vector in <math>B'</math> is as short as possible.

The approximation version SBP_γ problem consist of finding a basis whose longest vector is at most <math>\gamma</math> times longer than the longest vector in the shortest basis.

== Use in cryptography ==

{{main|Lattice-based cryptography}}

[[Average case|Average-case]] hardness of problems forms a basis for proofs-of-security for most cryptographic schemes. However, experimental evidence suggests that most NP-hard problems lack this property: they are probably only worst case hard. Many lattice problems have been conjectured or proven to be average-case hard, making them an attractive class of problems to base cryptographic schemes on. Moreover, worst-case hardness of some lattice problems have been used to create secure cryptographic schemes. The use of worst-case hardness in such schemes makes them among the very few schemes that are very likely secure even against [[quantum computers]].

The above lattice problems are easy to solve if the algorithm is provided with a "good" basis. [[Lattice reduction]] algorithms aim, given a basis for a lattice, to output a new basis consisting of relatively short, nearly [[orthogonal]] vectors. The [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm]] (LLL) was an early efficient algorithm for this problem which could output an almost reduced lattice basis in polynomial time.<ref>{{cite journal |first1=A. K. |last1=Lenstra |first2=H. W., Jr. |last2=Lenstra |first3=L. |last3=Lovász |title=Factoring polynomials with rational coefficients |journal=[[Mathematische Annalen|Math. Ann.]] |volume=261 |year=1982 |issue=4 |pages=515–534 |doi=10.1007/BF01457454 |s2cid=5701340 |url=https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.pdf |archive-url=https://web.archive.org/web/20110717132024/https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.pdf |archive-date=2011-07-17}}</ref> This algorithm and its further refinements were used to break several cryptographic schemes, establishing its status as a very important tool in cryptanalysis. The success of LLL on experimental data led to a belief that lattice reduction might be an easy problem in practice.; Howeverhowever, this belief was challenged when in the late 1990s, when several new results on the hardness of lattice problems were obtained, starting with the result of [[Miklós Ajtai|Ajtai]].<ref name="ajtai">{{cite book |first=M. |last=Ajtai |chapter=Generating hard instances of lattice problems |title=Proceedings of the Twenty-Eighth annual ACM symposium on Theory of computing |___location=Philadelphia, Pennsylvania, United States |publisher=ACM |year=1996 |pages=99–108 |doi=10.1145/237814.237838 |isbn=9780897917858978-0-89791-785-8 |s2cid=6864824 |chapter-url=http://portal.acm.org/citation.cfm?id=237838 }}</ref>

In his seminal papers, Ajtai showed that the SVP problem was NP-hard and discovered some connections between the worst-case complexity and [[average-case complexity]] of some lattice problems.<ref name="ajtai" /><ref name="Ajtai 1998 10–19"/> Building on these results, Ajtai and [[Cynthia Dwork|Dwork]] created a [[public-key cryptosystem]] whose security could be proven using only the worst case hardness of a certain version of SVP,<ref>{{cite book |first1=Miklós |last1=Ajtai |first2=Cynthia |last2=Dwork |chapter=A public-key cryptosystem with worst-case/average-case equivalence |title=Proceedings of the Twenty-Ninth annual ACM symposium on Theory of computing |___location=El Paso, Texas, United States |publisher=ACM |year=1997 |pages=284–293 |doi=10.1145/258533.258604 |isbn=08979188860-89791-888-6 |s2cid=9918417 |chapter-url=http://portal.acm.org/citation.cfm?id=258604 }}</ref> thus making it the first result to have used worst-case hardness to create secure systems.<ref>{{cite book |first=Jin-Yi |last=Cai |chapter=The Complexity of Some Lattice Problems |title=Algorithmic Number Theory |series=Lecture Notes in Computer Science |volume=1838 |year=2000 |pages=1–32 |doi=10.1007/10722028_1 |isbn=978-3-540-67695-9 }}</ref>

== See also ==

* [[Learning with errors]]

* [[Short integer solution problem]]

== References ==

{{reflist|colwidth=30em}}

== Further reading ==

* {{cite journal |author1=Agrell, E. |author2=Eriksson, T. |author3=Vardy, A. |author4=Zeger, K. |year=2002 |title=Closest Point Search in Lattices |journal=IEEE Trans. Inf. Theory |volume=48 |issue=8 |pages=2201–2214 |doi=10.1109/TIT.2002.800499 |url=httpshttp://researchpublications.lib.chalmers.se/enrecords/publicationfulltext/14990/local_14990.pdf }}

* {{cite journal |first=Daniele |last=Micciancio |title=The Shortest Vector Problem is {NP}-hard to approximate to within some constant |journal=SIAM Journal on Computing |year=2001 |volume=30 |issue=6 |pages=2008–2035 |doi=10.1137/S0097539700373039 |url=http://cseweb.ucsd.edu/~daniele/papers/SVP.html |citeseerx=10.1.1.93.6646 |s2cid=42794945 }}

* {{cite book |first1=Phong Q. |last1=Nguyen |first2=Jacques |last2=Stern |chapter=Lattice Reduction in Cryptology: An Update |title=Proceedings of the 4th International Symposium on Algorithmic Number Theory |publisher=Springer-Verlag |year=2000 |pages=85–112 |isbn=978-3-540-67695-9 |chapter-url=http://dl.acm.org/citation.cfm?id=749906 }}

Line 103 ⟶ 104:

[[Category:Lattice-based cryptography]]

[[Category:Mathematical problems]]

[[Category:Cryptography]]

[[Category:Post-quantum cryptography]]