FIPS 204-Compatible Threshold ML-DSA via Shamir Nonce DKG

Questo lavoro presenta il primo schema di soglia ML-DSA compatibile con FIPS 204 che garantisce la privacy della condivisione del nonce senza assunzioni computazionali, utilizzando una DKG di tipo Shamir e maschere PRF per produrre firme standard verificabili da implementazioni non modificate.

L'essenziale

🛡️ Il Grande Scudo Quantistico: Come firmare insieme senza fidarsi ciecamente

Immagina che il mondo digitale stia per affrontare un'orda di "super-criminali" (i computer quantistici) capaci di rompere tutti i lucchetti attuali. Per fermarli, gli scienziati hanno creato un nuovo lucchetto invincibile chiamato ML-DSA (o FIPS 204). È come un nuovo tipo di sigillo di cera che nessun computer quantistico potrà mai rompere.

Ma c'è un problema: chi ha il potere di usare questo sigillo?
Nella vita reale, non vogliamo che una sola persona (un amministratore) tenga il sigillo. Se quella persona viene rapita, corrotta o perde la chiave, tutto è perso. Vogliamo che un gruppo di persone debba accordarsi per firmare un documento. Se ci sono 5 persone, forse servono almeno 3 per firmare. Questo si chiama Firma Soglia.

Il problema è che creare una "firma a soglia" con questo nuovo lucchetto quantistico è stato estremamente difficile. I metodi precedenti erano lenti, costosi o producevano firme troppo grandi per essere accettate dai sistemi esistenti.

Questo paper presenta una soluzione geniale, come se avessimo trovato il modo di far lavorare insieme un gruppo di persone senza che nessuno di loro sappia la chiave completa, ma tutti insieme possano creare il sigillo perfetto.

---

🔑 L'Analogia della "Ricetta Segreta"

Immagina che il segreto per firmare sia una ricetta segreta (la chiave privata).
Nella crittografia classica, dividere la ricetta è facile: la tagli in 5 pezzi e dai un pezzo a ogni persona. Ma con il nuovo lucchetto quantistico (ML-DSA), c'è un trucco: la ricetta deve essere mescolata in un modo molto specifico, altrimenti il sigillo non viene riconosciuto.

Il Problema: Il "Rumore" che rovina tutto

Quando le persone provano a unire i loro pezzi della ricetta per firmare, spesso il risultato è "rumoroso" o distorto. È come se 5 cuochi provassero a cucinare insieme una zuppa, ma ognuno aggiunge un po' di sale in modo casuale. Alla fine, la zuppa è salata o insipida e il cliente (il verificatore) la rifiuta.
Nei metodi precedenti, per nascondere questo "rumore", si aggiungeva così tanto rumore di fondo che la zuppa diventava enorme (firma di 17 KB invece di 3.3 KB), rendendola inutilizzabile.

La Soluzione Magica: Il "Distributore di Nonce" (Shamir Nonce DKG)

Gli autori hanno inventato un nuovo modo per mescolare gli ingredienti. Invece di dare pezzi statici della ricetta, fanno in modo che ogni persona generi un ingrediente temporaneo (chiamato nonce) che cambia ogni volta che si firma.

Ecco la magia:

1. La Partita di Poker: Immagina che ogni persona abbia una mano di carte segrete. Per firmare, devono mescolare le loro carte in un modo matematico preciso.
2. Il Trucco di Shamir: Usano un metodo matematico (chiamato Shamir Secret Sharing) che assicura che, anche se un ladro ruba le carte di 2 persone su 3, non può mai ricostruire la mano completa. Ma se ci sono 3 persone, possono ricostruire la mano perfetta.
3. La Privacy Assoluta: La cosa incredibile è che questo metodo garantisce che la "mano" di ogni persona sia così imprevedibile da essere sicura al 100%, senza bisogno di assumere che i computer siano lenti. È una sicurezza matematica pura.

🚀 Tre Modi per Usare questo Sistema (I Profili)

Gli autori non si sono fermati alla teoria. Hanno creato tre modi pratici per usare questo sistema, a seconda di quanto vuoi fidarti delle persone o delle macchine:

1. Profilo P1: Il "Cassiere Sicuro" (Con TEE)

• L'Analogia: Immagina una banca con un cassaforte blindata (un TEE, un chip sicuro) che fa da coordinatore.
• Come funziona: Le persone inviano i loro pezzi al cassaforte. Il cassaforte li unisce, controlla che tutto sia a posto e stampa la firma.
• Vantaggio: È velocissimo (pochi millisecondi).
• Svantaggio: Devi fidarti che il cassaforte non sia manomesso.

2. Profilo P2: Il "Cerchio di Amici" (Senza Fiducia)

• L'Analogia: Immagina un gruppo di amici che devono firmare un contratto, ma nessuno si fida dell'altro e non c'è un cassaforte centrale.
• Come funziona: Usano un sistema di calcolo distribuito (MPC). È come se tutti scrivessero su foglietti trasparenti, li mescolassero in una scatola opaca e facessero i calcoli senza mai vedere cosa c'è scritto sugli altri fogli.
• Vantaggio: Non serve fidarsi di nessuno. Se anche 4 su 5 sono malintenzionati, la sicurezza regge.
• Svantaggio: È un po' più lento perché devono scambiarsi molti messaggi.

