CROSS: Firma Digitale basata sui codici

15 Apr 2026

Introduzione

Nel 2022 il NIST ha avviato un secondo processo di standardizzazione per schemi di firma digitale post-quantum, con l’obiettivo di diversificare le fondamenta matematiche del portafoglio crittografico rispetto agli schemi già selezionati per la standardizzazione, ovvero ML-DSA (CRYSTALS-Dilithium), SLH-DSA (SPHINCS+) e FALCON. Tra gli schemi proposti, hanno spiccato alternative fondate su isogenie, sistemi multivariati e codici lineari.

In questo contesto, nell’ottobre 2024 il NIST ha annunciato i 14 candidati selezionati per il secondo round del processo. Tra questi figura CROSS (Codes and Restricted Objects Signature Scheme)¹, uno schema di firma digitale la cui sicurezza si fonda su una variante strutturata del classico problema del Syndrome Decoding (SDP) applicato ai codici lineari su campi finiti. Lo schema è stato progettato da un team internazionale di ricercatori, con una significativa componente italiana, tra cui l’autore di questo articolo.

La crittografia basata su codici ha una lunga tradizione nella costruzione di schemi di cifratura e di incapsulamento di chiave (si vedano Classic McEliece e HQC), ma la progettazione di firme digitali efficienti a partire dal SDP si è rivelata storicamente più difficile. Nel contesto dei codici, l’approccio impiegato tipicamente per la costruzione di firme è quello di definire un protocollo di identificazione e successivamente applicare la trasformata di Fiat-Shamir. Questo paradigma è analogo a quanto si ritrova nel caso di Dilithium e di alcuni schemi multivariati. Similmente a questi ultimi, i protocolli di identificazione costruiti direttamente su SDP presentano una soundness-error (ovvero la probabilità di successo di un avversario) molto elevata, richiedendo numerose ripetizioni parallele del protocollo per ottenere il livello di sicurezza desiderato. Ogni ripetizione contribuisce alla dimensione della firma, portando a valori significativamente più grandi rispetto agli schemi lattice-based già standardizzati. CROSS affronta questo problema introducendo una variante “restricted” del problema Syndrome Decoding, una struttura algebrica che porta ad una riduzione dei parametri rispetto alla versione classica e, di conseguenza, della dimensione della firma.

Syndrome Decoding “ristretto”

Un codice lineare $[n, k]_q$ su un campo finito $\mathbb{F}_q$ è un sottospazio vettoriale di dimensione $k$ in $\mathbb{F}_q^n$ . Esso è descritto in modo equivalente dalla sua matrice di parità $H \in \mathbb{F}_q^{r \times n}$ (con $r = n - k$ ), tale che una parola $\mathbf{c} \in \mathbb{F}_q^n$ appartiene al codice se e solo se $\mathbf{c}H^\top = \mathbf{0}$ . Dato un vettore generico $\mathbf{e} \in \mathbb{F}_q^n$ , il vettore $\mathbf{s} = \mathbf{e}H^\top \in \mathbb{F}_q^r$ è detto sindrome di $\mathbf{e}$ .

Il Syndrome Decoding Problem (SDP) chiede: dati $H$ e una sindrome $\mathbf{s}$ , trovare un vettore $\mathbf{e} \in \mathbb{F}_q^n$ di peso di Hamming esattamente $w$ (ovvero con esattamente $w$ coordinate non nulle) tale che $\mathbf{e}H^\top = \mathbf{s}$ . Questo problema è stato dimostrato essere NP-completo nel caso generale e alcune sue formulazioni sono alla base di importanti schemi KEM post-quantum, quali i già citati Classic McEliece e HQC.

Come accennato nell’introduzione, CROSS non si basa direttamente sul SDP classico, bensì su una variante denominata Restricted Syndrome Decoding Problem (R-SDP), introdotta con l’obiettivo di costruire un protocollo a conoscenza zero (zero-knowledege, o ZK) più efficiente e di supportare chiavi di dimensione molto ridotta.

R-SDP

