La matematica dietro la PQC: i sistemi multivariati

14 Ott 2024

Introduzione

La crittografia multivariata si aggiunge ai crittosistemi basati su reticoli, codici e funzioni di hash come una delle principali classi di schemi crittografici resistenti agli attacchi quantistici.
Tali schemi sono basati sulla difficoltà di risolvere sistemi di equazioni a più variabili (anche detti multivariati) definiti su un campo finito.

Questa branca della crittografia asimmetrica emerse alla fine degli anni ’80 con lo schema ideato da Matsumoto e Imai (1988). La successiva crittoanalisi dello schema, proposta da Patarin nel 1995, stimolò lo sviluppo di nuovi paradigmi, che oggi costituiscono la base di numerosi schemi di firma digitale.

Sebbene nessuno degli schemi standardizzati dal NIST^[1] sia basato sui sistemi multivariati, negli ultimi anni il lavoro della comunità crittografica ha portato a importanti progressi in questo campo. Infatti, oggi la crittografia multivariata rappresenta la maggioranza degli schemi proposti nella recente call aggiuntiva del NIST per la standardizzazione di nuove firme digitali.

Sistemi multivariati

Un polinomio multivariato è una somma di monomi in più variabili. Formalmente può essere descritto nel seguente modo
$p(x_1,x_2,\dots,x_n) = \sum_{i=1}^s c_i \cdot x_1^{\alpha_{i,1}} x_2^{\alpha_{i,2}} \cdots x_n^{\alpha_{i,n}}$
con $s$ un numero intero positivo, i coefficienti $c_i$ elementi di un campo $\mathbb{K}$ e gli esponenti $\alpha_{i,j}$ dei numeri naturali.

Il grado del polinomio viene definito come il massimo grado dei monomi di cui è costituito. Ricordando che il grado di un monomio è la somma degli esponenti delle variabili di cui è composto si ha che
$grado(p) = \max \limits_{i=1,\dots,s} \sum_{j=1}^n \alpha_{i,j}$
Si noti infine come un polinomio multivariato in $n$ variabili con coefficienti su un campo $\mathbb{K}$ sia una mappa $p : \mathbb{K}^n \longrightarrow \mathbb{K}$ .

I sistemi multivariati sono dei sistemi composti da $m$ polinomi multivariati in $n$ variabili rappresentabili nel seguente modo
$\begin{cases} p^{(1)}(x_1,x_2,\dots,x_n) = \sum_{i=1}^{s_1} c_i^{(1)} \cdot x_1^{\alpha_{i,1}} x_2^{\alpha_{i,2}} \cdots x_n^{\alpha_{i,n}}\\ p^{(2)}(x_1,x_2,\dots,x_n) = \sum_{i=1}^{s_2} c_i^{(2)} \cdot x_1^{\alpha_{i,1}} x_2^{\alpha_{i,2}} \cdots x_n^{\alpha_{i,n}} \\ \vdots \\ p^{(m)}(x_1,x_2,\dots,x_n) = \sum_{i=1}^{s_m} c_i^{(m)} \cdot x_1^{\alpha_{i,1}} x_2^{\alpha_{i,2}} \cdots x_n^{\alpha_{i,n}} \end{cases}$
Conseguentemente queste strutture sono delle mappe $\mathcal{P}=(p^{(1)},p^{(2)},\dots, p^{(m)}):\mathbb{K}^n \longrightarrow \mathbb{K}^m$ di $m$ equazioni $p^{(i)}:\mathbb{K}^n \longrightarrow \mathbb{K}$ in $n$ incognite.

Problemi computazionali

Il principale problema matematico alla base della sicurezza degli schemi di crittografia multivariata è il problema della risoluzione di sistemi polinomiali, che consiste nella difficoltà di risolvere un sistema di equazioni multivariate su un campo finito.

