A rácselmélet problémái

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. szeptember 7-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A rácselméleti problémák a rácsokon (vagyis a halmazon definiált diszkrét additív alcsoportokon ) kapcsolatos optimalizálási problémák egy osztálya . Az ilyen problémák feltételezett rossz megoldhatósága központi szerepet játszik a biztonságos kriptorendszerek rácsokon történő felépítésében . Az ilyen kriptorendszerekben való alkalmazásokhoz a vektortereken (gyakran ) vagy a szabad modulokon (gyakran ) lévő rácsokat kell figyelembe venni. $\mathbb {R} ^{n}$ ${\displaystyle \mathbb {Q} ^{n))$ $\mathbb {Z} ^{n}$

Tegyük fel, hogy minden alábbi probléma esetén (más specifikusabb bemenetektől eltekintve) kapunk egy bázist egy V vektortérhez és egy N normához . A normáknál általában az L 2 -t veszik figyelembe . Azonban más normákat is figyelembe vettek, mint például az L p ) és különböző eredményekben jelennek meg [1] . Az alábbi cikkben az L rács legrövidebb vektorának hosszát jelenti , azaz $\lambda (L)$

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

Legrövidebb vektor probléma (SCV)

A legrövidebb vektorproblémában ( SVP) egy L rács megadja a V vektortér és egy N norma bázisát (gyakran L 2 ), és meg kell találni egy nullától eltérő, minimális hosszúságú vektort V -ben N normával . az L rácsban . Más szóval, az algoritmus kimenetének nullától eltérő v vektornak kell lennie , így . $N(v)=\lambda (L)$

A ZKV γ -közelítő változatában meg kell találni egy zérustól eltérő rácsvektort, amelynek hossza nem haladja meg a -t . $\gamma$ $\gamma \lambda (L)$

Nehézség

Csak a probléma pontos változata ismert, hogy NP-nehéz a randomizált redukcióhoz [2] [2] .

Ezzel szemben az egységes normák ekvivalens problémája ismert, hogy NP-kemény [3] .

Algoritmusok euklideszi normákhoz

Az euklideszi norma EQV pontos verziójának megoldásához számos különböző megközelítés létezik, amelyek két osztályba oszthatók - szuperexponenciális időt ( ) és memóriát igénylő algoritmusok, valamint exponenciális időt és memóriát ( ) igénylő algoritmusok a dimenzióban. a rácsról. Az algoritmusok első osztályában a rácsszámláló algoritmusok [4] [5] [6] és a véletlen minta-redukciós algoritmusok [7] [8] a legjelentősebbek , míg a második osztályba a rácsrostálás [9] [10] [11] tartozik. , Voronoi-cellák kiszámítása a rácson [12] [13] és diszkrét Gauss-eloszlások [14] . Nyitott probléma, hogy vannak-e olyan algoritmusok, amelyek a pontos CTE-t közönséges exponenciális időben ( ) oldják meg, és olyan memóriát igényelnek, amely polinomiálisan függ a rács méretétől [15] . ${\displaystyle 2^{\omega (n)))$ ${\megjelenítési stílus \operátornév {poly} (n)}$ ${\displaystyle 2^{\Theta (n)))$ $2^{O(n)}$

A CQV γ euklideszi norma -közelítő változatának megoldására a legismertebb megközelítés a rácsbázis redukcióján alapul . A nagy Lenstra-Lenstra-Lovas algoritmus a rácsalap redukciójára polinomiális időben talál megoldást a rács dimenziójából. Kis értékek esetén általában a blokk Korkin-Zolotarev algoritmust (BKZ) [16] [17] [18] használják , ahol az algoritmus bemenete (blokkméret ) határozza meg az időbonyolultságot és a kimenet minőségét - nagy közelítési együtthatók esetén a kis blokkméret elegendő , és az algoritmus gyorsan leáll. Kisebbeknél több kell a kellően rövid rácsvektorok megtalálásához, és az algoritmus tovább fut. A BKZ-algoritmus belsőleg a pontos ZKV-algoritmust használja szubrutinként (amely nem haladja meg a dimenziójú rácsot ), és az általános összetettség szorosan összefügg ezen ZKV-hívások költségével a dimenzióban . $\gamma$ $\gamma >1$ ${\displaystyle \gamma =2^{\Omega (n)))$ $\gamma$ $\beta$ $\gamma$ $\beta$ $\gamma$ $\beta$ $\beta$ $\beta$

