Firme multivariate basate su schemi di identificazione

15 Feb 2025

Introduzione

L’obiettivo di un protocollo di identificazione è quello di permettere che l’identità di qualcuno possa essere verificata. Più in particolare, un Prover deve dimostrare a un interlocutore, detto Verifier, di essere in possesso di un certo segreto senza che sia necessario rivelare alcuna informazione sul segreto stesso. Nel panorama crittografico esistono numerosi protocolli di identificazione riconducibili ad altrettanti problemi matematici. Tali protocolli sono di particolare interesse nell’ambito della transizione ad algoritmi post-quantum, in quanto a partire da essi è possibile costruire firme digitali (un esempio importante è quello dello schema Dilithium).
Fino ai primi anni 2000, non erano però noti protocolli di identificazione basati su assunzioni multivariate. La svolta si è avuta nel 2011, quando Sakumoto et al. hanno proposto due protocolli di identificazione costruiti su sistemi di equazioni multivariate su un campo finito, uno a 3 passi e uno a 5 passi.
Da quest’ultimo, nel 2016, è stato costruito lo schema MQDSS, firma multivariata sottomessa al processo di standardizzazione del NIST.
Mentre la costruzione di una firma a partire da un protocollo a 3 passi si può ottenere tramite una procedura standard (tramite la nota trasformata di Fiat-Shamir), un approccio analogo per un protocollo a 5 passi risulta più impegnativo e interessante.
Infatti, sebbene MQDSS sia stato eliminato dalla competizione del NIST e nessuno schema multivariato basato su schemi di identificazione sia presente in un processo di standardizzazione, vi sono stati numerosi sviluppi teorici che hanno reso questo approccio maggiormente competitivo.

Schemi di identificazione a 3 passi

Tipicamente, un protocollo di identificazione è composto da più interazioni tra Prover e Verifier. Un protocollo a 3 passi è tipicamente caratterizzato da una struttura ben definita. Il Prover invia inizialmente un primo messaggio detto Commitment, al quale il Verifier risponde con una Challenge. Infine, il Prover invia un’ultimo messaggio, detto Response, che contiene la prova da parte del Prover di conoscere un certo segreto. Protocolli con questa struttura sono anche chiamati Sigma Protocols.

Il lavoro di Sakumoto et al. è stato il primo a proporre uno schema di identificazione basato su assunzioni multivariate. Il protocollo a 3 passi è descritto di seguito.

Sia $\mathcal{F}$ un sistema multivariato di $m$ equazioni in $n$ incognite su $\mathbb{F}_q$ e sia $\mathcal{G}(\mathbf{x},\mathbf{y})=\mathcal{F}(\mathbf{x}+\mathbf{y})-\mathcal{F}(\mathbf{x})-\mathcal{F}(\mathbf{y})$ la sua forma polare.
Dati $\mathcal{F}$ l’istanza del problema $\mathcal{MQ}$ su $\mathbb{F}_q$ , e $\mathbf{v}\in\mathbb{F}_q^m$ un vettore, il problema $\mathcal{MQ}$ è trovare un vettore $\mathbf{s}\in\mathbb{F}_q^n$ tale che $\mathbf{v}=\mathcal{F}(\mathbf{s})$ .
Perciò, dopo aver scelto $\mathbf{s}\in\mathbb{F}_q^n$ random, l’algoritmo di generazione delle chiavi calcola $\mathbf{v}=\mathcal{F}(\mathbf{s})$ e restituisce $(pk, sk)=(\mathbf{v},\mathbf{s})$ .

L’idea alla base della costruzione a 3 passi del protocollo di identificazione risiede nella prova da parte del Prover di essere a conoscenza di una tupla $(\mathbf{r}_0, \mathbf{r}_1, \mathbf{t}_0, \mathbf{t}_1, \mathbf{e}_0, \mathbf{e}_1)$ che soddisfa le seguenti relazioni:

$\mathcal{G}(\mathbf{t}_0, \mathbf{r}_1)+\mathbf{e}_0=\mathbf{v}-\mathcal{F}(\mathbf{r}_1)-\mathcal{G}(\mathbf{t}_1, \mathbf{r}_1)-\mathbf{e}_1$

$(\mathbf{t}_0, \mathbf{e}_0)=(\mathbf{r}_0-\mathbf{t}_1, \mathcal{F}(\mathbf{r}_0)-\mathbf{e}_1).$

