Problem med gitterteorin

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 7 september 2021; verifiering kräver 1 redigering .

Gitterteoriproblem är en klass av optimeringsproblem på gitter (det vill säga diskreta additiva undergrupper definierade på uppsättningen ). Den hypotetiska dåliga lösbarheten av sådana problem är central för konstruktionen av säkra kryptosystem på gitter . För tillämpningar i sådana kryptosystem övervägs gitter på vektorrum (ofta ) eller fria moduler (ofta ). $\mathbb {R} ^{n}$ ${\displaystyle \mathbb {Q} ^{n))$ $\mathbb {Z} ^{n}$

För alla problem nedan, antag att vi (bortsett från andra mer specifika indata) får en grund för ett vektorrum V och en norm N . För normer brukar L 2 anses . Men även andra normer som L p ) beaktas och förekommer i olika resultat [1] . Nedan i artikeln betyder längden på den kortaste vektorn i gittret L , det vill säga $\lambda (L)$

\lambda (L)=\min _{v\in L\setminus \{\mathbf {0} \))\|v\|_{N}.

Kortaste vektorproblem (SCV)

I Kortaste vektorproblemet ( SVP) ges ett gitter L en bas av ett vektorrum V och en norm N (ofta L 2 ), och man måste hitta en vektor som inte är noll med minsta längd i V med normen N i gallret L . Med andra ord måste utdata från algoritmen vara en vektor som inte är noll så att . $N(v)=\lambda (L)$

I den ungefärliga versionen av ZKV γ är det nödvändigt att hitta en gittervektor som inte är noll med en längd som inte överstiger . $\gamma$ $\gamma \lambda (L)$

Svårighet

Endast den exakta versionen av problemet är känd för att vara NP-hård för randomiserad reduktion [2] [2] .

Däremot är det motsvarande problemet för enhetliga normer känt för att vara NP-hårt [3] .

Algoritmer för euklidiska normer

För att lösa den exakta versionen av EQV för den euklidiska normen finns det flera olika tillvägagångssätt som kan delas in i två klasser - algoritmer som kräver superexponentiell tid ( ) och minne, och algoritmer som kräver exponentiell tid och minne ( ), på dimensionen av gallret. I den första klassen av algoritmer är gitteruppräkningsalgoritmer [4] [5] [6] och slumpmässiga urvalsreduktionsalgoritmer [7] [8] mest signifikanta , medan den andra klassen inkluderar gittersiktning [9] [10] [11] , beräkna Voronoi-celler på gittret [12] [13] och diskreta Gauss-fördelningar [14] . Ett öppet problem är om det finns algoritmer som löser den exakta CTE i vanlig exponentiell tid ( ) och kräver minne som polynomiellt beror på gittrets dimension [15] . ${\displaystyle 2^{\omega (n)))$ $\operatörsnamn {poly} (n)$ ${\displaystyle 2^{\Theta (n)))$ $2^{O(n)}$

För att lösa den ungefärliga versionen av CQV γ för den euklidiska normen är det mest kända tillvägagångssättet baserat på reduktionen av gitterbasen . För stora Lenstra-Lenstra-Lovas algoritm för reduktion av basen av gittret kan hitta en lösning i polynomtid från dimensionen av gittret. För små värden används vanligen block-Korkin-Zolotarev- algoritmen (BKZ) [16] [17] [18] , där inmatningen av algoritmen (blockstorlek ) bestämmer tidskomplexiteten och utdatakvaliteten - för stora approximationskoefficienter , en liten blockstorlek är tillräcklig och algoritmen avslutas snabbt. För små krävs det mer för att hitta tillräckligt korta gittervektorer, och algoritmen löper längre. BKZ-algoritmen använder internt den exakta ZKV-algoritmen som en subrutin (körs på ett gitter med dimension som inte överstiger ), och den övergripande komplexiteten är nära relaterad till kostnaden för dessa ZKV-anrop i dimensionen . $\gamma$ $\gamma >1$ ${\displaystyle \gamma =2^{\Omega (n)))$ $\gamma$ $\beta$ $\gamma$ $\beta$ $\gamma$ $\beta$ $\beta$ $\beta$

GapSVP