GapSVP

A probléma az, hogy különbséget tegyünk a CQV azon változatai között, amelyekben a válasz nem haladja meg az 1-et vagy többet , ahol a rácsdimenzió fix függvénye lehet . Adott egy rácsbázis, az algoritmusnak el kell döntenie, hogy vagy . előfeltételekkel kapcsolatos egyéb problémákhoz hasonlóan az algoritmus minden más esetben megengedett hibákat. ${\displaystyle GapSVP_{\beta ))$ $\beta$ $\beta$ $n$ $\lambda (L)\leqslant 1$ $\lambda (L)>\beta$

A feladat egy másik változata bizonyos funkciókra vonatkozik . Az algoritmus bemenete a bázis és a szám . Az algoritmus biztosítja, hogy a Gram-Schmidt ortogonalizációban szereplő összes vektor hossza legalább 1 legyen, így és úgy, hogy , ahol a dimenzió. Az algoritmusnak el kell fogadnia, ha , és el kell utasítania, ha . Nagy ( ) esetén a probléma megegyezik a -val , mivel [19] az LLL algoritmust használó előfeldolgozó lépés redundánssá teszi a második feltételt (és ezért ). ${\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$ $\zeta (n)>2^{n/2}$ $GapSVP_{\gamma }$ $\zeta$

Legközelebbi vektorprobléma (NVV)

A legközelebbi vektorprobléma (CVP) egy L rácshoz adott egy V vektortérbázist és egy M metrikát (gyakran L 2 ), valamint egy v vektort V -ben , de nem feltétlenül L -ben . L -ben meg kell találni egy vektort, amely a legközelebb van v -hez (az M mértékhez képest ). A STAT γ -hozzávetőleges változatában meg kell találni a rácsvektort olyan távolságban, amely nem haladja meg a -t . $\gamma$ $\gamma$

Kommunikáció a Xenával

A legközelebbi vektor megtalálásának problémája a legrövidebb vektor megtalálásának problémájának általánosítása. Könnyen kimutatható, hogy adott a CBT γ prediktora (lásd alább), a CTA γ néhány lekérdezéssel megoldható a prediktoron [20] . A legrövidebb vektor megtalálásának természetes módszere a γ STTA prediktor lekérdezésével a legközelebbi vektor megkeresésére nem működik, mert a 0 egy rácsvektor, és az algoritmus potenciálisan 0-t adhat vissza.

A ZKV γ -ról ZBV γ -ra való redukció a következő: Tegyük fel, hogy a ZKV γ feladat bemenete a rács alapja . Tekintsük a bázist , és legyen a ZBV algoritmus által visszaadott vektor . Azt mondják, hogy egy halmaz legrövidebb vektora az adott rács legrövidebb vektora. $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}\}$

Nehézség

Goldreich, Missiancio, Safra és Seifert kimutatták, hogy a ZKV bármilyen összetettsége ugyanazt a komplexitást jelenti a ZBV esetében is [21] . Arora, Babai, Stern , Sweedyk a VPD eszközök segítségével kimutatták, hogy az FBV-t nehéz faktorral közelíteni , hacsak nem [22] . Dinur, Kindler, Safra ezt azzal erősítette meg, hogy rámutat a c [23] NP - keménységére . ${\displaystyle 2^{\log ^{1-\epsilon }(n)))$ $\operátornév {NP} \subseteq \operátornév {DTIME} (2^{poly(\log n)})$ ${\displaystyle \epsilon =(\log \log n)^{c))$ $c<1/2$

Szférikus dekódolás

