Riepilogo Tecnico: Come Firmare Messaggi Quantistici

1. Definizione del Problema

La trasmissione sicura di dati quantistici all'interno di una futura internet quantistica richiede meccanismi sia per la cifratura che per l'autenticazione. Sebbene la cifratura quantistica sia stata raggiunta sotto assunzioni standard, firmare messaggi quantistici è stato a lungo considerato impossibile, anche sotto assunzioni computazionali. Risultati di impossibilità precedenti (ad es. Barnum et al., Alagic et al.) hanno stabilito che qualsiasi algoritmo di verifica capace di dedurre un messaggio quantistico da una firma può essere invertito per falsificare una firma per un messaggio diverso.

Di conseguenza, la comunità crittografica si è affidata alla signcriptografia (signcryption), un primitivo che combina cifratura e firma. Tuttavia, la signcriptografia manca di verificabilità pubblica; solo il destinatario intenzionale (in possesso di una chiave di decifrazione segreta) può verificare l'autenticità. Questa limitazione impedisce l'instaurazione di un'infrastruttura a chiave pubblica (PKI) per i sistemi quantistici, dove le chiavi pubbliche devono essere autenticate senza segreti pre-condivisi. Inoltre, l'impossibilità di firmare stati quantistici ha ostacolato la realizzazione di denaro quantistico a chiave pubblica, un obiettivo che è rimasto elusivo sotto assunzioni computazionali standard, richiedendo spesso assunzioni forti e potenzialmente insicure come l'offuscamento indistinguibile.

Questo lavoro sfida la nozione che firmare messaggi quantistici sia impossibile introducendo la dipendenza dal tempo e la memoria quantistica limitata come risorse per aggirare gli attacchi di inversione inerenti agli standard schemi di firma.

2. Metodologia e Concetti Fondamentali

Gli autori propongono tre approoli distinti per firmare messaggi quantistici, sfruttando due vincoli primari per prevenire la falsificazione: il tempo e la memoria quantistica.

A. Firme Dipendenti dal Tempo (TD)

L'innovazione centrale è l'introduzione delle firme dipendenti dal tempo (TD - Time-Dependent), in cui gli algoritmi di firma e di verifica dipendono dal tempo corrente $t$. L'intuizione fondamentale è che l' "attacco di inversione" (invertire la verifica per falsificare una firma) richiede risorse che diventano proibitive quando il tempo è un fattore.

• Meccanismo: Una firma è valida solo se verificata entro una specifica finestra temporale rispetto alla sua creazione. Se un avversario tenta di invertire il processo di verifica per falsificare una nuova firma, il tempo necessario per risolvere il problema crittografico sottostante rende la firma falsificata obsoleta al momento della sua generazione.
• Assunzioni: Le costruzioni si basano su Funzioni Unidirezionali Post-Quantistiche (pq-OWFs) e, in alcuni casi, su Puzzle di Blocco Temporale (TLPs - Time-Lock Puzzles). I TLP garantiscono che un messaggio (o una chiave) rimanga nascosto per una durata specifica $t$, ma possa essere decifrato poco dopo.

B. Chiavi di Verifica Dinamiche (TD-DVK)

Per eliminare la dipendenza dai TLP, gli autori introducono le firme TD con Chiavi di Verifica Dinamiche (TD-DVK).

• Meccanismo: La chiave di verifica evolve nel tempo. Una chiave segreta viene utilizzata per generare chiavi di firma temporanee per specifici intervalli di tempo. La chiave di verifica per un determinato intervallo viene annunciata dopo che l'intervallo è trascorso.
• Sicurezza: Un avversario non può falsificare una firma per un intervallo passato perché non può prevedere la chiave di firma (protetta da pq-PRFs). Non può falsificare una firma per il futuro perché la chiave di verifica per l'intervallo corrente non è ancora stata annunciata, e la chiave di firma per l'intervallo futuro è sconosciuta. Ciò crea una proprietà di sicurezza "scomparsa" in cui le firme scadono.

C. Modello di Memoria Quantistica Limitata (BQSM)

Il secondo approccio principale opera sotto il Modello di Memoria Quantistica Limitata (BQSM - Bounded Quantum Storage Model), in cui gli avversari sono limitati nella loro memoria quantistica ($s$ qubit).

• Meccanismo: Questo approccio utilizza primitivi di programmi monouso e broadcast di programmi. La chiave pubblica è uno stato quantistico di grandi dimensioni (un broadcast di un programma) che gli utenti possono memorizzare solo parzialmente a causa dei vincoli di memoria.
• Sicurezza: La firma coinvolge programmi monouso che rivelano le informazioni necessarie per la verifica solo quando valutati su input specifici derivati dalla subchiave memorizzata dall'utente. Un avversario con memoria limitata non può memorizzare abbastanza informazioni per falsificare una firma o manomettere una firma esistente senza essere rilevato, poiché non può mantenere l'entanglement o lo stato necessario durante il processo di verifica.

3. Contributi Chiave e Risultati

1. Firme Dipendenti dal Tempo (Due Costruzioni)

