Il futuro della crittografia basata sulle isogenie

La rottura di SIKE da parte di Castryck-Decru, avvenuta nel luglio 2022, ha cambiato radicalmente il campo delle isogenie. Prima della rottura, la crittografia basata sulle isogenie era una promettente direzione post-quantistica, caratterizzata da dimensioni ridotte delle chiavi, da attivi sforzi di standardizzazione e da una comunità in crescita. Dopo la caduta di SIKE, il campo ha dovuto riesaminare le proprie basi. La domanda fondamentale è: quali aspetti della crittografia basata sulle isogenie restano difficili dopo le nuove tecniche basate sulle isogenie di Richelot? La risposta sembra essere la seguente: la difficoltà basata sugli anelli degli endomorfismi (utilizzata in SQISign) e le azioni commutative dei gruppi delle classi (CSIDH) restano intatte. La fuga di informazioni dai punti di torsione ausiliari specifica di SIDH è il componente compromesso, non le isogenie in generale.

SQISign (Short Quaternion and Isogeny Signature, De Feo et al., 2020) è lo schema di firma post-quantistico noto più compatto. Chiave pubblica: 64 byte (un j-invariant supersingolare). Firma: 177 byte al Level 1. Per confronto, ML-DSA (Dilithium) ha chiavi pubbliche di 1312 byte e firme di 2420 byte al Level 2. La sicurezza di SQISign si basa sulla corrispondenza di Deuring: il problema di calcolare un'isogenia di grado prescritto tra due curve supersingolari date equivale a trovare un ideale nell'algebra dei quaternioni dell'anello degli endomorfismi. SQISign utilizza uno schema di identificazione Fiat-Shamir basato su questo problema difficile e produce una firma sotto forma di rappresentazione compressa dell'isogenia di risposta.

La compattezza di SQISign comporta un costo elevato in termini di prestazioni. La firma richiede il calcolo di un'isogenia di grado elevato (circa p^{1/4}) mediante la conversione da ideali a isogenie nell'algebra dei quaternioni: un'operazione ad alta intensità computazionale che richiede circa 60-600 secondi su una CPU desktop, a seconda dell'insieme di parametri. La verifica è più veloce (circa 200 ms), ma resta molto più lenta della verifica di ML-DSA (microsecondi). SQISign 2.0 (2023) ha migliorato le prestazioni di 100 volte grazie a miglioramenti algoritmici, portando il tempo di firma a 1-10 secondi. SQISign HD (high degree) e altre varianti continuano il lavoro di ottimizzazione. L'obiettivo sono i casi d'uso in cui la larghezza di banda è fortemente limitata, come i certificati IoT, i dati blockchain e le comunicazioni spaziali, e in cui la velocità di calcolo è secondaria.

FESTA (Fast Encryption from Supersingular Torsion Attacks, 2023) è un KEM progettato esplicitamente per evitare la fuga di informazioni dai punti di torsione tipica di SIDH. L'idea progettuale fondamentale è la seguente: invece di pubblicare phi_A(P_B) e phi_A(Q_B) come in SIDH, FESTA utilizza una struttura di isogenie diversa, in cui la chiave pubblica del cifratore è costituita soltanto dalla curva immagine (senza immagini di punti di torsione). FESTA utilizza isogenie 2^n in modo modificato, così da consentire la decifratura senza le immagini della base di torsione della controparte. Le analisi iniziali suggeriscono che FESTA resista all'attacco di Castryck-Decru grazie alla diversa struttura delle informazioni ausiliarie. FESTA è una direzione promettente, ma richiede ulteriori analisi crittanalitiche: dopo la rottura a sorpresa di SIKE, la comunità delle isogenie procede con cautela.

