🔢 mathematics

A Compact Post-quantum Strong Designated Verifier Signature Scheme from Isogenies

Questo articolo propone un nuovo schema di firma compatta post-quantistica con verificatore forte designato basato su azioni di gruppo crittografico (abeliano) e isogenie, garantendo che solo il verificatore designato possa confermare l'autenticità di una firma.

Autori originali: Farzin Renan, Wendi Gao, Jason T. LeGrow

Pubblicato 2026-09-14

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Farzin Renan, Wendi Gao, Jason T. LeGrow

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 fiducia è solitamente una questione pubblica. Quando si firma un documento online, una firma digitale funge da sigillo che chiunque possieda gli strumenti adeguati può verificare. Questa trasparenza è l'ossatura della sicurezza moderna, garantendo che un messaggio provenga realmente dal mittente e non sia stato alterato. Tuttavia, esistono situazioni in cui questa natura pubblica è un difetto piuttosto che un pregio. Immaginate una conversazione privata tra due persone in cui una vuole dimostrare la propria identità all'altra, ma deve garantire che nessun terzo possa mai essere convinto che il messaggio provenga da lei. Se il destinatario potesse provare l'origine a un giudice o a un amico, la privacy dello scambio sarebbe compromessa. Questa è la sfida delle firme a "verificatore designato": creare una prova che sia innegabile per il destinatario previsto ma completamente non convincente per chiunque altro.

La difficoltà si approfondisce se consideriamo il futuro. I metodi di crittografia che attualmente proteggono i nostri dati si basano su problemi matematici che sono difficili per i computer odierni, ma che potrebbero essere risolti facilmente da potenti macchine quantistiche. Mentre gli scienziati corrono per costruire sistemi in grado di resistere a queste minacce future, si rivolgono a un ramo della matematica che riguarda le forme delle curve e i modi in cui possono essere trasformate l'una nell'altra. Queste trasformazioni, note come isogenie, offrono una nuova base per la sicurezza che si ritiene sia sicura contro gli attacchi quantistici. L'obiettivo è costruire un sistema che non solo sopravviva all'era quantistica, ma che preservi anche la delicata privacy delle conversazioni designate.

Un team di ricercatori ha introdotto un nuovo metodo per creare queste firme private e sicure contro i computer quantistici. Chiamano il loro sistema CSI-SDVS, uno schema costruito sulle proprietà delle isogenie supersingolari commutative. L'idea centrale è quella di utilizzare la relazione matematica unica tra le curve ellittiche per creare una firma che solo il destinatario previsto possa verificare. In questo sistema, il mittente e il destinatario possiedono ciascuno una chiave segreta e una corrispondente chiave pubblica. Quando il mittente vuole firmare un messaggio, utilizza la propria chiave segreta e la chiave pubblica del destinatario per generare un codice unico. Il destinatario può poi utilizzare la propria chiave segreta per controllare se il codice è valido. La genialità del design risiede nella sua capacità di simulazione. Il destinatario può anche utilizzare la propria chiave segreta per generare una firma che sembri esattamente una proveniente dal mittente. Poiché il destinatario può creare un falso perfetto, non può provare a un terzo che una specifica firma sia provenuta dal mittente piuttosto che essere stata creata da lui stesso. Questa proprietà, nota come non trasferibilità, garantisce che la conversazione rimanga privata anche se il destinatario tenta di condividere l'evidenza.

I ricercatori hanno dimostrato che il loro nuovo schema non è solo sicuro contro i computer quantistici, ma è anche altamente efficiente. Nei tentativi precedenti di costruire sistemi simili, le chiavi digitali e le firme erano spesso enormi, richiedendo centinaia di kilobyte di dati per essere archiviate o trasmesse. Ciò li rendeva impraticabili per molte applicazioni del mondo reale. Il nuovo design, tuttavia, è notevolmente compatto. Utilizzando un set specifico di parametri noto come CSIDH-512, i ricercatori hanno ottenuto un sistema in cui le chiavi segrete sono lunghe 256 bit, le chiavi pubbliche sono di 512 bit e le firme stesse sono anch'esse di soli 512 bit. Per dare un termine di paragone, una firma digitale standard nei sistemi più vecchi potrebbe avere le dimensioni di un piccolo file di testo, mentre questa nuova firma è grande circa quanto una singola riga di testo. Questa drastica riduzione delle dimensioni rende la tecnologia utilizzabile su dispositivi con memoria e larghezza di banda limitate.

