Oppimiseen perustuva avainten vaihto virheineen

Salaustekniikassa oppiminen virheen kanssa avaimen vaihto on  salausalgoritmi, jonka avulla kaksi osapuolta voivat luoda ja vaihtaa salaisen avaimen, jota ne käyttävät viestien salaamiseen keskenään. RLWE-KEX ( Ring Learning with Errors Key Exchange ) on yksi julkisen avaimen algoritmeista , joka on suunniteltu suojaamaan vastustajalta, jolla on kvanttitietokone . Tämä on tärkeää, koska nykyään yleisesti käytössä olevat julkisen avaimen salausjärjestelmät rikkoutuvat helposti kvanttitietokoneella [1] . RLWE-KEX on yksi monista post-kvanttisalausalgoritmeista, jotka perustuvat hilasalaukseen liittyvien matemaattisten ongelmien ratkaisemisen monimutkaisuuteen [2] .  

Tausta

1980-luvulta lähtien salausavainten vaihdon ja digitaalisten allekirjoitusten turvallisuus Internetissä on perustunut pääasiassa pieneen määrään suuria julkisen avaimen salausjärjestelmiä. Näiden algoritmien kryptografinen vahvuus perustuu pieneen määrään ongelmia, joita on vaikea laskea klassisilla menetelmillä, mutta melko helposti ratkaistavissa kvanttitietokoneella [3] . Näitä ongelmia ovat kahden huolellisesti valitun alkuluvun tekijöihin jakaminen , diskreetin logaritmin laskemisen vaikeus valitussa äärellisessä kentässä ja diskreetin logaritmin laskemisen vaikeus valitussa pisteryhmässä elliptisellä käyrällä . On olemassa mielipide, että kvanttitietokoneet ovat saatavilla 10-15 vuoden kuluttua [4] . Jos rakennettaisiin kvanttitietokoneita, joissa on riittävästi muistia, kaikki näihin kolmeen klassiseen kovaan ongelmaan perustuvat julkisen avaimen salausjärjestelmät tulisivat erittäin haavoittuvia [1] . Tämän tyyppistä julkisen avaimen salausta käytetään nykyään suojaamaan Internet-sivustoja , tietokoneiden valtuutustietoja ja estämään tietokoneita vastaanottamasta haittaohjelmia [5] .

Kryptografiaa, jota kvanttitietokone ei voi rikkoa, kutsutaan kvanttiturvalliseksi tai postkvanttisalaukseksi . Yksi näiden algoritmien luokka perustuu Oded Regevin esittämään " virheiden kanssa oppimisen " käsitteeseenvuonna 2005 [6] . Erityinen virheoppimisen muoto toimii polynomirenkaassa äärellisen kentän päällä . Tätä erikoismuotoa kutsutaan Errored Learning Ringiksi tai RLWE:ksi [7] .

On monia salausalgoritmeja, jotka toimivat RLWE-paradigman avulla. Julkisen avaimen lisäksi on olemassa julkisen avaimen salausjärjestelmiä , homomorfisia salausalgoritmeja ja digitaalisesti allekirjoitettuja RLWE- algoritmeja . Avainten vaihto on eräänlainen epäsymmetrinen salaus , joka muodostaa jaetun salaisen avaimen kahden vuorovaikutuksessa olevan agentin välille viestintälinkissä. Klassinen esimerkki avaintenvaihdosta on Diffie-Hellman-protokolla (ja sen laajennuksena elliptisen käyrän Diffie-Hellman-protokolla ). Vaihto koostuu yhdestä lähetyksestä linjan toisesta päästä ja yhdestä lähetyksestä linjan toisesta päästä [8] .

RLWE-avainvaihto on suunniteltu kvanttiturvalliseksi korvaajaksi protokollille , joita käytetään luomaan turvallisesti salaisia ​​avaimia epäluotettavilla viestintäkanavilla. Kuten Diffie-Hellman-protokolla, RLWE tarjoaa salausominaisuuden " täydellisesti eteenpäin salassapito " [9] , jonka tavoitteena on vähentää massavalvontaohjelmien tehokkuutta ja varmistaa, ettei ole olemassa pitkäaikaisia ​​salaisia ​​avaimia, jotka voivat vaarantua, mikä mahdollistaisi joukkosalauksen purkamisen.

