Lattice-based extended withdrawability

Sintesi Tecnica: Estendibilità di Prelievo Basata su Reticoli (Lattice-based Extended Withdrawability)

Definizione del Problema
Le firme digitali tradizionalmente forniscono permanenza: una volta firmato, un messaggio rimane verificabile sotto la chiave pubblica del firmatario indefinitamente. Tuttavia, molte applicazioni decentralizzate (ad esempio, accesso a tempo limitato, accordi revocabili, escrow decentralizzati) richiedono la capacità di ritirare una firma senza rivelare la chiave segreta o invalidare altre firme. Liu, Susilo e Baek hanno introdotto le firme estendibili di prelievo (Extended Withdrawable Signatures - EWS) per affrontare questo problema, consentendo che una firma sia ambigua tra un insieme di potenziali firmatari finché il vero firmatario non la "conferma". La loro costruzione si basa su primitive del logaritmo discreto (firme di Schnorr e firme 1-su-N).

Questo articolo affronta il "gap post-quantum": l'algoritmo di Shor rompe la fondazione del logaritmo discreto delle attuali schemi EWS. Sebbene esistano firme basate su reticoli (ad esempio, Dilithium), una diretta "trascrizione letterale" della costruzione di Liu-Susilo-Baek (LSB) ai reticoli fallisce a causa di ostacoli strutturali. Nello specifico, lo schema LSB si basa sulla pubblicazione di spostamenti moltiplicativi delle chiavi pubbliche per re-randomizzare il contributo del firmatario. Nel contesto dei reticoli (Fiat-Shamir con aborti), tali spostamenti assumono la forma $As_1 s_j$, che condividono un fattore comune $As_1$ con la chiave pubblica del firmatario $t_i = As_1 + s_2$. La pubblicazione di questi spostamenti rivela l'identità del firmatario, rompendo l'ambiguità richiesta.

Metodologia
Gli autori propongono una nuova costruzione per le EWS basate su reticoli che si discosta dall'approccio LSB, trattando lo schema come una firma ad anello reclamabile (Park e Sealfon). Invece di tentare di re-randomizzare le chiavi pubbliche in chiaro, la costruzione separa le due funzioni core delle EWS:

1. Ambiguità: Fornita da una firma anonima 1-su-N (ad anello), utilizzata come una scatola nera (black box).
2. Conferma: Fornita dalla rivendicazione (claim) del firmatario, che consiste in una firma vincolante sull'oggetto prelevabile e nell'apertura di un impegno (commitment) occultante rispetto all'indice del firmatario.

La costruzione opera secondo il paradigma Fiat-Shamir con aborti e si basa su tre ingredienti modulari:

• Uno schema di firma di base (ad esempio, uno schema di tipo Dilithium "no-hint, full-$t$").
• Una firma anonima 1-su-N (istanziata tramite una prova lattice 1-su-molti).
• Uno schema di impegno di tipo hiding-and-binding (stile Ajtai).

La firma prelevabile $\sigma$ consiste in una firma ad anello $\sigma_r$ sul messaggio e in un impegno $C$ rispetto all'indice del firmatario, insieme all'insieme delle chiavi pubbliche. Per confermare, il firmatario rivela l'apertura $(i, \rho)$ di $C$ e firma l'intero oggetto prelevabile $\langle \mu, \pi, \sigma \rangle$ con la propria chiave segreta di base.

Contributi Chiave

1. Raffinamento del Modello di Sicurezza: Gli autori raffinano il modello di sicurezza di LSB.

   • Sostituiscono la definizione di "completezza" di LSB per l'estendibilità di prelievo con un gioco di indistinguibilità anonymity-until-claim (anonimato fino alla rivendicazione) (Definizione 14), catturando esplicitamente la garanzia di occultamento (hiding).
   • Introducono la correttezza della rivendicazione (claimability soundness) (Definizione 16), garantendo che una firma confermata vincoli a un indice di firmatario unico, impedendo a un avversario di attribuire la stessa firma a diversi membri dell'anello.
   • Formalizzano l' unforgeability under insider corruption (non falsificabilità sotto corruzione interna) con un indice target fisso, evitando la perdita di riduzione della $q_H$ (query di hash) moltiplicativa presente nella prova LSB.