In questo modo, si ha che $\mathbf{s}=\mathbf{r}_0+\mathbf{r}_1$ e $\mathbf{v}=\mathcal{F}(\mathbf{r}_0+\mathbf{r}_1)$ . Notiamo che $\mathcal{G}$ è la forma polare di $\mathcal{F}$ .

Il Prover quindi genera $\mathbf{r}_0, \mathbf{t}_0\in\mathbb{F}_q^n, \mathbf{e}_0 \in\mathbb{F}_q^m$ e da essi calcola $\mathbf{r}_1, \mathbf{t}_1, \mathbf{e}_1$ secondo le relazioni descritte sopra e i commitment $c_0, c_1, c_2$ come descritto nello schema, che invia poi al Verifier. Il Verifier risponde con una Challenge che consiste in un numero tra $0$ , $1$ e $2$ scelto casualmente. A seconda del valore della Challenge, il Prover rivela una sola delle tre tuple $(\mathbf{r}_0, \mathbf{t}_1, \mathbf{e}_1)$ , $(\mathbf{r}_1, \mathbf{t}_1, \mathbf{e}_1)$ o $(\mathbf{r}_1, \mathbf{t}_0, \mathbf{e}_0)$ . Il Verifier può così verificare che la tupla ricevuta soddisfi le relazioni attraverso la verifica della correttezza dei commitment. D’altra parte, conoscendo soltanto una tupla delle tre il Verifier conosce soltanto $\mathbf{r}_0$ o $\mathbf{r}_1$ ma non entrambi, perciò non può ottenere nessuna informazione sulla chiave privata $\mathbf{s}$ .
Il Verifier restituisce $1$ se entrambe le verifiche sui due commitment passano, altrimenti $0$ .

Un tale schema a 3 passi si dice corretto in quanto, supponendo un Prover onesto, il Verifier accetterà sempre un’interazione con esso.

Schemi di identificazione a 5 passi

Nel protocollo a 5 passi di Sakumoto et al., la chiave privata e quella pubblica vengono ancora divise nel seguente modo:
$\mathbf{s}=\mathbf{r}_0+\mathbf{r}_1$ e
$\mathcal{F}(\mathbf{s})= \mathcal{F}(\mathbf{r}_0+\mathbf{r}_1)=\mathcal{F}(\mathbf{r}_0)+\mathcal{F}(\mathbf{r}_1)+\mathcal{G}(\mathbf{r}_0,\mathbf{r}_1)$ , come per il protocollo a 3 passi; ma a differenza di esso, nel protocollo a 5 passi $\mathbf{e}_1$ e $\mathbf{t}_1$ vengono calcolati secondo le relazioni $\alpha\mathbf{r}_0=\mathbf{t}_0+\mathbf{t}_1$ e $\alpha\mathcal{F}(\mathbf{r}_0)=\mathbf{e}_0+\mathbf{e}_1$ con $\alpha\in\mathbb{F}_q$ scelto dal Verifier in maniera casuale.
I due passi in più sono dati dall’invio del Verifier del messaggio contenente il valore $\alpha$ e dalla risposta del Prover contenente la coppia $(\mathbf{t}_1,\mathbf{e}_1)$ .
Quest’ultimo poi, una volta ricevuta la challenge dal Verifier, dipendentemente da essa invia la Response data da $\mathbf{r}_0$ o $\mathbf{r}_1$ .
Se $\mathbf{r}_0$ , $\mathbf{t}_0$ e $\mathbf{e}_0$ sono scelti casualmente, il Verifier non ottiene nessuna informazione sulla chiave privata $\mathbf{s}$ conoscendo soltanto uno tra $\mathbf{r}_0$ e $\mathbf{r}_1$ .
Il Verifier restituisce $1$ se la verifica passa, altrimenti $0$ .

Come per il precedente, un tale schema a 5 passi è corretto in quanto il Verifier accetta sempre un’interazione con un Prover onesto.

Un elemento importante da tenere in considerazione nello studio dei protocolli di identificazione è la probabilità che il Prover imbrogli, detta cheating probablity. La cheating probability indica la probabilità che un Prover disonesto possa convincere il Verifier di qualcosa senza conoscere il segreto. Se il Prover non conosce il segreto, è auspicabile che il Verifier accetti la Response ricevuta nel protocollo con una probabilità molto bassa. In questo caso si dice che il protocollo ha knowledge error bassa.

Il protocollo a 3-passi descritto precedentemente ha knowledge error piuttosto alta, pari a $2/3$ .