3. Profilo P3+: Il "Lavoro a Turni" (Semi-Asincrono)

• L'Analogia: Immagina un gruppo di manager che devono approvare una spesa. Non possono essere tutti online contemporaneamente alle 10:00.
• Come funziona: I manager preparano i loro pezzi "in anticipo" (mentre fanno altro). Quando arriva l'ordine di firmare, rispondono entro una finestra di tempo (es. 5 minuti). Due "controllori" (CP) fanno il lavoro pesante di unione.
• Vantaggio: È perfetto per la vita reale, dove le persone hanno impegni. È veloce e flessibile.

📊 Perché è un Grande Passo Avanti?

1. Dimensioni Standard: Le firme prodotte sono piccole (3.3 KB), esattamente come quelle che i computer già sanno leggere. Non serve cambiare nulla nei sistemi esistenti.
2. Velocità: Funziona in pochi millisecondi, quasi come se fosse una singola persona a firmare.
3. Sicurezza Matematica: Hanno dimostrato che anche se un gruppo di persone prova a imbrogliare, non può farlo senza essere scoperto, e la chiave rimane segreta.
4. Nessun "Colpo di Sfortuna": I metodi precedenti fallivano spesso (dovevano riprovare molte volte). Questo sistema ha un tasso di successo molto alto, simile a quello di una singola persona.

🎯 In Sintesi

Questo paper è come aver trovato il modo di far lavorare insieme un'orchestra di musicisti per suonare un brano perfetto, anche se:

• Ogni musicista non conosce la partitura completa.
• Non c'è un direttore d'orchestra che comanda tutti.
• Il pubblico (i verificatori) non si accorge che sono in molti, sente solo una musica perfetta e standard.

È la chiave per proteggere i nostri dati nel futuro quantistico, permettendo alle aziende e ai governi di distribuire il potere decisionale senza rischiare la sicurezza.

Sommario tecnico

Ecco un riassunto tecnico dettagliato del documento "Threshold ML-DSA via Shamir Nonce DKG" di Leo Kao, presentato in italiano.

Titolo

FIPS 204-Compatible Threshold ML-DSA via Shamir Nonce DKG

1. Il Problema: Il "Gap" delle Firme Soglia

Con l'avvento dei computer quantistici, il NIST ha standardizzato ML-DSA (Module-Lattice-Based Digital Signature Algorithm) come standard FIPS 204 per le firme digitali post-quantum. Tuttavia, l'implementazione di varianti a soglia (threshold) per ML-DSA presenta sfide uniche rispetto alle firme classiche (come ECDSA o Schnorr):

• Complessità del Rejection Sampling: ML-DSA utilizza il paradigma "Fiat-Shamir with Aborts". Una firma è valida solo se il vettore di risposta $z = y + cs_1$ soddisfa una norma limitata ($\|z\|_\infty < \gamma_1 - \beta$). In un contesto distribuito, combinare le risposte parziali di più parti senza violare questo vincolo è estremamente difficile.
• Limitazioni delle Soluzioni Esistenti:
  • Gli schemi basati su LSSS a coefficienti brevi (es. del Pino-Niot) sono limitati a soglie molto basse ($T \le 6$) a causa della crescita esponenziale dei coefficienti di Lagrange.
  • Le tecniche di Noise Flooding permettono soglie arbitrarie ma gonfiano la dimensione della firma (fino a 17 KB), rendendole incompatibili con il formato standard FIPS 204 (3.3 KB).
  • Costruzioni specializzate (es. Ringtail) offrono efficienza ma producono formati di firma non verificabili dagli implementatori standard FIPS 204.
• Il Gap: Non esisteva una soluzione che combinasse soglie arbitrarie, dimensione della firma standard (3.3 KB), compatibilità FIPS 204 e privacy delle quote del nonce senza assunzioni computazionali.

2. Metodologia e Tecnologie Chiave

L'autore propone un nuovo schema basato su due tecniche principali:

A. Shamir Nonce DKG (Distributed Key Generation)

Questa è la tecnica primaria. Invece di generare il nonce $y$ in modo uniforme e poi condividerlo, le parti generano congiuntamente il nonce come una condivisione di Shamir di grado $(T-1)$, che rispecchia esattamente la struttura della chiave segreta a lungo termine $s_1$.

• Meccanismo: Ogni parte $i$ genera un polinomio $f_i(x)$ di grado $T-1$. Il termine costante è un contributo al nonce, mentre i coefficienti di grado superiore sono campionati uniformemente da $R_q$ (non da una distribuzione corta).
• Privacy Statistica: Poiché l'avversario osserva al massimo $T-1$ valutazioni del polinomio di una parte onesta, rimane un grado di libertà. Questo grado di libertà agisce come un "one-time pad" statistico.
• Risultato: La quota del nonce di una parte onesta ($y_h$) possiede un'entropia minima condizionata che supera di oltre 5 volte l'entropia della chiave segreta (per $|S| \le 17$), senza alcuna assunzione computazionale. Questo elimina la necessità di un "due-honest assumption" (avere almeno $T+1$ partecipanti) richiesta da altri schemi.