Più formalmente, dato un sistema multivariato $\mathcal{P}:\mathbb{F}_q^n \longrightarrow \mathbb{F}_q^m$ con $m$ equazioni e $n$ incognite definito sul campo finito $\mathbb{F}_q$ di $q$ elementi, il problema consiste nel trovare un elemento $\bar{\bm{x}}=(\bar{x}_1,\bar{x}_2,\dots,\bar{x}_n)$ di $\mathbb{F}_q^n$ tale per cui $\mathcal{P}(\bar{\bm{x}}) = \mathbf{0}$ . Equivalentemente, tale per cui
$\begin{cases}p^{(1)}(\bar{\bm{x}}) = 0 \\ p^{(2)}(\bar{\bm{x}}) = 0\\ \vdots \\ p^{(m)}(\bar{\bm{x}}) = 0 \end{cases}$

In crittografia, questo problema viene tipicamente ristretto alla risoluzione di sistemi polinomiali quadratici, ovvero di grado 2, prendendo il nome di Multivariate Quadratic (MQ) Problem.
Contrariamente a quanto si potrebbe intuire, la versione generale del problema, per polinomi di grado maggiore, non si è dimostrata più complessa di quella MQ. Infatti, il problema MQ, come la sua versione generale, appartiene alla classe di problemi molto difficili detti NP-Completi^[2].

Dei parametri molto importanti all’interno di questo problema sono $m$ (il numero di equazioni) e $n$ (il numero di variabili). Le istanze più difficili si ottengono con valori di $m$ e $n$ simili. Se la differenza di valore tra $m$ e $n$ è molto grande, esistono degli algoritmi che riescono a risolvere il problema efficientemente.

Il problema MQ spesso è utilizzato in crittografia assieme ad un secondo problema chiamato Problema dell’Isomorfismo dei Polinomi (IP).
Quest’ultimo presenta molteplici varianti, ma nella pratica ci si riduce tipicamente alla sua forma estesa (EIP). Intuitivamente, questo problema chiede di trovare due mappe affini che trasformino un sistema multivariato in un altro.

Più formalmente, dati due sistemi multivariati $\mathcal{A}, \mathcal{B} : \mathbb{F}_q^n \longrightarrow \mathbb{F}_q^m$ , il problema EIP consiste nel trovare due mappe affini $S$ e $T$ tali che $\mathcal{A}$ possa essere scomposta nel seguente modo
$\mathcal{A} = S \circ \mathcal{B} \circ T$
A differenza del problema MQ, non si sa molto riguardo alla difficoltà del problema IP e delle sue varianti.

Attualmente, gli algoritmi più efficaci per la risoluzione del problema MQ si basano su tecniche algebriche che utilizzano le basi di Gröbner, particolari strutture algebriche introdotte da Buchberger nel 1965 che permettono di trovare le soluzioni di un sistema dandone una rappresentazione più semplice. Il calcolo di una base di Gröbner può essere intuitivamente visto come un’estensione dell’eliminazione gaussiana al caso multivariato.

Tuttavia, la complessità maggiore di questi algoritmi risiede proprio nel calcolo della base di Gröbner, il cui costo computazionale aumenta rapidamente con la dimensione del problema.

Questo rende tali approcci impraticabili per le istanze di dimensioni adatte alle applicazioni crittografiche. Tra gli algoritmi che seguono questo approccio ci sono l’algoritmo di Buchberger e i suoi miglioramenti, come F4 e F5.

Un altro algoritmo noto per la risoluzione del problema MQ è la tecnica di linearizzazione XL (eXtended Linearization) che, con le sue varianti più efficienti, permette di trasformare un sistema multivariato quadratico in uno lineare con un numero maggiore di variabili.

Infine, esistono appocci ibridi che massimizzano l’efficacia di una certa combinazione di algoritmi su determinate istanze, ad esempio combinando le tecniche di calcolo della base di Gröbner e algoritmo XL, oppure applicando una delle due dopo la tecnica della ricerca esaustiva, che fissa casualmente il valore di alcune variabili.

Storia della crittografia multivariata

Lo sviluppo della crittografia multivariata risale alla fine degli anni ’80, nel contesto dei rapidi progressi nel campo della crittografia a chiave pubblica seguiti alle costruzioni di Diffie-Hellman e RSA.
Un contributo fondamentale a questa branca venne dato nel 1988 da Matsumoto e Imai (MI), con l’introduzione dell’uso di sistemi multivariati nella cifratura a chiave pubblica.

