Tanulás alapú kulcscsere hibákkal

A kriptográfiában a tanulás hibával kulcscsere egy olyan kriptográfiai  algoritmus, amely lehetővé teszi két fél számára, hogy létrehozzanak és kicseréljenek egy titkos kulcsot, amelyet az üzenetek egymás közötti titkosításához használnak. Az RLWE-KEX ( Ring Learning with Errors Key Exchange ) a nyilvános kulcsú algoritmusok egyike, amelyet arra terveztek, hogy védelmet nyújtson egy kvantumszámítógéppel rendelkező ellenféllel szemben . Ez azért fontos, mert a ma általánosan használt nyilvános kulcsú kriptográfiai rendszereket egy kvantumszámítógép könnyen feltöri [1] . Az RLWE-KEX egyike a sok posztkvantum kriptográfiai algoritmusnak , amely a rácsos kriptográfiával kapcsolatos matematikai problémák megoldásának összetettségén alapul [2] .  

Háttér

Az 1980-as évek óta a kriptográfiai kulcscsere és a digitális aláírások biztonsága az interneten elsősorban néhány nagy nyilvános kulcsú kriptorendszeren alapul. Ezeknek az algoritmusoknak a kriptográfiai erőssége kisszámú, klasszikus módszerekkel nehezen kiszámítható, de kvantumszámítógép segítségével meglehetősen könnyen megoldható feladaton alapul [3] . Ezek a problémák a két gondosan megválasztott prím faktorizálása, a diszkrét logaritmus kiszámításának nehézsége egy kiválasztott véges mezőben, és a diszkrét logaritmus kiszámításának nehézsége egy elliptikus görbe kiválasztott pontcsoportjában . Egyes vélemények szerint a kvantumszámítógépek 10-15 éven belül elérhetőek lesznek [4] . Ha elegendő memóriával rendelkező kvantumszámítógépeket építenének, az e három klasszikus kemény problémán alapuló összes nyilvános kulcsú titkosítási rendszer rendkívül sebezhetővé válna [1] . Ezt a típusú nyilvános kulcsú titkosítást manapság internetes oldalak , számítógép- engedélyezési információk védelmére, valamint a számítógépek rosszindulatú szoftverek fogadásának megakadályozására használják [5] .

A kvantumszámítógéppel nem feltörhető kriptográfiát kvantumbiztonságos vagy posztkvantum kriptográfiának nevezik . Ezen algoritmusok egyik osztálya az Oded Regev által bevezetett „ hibákkal tanulás ” koncepción alapul2005-ben [6] . A hibatanulás speciális formája egy véges mező feletti polinomgyűrűben működik . Ezt a speciális űrlapot Errored Learning Ringnek vagy RLWE-nek [7] nevezik .

Számos kriptográfiai algoritmus működik az RLWE paradigma alapján. Vannak nyilvános kulcsú titkosítási rendszerek , homomorf titkosítási algoritmusok és RLWE digitálisan aláírt algoritmusok a nyilvános kulcson kívül. A kulcscsere az aszimmetrikus titkosítás egyik típusa, amely megosztott titkos kulcsot hoz létre egy kommunikációs kapcsolaton lévő két kölcsönhatásban lévő ügynök között. A kulcscsere klasszikus példája a Diffie-Hellman protokoll (és ennek kiterjesztéseként az Elliptic Curve Diffie-Hellman protokoll ). A központ egy adásból áll a vonal egyik végéről és egy adásból a vonal másik végéről [8] .

Az RLWE kulcscserét a nem megbízható kommunikációs csatornákon keresztüli titkos kulcsok biztonságos generálására használt protokollok kvantumbiztos helyettesítésére tervezték. A Diffie-Hellman protokollhoz hasonlóan az RLWE is biztosítja a " tökéletesen továbbított titkosság " kriptográfiai tulajdonságát [9] , amelynek célja a tömeges megfigyelési programok hatékonyságának csökkentése és annak biztosítása, hogy ne legyenek hosszú távú titkos kulcsok, amelyek veszélyeztethetők, lehetővé téve a tömeges visszafejtést.

Az algoritmus leírása

Bevezetés

Egy q prímszámot használva az RLWE a Ф(х) polinom modulo polinom gyűrűjében dolgozik együtthatókkal a modulo q egészek mezőjében (F q [x]/Φ(x) gyűrű) [10] [8] . Az a(x) polinomot a következőképpen fejezzük ki:

Ennek a polinomnak az együtthatói modulo q egész számok . Φ(x) = x n +1 polinom , ahol n 2 hatványa (a legtöbb esetben n értéke 256, 512 vagy 1024).

