La matematica dietro la PQC: Isogenie di Curve Ellittiche

19 Mag 2025

La crittografia basata sulle curve ellittiche

Dopo aver presentato i principali algoritmi di PQC definiti su reticoli, codici, funzioni di hash e sistemi multivariati, nel presente articolo ci si focalizzerà sul tema delle isogenie di curve ellittiche, sulle quali sono costruiti alcuni schemi partecipanti ai processi di standardizzazione del NIST.

L’applicazione delle curve ellittiche alla crittografia ha preso avvio nel corso degli anni ’80, quando Miller e Koblitz proposero di costruire una variante dello scambio chiave Diffie-Hellman (fino a quel momento costruito su campi finiti) basata su tali oggetti matematici. Il risultato, denominato ECDH (Elliptic-Curve Diffie-Hellman), è caratterizzato da ottime performance e ridotta dimensione delle chiavi ed è ancora oggi la variante di scambio chiave DH maggiormente utilizzata. Intorno all’anno 2000, inoltre, ha iniziato a svilupparsi l’idea di costruire schemi crittografici a partire dalle isogenie di curve ellittiche (che come verrà definito più avanti sono funzioni tra curve ellittiche), in particolare attraverso i lavori di Couveignes, Teske, Rostovtsev e Stolbunov. L’interesse nei confronti delle isogenie e della loro applicabilità nello sviluppo di algoritmi di PQC è poi aumentato a partire dal 2010, ricevendo un significativo impulso dall’avvio delle iniziative indette dal NIST nel 2016 e 2023.

Si può quindi notare come, se paragonati con i crittosistemi basati sui problemi matematici descritti nei precedenti articoli di questa rubrica, gli schemi crittografici costruiti a partire dalle isogenie di curve ellittiche risultino di più recente sviluppo e siano quindi in generale caratterizzati da una più breve storia di analisi crittoanalitica. La minor quantità di ricerca volta ad indagare possibili vulnerabilità degli algoritmi di isogeny-based cryptography aumenta il rischio di nuovi attacchi che possono ridurre o compromettere completamente la sicurezza di tali schemi: un esempio emblematico in tal senso è rappresentato da quanto successo a SIKE, KEM basato sulle isogenie di curve ellittiche partecipante alla prima call del NIST sul tema della PQC, la cui sicurezza è stata completamente compromessa da un attacco presentato nel 2022 da Castryck e Decru.

La totale compromissione di SIKE, unico schema basato sulle isogenie ancora in valutazione a quel punto, ha avuto un significativo impatto mediatico e ha sicuramente rappresentato un duro colpo per la isogeny-based cryptography. Bisogna però ricordare che l’attacco in questione non è applicabile a tutti gli schemi basati sulle isogenie e che vi sono ad oggi altri importati crittosistemi appartenenti a tale famiglia e ritenuti sicuri, tra cui si possono citare CSIDH (scambio chiave) e SQIsign, algoritmo di firma digitale che è stato ammesso al secondo round del processo di standardizzazione NIST avviato nel 2023.

La maggiore immaturità della isogeny-based cryptography la rende quindi una scelta meno conservativa, specialmente se confrontata con schemi basati sui reticoli o sui codici a correzione d’errori. Nonostante ciò, i crittosistemi basati sulle isogenie di curve ellittiche hanno riscosso notevole attenzione da parte della comunità crittografica, soprattutto grazie al fatto che tali algoritmi sono caratterizzati da chiavi pubbliche e firme di dimensioni estremamente contenute, che ne permetterebbero l’utilizzo in ambiti in cui ci sono forti restrizioni sulla larghezza di banda. L’applicabilità di schemi isogeny-based in tali contesti, però, è ancora limitata dalle scarse performance di tali algoritmi, che risultano peggiori non solo di quanto garantito da ECDH, ma anche dalle prestazioni delle altre famiglie di crittosistemi.

Isogenie di curve ellittiche

Per semplicità, presentiamo gli oggetti coinvolti tramite le loro definizioni operative.
Sia $\mathbb{K}$ un campo; a meno di condizioni tecniche su $\mathbb{K}$ , una curva ellittica $E$ definita su $\mathbb{K}$ è l’insieme dei punti $(x,y)$ che soddisfano la cosiddetta equazione di Weierstrass

$y^2 = x^3 + ax +b,\quad a,b\in\mathbb{K}\quad\text{e}\quad 4a^3+27b^2\neq0,$

con l’aggiunta di un punto speciale $\mathcal{O}$ , detto punto all’infinito. La natura di una curva ellittica dipende dal campo su cui è definita. Ad esempio, nella figura seguente si possono osservare curve ellittiche definite dalla stessa equazione di Weierstrass su campi diversi.

