⚛️ quantum physics

CRT-Decomposed $Σ$ -Protocols for CSIDH

Questo articolo presenta un protocollo $\Sigma$ decomposto tramite CRT per CSIDH che raggiunge la completezza perfetta, lo zero-knowledge e un'estrazione efficiente in linea retta nel QROM senza assunzioni euristiche, verificando rigorosamente la sua correttezza algebrica e dimostrando che la sua sicurezza attualmente si basa su parametri futuri con fattori primi grandi a causa di una significativa riduzione del costo degli attacchi classici quando le curve CRT hop vengono pubblicate.

Autori originali: I. Dey, I. Cherkaoui

Pubblicato 2026-09-23

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: I. Dey, I. Cherkaoui

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Nel mondo digitale, la privacy spesso si basa su un delicato equilibrio: un utente vuole dimostrare di avere il diritto di spendere denaro o accedere a un servizio senza rivelare la propria identità o i dettagli specifici della transazione. Questo è il regno delle firme cieche, uno strumento crittografico che permette a una banca di certificare una moneta senza mai vedere dove verrà spesa. Per decenni, la sicurezza di questi sistemi si è basata su enigmi matematici che coinvolgono numeri grandi, ma l'ascesa di potenti computer quantistici minaccia di risolvere tali enigmi, rendendo obsoleti gli attuali sistemi di protezione della privacy. Per contrastare ciò, gli scienziati si stanno rivolgendo a un tipo diverso di matematica basata sulla geometria delle curve ellittiche, specificamente un metodo chiamato crittografia basata su isogenia. Questo approccio utilizza un tipo unico di movimento tra le curve che è facile da eseguire in una direzione ma incredibilmente difficile da invertire, creando una base per una sicurezza che le macchine quantistiche non possono facilmente violare. Tuttavia, costruire sistemi pratici su questa base è stato difficile perché i metodi standard per provare la conoscenza di una chiave segreta spesso si affidano a un processo che fallisce di fronte ad avversari quantistici.

Un team di ricercatori della South East Technological University in Irlanda ha sviluppato un nuovo modo per costruire queste prove che evita le debolezze fatali dei metodi precedenti. Il loro lavoro si concentra su un sistema specifico noto come CSIDH, che utilizza una struttura matematica chiamata gruppo di classi per muoversi tra le curve ellittiche. I ricercatori hanno scoperto che quando la struttura interna di questo gruppo è pienamente nota, come nel caso di una versione specifica chiamata CSIDH-512, essa può essere scomposta in pezzi più piccoli e indipendenti utilizzando un classico principio matematico noto come Teorema della Restituzione Cinese. Invece di trattare la chiave segreta come un singolo blocco monolitico, hanno progettato un protocollo che prova la conoscenza di ogni piccolo pezzo separatamente. Questo cambiamento strutturale permette al sistema di estrarre la chiave segreta direttamente dalla prova usando una semplice aritmetica, piuttosto che affidarsi a un complesso e ripetitivo gioco di tentativi ed errori che i computer quantistici possono interrompere.

Il cuore del loro traguardo è un nuovo tipo di prova interattiva che è sia perfettamente completa che perfettamente sicura contro le intercettazioni. In questo sistema, un prover e un verifier si scambiano messaggi per confermare che il prover conosca una chiave segreta senza rivelare la chiave stessa. I ricercatori hanno dimostrato che se un prover riesce a rispondere con successo a due diverse sfide per lo stesso passaggio, il segreto può essere recuperato istantaneamente sottraendo le risposte e eseguendo una singola divisione. Questo processo, che chiamano estrazione algebrica, avviene in linea retta senza la necessità di riavvolgere o ricominciare l'interazione. Questa è una distinzione critica perché le precedenti prove di sicurezza per sistemi simili si affidavano al riavvolgimento dell'attaccante a uno stato precedente per indurlo in errore, una tecnica che è impossibile giustificare contro un computer quantistico che non può essere messo in pausa o copiato. Rimuovendo questo passaggio, il nuovo protocollo offre una via verso la sicurezza che regge anche in un futuro in cui i computer quantistici saranno comuni.

Per garantire che il loro design non fosse solo un'idea teorica, il team ha implementato l'intero sistema su un computer utilizzando i parametri esatti del gruppo CSIDH-512. Hanno verificato la logica matematica del protocollo su diecimila istanze casuali, confermando che i passaggi algebrici funzionavano esattamente come previsto ogni volta. Hanno anche eseguito simulazioni per misurare come il sistema si sarebbe comportato sotto attacco. Questi test hanno confermato che la sicurezza del sistema segue le leggi matematiche attese, con la difficoltà di violarlo che cresce in modo prevedibile all'aumentare del numero di round. Tuttavia, i ricercatori sono stati anche attenti a identificare i limiti del loro approccio. Hanno dimostrato che, sebbene scomporre il problema in pezzi più piccoli renda possibile l'estrazione del segreto, espone anche il sistema a un tipo specifico di attacco che riduce la difficoltà di violare la chiave. Per gli attuali parametri CSIDH-512, questa riduzione abbassa la sicurezza da un livello che richiede circa 2^128.6 valutazioni dell'azione del gruppo a circa 2^67.3 valutazioni, un calo significativo che rende i parametri attuali insufficienti per una sicurezza classica a 128 bit.

