Inlärningsbaserat nyckelutbyte med fel

Inom kryptografi är inlärning-med-fel nyckelutbyte en  kryptografisk algoritm som tillåter två parter att skapa och utbyta en hemlig nyckel, som de använder för att kryptera meddelanden sinsemellan. RLWE-KEX ( Ring Learning with Errors Key Exchange ) är en av de publika nyckelalgoritmerna som är designade för att skydda mot en motståndare som har en kvantdator . Detta är viktigt eftersom de kryptografiska systemen med offentlig nyckel som används idag lätt bryts av en kvantdator [1] . RLWE-KEX är en av många post-kvantkryptografiska algoritmer baserade på komplexiteten i att lösa matematiska problem relaterade till gitterkryptografi [2] .  

Bakgrund

Sedan 1980-talet har säkerheten för utbyte av kryptografiska nycklar och digitala signaturer på Internet i första hand baseras på ett litet antal stora kryptosystem med offentliga nyckel. Den kryptografiska styrkan hos dessa algoritmer är baserad på ett litet antal problem som är svåra att beräkna med klassiska metoder, men som ganska enkelt kan lösas med hjälp av en kvantdator [3] . Dessa problem är faktoriseringen av två noggrant utvalda primtal , svårigheten att beräkna den diskreta logaritmen i ett valt ändligt fält, och svårigheten att beräkna den diskreta logaritmen i en vald grupp av punkter på en elliptisk kurva . Det finns en uppfattning om att kvantdatorer kommer att finnas tillgängliga om 10-15 år [4] . Om kvantdatorer med tillräckligt med minne byggdes skulle alla kryptosystem med offentlig nyckel baserade på dessa tre klassiska svåra problem bli extremt sårbara [1] . Denna typ av offentlig nyckelkryptering används idag för att skydda webbplatser , datorbehörighetsinformation och för att förhindra att datorer tar emot skadlig programvara [5] .

Kryptografi som inte kan brytas av en kvantdator kallas kvantsäker eller postkvantkryptografi . En klass av dessa algoritmer är baserad på konceptet " inlärning med fel " introducerat av Oded Regevår 2005 [6] . En specialiserad form av felinlärning verkar i en polynomring över ett ändligt fält . Denna specialiserade form kallas Errored Learning Ring eller RLWE [7] .

Det finns många kryptografiska algoritmer som använder RLWE-paradigmet. Det finns publika nyckelkryptosystem , homomorfa krypteringsalgoritmer och RLWE digitalt signerade algoritmer utöver den publika nyckeln. Nyckelutbyte är en typ av asymmetrisk kryptering som upprättar en delad hemlig nyckel mellan två interagerande agenter på en kommunikationslänk. Ett klassiskt exempel på ett nyckelutbyte är Diffie-Hellman-protokollet (och, som dess förlängning, Elliptic Curve Diffie-Hellman-protokollet ). Växeln består av en överföring från ena änden av linjen och en överföring från den andra änden av linjen [8] .

RLWE-nyckelutbyte är designad som en kvantsäker ersättning för protokoll som används för att säkert generera hemliga nycklar över opålitliga kommunikationskanaler. Liksom Diffie-Hellman-protokollet tillhandahåller RLWE den kryptografiska egenskapen " perfekt framåtsekretess " [9] , som syftar till att minska effektiviteten av massövervakningsprogram och att se till att det inte finns några långsiktiga hemliga nycklar som kan äventyras, vilket möjliggör bulkdekryptering.

Beskrivning av algoritmen

Inledning

Med hjälp av ett primtal q, arbetar RLWE i ringen av polynom modulo polynomet Ф(х) med koefficienter i fältet för heltal modulo q (ring F q [x]/Φ(x)) [10] [8] . Polynomet a(x) uttrycks enligt följande:

Koefficienterna för detta polynom är heltal modulo q . Polynom Φ(x) = x n +1 , där n är en potens av 2 (i de flesta fall värden för n = 256, 512 eller 1024).

RLWE-KEX använder polynom som anses vara "små" med avseende på ett mått som kallas den "oändliga" normen [11] . Den oändliga normen för ett polynom är värdet på den största polynomkoefficienten när koefficienterna betraktas som element i mängden { ,..., 0, …, }. För att säkerställa algoritmens säkerhet är det nödvändigt att generera slumpmässiga polynom s(x) som är små med avseende på den oändliga normen. Detta görs genom att slumpmässigt generera koefficienter för polynomet ( s n-1 , …, s 0 ), som garanteras eller med stor sannolikhet är små. Det finns två vanliga sätt:

1. Använda en diskret enhetlig fördelning  - koefficienter för ett litet enhetligt provpolynom från en uppsättning små koefficienter. Låt b vara ett heltal mycket mindre än q. Vid slumpmässigt val av koefficienter från mängden { -b, -b+1, -b+2. … −2, −1, 0, 1, 2, … , b-2, b-1, b }, kommer polynomet att vara litet med avseende på a(x) . Sing föreslår att du använder b = 5 [12] . Således kommer koefficienterna att väljas från mängden { q-5, q-4, q-3, q-2, q-1, 0, 1, 2, 3, 4, 5 }.
2. Med användning av en diskret normalfördelning  - koefficienterna väljs slumpmässigt för ett udda värde på q med hjälp av ett urval från mängden { ; } enligt den diskreta Gaussfördelningen med medelvärde 0 och varians σ . Denna metod är mer komplicerad än den diskreta enhetliga fördelningen, men den låter dig bevisa algoritmens säkerhet [13] .

Låt slumpmässiga små polynom följa fördelningen, betecknade som D . Talet q kommer att vara udda primtal så att q ≡ 1 mod 4 och
q ≡ 1 mod 2n för att minimera antalet slumpmässiga bitvalsoperationer på den inställda gränsen [14] . Detta gör att du kan implementera algoritmen mest effektivt [15] . Graden av polynomet Ф(x) är graden 2 [16] .

Låt ett fast polynom a(x)  vara gemensamt för alla nätverksanvändare, genererat med hjälp av en kryptografiskt säker pseudoslumptalsgenerator . Med a(x) väljs små polynom s(x) och e(x) slumpmässigt , s(x)  är den privata nyckeln i den publika nyckelutbytet. Motsvarande publika nyckel kommer att vara polynomet t(x) = a(x)s(x) + e(x) [11] . Nyckelutbytessäkerhet baseras på svårigheten att hitta ett par små polynom s'(x) och e'(x) så att för en given t(x) a(x)s'(x) + e'(x) = t(x) .

Nyckelutbyte

Nyckelutbytet sker mellan nyckelutbytesagenterna Alice , märkt A , och Bob , märkt B. Både A och B känner till q , n , a(x) och kan generera små polynom enligt fördelningen D [10] [17] .

Alices första handlingar [17] :

1. Generering av två små polynom s A (x) och e A (x) genom sampling från fördelningen D .
2. Beräkning t A (x) = a(x)•s A (x) + e A (x) .
3. Skickar t A (x) till Bob.

Bobs handlingar [17] :

1. Generering av två små polynom s B (x) och e B (x) genom sampling från fördelningen D .
2. Beräkning v(x) = t A (x) s B (x) + e B (x) . Observera att v(x) = a(x)s A (x)s B (x) + e A (x)s B (x) + e B (x) och att e B (x) + e A ( x ) )s B (x) kommer också att vara liten, eftersom e B (x) valdes liten, är koefficienterna e A (x)s B (x) begränsade i tillväxt och kommer också att vara små.
3. Koefficientfördelningen v(x) jämnas ut genom att loopa igenom koefficienterna och slumpmässigt justera vissa värden. Från j=0 till n-1 :
   1. Om v j = 0 , kom med en slumpmässig bit (betecknad med b ). Om det är 0 så är v j = 0 , annars är v j = q-1 .
   2. Om v j = , kom med en slumpmässig bit( b ). Om det är 0 så är v j = annars v j = .