Az STT algoritmusát , különösen a Fincke és Post [5] változatát, például adatfelderítésre használják vezeték nélküli kommunikációs rendszerekben több bemenettel/többszörös kimenettel ( MIMO ) (kódolt és dekódolt jelekhez) [24] [12] . Ebben az összefüggésben gömbi dekódolásnak nevezik [25] .

Az algoritmust az egész számú GNSS vivőfázis -meghatározás ( GPS ) területén alkalmazták [26] . Ezen a területen ezt LAMBDA módszernek nevezik .

GapCVP

Ez a feladat hasonló a GapSVP feladathoz. Mert a bemenet a rács és a vektor alapja , és az algoritmusnak meg kell válaszolnia, hogy melyik feltétel teljesül ${\displaystyle GapCVP_{\beta ))$ $v$

van olyan rácsvektor, amelynél a és közötti távolság nem haladja meg az 1-et. $v$
bármely rácsvektor távolsága nagyobb , mint . $v$ $\beta$

Figyelemre méltó eredmények

A probléma triviálisan benne van az NP osztályban bármely közelítési együttható esetén.

Klaus Schnorr 1987-ben kimutatta, hogy a determinisztikus polinomiális idő algoritmusok meg tudják oldani a [27] problémáját . Aitai, Kumar, Sivakumar kimutatta, hogy a valószínűségi algoritmusok valamivel jobb közelítési tényezőt kaphatnak [9] . ${\displaystyle \beta =2^{O(n(\log \log n)^{2}/\log n)))$ ${\displaystyle \beta =2^{O(n\log \log n/\log n)))$

1993-ban Banaszczyk megmutatta, mit tartalmaz [28] . 2000-ben Goldreich és Goldwasser kimutatta, hogy a problémát mind az NP, mind a coAM osztályba helyezi [29] . 2005-ben Aharonov és Regzsev kimutatta, hogy bizonyos állandók esetén a c probléma szerepel a [30] -ban . $GapCVP_{n}$ $NP\cap coNP$ $\beta ={\sqrt {n/\log n))$ $c$ $\beta =c{\sqrt {n))$ $NP\cap coNP$

Az alsó határok esetében Dinur, Kindler és Safra 1998-ban kimutatta, hogy a probléma NP-nehéz [31] számára . $\beta =n^{o(1/\log {\log {n))))$

Legrövidebb független vektor probléma

Adott egy n dimenziójú L rács, az algoritmusnak n lineárisan független vektort kell előállítania úgy, hogy , ahol a jobb oldal a rács összes bázisából áll. ${\displaystyle v_{1},v_{2},\ldots ,v_{n))$ $\max \|v_{i}\|<\max _{B}\|b_{i}\|$ $B=\{b_{1},\ldots ,b_{n}\}$

A -közelítő változatban, ha adott egy n méretű L rács, az algoritmus n lineárisan független hosszúságú vektort talál , ahol a -edik egymást követő minimum . $\gamma$ ${\displaystyle v_{1},v_{2},\ldots ,v_{n))$ $\max ||v_{i}||\leqslant \gamma \lambda _{n}(L)$ $\lambda _{n}(L)$ $n$ $L$

Dekódolás korlátozott távolsággal

Ez a feladat hasonló a STAT-hoz. Adott egy vektor, amelynek távolsága a rácstól nem haladja meg a -t , akkor az algoritmusnak a legközelebbi rácsvektort kell visszaadnia. $\lambda (L)/2$

A rács sugarú lefedésének problémája

Adott a rács alapja, az algoritmusnak meg kell találnia a legnagyobb távolságot (vagy egyes változatokban a közelítését) bármely vektortól a rácsig.

A legrövidebb alap megtalálásának problémája

Sok probléma könnyebbé válik, ha a bemeneti bázis rövid vektorokból áll. A legrövidebb bázisproblémát (SCB) megoldó algoritmusnak a rácsbázis ismeretében egy ekvivalens bázist kell adnia úgy, hogy a leghosszabb vektor hossza a lehető legrövidebb legyen. $B$ $B'$ $B'$