2. Costruzione Generica: Viene presentata una costruzione generica di EWS sul paradigma Fiat-Shamir con aborti. Fondamentalmente, essa non pubblica alcun valore derivato dal firmatario in chiaro. L'ambiguità è derivata esclusivamente dalle proprietà di zero-knowledge della firma ad anello, e la tracciabilità è derivata dalla proprietà di binding del commitment.

3. Risultato di Impossibilità: Il documento dimostra (Proposizione 2) che una trascrizione letterale su reticoli della firma 1-su-N di LSB (utilizzando la divisione della sfida additiva) è insicura. Nel contesto dei reticoli con sfide sparse, la probabilità che un firmatario onesto produca una divisione della sfida valida è trascurabile ($2^{-\Omega(n)}$), e anche se la completezza venisse corretta, l'anonimato fallirebbe perché il trascritto simulato non sarebbe indistinguibile da uno reale.

4. Dimostrazioni di Sicurezza Complete: Gli autori forniscono riduzioni esplicite basate su giochi nel Modello di Oracle Random Quantistico (QROM) per:

   • Correttezza: Riduzione alla correttezza delle primitive sottostanti.
   • Estendibilità di Prelievo: Riduzione all'occultamento (hiding) del commitment (Decisional MLWE) e all'anonimato dello schema 1-su-N.
   • Non Falsificabilità: Riduzione alla sicurezza EUF-CMA della firma di base (senza rewinding e senza perdita $q_H$).
   • Correttezza della Rivendicazione: Riduzione al binding del commitment (MSIS).

5. Istanziazione: Lo schema è istanziato utilizzando una firma di base di tipo Dilithium "no-hint, full-$t$" e una prova lattice 1-su-molti stabilita. Il documento discute le scelte dei parametri e nota che HAETAE potrebbe servire come alternativa di base.

Risultati
Il documento stabilisce che la costruzione proposta è:

• Corretta: Le firme oneste vengono verificate con una probabilità schiacciante.
• Estendibile di Prelievo: Un avversario in possesso di tutte le chiavi segrete non può distinguere quale membro di un anello ha prodotto una firma prelevabile finché il firmatario non la conferma.
• Non Falsificabile: Anche con accesso agli oracoli di firma e alle chiavi segrete di tutti i membri dell'anello tranne il target, un avversario non può falsificare una firma confermata per un nuovo messaggio.
• Solida (Sound): Una firma confermata non può essere attribuita a due diversi firmatari.

La sicurezza si basa su assunzioni standard di moduli-reticoli: Decisional MLWE, MSIS e SelfTargetMSIS, insieme alla proprietà di zero-knowledge della prova 1-su-N.

Significatività
Il documento rivendica la sua significatività fornendo la prima realizzazione post-quantum sicura di firme estendibili di prelievo. Dimostra che la costruzione basata sul logaritmo discreto di LSB non può essere direttamente portata sui reticoli a causa della mancanza di "re-randomizzazione libera" dei valori condivisi. Riformulando il problema come una firma ad anello rivendicabile e utilizzando un meccanismo di conferma basato su commitment, gli autori ottengono uno schema che è:

• Post-Quantum Sicuro: Resistente agli avversari quantistici tramite assunzioni su reticoli.
• Pubblicamente Verificabile: A differenza delle varianti con verificatore designato, chiunque può verificare la firma prelevabile.
• Modulare: Le prove di sicurezza si basano solo sulle interfacce delle primitive sottostanti, consentendo la sostituzione di diversi componenti basati su reticoli (ad esempio, diverse firme di base o prove ad anello) senza dover ri-dimostrare l'intero sistema.
• Fedele agli Obiettivi Originali: Il design preserva gli obiettivi funzionali e l'intuizione del piano originale LSB, correggendo al contempo i suoi difetti strutturali nel contesto dei reticoli.