Algoritmin kuvaus

Johdanto

Alkulukua q käyttäen RLWE toimii polynomin renkaassa modulo polynomin Ф(х) kertoimilla kokonaislukujen kentässä modulo q (rengas F q [x]/Φ(x)) [10] [8] . Polynomi a(x) ilmaistaan ​​seuraavasti:

Tämän polynomin kertoimet ovat kokonaislukuja modulo q . Polynomi Φ(x) = x n +1 , jossa n on 2 :n potenssi (useimmissa tapauksissa n:n arvot = 256, 512 tai 1024).

RLWE-KEX käyttää polynomeja, joita pidetään "pieninä" suhteessa mittaan, jota kutsutaan "äärettömäksi" normiksi [11] . Polynomin ääretön normi on suurimman polynomikertoimen arvo, kun kertoimia pidetään joukon { ,…, 0, …, } elementteinä. Algoritmin turvallisuuden varmistamiseksi on tarpeen generoida satunnaisia ​​polynomeja s(x) , jotka ovat pieniä suhteessa äärettömään normiin. Tämä tehdään generoimalla satunnaisesti kertoimet polynomille ( s n-1 , …, s 0 ), jotka ovat taattuja tai suurella todennäköisyydellä pieniä. On olemassa kaksi yleistä tapaa:

1. Diskreetin tasajakauman käyttäminen  - Pienen tasaisen otospolynomin kertoimet pienten kertoimien joukosta. Olkoon b kokonaisluku paljon pienempi kuin q. Valittaessa kertoimia satunnaisesti joukosta { -b, -b+1, -b+2. … −2, −1, 0, 1, 2, … , b-2, b-1, b }, polynomi on pieni suhteessa a(x) . Sing ehdottaa b = 5 :n käyttöä [12] . Siten kertoimet valitaan joukosta { q-5, q-4, q-3, q-2, q-1, 0, 1, 2, 3, 4, 5 }.
2. Diskreetin normaalijakauman avulla  - kertoimet valitaan satunnaisesti q :n parittomille arvoille käyttämällä näytettä joukosta { ; } diskreetin Gaussin jakauman mukaan keskiarvolla 0 ja varianssilla σ . Tämä menetelmä on monimutkaisempi kuin diskreetti tasainen jakauma, mutta sen avulla voit todistaa algoritmin turvallisuuden [13] .

Seuraakoon satunnaiset pienet polynomit jakaumaa, jota merkitään D :llä . Luku q on pariton alkuluku siten, että q ≡ 1 mod 4 ja
q ≡ 1 mod 2n , jotta minimoidaan satunnaisten bittien valintaoperaatioiden määrä asetetulla rajalla [14] . Näin voit toteuttaa algoritmin tehokkaimmin [15] . Polynomin Ф(x) aste on 2: n aste [16] .

Olkoon kiinteä polynomi a(x)  yhteinen kaikille verkon käyttäjille, generoituna kryptografisesti suojatulla näennäissatunnaislukugeneraattorilla . Ottaen a(x) , pienet polynomit s(x) ja e(x) valitaan satunnaisesti , s(x)  on yksityinen avain julkisen avaimen vaihdossa. Vastaava julkinen avain on polynomi t(x) = a(x)s(x) + e(x) [11] . Avaintenvaihdon suojaus perustuu vaikeuteen löytää pari pieniä polynomia s'(x) ja e'(x) siten, että tietylle t(x) a(x)s'(x) + e'(x) = t(x) .

Avainten vaihto

Avainten vaihto tapahtuu avaintenvaihtoagenttien Alicen , merkintä A , ja Bobin , nimeltä B , välillä. Sekä A että B tietävät q , n , a(x) ja voivat generoida pieniä polynomeja jakauman D mukaisesti [10] [17] .