A γ PKB -probléma közelített változata az , hogy olyan bázist találjunk, amelynek leghosszabb vektora nem haladja meg 1-szeresen a legrövidebb bázis leghosszabb vektorának hosszát. $\gamma$

Használata a kriptográfiában

A problémák átlagos esetének nehézsége képezi az alapot a legtöbb kriptográfiai séma biztonságának bizonyításához. A kísérleti bizonyítékok azonban azt sugallják, hogy a legtöbb NP-nehéz probléma nem rendelkezik ezzel a tulajdonsággal – csak a legrosszabb esetben kemények. A rácselméletben sok problémát feltételeztek vagy bizonyítottak átlagosan nehéznek, ami vonzóvá teszi őket a kriptográfiai sémák számára. Azonban néhány rácselméleti probléma legrosszabb nehézségét használják fel erős kriptográfiai sémák létrehozására. Az ilyen áramkörökben a legrosszabb eset nehézségeinek alkalmazása a nagyon kevés áramkör osztályába sorolja őket, amelyek nagy valószínűséggel még a kvantumszámítógépek számára is stabilak .

A rácselmélet fenti problémái könnyen megoldhatók, ha „jó” alapot adunk. A bázisredukciós algoritmusok célja egy adott rácsbázisra egy új bázis létrehozása, amely viszonylag rövid, majdnem ortogonális vektorokból áll. A Lenstra –Lenstra–Lovász rácsbázis-redukciós algoritmus ( LLL ) egy korai hatékony algoritmus volt erre a problémára, amely redukált rácsbázist tudott előállítani polinomidőben [32] . Ezt az algoritmust és további fejlesztéseit használták egyes kriptográfiai sémák feltörésére, ami a kriptográfia nagyon fontos eszközévé vált. Az LLL kísérleti adatokon elért sikere arra a meggyőződésre vezetett, hogy a rácsbázis csökkentése egyszerű feladat lehet a gyakorlatban. Ez a hiedelem azonban megtört, amikor az 1990-es évek végén új eredmények születtek a rácselmélet problémáinak nehézségeiről, kezdve Aitai [33] eredményeivel .

Alapművében Aitai kimutatta, hogy a ZKV NP-kemény, és talált néhány összefüggést a legrosszabb eset komplexitása és a rácselmélet egyes problémáinak átlagos összetettsége között [2] . Ezen eredmények alapján Aitai és Dwork létrehoztak egy nyilvános kulcsú kriptorendszert , amelynek titkossága csak a ZKV egy adott verziójának legrosszabb keménységével igazolható [34] , amely az első eredménye volt a legrosszabb esetet használó biztonságos rendszerek létrehozásának. keménység [35] .

Lásd még

Tanulás hibákkal

Jegyzetek

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

Irodalom