Az RLWE-KEX olyan polinomokat használ, amelyek "kicsinek" tekinthetők a "végtelen" normának nevezett mértékhez képest [11]. . Egy polinom végtelen normája a legnagyobb polinomegyüttható értéke, ha az együtthatókat a { ,…, 0, …, } halmaz elemeinek tekintjük . Az algoritmus biztonsága érdekében s(x) véletlenszerű polinomokat kell generálni , amelyek kicsik a végtelen normához képest. Ez úgy történik, hogy véletlenszerűen generálunk együtthatókat a polinomhoz ( s n-1 , …, s 0 ), amelyek garantáltan vagy nagy valószínűséggel kicsik. Két általános módszer létezik:

1. Diszkrét egyenletes eloszlás használata  - Kis egyenletes mintapolinom együtthatói kis együtthatók halmazából. Legyen b egy q-nál jóval kisebb egész szám. Ha véletlenszerűen választunk együtthatókat a { -b, -b+1, -b+2 halmazból. … −2, −1, 0, 1, 2, … , b-2, b-1, b }, a polinom kicsi lesz a(x) -hoz képest . A Sing b = 5 használatát javasolja [12] . Így az együtthatók a { q-5, q-4, q-3, q-2, q-1, 0, 1, 2, 3, 4, 5 } halmazból lesznek kiválasztva .
2. Diszkrét normál eloszlást használva  - az együtthatók véletlenszerűen kerülnek kiválasztásra q páratlan értékére a { halmazból vett minta alapján ; } a diszkrét Gauss-eloszlás szerint 0 átlaggal és σ varianciával . Ez a módszer bonyolultabb, mint a diszkrét egyenletes eloszlás, de lehetővé teszi az algoritmus biztonságosságának bizonyítását [13] .

Kövessenek véletlenszerű kis polinomok az eloszlást, amelyet D -vel jelölünk . A q szám páratlan prímszámú lesz, így q ≡ 1 mod 4 és
q ≡ 1 mod 2n annak érdekében, hogy minimalizáljuk a véletlenszerű bitkiválasztási műveletek számát a beállított határon [14] . Ez lehetővé teszi az algoritmus leghatékonyabb megvalósítását [15] . A Ф(x) polinom foka 2 foka [16] .

Legyen egy rögzített a(x) polinom  közös minden hálózati felhasználó számára, amelyet egy kriptográfiailag biztonságos pszeudo-véletlenszám-generátor segítségével állítanak elő . Ha a(x) -t vesszük, az s(x) és e(x) kis polinomokat véletlenszerűen választjuk ki , s(x)  a nyilvános kulcscsere privát kulcsa . A megfelelő nyilvános kulcs a t(x) = a(x)s(x) + e(x) polinom lesz [11] . A kulcscsere biztonsága azon a nehézségen alapszik, hogy nehéz megtalálni az s'(x) és e'(x) kis polinompárt úgy, hogy egy adott t(x) esetén a(x)s'(x) + e'(x) = t(x) .

Kulcscsere

A kulcscsere Alice ( A ) és Bob ( B ) kulcscsereügynökök között zajlik. A és B is ismeri a q , n , a(x) értékeket , és a D eloszlás szerint tud kis polinomokat generálni [10] [17] .

Alice kezdeti akciói [17] :

1. Két kis s A (x) és e A (x) polinom előállítása mintavételezéssel a D eloszlásból .
2. Számítás t A (x) = a(x)•s A (x) + e A (x) .
3. t A (x) küldése Bobnak.

Bob tettei [17] :

1. Két kis s B (x) és e B (x) polinom előállítása mintavételezéssel a D eloszlásból .
2. Számítás v(x) = t A (x) s B (x) + e B (x) . Vegye figyelembe, hogy v(x) = a(x)s A (x)s B (x) + e A (x)s B (x) + e B (x) és e B (x) + e A ( x ) )s B (x) is kicsi lesz, mivel e B (x) kicsinek lett kiválasztva, az e A (x)s B (x) együtthatók növekedése korlátozott, és szintén kicsik lesznek.
3. A v(x) együttható eloszlást az együtthatók áthurkolásával és bizonyos értékek véletlenszerű beállításával simítjuk. j=0 - tól n-1- ig :
   1. Ha v j = 0 , akkor jöjjön létre egy véletlenszerű bit (jelölése b ). Ha 0 , akkor v j = 0 , ellenkező esetben v j = q-1 .
   2. Ha v j = , akkor jöjjön létre egy véletlenszerű bit( b ). Ha 0 , akkor v j = egyébként v j = .
4. 2 db c j és u j n hosszúságú bitfolyam kialakítása a v(x) együtthatókból a következő transzformációk segítségével. j=0 - tól n-1- ig :
   1. Írjuk c j -t a 4v j /q egész rész legkisebb jelentőségű bitjeként , azaz .
   2. Írj .
