dimensiunea codurilor Goppa

Pentru criptosistemele McEliece/Niederreiter, o alegere eficientă, aparent sigură, a codului este un cod Goppa binar ireductibil, definit de un cod ireductibil. $g(x)\în GF(2^m)[x]$ de grad $t$ și un vector suport $L=(\alpha_0,\ldots,\alpha_{n-1})$ cu distincte $\alpha_i\în GF(2^m)$.

Codul în sine este $GF(2)$-vectori valoroși în nucleul matricei de verificare a parității $$ H=\stânga( \begin{matrice}{cccc} g(\alpha_0)^{-1}&g(\alpha_1)^{-1}&\ldots&g(\alpha_{n-1})^{-1}\ g(\alpha_0)^{-1}\alpha_0&g(\alpha_1)^{-1}\alpha_1&\ldots&g(\alpha_{n-1})^{-1}\alpha_{n-1}\ \vdots&\vdots&\ldots&\vdots\ g(\alpha_0)^{-1}\alpha_0^{t-1}&g(\alpha_1)^{-1}\alpha_1^{t-1}&\ldots&g(\alpha_{n-1})^{ -1}\alpha_{n-1}^{t-1}\ \end{matrice}\dreapta). $$ Rețineți că $H$ este de rang complet. Pentru a produce o matrice de verificare a parității $H'$ peste $GF(2)$, se pot înlocui intrările de $H$ cu vectori coloană în $GF(2)$ (folosind o anumită bază pentru extensie $GF(2^m)/GF(2)$).

Aproape toate sursele pe care le consult listează codul rezultat ca $[n,k]=[n, n-mt]$, dar construcția generală (să zicem pentru codurile alternative) dă $k=n-mt$ ca limita inferioară pentru dimensiune $k$ a codului subspațial rezultat.

Întrebările mele sunt:

1. Cât de des este rangul rezultat $k=n-mt$? În configurația AG, cred că aceasta este o dimensiune Riemann-Roch, așa că poate un geometru algebric poate răspunde.
2. Contează dacă avem rânduri redundante în verificarea parității $H'$? Afectează acest lucru implementările criptosistemului?

Cred că acest lucru a fost abordat în generatorul de chei de la https://eprint.iacr.org/2017/595.pdf (secțiunea 5.2), chiar dacă doar pentru a returna un eșec și a reporni procesul de generare a cheii atunci când rref nu este atins; ele dau 29% ca probabilitate de succes bazata pe densitatea de $GL_{mt}(GF(2))$ în $Mat_{mt\times mt}(GF(2))$, adică densitatea asimptotică este $$ \prod_{i=1}^{\infty}\left(1-\frac{1}{2^i}\right)=0,288\ldots. $$

Gândindu-mă a doua oară în ceea ce privește 1), cred că este mai degrabă o întrebare despre când nucleul unei hărți liniare este definit într-un subcâmp (de exemplu, nucleul de $x-\sqrt{2}y$ are dimensiunea unu peste $\mathbb{Q}(\sqrt{2})$ dar dimensiunea zero când este limitată la $\mathbb{Q}$).

1. Din punct de vedere euristic (pentru parametrii de interes criptografic), este destul de puțin probabil. Binar $n\ori(n-r)$ matricele cu intrări aleatorii au un mai mic decât $2^{-n+r}$ șansa de a fi deficienți de rang. Poate exista un răspuns geometric mai precis.

2. Codul este probabil calculat prin punerea folosind transformări de rând pentru a pune $H'$ în formă sistematică $(I|A)$ iar apoi luând codul binar Goppa ca $(I|A^t)$. Dacă $H'$ este un rang deficitar, atunci implementarea va trebui să aibă un mijloc de a detecta că forma sistematică completă nu a fost atinsă și de a elimina rândurile rămase de $H'$. Dacă rangul de $H'$ este $r$ atunci va fi matricea noastră binară de generator de cod Goppa $n\ori(n-r)$ care este probabil mai mare decât memoria alocată (și se adaugă la problemele deja dureroase ale lățimii de bandă). Unele rânduri ale matricei generatoare vor trebui acum să fie junk. Dorim să evităm coloanele redundante pentru a menține greu decodificarea setului de informații, așa că probabil că vom dori să desistematizăm aleatoriu matricea generatorului înainte de a șterge rândurile, a permuta coloanele și a resistematiza. Există apoi problema interesantă că contururile de rânduri șterse ar putea fi prezentate decodorului nostru și pot fi dezordonate cu succes la ceva care nu se află în intervalul matricei noastre generatoare, dar decodorul nostru va folosi probabil matricea noastră resistematizată pentru a o mapa la intervalul matricei noastre. matricea generatoarelor. Este puțin probabil ca implementările să fie pregătite pentru acest lucru și ar putea prezenta un comportament imprevizibil. Una peste alta, probabil că ar fi mai bine să alegeți unul nou $g(X)$ și o ia de la capăt.