Succinct Arguments for QMA from Collapsing Hash Functions

Nel mondo della crittografia, esiste una costante tensione tra sicurezza ed efficienza. Da un lato, abbiamo la necessità di verificare che un calcolo complesso sia stato eseguito correttamente senza dover rifare l'intero calcolo noi stessi. Questo è il regno degli argomenti succinti, un metodo che permette a un verificatore di controllare una prova utilizzando molte meno risorse rispetto al tempo impiegato per crearla. Per decenni, questa tecnologia è stata una pietra miliare della fiducia digitale, abilitando tutto, dalla verifica della blockchain al cloud computing sicuro. Tuttavia, è esistito un divario significativo tra il mondo classico dei computer standard e il mondo emergente dei computer quantistici. Sebbene sappiamo come creare queste prove efficienti per problemi classici utilizzando solo strumenti matematici di base e non strutturati, fare lo stesso per i problemi quantistici ha sembrato richiedere macchinari crittografici molto più pesanti e complessi. La convinzione prevalente era che la verifica di prove quantistiche avrebbe sempre richiesto il tipo di sistemi di crittografia a chiave pubblica avanzati, che sono molto più costosi dal punto di vista computazionale e strutturalmente più complessi rispetto agli strumenti semplici usati per la verifica classica.

Questo articolo cambia questo panorama dimostrando che la verifica efficiente di prove quantistiche è possibile utilizzando solo le assunzioni crittografiche più semplici e fondamentali. I ricercatori hanno costruito un protocollo che permette a un cliente di verificare un calcolo quantistico con alta fiducia, basandosi esclusivamente sull'esistenza di "funzioni hash collassanti". Queste funzioni sono la versione quantum-safe di uno strumento di base utilizzato per garantire l'integrità dei dati, rappresentando il livello più debole di sicurezza crittografica richiesto per questo compito. Dimostrando che un tale sistema può essere costruito senza la necessità della pesante macchina della crittografia a chiave pubblica, gli autori mostrano che la capacità di verificare i calcoli quantistici risiede in un livello di crittografia molto più semplice e accessibile di quanto precedentemente pensato. Questo traguardo colma un divario critico, suggerendo che gli strumenti necessari per mettere in sicurezza il futuro quantistico sono già alla portata, radicati negli stessi principi fondamentali che proteggono il nostro attuale mondo digitale.

Il cuore di questa svolta risiede in un nuovo metodo per generare un tipo specifico di correlazione quantistica noto come "stato claw" (stato a artiglio). Per comprenderne la portata, immaginate uno scenario in cui un server potente vuole dimostrare di aver eseguito un calcolo complesso, ma un cliente più debole vuole controllare il lavoro senza eseguire il calcolo esso stesso. Il cliente deve stabilire una connessione segreta e condivisa con il server che provi che il server stia seguendo le regole, senza rivelare il segreto stesso. Nei tentativi precedenti, creare queste connessioni richiedeva al cliente di eseguire una quantità massiccia di lavoro quantistico o di fare affidamento su complessi sistemi a chiave pubblica. Gli autori hanno compreso che il cliente non deve essere interamente classico; può eseguire una piccola quantità fissa di operazioni quantistiche e comunque raggiungere l'obiettivo. Questa intuizione ha permesso loro di progettare un protocollo in cui il cliente prepara in anticipo una serie di messaggi quantistici accuratamente preparati, prima che inizi qualsiasi interazione. Il server elabora poi questi messaggi per generare migliaia di queste connessioni "claw" segrete, mentre il cliente esegue solo una minima quantità di lavoro quantistico.

Il protocollo funziona facendo sì che il cliente invii una sovrapposizione di molte possibilità contemporaneamente durante ogni round di interazione. Il server, utilizzando solo la comunicazione classica e la propria potenza di calcolo, è in grado di "collassare" questa sovrapposizione in un insieme di stati quantistici specifici e verificati. La parte intelligente del design è che il server può generare un numero vastissimo di questi stati, ma non può scoprire le etichette segrete specifiche associate ad essi. Se il server tenta di indovinare le etichette, il protocollo è progettato in modo che la probabilità di indovinare correttamente scenda drasticamente. Per rendere robusta questa sicurezza, i ricercatori eseguono questo processo molte volte in sequenza, inviando più messaggi quantistici in serie. Utilizzano poi una tecnica per "incollare" i risultati di queste esecuzioni separate, creando un singolo stato quantistico altamente sicuro. Questo processo di amplificazione assicura che, anche se il server ha una piccola possibilità di deviare in un'istanza, la possibilità di deviare attraverso tutte le istanze diventi infinitamente piccola, rendendo di fatto il sistema sicuro contro qualsiasi attacco realistico.

Questo nuovo metodo per generare correlazioni quantistiche funge da motore per un sistema più ampio chiamato "delega cieca" (blind delegation). In questa configurazione, un cliente può delegare un calcolo quantistico complesso a un server senza che il server apprenda nulla su cosa sia il calcolo o su come sia fatto il dato di input. Il cliente fornisce al server le risorse quantistiche necessarie, e il server esegue il calcolo, restituendo un risultato che il cliente può verificare. Poiché il nuovo protocollo è così efficiente e richiede risorse quantistiche minime dal cliente, si inserisce perfettamente in un framework che comprime la comunicazione tra le due parti. Combinando questo metodo di delega efficiente con un compilatore che riduce la quantità di dati scambiati, i ricercatori hanno creato un sistema completo di argomenti succinti per problemi quantistici. Il risultato finale è un protocollo in cui la quantità totale di dati scambiati è piccola, e il tempo necessario al cliente per verificare il risultato dipende solo dalla dimensione dell'enunciato del problema, non da quanto tempo è durato il calcolo. È importante notare, tuttavia, che questo protocollo richiede che il verificatore sia quantistico e utilizzi la comunicazione quantistica, il che rappresenta un limite fondamentale dell'approccio attuale.

La portata di questo lavoro va oltre i dettagli tecnici del protocollo. Risolve una questione di lunga data riguardo i requisiti fondamentali della verifica quantistica. Per anni, non era chiaro se la verifica di prove quantistiche richiedesse gli strumenti pesanti e complessi della crittografia a chiave pubblica o se potesse essere costruita con gli strumenti più leggeri e semplici utilizzati per la verifica classica. Gli autori hanno dimostrato che la seconda ipotesi è quella corretta. Hanno dimostrato che l'esistenza di questi sistemi di verifica quantistica efficienti è garantita dalle stesse assunzioni di base che sostengono la sicurezza di Internet oggi. Questo colloca la capacità di verificare i calcoli quantistici in una categoria di crittografia nota come "Minicrypt", un regno definito da assunzioni semplici e non strutturate, piuttosto che nel regno più complesso della "Cryptomania" che si pensava fosse necessario. Questa scoperta suggerisce che l'infrastruttura per un futuro quantistico sicuro potrebbe essere più semplice e robusta del previsto, basandosi sugli stessi blocchi fondamentali che hanno protetto il nostro mondo digitale per decenni.