Tramite l’estensione del protocollo a 5 passi si può ottenere una knowledge error inferiore (ma comunque ancora piuttosto alta), pari a $1/2+1/2q$ dove $q$ è la dimensione del campo finito $\mathbb{F}_q$ sul quale il sistema polinomiale è definito.

MQDSS

Nel 2016 è stato presentato da Chen et al MQDSS come schema di firma multivariato che è stato successivamente sottomesso al processo di standardizzazione PQC indetto dal NIST.
MQDSS adatta lo schema di identificazione a 5 passi in una firma non interattiva utilizzando la trasformata di Fiat-Shamir. Sebbene questa trasformazione sia una tecnica ben nota per convertire gli schemi di identificazione interattivi (a 3 passi) in firme, MQDSS presenta difficoltà aggiuntive per via della sua struttura a 5 passi.

In un tipico schema di identificazione a 3 passi, la trasformazione funziona sostituendo la Challenge casuale del Verifier con un hash del Commitment precedente. In questo modo il protocollo non richiede interazione tra le parti e conserva le sue proprietà di sicurezza, purché si modelli la funzione di hash come un oracolo random ^[1]. L’ipotesi dell’oracolo casuale è fondamentale, in quanto garantisce che la Challenge sia imprevedibile e non possa essere manipolata da un avversario.

Il caso di MQDSS risulta più interessante in quanto lo schema di identificazione sottostante presenta due passaggi di Challenge-Response, rendendo la trasformazione più complessa, come descritto nel seguito.
Prima di poter applicare la trasformazione di Fiat-Shamir, è necessario amplificare la soundness del protocollo, ovvero ridurre la cheating probability di un Prover disonesto fino a rendere questa possibilità trascurabile. Tipicamente, tale risultato viene ottenuto ripetendo il protocollo in parallelo un numero sufficiente di volte, di seguito indicato con $t$ . In questo modo, un Prover disonesto dovrà convincere il Verifier contemporaneamente su numerose istanze del protocollo.

Processo di firma

Supponiamo che un utente con chiave privata $\mathbf{s}$ voglia firmare un messaggio $\mathtt{msg}$ . Lo schema MQDSS procede in questo modo:

L’utente genera il Commitment $\mathtt{cmt} \gets (\mathtt{cmt}^{(1)}, \ldots, \mathtt{cmt}^{(t)})$ , dove ogni $\mathtt{cmt}^{(i)} = (c_{0,i}, c_{1,i})$ viene ottenuto ripetendo il processo di generazione nello schema di identificazione.
La prima Challenge viene calcolata come $\mathtt{ch}_1 = (\mathtt{ch}_1^{(1)}, \ldots, \mathtt{ch}_1^{(t)}) \gets \mathsf{H}_1(\mathbf{s}, \mathtt{msg}, \mathtt{cmt})$ , dove $\mathsf{H}_1$ è una funzione di Hash crittografica.
Per ogni coppia di Commitment-Challenge $(\mathtt{cmt}^{(i)}, \mathtt{ch}_1^{(i)})$ , l’utente genera la prima risposta $\mathtt{rsp}_1^{(i)}$ come nello schema di identificazione.
La seconda Challenge viene calcolata a partire da tutti i messaggi precedenti come $\mathtt{ch}_2 = (\mathtt{ch}_2^{(1)}, \ldots, \mathtt{ch}_2^{(t)}) \gets \mathsf{H}_2(\mathbf{s}, \mathtt{msg}, \mathtt{cmt}, \mathtt{ch}_1, \mathtt{rsp}_1)$ , dove $\mathsf{H}_2$ è una funzione di Hash crittografica.
Infine, la firma è ottenuta calcolando per ogni esecuzione la seconda risposta $\mathtt{rsp}_2^{(i)}$ come nel protocollo di identificazione. La firma è quindi data dal Commitment e dalle risposte: $\sigma = (\mathtt{cmt}, \mathtt{rsp}_1, \mathtt{rsp}_2)$ .

Si noti che non è necessario aggiungere le Challenge nella firma in quanto il Verifier potrà ricostruirle e validarle nel processo di verifica. In particolare, il Verifier può calcolare le challenge usando le funzioni di hash come nel processo di firma. A partire da queste, può verificare la correttezza delle risposte per ogni esecuzione del protocollo.

Considerazioni di sicurezza

