Virheillä oppimista

Virheillä oppiminen ( LWE ) on ongelma kertoimilla varustetun polynomin löytämisessä tietystä jäännösrenkaasta , jolle on annettu lineaarinen yhtälöjärjestelmä , jossa on virheitä (mikä tekee yksinkertaisesta laskentatehtävästä vaikeaa).

Oded Regevin vuonna 2005 esittelemä LWE on osoittautunut erittäin monipuoliseksi kehykseksi kryptografisille rakenteille, erityisesti postkvanttisalausalgoritmeille [ 1 ] [2] .

Virheoppimisongelman muunnelmaa, jossa polynomeja huomioidaan polynomien tekijärenkaassa tietyllä polynomilla, kutsutaan oppimiseksi virheiden kanssa renkaassa .

Määritelmä

Kiinnitetään parametri , moduuli ja ” virhetodennäköisyyden ” jakauma kohtaan . Antaa olla todennäköisyysjakauma , joka saadaan valitsemalla vektori tasaisesti satunnaisesti, valitsemalla virheen mukaisesti ja tuloksena oleva lauseke , jossa ja summaus suoritetaan modulo . $n\geqslant 1$ $q\geqslant 2$ $\chi$ ${Z}_{q}$ $A_{\mathbf {s} ,\chi }$ $\mathbb {Z} _{q}^{n}\times \mathbb {Z} _{q}$ $\mathbf {a} \in \mathbb {Z} _{q}^{n}$ $\mathbf {e} \in \mathbb {Z} _{q}$ $\chi$ $(\mathbf {a} ,\langle \mathbf {a} ,\mathbf {s} \rangle +e)$ $\textstyle \langle \mathbf {a} ,\mathbf {s} \rangle =\sum _{i=1}^{n}a_{i}s_{i}$ $q$

Sanotaan [3] , että algoritmi ratkaisee ongelman , jos jollakin , jolla on mielivaltainen polynomimäärä riippumattomia suhteita kohteesta , se tuottaa suurella todennäköisyydellä . $\mathrm {LWE} _{q,\chi }$ $\mathbf {s} \in \mathbb {Z} _{q}^{n}$ $A_{\mathbf {s} ,\chi }$ $s$

Ulkoasuhistoria

LWE-konseptin syntyä jäljitetään Miklós Aitain ja Cynthia Dworkin teoksissa [4] . He kuvasivat ensimmäisen julkisen avaimen salausjärjestelmän , jossa käytettiin hila kryptografiaa , ja sen myöhempiä parannuksia ja muutoksia [5] . LWE:tä ei esitelty eksplisiittisesti näissä papereissa, mutta Aitai-Dwork-rakenteen huolellinen tarkastelu, yksinkertaistettu Regevin artikkelissa [6] , osoittaa [3] , että LWE-ideat tulevat epäsuorasti esiin tässä paperissa.

On syytä huomata, että tämän alan varhainen tutkimus [4] [6] perustui riittämättömästi tutkittuun ongelmaan löytää ainutlaatuinen lyhin vektori . Pitkään aikaan ei ollut selvää, voitaisiinko se korvata standardinmukaisemmilla hilaongelmilla . Myöhemmin Chris Peikert [7] ja Vadim Lyubashevsky Daniele Micchancion kanssa selvittivät [8] , että ainutlaatuisen lyhimmän vektorin löytämisen ongelma on itse asiassa vastaava standardi GapSVP - hilaongelmalle , mikä johti selkeämpään kuvaan tällä alueella.

Esimerkki ongelmasta

Tarkastellaan tyypillistä LWE-ongelmaa [3] : on tarpeen palauttaa vektori , jolla on likimääräisten lineaaristen yhtälöiden sarja x:ssä. Esimerkiksi: $x\in \mathbb {Z} _{q}^{n}$

{\begin{cases}14x_{1}+15x_{2}+5x_{3}+2x_{4}=8(mod17)\\13x_{1}+14x_{2}+14x_{3}+ 6x_{4}=16(mod17)\\\pisteet \\6x_{1}+7x_{2}+16x_{3}+2x_{4}=3(mod17),\\\end{cases}}

jossa jokainen relaatio on tosi pieni lisävirheellä, sanotaan ± , ja tavoitteenamme on palautua (tässä esimerkissä ). Ilman virhettä se olisi helppo löytää: esimerkiksi polynomiajassa Gaussin menetelmällä . Virheen huomioon ottaminen tekee tehtävästä paljon vaikeampaa, koska jokaisella iteraatiolla virhe kasvaa ja saavuttaa lopulta hallitsemattomia arvoja [3] . $yksi$ $x$ $x=(0,13,9,11)$ $x$

Salaussovellukset

LWE:n kryptografisten sovellusten valikoima on viime aikoina tullut melko laajaksi. Alla olevan kryptosysteemiesimerkin lisäksi on olemassa tehokkaampia järjestelmiä [2] [9] . Lisäksi Ring-LWE:n käyttö voi tehdä järjestelmästä todella käyttökelpoisen [10] .

Erityisesti on syytä huomata, että LWE:tä voidaan käyttää perustana luotaessa kryptografisia järjestelmiä, jotka tarjoavat täysin homomorfisen salauksen . Sitä käytettiin esimerkiksi julkisesti saatavilla olevan FHEW-kirjaston [11] toteutuksessa .

Julkisen avaimen järjestelmä

