UOV e le sue varianti: firme digitali basate su sistemi multivariati

24 Nov

Nella precedente esplorazione della crittografia multivariata, si è esaminato come i sistemi di equazioni polinomiali su campi finiti possano costituire la base di schemi crittografici resistenti al computer quantistico. Lo schema UOV (Unbalanced Oil and Vinegar) rappresenta in questo contesto una delle proposte più solide ed efficienti per la costruzione di firme digitali.

Partendo dai concetti fondamentali precedentemente discussi — in particolare la difficoltà computazionale della risoluzione di sistemi di equazioni quadratici multivariati (MQ) — UOV si colloca tra le costruzioni bipolari, introducendo un’elegante costruzione della mappa centrale.

Sviluppato originariamente da Jacques Patarin nel 1997 e perfezionato nel 1999 a seguito di un attacco di Kipnis e Shamir, UOV estende la costruzione di base di Oil and Vinegar introducendo un’asimmetria nelle variabili della mappa centrale, da cui il termine “sbilanciato”. Questa asimmetria si è rivelata fondamentale per evitare gli attacchi algebrici che avevano compromesso la versione originale bilanciata.

Unbalanced Oil and Vinegar

Le costruzioni OV hanno una caratteristica principale che riguarda la particolare forma della mappa centrale $\mathcal{F} = (f^{(1)}, \ldots, f^{(m)}) \colon \mathbb{F}_q^n \to \mathbb{F}_q^m$ , dove le componenti $f^{(k)}$ sono polinomi della forma

$\begin{equation*} f^{(k)}(\mathbf{x}) = \sum_{i=1}^{n-m} \sum_{j=1}^{n-m} \alpha_{i,j}^{(k)}x_i x_j + \sum_{i=1}^{n-m} \sum_{j=n-m+1}^{n} \beta_{i,j}^{(k)}x_i x_j + \sum_{i=1}^{n} \gamma_{i}^{(k)}x_i + \delta^{(k)}. \end{equation*}$

L’aspetto peculiare di questi polinomi è che non presentano termini quadratici nelle ultime $m$ variabili. Questa proprietà rende la mappa centrale $\mathcal{F}$ facilmente invertibile, permettendone l’uso nella costruzione bipolare. Infatti, fissato casualmente il valore delle prime $n-m$ variabili, ciò che rimane è un sistema lineare di $m$ equazioni in $m$ variabili, per il quale una soluzione tipicamente esiste ed è facilmente calcolabile con il metodo di eliminazione di Gauss. Nel caso poco probabile in cui il sistema non avesse soluzioni, basterebbe ripetere il procedimento rifissando casualmente le prime $n-m$ variabili a valori diversi da quelli precedenti.

Patarin chiamò questo schema Oil and Vinegar per descrivere il comportamento delle variabili coinvolte. Infatti, all’interno dei polinomi $f^{(1)}, \ldots, f^{(m)}$ , le prime $n-m$ variabili, chiamate vinegar (aceto), non vengono mai mischiate completamente con le ultime $m$ variabili chiamate oil (olio). Questo è essenzialmente quello che accade anche in cucina, dove l’olio e l’aceto non si mescolano in modo omogeneo.

Generalmente, nelle applicazioni, la mappa centrale $\mathcal{F}$ viene scelta a componenti omogenee, cioè i polinomi $f^{(k)}$ presentano i coefficienti $\gamma_{i}^{(k)}=\delta^{(k)}=0$ . Nel seguito sarà adottata la medesima convenzione.

Inizialmente, Patarin propose l’utilizzo di una mappa centrale con $n=2m$ e quindi con lo stesso numero di variabili oil e vinegar. Tuttavia, nel 1999, Kipnis e Shamir evidenziarono una vulnerabilità derivata da questa scelta. Di conseguenza, le versioni moderne dello schema utilizzano un numero di variabili vinegar maggiore del numero di variabili oil, cioè $n > 2m$ , da cui il nome “Unbalanced” Oil and Vinegar.

Descrizione moderna di UOV