Liisan ensimmäiset toimet [17] :

1. Kahden pienen polynomin s A (x) ja e A (x) generointi näytteillepanolla jakaumasta D .
2. Laskenta t A (x) = a(x)•s A (x) + e A (x) .
3. Lähetetään t A (x) Bobille.

Bobin toimet [17] :

1. Kahden pienen polynomin s B (x) ja e B (x) generointi näytteillepanolla jakaumasta D .
2. Laskenta v(x) = t A (x) s B (x) + e B (x) . Huomaa, että v(x) = a(x)s A (x)s B (x) + e A (x)s B (x) + e B (x) ja e B (x) + e A ( x ) )s B (x) on myös pieni, koska e B (x) valittiin pieneksi, kertoimet e A (x) s B (x) ovat kasvussa rajoitettuja ja ovat myös pieniä.
3. Kerroinjakauma v(x) tasoitetaan silmukalla kertoimia ja säätämällä satunnaisesti tiettyjä arvoja. j =0 arvoon n-1 :
   1. Jos v j = 0 , niin keksi satunnainen bitti (merkitty b ). Jos se on 0 , niin v j = 0 , muuten v j = q-1 .
   2. Jos v j = , niin keksi satunnainen bitti( b ). Jos se on 0 , niin v j = muuten v j = .
4. 2 bittivirran c j ja u j , joiden pituus on n , muodostaminen kertoimista v(x) käyttämällä seuraavia muunnoksia. j =0 arvoon n-1 :
   1. Kirjoita c j kokonaislukuosan 4v j /q vähiten merkitseväksi bitiksi , eli .
   2. Kirjoita .
5. Avaimen k muodostaminen u n-1 , …, u 0 ketjutuksena .
6. "Match"-merkkijonon ( C ), jonka pituus on n , muodostaminen c n-1 , …, c 0 ketjutuksena .
7. Laskenta t B (x) = a(x) s B (x) + e B (x) .
8. Lähetetään t B (x) ja C Alicelle.

Liisen seuraavat askeleet [17] :

1. Haetaan t B (x) ja C Bobilta.
2. Laskenta w(x) = t B (x) s A (x) + e A (x) = a (x) s A (x) s B (x) + e B (x) s A (x) + e A (x) .
3. Bittivirran u j , jonka pituus on n , muodostuminen on seuraava:
   1. Jos c j = 0 ja ≤ w j < niin u j = 0 , muuten u j = 1 .
   2. Jos c j = 1 ja ≤ w j < niin u j = 0 , muuten u j = 1 .
4. Avaimen k muodostaminen u n-1 , …, u 0 ketjutuksena .

Jos avainten vaihto toimii oikein, merkkijonot u n-1 , …, u 0 Alicelle ja Bobille vastaavat [18] . Valittujen parametrien n , q , σ ja b ominaisuuksista riippuen on mahdollista , että t A (x) ja t B (x) täsmäävät. Avaintenvaihdon parametrit on valittava siten, että tämän avaimenvaihtovirheen todennäköisyys on hyvin pieni – paljon pienempi kuin havaitsemattoman vioittumisen tai laitevian todennäköisyys.

Vaihtoehtojen valinta

Vaihto toimii polynomin renkaassa, jonka aste on enintään n-1 moduloi polynomia Φ(х) . Oletetaan, että n on 2: n  potenssi ja q  on alkuluku, q ≡ 1 mod 4 . Peikertin työn perusteella Sing ehdotti kahta parametrijoukkoa RWLE-KEX:lle [19] .

128 - bittiselle suojaukselle: n = 512 , q = 25601 ja Φ (x) = x 512 + 1

256 - bittinen suojaus: n = 1024 , q = 40961 ja Φ(x) = x 1024 + 1

