Le applicazioni delle isogenie nella Post Quantum Cryptography

14 Lug 2025

Dopo aver introdotto la teoria delle curve ellittiche e aver definito gli strumenti necessari, presentiamo alcuni schemi classici della crittografia basata su isogenie. Come anticipato nell’articolo precedente, questo giovane campo della crittografia post-quantum è nato agli inizi degli anni 2000 grazie agli studi di Couveignes, Teske, Rostovtsev e Stolbunov. Nella decade successiva si è assistito ad un incremento dell’attenzione della comunità crittografica e, in seguito alle proposte alle call del NIST nel 2016 e 2023, oggi possiamo affermare che la crittografia basata su isogenie ha raggiunto una maturità molto promettente nel panorama post-quantum.

La funzione di Hash CGL

Nel 2006 Charles, Goren e Lauter presentano una funzione di hash $H_{\mathrm{CGL}}$ resistente alle collisioni la cui sicurezza è basata sul Problema $2$ –IsogenyPath.

Ricordiamo che una funzione di hash è un algoritmo che prende in input una stringa di lunghezza arbitraria e restituisce un output di lunghezza fissata. Una hash $H$ è detta resistente alle collisioni se è computazionalmente intrattabile trovare $x$ e $y$ distinti per cui $H(x)=H(y)$ .

L’idea è utilizzare i bit del messaggio di cui si vuole calcolare l’hash come guida per esplorare un isogeny graph. La funzione di hash $H_{\mathrm{CGL}}$ sfrutta una particolare proprietà di tali grafi: a meno di dover trattare i vertici corrispondenti ai $j$ -invarianti 0 e 1728, la componente supersingolare dell’isogeny graph di grado $\ell$ si dimostra essere $\ell+1$ -regolare, ovvero ogni vertice ha $\ell+1$ archi. Il $j$ -invariante del vertice di arrivo del cammino sarà l’hash del messaggio.

Le applicazioni delle isogenie nella Post Quantum Cryptography Componente supersingolare di un isogeny graph di grado 3 — Componente supersingolare di un isogeny graph di grado 3

Si inizia dunque scegliendo la componente supersingolare di un isogeny graph di grado 2. Tra i parametri della funzione di hash vi sono il grafo, un vertice $V_0$ — che sarà il punto di partenza del cammino — e due dei suoi tre archi $e_0^{(0)},e_1^{(0)}$ .

Per calcolare l’output di $H_{\mathrm{CGL}}$ su un messaggio $m$ , i cui bit sono $(m_0,\dots,m_N)$ , si procede come segue:

ci si sposta dal vertice $V_0$ al vertice $V_1$ , definito come il secondo vertice dell’arco $e_{m_0}^{(0)}$ . Dalla regolarità del grafo il vertice $V_1$ ha tre archi: $e_{m_0}^{(0)}$ , appena percorso, ed altri due, denotati $e_{0}^{(1)}$ e $e_{1}^{(1)}$ .
Iterativamente, per ogni $i=1,\dots,N$ , il bit $m_i$ determina l’arco $e_{m_i}^{(i)}$ da $V_{i-1}$ da percorrere, ottenendo così l’ $i$ -esimo vertice $V_i$ del cammino.
Una volta esauriti i bit del messaggio $m$ , l’output della funzione di hash è definito come il $j$ -invariante del vertice di arrivo, ovvero $H_{\mathrm{CGL}}(m)=V_{N+1}$

In questo modo si esplora l’isogeny graph in modo deterministico utilizzando i bit del messaggio di input. Come anticipato, il Problema $2$ –IsogenyPath assicura la resistenza alle collisioni di $H_{\mathrm{CGL}}$ : intuitivamente, trovare una collisione equivale a trovare due stringhe di bit che, utilizzate nell’esplorazione dell’isogeny graph, raggiungono lo stesso vertice. Fissando uno dei due cammini, individuare l’altro significa produrre una isogenia di grado una potenza di 2 tra due curve ellittiche fissate, ovvero esattamente il Problema $2$ –IsogenyPath.

Le buone proprietà degli isogeny graphs non garantiscono solo che $H_{\mathrm{CGL}}$ soddisfi le proprietà di sicurezza che definiscono una funzione di hash, ma anche condizioni ulteriori che la rendono particolarmente interessante da un punto di vista pratico. Ad esempio, $H_{\mathrm{CGL}}$ produce output uniformemente distribuiti nell’isogeny graph di grado 2. Ciò segue dal fatto che negli isogeny graphs cammini casuali convergono molto velocemente alla distribuzione uniforme. Più precisamente, il vertice finale di un cammino in un isogeny graph tende alla distribuzione uniforme dopo un numero di passi logaritmico nel numero di vertici del grafo.

Scambio di chiavi

Un’altra applicazione che ha portato interesse nella crittografia basata su isogenie è la possibilità di effettuare uno scambio di chiavi sul modello del Diffie-Hellman.

