CSIDH: isogenie supersingolari commutative

CSIDH (Commutative Supersingular Isogeny Diffie-Hellman, Castryck et al., 2018) è uno scambio di chiavi basato sulle isogenie che evita completamente la fuga di informazioni dai punti di torsione di SIDH, usando una struttura algebrica fondamentalmente diversa. CSIDH opera con curve supersingolari su Fp (non su Fp2 come SIDH). L'assunzione di difficoltà è la commutatività dell'azione del gruppo delle classi: ciascuna delle due parti applica un elemento segreto del gruppo delle classi a una curva iniziale comune, e la commutatività garantisce che entrambe arrivino alla stessa curva condivisa. Non viene pubblicata alcuna informazione ausiliaria sui punti di torsione; la chiave pubblica è costituita soltanto da un singolo j-invariante. Questa progettazione è sopravvissuta all'attacco di Castryck-Decru contro SIDH.

Su Fp con p = 3 mod 4, le curve supersingolari E hanno un endomorfismo distintivo pi (il Frobenius) e la loro algebra degli endomorfismi contiene l'ordine quadratico immaginario Z[pi]. Il gruppo delle classi Cl(Z[pi]) agisce liberamente e transitivamente sull'insieme delle curve supersingolari su Fp, a meno di isomorfismo. Un ideale a in Cl(Z[pi]) agisce su una curva E producendo una nuova curva a * E, calcolata come la curva E/E[a], dove E[a] è il sottogruppo di torsione corrispondente all'ideale a. Questa azione è commutativa: a * (b * E) = b * (a * E) = [ab] * E. Questa è l'azione del gruppo usata da CSIDH e fornisce un analogo commutativo di Diffie-Hellman.

Lo scambio di chiavi CSIDH si svolge come segue. Parametri pubblici: una curva supersingolare E0 su Fp e piccoli numeri primi dispari l_1, ..., l_n. Chiavi segrete: Alice sceglie a = (a_1, ..., a_n), con ogni a_i in {-m, ..., m} (piccoli interi casuali). Bob sceglie b = (b_1, ..., b_n). Chiave pubblica di Alice: E_A = [l_1^a_1 * ... * l_n^a_n] * E0. Chiave pubblica di Bob: E_B = [l_1^b_1 * ... * l_n^b_n] * E0. Segreto condiviso: Alice applica i propri esponenti segreti a E_B; Bob applica i propri a E_A. La commutatività garantisce che entrambi ottengano E_AB = [product(l_i^(a_i + b_i))] * E0. Il segreto condiviso è j(E_AB). Non vengono pubblicati punti ausiliari.

L'implementazione di riferimento di CSIDH utilizza p = 4 * l_1 * l_2 * ... * l_74 - 1, dove l_1 fino a l_74 sono i primi 74 numeri primi dispari (3, 5, 7, ..., 373). Si ottiene così un p di circa 512 bit. Ogni componente della chiave segreta a_i appartiene a {-5, ..., 5} (11 possibilità per componente, 74 componenti). L'ordine del gruppo delle classi è approssimativamente sqrt(p) e lo spazio delle chiavi ha dimensione 11^74. Calcolo di ogni passo di isogenia: per ogni primo l_i, si individua il sottogruppo di l_i-torsione e si calcola l'isogenia di grado l_i usando le formule di Velu. Con sqrt-Velu, ogni passo di isogenia di grado primo elevato richiede O(sqrt(l_i)) operazioni. Lo scambio complessivo di chiavi richiede circa 1-5 ms su hardware moderno per CSIDH-512.

La versione originale di CSIDH non è a tempo costante: il numero di passi di Velu dipende dai valori della chiave segreta a_i, facendo trapelare informazioni attraverso canali laterali basati sui tempi di esecuzione. CTIDH (Constant-Time ISOGENY Diffie-Hellman, Bernstein et al., 2021) risolve il problema usando un formato di chiave a peso fisso e un calcolo di isogenie progettato con attenzione per essere a tempo costante. Le chiavi segrete CTIDH sono limitate a vettori in cui la somma dei valori assoluti è fissa (ad esempio, sum |a_i| = 130). Il calcolo delle isogenie procede attraverso un numero fisso di passi, indipendentemente dai valori della chiave segreta, usando calcoli di isogenie fittizi per riempire i passi in cui l'esponente segreto è zero. CTIDH offre una sicurezza simile a quella di CSIDH-512, con rigorose garanzie di tempo costante adatte all'impiego su dispositivi embedded.

La sicurezza quantistica di CSIDH è più sfumata rispetto a quella degli schemi basati su reticoli. Il miglior attacco quantistico utilizza l'algoritmo di Kuperberg (2005) per il problema dell'hidden shift, che compromette la struttura dell'azione del gruppo delle classi in tempo subesponenziale L(1/2) = exp(O(sqrt(log p))). Questo è sostanzialmente migliore del miglior attacco classico, di complessità sqrt(p), il che significa che i computer quantistici indeboliscono notevolmente CSIDH rispetto agli attaccanti classici. Per ottenere una sicurezza post-quantistica di 128 bit (contro l'attacco L(1/2)), CSIDH richiede un primo p di circa 5000 bit (CSIDH-5000), rispetto ai 512 bit per una sicurezza classica di 128 bit. Si stima che CSIDH-512 offra soltanto 62-72 bit di sicurezza quantistica, ben al di sotto dei requisiti NIST Level 1.