4. Bildning av 2 -bitarsströmmar cj och uj med längden n från koefficienterna v(x) med hjälp av följande transformationer. Från j=0 till n-1 :
   1. Skriv c j som den minst signifikanta biten av heltalsdelen 4v j /q , dvs.
   2. Skriv .
5. Bildar nyckeln k som en sammanlänkning av u n-1 , …, u 0 .
6. Bildning av en "match"-sträng ( C ) med längden n , som en sammanlänkning av cn -1 , …, c0 .
7. Beräkning t B (x) = a(x) s B (x) + e B (x) .
8. Skickar t B (x) och C till Alice.

Alices nästa steg [17] :

1. Få t B (x) och C från Bob.
2. Beräkning 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. Bildandet av en bitström u j med längden n är som följer:
   1. Om c j = 0 och ≤ w j < så är u j = 0 , annars är u j = 1 .
   2. Om c j = 1 och ≤ w j < så är u j = 0 , annars är u j = 1 .
4. Bildar nyckeln k som en sammanlänkning av u n-1 , …, u 0 .

Om nyckelutbytet fungerar korrekt kommer strängarna u n-1 , …, u 0 för Alice och Bob att matcha [18] . Beroende på detaljerna för de valda parametrarna n , q , σ och b , finns det en möjlighet att t A (x) och t B (x) kommer att matcha. Parametrarna för nyckelutbytet måste väljas så att sannolikheten för detta nyckelutbytesfel är mycket låg - mycket mindre än sannolikheten för oupptäckbar korruption eller enhetsfel.

Val av alternativ

Utbytet fungerar i ringen av polynom av grad inte mer än n-1 modulo polynomet Φ(х) . Det antas att n  är potensen 2 och q  är primtal, q ≡ 1 mod 4 . Baserat på Peikerts arbete föreslog Sing två uppsättningar parametrar för RWLE-KEX [19] .

För 128 -bitars säkerhet: n = 512 , q = 25601 och Φ(x) = x 512 + 1

För 256 -bitars säkerhet: n = 1024 , q = 40961 och Φ(x) = x 1024 + 1

Eftersom nyckelutbytet använder slumpmässigt begränsat urval, finns det en chans att samma nycklar kommer att genereras för Alice och Bob . Antag att en Gaussisk parameter är σ = eller enhetlig sampling används med b = 5 , då är sannolikheten för matchningsfel för publik nyckel mindre än 2 −71 och 2 −75 för 128 bitars parametrar och mindre än 2 −91 och 2 −97 för 256 bitparametrar, respektive [19] .

Alkim, Duka, Popplemann och Schwabe (november 2015) rekommenderar följande parametrar: n = 1024 , q = 12289 och Φ(x) = x 1024 + 1 eftersom de säkerställer effektiviteten och säkerheten för algoritmen. I fallet med 256 -bitars säkerhet ger denna uppsättning en matchningsfelsannolikhet på 2 −110 [20] .

Algoritmens tillförlitlighet

Beräkningskomplexiteten för att bryta RLWE-KEX är av samma ordning som att lösa det kortaste vektorproblemet (SVP) i ett idealiskt gitter [21] . Det bästa sättet att utvärdera den praktiska säkerheten för en given uppsättning gitterparametrar är BKZ 2.0-reduktionsalgoritmen .  (obestämd). I enlighet med BKZ 2.0-algoritmen kommer huvudväxlingsparametrarna ovan att ge mer än 128 respektive 256 bitars säkerhet [22] .

Implementeringsexempel