Nell’applicazione di Fiat-Shamir a un protocollo a 5 passi, la prima considerazione riguarda la generazione delle Challenge, per le quali è necessario incorporare tutte le informazioni del protocollo disponibili in quel momento. Per questo motivo, l’hash della seconda Challenge non include solo il Commitment, ma anche la prima Challenge e la relativa risposta. Senza questa accortezza, un attaccante potrebbe essere in grado di eseguire più secondi round per un singolo primo round, trovando potenzialmente una combinazione che porti a una firma falsificata.

Una seconda importante considerazione di sicurezza è relativa al legame tra lo schema di firma e il segreto posseduto dal Prover nello schema di identificazione. Per dimostrare la sicurezza dello schema è infatti necessario provare che le firme valide prodotte da un eventuale avversario possono essere utilizzare per rompere l’assunto di sicurezza sottostante (in questo caso, il problema MQ). La tecnica standard consiste nell’utilizzare il “riavvolgimento”: il processo dell’avversario viene eseguito più volte con Challenge diverse ma con la stesso Commitment iniziale. Tuttavia, con protocolli a 5 passi, dobbiamo fare più attenzione a come riavvolgiamo.
In uno schema a 3 passi, abbiamo bisogno di due firme valide con Challenge diverse relative allo stesso Commitment per estrarre una soluzione al problema difficile sottostante. Nella struttura a 5 passaggi di MQDSS, abbiamo bisogno di più firme perché abbiamo due Challenge indipendenti. La prova di sicurezza deve quindi tenere conto di questa strategia di riavvolgimento più complessa.

MQDSS nella competizione del NIST

MQDSS è stato presentato al primo processo di standardizzazione PQC del NIST come candidato per le firme digitali. Lo schema si è rivelato inizialmente promettente grazie alla sua struttura e alle sue solide basi teoriche che ne riconducono la sicurezza direttamente al problema MQ.

Tuttavia, MQDSS ha successivamente rivelato limiti significativi che hanno portato nel 2020 alla sua eliminazione, al termine del secondo round. Lo svantaggio più rilevante dello schema è rappresentato dalle sue caratteristiche prestazionali: le firme hanno dimensioni significative, nell’ordine delle decine di kilobyte. Inoltre le operazioni di firma e verifica sono computazionalmente costose e la generazione delle firme risulta più lenta rispetto agli schemi concorrenti.

Nonostante le caratteristiche prestazionali limitate, gli aspetti di design e sicurezza dello schema avevano inizialmente determinato un interesse per MQDSS, soprattutto per quanto riguarda scenari applicativi conservativi.
Il colpo decisivo a MQDSS è arrivato invece da un attacco originale pubblicato da Kales e Zaverucha nel 2020. Questo attacco sfruttava una sottile vulnerabilità nell’applicazione della trasformata di Fiat-Shamir ai protocolli a 5 passi. La strategia proposta si basa su un’osservazione fondamentale: la fase di ricerca di risposte valide per la seconda Challenge può avvenire senza modificare il Commitment e la prima Challenge. In questo modo l’attacco può essere diviso in due fasi e ottimizzato rispetto al numero di round.

Sebbene l’attacco non coinvolgesse il problema matematico sottostante o le dimostrazioni di sicurezza teorica, per recuperare la sicurezza persa tramite nuovi parametri sarebbero state necessarie il 40% di iterazioni in più e chiavi più grandi del 50%.
Questa combinazione di fattori ha fatto sì che MQDSS non venisse selezionato per il terzo turno della competizione.

Ad oggi, sebbene nessuno schema multivariato basato su schemi di identificazione sia presente in un processo di standardizzazione, vi sono stati numerosi sviluppi teorici che hanno reso questo approccio nuovamente competitivo. In particolare, le tecniche legate al paradigma MPC-in-the-head sono facilmente applicabili al protocollo di Sakumoto et al., con interessanti risultati in termini di dimensione delle firme e di prestazioni.

^[1]Una funzione casuale che risponde ad ogni query con un output completamente random. Tipicamente sostituita nella pratica da una funzione di Hash.

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.

Edoardo Signorini, Cryptography Specialist in Telsy, dove dal 2020 fa parte del Gruppo di Ricerca in Crittografia. Ha conseguito il dottorato in Matematica Pura e Applicata presso il Politecnico di Torino nel 2024 con una tesi sull’aggregazione di firme digitali post-quantum. La sua attività si concentra sulla ricerca nell’ambito della Post-Quantum Cryptography e sull’analisi e lo sviluppo di protocolli crittografici.