Testarea trimiterilor PQC NIST runda 3

Sunt nou în acest domeniu și am câteva preocupări în ceea ce privește PQC;

Cum face NIST o comparație conform căreia un anumit algoritm este eficient și securitatea sa nu poate fi spartă de viitoarele atacuri cuantice? Sunt entuziasmat să înțeleg criteriile.

NIST încercase să spargă algoritmul de criptare aplicând algoritmul lui Shor folosind computerul cuantic IBM disponibil?

Care sunt criteriile NIST pentru a verifica transmiterea algoritmilor PQC?

Cum face NIST o comparație conform căreia un anumit algoritm este eficient și că securitatea sa nu poate fi spartă de viitoarele atacuri cuantice?

Cât de eficient este implementat un algoritm este ușor - acești algoritmi rulează pe computere clasice, așa că oamenii au realizat implementări ale acestor algoritmi și este simplu să măsurați performanța.

Securitatea este măsurată utilizând aceeași metodă pe care o folosim pentru algoritmii non-cuantici - oamenii proiectează cei mai buni algoritmi de criptoanaliza la care se pot gândi pentru a-i sparge, estimează timpul de rulare a acelor algoritmi de criptoanaliza și astfel putem selecta parametrii de securitate care îi fac cunoscuti pe toți. Algoritmii de criptoanaliza durează o perioadă de timp imposibil de realizat.

Singura diferență dintre un algoritm PQC și un algoritm non-PQC este că, pentru un algoritm PQC, luăm în considerare și algoritmii de criptoanaliza care rulează pe un computer cuantic. Acest lucru este oarecum mai complicat, deoarece nu avem nimic care să poată rula un algoritm de criptoanaliza netrivial (calculatorul cuantic IBM și altele similare sunt mult prea mici și nu pot efectua corectarea erorilor necesare) și simulatoare cuantice (care rulează pe calculatoarele clasice) sunt, de asemenea, limitate în numărul de qubiți pe care îi pot gestiona. Pe de altă parte, avem într-adevăr o bună înțelegere a operațiunilor pe care le poate face un computer cuantic și astfel putem proiecta algoritmi care pot rula pe un computer cuantic. NIST nu face toată această muncă de proiectare - marea majoritate a acestei lucrări este realizată de academicieni și criptografi din afara NIST - NIST monitorizează îndeaproape această muncă și ia în considerare acest lucru.

Este de menționat că estimările concrete ale durității cuantice a diferitelor probleme este încă a foarte nou domeniu de cercetare, iar anumite întrebări sunt încă nerezolvate. Un bun exemplu în acest sens este lucrarea lui Piekert El dă C site de către CSIDH. Pe lângă faptul că este un joc de cuvinte grozav, această lucrare folosește ceva numit sita de colinizare (dezvoltat în 2013 de Greg Kuperberg IIRC) pentru a ataca ipoteza CSIDH. Rețineți că această ipoteză se distinge între toate ipotezele post-cuantice, deoarece are randament direct schimb de chei non-interactiv, ceva ce este

• destul de ușor de obținut din problemele clasice (variante de jurnal discret), dar
• obținerea de la lucruri precum LWE fie necesită parametri foarte mari, fie apelarea la o primitivă avansată (fie FHE sau criptare a funcției) --- în orice caz, schema rezultată este ineficientă.

Principalul punct al lucrării este de a remarca faptul că sita de colinizare nu necesită acces la o mare ($\aproximativ 2^{30}$) cantitatea de memorie cuantică direct, dar în schimb poate folosi „memoria clasică accesibilă cuantică” (estimarea finală este pentru mai mult, $\aproximativ 2^{40}$). Îmi amintesc că a existat o dezbatere (presupun că între Dan Bernstein și Chris, dar nu-mi amintesc exact) nici pe twitter/nist PQC google group despre implicațiile practice ale acestei estimări modificate.

Foarte aproximativ, se poate caracteriza securitatea clasică în termenii unei perechi de (timp, memorie) necesare pentru a sparge o primitivă. Securitatea cuantică este apoi legată de 4-tuplu (timp clasic, memorie clasică, timp cuantic, memorie cuantică). Modul precis de a extrage o singură estimare de securitate dintr-un astfel de 4-tuplu este încă o chestiune de dezbatere și chiar și doi experți în criptografia post-cuantică pot avea dezacordurile lor.