Recentemente, Beullens ha proposto una descrizione alternativa, ma equivalente, dello schema UOV. Questa nuova descrizione è stata introdotta a seguito di nuovi tentativi di crittanalisi ed è risultata fondamentale per realizzare l’attacco allo schema Rainbow, uno dei partecipanti alla competizione PQC indetta dal NIST. La descrizione di Beullens, invece che utilizzare il concetto di mappa centrale $\mathcal{F}$ facilmente invertibile, basa la costruzione della chiave privata su determinate proprietà della chiave pubblica $\mathcal{P}$ .

Più nel dettaglio, la mappa $\mathcal{P}$ può essere invertita conoscendo un insieme $\mathcal{O} \subset \mathbb{F}_q^n$ di dimensione $m$ sul quale $\mathcal{P}$ si annulla, cioè tale per cui

$\mathcal{P}(\mathbf{o})=\mathbf{0} \ \mbox{per ogni} \ \mathbf{o} \in \mathcal{O}.$

Conseguentemente, mentre la chiave pubblica rimane la mappa $\mathcal{P}$ , la chiave privata non è altro che una base dello spazio $\mathcal{O}$ .

Per comprendere come la conoscenza dello spazio $\mathcal{O}$ permetta di trovare una soluzione al sistema $\mathcal{P}(\mathbf{x})=\mathbf{t}$ bisogna introdurre il concetto di forma polare. Per un polinomio quadratico omogeneo multivariato $f: \mathbb{F}_q^n \to \mathbb{F}_q$ , la sua forma polare è un polinomio multivariato $\Bar{f}\colon\mathbb{F}_q^n \times \mathbb{F}_q^n \to \mathbb{F}_q$ definito come

$\Bar{f}(\mathbf{x}, \mathbf{y}) := f(\mathbf{x} + \mathbf{y}) - f(\mathbf{x}) -f(\mathbf{y}).$

La forma polare di una mappa multivariata quadratica a componenti omogenee $\mathcal{F} = (f^{(1)}, \ldots, f^{(m)}) \colon \mathbb{F}_q^n \to \mathbb{F}_q^m$ è una mappa multivariata quadratica $\mathcal{\Bar{F}} = (\Bar{f}^{(1)}, \ldots, \Bar{f}^{(m)}) \colon \mathbb{F}_q^n \times \mathbb{F}_q^n \to \mathbb{F}_q^m$ le cui componenti sono la forma polare delle componenti della mappa $\mathcal{F}$ di partenza.

Una proprietà estremamente importante della forme polari di una mappa quadratica è quella di essere bilineare, cioè lineare rispetto a entrambi gli input.

Conoscendo la mappa $\mathcal{P}$ e uno spazio $\mathcal{O}$ di dimensione $m$ sulla quale $\mathcal{P}$ si annulla, una soluzione di $\mathcal{P}(\mathbf{x})=\mathbf{t}$ può essere trovata nel seguente modo. Come primo passo si seleziona casualmente un elemento $\mathbf{v}$ di $\mathbb{F}_q^n$ . A questo punto si prova a trovare una soluzione nella forma $\mathbf{v}+\mathbf{o}$ per un certo $\mathbf{o} \in \mathcal{O}$ . Questa strategia permette di trasformare il problema di trovare un elemento $\mathbf{x}$ tale per cui $\mathcal{P}(\mathbf{x})=\mathbf{t}$ nel problema di trovare un elemento $\mathbf{o} \in \mathcal{O}$ tale per cui $\mathcal{P}(\mathbf{v}+\mathbf{o})=\mathbf{t}$ . Utilizzando il concetto di forme polari, si può scomporre l’ultimo sistema nel seguente modo

$\mathcal{P}(\mathbf{v}+\mathbf{o}) = \mathcal{P}(\mathbf{v}) + \mathcal{P}(\mathbf{o}) + \mathcal{\Bar{P}}(\mathbf{v},\mathbf{o})=\mathbf{t}.$