Sia $p$ un numero primo e $\mathbb{F}_p$ il campo finito con $p$ elementi. Sia $g \in \mathbb{F}_p^*$ un elemento di ordine primo $z$ , e sia

$E = \langle g \rangle = \{g,\, g^2,\, \ldots,\, g^z\} \subseteq \mathbb{F}_p^*$

il sottogruppo ciclico di $\mathbb{F}_p^*$ generato da $g$ , di ordine $|E| = z$ . Un vettore $\mathbf{e} \in \mathbb{F}_p^n$ è detto ristretto se tutte le sue coordinate appartengono a $E$ , ovvero $\mathbf{e} \in E^n$ .

R-SDP $(n, k, p, z)$ :Data una matrice di parità $H \in \mathbb{F}_p^{r \times n}$ (con $r = n - k$ ), una sindrome $\mathbf{s} \in \mathbb{F}_p^r$ e un insieme ristretto $E$ , trovare $\mathbf{e} \in E^n$ tale che

$\mathbf{e} H^\top = \mathbf{s}.$

A differenza dell’SDP classico, dove si cerca un vettore sparso (basso peso di Hamming), in R-SDP la soluzione ha supporto pieno (tutte le coordinate sono non nulle) in quanto tutte le coordinate devono appartenere al sottogruppo $E$ . La restrizione impone un vincolo stringente sul problema in quanto tipicamente viene selezionato $z = |E| \ll p - 1 = |\mathbb{F}_p^*|$ , riducendo notevolmente il numero di soluzioni valide. Nonostante tale vincolo, è stato dimostrato che la versione decisionale del problema è NP-completa per qualsiasi restrizione $E$ .

Uno dei punti fondamentali che giustificano l’impiego di questa variante nella costruzione di CROSS è l’isomorfismo di gruppi

$(E^n,\, \star) \;\cong\; (\mathbb{F}_z^n,\, +),$

dove $\star$ denota la moltiplicazione componente per componente. Ogni vettore ristretto $\mathbf{e} = (g^{\bar{e}_1}, \ldots, g^{\bar{e}_n})$ è infatti univocamente descritto dal suo vettore di esponenti $\bar{\mathbf{e}} = (\bar{e}_1, \ldots, \bar{e}_n) \in \mathbb{F}_z^n$ , e la moltiplicazione componente per componente in $E^n$ corrisponde all’addizione in $\mathbb{F}_z^n$ . Questa corrispondenza permette di eseguire le operazioni del protocollo ZK interamente in $\mathbb{F}_z^n$ , su cui l’aritmetica è semplice ed efficiente. Inoltre, la rappresentazione di un vettore $\mathbf{e}$ avviene interamente tramite il vettore di esponenti in $\mathbb{F}_z^n$ , permettendo una rappresentazione compatta.

R-SDP(G)

In CROSS, viene inoltre considerata una variante con una restrizione aggiuntiva. In questo caso, la soluzione deve appartenere non all’intero gruppo $E^n$ , ma a un sottogruppo proprio $G < (E^n, \star)$ , strutturato come un codice lineare nello spazio degli esponenti. Tale variante viene denotata come R-SDP(G).

Più precisamente, sia $M \in \mathbb{F}_z^{m \times n}$ una matrice di rango $m < n$ , pubblica. Il sottogruppo $G$ è definito come l’immagine della mappa

$\mathbb{F}_z^m \to E^n, \qquad \bar{\mathbf{u}} \mapsto \mathbf{e} = \Bigl(g^{(\bar{\mathbf{u}} M)_1},\, \ldots,\, g^{(\bar{\mathbf{u}} M)_n}\Bigr),$

dove $(\mathbf{x})_i$ rappresenta la proiezione sulla $i$ -esima coordinata del vettore $\mathbf{x}$ . In altre parole, gli elementi di $G$ sono i vettori ristretti il cui vettore di esponenti appartiene al sottospazio $\operatorname{Im}(M) \subseteq \mathbb{F}_z^n$ . Da cui segue $|G| = z^m$ .

