Læringsbaseret nøgleudveksling med fejl

I kryptografi er læring-med-fejl nøgleudveksling en kryptografisk algoritme, der gør det muligt for  to parter at oprette og udveksle en hemmelig nøgle, som de bruger til at kryptere beskeder mellem sig. RLWE-KEX ( Ring Learning with Errors Key Exchange ) er en af ​​de offentlige nøglealgoritmer , der er designet til at beskytte mod en modstander, der har en kvantecomputer . Dette er vigtigt, fordi de offentlige nøglekrypteringssystemer, der er almindeligt brugt i dag, let brydes af en kvantecomputer [1] . RLWE-KEX er en af ​​mange post-kvantekryptografiske algoritmer baseret på kompleksiteten af ​​at løse matematiske problemer relateret til kryptografi på gitter [2] .

Baggrund

Siden 1980'erne har sikkerheden ved kryptografisk nøgleudveksling og digitale signaturer på internettet primært været baseret på et lille antal større offentlige nøglekryptosystemer. Den kryptografiske styrke af disse algoritmer er baseret på et lille antal problemer, som er svære at beregne med klassiske metoder, men ganske let løses ved hjælp af en kvantecomputer [3] . Disse problemer er faktoriseringen af ​​to omhyggeligt udvalgte primtal , vanskeligheden ved at beregne den diskrete logaritme i et valgt endeligt felt, og vanskeligheden ved at beregne den diskrete logaritme i en valgt gruppe af punkter på en elliptisk kurve . Der er en opfattelse af, at kvantecomputere vil være tilgængelige om 10-15 år [4] . Hvis kvantecomputere med tilstrækkelig hukommelse blev bygget, ville alle offentlige nøglekryptosystemer baseret på disse tre klassiske hårde problemer blive ekstremt sårbare [1] . Denne type offentlig nøglekryptering bruges i dag til at beskytte internetsider , computerautorisationsoplysninger og for at forhindre computere i at modtage skadelig software [5] .

Kryptografi, der ikke kan brydes af en kvantecomputer, kaldes kvantesikker eller postkvantekryptografi . En klasse af disse algoritmer er baseret på konceptet " læring med fejl " introduceret af Oded Regevi 2005 [6] . En specialiseret form for fejlindlæring opererer i en polynomialring over et begrænset felt . Denne specialiserede formular kaldes Errored Learning Ring eller RLWE [7] .

Der er mange kryptografiske algoritmer , der fungerer ved hjælp af RLWE-paradigmet. Der er offentlige nøglekryptosystemer , homomorfe krypteringsalgoritmer og RLWE digitalt signerede algoritmer ud over den offentlige nøgle. Nøgleudveksling er en type asymmetrisk kryptering , der etablerer en delt hemmelig nøgle mellem to interagerende agenter på et kommunikationslink. Et klassisk eksempel på en nøgleudveksling er Diffie-Hellman-protokollen (og, som dens forlængelse, Elliptic Curve Diffie-Hellman-protokollen ). Centralen består af en transmission fra den ene ende af linjen og en transmission fra den anden ende af linjen [8] .

RLWE nøgleudveksling er designet som en kvantesikker erstatning for protokoller , der bruges til sikkert at generere hemmelige nøgler over ikke-pålidelige kommunikationskanaler. Ligesom Diffie-Hellman-protokollen giver RLWE den kryptografiske egenskab " perfekt fremad hemmeligholdelse " [9] , som har til formål at reducere effektiviteten af ​​masseovervågningsprogrammer og sikre, at der ikke er nogen langsigtede hemmelige nøgler, der kan kompromitteres, hvilket giver mulighed for massedekryptering.

Beskrivelse af algoritmen

Introduktion

Ved hjælp af et primtal q arbejder RLWE i ringen af ​​polynomier modulo polynomiet Ф(х) med koefficienter i feltet af heltal modulo q (ring F q [x]/Φ(x)) [10] [8] . Polynomiet a(x) udtrykkes som følger:

Koefficienterne for dette polynomium er heltal modulo q . Polynomium Φ(x) = x n +1 , hvor n er en potens af 2 (i de fleste tilfælde er værdier for n = 256, 512 eller 1024).

RLWE-KEX bruger polynomier, der betragtes som "små" med hensyn til et mål kaldet den "uendelige" norm [11] . Den uendelige norm for et polynomium er værdien af ​​den største polynomiekoefficient, når koefficienterne betragtes som elementer i mængden { ,..., 0, …, }. For at sikre algoritmens sikkerhed er det nødvendigt at generere tilfældige polynomier s(x) , der er små i forhold til den uendelige norm. Dette gøres ved tilfældigt at generere koefficienter for polynomiet ( s n-1 , …, s 0 ), som er garanteret eller med stor sandsynlighed for at være små. Der er to almindelige måder:

1. Brug af en diskret ensartet fordeling  - koefficienter for et lille ensartet prøvepolynomium fra et sæt små koefficienter. Lad b være et heltal meget mindre end q. Ved tilfældigt valg af koefficienter fra mængden { -b, -b+1, -b+2. … −2, −1, 0, 1, 2, … , b-2, b-1, b }, vil polynomiet være lille i forhold til a(x) . Syng foreslår at bruge b = 5 [12] . Således vil koefficienterne blive valgt fra mængden { q-5, q-4, q-3, q-2, q-1, 0, 1, 2, 3, 4, 5 }.
2. Ved hjælp af en diskret normalfordeling  - koefficienterne vælges tilfældigt for en ulige værdi af q ved hjælp af en stikprøve fra mængden { ; } ifølge den diskrete Gauss-fordeling med middelværdi 0 og varians σ . Denne metode er mere kompliceret end den diskrete ensartede fordeling, men den giver dig mulighed for at bevise sikkerheden af ​​algoritmen [13] .

Lad tilfældige små polynomier følge fordelingen, betegnet som D . Tallet q vil være et ulige primtal, således at q ≡ 1 mod 4 og
q ≡ 1 mod 2n for at minimere antallet af tilfældige bitudvælgelsesoperationer på den indstillede grænse [14] . Dette vil give dig mulighed for at implementere algoritmen mest effektivt [15] . Graden af ​​polynomiet Ф(x) er graden af ​​2 [16] .

Lad et fast polynomium a(x)  være fælles for alle netværksbrugere, genereret ved hjælp af en kryptografisk sikker pseudo-tilfældig talgenerator . Ved at tage a(x) vælges små polynomier s(x) og e(x) tilfældigt , idet s(x)  er den private nøgle i den offentlige nøgleudveksling. Den tilsvarende offentlige nøgle vil være polynomiet t(x) = a(x)s(x) + e(x) [11] . Nøgleudvekslingssikkerhed er baseret på vanskeligheden ved at finde et par små polynomier s'(x) og e'(x), således at for en given t(x) a(x)s'(x) + e'(x) = t(x) .

Nøgleudveksling

Nøgleudvekslingen finder sted mellem nøgleudvekslingsagenterne Alice , mærket A , og Bob , mærket B. Både A og B kender q , n , a(x) og kan generere små polynomier ifølge fordelingen D [10] [17] .

Alices indledende handlinger [17] :

1. Generering af to små polynomier s A (x) og e A (x) ved stikprøver fra fordelingen D .
2. Beregning t A (x) = a(x)•s A (x) + e A (x) .
3. Sender t A (x) til Bob.

Bobs handlinger [17] :

