💻 computer science

Withdrawability in Fiat-Shamir with aborts constructions

Questo articolo estende il concetto di firme revocabili al paradigma Fiat-Shamir con aborti proponendo una costruzione astratta con prove di sicurezza e fornendo un'istanza concreta basata su uno schema di tipo Dilithium senza hint, pur rilevando i minori aggiustamenti richiesti per la produzione di ML-DSA con hint.

Autori originali: Ramses Fernandez-Valencia

Pubblicato 2026-07-08

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Ramses Fernandez-Valencia

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

Immagina di avere un timbro digitale molto speciale e indistruttibile. Una volta che metti questo timbro su un documento, di solito è permanente. Non puoi tornare indietro e nessuno può fingere che tu non l'abbia firmato. È così che funzionano la maggior parte delle firme digitali oggi.

Ma cosa succederebbe se volessi una firma "morbida"? Una che potresti ritirare se cambiassi idea, prima che qualcun altro la veda, senza distruggere la tua capacità di firmare altre cose?

Questo articolo presenta un nuovo tipo di firma digitale chiamata "Firma Reperibile" (Withdrawable Signature). È progettata per funzionare in un futuro in cui potenti computer quantistici potrebbero rompere la sicurezza odierna, quindi utilizza la matematica "basata sui reticoli" (pensa a un labirinto complesso e multidimensionale) invece della vecchia matematica che i computer quantistici possono risolvere facilmente.

Ecco come l'articolo lo spiega, usando analogie semplici:

1. Il Problema: Il "Timbro Permanente"

Di solito, quando firmi un contratto digitale, è come timbrare un documento con inchiostro bagnato che si asciuga istantaneamente. Una volta asciutto, è lì per sempre.

Il Problema: A volte devi cambiare idea. Magari hai firmato un contratto intelligente su una blockchain, ma l'affare è saltato. O forse hai espresso un voto in un'elezione digitale ma ti sei reso conto di aver fatto un errore prima che i voti venissero conteggiati.
L'Obiettivo: Hai bisogno di un modo per dire: "Ho firmato questo, ma lo sto ritirando", senza rivelare la tua password segreta (chiave privata) o compromettere le tue altre firme.

2. La Soluzione: La "Doppia Busta Magica"

Gli autori hanno creato un sistema in cui una firma inizia come una nota segreta e reperibile e può successivamente essere trasformata in un timbro pubblico e confermato.

Pensa a questo come a:

Fase 1: La Firma Reperibile (La Nota Segreta)
Immagina di scrivere una nota e metterla all'interno di una scatola speciale e chiusa. Dai questa scatola a una persona specifica (il "verificatore designato").
- Solo quella persona specifica ha la chiave per aprire la scatola e leggere la nota.
- Il Trucco Magico: Per chiunque altro (anche per una spia che ti osserva), la scatola sembra rumore casuale. Non possono capire se tu hai messo la nota dentro, o se il destinatario ha scritto la nota e l'ha messa nella scatola. È una situazione perfetta di "parole contro parole". Questo è chiamato Ambiguità.
- A causa di questa ambiguità, puoi dire: "Io non ho mai firmato quello", e il destinatario non può dimostrare che tu l'abbia fatto, a meno che tu non decida di confermarlo.
Fase 2: La Conferma (Il Timbro Pubblico)
Se decidi che vuoi che la firma sia permanente, esegui un passaggio di "Conferma".
- Prendi la nota segreta dalla scatola e usi la tua chiave segreta per generare una firma standard e pubblica che provi: "Sì, l'ho scritta io sicuramente".
- Ora, chiunque può vederlo e nessuno può negarlo.

3. Il "Labirinto Quantum-Proof" (Fiat-Shamir con Aborti)

L'articolo costruisce questo sistema utilizzando un tipo specifico di matematica chiamato Fiat-Shamir con Aborti (Fiat-Shamir with Aborts).

L'Analogia: Immagina di cercare di risolvere un labirinto gigante e complesso per dimostrare di conoscere la strada.
La Parte dell' "Aborto": A volte, potresti prendere una strada sbagliata che accidentalmente rivela un segreto su come hai risolto il labirinto. Se ciò accade, puoi semplicemente dire: "Aborto! Ho fatto un errore", e ricominciare da capo. Continui a provare finché non trovi un percorso che provi la tua conoscenza del labirinto senza trapelare alcun segreto.
Questo metodo di "prova e riprova" è ciò che rende la firma sicura contro i computer quantistici.

4. Come l'hanno Costruito (Il "No-Hint Dilithium")

Gli autori hanno preso uno schema di firma quantistica già famoso chiamato Dilithium (che è come un timbro standard ad alta sicurezza) e lo hanno modificato.