Il team ha dimostrato che il loro sistema soddisfa tutti i rigorosi standard di sicurezza richiesti per questo tipo di crittografia. Hanno dimostrato che un attaccante non può falsificare una firma senza le chiavi segrete e hanno provato che l'identità del firmatario rimane nascosta a chiunque altro rispetto al verificatore designato. Queste prove si basano sull'assunto che risolvere determinati problemi matematici relativi alle azioni di gruppo di queste curve sia computazionalmente impossibile, anche per un computer quantistico. I ricercatori hanno anche esplorato un modello matematico specifico per mostrare che la sicurezza del loro sistema può essere legata a un problema leggermente diverso, ma ugualmente difficile. Questo approccio a doppio strato rafforza la fiducia nella robustezza del sistema.

Combinando la privacy della verifica designata con l'efficienza della crittografia basata su isogenie, questo lavoro offre una soluzione pratica per la comunicazione sicura e privata in un mondo post-quantistico. Esso sposta il campo dalle possibilità teoriche a strumenti concreti e utilizzabili. I ricercatori hanno dimostrato che è possibile avere una firma che sia abbastanza forte da essere creduta dal destinatario, ma abbastanza debole da essere negata a tutti gli altri, il tutto mantenendo i dati abbastanza piccoli da poter essere utilizzati ovunque. Questo equilibrio tra privacy, sicurezza ed efficienza segna un passo significativo nella preparazione della nostra infrastruttura digitale per le sfide del futuro.

Riepilogo Tecnico: Uno schema di firme a verificatore designato forte e compatto post-quantum basato su isogenie

Definizione del Problema

Le firme digitali forniscono tradizionalmente la non-ripudio, il che significa che qualsiasi parte con accesso alla chiave pubblica del firmatario può verificare l'autenticità di una firma. Sebbene utile per molte applicazioni, questa proprietà è indesiderabile in scenari che richiedono comunicazioni "off-the-record", dove un firmatario (Alice) desidera autenticare un messaggio a un destinatario specifico (Bob) senza consentire a Bob di dimostrare a una terza parte l'origine del messaggio da parte di Alice.

Per affrontare questo problema, sono state introdotte le Firme a Verificatore Designato Forte (Strong Designated Verifier Signatures - SDVS). Uno schema SDVS assicura che solo il verificatore designato possa verificare l'autenticità della firma. Fondamentalmente, soddisfa la non-trasferibilità: il verificatore designato può simulare firme computazionalmente indistinguibili da quelle reali, impedendo a lui di convincere una terza parte della validità della firma. Inoltre, gli schemi SDVS devono soddisfare la Privacy dell'Identità del Firmatario (PSI), garantendo che, data una firma valida e molteplici chiavi pubbliche candidate, nessuna terza parte possa determinare quale chiave sia stata utilizzata per firmare.

Sebbene esistano schemi SDVS nella crittografia classica (basati su accoppiamenti bilineari o firme di Schnorr), essi sono vulnerabili agli attacchi quantistici tramite l'algoritmo di Shor. Le attuali proposte post-quantum basate su codici o reticoli spesso soffrono di dimensioni elevate per chiavi e firme (ad esempio, complessità $O(\lambda^2)$ ) o sono state dimostrate incapaci di soddisfare le proprietà di non-trasferibilità. Recenti proposte basate su isogenie hanno affrontato violazioni della sicurezza (ad esempio, SIDH) o si affidano ad assunzioni che potrebbero non essere robuste quanto desiderato.

Metodologia

Gli autori propongono CSI-SDVS, un nuovo schema SDVS basato sull'azione di gruppo Commutative Supersingular Isogeny Diffie-Hellman (CSIDH). La costruzione sfrutta la struttura algebrica dell'azione del gruppo delle classi degli ideali su un insieme di curve ellittiche supersingolari su un campo finito $\mathbb{F}_p$ .

Componenti Core

