Hilateorian ongelmia

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 7.9.2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Hilateoriaongelmat ovat luokka optimointiongelmia hilassa (eli joukossa määritellyt diskreetit additiivinen alaryhmät ). Tällaisten ongelmien hypoteettinen huono ratkaistavuus on keskeistä turvallisten salausjärjestelmien rakentamisessa hilalle . Tällaisten salausjärjestelmien sovelluksissa otetaan huomioon vektoriavaruuksien hilat (usein ) tai vapaita moduuleja (usein ). $\mathbb {R} ^{n}$ ${\displaystyle \mathbb {Q} ^{n))$ $\mathbb {Z} ^{n}$

Kaikissa alla olevissa ongelmissa oletetaan, että meille on annettu (muiden tarkempien syötteiden lisäksi) perusta vektoriavaruudelle V ja normille N . Normeille L 2 pidetään yleensä . Kuitenkin myös muita normeja, kuten L p ) otetaan huomioon ja ne näkyvät erilaisissa tuloksissa [1] . Alla artikkelissa tarkoitetaan hilan L lyhimmän vektorin pituutta , eli $\lambda (L)$

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

Lyhin vektoriongelma (SCV)

Lyhyimmässä vektoriongelmassa ( SVP) hilalle L annetaan kanta vektoriavaruudelle V ja normille N (usein L 2 ), ja on löydettävä nollasta poikkeava vektori, jonka minimipituus V :ssä normin N kanssa . hilassa L . Toisin sanoen algoritmin lähdön on oltava nollasta poikkeava vektori v siten, että . $N(v)=\lambda (L)$

ZKV γ :n -likimääräisessä versiossa on tarpeen löytää nollasta poikkeava hilavektori, jonka pituus ei ylitä . $\gamma$ $\gamma \lambda (L)$

Vaikeus

Ainoastaan ongelman tarkan version tiedetään olevan NP-kova satunnaistetussa vähentämisessä [2] [2] .

Sitä vastoin yhtenäisten normien vastaavan ongelman tiedetään olevan NP-kova [3] .

Algoritmit euklidisille normeille

Euklidisen normin EQV:n tarkan version ratkaisemiseksi on olemassa useita erilaisia lähestymistapoja, jotka voidaan jakaa kahteen luokkaan - algoritmeihin, jotka vaativat supereksponentiaalista aikaa ( ) ja muistia, ja algoritmeihin, jotka vaativat eksponentiaalista aikaa ja muistia ( ) ulottuvuudessa. hilasta. Ensimmäisessä algoritmiluokassa tärkeimmät ovat hilalaskenta-algoritmit [4] [5] [6] ja satunnaisotosvähennys-algoritmit [7] [8] , kun taas toiseen luokkaan kuuluu hilaseulonta [9] [10] [11] . , laskee Voronoi-solut hilassa [12] [13] ja diskreetit Gaussin jakaumat [14] . Avoin ongelma on, onko olemassa algoritmeja, jotka ratkaisevat tarkan CTE:n tavallisessa eksponentiaalisessa ajassa ( ) ja vaativat muistia, joka riippuu polynomiaalisesti hilan dimensiosta [15] . ${\displaystyle 2^{\omega (n)))$ ${\näyttötyyli \operaattorin nimi {poly} (n)}$ ${\displaystyle 2^{\Theta (n)))$ $2^{O(n)}$

Euklidisen normin CQV γ : n -likimääräisen version ratkaisemiseksi tunnetuin lähestymistapa perustuu hilapohjan pelkistykseen . Suurille Lenstra-Lenstra-Lovas-algoritmi hilan kannan pelkistys voi löytää ratkaisun polynomiajassa hilan dimensiosta. Pienille arvoille käytetään yleensä lohko-Korkin-Zolotarev- algoritmia (BKZ) [16] [17] [18] , jossa algoritmin syöte (lohkokoko ) määrittää ajan kompleksisuuden ja lähdön laadun - suurille approksimaatiokertoimille pieni lohkokoko riittää ja algoritmi päättyy nopeasti. Pienillä , riittävän lyhyiden hilavektorien löytäminen vie enemmän ja algoritmi toimii pidempään. BKZ-algoritmi käyttää sisäisesti tarkkaa ZKV-algoritmia alirutiinina (käytetään hilassa, jonka ulottuvuus ei ylitä ), ja yleinen monimutkaisuus liittyy läheisesti näiden ZKV-kutsujen kustannuksiin ulottuvuudessa . $\gamma$ $\gamma >1$ ${\displaystyle \gamma =2^{\Omega (n)))$ $\gamma$ $\beeta$ $\gamma$ $\beeta$ $\gamma$ $\beeta$ $\beeta$ $\beeta$

