Isogenie delle curve ellittiche: fondamenti matematici

Un'isogenia tra due curve ellittiche E ed E' su un campo k è una mappa razionale non costante phi: E -> E' che è anche un omomorfismo di gruppi: trasferisce la legge di gruppo di E alla legge di gruppo di E'. Ogni isogenia phi ha un'isogenia duale phi_hat: E' -> E tale che phi_hat composta con phi equivale alla moltiplicazione per deg(phi) su E. Il grado di un'isogenia è la cardinalità del suo nucleo: un'isogenia di grado l ha un nucleo di cardinalità l. Le isogenie generalizzano la moltiplicazione scalare: la moltiplicazione per n è un'isogenia da E a sé stessa di grado n^2. Le isogenie su campi finiti si calcolano come funzioni razionali (polinomi) che possono essere valutate in modo efficiente.

Le formule di Velu (1971) forniscono formule esplicite per calcolare un'isogenia phi: E -> E/G dato un sottogruppo G di E. La curva immagine E/G = E' e la mappa razionale phi sono completamente determinate da G. Le formule di Velu calcolano i coefficienti della curva immagine e la mappa razionale come funzioni razionali di grado pari a |G|. Per un sottogruppo nucleo G di ordine primo l, l'isogenia ha grado l e può essere calcolata con O(l) operazioni. Gli algoritmi sqrt-Velu (Bernstein et al., 2019) riducono questo costo a O(sqrt(l)) operazioni per valori grandi di l, rendendo possibili le isogenie efficienti di primo grande di CSIDH. Le formule di Velu sono lo strumento computazionale fondamentale di tutta la crittografia basata sulle isogenie.

Le curve ellittiche su un campo finito Fp possono essere organizzate in un grafo di isogenie. I vertici sono j-invarianti di curve ellittiche (un invariante canonico che determina la curva a meno di isomorfismo). Gli archi sono isogenie di grado l: ogni curva ordinaria ha esattamente l+1 isogenie di grado l uscenti per un primo l piccolo (per la struttura dei sottogruppi di l-torsione). Il grafo delle isogenie di grado l su Fp è un grafo (l+1)-regolare. La proprietà di Ramanujan di questi grafi (grafi espansori) fa sì che le passeggiate aleatorie si mescolino rapidamente, fornendo l'ipotesi di difficoltà alla base della crittografia basata sulle isogenie: passeggiate aleatorie di lunghezza O(log p) producono distribuzioni uniformi sugli j-invarianti.

Le curve ellittiche su Fp rientrano in due categorie. Le curve ordinarie hanno un p-rank non nullo, il che significa che esistono p^2 classi di isomorfismo e un grafo complesso di isogenie con una struttura a vulcano (crateri e livelli inferiori). Le curve supersingolari hanno p-rank pari a 0 e appartengono tutte a un unico grafo connesso di isogenie su Fp2. Il numero di j-invarianti supersingolari su Fp è approssimativamente p/12. SIDH e SIKE usano curve supersingolari perché il loro grafo di isogenie è un grafo di Ramanujan con forti proprietà di espansione e privo di una struttura a vulcano che potrebbe rivelare la direzione della passeggiata. Anche CSIDH usa curve supersingolari, ma su Fp (non su Fp2), sfruttando una struttura algebrica diversa.

La crittografia basata sulle isogenie si fonda su due problemi difficili correlati. Problema delle isogenie supersingolari (SSIP): date due curve ellittiche supersingolari E ed E' su Fp2, trovare un'isogenia phi: E -> E'. Problema computazionale delle isogenie supersingolari (CSSI): dati E, E' = phi(E) e il grado di phi, trovare phi. Il miglior algoritmo classico per SSIP richiede O(p^{1/4}) tempo. Il miglior algoritmo quantistico (ricerca di collisioni di Tani) richiede O(p^{1/6}) tempo. Per p = 2^{434}, ciò corrisponde a 128 bit di sicurezza classica. Si tratta di accelerazioni quantistiche significativamente inferiori rispetto all'accelerazione esponenziale dell'algoritmo di Shor contro RSA/ECC, rendendo gli schemi basati sulle isogenie sicuri post-quantisticamente.

