Criptografia bazată pe rețele

Criptografia bazată pe rețele este termenul generic pentru construcțiile primitivelor criptografice care implică rețele, fie în construcția în sine, fie în demonstrația de securitate. Construcțiile bazate pe rețele susțin standarde importante ale criptografiei post-cuantice.[1] Spre deosebire de schemele de cheie publică mai utilizate și mai cunoscute, cum ar fi criptosistemele RSA, Diffie-Hellman sau cele cu curbă eliptică – care ar putea fi, teoretic, învinse folosind algoritmul lui Shor pe un computer cuantic – unele construcții bazate pe rețele par a fi rezistente la atacuri atât din partea computerelor clasice, cât și a celor cuantice. În plus, multe construcții bazate pe rețele sunt considerate sigure sub presupunerea că anumite probleme de rețea computațională bine studiate nu pot fi rezolvate eficient.

În 2024, NIST a anunțat Standardul de Semnătură Digitală Bazat pe Module și Rețele pentru criptografia post-cuantică.[2]

Istoric

În 1996, Miklós Ajtai a introdus prima construcție criptografică bazată pe rețele a cărei securitate se putea baza pe duritatea problemelor de rețele bine studiate,[3] iar Cynthia Dwork a arătat că o anumită problemă de rețele în caz mediu, cunoscută sub numele de soluții întregi scurte (SIS), este cel puțin la fel de greu de rezolvat ca o problemă de rețele în cel mai rău caz.[4] Apoi, ea a arătat o funcție hash criptografică a cărei securitate este echivalentă cu duritatea computațională a SIS.

În 1998, Jeffrey Hoffstein, Jill Pipher și Joseph H. Silverman au introdus o schemă de criptare cu cheie publică bazată pe rețele, cunoscută sub numele de NTRU.[5] Cu toate acestea, schema lor nu este cunoscută ca fiind cel puțin la fel de dificilă ca rezolvarea unei probleme de rețele în cel mai rău caz.

Prima schemă de criptare cu cheie publică bazată pe rețele a cărei securitate a fost dovedită sub ipotezele de duritate în cel mai rău caz a fost introdusă de Oded Regev în 2005,[6] împreună cu problema învățării cu erori (LWE). De atunci, multe lucrări ulterioare s-au concentrat pe îmbunătățirea demonstrației de securitate a lui Regev[7][8] și pe îmbunătățirea eficienței schemei originale.[9][10][11][12] Mult mai multă muncă a fost dedicată construirii de primitive criptografice suplimentare bazate pe LWE și probleme conexe. De exemplu, în 2009, Craig Gentry a introdus prima schemă de criptare complet omomorfă, care se baza pe o problemă de rețea.[13]

Context matematic

În algebra liniară, o rețea L⊂ Rⁿ este mulțimea tuturor combinațiilor liniare întregi de vectori dintr-o bază {b₁, …, b_n} a lui Rⁿ. Cu alte cuvinte, L = {∑a_ib_i : a_i ∈ Z}. De exemplu, Zⁿ este o rețea, generată de baza standard pentru Rⁿ. Este esențial faptul că baza unei rețele nu este unică. De exemplu, vectorii (3, 1, 4), (1, 5, 9) și (2, −1, 0) formează o bază alternativă pentru Z³.

Cea mai importantă problemă de calcul bazată pe rețele este problema vectorului cel mai scurt (SVP sau uneori GapSVP), care solicită o lungime euclidiană minimă aproximativă a unui vector de rețea diferit de zero. Se consideră că această problemă este dificil de rezolvat eficient, chiar și cu factori de aproximare care sunt polinomiali în n și chiar cu un computer cuantic. Multe (deși nu toate) construcțiile criptografice bazate pe rețele sunt cunoscute ca fiind sigure dacă SVP este de fapt dificil în acest regim.

Referințe

1. CSRC, National Institute of Standards and Technology. Post-Quantum Cryptography. 2019. Available from the Internet on <https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/>, accessed in November 2nd, 2022.
2. „Module-Lattice-Based Digital Signature Standard” (PDF). NIST.gov. August 2024.
3. Ajtai, Miklós (1996). „Generating Hard Instances of Lattice Problems”. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. pp. 99–108. CiteSeerX 10.1.1.40.2489. doi:10.1145/237814.237838. ISBN 978-0-89791-785-8. S2CID 6864824.
4. Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence.
5. Hoffstein, Jeffrey; Pipher, Jill; Silverman, Joseph H. (1998). „NTRU: A ring-based public key cryptosystem”. Algorithmic Number Theory. Lecture Notes in Computer Science. Vol. 1423. pp. 267–288. CiteSeerX 10.1.1.25.8422. doi:10.1007/bfb0054868. ISBN 978-3-540-64657-0.
6. Regev, Oded (2005-01-01). „On lattices, learning with errors, random linear codes, and cryptography”. Proceedings of the thirty-seventh annual ACM symposium on Theory of computing – STOC ’05. ACM. pp. 84–93. CiteSeerX 10.1.1.110.4776. doi:10.1145/1060590.1060603. ISBN 978-1581139600. S2CID 53223958.
7. Peikert, Chris (2009-01-01). „Public-key cryptosystems from the worst-case shortest vector problem”. Proceedings of the 41st annual ACM symposium on Symposium on theory of computing – STOC ’09. ACM. pp. 333–342. CiteSeerX 10.1.1.168.270. doi:10.1145/1536414.1536461. ISBN 9781605585062. S2CID 1864880.
8. Brakerski, Zvika; Langlois, Adeline; Peikert, Chris; Regev, Oded; Stehlé, Damien (2013-01-01). „Classical hardness of learning with errors”. Proceedings of the 45th annual ACM symposium on Symposium on theory of computing – STOC ’13. ACM. pp. 575–584. arXiv:1306.0281. doi:10.1145/2488608.2488680. ISBN 9781450320290. S2CID 6005009.
9. Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010-05-30). „On Ideal Lattices and Learning with Errors over Rings”. Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science. Vol. 6110. pp. 1–23. CiteSeerX 10.1.1.352.8218. doi:10.1007/978-3-642-13190-5_1. ISBN 978-3-642-13189-9.
10. Peikert, Chris (2014-07-16). „Lattice cryptography for the Internet” (PDF). IACR. Retrieved 2017-01-11.
11. Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (2015-01-01). „Post-quantum key exchange – a new hope”. Cryptology ePrint Archive.
12. Bos, Joppe; Costello, Craig; Ducas, Léo; Mironov, Ilya; Naehrig, Michael; Nikolaenko, Valeria; Raghunathan, Ananth; Stebila, Douglas (2016-01-01). „Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE”. Cryptology ePrint Archive.
13. Gentry, Craig (2009-01-01). A Fully Homomorphic Encryption Scheme (Thesis). Stanford, CA, USA: Stanford University.

(Include texte traduse și adaptate din Wikipedia de Nicolae Sfetcu)