5. A k kulcsot u n-1 , …, u 0 összefűzéseként alkotva .
6. Egy n hosszúságú "match" karakterlánc ( C ) létrehozása c n-1 , …, c 0 összefűzéseként .
7. Számítás t B (x) = a(x) s B (x) + e B (x) .
8. t B (x) és C elküldése Alice-nek.

Alice következő lépései [17] :

1. t B (x) és C beszerzése Bobtól.
2. Számítás 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. Az n hosszúságú u j bitfolyam kialakítása a következő:
   1. Ha c j = 0 és ≤ w j < , akkor u j = 0 , ellenkező esetben u j = 1 .
   2. Ha c j = 1 és ≤ w j < , akkor u j = 0 , ellenkező esetben u j = 1 .
4. A k kulcsot u n-1 , …, u 0 összefűzéseként alkotva .

Ha a kulcscsere megfelelően működik, akkor az Alice és Bob u n-1 , …, u 0 karakterláncai megegyeznek [18] . A választott n , q , σ és b paraméterek sajátosságaitól függően fennáll annak a lehetősége , hogy t A (x) és t B (x) egyezik. A kulcscsere paramétereit úgy kell megválasztani, hogy ennek a kulcscsere-hibának a valószínűsége nagyon alacsony legyen – sokkal kisebb, mint az észlelhetetlen sérülés vagy eszközhiba valószínűsége.

Választási lehetőségek

A csere legfeljebb n-1 fokú polinomok gyűrűjében működik a Φ(х) polinom modulo -jában . Feltételezzük, hogy n 2  hatványa és q  prím, q ≡ 1 mod 4 . Peikert munkája alapján Sing két paraméterkészletet javasolt az RWLE-KEX számára [19] .

128 bites biztonság esetén : n = 512 , q = 25601 és Φ(x) = x 512 + 1

256 bites biztonság esetén : n = 1024 , q = 40961 és Φ(x) = x 1024 + 1

Mivel a kulcscsere véletlenszerű, korlátozott mintavételt használ, lehetséges, hogy ugyanazokat a kulcsokat generálják Alice és Bob számára . Tegyük fel, hogy egy Gauss-paraméter σ = vagy egyenletes mintavételt használunk b = 5 esetén, akkor a nyilvános kulcs illesztési hiba valószínűsége kisebb, mint 2 -71 és 2 -75 128 bites paraméterek esetén , és kisebb, mint 2 -91 és 2 -97 256 esetén bit paraméterek, ill. [19] .

Alkim, Duka, Popplemann és Schwabe (2015. november) a következő paramétereket javasolja: n = 1024 , q = 12289 és Φ(x) = x 1024 + 1 , mivel ezek biztosítják az algoritmus hatékonyságát és biztonságát. 256 bites biztonság esetén ez a halmaz 2 −110 egyezési hiba valószínűséget biztosít [20] .

Az algoritmus megbízhatósága

Az RLWE-KEX feltörésének számítási bonyolultsága ugyanolyan nagyságú, mint a legrövidebb vektorprobléma (SVP) megoldása ideális rácsban [21] . Egy adott rácsparaméter-készlet gyakorlati biztonságának értékelésére a legjobb módszer a BKZ 2.0 redukciós algoritmus .  (határozatlan). A BKZ 2.0 algoritmussal összhangban a fent felsorolt ​​fő csereparaméterek több mint 128, illetve 256 bites biztonságot nyújtanak [22] .

Megvalósítási példák

2014-ben Douglas Stebila javítást készített az OpenSSL 1.0.1f-hez. a "Post-quantum key exchange for the TLS protocol from the ring learning with errors problem" című könyvben megjelent munka alapján . A Synga munkaszoftvere a GitHubon található . (határozatlan)[23] .

Az algoritmus másik alkalmazása Zhang, Ding, Snook és Dagdelen "Post Quantum Authenticated Key Exchange from Ideal Lattices" munkája .  (határozatlan). A Diffie-Hellman algoritmus létrehozásának koncepcióját először Aguilar, Gaborite, Lacharme, Schreck és Zemor francia kutatók vezették be a PQCrypto 2010-ben „Noisy Diffie-Hellman Protocols” (nem elérhető link) című jelentésükben . Hozzáférés időpontja: 2015. december 1. Az eredetiből archiválva : 2015. szeptember 24. (határozatlan)  . Ezt a témát azután kibővítették, és Peukert munkája (határozatlan) szigorúbb tanulmányozásának kezdetét jelentette . [24] .

Lásd még

• Posztkvantum kriptográfia
• Kriptográfia rácsokon
• Tanulás hibákkal

Jegyzetek