Lo schema MI si basa su una tecnica innovativa, ancora oggi alla base di molti sistemi multivariati e più generalmente riconducibile alla classe delle costruzioni bipolari.
Questo approccio propone l’utilizzo di una mappa quadratica, detta mappa centrale, appartenente a particolari classi di mappe facili da invertire. Tale mappa viene poi opportunamente mascherata con l’obiettivo di ottenere un’altra mappa quadratica all’apparenza casuale, per la quale non esistono approcci più efficienti di quelli generalmente applicabili al problema MQ.

Più precisamente, in queste costruzioni, la chiave privata è costituita dalla mappa centrale $\mathcal{F}\colon \mathbb{F}_q^n \to \mathbb{F}_q^m$ e da due mappe affini $T\colon \mathbb{F}_q^n \to \mathbb{F}_q^n$ e $S \colon \mathbb{F}_q^m \to \mathbb{F}_q^m$ . La chiave pubblica è invece la mappa quadratica $\mathcal{P} = S \circ \mathcal{F} \circ T$ ottenuta dalla combinazione delle mappe segrete.
Talvolta la seconda mappa affine $S$ non è necessaria e la chiave pubblica è semplicemente ottenuta come $\mathcal{F} \circ T$ .

Le costruzioni bipolari sono potenzialmente adattabili sia nel contesto della cifratura a chiave pubblica che in quello delle firme digitali.
Nel caso della cifratura, dato un messaggio $\bm{v} \in \mathbb{F}_q^n$ , il mittente calcolerà il ciphertext $\bm{t} = \mathcal{P}(\bm{v})$ . Per decifrare, il destinatario utilizzerà la decomposizione della chiave pubblica tramite la privata per trovare una preimmagine, calcolando $\bm{v} = T^{-1}(\mathcal{F}^{-1}(S^{-1}(\bm{t})))$ .

In questo caso, scegliendo $m \ge n$ (dove $m$ è la dimensione dello spazio di arrivo e $n$ quella dello spazio di partenza), si garantisce che il valore $\bm{v}$ calcolato dal destinatario sia unico e coincida con il messaggio originale. Il calcolo dell’inversa tramite $T$ e $S$ è semplice poiché utilizza mappe lineari, mentre quello tramite la mappa quadratica $\mathcal{F}$ lo è per via della struttura particolare della mappa centrale.

Nel caso delle firme digitali, il processo è analogo: per firmare un messaggio $m$ , il firmatario utilizza una funzione di hash $\mathsf{H}\colon \{0,1\}^* \to \mathbb{F}_q^m$ per calcolare il valore $\bm{t} = \mathsf{H}(m)$ e la firma $\bm{\sigma} = T^{-1}(\mathcal{F}^{-1}(S^{-1}(\bm{t})))$ . Per verificare la firma, è sufficiente controllare che $\mathcal{P}(\bm{\sigma}) = \mathsf{H}(m)$ . In questo caso, è opportuno scegliere $n \ge m$ , in modo che una preimmagine per $\bm{t}$ esista con elevata probabilità.

Le costruzioni bipolari sono intuitive ed efficaci, e risultano preponderanti nel design di schemi multivariati. D’altra parte, tali costruzioni si basano sull’utilizzo di funzioni trapdoor e la loro sicurezza non è pertanto interamente riconducibile al problema MQ. Un attaccante potrebbe infatti tentare sia di invertire la mappa pubblica $\mathcal{P}$ , trattandola come una mappa random, sia sfruttare la particolare forma della mappa centrale, cercando una soluzione del problema IP esteso.

L’assenza di risultati definitivi sulla complessità del problema IP impedisce che la sicurezza di questi schemi possa essere ridotta completamente a problemi difficili. Storicamente, vi sono infatti numerosi esempi in cui la decomposizione della mappa pubblica $\mathcal{P}$ è risultata particolarmente facile per determinate classi di mappe centrali.

Il primo importante attacco riguardò proprio lo schema proposto da Matsumoto e Imai, il quale venne compromesso alla fine degli anni ’90 da Jacques Patarin. Quest’ultimo propose successivamente diversi schemi e migliorie della costruzione MI, in particolare con gli schemi Hidden Field Equation (HFE) e Oil and Vinegar (OV).

