Cum să mapați mesajul la vectorul greutății t în criptosistemul Niederreiter?

În criptosistemul Niederreiter, solicităm ca mesajul să fie un vector de greutate $t$ în $F_q^n$ în criptare, presupune $t$ este capacitatea de corectare a erorilor a codului. Dar care este maparea? O modalitate posibilă este maparea mesajului de lungime $k$ la un cuvânt de cod de greutate constantă $t$ cod liniar, de exemplu, $[n,k]_q$ cod. În acest fel, spațiul mesajului este $q^k$. Există o altă modalitate mai bună de a face asta, de exemplu, spațiul mai mare pentru mesaje?

Intrebare amuzanta! Putem, de fapt, să realizăm eficient spațiul maxim de dimensiune pentru mesaje $(q-1)^t({n\atop t})$.

Să începem cu cazul $q=2$. Vrem să generăm un șir de lungime $n$ și greutatea Hamming exact $t$. Sunt $C:=({n\atop t})$ astfel de șiruri și am dori să mapam un mesaj întreg din interval $[0,C-1]$ la acest set bijectiv. Combinatoric vorbind, setul de șiruri de biți îi corespunde combinatii (specific $t$-combinații ale numerelor întregi de la 0 la $n-1$). Putem rescrie bijectiv șirul nostru ca o secvență strict descrescătoare a $t$ valorile $n-1\ge c_t>c_{t-1}>\ldots>c_1\ge 0$ prin notarea indicilor locației celor 1.

Acum, o teoremă elegantă a matematicii pe care Knuth o atribuie matematicianului din secolul al XIX-lea Ernesto Pascal spune că fiecare număr $N$ poate fi reprezentat în sistem combinatoriu de numere $$N=\left({c_t\atop t}\right)+\cdots+\left({c_1\atop 1}\right)$$ iar această ordonare a pașilor prin combinații este o ordine lexicografică (în scopul nostru, prima $({n\atop t})$ greutatea listei de intrări $t$ șiruri de lungime $n$). Prin urmare, dacă avem un număr întreg $N\în [0,C-1]$ putem folosi un algoritm lacom pentru a recupera $N$greutatea-a $t$ șir binar dat de sistemul combinatoriu de numere. Iată niște pseudo-cod:

Inițializează i:=n-1, j:=t, rest=N
în timp ce i>=0
   dacă Binom(i,j) > rest
      setați bitul i al șirului la 0
   altfel
      setați bitul i al șirului la 1
         j--
         rest -= Binom(i,j)
   eu--

Harta inversă este simplă.

De exemplu, cu $n=10$, $t=3$ există 120 de combinații posibile, să găsim a 17-a (numărând cu 0 în sus). Mai întâi găsim cel mai mic număr tetraedric nu mai mare de 17; aceasta este $({5\atop 3})=10$; marcam locul 5 si mai avem 7. Găsim acum cel mai mic număr triunghiular nu mai mare de 7; aceasta este $({4\atop 2})=6$; marcăm locul 4 și ne rămâne 1. Găsim acum cel mai mic număr nu mai mare de 1; acest $({1\atop 1})=1$; marcam primul loc si nu ne mai ramane nimic. Coarda noastră este 0000110010. Dacă primim șirul pe care îl calculăm $({5\atop 3})+({4\atop 2})+({1\atop 1})=10+6+1=17$.

Pentru alfabete mai generale, putem folosi procesul de mai sus pentru a genera locațiile erorilor și apoi alegem dintre $q-1$ posibile valori de eroare pentru fiecare locație. Concret lăsat $M=C(q-1)^t$ să fie de dimensiunea spațiului nostru de mesaje. Dat un mesaj $m\în[0,M-1]$ noi lăsăm $N=[m/(q-1)^t]$ astfel încât $N\în[0,C-1]$ și generați o listă de locații ca mai sus. Lăsăm apoi $B=m\mod{(q-1)^t}$ si scrie $B$ ca $t$-numar cifra din baza $(q-1)$ (permițând zerouri înainte) și atribuiți valorile digit+1 fiecărei locații. Din nou, harta inversă este simplă.

De exemplu, să presupunem că avem un alfabet zecimal și luăm în considerare șiruri de lungime 10 cu 3 erori. Există 120*729=87480 de mesaje posibile; să găsim 12707th. Găsim $N=[12707/729]=17$ și astfel generați același șir de biți ca mai sus. Găsim $B=12707\mod{729}=314$ care este 378 în baza 9. Mesajul nostru se convertește în șirul de eroare 0000480090. Din nou, dacă primim acest șir, scoatem cifrele diferite de zero în ordine și scădem câte una din fiecare pentru a da numărul de bază 9 378, astfel încât $B=314$ la fel știm că $N=17$ din locațiile de eroare și pot calcula $m=729N+B=12707$.

Capitolul 7.2.1.3 „Generarea tuturor combinațiilor” din „Arta programării computerelor” definitivă a lui Donald Knuth este o relatare excelentă, cuprinzătoare (deși care distrag atenția) a altor algoritmi pentru generarea de combinații.