The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures

Il documento presenta un quadro generale per generalizzare lo schema di firma SQIsign mediante l'uso di strutture di livello, fornendo una nuova corrispondenza esplicita di Deuring per curve ellittiche supersingolari con tali strutture e risolvendo nuove equazioni di norma vincolate.

L'essenziale

Ecco una spiegazione del paper "SQInstructor" pensata per chiunque, usando metafore semplici e un linguaggio quotidiano.

Il Concetto di Base: Un Viaggio in Autostrada

Immagina il mondo della crittografia moderna come un enorme labirinto di autostrade. Per proteggere i nostri dati (come le password o i messaggi bancari), abbiamo bisogno di un modo per dimostrare di conoscere la strada senza rivelare l'intero percorso a chiunque.

Fino a poco tempo fa, la soluzione più compatta e sicura per questo era SQIsign. Funzionava un po' come un gioco di "indovina la strada":

1. Tu (il mittente) parti da un punto A.
2. Il controllore (il destinatario) ti chiede di arrivare a un punto B specifico.
3. Tu devi dimostrare di poter guidare da A a B senza sbagliare strada.

Il problema con SQIsign era che, per trovare la strada giusta, il tuo computer doveva fare calcoli matematici molto complessi e lenti (come risolvere equazioni quadratiche in un mondo astratto chiamato "algebra dei quaternioni"). Era come se dovessi calcolare a mano ogni singola curva di un viaggio transcontinentale prima di partire.