• Costruzione 1 (basata su TLP): Uno schema di firma TD che assume pq-OWFs e TLP. La firma consiste in un messaggio quantistico cifrato e un TLP contenente la chiave di decifrazione e un timestamp. La verifica richiede la risoluzione del TLP, che richiede tempo $t$. Al momento in cui la chiave viene rivelata, la firma è scaduta.
• Costluzione 2 (TD-DVK): Uno schema di firma TD basato esclusivamente su pq-OWFs. Utilizza uno schema di cifratura autenticata simmetrica in cui la chiave viene rivelata solo dopo l'intervallo di firma. Questa costruzione raggiunge la non falsificabilità quantistica (QUF) e una proprietà di scomparsa (le firme non possono essere riutilizzate o falsificate per messaggi passati anche se una firma è stata precedentamente osservata).

2. Firme nel BQSM

• Costruzione 3: Uno schema di firma a sicurezza informazionale per messaggi quantistici nel BQSM.
• Caratteristiche: Affronta tre limitazioni del lavoro precedente sul BQSM: firma messaggi quantistici (non solo classici), è sicuro contro avversari con accesso illimitato all'oracolo di firma (a differenza dei lavori precedenti) e include chiavi pubbliche quantistiche certificate.
• Meccanismo: La chiave pubblica è un broadcast di un programma di una funzione lineare. La firma utilizza due programmi monouso interdipendenti per autenticare il messaggio e la chiave, impedendo a un avversario di modificare la firma senza conoscere la chiave segreta, che non può ricostruire completamente a causa dei limiti di memoria.

3. Applicazioni

Gli autori dimostrano che le firme TD consentono diversi primitivi crittografici precedentemente difficili o impossibili:

• Chiavi Pubbliche Quantistiche Autenticate (QPKE):

  • Costruzione 4 (Stato Misto): Uno schema QPKE che utilizza firme TD-DVK per autenticare chiavi pubbliche quantistiche a stato misto. Raggiunge la sicurezza IND-qCKCA2 (indistinguibilità sotto attacco adattivo scelto di chiavi e ciphertext quantistici) da pq-OWFs.
  • Costruzione 5 (Stato Puro): Uno schema QPKE che utilizza firme TD-DVK monouso per autenticare chiavi a stato puro. Questo schema raggiunge la sicurezza IND-CKPA basata su Stati di Funzioni Pseudocasuali (PRFS), un'assunzione potenzialmente più debole rispetto alle pq-OWFs. Risolve questioni aperte riguardanti gli errori di decifrazione e la forza delle assunzioni nei lavori QPKE precedenti.

• Denaro Quantistico a Chiave Pubblica:

  • Schema Semi-Online (TD-DVK): Uno schema di denaro quantistico a chiave pubblica basato su pq-OWFs. Le banconote sono stati quantistici cifrati con molteplici livelli di QAE monouso. Le chiavi di verifica vengono annunciate periodicamente, permettendo agli utenti di validare la banconota. La banconota scade dopo che tutte le chiavi sono state rivelate.
  • Schema Offline (TD + TLP): Uno schema di denaro quantistico a chiave pubblica completamente offline basato su pq-OWFs e TLP. Le chiavi sono codificate in TLP, permettendo agli utenti di dedurle solo in momenti specifici senza interagire con la banca. È il primo schema di denaro quantistico a chiave pubblica costruito da assunzioni computazionali standard (pq-OWFs).

4. Significato e Rivendicazioni

Il documento afferma di essere il primo lavoro in grado di firmare messaggi quantistici senza utilizzare la signcriptografia, ottenendo così la verificabilità pubblica per i dati quantistici.

• Superamento dell'Impossibilità: Il lavoro sfida l'impossibilità stabilita di firmare l'informazione quantistica dimostrando che ciò è realizzabile quando il processo di verifica è vincolato dal tempo o dalla memoria.
• Assunzioni Standard: Fornisce le prime costruzioni per il denaro quantistico a chiave pubblica e le chiavi pubbliche quantistiche autenticate basate su assunzioni computazionali standard (pq-OWFs), evitando la necessità di offuscamento indistinguibile o altre assunzioni complesse e potenzialmente insicure.
• Praticità del Tempo: Gli autori sostengono che il tempo agisca come una forma di sincronizzazione semplice da implementare in pratica, offrendo uno strumento potente per costruire primitivi crittografici fondamentali.
• Livelli di Sicurezza: La costruzione BQSM offre sicurezza informazionale, mentre le costruzioni TD offrono sicurezza computazionale basata su assunzioni post-quantistiche ben studiate.

Gli autori riconoscono i limiti, come la scadenza di firme e banconote e la necessità di sincronizzazione temporale o annunci di chiavi dinamiche. Tuttavia, sostengono che questi siano scambi ragionevoli per ottenere sistemi crittografici quantistici pubblicamente verificabili e resistenti alle manomissioni. Il lavoro apre nuove strade per la ricerca nei modelli dipendenti dal tempo e nell'applicazione dei modelli di memoria limitata ad altri primitivi crittografici.