Firme CRYSTALS-Dilithium e Falcon

Le firme RSA ed ECDSA vengono compromesse dall'algoritmo di Shor. Le firme post-quantistiche devono sostituirle per: certificati TLS, firma del codice, firma delle email (S/MIME, PGP) e autenticazione degli aggiornamenti software. NIST ha standardizzato due schemi basati su reticoli: ML-DSA e FN-DSA.

Dilithium si basa sulla difficoltà di Module-LWE e Module-SIS (Short Integer Solution). La dimostrazione di sicurezza è formulata nel QROM (Quantum Random Oracle Model). Tre varianti: Dilithium2 (~128 bit), Dilithium3 (~192 bit), Dilithium5 (~256 bit). Percorso di firma semplice e privo di rejection sampling.

Chiave privata: matrici segrete s1, s2. Chiave pubblica: t = As1 + s2. Firma: campiona y casuale; calcola w = Ay; calcola la challenge c = H(mu || w1), dove w1 = HighBits(w); calcola z = y + cs1; se ||z|| o ||r0|| è troppo grande, rifiuta e riprova. Restituisce (z, c, hint).

Verifica (z, c, hint): controlla che ||z|| sia piccolo; calcola w' = Az - ct; usa hint per recuperare w1; verifica c == H(mu || w1). hint è costituito da un numero ridotto di bit prodotto da MakeHint(). Il rifiuto garantisce che z non riveli s1: l'argomentazione di sicurezza è un'argomentazione "aborts-then-uniform".

ML-DSA-65 (Dilithium3, sicurezza a 192 bit): chiave pubblica di 1952 byte, chiave privata di 4000 byte, firma di 3293 byte. A confronto, ECDSA-P256: chiave pubblica di 64 byte, firma di 64 byte. Le firme Dilithium sono circa 40-50 volte più grandi, ma sono sicure contro i computer quantistici.

Falcon si basa sui reticoli NTRU e usa un campionatore gaussiano sul reticolo NTRU. Le firme sono significativamente più piccole di quelle di Dilithium, ma la firma richiede un campionatore gaussiano in virgola mobile, più difficile da implementare a tempo costante e più complesso da codificare in modo sicuro.

Falcon-512 (sicurezza a 128 bit): chiave pubblica di 897 byte, firma di 666 byte, molto più piccole rispetto a Dilithium. Compromesso: Falcon è più difficile da implementare in modo sicuro (il campionamento gaussiano è suscettibile agli attacchi basati sui tempi). È adatto agli ambienti con larghezza di banda limitata, ma richiede un'implementazione accurata.

SPHINCS+ è uno schema di firma basato su hash: una scelta conservativa che non presuppone proprietà algebriche strutturali. La sicurezza dipende soltanto dalla sicurezza della funzione hash. Dimensione della firma: circa 8-50 KB, quindi elevata. Firma lenta. Viene usato quando la fiducia a lungo termine è fondamentale e le prestazioni sono secondarie.

ML-DSA (Dilithium): uso generale, implementazione semplice, adatto ai certificati TLS e alla firma del codice. FN-DSA (Falcon): ambienti con larghezza di banda limitata (IoT, LPWAN). SLH-DSA (SPHINCS+): estremamente conservativo, adatto alle radici di lunga durata (chiavi CA offline, radice di attendibilità del software).

Dilithium: il rejection sampling può causare perdite di informazioni sui tempi dei branch; utilizzi un confronto a tempo costante. Falcon: il campionatore gaussiano usa la virgola mobile; garantisca il determinismo delle operazioni in virgola mobile. Per entrambi: eviti i canali laterali nell'aritmetica dei polinomi. Utilizzi le implementazioni di riferimento dei pacchetti di submission NIST.

NIST FIPS 204: ML-DSA (Dilithium). NIST FIPS 205: SLH-DSA (SPHINCS+). NIST FIPS 206: FN-DSA (Falcon). Tutti sono stati pubblicati nell'agosto 2024. Librerie: OpenSSL 3.x, BoringSSL e liboqs (progetto Open Quantum Safe) implementano tutti e tre gli schemi.

ML-DSA (Dilithium): basato su reticoli, semplice, firme di circa 3 KB. FN-DSA (Falcon): basato su NTRU, firme di circa 700 byte, implementazione complessa. SLH-DSA (SPHINCS+): basato su hash, conservativo, di grandi dimensioni. Tutti sono standardizzati in FIPS 204/205/206. Prossimo argomento: migrazione alla PQC con approcci ibridi.