Hanno rimosso una piccola funzione di "hint" (indizio) che Dilithium di solito usa per renderlo più veloce.
Perché? Rimuovere l'indizio rende la matematica "perfetta". Assicura che la nota segreta sia davvero indistinguibile da una falsa, anche per un supercomputer.
Hanno avvolto questa firma modificata in uno strato di crittografia. Questo è come mettere la "Doppia Busta Magica" all'interno di un servizio di corriere sicuro che solo il destinatario e il mittente possono aprire.

5. Perché Questo è Importante (Secondo l'Articolo)

L'articolo afferma che questa costruzione raggiunge due obiettivi principali:

Inautenticabilità (Unforgeability): Anche se un hacker ruba la chiave segreta del destinatario, non può comunque falsificare una firma che sembri provenire dal firmatario originale. Solo il firmatario originale può trasformare la nota "reperibile" in un timbro "confermato".
Reperibilità (Withdrawability): Finché non hai confermato la firma, nessuno (nemmeno il destinatario) può dimostrare chi ha scritto la nota. È un pareggio perfetto.

Riassunto

L'articolo presenta un nuovo modo per firmare documenti digitali che permette di revocare la propria firma prima che diventi permanente. Utilizza una "nota segreta" che solo una persona specifica può leggere, la quale può successivamente essere trasformata in un "timbro pubblico". Questo sistema è costruito su una matematica "quantum-proof" (reticoli) e utilizza un metodo di "prova e riprova" per garantire che nessun segreto venga trapelato durante il processo.

Fondamentalmente, l'articolo si concentra interamente sulla costruzione matematica e sulle prove di sicurezza. Menziona che questo potrebbe essere utile per sistemi blockchain o di voto, ma non sostiene di aver costruito un'app di voto o di blockchain funzionante, bensì fornisce solo il "motore" sicuro che potrebbe alimentare tali cose in futuro.

Sintesi Tecnica: Costruzioni di Firme Ritirovabili in Fiat–Shamir con Aborti

Enunciato del Problema
Le firme digitali tradizionalmente forniscono permanenza; una volta generata, una firma non può essere revocata senza compromettere la chiave privata del firmatario o invalidare altre firme. Questa limitazione pone sfide in ambienti dinamici come gli smart contract blockchain, il voto elettronico decentralizzato e i servizi di escrow, dove i partecipanti potrebbero dover revocare gli impegni in base a condizioni mutevoli. Liu, Baek e Susilo [LBS23] hanno introdotto le "firme ritirabili" (withdrawable signatures), un primitivo che permette a un firmatario di generare una firma verificabile solo da un verificatore designato, la quale può successivamente essere trasformata in una firma pubblicamente verificabile. Tuttavia, la loro costruzione si basa su assunzioni classiche (Logaritmo Discreto, Diffie-Hellman) vulnerabili agli attacchi quantistici.

La sfida affrontata da questo articolo è estendere il concetto di firme ritirabili nell'ambito post-quantistico, specificamente all'interno del paradigma Fiat–Shamir con aborti. Questo paradigma è la base di schemi di firma post-quantistici leader come Dilithium (ML-DSA) e HAETAE. Esiste un ostacolo strutturale specifico: la costruzione originale di Liu–Baek–Susilo si basa su un segreto condiviso Diffie-Hellman "gratuito" per ottenere simultaneamente l'ambiguità firmatario/verificatore e la designazione. La crittografia basata su reticoli manca di un analogo economico ed efficiente per questo segreto condiviso, rendendo necessaria una nuova approccio architettonico.

Metodologia
L'articolo propone una costruzione astratta generale per firme ritirabili basata sul paradigma Fiat–Shamir con aborti, seguita da un'istanza concreta.

Costruzione Astratta:
Gli autori definiscono un framework composto da cinque algoritmi: KeyGen, WSign (firma ritirabile), WSVerify (verifica ritirabile), Confirm e CVerify.
- Meccanismo Core: Lo schema utilizza una prova OR-proof di Fiat–Shamir con aborti a due parti. La firma ritirabile consiste in due rami: uno generato dal firmatario (usando la sua chiave segreta) e uno simulato dal firmatario per imitare il ramo del verificatore.
- Ambiguità: Poiché sia il firmatario che il verificatore designato possono generare un ramo valido (il firmatario simulando il verificatore, e il verificatore simulando il firmatario), l'origine della firma è indistinguibile per terze parti.
- Conferma: Per rendere la firma pubblicamente verificabile, il firmatario esegue l'algoritmo Confirm, che genera una firma standard, ordinaria, sul messaggio, sull'insieme delle chiavi pubbliche e sulla firma ritirabile stessa. Questo lega la firma ritirabile all'identità del firmatario senza richiedere la riderivazione della casualità condivisa (il che è impraticabile nei sistemi a reticoli FS-con-aborti a causa del campionamento di rifiuto/rejection sampling).
Variante Strong Designated-Verifier (SDVS):
Per garantire che la firma ritirabile non sia pubblicamente verificabile (rispettando il modello Liu–Baek–Susilo), gli autori criptano il nucleo pubblico della firma utilizzando uno schema di Crittografia a Chiave Pubblica (PKE) (specificamente, la crittografia module-LWE CPA-secure sottostante a ML-KEM/Kyber).
- La firma è criptata sia verso la chiave pubblica del verificatore designato che verso la chiave pubblica del firmatario. Ciò consente al verificatore di decriptare e verificare, e al firmatario di decriptare ed eseguire l'operazione di Confirm in modo stateless.
- Questo approccio sostituisce il segreto condiviso Diffie-Hellman con la crittografia esplicita, riconoscendo che il protocollo NIKE (Non-Interactive Key Exchange) basato su reticoli è attualmente troppo inefficiente per questo scopo.
Istanza Concreta:
Il framework astratto viene istanziato utilizzando una costruzione no-hint, full- $t$ di tipo Dilithium.
- Gli autori utilizzano una variante di Dilithium che non utilizza "hint" (la scissione $t_1$ / $t_0$ ), garantendo che il simulatore per la prova a conoscenza zero sia perfetto ( $\varepsilon_{zk} = 0$ ).
- Questa scelta semplifica le prove di sicurezza, in particolare per la proprietà di ritirabilità, evitando i piccoli errori statistici associati agli schemi con hint.

Contributi Chiave

Framework Generale: Il documento introduce la prima costruzione astratta per firme ritirabili basata sul paradigma Fiat–Shamir con aborti, colmando il divario tra il modello Liu–Baek–Susilo e la crittografia a reticoli post-quantistica.
Prove di Sicurezza:
- Infalsificabilità: Lo schema è dimostrato infalsificabile sotto corruzione interna (dove l'avversario possiede la chiave segreta del verificatore) nel Modello dell'Oracolo Casuale (Quantum) Random Oracle Model (QROM). La prova si riduce alla sicurezza EUF-CMA dello schema di firma a reticoli sottostante (assunzioni SelfTargetMSIS/MSIS).
- Ritirabilità: Lo schema è dimostrato ritirabile, il che significa che un avversario non può distinguere se una firma è stata generata dal firmatario o dal verificatore designato. Per l'istanza no-hint, questa proprietà è statistica (informazionale) con $\varepsilon_{zk} = 0$ , basandosi sulla perfetta naHVZK (non-abort honest-verifier zero-knowledge) dello schema di identificazione sottostante e sull'entropia minima dei commitment.
Adattamento ai Vincoli Post-Quantum: L'articolo affronta esplicitamente la mancanza di un segreto condiviso Diffie-Hellman basato su reticoli. Dimostra che la designazione può essere ottenuta tramite Crittografia a Chiave Pubblica (PKE) piuttosto che tramite NIKE, e che l'ambiguità del firmatario può essere ottenuta tramite OR-proof piuttosto che tramite simmetria algebrica.

Risultati

Sicurezza Concreta: Per l'istanza Dilithium no-hint, il documento fornisce limiti di sicurezza concreti. Il vantaggio di infalsificabilità è limitato dalla sicurezza dello schema sottostante più un termine trascurabile relativo alla programmazione dell'oracolo casuale ( $2^{-1024}$ ). Il vantaggio di ritirabilità è limitato da $1/2$ più un termine statistico trascurabile, ottenendo efficacemente un'ambiguità perfetta per il verificatore designato nel caso no-hint.
Confronto: Gli autori forniscono un confronto dettagliato con lo schema Liu–Baek–Susilo (Tabella 2). Sebbene la costruzione a reticoli richieda materiale di chiave aggiuntivo (chiavi di cifratura) e comporti firme più grandi (a causa dell'overhead di cifratura), essa acquisisce due proprietà significative: la firma ritirabile è pseudocasuale (nascondendo la sua esistenza a terze parti) e la non-trasferibilità contro il verificatore designato è perfetta (statistica) anziché computazionale.

Significatività
L'articolo rivendica la significatività come un adattamento necessario del primitivo di firma ritirabile nell'era post-quantistica. Stabilisce che la ritirabilità è ottenibile nella crittografia a reticoli senza fare affidamento su analoghi Diffie-Hellman basati su reticoli inefficienti o inesistenti. Separando i meccanismi di designazione (cifratura) e di ambiguità (OR-proofs), gli autori forniscono una costruzione robusta e provabilmente sicura che mantiene le proprietà di sicurezza degli schemi sottostanti come Dilithium, aggiungendo al contempo la fondamentale flessibilità della revoca della firma. Il lavoro suggerisce che queste costruzioni potrebbero potenziare la resistenza quantistica nei sistemi blockchain dove la revoca delle transazioni è desiderabile ma tradizionalmente difficile da implementare.