SQIsign: la firma digitale basata su isogenie proposta al NIST

08 Set 2025

Introduzione

Tra le firme digitali presentate nel 2023 alla call del NIST nel processo di standardizzazione post-quantum, l’unica proposta basata su isogenie è SQIsign (Short Quaternion Isogeny Signature). Unico nel suo genere, questo protocollo garantisce una maggiore varietà nei possibili problemi computazionali resistenti ad un attacco quantistico; l’altra faccia della medaglia è la complessità della teoria matematica in cui si inseriscono le tecniche e gli oggetti coinvolti.

La sicurezza di SQIsign è basata sul Problema EndRing, che per curve ellittiche supersingolari è equivalente al Problema $\ell$ –IsogenyPath. Il legame tra questi due problemi è suggerito dagli isogeny graphs: cicli negli isogeny graphs determinano endomorfismi.

Più esplicitamente, ciò implica che, date due curve ellittiche con anello degli endomorfismi noto, è possibile calcolare una isogenia fra loro e, viceversa, data una isogenia del cui dominio è noto l’anello degli endomorfismi, è possibile calcolare anche l’anello degli endomorfismi della curva a codominio. La scelta standard di una curva di partenza $E_0$ di cui conosciamo $\mathrm{End}(E_0)$ è

$E_0: y^2=x^3-x,$

adottata anche nella firma.

SQIsign si basa su uno schema di identificazione in tre passi trasformato in una firma digitale attraverso il paradigma di Fiat-Shamir. La chiave pubblica del Prover consiste in una curva ellittica $E_{pk}$ e la chiave segreta nel suo anello degli endomorfismi $\mathrm{End}(E_{pk})$ . Essenzialmente, resa pubblica $E_{pk}$ , l’obiettivo del Prover è convincere il Verifier che ha conoscenza di $\mathrm{End}(E_{pk})$ .

La versione più recente del protocollo è stata presentata nel 2025 e utilizza in modo costruttivo le tecniche sfruttate per attaccare SIDH nel 2022. Grazie ad esse, è possibile rappresentare in modo più efficiente le isogenie coinvolte e migliorare così le performance dello schema di firma.

Panoramica del Protocollo di Firma

In SQIsign la chiave pubblica è una curva ellittica $E_{pk}$ e la chiave segreta $\mathrm{End}(E_{pk})$ . Per l’equivalenza tra i Problemi EndRing e $\ell$ –IsogenyPath, la conoscenza della chiave segreta è equivalente alla conoscenza di una isogenia

Lo schema di identificazione di cui SQIsign è la trasformata di Fiat-Shamir, permette al Prover di dimostrare al Verifier la sua conoscenza di $\mathrm{End}(E_{pk})$ . Si divide in tre passi ed può essere semplificato come segue:

Commitment: il Prover genera una isogenia $\phi_{com}: E_0\rightarrow E_{com}$ e invia la curva $E_{com}$ al Verifier. Ricordiamo che, per l’equivalenza tra EndRing e $\ell$ –PathProblem, il Prover conosce l’anello degli endomorfismi di $E_{com}$ .
Challenge: il Verifier risponde con una isogenia $\phi_{chl}: E_{pk}\rightarrow E_{chl}$ .
Response: dal momento che il Prover conosce $\mathrm{End}(E_{pk})$ e $\phi_{chl}: E_{pk}\rightarrow E_{chl}$ , è in grado di calcolare $\mathrm{End}(E_{chl})$ . La conoscenza di entrambi gli anelli $\mathrm{End}(E_{com})$ e $\mathrm{End}(E_{chl})$ permette al Prover di calcolare una isogenia $\phi_{rsp}: E_{com}\rightarrow E_{chl}$ , che viene inviata al Verifier.

Il Verifier accetta se $\phi_{rsp}$ è effettivamente una isogenia da $E_{com}$ a $E_{chl}$ e se $\phi_{chl}$ non è una componente della isogenia in risposta; rifiuta in caso contrario.

