La matematica dietro la PQC: Syndrome Decoding Problem

11 Dic

Introduzione

Gli schemi crittografici protagonisti del processo di standardizzazione del NIST appartenenti alla famiglia della code-based cryptography sono costruiti a partire da un problema detto Decoding Problem.

Dato un codice e un vettore, il problema consiste nel trovare la parola del codice più vicina (secondo una certa metrica) al vettore.

In particolare, il Syndrome Decoding Problem (SD) sta alla base dei crittosistemi McEliece (1978) e Niederreiter (1986) che hanno dato origine alla branca della crittografia asimmetrica detta code-based cryptography.

Codici e sindromi

Una rappresentazione di un codice lineare $\mathcal{C}$ alternativa alla matrie generatrice può essere fatta considerando la sua parity-check matrix (o matrice di parità), una matrice che descrive le relazioni lineari che le componenti di una parola (codeword) devono soddisfare.

La parity-check matrix è la matrice generatrice del codice duale di $\mathcal{C}$ , ovvero l’insieme dei vettori ortogonali ai vettori di $\mathcal{C}$ , detto $\mathcal{C}^{*}$ . Più formalmente il codice duale di $\mathcal{C}$ è $\mathcal{C}^{*}=\{v\in\mathbb{F}_q^n \mid xv^{T}=0\ \forall x\in C\}.$

Sia $H\in\mathbb{F}_q^{n-k}$ una matrice tale che le sue righe formano una base di $\mathcal{C}^{*}$ , il codice lineare $\mathcal{C}$ può essere scritto come $\mathcal{C}=\{c\in\mathbb{F}_q^n \mid Hc^{T}=0\}$ .
Pertanto, ${H}$ definita nel precedente modo è la parity-check matrix del codice $\mathcal{C}$ .

Potrebbe sembrare innaturale rappresentare un codice attraverso la sua parity-check matrix se confrontata con la matrice generatrice.
Tuttavia, anche se le due rappresentazioni sono equivalenti, in molte applicazioni dei codici la rappresentazione con parity-check è più rilevante.

Consideriamo il codice descritto dalla seguente matrice generatrice:
$G = \left(\begin{matrix} 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{matrix}\right).$

