Schimb de chei bazat pe învățare cu erori

În criptografie , schimbul de chei de învățare cu eroare  este un algoritm criptografic care permite două părți să creeze și să schimbe o cheie secretă, pe care o folosesc pentru a cripta mesajele între ele. RLWE-KEX ( Ring  Learning with Errors Key Exchange ) este unul dintre algoritmii de cheie publică care este conceput pentru a proteja împotriva unui adversar care are un computer cuantic . Acest lucru este important pentru că sistemele criptografice cu cheie publică de uz curent astăzi sunt ușor sparte de un computer cuantic [1] . RLWE-KEX este unul dintre multealgoritmi criptografici post-cuantici bazati pe complexitatea rezolvarii problemelor matematice legate de criptografia pe retele [2] .

Fundal

Începând cu anii 1980, securitatea schimbului de chei criptografice și a semnăturilor digitale pe Internet s-a bazat în primul rând pe un număr mic de criptosisteme majore cu chei publice. Puterea criptografică a acestor algoritmi se bazează pe un număr mic de probleme greu de calculat prin metode clasice, dar destul de ușor de rezolvat folosind un computer cuantic [3] . Aceste probleme sunt factorizarea a două numere prime alese cu grijă , dificultatea de a calcula logaritmul discret într-un câmp finit ales și dificultatea de a calcula logaritmul discret într-un grup ales de puncte pe o curbă eliptică . Există o opinie că calculatoarele cuantice vor fi disponibile în 10-15 ani [4] . Dacă s-ar construi calculatoare cuantice cu memorie suficientă, toate criptosistemele cu cheie publică bazate pe aceste trei probleme clasice ar deveni extrem de vulnerabile [1] . Acest tip de criptografie cu cheie publică este folosit astăzi pentru a proteja site-urile Internet , informațiile de autorizare a computerelor și pentru a preveni calculatoarele să primească software rău intenționat [5] .

Criptografia care nu poate fi spartă de un computer cuantic se numește criptografie cuantică sigură sau post-cuantică . O clasă a acestor algoritmi se bazează pe conceptul de „ învățare cu erori ” introdus de Oded Regevîn 2005 [6] . O formă specializată de învățare a erorilor operează într-un inel polinomial peste un câmp finit . Această formă specializată se numește Errored Learning Ring sau RLWE [7] .

Există mulți algoritmi criptografici care funcționează folosind paradigma RLWE. Există criptosisteme cu cheie publică , algoritmi de criptare homomorfă și algoritmi RLWE semnați digital în plus față de cheia publică. Schimbul de chei este un tip de criptare asimetrică care stabilește o cheie secretă partajată între doi agenți care interacționează pe o legătură de comunicație. Un exemplu clasic de schimb de chei este protocolul Diffie-Hellman (și, ca extensie, protocolul Elliptic Curve Diffie-Hellman ). Centrala constă dintr-o transmisie de la un capăt al liniei și o transmisie de la celălalt capăt al liniei [8] .

Schimbul de chei RLWE este conceput ca un înlocuitor cuantic sigur pentru protocoalele care sunt utilizate pentru a genera în siguranță chei secrete pe canale de comunicare neîncrezătoare. La fel ca protocolul Diffie-Hellman, RLWE oferă proprietatea criptografică de „secreție perfectă de transmitere ” [9] , care urmărește să reducă eficacitatea programelor de supraveghere în masă și să se asigure că nu există chei secrete pe termen lung care să poată fi compromise, permițând decriptarea în bloc.

Descrierea algoritmului

Introducere

Folosind un număr prim q, RLWE lucrează în inelul de polinoame modulo polinomul Ф(х) cu coeficienți în câmpul numerelor întregi modulo q (inelul F q [x]/Φ(x)) [10] [8] . Polinomul a(x) se exprimă după cum urmează:

Coeficienții acestui polinom sunt numere întregi modulo q . Polinomul Φ(x) = x n +1 , unde n este o putere a lui 2 (în cele mai multe cazuri, valori pentru n = 256, 512 sau 1024).