Subhash Khot. A legrövidebb vektorprobléma közelítésének keménysége rácsokban // J. ACM. - 2005. - T. 52 , sz. 5 . - doi : 10.1145/1089023.1089027 .
Ajtai Miklós. A legrövidebb vektorprobléma L 2 -ben az NP -nehéz a randomizált redukciókhoz // Proceedings of the thirtieth year ACM symposium on Theory of computing. – Dallas, Texas, Egyesült Államok: ACM, 1998.
Peter van Emde Boas. Egy másik NP-teljes probléma és a rövid vektorok rácsban történő kiszámításának összetettsége . Technical Report 8104. - Amszterdami Egyetem, Matematika Tanszék, Hollandia, 1981.
Chris Peikert. Nyilvános kulcsú kriptorendszerek a legrosszabb esetben a legrövidebb vektorproblémából: kiterjesztett abstract // Proceedings of the 41st year ACM symposium on Theory of Computing. – Bethesda, MD, USA: ACM, 2009.
Daniele Micciancio, Shafi Goldwasser. A rácsproblémák összetettsége: kriptográfiai perspektíva. - 2002. - T. 671. - (Kluwer International Series in Engineering and Computer Science). — ISBN 0792376889 .
- Daniele Micciancio, Shafi Goldwasser. A rácsproblémák összetettsége: kriptográfiai perspektíva. - Springer US, 2011. - (The Springer International Series in Engineering and Computer Science). — ISBN 9781461508984 .
Goldreich O., Micciancio D., Safra S., Seifert J. -p. A legrövidebb rácsvektorok közelítése nem nehezebb, mint a legközelebbi rácsvektorok közelítése // Inf. folyamat. Lett .. - 1999. - T. 71 , sz. 2 . - doi : 10.1016/S0020-0190(99)00083-6 .
Oded Goldreich, Shafi Goldwasser. A rácsproblémák nem közelíthetőségének határairól // Proceedings of the thirtyth year ACM symposium on Theory of computing. – Dallas, Texas, Egyesült Államok: ACM, 1998.

Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk. A közelítő optimumok keménysége rácsokban, kódokban és lineáris egyenletrendszerekben // J. Comput. Syst. Sci.. - 1997. - V. 54 , no. 2 . - doi : 10.1109/SFCS.1993.366815 .
Dinur I., Kindler G., Safra S. A CVP közelítése majdnem polinomiális tényezőkhöz NP-Hard // Combinatorica. - 2003. - T. 23 , sz. 2 . - doi : 10.1007/s00493-003-0019-y .
Dinur I., Kindler G., Safra S. Approximating-CVP to within Almost-Polynomial Factors is NP-Hard // Proceedings of the 39th Annual Symposium on Foundations of Computer Science. - IEEE Computer Society, 1998. - ISBN 0-8186-9172-7 .