Problemet är att skilja mellan varianter av CQV där svaret inte överstiger 1 eller mer , där kan vara en fast funktion av gitterdimensionen . Givet en gitterbas måste algoritmen avgöra om eller . Liksom andra problem med preconditions , tillåts algoritmen fel i alla andra fall. ${\displaystyle GapSVP_{\beta ))$ $\beta$ $\beta$ $n$ $\lambda (L)\leqslant 1$ $\lambda (L)>\beta$

En annan version av uppgiften är för vissa funktioner . Algoritmens indata är basen och numret . Algoritmen säkerställer att alla vektorer i Gram-Schmidt-ortogonaliseringen har en längd på minst 1, så att och så att , där är dimensionen. Algoritmen måste acceptera om och avvisa om . För stor ( ) är problemet ekvivalent med , eftersom [19] förprocessorsteget som använder LLL-algoritmen gör det andra villkoret (och därför ) redundant. ${\displaystyle GapSVP_{\zeta ,\gamma ))$ $\zeta ,\gamma$ $B$ $d$ $\lambda (L(B))\leqslant \zeta (n)$ $1\leqslant d\leqslant \zeta (n)/\gamma (n)$ $n$ $\lambda (L(B))\leqslant d$ $\lambda (L(B))\geqslant \gamma (n).d$ $\zeta$ ${\displaystyle \zeta (n)>2^{n/2))$ ${\displaystyle GapSVP_{\gamma ))$ $\zeta$

Närmaste vektorproblem (NVV)

Närmaste vektorproblem (CVP) för ett gitter L ges en vektorrumsbas V och en metrisk M (ofta L 2 ), såväl som en vektor v i V , men inte nödvändigtvis i L . Det krävs att man hittar en vektor i L som är närmast v (med avseende på måttet M ). I den ungefärliga versionen av STAT γ måste du hitta gittervektorn på ett avstånd som inte överstiger . $\gamma$ $\gamma$

Kommunikation med Xena

Problemet med att hitta den närmaste vektorn är en generalisering av problemet att hitta den kortaste vektorn. Det är lätt att visa att givet en prediktor för CBT γ (definierad nedan), kan man lösa CTA γ genom några frågor på prediktorn [20] . Den naturliga metoden att hitta den kortaste vektorn genom att fråga STTA-prediktorn γ för att hitta den närmaste vektorn fungerar inte eftersom 0 är en gittervektor och algoritmen kan potentiellt returnera 0.

Reduktionen från ZKV γ till ZBV γ är som följer: Antag att ingången till ZKV γ -problemet är grunden för gittret . Låt oss överväga grunden och låt oss vara vektorn som returneras av ZBV- algoritmen . Det anges att den kortaste vektorn i en mängd är den kortaste vektorn i det givna gittret. $B=[b_{1},b_{2},\ldots ,b_{n}]$ $B^{i}=[b_{1},\ldots ,2b_{i},\ldots ,b_{n}]$ $x_{i}$ $\gamma (B^{i},b_{i})$ $\{x_{i}-b_{i}\}$

Svårighet

Goldreich, Missiancio, Safra och Seifert har visat att all komplexitet hos ZKV innebär samma komplexitet för ZBV [21] . Arora, Babai, Stern , Sweedyk, med hjälp av VPD- verktygen , har visat att FBV är svår att uppskatta till en faktor på , om inte [22] . Dinur, Kindler, Safra stärkte detta genom att påpeka NP-hårdheten för c för [23] . ${\displaystyle 2^{\log ^{1-\epsilon }(n)))$ $\operatörsnamn {NP} \subseteq \operatörsnamn {DTIME} (2^{poly(\log n)})$ ${\displaystyle \epsilon =(\log \log n)^{c))$ $c<1/2$

Sfärisk avkodning

Algoritmen för STT , speciellt varianten av Fincke och Post [5] används till exempel för dataupptäckt i trådlösa kommunikationssystem med multipla input/multiple output ( MIMO ) (för kodade och avkodade signaler) [24] [12] . I detta sammanhang kallas det för sfärisk avkodning [25] .

Algoritmen har tillämpats inom området heltals GNSS -bärvågsfasdisambiguation ( GPS ) [26] . Inom detta område kallas detta för LAMBDA-metoden .

GapCVP

Denna uppgift liknar GapSVP-uppgiften. För indata är grunden för gittret och vektorn , och algoritmen måste svara på vilket av villkoren som är uppfyllt ${\displaystyle GapCVP_{\beta ))$ $v$

