Sintesi Tecnica: Firme Digitali con Classical Shadows su Computer Quantistici Near-Term

Definizione del Problema

I tradizionali schemi di firma digitale si basano sull'esistenza di funzioni unidirezionali (OWF), come la fattorizzazione di interi (RSA) o i problemi basati su reticoli (LWE). Tali assunzioni sono vulnerabili a computer quantistici tolleranti ai guasti (ad esempio, l'algoritmo di Shor) e sono oggetto di ricerca costante riguardo alla loro sicurezza contro avversari quantistici. Sebbene la meccanica quantistica offra primitive crittografiche alternative fondate sulle leggi fisiche piuttosto che sulla durezza matematica, le proposte esistenti per le firme digitali quantistiche (QDS) richiedono tipicamente la trasmissione e lo stoccaggio coerente di stati quantistici come chiavi pubbliche. Questa dipendenza da comunicazioni quantistiche a basso rumore e da memorie quantistiche a lungo termine rende le attuali proposte impraticabili per i dispositivi quantistici near-term.

La sfida centrale affrontata in questo lavoro è la realizzazione di uno schema di firma digitale quantistica che:

1. Non si basi su OWF o sull'esistenza di funzioni unidirezionali.
2. Operi utilizzando esclusivamente la comunicazione classica, eliminando la necessità di memoria quantistica o della trasmissione quantistica delle chiavi pubbliche.
3. Sia fattibile su hardware NISQ (Noisy Intermediate-Scale Quantum) near-term.

Metodologia

Concetto Centrale: Classical Shadows come Chiavi Pubbliche

Gli autori propongono uno schema di firma in cui le chiavi pubbliche non sono stati quantistici, ma classical shadows (ombre classiche) di stati quantistici.

• Chiave Segreta: Due circuiti quantistici casuali, $C_0$ e $C_1$.
• Chiave Pubblica: Classical shadows, $S(|C_0\rangle)$ e $S(|C_1\rangle)$, generati eseguendo misurazioni casuali sugli stati $|C_b\rangle = C_b|0\rangle$.
• Firma: Per firmare un bit $b$, il mittente rivela la descrizione classica del circuito $C_b$.
• Verifica: Il ricevente utilizza le ombre pubbliche e il circuito rivelato per verificare che il circuito $C_b$ produca uno stato coerente con le ombre pubbliche. Ciò viene ottenuto tramite un protocollo di sovrapposizione di ombre (shadow overlap protocol).

Assunzione di Sicurezza: Computational No-Learning (CNL)

La sicurezza dello schema poggia sulla congettura Computational No-Learning (CNL) dai shadows. Questa congettura postula che sia computazionalmente impraticabile per un avversario apprendere la descrizione di un circuito quantistico casuale partendo solo dai suoi shadows classici (campioni di lunghezza polinomiale di misurazioni casuali).

• Questa assunzione è distinta e più debole della standard congettura "no-learning from states", poiché i shadows derivano da copie dello stato tramite semplici misurazioni.
• Il documento fornisce prove teoriche che gli algoritmi di apprendimento esistenti (ad esempio, quelli basati su inversione locale o argomenti di light-cone) falliscono nel apprendere questi circuiti sotto i vincoli del protocollo (apprendimento appropriato, geometria arbitraria e accesso limitato ai soli shadows).
• Gli autori dimostrano una separazione tra il tempo richiesto per verificare una firma (esponenziale in $n$, ma fattibile per il verificatore) e il tempo richiesto per apprendere (spoofing) il circuito (esponenzialmente più difficile), creando un gap di sicurezza.

Innovazioni Tecniche

Per rendere lo schema utilizzabile su hardware rumoroso, gli autori introducono due miglioramenti tecnici chiave:

