Numărul de operații pe biți necesare pentru atacurile de decodare a setului de informații asupra sistemelor cripto-cod?

Această întrebare este potențial relevantă pentru standardele de criptografie post-cuantică NIST, care implică criptosisteme bazate pe cod, cum ar fi McEliece, BIKE și HQC.

Această hârtie estimează numărul concret de operații pe biți necesare pentru a efectua atacul MayâMeurerâThomae (MMT) de decodare a setului de informații (ISD). Acesta arată că acest lucru este semnificativ mai mic decât pentru oricare dintre celelalte variante ISD luate în considerare, inclusiv algoritmul BJMM, care este considerat în general o îmbunătățire față de MMT. (De exemplu, pentru setul de parametri McEliece clasic 8192128, lucrarea prezintă complexitatea MMT ca $2^{249.74}$ spre deosebire de $2^{299.89}$ pentru BJMM.) Este corectă această analiză?

Dacă analiza este corectă, se pare că aceasta ar putea amenința nu doar unii dintre parametrii McEliece, ci și unii dintre parametrii celorlalte scheme bazate pe cod. Dacă nu, care este o sursă bună pentru numere precise?

(Hârtia susține $2^{87.95}$ complexitatea memoriei pentru MMT, în comparație cu $2^{79.97}$ pentru BJMM și $2^{67.64}$ pentru algoritmul lui Stern, vezi Tabelul 5. Acest lucru nu pare suficient de mare pentru a compensa discrepanța pe orice model plauzibil pentru costul memoriei vs operațiuni pe biți. MMT se pretinde la fel de ieftin pentru alte seturi și scheme de parametri.)

Această întrebare este postată pe forumul NIST PQC Aici.

Nu am putut reproduce exact complexitatea biților din lucrarea menționată [1], autorii nu au furnizat codul sursă. Îmi postez estimatorii pentru atacurile MMT și BJMM Aici.

Concluzia că algoritmul BJMM este mai rău decât MMT este incorectă deoarece MMT este un caz special de BJMM. Pe scurt, BJMM este MMT fără reprezentări ale tipului $1 = 0+0 \bmod 2 $ pentru vectorul de eroare. Confuzia vine din faptul că autorii [1] luați în considerare BJMM cu o anumită adâncime fixă ​​a arborelui de căutare (și anume, adâncimea 3 așa cum se face în lucrarea originală [2]. Cu toate acestea, acest lucru poate să nu fie optim pentru un anumit regim de sparsitate, prin urmare, concluzia greșită că BJMM este mai rău decât MMT. Dau mai multe detalii mai jos.

La baza ambelor algoritmi MMT și BJMM se află ideea de ambiguu împărțirea vectorului de eroare $e \in \{0,1\}^k$ de greutate $p$ la fel de $e = e_1 + e_2$. MMT ia $e_1, e_2 \in \{0,1\}^k$ fiecare de greutate $p/2$, dând astfel $\binom{p}{p/2}$ moduri de a reprezenta $0$-coordonate ca $0+1$ sau $1+0$ în $e$. BJMM ia $e_1, e_2 \in \{0,1\}^k$ fiecare de greutate $p/2 + \varepsilon$, dând astfel $\binom{p}{p/2} \cdot \binom{k-p}{\varepsilon}$ reprezentări (al doilea multiplu este numărul de reprezentări de tip $0 = 1+1$).

Se pare că pentru problema decodării în regim dens, adică atunci când greutatea de $e$ este de ordine $\Theta(n)$, algoritmul BJMM este mai rapid atunci când repetam procesul prin reprezentare $e_1$, $e_2$ într-un mod ambiguu. Astfel, se ajunge la o structură de arbore de căutare a algoritmului, unde adâncimea optimă a arborelui este un parametru de optimizat. Din [2] pentru regimul dens se întâmplă să fie 3.

Pentru parametrii Classic McEliece, se dovedește că efectuarea adâncimii-2 este optimă. Intuitiv, cu cât eroarea este mai rară, cu atât arborele optim va fi mai puțin adânc, deoarece nu se poate împărți o greutate mică în jumătate de prea multe ori.

În special, obțin următoarele securități de biți (și complexități de memorie) cu estimatorul meu. Acestea sunt probabil subestimări, așa cum $poli(n)$ factorii sunt ignorați. Le puteți reproduce rulând scriptul.

-------------------- MMT --------------------

n = 3488 k = 2720 w = 64 {„runtime”: 133,610045757394, „mem”: 61,4108701659799}

n = 4608 k = 3360 w = 96 {„runtime”: 174,170500202444, „mem”: 76,7183814578096}

n = 6960 k = 5413 w = 119 {„runtime”: 244,706198594600, „mem”: 123,451330788046}

n = 8192 k = 6528 w = 128 {„runtime”: 277,268692835670, „mem”: 140,825234863797}

BJMM adâncimea 2 depășește ușor atât MMT, cât și BJMM adâncimea 3.

----------------BJMM adâncime 2 -----------------

n = 3488 k = 2720 w = 64 {'runtime': 127.121142192395,'mem': 65.4912086419963,'eps': 4}

n = 4608 k = 3360 w = 96 {„runtime”: 164,510671206084, „mem”: 88,1961572319148, „eps”: 6}

n = 6960 k = 5413 w = 119 {„runtime”: 231,228308300186, „mem”: 118,193072674123, „eps”: 8}

n = 8192 k = 6528 w = 128 {„runtime”: 262,367185095806, „mem”: 134,928413147468, „eps”: 8}

----------------BJMM adâncime 3 ----------------

n = 3488 k = 2720 w = 64 {„runtime”: 132,929177320070, „mem”: 30,8744409777593, „eps”: [2, 0]}

n = 4608 k = 3360 w = 96 {„runtime”: 167,443669507488, „mem”: 45,4015594758618, „eps”: [6, 0]}

n = 6960 k = 5413 w = 119 {„runtime”: 236,346159271338, „mem”: 67,5649403829532, „eps”: [6, 0]}

n = 8192 k = 6528 w = 128 {„runtime”: 269,431207750362, „mem”: 70,1193015124538, „eps”: [6, 0]}

[1] https://www.mdpi.com/1999-4893/12/10/209/pdf

[2] https://eprint.iacr.org/2012/026.pdf