Si noti che $\mathcal{P}(\mathbf{v})$ è un elemento fissato e noto, $\mathcal{P}(\mathbf{o})= \mathbf{0}$ per come $\mathcal{O}$ è stato definito e, $\mathcal{\Bar{P}}(\mathbf{v},\mathbf{o})$ è una mappa lineare in $\mathbf{o}$ poiché $\mathbf{v}$ è un elemento fissato e le forme polari sono bilineari. Conseguentemente, la risoluzione del sistema $\mathcal{P}(\mathbf{x})=\mathbf{t}$ si trasforma nella ricerca di una soluzione di un sistema lineare. Con buona probabilità il sistema ottenuto ha un’unica soluzione e, in questo caso, essa può essere ottenuta mediante il metodo di eliminazione di Gauss. Se così non fosse basta ripetere il procedimento pescando un nuovo valore per $\mathbf{v}$ diverso da quello fissato precedentemente.

Rainbow e MAYO

La fiducia nella sicurezza dello schema UOV ha ispirato numerosi ricercatori a proporre varianti con l’obiettivo di ridurne le dimensioni delle chiavi e migliorarne l’utilizzabilità pratica.

Una nota variante di UOV è lo schema di firma Rainbow, in cui vengono combinati più livelli UOV ottenendo chiavi più piccole e prestazioni migliori.
A differenza di UOV, in cui la chiave privata è rappresentata da un singolo sottospazio, la chiave privata di Rainbow è descritta da tre sottospazi distinti $\mathcal{O}_1, \mathcal{O}_2, \mathcal{W}$ , che soddisfano le sequenti proprietà:

$\mathcal{O}_2\subset\mathcal{O}_1\subset\mathbb{F}_q^n$ e $\mathcal{W}\subset\mathbb{F}_q^m$ ,
$\dim(\mathcal{O}_2)=\dim(\mathcal{W})$ , $\dim(\mathcal{O}_1)=m$ ,
per ogni $\mathbf{o}_2\in\mathcal{O}_2$ e $\mathbf{x}\in\mathbb{F}_q^n$ si ha $\mathcal{P}(\mathbf{o}_2)=0$ e $\mathcal{P}'(\mathbf{x},\mathbf{o}_2)\in\mathcal{W}$ ,
per ogni $\mathbf{o}_1\in\mathcal{O}_1$ si ha $\mathcal{P}(\mathbf{o}_1)\in\mathcal{W}.$

Questa struttura a più livelli — riassunta nel diagramma seguente — conferisce a Rainbow una trapdoor più complessa, che ha suscitato un forte interesse da parte della comunità crittografica e ha portato a importanti progressi nella crittanalisi di questi schemi.

Durante il terzo round della competizione del NIST, Rainbow è stato tuttavia ritirato in seguito alla scoperta di un attacco da parte di Beullens. Sebbene sia possibile mitigare tale attacco aumentando le dimensioni dei parametri, lo schema risultante non sarebbe comunque realmente utilizzabile a causa della dimensione eccessiva delle chiavi e di una minore efficienza rispetto alla versione standard di UOV.

Nonostante i tentativi di miglioramento, UOV rimane tuttora la proposta multivariata non strutturata più solida ed efficiente per la costruzione di firme digitali. La vulnerabilità individuata in Rainbow, infatti, non intacca la sicurezza dello schema UOV originale, ma fornisce al contrario nuovi indizi sulla robustezza dell’assunzione sottostante.

La possibilità di ridurre la dimensione delle chiavi di UOV introducendo maggiore struttura ha continuato a essere analizzata in schemi successivi.
Nel 2017 è stata proposta la variante Lifted UOV (LUOV) che ha partecipato al primo processo del NIST fino a quando, durante il secondo round, la struttura di lifting sulla quale è basata si è rivelata insicura.
Successivamente, nel 2021, lo stesso Beullens ha suscitato nuovo interesse in questo approccio con lo schema MAYO.
L’idea alla base di MAYO è di consentire la scelta di uno spazio segreto “Oil” con una dimensione $o$ più piccola rispetto a $m$ , in modo da ottenere chiavi di dimensioni ridotte rispetto allo schema UOV originale.