B. Maschere a Cancellazione Pairwise (Pairwise-Canceling Masks)

Adattate dalle firme ECDSA, queste maschere sono utilizzate per nascondere i valori di impegno ($W_i$) e le quote di controllo $r_0$ ($V_i$).

• Funzionamento: Ogni parte calcola una maschera $m_i$ basata su semi condivisi a coppie e PRF (Pseudorandom Functions), tale che la somma di tutte le maschere nel gruppo sia zero ($\sum m_i = 0$).
• Scopo: Permette di sommare i contributi parziali senza rivelare i singoli contributi, proteggendo la privacy durante la fase di aggregazione e il controllo $r_0$ (che altrimenti rivelerebbe $cs_2$ e porterebbe al recupero della chiave).

C. Distribuzione Irwin-Hall

L'aggregazione dei nonce segue una distribuzione di Irwin-Hall (somma di variabili uniformi) invece di una distribuzione uniforme singola.

• Analisi di Sicurezza: L'autore dimostra che questa deviazione introduce una perdita di sicurezza trascurabile. Utilizzando un'analisi diretta di shift-invariance (invece dei bound conservativi di tipo Raccoon), la perdita di sicurezza per sessione è $< 0.013$ bit per $|S| \le 33$. Questo risolve il problema della scalabilità presente nelle analisi precedenti.

3. Profili di Implementazione

Il lavoro definisce tre profili di deployment, tutti con prove di sicurezza UC (Universal Composability):

1. Profilo P1 (Assistito da TEE):

   • Utilizza un coordinatore in un ambiente di esecuzione attendibile (TEE/HSM) per eseguire il controllo $r_0$ e la generazione dell'hint.
   • Vantaggi: 3 round online, latenza molto bassa (~5.8 ms per 3-of-5).
   • Assunzioni: Integrità del TEE.

2. Profilo P2 (Completamente Distribuito):

   • Nessun trusted dealer o TEE. Utilizza MPC (Secure Multi-Party Computation) basato su SPDZ e edaBits per il controllo $r_0$.
   • Vantaggi: Sicurezza contro maggioranza disonesta, 5 round online.
   • Svantaggi: Latenza più alta (~21.5 ms per 3-of-5), ma elimina la fiducia hardware.

3. Profilo P3+ (Semi-Asincrono 2PC):

   • Progettato per scenari "human-in-the-loop". Due parti di calcolo (CP) eseguono un 2PC per il controllo $r_0$.
   • Innovazione: I firmatari pre-calcolano i nonce offline e rispondono entro una finestra temporale (es. 5 minuti), senza bisogno di sincronizzazione multi-round.
   • Vantaggi: 2 round logici, latenza ~22 ms, ideale per autorizzazioni distribuite.

4. Risultati Sperimentali

L'implementazione in Rust è stata testata su hardware commodity (Intel i7-12700H):

• Dimensione Firma: 3.3 KB (identica a ML-DSA standard), verificabile da qualsiasi implementazione FIPS 204 non modificata.
• Latenza:
  • P1 (TEE): 4-60 ms (da 2-of-3 a 32-of-45).
  • P2 (MPC): 21-194 ms.
  • P3+ (2PC): 17-94 ms.
• Tasso di Successo: Il tasso di successo per tentativo è compreso tra il 21% e il 45%, paragonabile o leggermente superiore alla firma singola (20-25%) grazie alla concentrazione della distribuzione di Irwin-Hall vicino allo zero.
• Scalabilità: Lo schema scala fino a soglie elevate (es. 32-of-45) mantenendo latenze sub-100ms nei profili P1 e P3+.

5. Significato e Contributi

Questo lavoro rappresenta un avanzamento fondamentale nella crittografia post-quantum:

1. Prima Soluzione Completa: È il primo schema a soglia per ML-DSA che raggiunge soglie arbitrarie, mantiene la dimensione standard della firma e garantisce la privacy delle quote del nonce in modo statistico (senza assunzioni computazionali).
2. Chiusura del Gap di Scalabilità: Risolve il problema della perdita di sicurezza scalabile nelle analisi precedenti, dimostrando che l'uso di nonces distribuiti non degrada significativamente la sicurezza anche con un gran numero di partecipanti.
3. Compatibilità Pratica: Permette alle organizzazioni di adottare la crittografia post-quantum in scenari distribuiti (custodia di chiavi, CA distribuite, autorizzazioni finanziarie) senza dover modificare i verificatori esistenti.
4. Flessibilità Operativa: Offre diverse opzioni di deployment (P1, P2, P3+) per bilanciare fiducia hardware, complessità computazionale e requisiti di latenza/sincronizzazione.

In sintesi, questo documento fornisce un ponte pratico e sicuro tra la standardizzazione FIPS 204 e le esigenze reali di gestione distribuita delle chiavi nel mondo post-quantum.