R-SDP(G) $(n, k, m, p, z)$ :Data $H \in \mathbb{F}_p^{r \times n}$ , una matrice $M \in \mathbb{F}_z^{m \times n}$ di rango $m < n$ , e una sindrome $\mathbf{s} \in \mathbb{F}_p^r$ , trovare $\mathbf{e}_G \in \mathbb{F}_z^m$ tale che, detto $\bar{\mathbf{e}} = \mathbf{e}_G M \in \mathbb{F}_z^n$ e $\mathbf{e} = g^{\bar{\mathbf{e}}} = \bigl(g^{\bar{e}_1}, \ldots, g^{\bar{e}_n}\bigr) \in G \subset \mathbb{F}_p^n$ , vale

$\mathbf{e}_G M H^\top = \mathbf{s}.$

Il vantaggio di questo approccio riguarda l’uso dell’isomorfismo $G \cong \mathbb{F}_z^m$ con $m < n$ , il quale permette una rappresentazione ancora più compatta dei vettori ristretti. Tuttavia, la struttura algebrica aggiuntiva può essere sfruttata da un avversario per costruire attacchi a collisione più efficaci, richiedendo un’analisi più accurata dei parametri.

CROSS

CROSS segue il paradigma classico delle firme basate su schemi di identificazione: si definisce un problema difficile come relazione, si costruisce su di esso un protocollo di identificazione a conoscenza zero, e lo si converte in firma non interattiva tramite la trasformata di Fiat-Shamir. Per maggiori dettagli sulla struttura di tali costruzioni rimandiamo all’articolo sulle firme multivariate basate su schemi di identificazione.

Generazione delle chiavi

Nei protocolli di identificazione, il punto di partenza è la definizione di una relazione $\mathcal{R} \subseteq \mathcal{X} \times \mathcal{W}$ associata ad un problema difficile: un insieme di coppie $(x, w)$ in cui $x$ è detto statement e $w$ è detto witness. Lo statement è pubblico e descrive il problema; il witness è segreto e ne costituisce la soluzione. L’obiettivo del protocollo è che il prover dimostri al verifier di conoscere un witness valido per lo statement pubblico, senza rivelarlo.

Nel caso di CROSS, la relazione è quella di R-SDP (risp. R-SDP(G)): lo statement è la coppia $(\mathbf{s}, H)$ che specifica l’istanza del problema, mentre il witness è il vettore ristretto $\mathbf{e} \in E^n$ (risp. $G$ ) che ne è soluzione. Questo si traduce direttamente nella coppia chiave pubblica/privata.

Il protocollo di identificazione a 5 passi

Il protocollo alla base di CROSS è un protocollo di identificazione a 5 passi. La struttura ad alto livello tra prover (P) e verifier (V), illustrata nel diagramma sottostante, è la seguente.

Commit (P $\to$ V): Il prover sceglie randomicamente $\mathbf{e}' \in G$ e $\mathbf{u}' \in \mathbb{F}_p^n$ . Successivamente calcola la trasformazione $\mathbf{v} \in G$ tale che $\mathbf{v} \star \mathbf{e}' = \mathbf{e}$ e definisce $\mathbf{u} = \mathbf{v} \star \mathbf{u}'$ . Il prover quindi calcola i commitment crittografici $c_0 = \operatorname{Hash}(\mathbf{u}H^\top, \mathbf{v})$ associato alla sindrome $\mathbf{u}H^\top$ e alla trasformazione $\mathbf{v}$ , e $c_1=\operatorname{Hash}(\mathbf{e}', \mathbf{u}')$ associato ai valori random $\mathbf{e}'$ e $\mathbf{u}'$ .
Prima challenge (V $\to$ P): Il verifier invia $z \xleftarrow{$} \mathbb{F}_p^*$ , una challenge scalare nell’intero gruppo moltiplicativo di $\mathbb{F}_p$ .
Risposta (P $\to$ V): Il prover calcola e invia la risposta $\mathbf{y} = \mathbf{u}' + z \cdot \mathbf{e}' = \mathbf{v}^{-1}\star(\mathbf{u} + z \cdot \mathbf{e}).$
Seconda challenge (V $\to$ P): Il verifier invia una challenge binaria $b \xleftarrow{$} \{0, 1\}$ .
Apertura (P $\to$ V): Se $b=0$ , il prover rivela $\mathbf{v}$ ; se $b=1$ , il prover rivela gli elementi random $\mathbf{e}'$ e $\mathbf{u}'$ .
Verifica (V): Se $b=0$ , il verifier può verificare $c_0$ calcolando $\operatorname{Hash}((\mathbf{v} \star \mathbf{y})H^\top - z \cdot \mathbf{s}, \mathbf{v})$ poiché $\mathbf{v} \star \mathbf{y} = \mathbf{u} + z\cdot \mathbf{e}$ . Se $b=1$ , il verifier può verificare $c_1$ calcolando $\operatorname{Hash}(\mathbf{e}', \mathbf{u}')$ e successivamente verificare che $\mathbf{y}$ sia stato calcolato onestamente.