La sicurezza di CSIDH si basa sul Group Action Inverse Problem (GAIP): dati E_A = a * E0 ed E0, occorre trovare a. Il miglior algoritmo noto è una riduzione simile a quella di Pohlig-Hellman combinata con baby-step-giant-step, con complessità classica O(sqrt(|Cl|)) ~ O(p^{1/4}). La difficoltà quantistica (Kuperberg) rende CSIDH meno sicuro contro i computer quantistici rispetto agli schemi basati su LWE. Il miglior attacco quantistico contro LWE (lattice sieving) offre margini di sicurezza più conservativi. Il vantaggio di CSIDH è la sua compattezza: CSIDH-512 ha chiavi pubbliche di 64 byte (costituite soltanto dal j-invariant), contro gli 800 byte di ML-KEM-512. Per le applicazioni che richiedono chiavi il più piccole possibile e accettano margini di sicurezza quantistica inferiori, CSIDH resta una soluzione interessante.

Diverse varianti di CSIDH affrontano i suoi limiti in termini di sicurezza quantistica. BSIDH (B per "better") utilizza curve di base di grado superiore e prodotti di curve ellittiche per aumentare la dimensione del gruppo delle classi mantenendo rapide le computazioni. Csurf (CSIDH on the surface) utilizza un insieme diverso di curve supersingolari per consentire un calcolo più rapido dell'azione di gruppo. Le proposte di CSIDH a genere superiore utilizzano jacobiane di curve di genere 2 su Fp, offrendo uno spazio di azione di gruppo più ampio e potenzialmente margini di sicurezza quantistica migliori. Nessuna di queste varianti ha raggiunto un'adozione diffusa o è stata presa in considerazione da NIST, in parte perché l'analisi della sicurezza quantistica delle varianti di CSIDH è ancora in evoluzione e meno matura rispetto a quella degli schemi basati su reticoli.

CSIDH e SIDH differiscono sotto aspetti fondamentali. Commutatività: CSIDH utilizza un'azione commutativa di gruppo (il gruppo delle classi); SIDH è uno scambio di chiavi non interattivo basato su isogenie non commutative e punti di torsione ausiliari. Campo di base: CSIDH opera su Fp, mentre SIDH opera su Fp2 (un'estensione quadratica). Dimensione della chiave pubblica: CSIDH occupa 64 byte (un singolo j-invariant su Fp), mentre SIDH occupava 324+ byte (una curva e due punti su Fp2). Sicurezza: CSIDH ha resistito all'attacco di Castryck-Decru, mentre SIDH è stato compromesso. Sicurezza quantistica: CSIDH richiede primi di 5000 bit per una sicurezza quantistica di 128 bit; prima della rottura classica, SIDH offriva una resistenza quantistica comparabile. Prestazioni: CSIDH-512 richiede circa 1-5 ms; SIDH aveva prestazioni simili, ma CSIDH-5000 sarebbe molto più lento.

La commutatività di CSIDH consente uno scambio di chiavi non interattivo (NIKE): Alice pubblica E_A = a * E0, mentre Bob pubblica E_B = b * E0. In seguito, senza alcuna ulteriore comunicazione, chiunque può calcolare il segreto condiviso a partire da una delle due chiavi pubbliche: Alice calcola a * E_B = a * (b * E0) = ab * E0, mentre Bob calcola b * E_A = b * (a * E0) = ab * E0. Questa proprietà NIKE è preziosa nelle applicazioni in cui uno scambio interattivo di chiavi non è praticabile, per esempio nella cifratura delle email, quando mittente e destinatario non sono online contemporaneamente. La NIKE di CSIDH è analoga alla NIKE di Diffie-Hellman, ma è post-quantistica. ML-KEM (basato su LWE) non supporta naturalmente la NIKE senza una progettazione aggiuntiva del protocollo.

CSIDH non è stato standardizzato e non è ancora utilizzato nei sistemi di produzione. È un tema di ricerca attivo, con implementazioni disponibili: CTIDH (a tempo costante), csidh-reference (Python, a scopo didattico) e supersingular-isogeny-toolbox (C ottimizzato). Il principale ostacolo all'adozione è la sicurezza quantistica: si stima che i 62-72 bit di sicurezza quantistica di CSIDH-512 siano inferiori al livello NIST Level 1 (128 bit), rendendolo inadatto alle applicazioni post-quantistiche che richiedono la conformità agli standard NIST. CSIDH-5000 raggiungerebbe il livello di sicurezza richiesto, ma sarebbe molto più lento. La ricerca prosegue per migliorare l'analisi della sicurezza quantistica e sviluppare varianti in grado di colmare questa lacuna, ma nel 2024 CSIDH rimane un primitivo di ricerca, non ancora pronto per la distribuzione.

Perché l'azione commutativa del gruppo delle classi di CSIDH consente uno scambio di chiavi non interattivo?

CSIDH utilizza l'azione commutativa del gruppo delle classi Cl(Z[pi]) su curve supersingolari su Fp, dove pi è l'endomorfismo di Frobenius. Le chiavi pubbliche sono singoli j-invariant (64 byte). Non vengono pubblicati punti di torsione ausiliari, evitando la vulnerabilità di SIDH. L'azione del gruppo delle classi è commutativa e consente la NIKE. Il miglior attacco classico ha complessità O(p^{1/4}); il miglior attacco quantistico (Kuperberg) ha tempo subesponenziale L(1/2) e richiede primi di 5000 bit per una sicurezza quantistica di 128 bit. CTIDH offre un'implementazione a tempo costante. CSIDH-512 offre soltanto circa 65 bit di sicurezza quantistica. CSIDH non è standardizzato; la ricerca si concentra su varianti che migliorino la resistenza quantistica mantenendo chiavi compatte.