Per avere tale risultato, sarebbe sufficiente che il processo di generazione della firma preveda di risolvere un sistema lineare di $m$ equazioni in $o < m$ variabili. Ma visto che un tale sistema con alta probabilità non ammette una soluzione, un suo utilizzo causerebbe il fallimento dell’algoritmo di generazione della firma.

MAYO affronta questo problema proponendo una “whipping transformation” (trasformazione a frusta, da cui prende il nome lo schema) che estende la mappa quadratica $\mathcal{P}\colon\mathbb{F}_q^n\to \mathbb{F}_q^m$ in una mappa $\mathcal{P}^*\colon\mathbb{F}_q^{kn}\to \mathbb{F}_q^m$ , con $k$ intero. La mappa estesa $\mathcal{P}^*$ è costruita in modo che si annulli su spazio Oil, a sua volta esteso, di dimensione $ko \ge m$ , consentendo così la risoluzione del sistema lineare necessario per la firma.

Più precisamente, dopo aver scelto in modo casuale un sottospazio Oil $\mathcal{O}\subset \mathbb{F}^n$ di dimensione $o < m$ , viene costruita una mappa pubblica UOV $\mathcal{P}\colon\mathbb{F}_q^n\to \mathbb{F}_q^m$ tale che $\mathcal{P}(\mathcal{O})=0$ . In questo modo a partire da $\mathcal{P}$ è sempre possibile derivare una mappa $\mathcal{P}^*$ che si annulla su $\mathcal{O}^k\subset \mathbb{F}_q^{kn}$ .
Questo procedimento permette di trasformare una mappa UOV con $o < m$ , inutilizzabile per creare direttamente schemi di firma, in una mappa utile che si annulla su uno spazio di dimensione almeno $m$ .

UOV nella competizione del NIST

La prima competizione per la selezione di schemi post-quantum, indetta dal NIST nel 2017, ha visto la partecipazione di due schemi basati su UOV: LUOV e Rainbow. Sebbene entrambi questi schemi si siano rivelati parzialmente insicuri e non siano stati selezionati per la standardizzazione, la loro analisi è stata fondamentale per il design e la definizione delle proposte più recenti.

Nel 2023, il NIST ha avviato una nuova competizione dedicata alle firme post-quantum, con lo scopo di diversificare le assunzioni di sicurezza. Delle 40 sottomissioni accettate al primo round, 11 sono basate su assunzioni multivariate. Tra queste ultime, vi sono 7 proposte direttamente basate o derivate da UOV.
Alcune tra le nuove costruzioni presentano solo piccole variazioni rispetto allo schema originale (ad esempio, Provable e Triangular UOV).
Altre, come MAYO, SNOVA e QR-UOV, introducono modifiche sostanziali volte a migliorare l’efficienza e la compattezza della costruzione originale.
Nell’ottobre 2024, a seguito del passaggio al secondo round della competizione, il NIST ha selezionato la versione originale di UOV e tutte le varianti strutturate per una nuova fase di analisi più mirata.

Generalmente, UOV e le sue varianti più prossime sono considerati schemi multivariati non strutturati, caratterizzati da una buona robustezza ed efficienza ma con chiavi pubbliche di elevate dimensioni. L’introduzione di maggiore struttura all’interno del problema permette di ridurre sensibilmente la dimensione delle chiavi. D’altra parte, tali approcci richiedono particolare attenzione, in quanto questa stessa struttura potrebbe essere sfruttata per nuovi attacchi crittanalitici, come è accaduto nel caso di Rainbow.
Attualmente, per nessuna delle nuove proposte sottomesse al NIST sono state evidenziate delle vulnerabilità.

UOV e le sue varianti firme digitali basate su sistemi multivariati sig_plot — Nella figura è riportato un grafico della dimensione di firme e chiavi pubbliche, mettendo a confronto gli schemi basati su UOV al variare del parametro di sicurezza. Per semplificare il confronto, sono stati utilizzati simboli diversi per le varianti strutturate e quelle non strutturate.

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 a ottobre 2024 è stata stagista in Telsy nel Gruppo di Ricerca in Crittografia.

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.