1. Generering af to små polynomier s B (x) og e B (x) ved sampling fra fordelingen D .
2. Beregning v(x) = t A (x) s B (x) + e B (x) . Bemærk at v(x) = a(x)s A (x)s B (x) + e A (x)s B (x) + e B (x) og at e B (x) + e A ( x )s B (x) vil også være lille, da e B (x) blev valgt lille, er koefficienterne e A (x)s B (x) begrænset i vækst og vil også være små.
3. Koefficientfordelingen v(x) udjævnes ved at sløjfe gennem koefficienterne og tilfældigt justere visse værdier. Fra j=0 til n-1 :
   1. Hvis v j = 0 , så kom med en tilfældig bit (betegnet med b ). Hvis det er 0 , så v j = 0 , ellers v j = q-1 .
   2. Hvis v j = , så kom med en tilfældig bit( b ). Hvis det er 0 , så er v j = ellers v j = .
4. Dannelse af 2 bitstrømme c j og u j af længden n ud fra koefficienterne v(x) ved hjælp af følgende transformationer. Fra j=0 til n-1 :
   1. Skriv c j som den mindst signifikante bit af heltalsdelen 4v j /q , dvs.
   2. Skriv .
5. Dannelse af nøglen k som en sammenkædning af u n-1 , …, u 0 .
6. Dannelse af en "match"-streng ( C ) af længden n , som en sammenkædning af cn -1 , …, c0 .
7. Beregning t B (x) = a(x) s B (x) + e B (x) .
8. Sender t B (x) og C til Alice.

Alices næste skridt [17] :

1. Får t B (x) og C fra Bob.
2. Beregning 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. Dannelsen af ​​en bitstrøm u j af længden n er som følger:
   1. Hvis c j = 0 og ≤ w j < så er u j = 0 , ellers er u j = 1 .
   2. Hvis c j = 1 og ≤ w j < så er u j = 0 , ellers er u j = 1 .
4. Dannelse af nøglen k som en sammenkædning af u n-1 , …, u 0 .

Hvis nøgleudvekslingen fungerer korrekt, vil strengene u n-1 , …, u 0 for Alice og Bob matche [18] . Afhængigt af de valgte parametres specifikationer n , q , σ og b , er der mulighed for , at t A (x) og t B (x) vil matche. Parametrene for nøgleudvekslingen skal vælges således, at sandsynligheden for denne nøgleudvekslingsfejl er meget lav - meget mindre end sandsynligheden for uopdagelig korruption eller enhedsfejl.

Valg af muligheder

Udvekslingen fungerer i ringen af ​​polynomier af grad ikke mere end n-1 modulo polynomiet Φ(х) . Det antages, at n  er en potens af 2 , og q  er primtal, q ≡ 1 mod 4 . Baseret på Peikerts arbejde foreslog Sing to sæt parametre for RWLE-KEX [19] .

For 128 -bit sikkerhed: n = 512 , q = 25601 og Φ(x) = x 512 + 1

For 256 -bit sikkerhed: n = 1024 , q = 40961 og Φ(x) = x 1024 + 1

Da nøgleudvekslingen bruger tilfældig begrænset sampling, er der en chance for, at de samme nøgler vil blive genereret for Alice og Bob . Antag, at en Gauss-parameter er σ = eller ensartet sampling bruges med b = 5 , så er sandsynligheden for offentlig nøglematchningsfejl mindre end 2 −71 og 2 −75 for 128 bit parametre og mindre end 2 −91 og 2 −97 for 256 bitparametre, henholdsvis [19] .

Alkim, Duka, Popplemann og Schwabe (november 2015) anbefaler følgende parametre: n = 1024 , q = 12289 og Φ(x) = x 1024 + 1 , da de sikrer effektiviteten og sikkerheden af ​​algoritmen. I tilfælde af 256 -bit sikkerhed giver dette sæt en matchfejlssandsynlighed på 2 -110 [20] .

Algoritmens pålidelighed

Den beregningsmæssige kompleksitet ved at bryde RLWE-KEX er af samme størrelsesorden som at løse det korteste vektorproblem (SVP) i et ideelt gitter [21] . Den bedste måde at evaluere den praktiske sikkerhed af et givet sæt gitterparametre på er BKZ 2.0-reduktionsalgoritmen .  (ubestemt). I overensstemmelse med BKZ 2.0-algoritmen vil de vigtigste udvekslingsparametre angivet ovenfor give mere end henholdsvis 128 og 256 bits sikkerhed [22] .

