înregistrare Logare
Puncte:1
avatar Crypto

Utilizarea codurilor ireductibile Goppa în schema McEliece

drapel in
yoyo

Există un motiv criptografic pentru utilizarea unui ireductibil polinomul Goppa $g$ în schema McEliece? Nu este nevoie de ireductibilitate pentru a defini un cod utilizabil, așa că presupun că există un atac structural împotriva polinoamelor reductibile? [Un avertisment este că prezentarea pe care am văzut-o pentru decodarea Patterson folosește ireductibilitatea, dar nu trebuie să folosiți acel algoritm (și nu este folosit, de exemplu, în implementarea FPGA). Aici).]

Generația de chei este deja suficient de enervantă fără a impune ireductibilitatea IMHO. Singurul lucru la care mă pot gândi este că ireductibilitatea asigură cu siguranță suportul $L$ este disjuns de zerourile lui $g$ menţinând în acelaşi timp distribuţii uniforme asupra alegerii $g$ și $L$

68
0 + 0
Puncte:2
Daniel S avatar Crypto
drapel ru
Daniel S

După cum observați, $g(X)$ nu poate avea rădăcini în $L$ și deci trebuie să efectuăm cel puțin un polinom GCD pentru a verifica acest lucru.

Pentru codurile Goppa binare, trebuie să verificăm și asta $g(X)$ nu are rădăcini repetate, altfel dovada distanței minime se poate deteriora. Acest lucru va necesita o altă verificare GCD.

Ireductibilitatea exclude ambele aceste situații, precum și probleme iritante cu algoritmul lui Patterson (cred că Patterson poate fi asimptotic mai rapid decât varianta Berlekamp-Massey lui Sendrier, dar nu sunt sigur). Complexitatea Testul lui Rabin nu va fi cu mult mai rău decât testele pe care trebuie să le facem deja, așa că pentru o bucată unică de generare a cheilor am putea la fel de bine să facem asta.

0 + 0
drapel in
yoyo
Nu am luat în considerare separabilitatea (necesară pentru „boost” în distanță minimă) - aș putea cumpăra asta ca un motiv suficient (împreună cu evaluarea de-a lungul $L$). Există teste de ireductibilitate mai bune decât cel la care v-ați legat? ($x^{q^n}-x$ este destul de mare sau poate că nu fac o parte din aritmetica polinomială suficient de eficient.) Lucrarea la care am făcut legătura preia un element aleatoriu dintr-o extensie adecvată și calculează polinomul minim ( sperând un câștigător) mai degrabă decât respingerea eșantionării polinoame aleatoare.
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.