La matematica dietro la PQC Isogenie di Curve Ellittiche fig1 — $y^2=x^3-3x+3$ su $\mathbb{R}$

La matematica dietro la PQC Isogenie di Curve Ellittiche fig2 — $y^2=x^3-3x+3$ su $\mathbb{F}_{401}$

Il $j$ -invariante di una curva ellittica $E$ definita come sopra è

$j(E) = \frac{4a^3}{4a^3 + 27b^2}1728.$

È possibile definire su $E$ una operazione $+$ che rende l’insieme dei suoi punti un gruppo commutativo con elemento neutro il punto all’infinito $\mathcal{O}$ . Denotiamo la somma $m$ -volte di un punto $P\in E$

$[m]P:=\underbrace{P+...+P}_{m\text{ volte}}.$

Su tale struttura algebrica è basata la crittografia “classica” su curve ellittiche, come ad esempio ECDH. La chiave pubblica di uno schema classico è essenzialmente costituita da una coppia di punti $(P,Q)$ in $E$ e la chiave segreta da un intero $m$ tale che $Q=[m]P$ .

Nella crittografia basata su isogenie avviene un sostanziale cambio di prospettiva: gli oggetti manipolati non sono più punti di una curva ellittica fissata, ma l’insieme delle curve ellittiche. La chiave pubblica è ora una coppia di curve ellittiche $(E_1,E_2)$ e la chiave segreta una certa mappa tra $E_1$ ed $E_2$ , detta isogenia.

Una isogenia $\phi:E_1\rightarrow E_2$ è una mappa tra curve ellittiche $E_1$ ed $E_2$ che ne rispetta la struttura, in particolare

per ogni coppia di punti $P,Q$ in $E_1$ vale che $\phi(P+Q)=\phi(P)+\phi(Q)$ ;
$\phi(\mathcal{O}_1)=\mathcal{O}_2$ , dove $\mathcal{O}_1$ e $\mathcal{O}_2$ sono i punti all’infinito di $E_1$ e $E_2$ , rispettivamente.

Un isomorfismo è una isogenia che ammette una mappa inversa. Il $j$ -invariante identifica una curva ellittica a meno di isomorfismi, ovvero, due curve ellittiche definite su $\mathbb{K}$ hanno lo stesso $j$ -invariante se e solo se tra di loro esiste un isomorfismo.

Una isogenia da $E$ in se stessa è detta endomorfismo; l’insieme degli endomorfismi di una curva ellittica $E$ – insieme alla mappa nulla – possiede una struttura di anello ed è indicato con $\text{End}(E)$ . Un esempio di endomorfismo è la somma $m$ -volte $[m]$ definita precedentemente; poiché la famiglia $\{[m]\,:\, m\in\mathbb{Z}\}$ appartiene ad $\mathrm{End}(E)$ per ogni curva ellittica $E$ , tali mappe sono dette endomorfismi banali.

Ad ogni isogenia $\phi$ è associato un intero positivo $\deg\phi$ , detto grado, che nei casi di interesse crittografico coincide con la cardinalità del kernel di $\phi$ , ovvero l’insieme dei punti mappati nel punto all’infinito da $\phi$ .

Un approccio visivo: Isogeny Graphs

Le relazioni tra curve ellittiche e isogenie possono essere rappresentate mediante un grafo, chiamato in letteratura isogeny graph.

Dato un campo $\mathbb{K}$ e fissato un intero $\ell$ , l’isogeny graph di grado $\ell$ è il grafo $\mathcal{G}_{\mathbb{K},\ell}=(V,A)$ avente come vertici $V$ l’insieme delle curve ellittiche a meno di isomorfismi e tra due vertici $(E_1,E_2)$ esiste un arco se e solo se tra le due curve esiste una isogenia di grado $\ell$ .

Nella pratica, le classi di isomorfismo di curve ellittiche che costituiscono i vertici di un isogeny graph sono rappresentate tramite il loro $j$ -invariante.

Le figure seguenti rappresentano due componenti connesse dell’isogeny graph di grado 3 sul campo $\mathbb{F}_{401^2}$ .

La matematica dietro la PQC Isogenie di Curve Ellittiche fig3 — Componente ordinaria

La matematica dietro la PQC Isogenie di Curve Ellittiche fig4 — Componente supersingolare

Nella figura di sinistra si nota una forte simmetria mancante in quanto rappresentato a destra. Ciò si deve alla diversa natura delle curve ellittiche coinvolte: nella prima, i nodi corrispondono a $j$ -invarianti di curve dette ordinarie; nella seconda, a $j$ -invarianti di curve dette supersingolari. Una curva ellittica $E$ è definita ordinaria se $\mathrm{End}(E)$ è commutativo; altrimenti, è detta supersingolare.