GapSVP

Ongelmana on erottaa CQV:n variantit, joissa vastaus ei ylitä yhtä tai useampaa , missä voi olla hilamitan kiinteä funktio . Hilapohjan perusteella algoritmin on päätettävä, onko vai . Kuten muutkin ongelmat ennakkoehtojen kanssa, algoritmi sallii virheet kaikissa muissa tapauksissa. ${\displaystyle GapSVP_{\beta ))$ $\beeta$ $\beeta$ $n$ $\lambda (L)\leqslant 1$ $\lambda (L)>\beta$

Toinen tehtävän versio on joillekin toiminnoille . Algoritmin syöte on kanta ja luku . Algoritmi varmistaa, että Gram-Schmidt-ortogonalisoinnin kaikkien vektorien pituus on vähintään 1, niin että ja niin että , missä on ulottuvuus. Algoritmin on hyväksyttävä jos ja hylättävä jos . Suurille ( ) ongelma on sama kuin , koska [19] LLL-algoritmia käyttävä esiprosessorivaihe tekee toisesta ehdosta (ja siten ) redundantin. ${\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$

Lähin vektoriongelma (NVV)

Lähimmälle vektoriongelmalle (CVP) hilalle L annetaan vektoriavaruuden kanta V ja metriikka M (usein L 2 ), samoin kuin vektori v V : ssä , mutta ei välttämättä L: ssä . L: stä on löydettävä vektori, joka on lähinnä v :tä (mitan M suhteen ). STAT γ : n -likimääräisessä versiossa sinun on löydettävä hilavektori etäisyydeltä, joka ei ylitä . $\gamma$ $\gamma$

Viestintä Xenan kanssa

Lähimmän vektorin löytämisen ongelma on yleistys lyhimmän vektorin löytämisen ongelmasta. On helppo osoittaa, että kun CBT γ :n ennustaja (määritelty alla) on annettu, CTA γ voidaan ratkaista joillain ennustajan kyselyillä [20] . Luonnollinen menetelmä löytää lyhin vektori kysymällä STTA-ennustajaa γ lähimmän vektorin löytämiseksi ei toimi, koska 0 on hilavektori ja algoritmi voi mahdollisesti palauttaa arvon 0.

Pelkistys ZKV γ : sta ZBV γ :ksi on seuraava: Oletetaan, että ZKV γ -tehtävän syöte on hilan perusta . Tarkastellaan kantaa ja olkoon ZBV- algoritmin palauttama vektori . Sanotaan, että joukon lyhin vektori on lyhin vektori annetussa hilassa. $B=[b_{1},b_{2},\ldots ,b_{n}]$ $B^{i}=[b_{1},\ldots ,2b_{i},\ldots ,b_{n}]$ $x_{i}$ ${\näyttötyyli \gamma (B^{i},b_{i})}$ $\{x_{i}-b_{i}\}$

Vaikeus

Goldreich, Missiancio, Safra ja Seifert ovat osoittaneet, että mikä tahansa ZKV:n monimutkaisuus merkitsee samaa monimutkaisuutta ZBV :lle [21] . Arora, Babai, Stern , Sweedyk ovat VPD -työkaluja käyttäneet osoittaneet, että FBV:tä on vaikea arvioida kertoimella , ellei [22] . Dinur, Kindler, Safra vahvistivat tätä osoittamalla c : n NP-kovuuden [23] . ${\displaystyle 2^{\log ^{1-\epsilon }(n)))$ $\operaattorinimi {NP} \subseteq \operaattorinimi {DTIME} (2^{poly(\log n)})$ ${\displaystyle \epsilon =(\log \log n)^{c))$ $c<1/2$

Pallomainen dekoodaus

STT - algoritmia , erityisesti Fincken ja Postin varianttia [5] , käytetään esimerkiksi tiedonhakuun langattomissa viestintäjärjestelmissä, joissa on useita tulo/monilähtöjä ( MIMO ) (koodatuille ja dekoodatuille signaaleille) [24] [12] . Tässä yhteydessä sitä kutsutaan pallomaiseksi dekoodaukseksi [25] .

Algoritmia on sovellettu kokonaislukujen GNSS - kantoaaltovaiheen yksiselitteisyyden ( GPS ) alueella [26] . Tällä alueella tätä kutsutaan LAMBDA-menetelmäksi .

GapCVP

Tämä tehtävä on samanlainen kuin GapSVP-tehtävä. Sillä syöte on hilan ja vektorin perusta ja algoritmin on vastattava mikä ehdoista täyttyy ${\displaystyle GapCVP_{\beta ))$ $v$

on hilavektori, jonka ja välinen etäisyys ei ole suurempi kuin 1. $v$
mikä tahansa hilavektori on etäisyydellä suurempi kuin . $v$ $\beeta$

Merkittäviä tuloksia

Tehtävä sisältyy triviaalisti luokkaan NP mille tahansa approksimaatiokertoimelle.

Klaus Schnorr vuonna 1987 osoitti, että deterministiset polynomiaika-algoritmit voivat ratkaista ongelman [27] . Aitai, Kumar, Sivakumar osoittivat, että todennäköisyyspohjaiset algoritmit voivat saada hieman paremman approksimaatiokertoimen [9] . ${\displaystyle \beta =2^{O(n(\log \log n)^{2}/\log n)))$ ${\displaystyle \beta =2^{O(n\log \log n/\log n)))$

Vuonna 1993 Banaszczyk osoitti, mitä [ 28] sisältää . Vuonna 2000 Goldreich ja Goldwasser osoittivat, että hän sijoittaa ongelman sekä NP- että coAM-luokkiin [29] . Vuonna 2005 Aharonov ja Regzhev osoittivat, että jollekin vakiolle ongelma c sisältyy [30] . $GapCVP_{n}$ $NP\cap coNP$ $\beta ={\sqrt {n/\log n))$ $c$ $\beta =c{\sqrt {n))$ $NP\cap coNP$

Alarajan osalta Dinur, Kindler ja Safra osoittivat vuonna 1998, että ongelma on NP-kova [31] . $\beta =n^{o(1/\log {\log {n))))$

Lyhin itsenäinen vektoriongelma

Kun on annettu hila L, jonka dimensio on n, algoritmin tulee tuottaa n lineaarisesti riippumatonta vektoria siten, että , jossa oikea puoli koostuu hilan kaikista kannoista. ${\displaystyle v_{1},v_{2},\ldots ,v_{n))$ $\max \|v_{i}\|<\max _{B}\|b_{i}\|$ $B=\{b_{1},\ldots ,b_{n}\}$

Jos -likimääräisessä versiossa on annettu hila L, jonka ulottuvuus on n, algoritmi löytää n lineaarisesti riippumatonta pituusvektoria , jossa on -: s peräkkäinen minimi . $\gamma$ ${\displaystyle v_{1},v_{2},\ldots ,v_{n))$ $\max ||v_{i}||\leqslant \gamma \lambda _{n}(L)$ $\lambda _{n}(L)$ $n$ $L$

Dekoodaus rajoitetulla etäisyydellä

Tämä tehtävä on samanlainen kuin STAT. Jos vektori on sellainen, että sen etäisyys hilasta ei ylitä , algoritmin on palautettava lähin hilavektori. $\lambda (L)/2$

Hilan peittämisen ongelma säteillä

Hilan perustan perusteella algoritmin on löydettävä pisin etäisyys (tai joissain versioissa sen approksimaatio) mistä tahansa vektorista hilaan.

Lyhimmän perustan löytämisen ongelma

Monet ongelmat helpottuvat, jos syöttökanta koostuu lyhyistä vektoreista. Algoritmin, joka ratkaisee Shortest Basis Problem (SCB) -ongelman, on hilakanta huomioon ottaen annettava ekvivalentti kanta siten, että pisimmän vektorin pituus in on mahdollisimman lyhyt. $B$ $B'$ $B'$

PKB -ongelman γ likimääräinen versio on löytää kanta, jonka pisin vektori ei ylitä lyhimmän kannan pisimmän vektorin pituutta kertoimella 1. $\gamma$

Käytä kryptografiassa

Ongelmien keskimääräisen tapauksen vaikeus muodostaa perustan useimpien salausmenetelmien turvallisuuden todistamiselle. Kokeellinen näyttö kuitenkin viittaa siihen, että useimmilla NP-kovilla ongelmilla ei ole tätä ominaisuutta - ne ovat vaikeita vain pahimmassa tapauksessa. Monet hilateorian ongelmat on oletettu tai osoittautuneet keskimäärin vaikeiksi, mikä tekee niistä houkuttelevia kryptografisille järjestelmille. Kuitenkin joidenkin hilateoriaongelmien pahimman tapauksen vaikeutta käytetään luomaan vahvoja salausjärjestelmiä. Pahimman tapauksen vaikeusasteen käyttö tällaisissa piireissä asettaa ne niiden harvojen piirien luokkaan, jotka ovat erittäin todennäköisesti vakaita jopa kvanttitietokoneissa .

Yllä olevat hilateorian ongelmat ovat helposti ratkaistavissa, jos annetaan "hyvä" perusta. Kantavähennysalgoritmien tarkoitus tietylle hilakantalle on tuottaa uusi kanta, joka koostuu suhteellisen lyhyistä lähes ortogonaalisista vektoreista . Lenstra -Lenstra -Lovász hilakantavähennys-algoritmi ( LLL ) oli varhainen tehokas algoritmi tähän ongelmaan, joka pystyi tuottamaan pelkistetyn hilakannan polynomiajassa [32] . Tätä algoritmia ja sen lisäparannuksia on käytetty joidenkin kryptografisten järjestelmien rikkomiseen, mikä on vakiinnuttanut asemansa erittäin tärkeänä työkaluna kryptografiassa. LLL:n menestys kokeellisella tiedolla johti uskoon, että hilapohjan pienentäminen voisi olla käytännössä yksinkertainen tehtävä. Tämä usko kuitenkin murtui, kun 1990-luvun lopulla saatiin uusia tuloksia hilateorian ongelmien vaikeudesta alkaen Aitain [33] tuloksista .

Keskeisessä työssään Aitai osoitti, että ZKV oli NP-kova ja löysi joitakin yhteyksiä pahimman tapauksen monimutkaisuuden ja joidenkin hilateorian ongelmien keskimääräisen monimutkaisuuden välillä [2] . Näiden tulosten perusteella Aitai ja Dwork loivat julkisen avaimen salausjärjestelmän , jonka salassapito voidaan todistaa käyttämällä vain ZKV:n tietyn version pahimman tapauksen kovuutta [34] , mikä oli ensimmäinen tulos turvallisten järjestelmien rakentamisesta pahimman tapauksen avulla. kovuus [35] .

Katso myös

Virheillä oppimista

Muistiinpanot

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

Kirjallisuus

Subhash Khot. Hilan lyhimmän vektoriongelman approksimoinnin kovuus // J. ACM. - 2005. - T. 52 , no. 5 . - doi : 10.1145/1089023.1089027 .
Miklos Ajtai. L 2 :n lyhin vektoriongelma on NP -kova satunnaistetuille vähennyksille // Proceedings of the thirtyth annual ACM symposium on Theory of computing. — Dallas, Texas, Yhdysvallat: ACM, 1998.
Peter van Emde Boas. Toinen NP-täydellinen ongelma ja lyhyiden vektorien laskemisen monimutkaisuus hilassa . Technical Report 8104. - Amsterdamin yliopisto, matematiikan laitos, Alankomaat, 1981.
Chris Peikert. Julkisen avaimen salausjärjestelmät pahimman mahdollisen lyhimmän vektorin ongelmasta: laajennettu tiivistelmä // Proceedings of the 41st Annual ACM symposium on Theory of Computing. — Bethesda, MD, USA: ACM, 2009.
Daniele Micciancio, Shafi Goldwasser. Hilaongelmien monimutkaisuus: kryptografinen näkökulma. - 2002. - T. 671. - (Kluwer International Series in Engineering and Computer Science). — ISBN 0792376889 .
- Daniele Micciancio, Shafi Goldwasser. Hilaongelmien monimutkaisuus: kryptografinen näkökulma. - Springer US, 2011. - (The Springer International Series in Engineering and Computer Science). — ISBN 9781461508984 .
Goldreich O., Micciancio D., Safra S., Seifert J. -s. Lyhimpien hilavektorien approksimointi ei ole vaikeampaa kuin lähimpien hilavektorien approksimointi // Inf. prosessi. Lett .. - 1999. - T. 71 , no. 2 . - doi : 10.1016/S0020-0190(99)00083-6 .
Oded Goldreich, Shafi Goldwasser. Hilaongelmien ei-lähestyttävyyden rajoista // Proceedings of the 30th vuosittainen ACM symposium on Theory of computing. — Dallas, Texas, Yhdysvallat: ACM, 1998.

Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk. Likimääräisten optimien kovuus hilassa, koodeissa ja lineaariyhtälöjärjestelmissä // J. Comput. Syst. Sci.. - 1997. - V. 54 , no. 2 . - doi : 10.1109/SFCS.1993.366815 .
Dinur I., Kindler G., Safra S. CVP:n lähentäminen lähes polynomisiin tekijöihin on NP-Hard // Combinatorica. - 2003. - T. 23 , no. 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. Parannetut menetelmät hilassa olevien lyhytpituisten vektorien laskentaan, mukaan lukien monimutkaisuusanalyysi // Math. Comp.. - 1985. - T. 44 , no. 170 . - doi : 10.1090/S0025-5718-1985-0777278-8 .
Biglieri E., Calderbank R., Constantinides A., Goldsmith A., Paulraj A., Huono HV MIMO Wireless Communications. - Cambridge: Cambridge UP, 2007.
Ping Wang, Tho Le-Ngoc. List Sphere -dekoodausalgoritmi parannetuilla säteen asetusstrategioilla // Langaton henkilökohtainen viestintä. - 2011. - T. 61 , no. 1 . - doi : 10.1007/s11277-010-0018-4 .
Hassibi A., Boyd S. Kokonaislukuparametrien arviointi lineaarisissa malleissa, joissa on sovelluksia GPS:ään // IEEE Trans. Sig. Proc .. - 1998. - T. 46 , no. 11 . - doi : 10.1109/78.726808 .
Miklos Ajtai, Ravi Kumar, D. Sivakumar. Seula-algoritmi lyhimmän hilavektoriongelmaan // Proceedings of the Thirty-3thyear ACM symposium on Theory of Computing. — Hersonissos, Kreikka: ACM, 2001.
Banaszczyk W. Uudet rajat joissakin siirtoteoreemoissa lukugeometriassa // Math. Ann. . - 1993. - T. 296 , no. 1 . - doi : 10.1007/BF01445125 .
Dorit Aharonov, Oded Regev. Hilaongelmat NP coNP:ssä // J. ACM. - 2005. - T. 52 , no. 5 . - doi : 10.1145/1089023.1089025 . $\korkki$
Ajtai M. Hilaongelmien kovien ilmentymien luominen // Proceedings of the twenty-kahdeksas vuotuinen ACM symposium on Theory of Computing. - Philadelphia, Pennsylvania, Yhdysvallat: ACM, 1996.
Miklos Ajtai, Cynthia Dwork. Julkisen avaimen salausjärjestelmä, jolla on pahimman tapauksen/keskimääräisen tapauksen vastaavuus // Proceedings of the 29th century ACM symposium on Theory of Computing. - El Paso, Texas, Yhdysvallat: ACM, 1997.
Jin Yi Cai. Joidenkin hilaongelmien monimutkaisuus // Algoritminen lukuteoria. - 2000. - T. 1838. - doi : 10.1007/10722028_1 .
Lenstra AK, Lenstra HW, Lovász L. Polynomien faktorointi rationaalisilla kertoimilla // Math. Ann. . - 1982. - T. 261 , no. 4 . - doi : 10.1007/BF01457454 .
Ravi Kanan. Parannetut algoritmit kokonaislukuohjelmointiin ja niihin liittyviin hilaongelmiin // Proceedings of the Fifteenth 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. Hilakenaaminen äärimmäistä karsimista käyttämällä // Advances in Cryptology - EUROCRYPT 2010 . - Springer, Berliini, Heidelberg, 2010. - doi : 10.1007/978-3-642-13190-5_13 .
Yoshinori Aono, Phong Q. Nguyen. Satunnaisotos uudelleen: Hilalaskenta diskreetillä karsinnalla // Advances in Cryptology – EUROCRYPT 2017 . - Springer, Cham, 2017. - doi : 10.1007/978-3-319-56614-6_3 .
Daniele Micciancio, Panagiotis Voulgaris. Nopeammat eksponentiaaliset aikaalgoritmit lyhimmän vektorin ongelmaan // Diskreettejä algoritmeja käsittelevän 21. vuotuisen ACM-SIAM-symposiumin julkaisut . - Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2010. - S. 1468-1480. — (SODA '10). — ISBN 9780898716986 .
Daniele Micciancio, Panagiotis Voulgaris. Deterministinen yhden eksponentiaalisen ajan algoritmi useimmille hilaongelmille Voronoi -solulaskelmien perusteella // 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-7th Annual ACM-SIAM Symposium on Discrete Algorithms . - Teollisen ja soveltavan matematiikan seura, 2015. - S. 10–24. - (Käsittely). - doi : 10.1137/1.9781611974331.ch2 .
Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz. Lyhimmän vektoriongelman ratkaiseminen 2N ajassa käyttämällä diskreettiä Gaussin näytteenottoa: Laajennettu tiivistelmä // 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. Lattice Cryptography - Lyhin vektoriongelma . – 2017.
Schnorr CP Polynomiaikahilan peruspelkistysalgoritmien hierarkia // Tietojenkäsittelyteoria. - 1987. - Voi. 53. - Ongelma. 2 . - doi : 10.1016/0304-3975(87)90064-8 .
Schnorr CP, Euchner M. Hilakantavähennys : Parannetut käytännön algoritmit ja osajoukkosummaongelmien ratkaiseminen // Mathematical Programming. - 1994. - T. 66 , no. 1-3 . — ISSN 0025-5610 . - doi : 10.1007/bf01581144 .
Claus Peter Schnorr. Hilan vähentäminen satunnaisnäytteenotolla ja syntymäpäivämenetelmillä // STACS . - Springer, Berliini, Heidelberg, 2003. - ISBN 3540364943 . - doi : 10.1007/3-540-36494-3_14 .
Schnorr CP Kokonaislukujen faktorointi ja diskreettien logaritmien laskeminen diofantiiniapproksimaatiolla // . - 1993. - V. 13. - S. 171-181 .. - (AMS DIMACS -sarja julkaisussa Disc. Math ja Theoretical Comp. Science).
Yuanmi Chen, Phong Q. Nguyen. Kryptologian edistysaskel - ASIACRYPT 2011 . - Springer, Berliini, Heidelberg, 2011. - doi : 10.1007/978-3-642-25385-0_1 .

Lue lisää lukemista varten

Agrell E., Eriksson T., Vardy A., Zeger K. Closest Point Search in Lattices // IEEE Trans. ilmoittaa. teoria. - 2002. - T. 48 , no. 8 . - doi : 10.1109/TIT.2002.800499 .
Daniele Micciancio. Lyhyin vektoriongelma on {NP}-vaikea approksimoida johonkin vakioon // SIAM Journal on Computing. - 2001. - T. 30 , no. 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 .