Verificare che la isogenia response non abbia come fattore la isogenia challenge è necessario per la sicurezza del protocollo. Infatti, un Prover disonesto — che non ha conoscenza di $\mathrm{End}(E_{pk})$ — può generare un commitment scegliendo una isogenia causale $\phi_{com}^{\textit{cheat}}: E_{pk}\rightarrow E_{com}$ . Senza $\mathrm{End}(E_{pk})$ il Prover non sarà in grado di calcolare $\mathrm{End}(E_{com})$ ma non è un ostacolo. Difatti, data la challenge $\phi_{chl}: E_{pk}\rightarrow E_{chl}$ , il Prover disonesto risponderà con

$\phi_{rsp}^{\textit{cheat}}:=\phi_{chl}\circ \widehat{\phi_{com}^{\textit{cheat}}}: E_{com}\longrightarrow E_{chl},$

dove $\widehat{\phi_{com}^{\textit{cheat}}}: E_{com}\rightarrow E_{pk}$ è la duale di $\phi_{com}^{\textit{cheat}}$ .

Se il Verifier non controllasse che la isogenia response non ha questa forma, il Prover disonesto supererebbe la verifica e SQIsign sarebbe banalmente insicuro.

Riassumendo, il Prover deve produrre una isogenia dalla curva inviata nel commitment (di cui conosce l’anello degli endomorfismi) ad una curva qualsiasi data dal codominio della challenge del Verifier. L’equivalenza tra EndRing e $\ell$ –PathProblem implica che ciò coincide con il conoscere l’anello degli endomorfismi di $E_{chl}$ . Essendo la challenge una isogenia dalla chiave pubblica del Prover a $E_{chl}$ , conoscere $\mathrm{End}(E_{chl})$ implica conoscere la chiave segreta $\mathrm{End}(E_{pk})$ .

La Matematica dell’Implementazione di SQIsign

L’implementazione di SQIsign è basata non solo sulla teoria delle curve ellittiche, ma anche su altre due famiglie di oggetti matematici, i quaternioni e le superfici abeliane.

Quaternioni

È ragionevole considerare i quaternioni nello studio delle curve ellittiche grazie ad una corrispondenza matematica, chiamata corrispondenza di Deuring, che permette di tradurre il mondo geometrico delle curve ellittiche nel mondo puramente algebrico dei quaternioni. Il passaggio ai quaternioni è necessario per la generazione della chiave e l’operazione di firma, mentre per la verifica si rimane nel contesto delle curve ellittiche.

I quaternioni possono essere pensati come una generalizzazione dei numeri complessi. Un numero complesso è dato da $a+bi$ , dove $i$ è la radice quadrata di $-1$ , ovvero $i^2=-1$ . In modo analogo, per definire i quaternioni si aggiunge, oltre alla radice $i$ di $-1$ , anche la radice $j$ di un primo negativo $-p$ , che in SQIsign è la caratteristica del campo (finito) di definizione delle curve ellittiche in oggetto. Operativamente, un quaternione può essere rappresentato da una quadrupla di numeri razionali. L’insieme di questi elementi forma la cosiddetta algebra di quaternioni, denotata $B_{p,\infty}$ .

La corrispondenza di Deuring afferma che gli anelli degli endomorfismi di curve ellittiche supersingolari corrispondono a particolari sottoinsiemi della algebra di quaternioni $B_{p,\infty}$ , detti ordini massimali. I quaternioni corrispondenti ad endomorfismi hanno il vantaggio di poter essere rappresentati da quadruple di numeri interi.

Tramite la corrispondenza di Deuring otteniamo un analogo dei problemi fondazionali della crittografia basata su isogenie in termini di quaternioni. Ad esempio, il Problema EndRing si traduce nel Problema MaxOrder che richiede, data una curva ellittica $E$ (definita su un campo di caratteristica $p$ ), di determinare esplicitamente l’ordine massimale di $B_{p,\infty}$ isomorfo a $\mathrm{End}(E)$ .