Implementeringseksempler

I 2014 lavede Douglas Stebila en patch til OpenSSL 1.0.1f. baseret på arbejdet udgivet i bogen "Post-quantum key exchange for the TLS protocol from the ring learning with errors problem" . Syngas arbejdssoftware er på GitHub . (ubestemt)[23] .

En anden anvendelse af algoritmen er arbejdet fra Zhang, Ding, Snook og Dagdelen "Post Quantum Authenticated Key Exchange from Ideal Lattices" .  (ubestemt). Konceptet med at skabe en Diffie-Hellman-algoritme blev først introduceret af de franske forskere Aguilar, Gaborite, Lacharme, Schreck og Zemor ved PQCrypto 2010 i deres rapport "Noisy Diffie-Hellman Protocols" (utilgængeligt link) . Dato for adgang: 1. december 2015. Arkiveret fra originalen 24. september 2015. (ubestemt)  . Dette emne blev derefter udvidet og markerede begyndelsen på Peukerts mere stringente studier i hans arbejde .  (ubestemt)[24] .

Se også

• Postkvantekryptografi
• Kryptografi på gitter
• Læring med fejl

Noter

1. ↑ 1 2 Valiev, 2000 .
2. ↑ Lyubashevsky, Peikert, Regev, 2013 , s. 1-2.
3. ↑ En kvantecomputer var nødvendig for at bryde NSA-cifre . Hentet 27. november 2015. Arkiveret fra originalen 8. december 2015. (ubestemt)
4. ↑ At skabe en kvantecomputer bliver en teknisk udfordring . Dato for adgang: 5. december 2015. Arkiveret fra originalen 7. november 2015. (ubestemt)
5. ↑ Offentlig nøgle kryptosystemer . Hentet 27. november 2015. Arkiveret fra originalen 8. december 2015. (ubestemt)
6. ↑ Regev, Oded. Om gitter, læring med fejl, tilfældige lineære koder og kryptografi  //  Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing: tidsskrift. - 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. en.
10. ↑ 1 2 Peikert, 2014 , pp. 200-201.
11. ↑ 12 Singh , 2015 , s. 1-2.
12. ↑ Singh, 2015 , s. 7.
13. ↑ Peikert, 2010 , pp. 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. otte.
19. ↑ 12 Singh , 2015 , s. 21-24.
20. ↑ Alkim et al, 2015 , s. 6:15-16.
21. ↑ Peikert, 2014 , pp. 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, Canada, 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 the Internet using Lattice Cryptography  31. International Association for Cryptologic Research (2015) .
• Lyubashevsky, Vadim; Peikert, Chris; Regev, Chris. A Toolkit for Ring-LWE Cryptography  (engelsk)  // 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-kvante nøgleudveksling - et nyt håb  (engelsk) 32. International Association for Cryptologic Research (2015).
• Joppe W. Bos; Craig Costello; Michael Naehrig; Douglas Stebila. Post-kvante nøgleudveksling for TLS-protokollen fra Ring Learning with Errors Problem  (engelsk)  // Security and Privacy (SP): samling. - IEEE, 2015. - S. 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. Sikker cloud computing ved hjælp af homomorfisk kryptografi  // Security of Information Technologies: journal. - 2013. - Januar ( nr. 1 ). - S. 1-12 . — ISSN 2074-7128 . (Russisk)
• Valiev K.A. Kvanteinformatik: computere, kommunikation og kryptografi  // Bulletin of the Russian Academy of Sciences: tidsskrift. - 2000. - August ( bind 70 , nr. 8 ). - S. 688-695 . — ISSN 0869-5873 . (Russisk)
• Peikert, Chris. An Efficient and Parallel Gaussian Sampler for Lattices  (engelsk)  // 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 .