RLWE-KEX utilizează polinoame care sunt considerate „mici” în raport cu o măsură numită norma „infinită” [11] . Norma infinită pentru un polinom este valoarea celui mai mare coeficient polinom atunci când coeficienții sunt considerați elemente ale mulțimii { ,…, 0, …, }. Pentru a asigura securitatea algoritmului, este necesar să se genereze polinoame aleatoare s(x) care sunt mici în raport cu norma infinită. Acest lucru se realizează prin generarea aleatorie a coeficienților pentru polinom ( s n-1 , …, s 0 ), care sunt garantați sau cu o mare probabilitate să fie mici. Există două moduri comune:

1. Utilizarea unei distribuții uniforme discrete  - Coeficienții unui polinom de eșantion uniform mic dintr-un set de coeficienți mici. Fie b un număr întreg mult mai mic decât q. La alegerea aleatorie a coeficienților din mulțimea { -b, -b+1, -b+2. … −2, −1, 0, 1, 2, … , b-2, b-1, b }, polinomul va fi mic în raport cu a (x) . Sing sugerează utilizarea b = 5 [12] . Astfel, coeficienții vor fi aleși din mulțimea { q-5, q-4, q-3, q-2, q-1, 0 , 1, 2, 3, 4, 5 }.
2. Folosind o distribuție normală discretă  - coeficienții sunt aleși aleatoriu pentru o valoare impară a lui q folosind un eșantion din mulțimea { ; } conform distribuţiei discrete gaussiene cu medie 0 şi varianţă σ . Această metodă este mai complicată decât distribuția uniformă discretă, dar vă permite să demonstrați siguranța algoritmului [13] .

Fie polinoame mici aleatoare să urmeze distribuția, notate cu D . Numărul q va fi prim impar astfel încât q ≡ 1 mod 4 și
q ≡ 1 mod 2n pentru a minimiza numărul de operații aleatorii de selecție a biților pe granița setată [14] . Acest lucru vă va permite să implementați algoritmul cel mai eficient [15] . Gradul polinomului Ф(x) este gradul lui 2 [16] .

Fie un polinom fix a(x)  să fie comun tuturor utilizatorilor de rețea, generat folosind un generator de numere pseudoaleatoare securizat criptografic . Luând a(x) , polinoamele mici s(x) și e(x) sunt alese aleatoriu , s(x)  fiind cheia privată în schimbul de chei publice. Cheia publică corespunzătoare va fi polinomul t(x) = a(x)s(x) + e(x) [11] . Securitatea schimbului de chei se bazează pe dificultatea de a găsi o pereche de polinoame mici s'(x) și e'(x) astfel încât pentru un t(x) dat a(x)s'(x) + e'(x) = t(x) .

Schimb de chei

Schimbul de chei are loc între agenții de schimb de chei Alice , etichetat A și Bob , etichetat B. Atât A cât și B cunosc q , n , a(x) și pot genera polinoame mici conform distribuției D [10] [17] .

Acțiunile inițiale ale lui Alice [17] :

1. Generarea a două polinoame mici s A (x) și e A (x) prin eșantionare din distribuția D .
2. Calcul t A (x) = a(x)•s A (x) + e A (x) .
3. Trimiterea t A (x) lui Bob.

Acțiunile lui Bob [17] :

1. Generarea a două polinoame mici s B (x) și e B (x) prin eșantionare din distribuția D .
2. Calcul v(x) = t A (x) s B (x) + e B (x) . Rețineți că v(x) = a(x)s A (x)s B (x) + e A (x)s B (x) + e B (x) și că e B (x) + e A ( x )s B (x) va fi de asemenea mic, deoarece e B (x) a fost ales mic, coeficienții e A (x)s B (x) sunt limitați în creștere și vor fi, de asemenea, mici.
3. Distribuția coeficienților v(x) este netezită prin trecerea în buclă a coeficienților și ajustarea aleatorie a anumitor valori. De la j=0 la n-1 :
   1. Dacă v j = 0 , atunci găsiți un bit aleatoriu (notat cu b ). Dacă este 0 , atunci v j = 0 , în caz contrar v j = q-1 .
   2. Dacă v j = , atunci găsiți un bit aleatoriu ( b ). Dacă este 0 atunci v j = în caz contrar v j = .