Il protocollo soddisfa le proprietà di sicurezza necessarie per poter essere trasformato in una firma digitale. In particolare è zero-knowledege (esiste un algoritmo pubblico che produce transcript indistinguibili senza conoscere $\mathbf{e}$ ) ed è sound (un prover disonensto non può convincere il verifier se non con una probabilità limitata). La soundness-error in una singola esecuzione è $\frac{p}{2(p-1)}$ . Per raggiungere il livello di sicurezza richiesto, il protocollo viene ripetuto in parallelo, applicando diverse ottimizzazioni in grado di ridurre la dimensione complessiva della prova trasmessa.

Infine, al protocollo viene applicata la trasformata di Fiat-Shamir, dove le due challenge del verifier vengono sostituite da valori derivata tramite l’hash del messaggo da firmare e del transcript parziale.

Schema semplificato del protocollo di identificazione a 5 passi alla base di CROSS (singola esecuzione).

Prestazioni

CROSS è proposto al NIST in due varianti principali, basate rispettivamente su R-SDP e R-SDP(G), ciascuna declinata in tre configurazioni (fast, balanced, small) che bilanciano dimensione della firma e velocità di esecuzione. I grafici seguenti confrontano la variante balanced di CROSS con gli schemi post-quantum già standardizzati e con due riferimenti classici non post-quantum. Tutti i parametri sono scelti all’interno della categoria I dei livelli di sicurezza definiti dal NIST.

La variante fast di CROSS ha firme tra 12 e 18 kB; la variante small raggiunge i 9.0 kB per CROSS-RSDP(G)-s e i 12.4 kB per CROSS-RSDP-s, al costo di tempi di escuzione 3–4 volte superiori. In entrambe le famiglie, R-SDP(G) risulta sempre più compatto e veloce di R-SDP, grazie alla rappresentazione compressa del witness in $\mathbb{F}_z^m$ con $m < n$ .

I grafici evidenziano come CROSS abbia chiavi pubbliche estremamente compatte (54–77 B), a fronte di firme nell’ordine di 9–18 kB per la categoria I. Queste ultime risultano significativamente più grandi di ML-DSA ma comparabili con SLH-DSA. D’altra parte, i tempi di firma e verifica della variante balanced, si collocano in un range competitivo, risultando molto più efficienti di SLH-DSA-128s.

La rilevanza di CROSS risiede anche nei problemi sottostanti, le cui basi crittografiche sono completamente disgiunte dagli schemi già standardizzati. Tuttavia, R-SDP rimane un problema relativamente recente rispetto a LWE e alle primitive simmetriche su cui poggiano ML-DSA e SLH-DSA. Inoltre, l’implementazione di riferimento presenta un memory footprint² non trascurabile su dispositivi embedded a risorse molto limitate. Il processo di valutazione del secondo round NIST è ancora in corso e ne determinerà le sorti verso una possibile standardizzazione.

https://www.cross-crypto.com/↩︎
La quantita totale di memoria (RAM e/o Flash) occupata da un programma durante la sua esecuzione.↩︎

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.

L’autore

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.