SCALLOP (Scalable Commutative Actions with Large Oriented Primes, 2023) affronta il punto debole della sicurezza quantistica di CSIDH. Il piccolo primo p = 512 bit di CSIDH offre soltanto circa 65 bit di sicurezza quantistica (a causa dell'algoritmo subesponenziale di Kuperberg). SCALLOP utilizza una struttura algebrica diversa: curve con moltiplicazione complessa per ordini quadratici immaginari di grandi dimensioni, in cui il gruppo delle classi è progettato specificamente per resistere agli attacchi quantistici nello stile di Kuperberg. SCALLOP ottiene un gruppo delle classi effettivo più grande, con parametri che forniscono una sicurezza quantistica di 128 bit con dimensioni dei parametri inferiori a quelle di CSIDH-5000. Il compromesso è una configurazione algebrica più complessa e un numero inferiore di analisi indipendenti rispetto a CSIDH.

Data la particolare compattezza degli schemi basati sulle isogenie (firme di 177 byte per SQISign e chiavi di 64 byte per CSIDH) e le loro ipotesi di difficoltà, diverse da quelle degli schemi basati su reticoli, le costruzioni ibride combinano componenti basati su isogenie e su reticoli per ottenere una difesa stratificata. In un KEM ibrido, si esegue l'incapsulamento con ML-KEM-512 e con CSIDH-512, quindi si calcola l'hash di entrambi i segreti. Per compromettere la chiave combinata è necessario violare contemporaneamente sia ML-KEM (la difficoltà di LWE) sia CSIDH (l'azione del gruppo delle classi). Se uno dei due rimane integro, lo schema ibrido è sicuro. Questo approccio di agilità crittografica è sostenuto da NIST e NSA per le organizzazioni che desiderano garanzie aggiuntive rispetto a un singolo primitivo post-quantistico, soprattutto quando le tempistiche di sviluppo dei computer quantistici sono incerte.

Le prove a conoscenza zero basate sulle isogenie sono una direzione di ricerca emergente. Il problema del cammino delle isogenie (trovare phi: E -> E' date entrambe le curve) può fungere da problema difficile per gli schemi di prova di conoscenza. I protocolli Sigma per "Conosco un'isogenia da E a E'" consentono l'autenticazione senza rivelare l'isogenia. Vero (2022) dimostra un sistema pratico di prove a conoscenza zero basato sulle isogenie. Queste prove ZK sono naturalmente compatte (l'enunciato consiste soltanto di due j-invariant), ma attualmente sono troppo lente per una distribuzione pratica. Con il miglioramento del calcolo delle isogenie, le prove a conoscenza zero basate sulle isogenie potrebbero offrire alternative alle prove basate su reticoli o hash, nei casi in cui sia importante la diversità delle ipotesi.

Le tecniche delle isogenie non sono rilevanti soltanto per la crittografia post-quantistica: hanno applicazioni anche nella crittografia classica a curve ellittiche. L'algoritmo Schoof-Elkies-Atkin (SEA) per il conteggio dei punti sulle curve ellittiche utilizza le isogenie per calcolare la traccia di Frobenius, consentendo la generazione efficiente di parametri sicuri per le curve ellittiche. Le isogenie compaiono nei miglioramenti dell'algoritmo rho di Pollard per il calcolo dell'ECDLP. Il metodo CM (Complex Multiplication) per costruire curve con un ordine prescritto utilizza polinomi delle classi che sono fondamentalmente oggetti legati alle isogenie. Gli strumenti di crittoanalisi basati sulle isogenie (per trovare cammini di isogenie di grado liscio) vengono utilizzati per valutare i parametri proposti per le curve ellittiche alla ricerca di backdoor nascoste, un aspetto direttamente correlato alla problematica di Dual EC DRBG.

Al 2024, nessuno schema basato sulle isogenie è stato standardizzato da NIST o da altri importanti organismi. Il processo PQC di NIST ha standardizzato ML-KEM, ML-DSA, SLH-DSA e FN-DSA, tutti basati su reticoli o su hash. NIST sta conducendo una seconda tornata di valutazione delle firme PQC; SQISign è stato presentato, ma deve affrontare problemi di prestazioni. La comunità delle isogenie sta lavorando a un SQISign 3.0 più maturo, con tempi di firma pratici (obiettivo: meno di un secondo). ISO ed ETSI non hanno standardizzato alcuno schema basato sulle isogenie. Il percorso di standardizzazione più probabile nel breve termine è SQISign per applicazioni di nicchia che richiedono firme di dimensioni minime, eventualmente come standard informativo anziché come primitivo obbligatorio. Un'ampia distribuzione richiede miglioramenti delle prestazioni di un ordine di grandezza.

Al 2024, le direzioni di ricerca attive nella crittografia basata sulle isogenie sono: (1) varianti di SQISign (SQISign 2.0, HD, Fast SQISign) che migliorano le prestazioni della firma puntando a un'operazione in meno di un secondo; (2) analisi della sicurezza quantistica di CSIDH e delle sue varianti, con stime più precise degli attacchi di Kuperberg e studio di strutture algebriche in grado di resistervi; (3) nuove ipotesi di difficoltà, tra cui il calcolo degli anelli degli endomorfismi supersingolari e problemi su moduli di anelli quadratici immaginari; (4) PRF oblivue basate su isogenie e applicazioni a protocolli che tutelano la privacy; (5) implementazioni hardware dell'aritmetica delle isogenie, sfruttando il parallelismo degli FPGA per l'azione del gruppo delle classi di CSIDH; (6) integrazione delle azioni di gruppo basate sulle isogenie con framework generici per la crittografia delle azioni di gruppo, allo scopo di sviluppare nuovi schemi di cifratura funzionale e basati su attributi.

La violazione di SIKE potrebbe far pensare di abbandonare completamente la crittografia basata sulle isogenie. La comunità crittografica ritiene invece il contrario: la violazione è stata preziosa proprio perché ha individuato quali strutture non sono sicure (la fuga di informazioni dai punti di torsione di SIDH) e quali rimangono difficili da attaccare (gli anelli di endomorfismi e le azioni dei gruppi di classi). Studiare le isogenie rimane importante per: (1) la diversità post-quantistica — disporre di ipotesi di sicurezza oltre ai reticoli riduce il rischio sistemico nel caso in cui LWE venga violato; (2) SQISign offre firme eccezionalmente compatte, senza equivalenti attuali; (3) le tecniche basate sulle isogenie contribuiscono alla crittoanalisi delle curve ellittiche e alla validazione dei parametri; (4) la matematica è elegante e produttiva — gli strumenti sviluppati per la violazione di SIKE hanno migliorato direttamente la comprensione degli anelli di endomorfismi delle curve ellittiche, utilizzati anche in altri contesti.

Qual è l'ipotesi di difficoltà alla base delle firme SQISign?

Dopo la violazione di SIKE nel 2022, la crittografia basata sulle isogenie continua a svilupparsi grazie a ipotesi di difficoltà diverse. SQISign offre firme post-quantistiche da 177 byte, le più compatte note, basate sulla difficoltà del problema degli anelli di endomorfismi; le prestazioni stanno migliorando (obiettivo: meno di un secondo). FESTA è progettato per aggirare la fuga di informazioni dai punti di torsione di SIDH nei KEM. SCALLOP punta a una sicurezza quantistica di 128 bit tramite curve orientate. Gli schemi ibridi basati su isogenie e reticoli diversificano le ipotesi di sicurezza. Attualmente nessuno schema basato sulle isogenie è standardizzato. La standardizzazione di SQISign è la strada più probabile nel breve periodo. La violazione di SIKE ha consolidato la comprensione di ciò che deve rimanere nascosto nei protocolli basati sulle isogenie e ha prodotto nuovi strumenti matematici utilizzati in tutta la crittografia delle curve ellittiche.