CRYSTALS-Dilithium: firma digitale basata su LWE

31 Mag

Introduzione

Il processo di standardizzazione del NIST in ambito Post-Quantum ha identificato due schemi crittografici da intendersi come soluzioni “primarie”. Per quanto riguarda i Key Encapsulation Mechanisms (KEMs), schemi di derivazione chiave, è stato selezionato CRYSTALS-Kyber, mentre in ottica firme digitali la scelta è ricaduta su CRYSTALS-Dilithium.

All’interno dei moderni protocolli crittografici di comunicazione, Dilithium andrà a sostituire gli schemi attualmente utilizzati per la firma digitale, tra i quali si ricordano RSA e quelli basati su curve ellittiche, entrambi provati essere vulnerabili agli attacchi di un computer quantistico.

CRYSTALS-Dilithium

Analogamente a Kyber, Dilithium basa la propria sicurezza su alcuni problemi computazionali definiti sui reticoli e ritenuti intrattabili anche per un computer quantistico. In particolare, come si analizzerà in seguito, la generazione della coppia di chiavi pubblica-privata avviene attraverso la definizione di un’istanza del Module-LWE.
Per completezza, si cita anche lo Short Integer Solution (SIS)[1] Problem, ovvero il problema di trovare soluzioni di dimensioni contenute ad un sistema lineare, formalmente definito come:

Data una matrice $\mathbf{A}\in\mathbb{Z}^{k\times m}$ , un numero intero positivo $q$ , un numero reale positivo $\beta$ , si trovi un vettore $\mathbf{x}\in\mathbb{Z}^m$ tale che

$0\leq ||\mathbf{x}|| < \beta$ ;
$\mathbf{A}\cdot \mathbf{x} \equiv \mathbf{0}\mod q$ .

Prima di affrontare il dettaglio dello schema di firma Dilithium, è utile fissare alcune notazioni.

$q$ è un numero primo
$\mathbb{Z}_q$ indica l’insieme $\{0,\dots,q-1\}$
$R_q=\mathbb{Z}_q[X]/(X^n+1)$ indica l’insieme dei polinomi in $X$ a coefficienti in $\mathbb{Z}_q$ con relazione $X^n=-1$
$S_\eta$ indica un sottoinsieme di $R_q$ con coefficienti limitati da $\eta$
Sia $S$ un insieme, $s\leftarrow S$ indica che $s$ è campionato uniformemente in $S$
$B_{\tau}$ indica il sottoinsieme di $R_q$ composto dai polinomi con $\tau$ coefficienti uguali a $\pm 1$ ed il resto a $0$
$\textsf{H}$ è una funzione di hash con spazio di arrivo $B_{\tau}$

In quanto firma digitale, le fasi che compongono lo schema Dilithium, di seguito riportate in modo semplificato, si identificano in Generazione chiavi, Firma e Verifica.

Generazione chiavi

In questa fase vengono prodotte la chiave privata e la chiave pubblica che verranno utilizzate rispettivamente per realizzare e verificare una firma. Viene campionata uniformemente una matrice pubblica $\mathbf{A}$ in cui ciascuna componente è un polinomio nell’insieme $R_q$ . Le entrate della chiave privata $(\mathbf{s_1}, \mathbf{s_2})$ sono campionate uniformemente nell’insieme $S_{\eta}$ . Utilizzando la matrice $\mathbf{A}$ ed i vettori $(\mathbf{s_1}, \mathbf{s_2})$ , si ricava il vettore $\mathbf{t}$ che, insieme a $\mathbf{A}$ , forma la chiave pubblica dello schema di firma.

Come riportato in precedenza, la generazione delle chiavi in Dilithium consiste nella creazione di un’istanza del Module-LWE. Infatti, per risalire ai segreti $(\mathbf{s_1},\mathbf{s_2})$ della chiave privata data la chiave pubblica $(\mathbf{A},\mathbf{t})$ , un attaccante dovrebbe essere in grado di risolvere il problema Module-LWE e, considerata l’assunzione di intrattabilità, questo fornisce solide garanzie sulla sicurezza dello schema.

Si osserva che, a differenza di altri schemi basati sui reticoli partecipanti al processo del NIST, i vettori segreti $(\mathbf{s_1}, \mathbf{s_2})$ sono campionati in modo uniforme e non seguendo una distribuzione Gaussiana discreta. Gli autori sostengono che, grazie a questa scelta, sia possibile ridurre il rischio di particolari attacchi di tipo side-channel che renderebbero insicure alcune implementazioni.

È rilevante notare che, essendo la matrice random $\mathbf{A}$ composta da $k\cdot l$ polinomi in $R_q$ , la sua rappresentazione avrebbe dimensioni eccessive rendendo la trasmissione piuttosto costosa e, quindi, l’utilizzo di Dilithium meno praticabile. La soluzione adottata è di generare $\mathbf{A}$ a partire da un seed di dimensioni più contenute, così facendo è sufficiente trasmettere all’interno della chiave pubblica unicamente il seed individuato.

Firma

La firma di un messaggio in Dilithium è realizzata ricorrendo all’approccio denominato Fiat-Shamir with Aborts, introdotto dal matematico ucraino-statunitense Vadim Lyubashevsky nel 2009.