1. ↑ 1 2 Valiev, 2000 .
2. ↑ Lyubashevsky, Peikert, Regev, 2013 , pp. 1-2.
3. ↑ Kvantumszámítógépre volt szükség az NSA titkosításainak feltöréséhez . Letöltve: 2015. november 27. Az eredetiből archiválva : 2015. december 8.. (határozatlan)
4. ↑ A kvantumszámítógép létrehozása mérnöki kihívássá válik . Hozzáférés dátuma: 2015. december 5. Az eredetiből archiválva : 2015. november 7.. (határozatlan)
5. ↑ Nyilvános kulcsú titkosítási rendszerek . Letöltve: 2015. november 27. Az eredetiből archiválva : 2015. december 8.. (határozatlan)
6. ↑ Regev, Oded. A rácsokról, a hibákkal való tanulásról, a véletlenszerű lineáris kódokról és a kriptográfiáról  //  Proceedings of the Thirty-7th Annual ACM Symposium on Theory of Computing : folyóirat. - New York, NY, USA: ACM, 2005. - Vol. STOC'05 . - 84-93 . o . — ISBN 1-58113-960-8 . - doi : 10.1145/1060590.1060603 .
7. ↑ Lyubashevsky, Peikert, Regev, 2013 , pp. 35-37.
8. ↑ Singh 12 , 2015 , pp. 2.
9. ↑ Singh, 2015 , pp. egy.
10. ↑ 1 2 Peikert, 2014 , pp. 200-201.
11. ↑ Singh 12 , 2015 , pp. 1-2.
12. ↑ Singh, 2015 , pp. 7.
13. ↑ Peikert, 2010 , pp. 15-16.
14. ↑ Singh, 2015 , pp. 9-10.
15. ↑ Alkim et al, 2015 , pp. 18-20.
16. ↑ Singh, 2015 , pp. 10-11.
17. ↑ 1 2 3 4 Singh, 2015 , pp. 8-11.
18. ↑ Singh, 2015 , pp. nyolc.
19. ↑ Singh 12 , 2015 , pp. 21-24.
20. ↑ Alkim et al, 2015 , pp. 6:15-16.
21. ↑ Peikert, 2014 , pp. 204-205.
22. ↑ Singh, 2015 , pp. 22.
23. ↑ Singh, 2015 , pp. 26.
24. ↑ Lyubashevsky, Peikert, Regev, 2013 , pp. 47-48.

Irodalom

• Peikert C. Lattice Cryptography for the Internet  // Post-Quantum Cryptography : 6th International Workshop, PQCrypto 2014, Waterloo, ON, Canada, 2014. október 1-3. Proceedings / M. Mosca - Berlin , Heidelberg , New York, NY , London [stb.] : Springer International Publishing , 2014. - P. 197-219. - ( Számítástechnikai előadások jegyzetei ; 8772. kötet) - ISBN 978-3-319-11658-7 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-319-11659-4_12
• Singh, Vikram. Gyakorlati kulcscsere az internethez a rácsos kriptográfia segítségével  31. International Association for Cryptologic Research (2015) .
• Lyubashevsky, Vadim, Peikert, Chris; Regev, Chris. Eszközkészlet a Ring-LWE kriptográfiához  (angol)  // Advances in Cryptology - EUROCRYPT 2013: gyűjtemény. - Springer-Verlag Berlin Heidelberg, 2013. - P. 3-54 . - ISBN 978-3-642-38348-9 . — ISSN 0302-9743 . - doi : 10.1007/978-3-642-38348-9_3 .
• Alkim, Erdem; Ducas, Oroszlán; Poppelman, Thomas; Schwabe, Péter. Post-quantum key exchange - a new hope  (angol) 32. International Association for Cryptologic Research (2015).
• Joppe W. Bos; Craig Costello; Michael Naehrig; Douglas Stebila. Post-kvantumkulcscsere a TLS protokollhoz a Ring Learning with Errors Problem-ből  (angol)  // Biztonság és adatvédelem (SP): gyűjtemény. - 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 using homomorphic cryptography  // Security of Information Technologies : Journal. - 2013. - január ( 1. sz .). - S. 1-12 . — ISSN 2074-7128 . (Orosz)
• Valiev K.A. Kvantuminformatika: számítógépek, kommunikáció és kriptográfia  // Az Orosz Tudományos Akadémia közleménye: folyóirat. - 2000. - augusztus ( 70. évf. 8. szám ). - S. 688-695 . — ISSN 0869-5873 . (Orosz)
• Peikert, Chris. Egy hatékony és párhuzamos Gauss-féle mintavevő rácsokhoz  (angol)  // Advances in Cryptology - CRYPTO 2010: gyűjtemény. - Springer Berlin Heidelberg, 2010. - P. 80-97 . — ISBN 978-3-642-14622-0 . — ISSN 0302-9743 . - doi : 10.1007/978-3-642-14623-7_5 .