La sua parity-check matrix è:
$H = \left(\begin{matrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{matrix}\right).$

Notiamo che le colonne di $H$ hanno una struttura particolare, ovvero sono i numeri da 1 a 7 scritti in binario. Supponiamo di voler decodificare $y=c+e$ dove $e$ è il vettore dato da tutti 0 tranne un 1 in posizione $i$ .

Non è chiaro come utilizzare la matrice $G$ per ricavare $\mathcal{C}$ . Invece, la matrice $H$ fornisce delle informazioni utili: la sindrome $Hy^{T}=Hc^{T}+e^{T}=He^{T}$ di $y$ che corrisponde alla $i$ -esima colonna di $H$ .

Questo significa che per questo codice la posizione $i$ dell’errore è data dalla sindrome $Hy^{T}$ di $y$ in rappresentazione binaria.
Il codice $\mathcal{C}$ così definito è conosciuto come codice di Hamming di lunghezza 7.

La rappresentazione con parity-check matrix può essere utilizzata per decidere se un vettore è una parola del codice e risulta essere molto utile in fase di decodifica di un messaggio. Infatti, supponiamo che $\mathcal{C}$ sia la parola del codice che il mittente vuole inviare, $e$ l’errore che la parola ha subito lungo il canale di comunicazione e $y=c+e$ la parola ricevuta dal decoder, abbiamo visto come $Hy^{T}$ , detta sindrome (o, in inglese, syndrome) di $y$ rispetto a $H$ , è una buona fonte di informazioni quando proviamo a decodificare $y$ .

In particolare, se $y$ è una parola del codice, allora la sua sindrome sarà zero dalla definizione di parity-check matrix. Inoltre, due messaggi $y_1,\ y_2$ aventi lo stesso errore, ovvero $y_1=c_1 + e$ e $y_2=c_2 + e$ avranno la stessa sindrome: $Hy_1^y = Hc_1 ^{T} + He ^{T} = He ^{T} = Hc_2 ^{T} + He ^{T} = Hy_2 ^{T}.$

Syndrome Decoding Algorithm

Per descrivere come il calcolo della sindrome risulta utile per la decodifica delle parole del codice, è necessario definire alcuni elementi fondamentali della teoria dei codici.

Sia $\mathcal{C}$ un codice lineare su $\mathbb{F}_q$ e $a\in\mathbb{F}_q^n$ , si definisce coset di $a$ (rispetto al codice $\mathcal{C}$ ) la classe di equivalenza $a+C=\{a+c \mid c\in \mathcal{C}\}$ e si definisce coset leader il vettore del coset col peso più piccolo.

C’è una biiezione tra l’insieme dei coset e le sindromi. Sia $H$ la parity-check matrix di $\mathcal{C}$ . Allora per ogni $a, b\in\mathbb{F}_q^n$ $a+\mathcal{C}=b+\mathcal{C} \iff Ha^{T}=Hb^{T}.$
Infatti, $Ha^{T}=Hb^{T} \iff H(a-b)^{T}=0 \iff a-b \in \mathcal{C}$ .

I coset giocano quindi un ruolo importante nella geometria dei codici perché costituiscono una partizione dello spazio su cui è definito il codice. Infatti, sia $\mathcal{C}$ un codice lineare su $\mathbb{F}_q$ di dimensione $k$ , si ha una partizione di $\mathbb{F}_q^n$ in $q^{n-k }$ insiemi di dimensione $q^{k}$ data dai coset: $\mathbb{F}_q^n=\bigsqcup_{a\in\mathbb{F}_q^n}a+\mathcal{C} .$

Un algoritmo di decodifica tramite le sindromi può essere descritto da tre fasi:

pre-computation phase: creiamo una tabella in cui per ogni sindrome $s$ , scegliamo il coset leader del coset con sindrome $s$ . Questo è possibile perché c’è una biiezione tra coset e sindromi.
calcoliamo la sindrome $s$ di $y$ utilizzando $H$ : $Hy^{T}.$
decodifichiamo $y$ nella parola $y-e_s$ con $e_s$ il coset leader.

Sebbene quello appena mostrato sia un algoritmo che risolve il problema della decodifica, è importante notare che questo richiede tempo esponenziale nella dimensione del codice; infatti la tabella costruita nella prima fase dell’algoritmo ha dimensione $q^{n-k}$ , esponenziale in $n$ .

Syndrome Decoding Problem

In generale, data una parity-check matrix $H$ , un vettore $y$ e un intero $t$ , il problema di trovare un vettore $\mathcal{C}$ tale che $Hc^{T} =0$ e $\mathrm{w}( y-c)\le t$ (con $\mathrm{w}$ peso di Hamming) è un problema difficile. Questo problema in letteratura è noto come Syndrome Decoding Problem (SD) ed è stato dimostrato essere NP-completo nel 1978 da Berlekamp, McEliece e Van Tilborg^[1].

Sebbene in letteratura esistano famiglie di codici e distanze di decodifica per i quali il problema è facile da risolvere, cioè che ammettono un algoritmo di decodifica efficiente, in generale dato un codice C non è detto che un tale algoritmo sia noto.
Infatti, la NP-completezza mostra che non possiamo sperare di risolvere il problema della decodifica in tempo polinomiale per tutti gli input.

Un problema strettamente collegato al Syndrome Decoding Problem è dato dalla sua formulazione duale: data una matrice generatrice $G$ del codice $\mathcal{C}$ , un vettore $y$ e un intero $t$ , si chiede di trovare una parola del codice $\mathcal{C}$ che disti da $y$ al più $t$ . Questo problema è chiamato Nearest Codeword Problem (NC) ed è anch’esso NP-completo.

Questi due problemi (nel caso peggiore) sono strettamente equivalenti, se siamo in grado di risolverne uno, allora possiamo trasformare l’algoritmo di risoluzione di uno nell’algoritmo che risolve l’altro nello stesso tempo di esecuzione (fino a un piccolo overhead di tempo polinomiale).

Syndrome Decoding Problem negli schemi post quantum

Entrambi i problemi sopra sono stati usati per il design di crittosistemi di cifratura a chiave pubblica.
La crittografia basata su codici inizia con il lavoro di Robert McEliece del 1978, che propone uno schema di cifratura che basa la propria sicurezza sul problema NC.

Un’evoluzione dello schema di McEliece si trova nel lavoro di Harald Niederreiter (1986), che propone una versione duale basata sul Syndrome Decoding Problem. Questa variante permette di avere lo stesso livello di sicurezza della precedente versione, ma con testi cifrati più piccoli.

Proprio sullo schema di Niederreiter si basano tutte le proposte arrivate al round finale della competizione del NIST volta ad individuare standard post quantum.

Tra queste, la proposta più conservativa è chiamata “Classic McEliece” (nome fuorviante in quanto basata sullo schema di Niedettereiter e non di McEliece), mentre gli schemi BIKE e HQC sono più innovativi e performanti.

Nel corso dei prossimi articoli, tali schemi verranno approfonditi.

^[1] Berlekamp, E., McEliece, R., and Van Tilborg, H. On the inherent intractability of certain coding problems (corresp.). IEEE Transactions on Information Theory 24, 3 (1978), 384–386.

Questo articolo appartiene ad una serie di contributi, a cura del Gruppo di Ricerca in Crittografia di Telsy, dedicata al calcolo quantistico e alle sue implicazioni sulla Crittografia. Per la consultazione di altri articoli si rimanda all’indice della rubrica.

Per altri articoli relativi ai temi Quantum e Crittografia si rimanda alle relative categorie nel blog.

Gli autori

Veronica Cristiano, laureata triennale in Matematica presso l’Università di Pisa e laureata magistrale in Matematica con specializzazione in Crittografia presso l’Università di Trento, entrata a far parte del gruppo di ricerca in Crittografia di Telsy a metà del 2021.

Giuseppe D’Alconzo, laureato in Matematica con specializzazione in Crittografia presso l’Università di Trento, ha svolto nel 2019 uno stage presso Telsy, occupandosi di Multi-party Computation e Attribute Based Encryption. Attualmente è studente di dottorato in Matematica Pura e Applicata presso il Politecnico di Torino, con una borsa a tema “Crittografia Post-Quantum” nell’ambito del programma UniversiTIM e in collaborazione con il Gruppo di Ricerca di Telsy.