Supponiamo che Alice e Bob vogliano ottenere un segreto condiviso. Dopo aver concordato una curva ellittica comune $E_0$ , scelgono le loro isogenie segrete $\phi_A$ e $\phi_B$ e calcolano le rispettive chiavi pubbliche come $E_A=\phi_A(E_0)$ e $E_B=\phi_B(E_0)$ . Il classico Diffie-Hellman prevederebbe che, da questo scambio di informazioni, le due parti fossero in grado di calcolare un segreto condiviso, che nel nostro caso sarà il $j$ -invariante di una curva $E$ . Per instanziare una versione di Diffie-Hellman basata su isogenie sono però necessarie alcune modifiche.

Le due proposte pratiche: SIDH e CSIDH

Nel 2011 De Feo, Jao e Plût propongono lo scambio chiavi SIDH (Supersingular Isogeny Diffie-Hellman) che verrà successivamente presentato alla call del NIST con il nome SIKE (Supersingular Isogeny Key Encapsulation). In SIDH, per permettere alla controparte di calcolare il segreto condiviso $E$ , oltre alle curve $E_A$ ed $E_B$ , sia Alice sia Bob devono pubblicare l’immagine di alcuni punti tramite la loro isogenia privata. Nonostante per più di una decade i protocolli siano stati ritenuti sicuri anche contro avversari quantistici, nel 2023 le ulteriori informazioni pubblicate sono state alla base di attacchi non quantistici a SIDH e SIKE. Tali attacchi impiegano tecniche fino ad allora inesplorate nella crittografia basata su isogenie e, sorprendentemente, queste stesse tecniche sono state in seguito utilizzate in modo costruttivo per progettare nuovi schemi.

Un altro approccio al problema è quello di limitare le possibili curve ellittiche considerate, in modo tale da poter calcolare il segreto comune senza la necessità di pubblicare ulteriori informazioni. Nel 2018 Castryck, Lange, Martindale, Panny e Renes pubblicano lo scambio di chiavi CSIDH [1] (Commutative SIDH) che rielabora il protocollo utilizzando il linguaggio delle azioni di gruppo commutative. In particolare, si considerano solo curve ellittiche supersingolari definite su un certo sottocampo sulle quali agisce il cosiddetto ideal class group. Questo setting, oltre ad aver reso pratico lo scambio di chiavi à la Diffie-Hellman, ha agevolato diverse costruzioni tra cui le firme digitali.

Firme digitali

La costruzione di firme digitali a partire da assunzioni basate su isogenie risale allo studio teorico effettuato nel 2012 da Stolbunov che, dopo aver presentato uno schema di identificazione, trasforma quest’ultimo in una firma digitale attraverso il paradigma di Fiat-Shamir.

Lo schema di identificazione presentato da Stolbunov è la base delle successive firme SeaSign (2018) e CSI-FiSh (2019) ed è ispirato al protocollo del 1991 di Goldreich, Micali e Wigderson per provare la conoscenza di un isomorfismo tra due grafi pubblici. Analogamente, Stolbunov pubblica un protocollo a tre passi che permette ad un Prover di mostrare ad un Verifier la conoscenza di una isogenia segreta tra due curve ellittiche pubbliche. Questa proposta basa la propria sicurezza sull’azione dell’ideal class group in un modo analogo a CSIDH. Al tempo, il suo interesse è risultato più teorico che pratico, in quanto per instanziare il protocollo è necessaria la conoscenza della struttura dell’ideal class group, cosa non ovvia per parametri di interesse crittografico.

SeaSign e CSI-FiSh: le firme basate su CSIDH

Nel 2018 dopo la pubblicazione di CSIDH, De Feo e Galbraith pubblicano SeaSign [2], una instanziazione della firma presentata da Stolbunov che utilizza gli strumenti messi a disposizione da CSIDH. La struttura dell’ideal class group non è ancora nota, ma questo problema tecnico viene superato con l’ausilio del paradigma Fiat-Shamir with aborts, utilizzato anche nella firma CRYSTALS-Dilithium. Questa tecnica permette di ottenere una firma digitale sì implementabile, ma ancora non del tutto utilizzabile: i tempi di firma e verifica sono infatti nell’ordine dei minuti.

Nel 2019 Beullens, Kleinjung e Vercauteren, in seguito a quella che è stata definita come record computation, calcolano la struttura dell’ideal class group utilizzato in CSIDH e pubblicano CSI-FiSh (Commutative Supersingular Isogeny based Fiat-Shamir), la naturale evoluzione di SeaSign che non ha la necessità di ricorrere alle operazioni di abort. Questo si traduce in un protocollo più performante e snello, con tempi sull’ordine delle centinaia di millisecondi: le firme basate su isogenie si stanno quindi sempre di più avvicinando ad essere pratiche ed utilizzabili.

[1] pronunciato “Seaside”, in quanto gli autori hanno iniziato a lavorarci mentre erano vicino una ben nota grande massa di acqua salata (https://csidh.isogeny.org)
[2] sia il nome sia la sua pronuncia sono una citazione a CSIDH (Seaside).

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.