In questa strategia, lo schema di firma è ottenuto a partire da un protocollo di identificazione in cui viene rimossa l’interattività ricorrendo alla trasformata di Fiat-Shamir, come avviene per la firma di Schnorr in EdDSA. In un protocollo di identificazione, un Prover deve dimostrare ad un interlocutore Verifier di essere in possesso di un certo segreto, in questo caso la coppia $(\mathbf{s_1},\mathbf{s_2})$ , senza rivelarlo.

Lo schema di identificazione prevede un’interazione fra le parti propedeutica all’invio della prova $\mathbf{z}$ . In uno schema di firma, le due comunicazioni preliminari possono essere rimosse permettendo al prover di generare la challenge $c$ calcolandola come hash della concatenazione tra messaggio $m$ e commitment $\mathbf{w}$ .

Si osservi che, seguendo lo schema sopra riportato, per alcune sfortunate scelte del vettore $\mathbf{y}$ , è possibile che un attaccante ricavi informazioni sulla chiave privata a partire dalla firma $(\mathbf{z},c)$ .
Si rende pertanto necessaria una fase cosiddetta di rejection sampling che si curi di questa eventualità, ripetendo il processo di firma qualora alcuni parametri escano da un regime di sicurezza. Infatti, per completare la costruzione Fiat-Shamir with Aborts, è necessario introdurre tale controllo prima di inviare la firma.
Nello schema di Dilithium, il rejection sampling è effettuato attraverso un ciclo che termina solamente quando i coefficienti della firma rientrano in certi limiti derivati dai parametri dello schema.

In Dilithium sono introdotte alcune ottimizzazioni che permettono di considerare solamente i bit più significativi del commitment $\mathbf{w'}$ . Al fine di mantenere la correttezza delle operazioni, si rende necessario trasmettere un hint che permetta di verificare la firma pur avendo a disposizione solamente la versione troncata del vettore di commitment. Se da un lato l’invio di un hint rende necessario aggiungere circa 100 byte alla lunghezza della firma, questa stessa accortezza permette di ridurre di circa un fattore 2 la dimensione della chiave pubblica.

Verifica

Nel passaggio di verifica si controlla che il commitment $c$ , contenuto nella firma, coincida con l’output della funzione di hash calcolata sulla concatenazione del messaggio $m$ e $\mathbf{w'}$ , ove $\mathbf{w'}$ è ricavato a partire dalla firma $\sigma=(z,c)$ e dalla chiave pubblica $\mathbf{A}$ .
Anche nel processo di verifica della firma sono state introdotte alcune ottimizzazioni che, lavorando con solamente i bit più significativi, permettono di ridurre in modo sensibile la dimensione della firma digitale.

Performance

L’obiettivo principale degli autori di CRYSTALS-Dilithium è quello di costruire uno schema che minimizzi le dimensioni di chiave pubblica e firma di un messaggio.
Questa scelta è volta a favorire l’utilizzo di Dilithium in contesti, come quello della navigazione sicura nel web, in cui sia necessario trasmettere una catena di certificati contenente numerose firme e le rispettive chiavi pubbliche utilizzate per la verifica.

Nel grafico sopra riportato, viene fornita una comparazione fra le performance di Dilithium e di due degli schemi tradizionali maggiormente utilizzati (RSA e EdDSA) in termini di dimensione dati da trasmettere (a sinistra), ovvero chiave pubblica e firma, e di costo computazionale delle componenti descritte nelle sezioni precedenti (a destra).
Se da un lato si osserva come l’efficienza computazionale in cicli richiesti non rappresenti un problema — Dilithium è paragonabile a EdDSA e molto più efficiente di RSA –, i costi di trasmissione vanno ulteriormente investigati. Infatti, si nota come in Dilithium la dimensione di chiave pubblica e firma sia significativamente maggiore rispetto a quella prodotta dagli algoritmi tradizionali. Inoltre, questa risulta maggiore della Maximum Transmission Unit (MTU) che è tipicamente fissata a 1500 byte e rappresenta la massima capacità di un pacchetto IP. Il processo di transizione a schemi post-quantum dovrà, quindi, tenere fortemente in considerazione la questione individuata per mitigare al meglio gli effetti che ciò potrà avere in termini di latenza e frammentazione di pacchetti.

[1] In Dilithium, variazioni di SIS giocano un ruolo fondamentale in un’analisi di sicurezza più approfondita rispetto al presente articolo

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

Francesco Stocco, laureato magistrale in Matematica presso l’Università degli Studi di Padova e l’Université de Bordeaux frequentando il percorso di studi “Algebra Geometry And Number Theory” (ALGANT), entrato a far parte del gruppo di ricerca in Crittografia di Telsy alla fine del 2020 occupandosi in particolare di temi inerenti alle tecnologie quantistiche.

Marco Rinaudo, laureato triennale in Matematica presso l’Università degli Studi di Torino e laureato magistrale con specializzazione in Crittografia presso l’Università di Trento. In seguito ad uno stage curricolare svolto nel 2022 in Telsy, da gennaio 2023 è parte del Gruppo di Ricerca in Crittografia.