SIDH (Supersingular Isogeny Diffie-Hellman) usa un primo appositamente strutturato p = 2^a * 3^b - 1, che garantisce che la curva E su Fp2 disponga di punti di 2^a-torsione (l'insieme dei punti P tali che 2^a * P = 0) e di punti di 3^b-torsione accessibili. Il segreto di Alice è un'isogenia di grado 2^a phi_A: E -> E_A, il cui nucleo è generato da un elemento casuale della 2^a-torsione. Il segreto di Bob è un'isogenia di grado 3^b phi_B: E -> E_B. Si scambiano le immagini dei punti di torsione: Alice pubblica E_A e phi_A(P_B), phi_A(Q_B). Bob pubblica E_B e phi_B(P_A), phi_B(Q_A). Ciò consente a ciascuna parte di calcolare isogenie a partire dalla curva dell'altra, arrivando allo stesso j-invariante condiviso.

L'anello degli endomorfismi End(E) di una curva ellittica è l'anello di tutte le isogenie da E a sé stessa (incluse le moltiplicazioni scalari). Per le curve ordinarie su Fp, End(E) è un ordine in un campo quadratico immaginario. Per le curve supersingolari, End(E) è un ordine massimale in un'algebra quaternionica ramificata in p e all'infinito. La struttura di End(E) determina completamente la curva a meno di isomorfismo. Il problema dell'anello degli endomorfismi, cioè il calcolo di End(E) dato E, è ritenuto difficile (equivalente a SSIP per le curve supersingolari). L'attacco di Castryck-Decru contro SIDH/SIKE ha sfruttato informazioni aggiuntive divulgate dal protocollo SIDH per ricostruire efficientemente parte dell'anello degli endomorfismi, compromettendo lo schema.

Un'isogenia di grado l phi: E -> E' può essere rappresentata da un polinomio di grado l (o l/2 dopo un'ottimizzazione per simmetria che sfrutta il fatto che gli inversi dei punti hanno la stessa coordinata x). Calcolare phi(P) per un dato punto P richiede O(l) moltiplicazioni usando le formule di Velu. Per SIDH con l = 2^a intorno a 2^216, questo sembra proibitivo, ma SIDH sfrutta il fatto che le isogenie di grado 2^a possono essere scomposte in una catena di a singole 2-isogenie: ogni 2-isogenia è economica e una catena di a passaggi produce un'isogenia di grado 2^a. Lo stesso vale per 3^b. sqrt-Velu consente di eseguire i calcoli delle isogenie di primo dispari grande di CSIDH in O(sqrt(l)) invece di O(l), rendendo CSIDH pratico.

SIKE (Supersingular Isogeny Key Encapsulation) era un candidato alla competizione PQC del NIST che aveva superato tutti i round fino al quarto, quando è stato compromesso. SIKE si distingueva per le dimensioni delle chiavi più ridotte tra tutti i candidati NIST: 374 byte per SIKEp434 (livello 1 NIST). Per confronto, ML-KEM-512 ha chiavi pubbliche da 800 byte. SIKE raggiungeva questa compattezza perché il segreto condiviso deriva da un singolo j-invariante (un elemento del campo di circa 430 bit). La compattezza aveva però un costo: SIKE era da 100 a 1000 volte più lento degli altri candidati. Quando Castryck e Decru hanno violato SIKE nel luglio 2022 usando un attacco classico eseguibile in pochi minuti su un computer portatile, SIKE è stato immediatamente eliminato dalla competizione NIST.

La crittografia basata sulle isogenie occupa una posizione unica tra gli approcci post-quantistici. Dimensioni delle chiavi: molto inferiori a quelle della crittografia reticolare (ML-KEM: oltre 800 byte) o delle firme basate su hash (SLH-DSA: chiave pubblica da 32-49 byte, ma firme da 7856-49856 byte). Prestazioni: molto inferiori a quelle di tutte le alternative (SIKE era da 100 a 1000 volte più lento di ML-KEM). Ipotesi di sicurezza: distinta da LWE (usato in ML-KEM/ML-DSA), SIS e dalle funzioni hash, e quindi fonte di diversità crittografica. Base della sicurezza post-quantistica: il problema del percorso delle isogenie non ha alcun algoritmo quantistico noto in tempo polinomiale, a differenza di RSA/ECC, che l'algoritmo di Shor rompe completamente. La violazione classica di SIKE dimostra che la difficoltà delle isogenie è ancora oggetto di studio, a differenza del problema LWE, ampiamente studiato.

Nonostante la violazione di SIKE, la crittografia basata sulle isogenie rimane un'area di ricerca attiva. SQISign (Short Quaternion and Isogeny Signature) è uno schema di firma basato sulle isogenie con firme da 177 byte (rispetto ai 2420 byte di ML-DSA per il livello 2): le firme PQC più piccole note. SQISign usa il problema difficile del calcolo di un'isogenia di grado prescritto tra due curve supersingolari date, formalizzato come problema dell'anello degli endomorfismi. FESTA (Fast Encryption from Supersingular Torsion Attacks) è un nuovo progetto KEM che evita i dati ausiliari aggiuntivi sui punti di torsione che avevano reso SIDH vulnerabile. CTIDH (Constant-Time CSIDH) migliora le prestazioni di CSIDH. Questi schemi mantengono rilevante la ricerca sulle isogenie anche dopo l'eliminazione di SIKE.

Che cos'è un'isogenia tra curve ellittiche?

Un'isogenia è una mappa razionale phi: E -> E' che è un omomorfismo di gruppi, con grado pari alla cardinalità del suo nucleo. Le formule di Velu calcolano la curva immagine e la mappa a partire dal sottogruppo nucleo. I grafi di isogenie organizzano le curve come vertici con archi corrispondenti a isogenie di grado l, formando grafi di Ramanujan (l+1)-regolari. Le curve supersingolari (usate in SIDH/SIKE/CSIDH) hanno grafi di isogenie con una forte espansione. I problemi SSIP e CSSI sono alla base della sicurezza delle isogenie. SIDH usa la struttura dei punti di torsione con catene alternate di 2-isogenie e 3-isogenie. Il calcolo dell'anello degli endomorfismi è equivalente a SSIP. SQISign e FESTA rappresentano direzioni attive della ricerca post-SIKE che sfruttano la difficoltà dell'anello degli endomorfismi.