Quantum Oracle Distribution Switching and its Applications to Fully Anonymous Ring Signatures

1. Il Problema

Le firme ad anello (Ring Signatures - RSS) sono primitive crittografiche che permettono a un membro di un gruppo di firmare un messaggio a nome dell'intero gruppo senza rivelare la propria identità. Sono fondamentali per protocolli di scambio di chiavi autenticati e deniabili (DAKE), come le versioni post-quantum del protocollo Signal utilizzato in servizi di messaggistica crittografata end-to-end (es. WhatsApp, Signal).

Attualmente, le costruzioni di firme ad anello più efficienti e promettenti per l'uso post-quantum (come quelle basate sul paradigma AOS o su ring trapdoor come Gandalf e FalconRS) sono state dimostrate sicure solo nel modello Random Oracle Classico (ROM). Tuttavia, nel contesto della sicurezza post-quantum, è necessario dimostrare la sicurezza nel modello Random Oracle Quantistico (QROM), dove l'avversario ha accesso quantistico all'oracolo casuale.

Il problema principale affrontato dagli autori è che le tecniche di riduzione di sicurezza classiche (spesso basate sulla distanza statistica o sulla divergenza di Rényi applicate a distribuzioni classiche) non si traducono direttamente o sono insufficienti nel regime quantistico. In particolare, l'uso della divergenza di Rényi per sostituire l'intera distribuzione di un oracolo fallisce nel QROM a causa di algoritmi quantistici come quello di Deutsch-Jozsa, che possono distinguere distribuzioni con un rapporto di probabilità illimitato.

2. Metodologia

Gli autori sviluppano un quadro teorico e tecnico per colmare il divario tra ROM e QROM per le firme ad anello. La metodologia si articola in tre pilastri principali:

• Quantum Oracle Distribution Switching (QODS):
  Gli autori studiano il comportamento degli algoritmi quantistici che interagiscono con un oracolo i cui output sono campionati indipendentemente da una distribuzione $P$ o $Q$.

  • Dimostrano che la distanza statistica tra le distribuzioni di output di un algoritmo con $q$ query quantistiche è limitata da $O(q\sqrt{\epsilon})$, dove $\epsilon$ è la distanza statistica tra $P$ e $Q$. Questo risultato è ottenuto utilizzando la tecnica dell'oracolo compresso (compressed oracle).
  • Analizzano l'uso della divergenza di Rényi. Dimostrano che, a differenza del caso classico, non è possibile sostituire l'intera distribuzione di un oracolo quantistico mantenendo un limite moltiplicativo basato sulla divergenza di Rényi (fornendo un controesempio basato sull'algoritmo di Deutsch-Jozsa).
  • Propongono una soluzione pratica: invece di sostituire l'intera distribuzione, si sostituiscono solo un numero limitato di valori (reprogramming adattivo). In questo scenario limitato, le proprietà classiche della divergenza di Rényi possono essere riutilizzate, introducendo un termine di errore additivo controllabile.

• Generalizzazione delle Riduzioni "History-Free":
  Estendono la tecnica delle riduzioni "history-free" (senza memoria), introdotta da Boneh et al. per le firme digitali, al contesto delle firme ad anello. Questa tecnica permette di simulare l'oracolo casuale e l'oracolo di firma senza conoscere le query future, basandosi su argomenti di distanza statistica per garantire la sicurezza nel QROM.

• Tecnica Measure-and-Reprogram:
  Utilizzano la tecnica measure-and-reprogram per gestire l'ordinamento temporale delle query in un contesto quantistico, essenziale per le riduzioni di sicurezza che richiedono una sequenza specifica di eventi (es. impegno prima della sfida).

3. Contributi Chiave

1. Quadro Teorico QODS:

   • Forniscono limiti espliciti e stretti per la distanza statistica tra le uscite di algoritmi quantistici che interagiscono con oracoli basati su distribuzioni diverse.
   • Dimostrano l'impossibilità di un limite moltiplicativo puro basato sulla divergenza di Rényi per la sostituzione completa di un oracolo nel QROM.
   • Propongono un metodo di "switching" parziale (sostituzione di posizioni specifiche) che permette di utilizzare la divergenza di Rényi con un errore additivo, rendendo la tecnica applicabile in scenari pratici come la sicurezza delle firme.

2. Sicurezza QROM per Firme ad Anello basate su Ring Preimage Sampleable Functions (RPSF):

   • Formalizzano il concetto di Ring Preimage Sampleable Functions (RPSF), generalizzando le funzioni con preimmagine campionabile (PSF) per le firme ad anello.
   • Costruiscono una generica firma ad anello basata su RPSF.
   • Forniscono due prove di sicurezza per questa costruzione nel QROM:
     • Una basata su riduzioni history-free (usando la distanza statistica).
     • Una basata sul reprogramming adattivo (usando la divergenza di Rényi per i valori campionati), che richiede l'aggiunta di "salt" (sale) per garantire l'alta entropia minima necessaria.

3. Sicurezza QROM per le Firme AOS (Abe-Ohkubo-Suzuki):

   • Analizzano il framework AOS, che trasforma protocolli $\Sigma$ in firme ad anello lineari.
   • Forniscono due limiti di sicurezza:
     • Un limite generico per protocolli $\Sigma$ qualsiasi, utilizzando la tecnica measure-and-reprogram. Questo limite ha una perdita esponenziale nella dimensione dell'anello ($N$), ma è significativo per anelli piccoli (es. dimensione 2, necessaria per i protocolli tipo Signal).
     • Un limite stretto (multiplicativamente) per protocolli $\Sigma$ con struttura Commit-and-Open (C&O), utilizzando tecniche di estrazione straightline e proprietà dell'oracolo compresso. Questo risultato evita la perdita esponenziale.

4. Istante e Discussione:

   • Applicano i loro risultati a costruzioni concrete come Gandalf e FalconRS, mostrando come i parametri e le prove possano essere adattati al QROM.
   • Discutono le implicazioni per Falcon, un candidato NIST per le firme digitali. Sottolineano che la prova di sicurezza attuale di Falcon, che si basa sulla divergenza di Rényi per la uniformità del dominio, potrebbe non reggere nel QROM senza le correzioni proposte in questo lavoro.

4. Risultati Principali

• Dimostrazione di Sicurezza: Sono state fornite le prime riduzioni di sicurezza nel QROM per due classi principali di firme ad anello post-quantum (basate su RPSF e AOS), risolvendo un gap critico nella letteratura sulla sicurezza post-quantum.
• Limiti di Sicurezza:
  • Per le firme basate su RPSF, la sicurezza è ridotta alla resistenza alle collisioni e alla one-wayness delle funzioni sottostanti, con perdite di sicurezza gestibili (additive o moltiplicative controllate).
  • Per le firme AOS, è stata ottenuta una prova di sicurezza stretta per i protocolli Commit-and-Open, che è cruciale per le implementazioni efficienti.
• Analisi della Divergenza di Rényi: È stato stabilito che la divergenza di Rényi non può essere usata per sostituire l'intero oracolo nel QROM, ma rimane uno strumento potente se applicata a un sottoinsieme limitato di query (reprogramming), a condizione di accettare un termine di errore additivo.

5. Significato e Impatto

Questo lavoro è fondamentale per la transizione verso la crittografia post-quantum sicura e deniabile:

• Sicurezza dei Protocolli di Messaggistica: Permette di costruire versioni post-quantum del protocollo Signal (e simili) con garanzie di sicurezza formali nel modello quantistico, eliminando la necessità di accettare protocolli con sicurezza non provata o di usare soluzioni inefficienti (come split-KEM).
• Validazione di Standard: Offre un'analisi critica e strumenti per validare o correggere le prove di sicurezza di candidati standard come Falcon, suggerendo che le attuali prove potrebbero essere insufficienti senza l'uso di tecniche di reprogramming adattivo o salt.
• Avanzamento Teorico: I risultati sul "Quantum Oracle Distribution Switching" e sull'uso della divergenza di Rényi nel QROM costituiscono contributi teorici indipendenti che potrebbero trovare applicazione in altri campi della crittografia quantistica, andando oltre le sole firme ad anello.

In sintesi, gli autori non solo risolvono il problema della sicurezza QROM per le firme ad anello, ma forniscono anche nuovi strumenti tecnici per analizzare la sicurezza degli oracoli quantistici, ponendo le basi per protocolli di comunicazione privati e sicuri nell'era dei computer quantistici.