Cum putem măsura nivelurile de securitate ale algoritmilor criptografici post-cuantici? Există o modalitate standard de măsurare?

Cum măsurăm nivelurile de securitate ale algoritmilor criptografici Post Quantum, cum ar fi: NTRU Prime, Sabre, Kyber,... care sunt supuși procesului de standardizare NIST PQC (Competiție) în general?

Am citit documentația din pachetul de trimitere NIST al NTRU Prime, dar înțelegerea nivelurilor de securitate pare foarte complicată pentru algoritmii PQC, spre deosebire de cei non-PQC pentru care putem folosi metode de comparare ușoare cu AES-256. Se vorbește despre transformări și niveluri de securitate CCA, CPA în funcție de niște parametri dar mi se pare complicat.

Poate cineva să explice măsurarea securității pentru algoritmii PQC în general?

Această întrebare este legat. Rețineți că această întrebare face spuneți că securitatea este analizată prin comparație cu AES/SHA3, după cum bănuiți.

Poate că cel mai informativ mod de a afla mai multe despre acest lucru este să mergeți „în practică” și să citiți secțiunile de analiză de securitate ale diverșilor candidați NIST PQC runda 3. Acestea ar trebui să fie aproape de consensul comunității cu privire la modul de analiză a schemelor (deși există încă dezacorduri, care sunt de obicei discutate în grupul google NIST PQC). Exemple de câteva dintre dezacorduri sunt lucruri precum:

• Rotunjirea (în scopuri de compresie) îmbunătățește securitatea KEM-urilor bazate pe zăbrele? Dacă da, cu câți biți? (sau după ce „coreSVP count”, o metrică specifică analizei schemelor bazate pe zăbrele)
• Ce înseamnă mai exact numărul „CoreSVP”?
• Cât de precise sunt estimările (din criptoanaliza primitivelor bazate pe rețea „zgomotoase”) atunci când sunt aplicate la primitive bazate pe rețea cu zgomot exclusiv „determinist” (indus din rotunjire)?
• Cum să faceți față analizării adecvate a costurilor de memorie ale atacurilor. O mare problemă aici este diferențele dintre memoria cuantică (adică sunt necesari qubiți) și memoria clasică accesibilă cuantic, care ar trebui să fie mult mai abundentă (de exemplu, $2^{30}$ memoria clasică este în prezent destul de fezabilă, dar nu am auzit niciodată de o estimare sigură a când ar trebui să ne așteptăm $2^{30}$ qubits logici --- Nu cred că am lovit unu qubit logic încă!).
• Cum să gestionați în mod corespunzător reducerile nestrânse? Adesea, reducerile QROM sunt mai puțin stricte decât reducerile ROM.Ar trebui setați parametrii mai liberi pentru a compensa sau este acesta un artefact al modelului relativ nou?

În general, totuși, până la unele dezacorduri, măsurătorile de securitate sunt aproximativ similare cu ceea ce sunt pentru securitatea clasică (adică prin comparații cu securitatea AES/SHA3) și pot fi găsite în specificațiile diferitelor depuneri. Dacă citiți destule dintre ele, ar trebui să vă faceți o idee destul de bună despre modul în care comunitatea s-a hotărât (în mare parte) să analizeze securitatea diferitelor scheme.

Puteți citi și grupul google, desigur, dar este mult mai... formă liberă decât trimiterile, deci nu este poate cea mai succintă sursă de informații. Este demn de menționat că poate fi distractiv de citit indiferent, deoarece dezbaterea poate deveni oarecum animată (ceea ce poate contribuie la faptul că este mai puțin densă de informații decât trimiterile).

De multe ori, schemele de criptare (asimetrice) pot fi discutate în termeni de securitate demonstrabilă - putem arăta că schema este sigură în cazul anumitor atacuri dacă primativul criptografic de bază este greu. Cu alte cuvinte, securitatea demonstrabilă se bazează pe reducerea problemei noastre la prima sa, de exemplu, problema RSA se poate reduce la problema factoring.

În general, sunt discutate următoarele patru proprietăți, IND, CPA, CCA și CCA2:

IND (nediferențiere): un adversar nu poate distinge criptarea oricăror două mesaje de aceeași lungime, adică. dacă i se oferă un text cifrat de provocare $c$, ei nu pot spune dacă $c$ vin de la $m_1$ sau $m_2$.

IND-CPA (nediferențiere în cadrul unui atac de text simplu ales): un adversar nu poate distinge ce mesaj a fost folosit pentru a crea un text cifrat de provocare dacă i se oferă acces la cheia publică (cu alte cuvinte, este capabil să creeze texte cifrate din mesajele alese).

IND-CCA (nediferențiere în cazul unui atac cu text cifrat ales): Aceeași configurație ca și înainte, dar de data aceasta, adversarul are un oracol de decriptare pe care îl poate interoga până când i se dă textul cifrat de provocare.

IND-CCA2 (nedistingere într-un atac cu text cifrat ales adaptiv): Ca și exemplul anterior, totuși, acum adversarului i se permite să interogheze oracolul de decriptare chiar și după ce a primit provocarea (cu avertismentul, nu au voie să introducă textul cifrat de provocare la oracol)

Acestea sunt alese pentru a fi discutate ca și cum am putea demonstra că (presupunând dovezile aplicate în contextul adecvat), trebuie doar să ne îngrijorăm cu privire la duritatea problemei care stă la baza acesteia.

Definițiile acestor proprietăți pot fi ușor diferite pentru schemele simetrice (nu se bazează pe probleme matematice), dar suntem capabili să dovedim rezultate analoge, din nou în anumite condiții (gândiți-vă la lungimea cheii).

Acest lucru ne permite acum să evaluăm „nivelul de securitate” pentru acești parametri într-un mod care poate fi tradus și comparat cu cel al AES.