4. Formarea fluxurilor de 2 biți c j și u j de lungime n din coeficienții v(x) folosind următoarele transformări. De la j=0 la n-1 :
   1. Scrieți c j ca bitul cel mai puțin semnificativ al părții întregi 4v j /q , adică .
   2. Scrie .
5. Formând cheia k ca o concatenare a u n-1 , …, u 0 .
6. Formarea unui șir de „potrivire” ( C ) de lungime n , ca o concatenare a lui c n-1 , …, c 0 .
7. Calcul t B (x) = a(x) s B (x) + e B (x) .
8. Trimitând t B (x) și C către Alice.

Următorii pași ai lui Alice [17] :

1. Obținerea t B (x) și C de la Bob.
2. Calcul 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. Formarea unui flux de biți u j de lungime n este următoarea:
   1. Dacă c j = 0 și ≤ w j < atunci u j = 0 , în caz contrar u j = 1 .
   2. Dacă c j = 1 și ≤ w j < atunci u j = 0 , în caz contrar u j = 1 .
4. Formând cheia k ca o concatenare a u n-1 , …, u 0 .

Dacă schimbul de chei funcționează corect, atunci șirurile u n-1 , …, u 0 pentru Alice și Bob se vor potrivi [18] . În funcție de specificul parametrilor aleși n , q , σ și b , există posibilitatea ca t A (x) și t B (x) să se potrivească. Parametrii pentru schimbul de chei trebuie aleși astfel încât probabilitatea acestei erori de schimb de chei să fie foarte mică – mult mai mică decât probabilitatea unei corupții nedetectabile sau a unei defecțiuni a dispozitivului.

Alegerea opțiunilor

Schimbul funcționează în inelul de polinoame de grad nu mai mult de n-1 modulo polinomul Φ(х) . Se presupune că n  este o putere a lui 2 și q  este prim, q ≡ 1 mod 4 . Pe baza lucrării lui Peikert, Sing a propus două seturi de parametri pentru RWLE-KEX [19] .

Pentru securitate pe 128 de biți: n = 512 , q = 25601 și Φ(x) = x 512 + 1

Pentru securitate pe 256 de biți: n = 1024 , q = 40961 și Φ(x) = x 1024 + 1

Deoarece schimbul de chei folosește eșantionare limitată aleatorie, există șansa ca aceleași chei să fie generate pentru Alice și Bob . Să presupunem că un parametru gaussian este σ = sau eșantionarea uniformă este utilizată cu b = 5 , atunci probabilitatea de eroare de potrivire a cheii publice este mai mică de 2 -71 și 2 -75 pentru parametrii pe 128 de biți și mai mică de 2 -91 și 2 -97 pentru 256 parametri de biți, respectiv [19] .

Alkim, Duka, Popplemann și Schwabe (noiembrie 2015) recomandă următorii parametri: n = 1024 , q = 12289 și Φ(x) = x 1024 + 1 deoarece asigură eficiența și siguranța algoritmului. În cazul securității pe 256 de biți, acest set oferă o probabilitate de eroare de potrivire de 2 −110 [20] .

Fiabilitatea algoritmului

Complexitatea de calcul a ruperii RLWE-KEX este de aceeași ordine cu rezolvarea celei mai scurte probleme vectoriale (SVP) într-o rețea ideală [21] . Cea mai bună modalitate de a evalua siguranța practică a unui anumit set de parametri de rețea este algoritmul de reducere BKZ 2.0 .  (nedefinit). În conformitate cu algoritmul BKZ 2.0, principalii parametri de schimb enumerați mai sus vor oferi mai mult de 128, respectiv 256 de biți de securitate [22] .

Exemple de implementare

În 2014, Douglas Stebila a făcut un patch pentru OpenSSL 1.0.1f. pe baza lucrării publicate în cartea „Schimb de chei post-cuantice pentru protocolul TLS din problema de învățare în inel cu erori” . Software-ul de lucru Synga este pe GitHub . (nedefinit)[23] .