Sorprendentemente, gli analoghi quaternionici sono risolvibili in modo più efficiente rispetto ai problemi originari — mostrando quanto il mondo algebrico dei quaternioni sia più conveniente da un punto di vista computazionale. Ciò non inficia però la sicurezza della crittografia basata su isogenie perché la complessità risiede nel passaggio dalle isogenie ai quaternioni: tale conversione è infatti l’operazione computazionalmente più costosa del processo di firma di SQIsign.

Isogenie in Dimensione 2

L’utilizzo di isogenie tra superfici abeliane, la generalizzazione bidimensionale delle curve ellittiche, è una delle differenze più significative dell’ultima versione di SQIsign.

Le curve ellittiche sono oggetti geometrici di dimensione 1. La loro definizione può essere generalizzata ad ogni dimensione, arrivando così alla nozione di varietà abeliana; specializzando alla dimensione 2, otteniamo le superfici abeliane. Un esempio concreto è dato dal prodotto di due curve ellittiche; queste sono le superficie abeliane di maggiore interesse nel protocollo SQIsign.

Aumentare la dimensione permette di rappresentare ogni isogenia tra prodotti di curve ellittiche tramite l’immagine di alcuni punti. Questo è possibile grazie al Lemma di Kani, un risultato teorico risalente alla fine degli anni ’90, che essenzialmente permette di scrivere isogenie tra prodotti di curve ellittiche come matrici $2\times 2$ le cui entrate sono isogenie in dimensione 1.

Il Lemma di Kani è il punto cruciale degli attacchi a SIDH e SIKE del 2022 poiché permette di ricostruire una isogenia tra curve ellittiche “immergendola” in una isogenia tra superfici abeliane. Ciò significa ottenerla come una delle entrate della matrice $2\times 2$ che rappresenta una isogenia tra prodotti di curve ellittiche.

Il risultato di Kani era già noto nella letteratura matematica da più di vent’anni quando è stato sfruttato per questi attacchi. Ciò conferma uno degli aspetti più delicati di SQIsign e della crittografia basata su isogenie: la teoria matematica su cui si basano le assunzioni di sicurezza è profonda e sofisticata, e solo recentemente è diventata di interesse crittografico ed analizzata da questo punto di vista.

Performance

Le proprietà più attraenti di SQIsign sono senza dubbio le dimensioni di chiave pubblica e firma, entrambe minori degli schemi di firma post-quantum standardizzati dal NIST nel 2023, Falcon, CRYSTALS-Dilithium e SPHINCS+.

fig6_28 — Dimensione chiave pubblica e firma delle principali digital signatures

D’altro canto, come abbiamo visto nella sezione precedente, le operazioni da effettuare nei processi di generazione chiavi e di firma sono altamente non banali dovendo gestire quaternioni e isogenie di secondo grado. Questo implica che, nonostante negli ultimi anni la ricerca abbia migliorato di molto le prestazioni, queste sono ancora il tallone di Achille di SQIsign. Dato che la generazione delle chiavi viene effettuata offline e solo un numero limitato di volte, ci focalizziamo sul processo di firma. Rispetto alle firme su reticoli CRYSTALS-Dilithium e Falcon, per il primo livello di sicurezza (128 bit) SQIsign impiega un numero di cicli di svariati ordini di grandezza in più per firmare un messaggio.

Le tempistiche per la verifica, seppur ancora lontane dai competitor su reticoli, sono invece accettabili e rendono SQIsign una alternativa interessante in casi d’uso in cui sono necessarie la trasmissione e la verifica di un numero elevato di firme.

fig7_28 — Performance (misurata in cicli) delle operazioni di generazione chiavi, firma e verifica

Questo articolo appartiene a 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.