Isogenie e problemi difficili

La sicurezza degli schemi a chiave pubblica è basata su problemi computazionali ritenuti intrattabili. La teoria delle isogenie di curve ellittiche fa sorgere problemi congetturati essere difficili anche per una macchina quantistica.

Il problema principale della crittografia basata su isogenie è il cosiddetto Problema Isogeny: date due curve ellittiche $E$ ed $E'$ definite su $\mathbb{K}$ , trovare, se esiste, una isogenia $\phi:E\rightarrow E'$ .

Diversi crittosistemi su isogenie si basano su una sua variante, detta $\ell$ –IsogenyPath, in cui si cerca una isogenia di grado fissato. Formalmente, date due curve ellittiche $E$ ed $E'$ definite su $\mathbb{K}$ e un numero primo $\ell$ , il problema chiede di trovare, se esiste, una isogenia $\phi:E\rightarrow E'$ tale che $\phi=\phi_1\circ...\circ \phi_n$ con $\deg\phi_i=\ell$ per $i=1,..,n$ .

Il nome del problema deriva dal fatto che una sua soluzione è equivalente a trovare un cammino di lunghezza $n$ nell’isogeny graph di grado $\ell$

$E=E_1\xrightarrow{\; \phi_1\; } E_2\xrightarrow{\; \phi_2\; }\cdots \xrightarrow{\phi_{i-1}}E_i\xrightarrow{\; \phi_i\; }E_{i+1}\xrightarrow{\phi_{i+1} }\cdots \xrightarrow{\; \phi_{n}\; }E_{n+1}=E'.$

La formulazione di questi problemi dà una prima intuizione del perché in crittografia siano utilizzate principalmente curve ellittiche supersingolari: la mancanza di una chiara struttura nel grafo rende infatti la ricerca di tali percorsi più complessa.

Storicamente, è stata studiata una seconda categoria di problemi provenienti dalla teoria delle isogenie, la quale riguarda l’anello degli endomorfismi. A questa classe appartiene il Problema EndRing in cui, data una curva ellittica $E$ definita su $\mathbb{K}$ , si chiede di calcolare $\mathrm{End}(E)$ .

Infine, sono state recentemente definite primitive crittografiche che basano la loro sicurezza sull’assunzione che trovare anche un solo endomorfismo non banale sia difficile. Questo si formalizza nel Problema OneEnd, in cui è richiesto di calcolare una isogenia $\phi:E\to E$ diversa da $[m]$ per ogni intero $m$ .

In realtà, le due classi di problemi qui presentate sono più connesse di quanto possa apparire. Infatti, è stato sorprendentemente dimostrata l’equivalenza dei problemi Isogeny, EndRing e OneEnd.

Su quest’ultimo problema basa la propria sicurezza la firma digitale SQIsign, l’unica proposta basata su isogenie presentata alla call per la standardizzazione post-quantum indetta dal NIST nel 2023, che verrà presentato nel prossimo articolo della rubrica.

Questo articolo appartiene ad una serie di contributi, a cura del Gruppo di Ricerca in Crittografia di Telsy, dedicata al calcolo quantistico e alle sue implicazioni sulla Crittografia. Per la consultazione di altri articoli si rimanda all’indice della rubrica.

Per altri articoli relativi ai temi Quantum e Crittografia si rimanda alle relative categorie nel blog.

Gli autori

Elena Broggini, laureata magistrale in Scienze Matematiche presso l’Università degli Studi di Milano. Attualmente è una studentessa di dottorato del gruppo Teoria dei Numeri e Crittografia presso il Politecnico di Torino con una borsa a tema Crittografia Post-Quantum e Fully Homomorphic Encryption in collaborazione con il gruppo di ricerca di Telsy.

Giuseppe D’Alconzo, assegnista di ricerca presso il Politecnico di Torino, ha conseguito il suo dottorato in Matematica con una borsa a tema “Crittografia Post-Quantum” nell’ambito del programma UniversiTIM e in collaborazione con il Gruppo di Ricerca di Telsy. Laureato in Matematica con specializzazione in Crittografia presso l’Università di Trento, ha svolto nel 2019 uno stage presso Telsy, occupandosi di Multi-party Computation e Attribute Based Encryption.

Marco Rinaudo, laureato triennale in Matematica presso l’Università degli Studi di Torino e laureato magistrale con specializzazione in Crittografia presso l’Università di Trento. In seguito ad uno stage curricolare svolto nel 2022 in Telsy, da gennaio 2023 è parte del Gruppo di Ricerca in Crittografia.