Koska avainten vaihto käyttää satunnaista rajoitettua otantaa, on mahdollista, että samat avaimet luodaan Alicelle ja Bobille . Oletetaan, että Gaussin parametri on σ = tai tasaista näytteenottoa käytetään b = 5 :n kanssa , jolloin julkisen avaimen sovitusvirheen todennäköisyys on pienempi kuin 2 -71 ja 2 -75 128 - bittisille parametreille ja pienempi kuin 2 -91 ja 2 -97 arvolle 256 bittiparametrit, vastaavasti [19] .

Alkim, Duka, Popplemann ja Schwabe (marraskuu 2015) suosittelevat seuraavia parametreja: n = 1024 , q = 12289 ja Φ(x) = x 1024 + 1 , koska ne varmistavat algoritmin tehokkuuden ja turvallisuuden. Jos kyseessä on 256 - bittinen suojaus, tämä sarja tarjoaa täsmäysvirhetodennäköisyyden 2 −110 [20] .

Algoritmin luotettavuus

RLWE-KEX:n katkaisun laskennallinen monimutkaisuus on samaa luokkaa kuin lyhimmän vektorin ongelman (SVP) ratkaiseminen ideaalisessa hilassa [21] . Paras tapa arvioida tietyn hilaparametrijoukon käytännön turvallisuutta on BKZ 2.0 - pelkistysalgoritmi .  (määrätön). BKZ 2.0 -algoritmin mukaisesti yllä luetellut tärkeimmät vaihtoparametrit tarjoavat vastaavasti yli 128 ja 256 bitin suojauksen [22] .

Toteutusesimerkkejä

Vuonna 2014 Douglas Stebila teki korjaustiedoston OpenSSL 1.0.1f:lle. perustuu kirjassa "Post-quantum key exchange for the TLS protocol from the ring learning with errors Problem" julkaistuun työhön . Syngan työohjelmisto on GitHubissa . (määrätön)[23] .

Toinen algoritmin sovellus on Zhangin, Dingin, Snookin ja Dagdelenin työ "Post Quantum Authenticated Key Exchange from Ideal Lattices" .  (määrätön). Diffie-Hellman-algoritmin luomisen käsitteen esittelivät ensimmäisenä ranskalaiset tutkijat Aguilar, Gaborite, Lacharme, Schreck ja Zemor PQCrypto 2010 -tapahtumassa raportissaan "Noisy Diffie-Hellman Protocols" (linkki ei saatavilla) . Käyttöpäivä: 1. joulukuuta 2015. Arkistoitu alkuperäisestä 24. syyskuuta 2015. (määrätön)  . Tätä aihetta laajennettiin sitten ja se merkitsi alkua Peukertin tiukemmille tutkimuksille työssään .  (määrätön)[24] .

Katso myös

• Postkvanttisalaus
• Kryptografia ristikoilla
• Virheillä oppimista

Muistiinpanot

1. ↑ 1 2 Valiev, 2000 .
2. ↑ Lyubashevsky, Peikert, Regev, 2013 , s. 1-2.
3. ↑ Kvanttitietokone tarvittiin murtamaan NSA:n salaukset . Haettu 27. marraskuuta 2015. Arkistoitu alkuperäisestä 8. joulukuuta 2015. (määrätön)
4. ↑ Kvanttitietokoneen luomisesta tulee tekninen haaste . Käyttöpäivä: 5. joulukuuta 2015. Arkistoitu alkuperäisestä 7. marraskuuta 2015. (määrätön)
5. ↑ Julkisen avaimen salausjärjestelmät . Haettu 27. marraskuuta 2015. Arkistoitu alkuperäisestä 8. joulukuuta 2015. (määrätön)
6. ↑ Regev, Oded. Hiloista, virheistä oppimisesta, satunnaisista lineaarisista koodeista ja kryptografiasta  //  Proceedings of the Thirty-7th Annual ACM Symposium on Theory of Computing : Journal. - New York, NY, USA: ACM, 2005. - Voi. STOC'05 . - s. 84-93 . — ISBN 1-58113-960-8 . - doi : 10.1145/1060590.1060603 .
7. ↑ Lyubashevsky, Peikert, Regev, 2013 , s. 35-37.
8. ↑ 12 Singh , 2015 , s. 2.
9. ↑ Singh, 2015 , s. yksi.
10. ↑ 1 2 Peikert, 2014 , s. 200-201.
11. ↑ 12 Singh , 2015 , s. 1-2.
12. ↑ Singh, 2015 , s. 7.
13. ↑ Peikert, 2010 , s. 15-16.
14. ↑ Singh, 2015 , s. 9-10.
15. ↑ Alkim et al, 2015 , s. 18-20.
16. ↑ Singh, 2015 , s. 10-11.
17. ↑ 1 2 3 4 Singh, 2015 , s. 8-11.
18. ↑ Singh, 2015 , s. kahdeksan.
19. ↑ 12 Singh , 2015 , s. 21-24.
20. ↑ Alkim et al, 2015 , s. 6:15-16.
21. ↑ Peikert, 2014 , s. 204-205.
22. ↑ Singh, 2015 , s. 22.
23. ↑ Singh, 2015 , s. 26.
24. ↑ Lyubashevsky, Peikert, Regev, 2013 , s. 47-48.