Di conseguenza, i ricercatori concludono che, sebbene la loro costruzione sia matematicamente corretta e strutturalmente completa, non è ancora sicura per una distribuzione immediata sui parametri CSIDH-512 attuali. Il sistema funziona perfettamente, ma la stessa caratteristica che lo rende efficiente — l'esposizione dei passaggi intermedi — lo rende anche vulnerabile a un noto metodo di attacco. La soluzione, sostengono, risiede in futuri set di parametri in cui i componenti matematici siano molto più grandi. Se il gruppo è costruito da fattori primi che sono individualmente molto grandi, la perdita di sicurezza derivante dall'esposizione degli step intermedi diventa trascurabile, e il sistema rimarrebbe sicuro. Il documento ha anche confrontato il loro metodo con gli schemi esistenti, notando che, sebbene le loro firme siano attualmente più grandi, il compromesso è un modello di sicurezza che non degrada di fronte alle minacce quantistiche. Il lavoro rappresenta una dimostrazione rigorosa che la struttura algebrica può sostituire le prove di sicurezza complesse e soggette a errori, a patto che i numeri sottostanti siano scelti con sufficiente cura per resistere alle nuove vulnerabilità che la struttura introduce.

Sintesi Tecnica: Protocolli $\Sigma$ -Decomposti tramite CRT per le Azioni di Gruppo Classico di CSIDH

Enunciato del Problema
Il documento affronta una debolezza critica nelle prove di sicurezza dei protocolli di firma cieca e identificazione basati su isogenie, specificamente quelli costruiti sull'azione di gruppo CSIDH (Commutative Supersingular Isogeny Diffie-Hellman). Gli attuali protocolli allo stato dell'arte (ad esempio, CSI-Otter, Tanuki) si affidano a protocolli di identificazione interattivi la cui riduzione di sicurezza dipende dal lemma di forking (forking lemma). Questo lemma richiede di "riavvolgere" (rewinding) un avversario quantistico per estrarre una chiave segreta, un processo che comporta una perdita di sicurezza quadratica ed è teoricamente invalido contro avversari quantistici i cui stati interni non possono essere clonati. Di conseguenza, queste prove impongono l'uso di parametri più grandi e lenti per compensare tale perdita. Il documento mira a eliminare questo passaggio di riavvolgimento sfruttando la struttura algebrica del gruppo di classi di CSIDH per abilitare l'estrazione in linea retta (straight-line extraction).

Metodologia
Gli autori costruiscono una prova di conoscenza zero-knowledge ( $\Sigma$ -protocol) che sfrutta la struttura del Teorema Cinese del Resto (CRT) del gruppo di classi di CSIDH. Questo approccio è applicabile solo quando la struttura del gruppo è esattamente nota, una condizione attualmente soddisfatta solo da CSIDH-512.

Decomposizione CRT: Il gruppo di classi $C\ell(\mathcal{O})$ di ordine $N$ viene decomposto in componenti cicliche indipendenti corrispondenti ai fattori di potenza prima di $N$ . La chiave segreta $s$ viene suddivisa in componenti $s_i$ modulo ciascun fattore primo $q_i$ .
Curve Hop: Il protocollo pubblica una catena di "curve hop" ( $F_0, \dots, F_k$ ) che rappresentano gli stati intermedi dell'azione di gruppo. Ogni hop $i$ corrisponde a un problema di vettorizzazione all'interno di un sottogruppo specifico $\langle h_i \rangle$ di ordine $q_i$ .
Struttura del Protocollo: Il protocollo consiste in $k$ hop, ciascuno eseguito in $t$ round paralleli. In ogni round, il prover si impegna (commits) su uno spostamento casuale, il verificatore emette una sfida binaria ( $c \in \{0,1\}$ ) e il prover risponde con un valore $z$ .
Estrazione Algebrica: A differenza delle prove standard che richiedono il riavvolgimento per trovare due trascrizioni accettabili con sfide diverse, questo protocollo permette di recuperare il segreto tramite una formula algebrica a forma chiusa. Date due trascrizioni accettabili per lo stesso impegno, la componente segreta è semplicemente la differenza delle risposte ( $z_0 - z_1$ ), seguita da inversione modulare e ricombinazione CRT.
Compilazione QROM: Poiché ogni round ammette esattamente due risposte, il protocollo è compatibile con la trasformazione di Unruh. Ciò consente di convertire il protocollo interattivo in una prova di conoscenza non interattiva nel Modello di Oracolo Casuale Quantistico (QROM) con estrazione in linea retta, evitando completamente il lemma di forking.

Contributi Principali
Il documento presenta cinque contributi primari:

Definizione Formale: Formalizza la estraibilità debole (weak extractability) per le azioni di gruppo crittografiche, definendo una nozione di sicurezza in cui un estrattore può recuperare il segreto usando solo operazioni di anello (senza riduzione di reticoli o euristiche) dalle trascrizioni accettabili.
Costruzione del Protocollo ( $\Pi_{CRT}$ ): Costruisce un protocollo che prova quattro proprietà:
- Completezza Perfetta: I prover onesti hanno sempre successo.
  े * HVZK Speciale Perfetta: Le trascrizioni non rivelano alcuna informazione sul segreto, nemmeno a osservatori illimitati.
- 2-Special Soundness: Il segreto è algebricamente recuperabile da due trascrizioni tramite semplice sottrazione e inversione modulare.
- Errore di Conoscenza: La probabilità che un prover abbia successo senza la chiave è $2^{-t}$ .
Verifica tramite Macchina: Gli autori hanno implementato lo strato algebrico sull'esatto modulo a 258 bit di CSIDH-512. Hanno verificato 10.000 istanze casuali, confermando che l'estrazione algebrica funziona perfettamente e che la logica del protocollo regge senza calcolare effettivamente le isogenie.
Delimitazione dei Risultati (Risultati Negativi):
- Limite dello Spazio delle Sfide: La decomposizione CRT non amplia lo spazio delle sfide per round; le sfide binarie rimangono necessarie a meno di pubblicare più curve, il che aumenta la dimensione della chiave.
- Costo di Sicurezza: Pubblicare le curve hop intermedie riduce la sicurezza classica del recupero della chiave da $\approx 2^{128.6}$ a $\approx 2^{67.3}$ valutazioni di azione di gruppo. Questo perché il problema si decompone in istanze di vettorizzazione indipendenti nei sottogruppi, risolvibili tramite attacchi meet-in-the-middle sui componenti più grandi.
Sicurezza QROM: Il documento dimostra che il protocollo, quando compilato tramite la trasformazione di Unruh, produce una prova non interattiva con estrazione online nel QROM, eliminando la perdita moltiplicativa del lemma di forking.

Risultati e Analisi Quantitativa

Istanziazione: Lo schema è istanziato su CSIDH-512. Il gruppo di classi ha 5 fattori primi (lunghezze in bit: 2, 6, 21, 96, 135).
Limiti di Sicurezza:
- Classica: La sicurezza è limitata dal fattore primo più grande ( $q_{max} \approx 2^{135}$ ). Il costo dell'attacco meet-in-the-middle è $O(\sqrt{q_{max}}) \approx 2^{67.3}$ . Il documento nota che CSIDH-512 non raggiunge la sicurezza classica a 128 bit sotto questa costruzione a causa delle curve hop pubblicate.
- Quantistica: La sicurezza è limitata dai setacci stile Kuperberg, similmente ad altri schemi CSIDH.
Prestazioni:
- Dimensione della Firma: Per $t=128$ round e $k=5$ componenti, la dimensione della firma è di circa 24.1 KiB (rispetto a 263 B per CSI-FiSh e 8 KiB per CSI-Otter).
- Computazione: L'estrazione algebrica e la simulazione sono nell'ordine dei microsecondi. Il costo dominante rimane la valutazione dell'isogenia (proiettata a 40 ms per azione), rendendo il tempo totale di firma di circa 25.6 secondi per l'intero protocollo.
Simulazione: Simulazioni Monte Carlo hanno confermato che l'errore di correttezza (soundness error) corrisponde al limite teorico $2^{-t}$ entro intervalli di confidenza del 95%.

Significatività e Rivendicazioni
Il documento rivendica che la costruzione è strutturalmente completa e corretta per i gruppi di classi con struttura nota come CSIDH-512. La sua importanza primaria risiede nel fornire una riduzione di sicurezza quantum-safe per le prove di conoscenza basate su isogenie eliminando il passaggio di riavvolgimento, che è una vulnerabilità nota nelle prove di sicurezza post-quantistiche.

Tuttavia, gli autori sono espliciti riguardo ai compromessi:

Modestia sulla Sicurezza: Lo schema non è quantitativamente sicuro al livello di 128 bit per CSIDH-512 a causa della degradazione della sicurezza causata dalla pubblicazione delle curve hop. Gli autori affermano che la costruzione è "quantitativamente sicura solo su futuri set di parametri il cui numero di classi ha fattori primi grandi" (ad esempio, dove ogni fattore è $\ge 256$ bit).
Nessun "Bagno di Magia": La decomposizione CRT non riduce il numero di round richiesti per la correttezza (soundness); essa cambia semplicemente il meccanismo di estrazione.
Lavoro Futuro: Il documento lascia la costruzione di una firma cieca basata su questa prova di conoscenza e la riduzione stretta della sua non-falsificabilità al problema dell'anello di endomorfismi come lavori futuri.

In sintesi, il documento presenta un protocollo matematicamente rigoroso e verificato tramite macchina che risolve il "problema del riavvolgimento" per le prove di conoscenza basate su CSIDH, offrendo una via per firme cieche sicure in QROM, ma al costo di dimensioni delle firme più grandi e di una ridotta sicurezza classica per gli attuali set di parametri.

Articoli simili