La Nuova Idea: SQInstructor (L'Insegnante di Guida)

Gli autori di questo paper hanno pensato: "E se invece di costringere l'auto a fermarsi esattamente in un punto preciso, le chiedessimo di rispettare una regola di navigazione più flessibile?"

Qui entra in gioco il concetto di "Struttura di Livello" (Level Structure).
Immagina che ogni curva (il punto di partenza o arrivo) non sia solo un punto, ma abbia dei segnali stradali specifici (come un semaforo rosso, un cartello "divieto di sosta" o una striscia pedonale).

• SQIsign (Vecchio metodo): "Devi arrivare esattamente a quel palo della luce." (Molto rigido, calcoli lenti).
• SQInstructor (Nuovo metodo): "Devi arrivare a quel palo della luce, ma assicurati che il tuo percorso passi sopra quel cartello rosso e accanto a quella striscia bianca."

Questa nuova regola sembra più complicata, ma in realtà apre la porta a due strade molto più veloci:

1. La Strada "Classica" (Isogenie 1-dimensionali)

È come guidare su una strada di campagna. È più lenta, ma è l'unica strada che permette di costruire cose molto specifiche, come firme digitali a più mani (dove più persone devono firmare insieme) o hash camaleontici (che cambiano colore se li tocchi).
Gli autori hanno creato un nuovo "GPS" (chiamato ScalarSigningKLPT) che sa navigare queste strade complesse rispettando i segnali stradali (le strutture di livello) senza impazzire nei calcoli. È come se avessero trovato un modo per risolvere le equazioni matematiche velocemente, anche con i nuovi vincoli.

2. La Strada "Super-Autostrada" (Isogenie 2-dimensionali)

Questa è la vera rivoluzione. Invece di guidare su una singola strada (1D), immagina di poter guidare su un ponte sospeso che collega due autostrade parallele (2D).
Questa tecnica permette di saltare i calcoli lenti e di viaggiare a velocità supersonica.

• Il risultato: SQInstructor, quando usa questa strada, è veloce quanto SQIsign (il campione attuale), ma è più flessibile.
• La sicurezza: È sicura quanto SQIsign, perché si basa sugli stessi principi matematici solidi, solo applicati in modo più intelligente.

Perché è importante? (L'Analogia del "Trucco di Magia")

Immagina che SQIsign sia un prestigiatore che fa sparire una moneta. È molto bravo, ma il trucco richiede un movimento della mano molto specifico e lento.
SQInstructor è un nuovo prestigiatore che usa un trucco diverso.

• Può fare lo stesso trucco (la firma digitale) ma in modo più veloce.
• Può anche fare trucchi che il vecchio prestigiatore non sapeva fare (come le firme a più mani).
• Il pubblico (i computer che verificano la sicurezza) non nota la differenza: il trucco funziona perfettamente e nessuno riesce a smascherarlo.

In Sintesi: Cosa hanno fatto gli autori?

1. Hanno generalizzato le regole: Invece di dire "arriva qui", hanno detto "arriva qui rispettando questi segnali". Questo si chiama Struttura di Livello.
2. Hanno mappato il territorio: Hanno creato una nuova mappa matematica (la "Corrispondenza di Deuring" generalizzata) che collega le strade delle curve ellittiche ai calcoli dei quaternioni, tenendo conto di questi nuovi segnali.
3. Hanno costruito due GPS:
   • Uno per le strade lente ma versatili (per usi avanzati).
   • Uno per le super-autostrade veloci (per la massima efficienza).
4. Hanno dimostrato che funziona: Hanno scritto il codice, lo hanno testato e hanno dimostrato che è sicuro contro i computer quantistici (i futuri "ladri" che potrebbero rompere le attuali protezioni).

Conclusione

SQInstructor è come un'evoluzione dell'autostrada della crittografia. Non ha solo riparato le buche della vecchia strada (rendendo i calcoli più veloci), ma ha aggiunto nuove corsie e regole di traffico che permettono di fare cose che prima erano impossibili o troppo lente. È un passo avanti fondamentale per rendere la nostra vita digitale sicura anche quando arriveranno i computer del futuro.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del paper "The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures" in lingua italiana.

1. Il Problema e il Contesto

La crittografia basata su isogenie è un candidato promettente per la crittografia post-quantum. SQIsign è attualmente lo schema di firma digitale più compatto in competizione per la standardizzazione NIST. Tuttavia, SQIsign presenta due sfide principali:

1. Complessità del processo di firma: La procedura di firma originale (basata sull'algoritmo KLPT) è complessa e lenta.
2. Sicurezza dimostrabile: Esistono difficoltà intrinseche nel provare la sicurezza EUF-CMA (Existential Unforgeability under Chosen Message Attack) a causa delle limitazioni dell'algoritmo KLPT.

Recenti attacchi a SIDH hanno portato all'adozione di isogenie in dimensioni superiori (HD) per migliorare velocità e sicurezza, ma la comprensione teorica e la generalizzazione di questi protocolli rimangono un'area di ricerca attiva. Il paper si propone di generalizzare SQIsign introducendo il concetto di strutture di livello (level structures) per definire un nuovo framework flessibile chiamato SQInstructor.

2. Metodologia e Framework Teorico

Il cuore del lavoro è l'estensione della Corrispondenza di Deuring (l'equivalenza tra curve ellittiche supersingolari e ordini di algebre di quaternioni) al contesto di curve dotate di strutture di livello.

• Strutture di Livello: Una struttura di livello $\Gamma$ su una curva $E$ è definita come una base del sottogruppo di torsione $E[N]$, a meno di trasformazioni da un sottogruppo $\Gamma \subseteq GL_2(\mathbb{Z}/N)$. Gli autori considerano strutture come quelle di Borel, Cartan e scalari.
• Generalizzazione della Corrispondenza: Gli autori dimostrano come mappare le isogenie che preservano le strutture di livello a ideali "localmente principali" in ordini specifici delle algebre di quaternioni ($B_{p,\infty}$). Questo permette di tradurre problemi sulle curve in problemi sugli ideali, mantenendo i vincoli imposti dalla struttura di livello.
• Il Protocollo SQInstructor: Viene proposto un protocollo di identificazione sigma-protocollo generico:
  1. Chiave Pubblica: Una curva $E_{pk}$ con una struttura di livello $S_{pk}$.
  2. Impegno (Commitment): Una curva $E_{com}$ con una struttura $S_{com}$.
  3. Sfida (Challenge): Il verificatore sceglie una nuova struttura di livello $S'_{com}$ su $E_{com}$.
  4. Risposta: Il prover deve fornire un'isogenia $\phi_{rsp}$ che mappi la struttura iniziale $S_{pk}$ alla struttura di sfida $S'_{com}$.

A differenza di SQIsign classico, dove la risposta deve annullare un punto di torsione (annullare una struttura), qui la risposta deve trasferire una struttura di livello a un'altra.

3. Contributi Chiave

Gli autori forniscono quattro contributi principali:

1. Estensione Esplicita della Corrispondenza di Deuring:

   • Generalizzano la corrispondenza per curve supersingolari con strutture di livello, fornendo esempi concreti e mostrando come renderla esplicita anche per livelli non lisci (non-smooth).
   • Dimostrano come calcolare gli anelli di endomorfismi $O(E, S)$ per diverse strutture (Borel, Scalari, Cartan).

2. Algoritmi per Equazioni di Norme Vincolate (Dimensione 1):

   • Per l'istanza con isogenie 1-dimensionali (simile a SQIsign pre-attacchi SIDH), gli autori adattano l'algoritmo KLPT per risolvere equazioni di norme con vincoli di struttura di livello.
   • Propongono varianti specifiche come ScalarSigningKLPT e BorelSigningKLPT per trovare ideali equivalenti con norme lisce che rispettino i vincoli di livello.
   • Forniscono un'implementazione proof-of-concept, sebbene lenta, per dimostrare la fattibilità.

3. Istanza Moderna con Isogenie 2-Dimensionali (Dimensione HD):

   • Implementano SQInstructor utilizzando tecniche di isogenie in dimensioni superiori (2D), simili alla versione NIST di SQIsign.
   4. Analisi di Sicurezza e Zero-Knowledge:
   • Dimostrano la 2-special soundness del protocollo, riducendo la sicurezza al problema di trovare un endomorfismo non scalare su una curva con struttura di livello (equivalente al problema dell'anello di endomorfismi).
   • Analizzano la proprietà Zero-Knowledge, discutendo l'uso di oracoli di isogenie (Γ-UTO e FIDIO) per simulare le risposte, analogamente alle prove di sicurezza di SQIsign HD.

4. Risultati Sperimentali e Prestazioni

Gli autori hanno implementato la variante 2-dimensionale di SQInstructor, forkando il codice di riferimento di SQIsign.

• Confronto Prestazionale: I benchmark mostrano che SQInstructor ha prestazioni molto simili a SQIsign.
  • C'è un leggero aumento nella dimensione della firma e nel tempo di verifica, attribuito alla catena di isogenie (2,2) leggermente più lunga necessaria per gestire le strutture di livello.
  • Le dimensioni delle chiavi pubbliche e delle firme sono comparabili (es. per NIST Level I: PK ~65 byte, Sig ~174 byte per SQInstructor vs ~148 byte per SQIsign).
• Flessibilità: Il framework permette di scegliere liberamente il tipo di struttura di livello e la tecnica di isogenia (1D o HD), rendendolo adatto non solo per firme, ma anche per primitive avanzate come firme ad anello e hash camaleonte.

5. Significato e Impatto

Il lavoro è significativo per diversi motivi:

• Unificazione Teorica: Fornisce una cornice teorica unificata che spiega SQIsign e le sue varianti attraverso le strutture di livello, chiarendo il ruolo delle torsioni e dei sottogruppi ciclici.
• Generalizzazione: Dimostra che la sicurezza e l'efficienza di SQIsign non dipendono strettamente dall'annullamento di un punto, ma possono essere generalizzate a mappe tra strutture di livello più complesse.
• Fondamenta per Primitive Avanzate: Mentre le isogenie 1D sono meno efficienti per le firme dirette, sono essenziali per firme ad anello e hash camaleonte. SQInstructor offre un framework solido per costruire queste primitive basate su strutture di livello, colmando un gap tra la teoria delle algebre di quaternioni e le applicazioni pratiche.
• Sicurezza Post-Quantum: Conferma che le basi di sicurezza di SQIsign (il problema dell'anello di endomorfismi) sono robuste anche in questo contesto generalizzato, mantenendo la resistenza contro gli attacchi quantistici noti.

In sintesi, SQInstructor non è solo una nuova istanza di firma, ma un "manuale di istruzioni" teorico e pratico che espande l'orizzonte della crittografia basata su isogenie, offrendo flessibilità nella progettazione di protocolli senza sacrificare la sicurezza o l'efficienza.