Tarkastellaan yksinkertaista esimerkkiä Regevin [1] ehdottamasta julkisen avaimen salausjärjestelmästä . Se perustuu LWE-ongelman ratkaisun monimutkaisuuteen. Järjestelmää kuvataan seuraavilla numeroilla: -salainen parametri, -ulottuvuus, -moduuli ja todennäköisyysjakauma . Järjestelmän turvallisuuden ja oikeellisuuden varmistamiseksi on valittava seuraavat vaihtoehdot: $n$ $m$ $q$ $\chi \in \mathbb {Z} _{q}$

$q\geq 2$ , ja välissä oleva alkuluku $n^{2}$ $2n^{2}$
$m=(1+\epsilon )(n+1)\log {q}$ mielivaltaiselle vakiolle $\epsilon$
$\alpha (n)=1/{\sqrt {n}}\log ^{2}{n}$

Sitten kryptojärjestelmä määritellään seuraavasti:

Salainen avain : Salainen avain valitaan mielivaltaisesti. $\mathbf {s} \in \mathbb {Z} _{q}^{n}$
Julkinen avain : valitaan vektorit mielivaltaisesti ja itsenäisesti. Valitaan hyväksyttävät virheet itsenäisesti jakauman mukaan . Julkinen avain koostuu $m$ $a_{1},\ldots ,a_{m}\in \mathbb {Z} _{q}^{n}$ $e_{1},\ldots ,e_{m}\in \mathbb {Z} _{q}$ $\chi$ $(a_{i},b_{i}=\langle a_{i},\mathbf {s} \rangle /q+e_{i})_{i=1}^{m}$
Salaus : Bittisalaus tehdään seuraavasti : valitaan satunnainen osajoukko ja salaus määritetään $x\in\{0,1\}$ $S$ $[m]$ $Enc(x)$ $(\sum _{i\in S}a_{i},x/2+\sum _{i\in S}b_{i})$
Salauksen purkaminen : Tämän purkaminen, jos se on lähempänä kuin , ja muuten. $(a, b)$ $0$ $b-\langle a,\mathbf {s} \rangle /q$ $0$ ${\frac {1}{2))$ $yksi$

Oded Regev osoitti teoksissaan [1] [3] tämän kryptojärjestelmän oikeellisuuden ja turvallisuuden sopivalla parametrivalinnalla.

Muistiinpanot

↑ 1 2 3 4 Oded Regev "On hilat, oppiminen virheillä, satunnaiset lineaariset koodit ja kryptografia", julkaisussa Proceedings of the 37. vuotuinen ACM symposium on Theory of Computing (Baltimore, MD, USA: ACM, 2005), 84 -93, http://portal.acm.org/citation.cfm?id=1060590.1060603 .
↑ 1 2 D. Micciancio ja O. Regev. Hilapohjainen kryptografia. Julkaisussa DJ Bernstein ja J. Buchmann, toimittajat, Post-quantum Cryprography. Springer, 2008
↑ 1 2 3 4 5 Oded Regev, "The Learning with Errors Problem" http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf Arkistoitu 23. syyskuuta 2015 Wayback Machinessa
↑ 1 2 M. Ajtai ja C. Dwork. Julkisen avaimen salausjärjestelmä, jossa on pahimman tapauksen/keskimääräisen tapauksen vastaavuus. Julkaisussa Proc. 29th Annual ACM Symp. on Theory of Computing (STOC), sivut 284-293. 1997
↑ M. Ajtai ja C. Dwork. Ensimmäinen ja neljäs julkisen avaimen salausjärjestelmä pahimman tapauksen/keskimääräisen tapauksen vastaavuudella, 2007. Saatavilla ECCC:stä osoitteesta http://www.uni-trier.de/eccc/ (linkki ei saatavilla)
↑ 1 2 O. Regev. Uudet hilapohjaiset kryptografiset rakenteet. Journal of the ACM, 51(6):899-942, 2004. Alustava versio STOC'03:ssa
↑ C. Peikert. Julkisen avaimen salausjärjestelmät pahimman mahdollisen lyhimmän vektoriongelmasta. Julkaisussa Proc. 41. ACM Symp. on Theory of Computing (STOC), sivut 333-342. 2009
↑ V. Lyubashevsky ja D. Micciancio. Rajoitetun etäisyyden dekoodauksesta, ainutlaatuisista lyhyimmistä vektoreista ja minimietäisyyden ongelmasta. Kirjassa CRYPTO, sivut 577-594. 2009.
↑ C. Peikert, V. Vaikuntanathan ja B. Waters. Puitteet tehokkaalle ja muokattavalle tietämättömälle siirrolle. Kirjassa CRYPTO, sivut 554-571. 2008
↑ V. Lyubashevsky, C. Peikert ja O. Regev. Ihanteellisella hilalla ja oppiminen virheillä renkaiden yli. EUROCRYPT:ssä. 2010.
↑ Leo Ducas, Daniele Micciancio. FHEW: Täysin homomorfinen salauskirjasto . Käyttöpäivä: 31. joulukuuta 2014. Arkistoitu alkuperäisestä 21. toukokuuta 2016. (määrätön)

Kirjallisuus

Post-quantum Cryptography (uuspr.) . - Springer, 2008. - S. 245. - ISBN 978-3540887010 .
Peikert, Chris. Lattice Cryptography for the Internet (uuspr.) / Mosca, Michele. - Springer International Publishing , 2014. - S. 197-219. — (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 978-3-319-11658-7 .
Chen, Yuanmi; Phong Q., Nguyen . BKZ 2.0 : Paremmat ristikon suojausarviot . - Springer Berlin Heidelberg, 2011. - S. 1-20.