det finns en gittervektor så att avståndet mellan och inte överstiger 1. $v$
någon gittervektor är på ett avstånd större än . $v$ $\beta$

Anmärkningsvärda resultat

Problemet finns trivialt i klassen NP för någon approximationskoefficient.

Klaus Schnorr 1987 visade att deterministiska polynomtidsalgoritmer kan lösa problemet för [27] . Aitai, Kumar, Sivakumar visade att probabilistiska algoritmer kan få en något bättre approximationsfaktor [9] . ${\displaystyle \beta =2^{O(n(\log \log n)^{2}/\log n)))$ ${\displaystyle \beta =2^{O(n\log \log n/\log n)))$

1993 visade Banaszczyk vad som finns i [28] . År 2000 visade Goldreich och Goldwasser att han placerar problemet i både NP- och coAM-klasser [29] . År 2005 visade Aharonov och Regzhev att, för vissa konstant , ingår problem c i [30] . $GapCVP_{n}$ $NP\cap coNP$ $\beta ={\sqrt {n/\log n))$ $c$ $\beta =c{\sqrt {n))$ $NP\cap coNP$

För lägre gränser visade Dinur, Kindler och Safra 1998 att problemet är NP-svårt för [31] . $\beta =n^{o(1/\log {\log {n))))$

Kortaste oberoende vektorproblemet

Givet ett gitter L med dimension n, måste algoritmen producera n linjärt oberoende vektorer så att , där den högra sidan består av alla baser av gittret. ${\displaystyle v_{1},v_{2},\ldots ,v_{n))$ $\max \|v_{i}\|<\max _{B}\|b_{i}\|$ $B=\{b_{1},\ldots ,b_{n}\}$

I den ungefärliga versionen, om ett gitter L med dimensionen n ges, hittar algoritmen n linjärt oberoende vektorer av längd , där är det -: te successiva minimumet av . $\gamma$ ${\displaystyle v_{1},v_{2},\ldots ,v_{n))$ $\max ||v_{i}||\leqslant \gamma \lambda _{n}(L)$ $\lambda _{n}(L)$ $n$ $L$

Avkodning med begränsat avstånd

Denna uppgift liknar STAT. Givet en vektor så att dess avstånd från gittret inte överstiger , måste algoritmen returnera närmaste gittervektor. $\lambda (L)/2$

Problemet med att täcka ett gitter med radier

Givet en grund för gittret måste algoritmen hitta det längsta avståndet (eller, i vissa versioner, dess approximation) från vilken vektor som helst till gittret.

Problemet med att hitta den kortaste basen

Många problem blir lättare om indatabasen består av korta vektorer. En algoritm som löser Shortest Basis Problem (SCB) måste, givet gitterbasen , ge en ekvivalent bas , så att längden på den längsta vektorn i blir så kort som möjligt. $B$ $B'$ $B'$

En approximerad version av PKB- problemet γ är att hitta en bas vars längsta vektor inte överstiger längden på den längsta vektorn i den kortaste basen med en faktor 1. $\gamma$

Använd i kryptografi

Svårigheten med det genomsnittliga fallet av problem utgör grunden för att bevisa säkerheten för de flesta kryptografiska system. Experimentella bevis tyder dock på att de flesta NP-hårda problem inte har denna egenskap - de är svåra bara i värsta fall. Många problem inom gitterteorin har antagits eller visat sig vara svåra i genomsnitt, vilket gör dem attraktiva för kryptografiska system. Emellertid används den värsta svårigheten hos vissa gitterteoriproblem för att skapa starka kryptografischeman. Användningen av värsta tänkbara svårigheter i sådana kretsar placerar dem i klassen av de mycket få kretsarna som med stor sannolikhet är stabila även för kvantdatorer .