O altă aplicație a algoritmului este munca lui Zhang, Ding, Snook și Dagdelen „Post Quantum Authenticated Key Exchange from Ideal Lattices” .  (nedefinit). Conceptul de creare a unui algoritm Diffie-Hellman a fost introdus pentru prima dată de cercetătorii francezi Aguilar, Gaborite, Lacharme, Schreck și Zemor la PQCrypto 2010 în raportul lor „Noisy Diffie-Hellman Protocols” (link indisponibil) . Data accesului: 1 decembrie 2015. Arhivat din original pe 24 septembrie 2015. (nedefinit)  . Acest subiect a fost apoi extins și a marcat începutul studiilor mai riguroase ale lui Peukert în lucrarea sa .  (nedefinit)[24] .

Vezi și

• Criptografia post-cuantică
• Criptografia pe zăbrele
• Învățarea cu erori

Note

1. ↑ 1 2 Valiev, 2000 .
2. ↑ Lyubashevsky, Peikert, Regev, 2013 , pp. 1-2.
3. ↑ A fost nevoie de un computer cuantic pentru a sparge cifrurile NSA . Consultat la 27 noiembrie 2015. Arhivat din original la 8 decembrie 2015. (nedefinit)
4. ↑ Crearea unui computer cuantic devine o provocare inginerească . Data accesului: 5 decembrie 2015. Arhivat din original pe 7 noiembrie 2015. (nedefinit)
5. ↑ Criptosisteme cu chei publice . Consultat la 27 noiembrie 2015. Arhivat din original la 8 decembrie 2015. (nedefinit)
6. ↑ Regev, Oded. Despre zăbrele, învățare cu erori, coduri liniare aleatorii și criptografie  //  Proceedings of the Thirty-77th Annual ACM Symposium on Theory of Computing : jurnal. - New York, NY, SUA: ACM, 2005. - Vol. STOC'05 . - P. 84-93 . — ISBN 1-58113-960-8 . - doi : 10.1145/1060590.1060603 .
7. ↑ Lyubashevsky, Peikert, Regev, 2013 , pp. 35-37.
8. ↑ 12 Singh , 2015 , pp. 2.
9. ↑ Singh, 2015 , pp. unu.
10. ↑ 1 2 Peikert, 2014 , pp. 200-201.
11. ↑ 12 Singh , 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. opt.
19. ↑ 12 Singh , 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.

Literatură

• Peikert C. Lattice Cryptography for the Internet  // Post-Quantum Cryptography : 6th International Workshop, PQCrypto 2014, Waterloo, ON, Canada, 1-3 octombrie 2014. Proceedings / M. Mosca - Berlin , Heidelberg , New York, NY , Londra [etc.] : Springer International Publishing , 2014. - P. 197-219. - ( Note de curs în Informatică ; 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. Asociația Internațională pentru Cercetare Cryptologică (2015) .
• Lyubashevsky, Vadim; Peikert, Chris; Regev, Chris. A Toolkit for Ring-LWE Cryptography  (engleză)  // Advances in Cryptology - EUROCRYPT 2013: colecție. - 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, Leu; Poppelman, Thomas; Schwabe, Peter. Schimb de chei post-cuantice - o nouă speranță  (engleză) 32. Asociația Internațională pentru Cercetare Cryptologică (2015).
• Joppe W. Bos; Craig Costello; Michael Naehrig; Douglas Stebila. Schimb de chei post-cuantice pentru protocolul TLS din Ring Learning with Errors Problem  (engleză)  // Security and Privacy (SP): colecție. - 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 folosind criptografia homomorfă  // Security of Information Technologies : journal. - 2013. - ianuarie ( Nr. 1 ). - S. 1-12 . — ISSN 2074-7128 . (Rusă)
• Valiev K.A. Informatică cuantică: calculatoare, comunicații și criptografie  // Buletinul Academiei Ruse de Științe: jurnal. - 2000. - august ( vol. 70 , nr. 8 ). - S. 688-695 . — ISSN 0869-5873 . (Rusă)
• Peikert, Chris. An Efficient and Parallel Gaussian Sampler for Lattices  (engleză)  // Advances in Cryptology - CRYPTO 2010: collection. - 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 .