1. Protocollo di Shadow Overlap Migliorato: Modificano i protocolli di shadow overlap esistenti (basati sul Riferimento [30]) utilizzando circuiti Clifford casuali su sottoinsiemi di qubit anziché solo misurazioni di Pauli casuali. Ciò riduce il "tempo di rilassamento" ($\tau$) della catena di Markov per la certificazione e abbassa la varianza dello stimatore, migliorando significamente la tolleranza al rumore e riducendo la complessità campionaria richiesta per la certificazione.
2. Rilevamento dell'Errore Quantistico (QED): Per superare l'infedeltà dell'hardware, gli autori impiegano un codice di rilevamento dell'errore Iceberg multi-blocco.
   • Il codice Iceberg codifica $k$ qubit logici in $k+2$ qubit fisici.
   • Utilizzano il gauge fixing per promuovere determinati operatori logici a stabilizzatori, creando qubit "proxy" che permettono la parallelizzazione di gate logici a singolo qubit, riducendo così la profondità del circuito e gli errori di memoria.
   • Questo approccio raggiunge prestazioni "oltre il break-even", dove la fedeltà codificata supera la fedeltà non codificata nonostante l'overhead.

Risultati Chiave

Evidenza Teorica

• Difficoltà di Apprendimento: Gli autori mostrano che gli algoritmi noti per l'apprendimento di circuiti poco profondi (shallow circuits) falliscono nel soddisfare le condizioni necessarie (apprendimento appropriato, geometria arbitraria, accesso ai soli shadows) per violare lo schema.
• Gap di Sicurezza: Dimostrano che, per specifici ensemble di circuiti (approximate designs), la complessità temporale per un avversario che tenta di apprendere il circuito tramite polinomi di basso grado o training variazionale è esponenzialmente maggiore rispetto al tempo richiesto per la verifica. Nello specifico, mostrano che il training variazionale richiede un numero esponenziale di query per raggiungere la fedeltà target per le profondità dei circuiti utilizzate.

Dimostrazione Sperimentale

Gli autori hanno implementato il protocollo sul processore a ioni intrappolati Quantinuum H2 (56 qubit fisici).

• Parametri del Circuito: Hanno generato shadows per stati a 32 qubit utilizzando circuiti casuali con $\ge 80$ gate logici a due qubit (corrispondenti a $\ge 582$ gate fisici a due qubit).
• Fedeltà: Utilizzando il codice Iceberg multi-blocco con gauge fixing, hanno ottenuto una fedeltà certificata di $0.90 \pm 0.01$ con 17.316 campioni.
• Prova di Principio: L'esperimento ha dimostrato con successo la capacità di distinguere tra un firmatario onesto e un avversario. Gli autori hanno calcolato che aumentare la dimensione del campione di un fattore 19,5 (circa 340k campioni) sarebbe sufficiente per raggiungere un parametro di sicurezza in cui la probabilità che un avversario computazionalmente limitato riesca a falsificare la firma sia trascurabile ($< 10^{-5}$).

Significato e Rivendicazioni

Il documento rivendica di aver dimostrato la fattibilità near-term di firme digitali quantistiche che non dipendono da OWF o da comunicazione quantistica.

• Indipendenza dalle OWF: Lo schema fonda la sicurezza nella difficoltà fisica di apprendere processi quantistici, offrendo una via per la crittografia che rimane sicura anche qualora le OWF non esistessero.
• Compatibilità NISQ: Utilizzando classical shadows e codici di rilevamento dell'errore anziché la correzione completa dell'errore, il protocollo opera entro le capacità degli attuali hardware quantistici rumorosi.
• Primitiva Fondamentale: Il lavoro stabilisce un legame tra le firme digitali quantistiche e i one-way puzzles, una primitiva che consente la costruzione di altre primitive crittografiche quantistiche (come gli impegni di bit non interattivi) senza assumere l'esistenza di OWF.

Gli autori sottolineano che, sebbene la dimostrazione attuale sia una prova di principio per una firma a singolo bit, le primitive sottostanti (certificazione di shadow overlap e rilevamento dell'errore) sono scalabili. Notano che estendere questo approccio a messaggi multi-bit è possibile utilizzando codici di correzione dell'errore classici per ridurre i costi di verifica, e che aumentare la dimensione del circuito favorirebbe ulteriormente la sicurezza contro potenziali futuri progressi negli algoritmi di apprendimento.