Ovanstående problem med gitterteorin löses lätt om en "bra" grund ges. Syftet med basreduktionsalgoritmerna [ för en given gitterbas är att producera en ny bas bestående av relativt korta nästan ortogonala vektorer. Lenstra -Lenstra-Lovász lattice-basreduktionsalgoritm ( LLL ) var en tidig effektiv algoritm för detta problem som kunde producera en reducerad gitterbas i polynomtid [32] . Denna algoritm och dess ytterligare förbättringar har använts för att bryta vissa kryptografiska system, vilket har etablerat sin status som ett mycket viktigt verktyg inom kryptografi. Framgången för LLL på experimentella data ledde till tron att minskning av gitterbasen kunde vara en enkel uppgift i praktiken. Men denna övertygelse krossades när, i slutet av 1990-talet, nya resultat erhölls om svårigheten med problem inom gitterteorin, med början med resultaten av Aitai [33] .

I sitt framstående arbete visade Aitai att ZKV var NP-hård och fann några kopplingar mellan den värsta komplexiteten och den genomsnittliga komplexiteten hos vissa problem i gitterteorin [2] . Baserat på dessa resultat skapade Aitai och Dwork ett kryptosystem med offentlig nyckel vars hemlighet kan bevisas med endast den värsta hårdheten i en viss version av ZKV [34] , vilket var det första resultatet att bygga säkra system med värsta tänkbara hårdhet [35] .

Se även

Lärande med fel

Anteckningar

↑ Khot, 2005 , sid. 789–808.
↑ 1 2 3 Ajtai, 1998 , sid. 10–19.
↑ van Emde Boas, 1981 .
↑ Kannan, 1983 , sid. 193–206.
↑ 1 2 Fincke, Pohst, 1985 , sid. 463–471.
↑ Gama, Nguyen, Regev, 2010 , sid. 257–278.
↑ Schnorr, 2003 , sid. 145–156.
↑ Aono, Nguyen, 2017 , sid. 65–102.
↑ 1 2 Ajtai, Kumar, Sivakumar, 2001 , sid. 601–610.
↑ Micciancio, Voulgaris, 2010 , sid. 1468–1480.
↑ Becker, Ducas, Gama, Laarhoven, 2015 , sid. 10–24.
↑ 1 2 Agrell, Eriksson, Vardy, Zeger, 2002 , sid. 2201–2214.
↑ Micciancio, Voulgaris, 2010a , sid. 351–358.
↑ Aggarwal, Dadush, Regev, Stephens-Davidowitz, 2015 , sid. 733–742.
↑ Micciancio, 2017 .
↑ Schnorr, 1987 , sid. 201–224.
↑ Schnorr och Euchner 1994 , sid. 181–199.
↑ Chen, Nguyen, 2011 , sid. 1–20.
↑ Peikert, 2009 , sid. 333–342.
↑ Micciancio, Goldwasser, 2002 .
↑ Goldreich, Micciancio, Safra, Seifert, 1999 , sid. 55–61.
↑ Arora, Babai, Stern, Sweedyk, 1997 , sid. 317–331.
↑ Dinur, Kindler, Safra, 2003 , sid. 205–243.
↑ Biglieri, Calderbank, Constantinides, Goldsmith, Paulraj, Poor, 2007 .
↑ Wang, Le-Ngoc, 2011 , sid. 189–200.
↑ Hassibi, Boyd, 1998 , sid. 2938–2952.
↑ Schnorr, 1993 .
↑ Banaszczyk, 1993 , sid. 625–635.
↑ Goldreich och Goldwasser 1998 , sid. 1–9.
↑ Aharonov, Regev, 2005 .
↑ Dinur, Kindler, Safra, 1998 , sid. 99.
↑ Lenstra, Lenstra, Lovász, 1982 , sid. 515–534.
↑ Ajtai, 1996 , sid. 99–108.
↑ Ajtai, Dwork, 1997 , sid. 284–293.
↑ Cai, 2000 , sid. 1–32.

Litteratur

Subhash Khot. Hårdhet för att approximera det kortaste vektorproblemet i gitter // J. ACM. - 2005. - T. 52 , nr. 5 . - doi : 10.1145/1089023.1089027 .
Miklos Ajtai. Det kortaste vektorproblemet i L 2 är NP -svårt för randomiserade reduktioner // Proceedings of the thirtionth annual ACM symposium on Theory of computing. — Dallas, Texas, USA: ACM, 1998.
Peter van Emde Boas. Ett annat NP-komplett problem och komplexiteten i att beräkna korta vektorer i ett gitter . Teknisk rapport 8104. - University of Amsterdam, Institutionen för matematik, Nederländerna, 1981.
Chris Peikert. Offentlig nyckel kryptosystem från det värsta fallet med kortaste vektorproblem: utökat sammandrag // Proceedings of the 41st annual ACM symposium on Theory of Computing. — Bethesda, MD, USA: ACM, 2009.
Daniele Micciancio, Shafi Goldwasser. Gitterproblemens komplexitet: ett kryptografiskt perspektiv. - 2002. - T. 671. - (Kluwer International Series in Engineering and Computer Science). — ISBN 0792376889 .
- Daniele Micciancio, Shafi Goldwasser. Gitterproblemens komplexitet: ett kryptografiskt perspektiv. - Springer USA, 2011. - (Springer International Series in Engineering and Computer Science). — ISBN 9781461508984 .
Goldreich O., Micciancio D., Safra S., Seifert J. -p. Att approximera kortaste gittervektorer är inte svårare än att approximera närmaste gittervektorer // Inf. bearbeta. Lett .. - 1999. - T. 71 , nr. 2 . - doi : 10.1016/S0020-0190(99)00083-6 .
Oded Goldreich, Shafi Goldwasser. Om gränserna för icke-approximability av gitterproblem // Proceedings of the trettionth annual ACM symposium on Theory of computing. — Dallas, Texas, USA: ACM, 1998.

Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk. Hårdheten hos ungefärliga optima i gitter, koder och system av linjära ekvationer // J. Comput. Syst. Sci.. - 1997. - V. 54 , nr. 2 . - doi : 10.1109/SFCS.1993.366815 .
Dinur I., Kindler G., Safra S. Att approximera CVP till inom nästan polynomiala faktorer är NP-hårt // Combinatorica. - 2003. - T. 23 , nr. 2 . - doi : 10.1007/s00493-003-0019-y .
Dinur I., Kindler G., Safra S. Approximating-CVP till inom nästan-polynomiala faktorer är NP-Hård // Proceedings of the 39th Annual Symposium on Foundations of Computer Science. - IEEE Computer Society, 1998. - ISBN 0-8186-9172-7 .

Fincke U., Pohst M. Förbättrade metoder för att beräkna vektorer av kort längd i ett gitter, inklusive en komplexitetsanalys // Math. Comp.. - 1985. - T. 44 , nr. 170 . - doi : 10.1090/S0025-5718-1985-0777278-8 .
Biglieri E., Calderbank R., Constantinides A., Goldsmith A., Paulraj A., Poor HV MIMO Wireless Communications. — Cambridge: Cambridge UP, 2007.
Ping Wang, Tho Le-Ngoc. En listsfäravkodningsalgoritm med förbättrade radieinställningsstrategier // Trådlös personlig kommunikation. - 2011. - T. 61 , nr. 1 . - doi : 10.1007/s11277-010-0018-4 .
Hassibi A., Boyd S. Heltalsparameteruppskattning i linjära modeller med applikationer till GPS // IEEE Trans. Sig. Proc .. - 1998. - T. 46 , nr. 11 . - doi : 10.1109/78.726808 .
Miklos Ajtai, Ravi Kumar, D. Sivakumar. En sållalgoritm för det kortaste gittervektorproblemet // Proceedings of the trettiotredje årliga ACM-symposiet om teorin om datoranvändning. — Hersonissos, Grekland: ACM, 2001.
Banaszczyk W. Nya gränser i vissa överföringssatser i talens geometri // Math. Ann. . - 1993. - T. 296 , nr. 1 . - doi : 10.1007/BF01445125 .
Dorit Aharonov, Oded Regev. Gitterproblem i NP coNP // J. ACM. - 2005. - T. 52 , nr. 5 . - doi : 10.1145/1089023.1089025 . $\keps$
Ajtai M. Generera svåra fall av gallerproblem // Proceedings of the twenty-eightth annual ACM symposium on Theory of computing. — Philadelphia, Pennsylvania, USA: ACM, 1996.
Miklos Ajtai, Cynthia Dwork. Ett kryptosystem med offentlig nyckel med värsta/genomsnittliga likvärdighet // Proceedings of the twenty-nionth annual ACM symposium on Theory of computing. — El Paso, Texas, USA: ACM, 1997.
Jin Yi Cai. Komplexiteten hos vissa gitterproblem // Algoritmisk talteori. - 2000. - T. 1838. - doi : 10.1007/10722028_1 .
Lenstra AK, Lenstra HW, Lovász L. Faktorering av polynom med rationella koefficienter // Math. Ann. . - 1982. - T. 261 , nr. 4 . - doi : 10.1007/BF01457454 .
Ravi Kanan. Förbättrade algoritmer för heltalsprogrammering och relaterade nätverksproblem // Proceedings of the femtonde årliga ACM-symposiet om beräkningsteori . - New York, NY, USA: ACM, 1983. - (STOC). — ISBN 0897910990 . - doi : 10.1145/800061.808749 .
Nicolas Gama, Phong Q. Nguyen, Oded Regev. Gitteruppräkning med extrem beskärning // Framsteg inom kryptologi - EUROCRYPT 2010 . - Springer, Berlin, Heidelberg, 2010. - doi : 10.1007/978-3-642-13190-5_13 .
Yoshinori Aono, Phong Q. Nguyen. Slumpmässig provtagning återbesökt: Gitteruppräkning med diskret beskärning // Framsteg inom kryptologi – EUROCRYPT 2017 . - Springer, Cham, 2017. - doi : 10.1007/978-3-319-56614-6_3 .
Daniele Micciancio, Panagiotis Voulgaris. Snabbare exponentiella tidsalgoritmer för det kortaste vektorproblemet // Proceedings of the Twenty-fire annual ACM-SIAM Symposium on Discrete Algorithms . - Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2010. - S. 1468-1480. — (SODA '10). — ISBN 9780898716986 .
Daniele Micciancio, Panagiotis Voulgaris. En deterministisk enkel exponentiell tidsalgoritm för de flesta gitterproblem baserad på Voronoi-cellberäkningar // Proceedings of the Forty-second ACM Symposium on Theory of Computing . — New York, NY, USA: ACM, 2010a. — ISBN 9781450300506 . - doi : 10.1145/1806689.1806739 .
Becker A., Ducas L., Gama N., Laarhoven T. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms . - Sällskapet för industriell och tillämpad matematik, 2015. - S. 10–24. - (Processen). - doi : 10.1137/1.9781611974331.ch2 .
Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz. Att lösa det kortaste vektorproblemet på 2N-tid med hjälp av diskret Gaussisk sampling: Extended Abstract // Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing . - New York, NY, USA: ACM, 2015. - (STOC). — ISBN 9781450335362 . - doi : 10.1145/2746539.2746606 .
Daniele Micciancio. Gitterkryptering - Kortaste vektorproblemet . — 2017.
Schnorr CP En hierarki av polynomiska tidsgitterbasreduktionsalgoritmer // Teoretisk datavetenskap. - 1987. - Vol. 53. - Fråga. 2 . - doi : 10.1016/0304-3975(87)90064-8 .
Schnorr CP, Euchner M. Reduktion av gitterbas : Förbättrade praktiska algoritmer och lösning av delmängdssummaproblem // Matematisk programmering. - 1994. - T. 66 , nr. 1-3 . — ISSN 0025-5610 . - doi : 10.1007/bf01581144 .
Claus Peter Schnorr. Gitterminskning genom slumpmässigt urval och födelsedagsmetoder // STACS . - Springer, Berlin, Heidelberg, 2003. - ISBN 3540364943 . - doi : 10.1007/3-540-36494-3_14 .
Schnorr CP Factoring heltal och beräkning av diskreta logaritmer via diofantapproximation // . - 1993. - V. 13. - S. 171-181 .. - (AMS DIMACS-serien i Disc. Math, and Theoretical Comp. Science).
Yuanmi Chen, Phong Q. Nguyen. Framsteg inom kryptologi - ASIACRYPT 2011 . - Springer, Berlin, Heidelberg, 2011. - doi : 10.1007/978-3-642-25385-0_1 .

Läsning för vidare läsning

Agrell E., Eriksson T., Vardy A., Zeger K. Closest Point Search in Lattices // IEEE Trans. underrätta. teori. - 2002. - T. 48 , nr. 8 . - doi : 10.1109/TIT.2002.800499 .
Daniele Micciancio. Det kortaste vektorproblemet är {NP}-svårt att uppskatta inom någon konstant // SIAM Journal on Computing. - 2001. - T. 30 , nr. 6 . — S. 2008–2035 . - doi : 10.1137/S0097539700373039 .
Phong Q. Nguyen, Jacques Stern. Lattice Reduction in Cryptology: An Update // Proceedings of the 4th International Symposium on Algorithmic Number Theory. - Springer-Verlag, 2000. - S. 85-112. — ISBN 3-540-67695-3 .