Kirjallisuus

• Peikert C. Lattice Cryptography for the Internet  // Post-Quantum Cryptography : 6th International Workshop, PQCrypto 2014, Waterloo, ON, Kanada, 1.-3.10.2014. Proceedings / M. Mosca - Berlin , Heidelberg , New York, NY , Lontoo [jne.] : Springer International Publishing , 2014. - s. 197-219. - ( Lecture Notes in Computer Science ; Voi. 8772) - ISBN 978-3-319-11658-7 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-319-11659-4_12
• Singh, Vikram. Käytännön avainten vaihto Internetiin käyttämällä hila kryptografiaa  31. International Association for Cryptologic Research (2015) .
• Lyubashevsky, Vadim, Peikert, Chris; Regev, Chris. Toolkit for Ring-LWE Cryptography  (englanniksi)  // Advances in Cryptology - EUROCRYPT 2013: kokoelma. - Springer-Verlag Berlin Heidelberg, 2013. - S. 3-54 . - ISBN 978-3-642-38348-9 . — ISSN 0302-9743 . - doi : 10.1007/978-3-642-38348-9_3 .
• Alkim, Erdem; Ducas, Leijona; Poppelman, Thomas; Schwabe, Peter. Post-quantum key exchange - a new hope  (englanniksi) 32. International Association for Cryptologic Research (2015).
• Joppe W. Bos; Craig Costello; Michael Naehrig; Douglas Stebila. Post-kvanttiavainten vaihto TLS-protokollaa varten Ring Learning with Errors Problem -ohjelmasta  (englanniksi)  // Security and Privacy (SP): kokoelma. - IEEE, 2015. - P. 553-570 . - ISBN 978-3-642-38348-9 . — ISSN 1081-6011 . - doi : 10.1109/SP.2015.40 .
• Zhirov A. O., Zhirova O. V., Krendelev S. F. Secure cloud computing käyttäen homomorfista kryptografiaa  // Tietoteknologioiden tietoturva : päiväkirja. - 2013. - tammikuu ( nro 1 ). - S. 1-12 . — ISSN 2074-7128 . (Venäjän kieli)
• Valiev K.A. Kvanttiinformatiikka: tietokoneet, viestintä ja kryptografia  // Venäjän tiedeakatemian tiedote: aikakauslehti. - 2000. - elokuu ( nide 70 , nro 8 ). - S. 688-695 . — ISSN 0869-5873 . (Venäjän kieli)
• Peikert, Chris. Tehokas ja rinnakkainen Gaussian Sampler for Lattices  (englanniksi)  // Advances in Cryptology - CRYPTO 2010: kokoelma. - Springer Berlin Heidelberg, 2010. - S. 80-97 . — ISBN 978-3-642-14622-0 . — ISSN 0302-9743 . - doi : 10.1007/978-3-642-14623-7_5 .