Poco dopo la presentazione di OV, Kipnis e Shamir individuarono una vulnerabilità nello schema e proposero insieme a Patarin una versione rivisitata, nota come Unbalanced Oil and Vinegar (UOV). UOV è inoltre alla base dello schema di firma Rainbow, proposto nel 2005 e noto per aver raggiunto il terzo round della competizione del NIST ed essere stato completamente rotto nel 2022 da Ward Beullens.

Nel contesto delle firme digitali, è possibile adottare una costruzione alternativa che permette di ridurre interamente la sicurezza dello schema al problema MQ.
Tale approccio richiede la definizione di un protocollo di identificazione, dal quale è possibile ricavare uno schema di firma tramite l’applicazione della trasformata di Fiat-Shamir. Questa tecnica non è esclusiva dell’ambito multivariato ed è ampiamente utilizzata nella costruzione di firme Post-Quantum (si veda ad esempio lo schema Dilithium).

Il primo protocollo di identificazione basato sul problema MQ è stato proposto in un articolo del 2011 da Sakumoto et al. Su questa costruzione si basano tutti gli schemi di firma Fiat-Shamir multivariati.

I sistemi multivariati nella PQC

Sebbene i sistemi multivariati si prestino sia alla costruzione di firme digitali che di schemi di cifratura, per questi ultimi si è registrato nel tempo minor interesse. La difficoltà nella costruzione di schemi di cifratura multivariati e la poca competitività in questa classe di schemi ne hanno decretato infatti un progressivo abbandono da parte della comunità scientifica.

Per quanto riguarda le firme digitali, invece, diversi schemi multivariati sono stati oggetto di studi e analisi durante il processo di standardizzazione guidato dal NIST. Al terzo round della competizione erano presenti due schemi multivariati: Rainbow, firma basata su UOV e candidata alla standardizzazione (successivamente scartata a causa di un attacco), e GeMSS, un candidato alternativo basato su HFE (che è stato escluso a favore dello schema basato sulle funzioni di hash SPHINCS+).
Inoltre, lo schema di firma MQDSS, basato sul protocollo di identificazione di Sakumoto et al., ha raggiunto il secondo round della competizione, durante il quale ha sofferto un attacco che lo ha reso poco competitivo rispetto agli altri candidati.

Nonostante gli scarsi risultati ottenuti nella prima competizione del NIST, negli ultimi anni vi è stato un notevole lavoro da parte della comunità crittografica che ha portato a importanti sviluppi nel design e nelle analisi di sicurezza degli schemi multivariati. Infatti, questa tipologia di schemi è la più rappresentata nella recente call aggiuntiva del NIST dedicata esclusivamente alle firme, con 11 sottomissioni al primo round, di cui 7 basate su UOV, al quale sarà dedicato il prossimo articolo di questa rubrica.

In conclusione, le firme multivariate appaiono già oggi come una scelta valida in numerosi scenari, con interessanti proposte in corso di validazione per un uso generico.

^[1]CRYSTALS-Kyber, CRYSTALS-Dilithium e SPHINCS+.
^[2]La classe NP racchiude problemi per cui è molto difficile trovare una soluzione ma è facile verificare una soluzione proposta. I problemi NP-Completi sono i più generali e difficili tra quelli NP. Infatti, un algoritmo che risolve un problema NP-Completo potrebbe essere adattato per risolvere qualsiasi altro problema NP.

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.

Federica Zanetti, laureata triennale in Matematica presso l’Università degli Studi di Trento, dove attualmente è laureanda magistrale con specializzazione in Crittografia. Da giugno 2024 stagista in Telsy nel Gruppo di Ricerca in Crittografia.

Edoardo Signorini, laureato in Matematica con curriculum in crittografia presso l’Università di Trento, ha svolto nel 2020 la Tesi Magistrale nell’ambito della Post-Quantum Cryptography (PQC) presso Telsy. Attualmente ricopre il ruolo di crittografo all’interno del gruppo di ricerca di Telsy e svolge un Dottorato di ricerca industriale in Matematica Pura e Applicata presso il Politecnico di Torino. La sua attività si concentra sulla ricerca in ambito PQC e sull’analisi e lo sviluppo di protocolli crittografici.