2014 gjorde Douglas Stebila en patch för OpenSSL 1.0.1f. baserat på arbetet publicerat i boken "Post-quantum key exchange for the TLS protocol from the ring learning with errors problem" . Syngas arbetsmjukvara finns på GitHub . (obestämd)[23] .

En annan tillämpning av algoritmen är arbetet av Zhang, Ding, Snook och Dagdelen "Post Quantum Authenticated Key Exchange from Ideal Lattices" .  (obestämd). Konceptet att skapa en Diffie-Hellman-algoritm introducerades först av de franska forskarna Aguilar, Gaborite, Lacharme, Schreck och Zemor vid PQCrypto 2010 i deras rapport "Noisy Diffie-Hellman Protocols" (ej tillgänglig länk) . Datum för åtkomst: 1 december 2015. Arkiverad från originalet den 24 september 2015. (obestämd)  . Detta ämne utökades sedan och markerade början på Peukerts mer rigorösa studier i hans arbete .  (obestämd)[24] .

Se även

• Postkvantkryptografi
• Kryptografi på galler
• Lärande med fel

Anteckningar

1. ↑ 1 2 Valiev, 2000 .
2. ↑ Lyubashevsky, Peikert, Regev, 2013 , s. 1-2.
3. ↑ En kvantdator behövdes för att bryta NSA-chiffer . Hämtad 27 november 2015. Arkiverad från originalet 8 december 2015. (obestämd)
4. ↑ Att skapa en kvantdator blir en ingenjörsutmaning . Tillträdesdatum: 5 december 2015. Arkiverad från originalet 7 november 2015. (obestämd)
5. ↑ Kryptosystem för offentlig nyckel . Hämtad 27 november 2015. Arkiverad från originalet 8 december 2015. (obestämd)
6. ↑ Regev, Oded. Om gitter, lärande med fel, slumpmässiga linjära koder och kryptografi  //  Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing: tidskrift. - New York, NY, USA: ACM, 2005. - Vol. 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. ett.
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. åtta.
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.

Litteratur

• Peikert C. Lattice Cryptography for the Internet  // Post-Quantum Cryptography : 6th International Workshop, PQCrypto 2014, Waterloo, ON, Kanada, 1-3 oktober 2014. Proceedings / M. Mosca - Berlin , Heidelberg , New York, NY , London [etc.] : Springer International Publishing , 2014. - S. 197-219. - ( Lecture Notes in Computer Science ; Vol. 8772) - ISBN 978-3-319-11658-7 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-319-11659-4_12
• Singh, Vikram. A Practical Key Exchange for Internet using Lattice Cryptography  31. International Association for Cryptologic Research (2015) .
• Lyubashevsky, Vadim; Peikert, Chris; Regev, Chris. A Toolkit for Ring-LWE Cryptography  (engelska)  // Advances in Cryptology - EUROCRYPT 2013: samling. - 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, Leo; Poppelman, Thomas; Schwabe, Peter. Post-quantum key exchange - a new hope  (engelska) 32. International Association for Cryptologic Research (2015).
• Joppe W. Bos; Craig Costello; Michael Naehrig; Douglas Stebila. Post-kvantnyckelutbyte för TLS-protokollet från Ring Learning with Errors Problem  (engelska)  // Security and Privacy (SP): insamling. - 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. Säker cloud computing med homomorfisk kryptografi  // Security of Information Technologies: journal. - 2013. - Januari ( nr 1 ). - S. 1-12 . — ISSN 2074-7128 . (ryska)
• Valiev K.A. Kvantinformatik: datorer, kommunikation och kryptografi  // Bulletin of the Russian Academy of Sciences: tidskrift. - 2000. - Augusti ( vol. 70 , nr 8 ). - S. 688-695 . — ISSN 0869-5873 . (ryska)
• Peikert, Chris. En effektiv och parallell Gaussisk Sampler for Lattices  (engelska)  // Advances in Cryptology - CRYPTO 2010: samling. - 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 .