Configurazione dell'Azione di Gruppo: Lo schema opera all'interno di un'azione di gruppo efficace $(G, X, *)$ , dove $G$ è il gruppo delle classi degli ideali di un ordine in un campo quadratico immaginario e $X$ è l'insieme delle curve ellittiche supersingolari. L'azione è libera e transitiva.
Generazione delle Chiavi:
- Il firmatario e il verificatore generano chiavi segrete ( $sk_S, sk_V$ ) come interi casuali in $\mathbb{Z}_N$ (dove $N$ è il numero di classe).
- Le chiavi pubbliche sono generate applicando l'azione di gruppo a una curva base $E$ : $pk_S = [g^{sk_S}] * E$ e $pk_V = [g^{sk_V}] * E$ .
Firma e Simulazione:
- Firma: Per firmare un messaggio $m$ , il firmatario sceglie un $z \in \mathbb{Z}_N$ casuale, calcola $Y = [g^{z+sk_S}] * pk_V$ e imposta la firma $\sigma = (h, z)$ dove $h = H(Y || m)$ .
- Simulazione: Il verificatore, possedendo $sk_V$ , può simulare una firma scegliendo un $z$ casuale, calcolando $Y = [g^{z+sk_V}] * pk_S$ e impostando $\sigma = (h, z)$ con $h = H(Y || m)$ .
- Correttezza: Grazie alla commutatività dell'azione di gruppo, $[g^{z+sk_S}] * pk_V = [g^{z+sk_S+sk_V}] * E = [g^{z+sk_V}] * pk_S$ . Pertanto, il valore $Y$ calcolato dal firmatario e dal simulatore è identico, garantendo che entrambi producano firme valide per lo stesso input di hash.
Verifica: Il verificatore controlla se $h = H([g^{z+sk_V}] * pk_S || m)$ .

Contributi Chiave

SDVS Post-Quantum Compatto: Il documento presenta CSI-SDVS, uno schema SDVS efficiente con complessità $O(\lambda)$ per chiavi e firme. Utilizzando i parametri CSIDH-512, lo schema raggiunge:
- Chiave Segreta: 256 bit.
- Chiave Pubblica: 512 bit.
- Firma: 512 bit.
  Questo rappresenta un miglioramento significativo rispetto ai precedenti schemi SDVS basati su reticoli, che spesso presentano dimensioni $O(\lambda^2)$ , e agli schemi basati su isogenie con chiavi pubbliche più grandi.
Dimostrazioni di Sicurezza in ROM e AGAM:
- Non-Trasferibilità (NT): Dimostrata in modo incondizionato, poiché le distribuzioni delle firme reali e simulate sono identiche.
- Unforgeability Forte (SUF-CMA) e PSI: Dimostrate sicure nel Modello dell'Oracolo Casuale (ROM) sotto l'assunzione Group Action Decisional Diffie-Hellman (GA-DDH).
- Riduzioni Strette: Gli autori dimostrano ulteriormente che, nel Modello di Azione di Gruppo Algebrica (AGAM), la sicurezza SUF-CMA e PSI di CSI-SDVS si riduce strettamente al Group Action Inverse Problem (GAIP), un problema computazionale piuttosto che decisionale.
Analisi della Sicurezza: Lo schema è mostrato essere conforme a tutte le definizioni standard di sicurezza SDVS (NT, SUF-CMA, PSI) senza fare affidamento sul protocollo SIDH (che è stato violato), utilizzando l'azione di gruppo CSIDH, attualmente ritenuta sicura.

Risultati

Il documento fornisce prove formali di sicurezza dimostrando che:

Lo schema è incondizionatamente non-trasferibile.
Sotto l'assunzione GA-DDH nel ROM, lo schema è fortemente non falsificabile e fornisce la privacy dell'identità del firmatario.
Sotto l'assunzione GAIP nell'AGAM e nel ROM, lo schema raggiunge riduzioni strette sia per la sicurezza SUF-CMA che per la PSI.
Performance: La Tabella 1 nel documento confronta CSI-SDVS con i lavori precedenti (Sun et al. [26] e Khuc et al. [12]). CSI-SDVS offre la chiave pubblica (512 bit) e la firma (512 bit) più piccole tra gli schemi post-quantum confrontati, mantenendo una dimensione della chiave segreta di 256 bit.

Significato

Gli autori posizionano CSI-SDVS come una soluzione pratica e sicura per le firme a verificatore designato post-quantum. Il significato risiede in:

Efficienza: Raggiunge parametri compatti adatti ad ambienti con risorse limitate, affrontando i limiti di dimensione delle precedenti proposte basate su reticoli o isogenie.
Robustezza: Basando la sicurezza sul GAIP (un'assunzione computazionale) nell'AGAM, lo schema evita l'affidamento su assunzioni decisionali che possono talvolta essere più deboli o meno intuitive nel contesto dell'azione di gruppo.
Completezza: Il lavoro fornisce un'analisi completa della sicurezza coprendo tutti e tre i pilastri di SDVS (non-trasferibilità, unforgeability e privacy del firmatario) in un contesto post-quantum, colmando una lacuna lasciata dai precedenti schemi che o fallivano la non-trasferibilità o soffrivano di inefficienza.

Il documento conclude che CSI-SDVS offre un equilibrio ottimale tra sicurezza ed efficienza, rendendolo un candidato valido per applicazioni che richiedono un'autenticazione resistente ai computer quantistici e non-trasferibile.