Fincke U., Pohst M. Továbbfejlesztett módszerek rövid hosszúságú vektorok kiszámítására egy rácsban, beleértve a komplexitáselemzést // Math. Összeg.. - 1985. - T. 44 , sz. 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. Lista gömb dekódoló algoritmus továbbfejlesztett sugárbeállítási stratégiákkal // Vezeték nélküli személyes kommunikáció. - 2011. - T. 61 , sz. 1 . - doi : 10.1007/s11277-010-0018-4 .
Hassibi A., Boyd S. Integer Parameter Estimation integer Parameter Estimation integer Models with Applications to GPS // IEEE Trans. Sig. Proc .. - 1998. - T. 46 , no. 11 . - doi : 10.1109/78.726808 .
Ajtai Miklós, Ravi Kumar, D. Sivakumar. Szitaalgoritmus a legrövidebb rácsvektor-problémára // Proceedings of the thirty-third year ACM symposium on Theory of Computing. – Hersonissos, Görögország: ACM, 2001.
Banaszczyk W. Új korlátok néhány átviteli tételben a számok geometriájában // Math. Ann. . - 1993. - T. 296 , sz. 1 . - doi : 10.1007/BF01445125 .
Dorit Aharonov, Oded Regev. Rácsproblémák az NP coNP-ben // J. ACM. - 2005. - T. 52 , sz. 5 . - doi : 10.1145/1089023.1089025 . $\sapka$
Ajtai M. A rácsproblémák kemény példányainak generálása // Proceedings of the twenty-nyolcas year ACM symposium on Theory of computing. – Philadelphia, Pennsylvania, Egyesült Államok: ACM, 1996.
Ajtai Miklós, Dwork Cynthia. Nyilvános kulcsú kriptorendszer a legrosszabb eset/átlagos eset ekvivalenciájával // Proceedings of the huszonkilencedik éves ACM szimpózium a számítástechnika elméletéről. – El Paso, Texas, Egyesült Államok: ACM, 1997.
Jin Yi Cai. Néhány rácsfeladat összetettsége // Algoritmikus számelmélet. - 2000. - T. 1838. - doi : 10.1007/10722028_1 .
Lenstra AK, Lenstra HW, Lovász L. Polinomok faktorálása racionális együtthatókkal // Math. Ann. . - 1982. - T. 261 , sz. 4 . - doi : 10.1007/BF01457454 .
Ravi Kannan. Továbbfejlesztett algoritmusok egészszámú programozáshoz és a kapcsolódó rácsproblémákhoz // Proceedings of the Fifteenth Annual Annual ACM Symposium on Theory of Computing . - New York, NY, USA: ACM, 1983. - (STOC). — ISBN 0897910990 . - doi : 10.1145/800061.808749 .
Nicolas Gama, Phong Q. Nguyen, Oded Regev. Rácsfelsorolás extrém metszéssel // Advances in Cryptology - EUROCRYPT 2010 . - Springer, Berlin, Heidelberg, 2010. - doi : 10.1007/978-3-642-13190-5_13 .
Yoshinori Aono, Phong Q. Nguyen. Random Sampling Revisited: Lattice Enumeration with Discrete Pruning // Advances in Cryptology – EUROCRYPT 2017 . - Springer, Cham, 2017. - doi : 10.1007/978-3-319-56614-6_3 .
Daniele Micciancio, Panagiotis Voulgaris. Gyorsabb exponenciális idő algoritmusok a legrövidebb vektorproblémára // A huszonegyedik éves ACM-SIAM szimpózium előadása a diszkrét algoritmusokról . - Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2010. - S. 1468-1480. – (SZÓDA '10). — ISBN 9780898716986 .
Daniele Micciancio, Panagiotis Voulgaris. Determinisztikus egyszeri exponenciális idő algoritmus a legtöbb rácsproblémára Voronoi-cellaszámítások alapján // 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 . - Ipari és Alkalmazott Matematikai Társaság, 2015. - P. 10–24. - (Eljárás). - doi : 10.1137/1.9781611974331.ch2 .
Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz. A legrövidebb vektorprobléma megoldása 2N idő alatt diszkrét Gauss-mintavételezéssel: Extended Abstract // Proceedings of the Forty-7th Annual ACM Symposium on Theory of Computing . - New York, NY, USA: ACM, 2015. - (STOC). — ISBN 9781450335362 . - doi : 10.1145/2746539.2746606 .
Daniele Micciancio. Rácsos kriptográfia – legrövidebb vektoros probléma . — 2017.
Schnorr CP A polinomiális időrács bázisredukciós algoritmusainak hierarchiája // Theoretical Computer Science. - 1987. - 1. évf. 53. - Kiadás. 2 . - doi : 10.1016/0304-3975(87)90064-8 .
Schnorr CP, Euchner M. Rácsbázis redukció: Javított gyakorlati algoritmusok és részhalmazösszeg-feladatok megoldása // Matematikai programozás. - 1994. - T. 66 , sz. 1-3 . — ISSN 0025-5610 . - doi : 10.1007/bf01581144 .
Claus Peter Schnorr. Rácscsökkentés véletlenszerű mintavétellel és születésnapi módszerekkel // STACS . - Springer, Berlin, Heidelberg, 2003. - ISBN 3540364943 . - doi : 10.1007/3-540-36494-3_14 .
Schnorr CP Egész számok faktorálása és diszkrét logaritmusok számítása diofantin közelítéssel // . - 1993. - V. 13. - S. 171-181 .. - (AMS DIMACS sorozat Disc. Math, and Theoretical Comp. Science).
Yuanmi Chen, Phong Q. Nguyen. Előrelépések a kriptológiában – ASIACRYPT 2011 . - Springer, Berlin, Heidelberg, 2011. - doi : 10.1007/978-3-642-25385-0_1 .

Olvasás további olvasáshoz

Agrell E., Eriksson T., Vardy A., Zeger K. Closest Point Search in Lattices // IEEE Trans. tájékoztatni. elmélet. - 2002. - T. 48 , sz. 8 . - doi : 10.1109/TIT.2002.800499 .
Daniele Micciancio. A legrövidebb vektor probléma {NP}-nehezen közelíthető valamilyen állandó // SIAM Journal on Computing-on belül. - 2001. - T. 30 , sz. 6 . — S. 2008–2035 . - doi : 10.1137/S0097539700373039 .
Phong Q. Nguyen, Jacques Stern. Rácsredukció a kriptológiában: frissítés // Proceedings of the 4th International Symposium on Algorithmic Number Theory. - Springer-Verlag, 2000. - S. 85-112. — ISBN 3-540-67695-3 .