Quantum Time-Lock Puzzles in the Quantum Random Oracle Model

Nel mondo della crittografia, esiste un desiderio di lunga data: quello di inviare un messaggio che non possa essere letto finché non sia trascorso un determinato periodo di tempo. Immaginate una lettera digitale sigillata all'interno di una scatola che richiede una chiave, ma la chiave può essere forgiata solo eseguendo un compito che richiede esattamente un anno di lavoro continuo e passo dopo passo. Questo concetto, noto come puzzle a blocco temporale (time-lock puzzle), è la base di tecnologie come la crittografia a rilascio temporizzato, dove un segreto viene rivelato solo dopo una data prestabilita, o le aste a offerta sigillata dove le offerte rimangono nascoste fino a una scadenza. La sfida è sempre stata garantire che la persona che crea il puzzle possa farlo rapidamente, mentre la persona che cerca di risolverlo sia costretta ad attendere, anche se ha accesso a migliaia di computer potenti lavorando contemporaneamente. Per decenni, i ricercatori hanno creduto che, in un ambiente di calcolo standard, un tale puzzle fosse impossibile da costruire in modo sicuro. La logica era semplice: se il puzzle è solo un pezzo di dati, un attaccante accorto potrebbe semplicemente copiare quei dati e suddividere il lavoro tra molti processori, risolvendolo quasi istantaneamente invece di aspettare il tempo richiesto.

Questa impossibilità era vera per i computer classici, ma un team di ricercatori ha ora dimostrato che le regole cambiano quando il puzzle stesso è un oggetto quantistico. In uno studio recente, Prabhanjan Ananth e Yao-Ting Lin dimostrano che, codificando il puzzle in uno stato quantistico delicato, possono creare un blocco temporale che sia sicuro anche contro i computer quantistici più potenti, a condizione che tali computer non possano operare per l'intera durata richiesta. Il loro lavoro risolve una questione rimasta aperta per oltre quindici anni: se le leggi della meccanica quantistica possano essere utilizzate per imporre un ritardo temporale che non possa essere aggirato tramite l'elaborazione parallela. Hanno costruito un sistema in cui il puzzle viene generato in un lampo, ma risolverlo richiede un tempo sequenziale specifico che non può essere abbreviato, creando di fatto una capsula del tempo digitale che si affida alla natura fondamentale dell'informazione quantistica per mantenere al sicuro i propri segreti.

Il cuore del problema risiede nella differenza tra la creazione di un puzzle e la sua risoluzione. In un contesto classico, se un puzzle è solo una stringa di bit, un attaccante può copiare quella stringa e distribuirla a mille diversi computer. Ogni computer prova una parte diversa della soluzione simultaneamente, e il puzzle viene risolto in una frazione del tempo che richiederebbe un singolo computer. Questa capacità di copiare e parallelizzare è ciò che ha reso i puzzle a blocco temporale classici impossibili da rendere sicuri nei modelli standard utilizzati dai crittografi. I ricercatori hanno capito che la soluzione risiedeva nella proprietà unica degli stati quantistici: essi non possono essere copiati perfettamente. Se il puzzle è uno specifico stato quantistico, un attaccante è limitato a una singola copia del puzzle. Questo vincolo della copia singola è cruciale perché impedisce all'attaccante di distribuire duplicati a una rete di computer. Inveve, deve procedere attraverso la soluzione in modo sequenziale, un passo dopo l'altro, proprio come intendeva il creatore del puzzle, anche se ha accesso a molti processori paralleli.

Per costruire questo, i ricercatori hanno progettato un sistema in cui il puzzle consiste in una collezione di minuscole particelle quantistiche, ognuna preparata in una specifica e delicata configurazione. Il creatore del puzzle genera queste particelle e vi attacca alcuni indizi classici, poi invia l'intero pacchetto al destinatario. Il destinatario deve quindi eseguire una serie di operazioni per trovare un codice nascosto. Il processo è progettato in modo che il creatore possa generare il puzzle quasi istantaneamente, ma il destinatario debba trascorrere molto tempo, eseguendo una sequenza di controlli che non possono essere saltati o accelerati utilizzando più computer. I ricercatori hanno dimostrato che anche se un attaccante possiede una potenza di calcolo illimitata e può utilizzare molti processori paralleli, non può risolvere il puzzle più velocemente del limite di tempo previsto, a meno che non sia disposto ad attendere l'intera durata dei passaggi sequenziali richiesti.

La sicurezza di questo sistema si basa su un uso intelligente di funzioni casuali e del modo in cui gli stati quantistici interagiscono con esse. Il puzzle include un insieme di token quantistici, ciascuno collegato a un numero nascosto. Per trovare la soluzione, chi risolve deve testare diverse possibilità contro una funzione casuale, un processo che agisce come una serratura che si apre solo quando viene provata la chiave corretta. In un mondo classico, un attaccante potrebbe provare tutte le chiavi contemporaneamente. In questa versione quantistica, poiché il puzzle è uno stato a copia singola non duplicabile, l'attaccante non può semplicemente duplicare il puzzle per provare le chiavi in parallelo su diverse copie. Sebbene all'attaccante sia permesso effettuare molteplici query parallele all'interno di un singolo round di calcolo, la natura a copia singola del puzzle lo costringe a procedere attraverso una sequenza di round che non possono essere aggirati. I ricercatori hanno dimostrato che, anche con gli algoritmi quantistici più avanzati, l'attaccante non può ottenere un vantaggio significativo provando a indovinare la risposta o usando l'elaborazione parallela oltre la larghezza polinomiale consentita. L'unico modo per riuscire è seguire il percorso lungo e lento che il puzzle richiede.

I ricercatori hanno anche affrontato il problema di come verificare che la risposta corretta sia stata trovata senza rivelare la risposta prematuramente. Hanno incluso un tag di verifica, un piccolo pezzo di informazione classica che permette a chi risolve di controllare se ha trovato il numero nascosto corretto. Questo tag viene generato in modo da essere strettamente legato allo stato quantistico, ma non rivela la soluzione. Se chi risolve tenta di indovinare la risposta senza compiere tutto il lavoro, il tag di verifica fallirà quasi certamente, costringendolo a ricominciare da capo. Questo meccanismo assicura che chi risolve non possa tentare di aggirare il lavoro richiesto tramite tentativi ed errori, ma debba invece eseguire l'intera sequenza di operazioni necessarie per sbloccare il messaggio.

Uno degli aspetti più significativi di questo lavoro è che opera all'interno di un quadro teorico noto come modello dell'oracolo casuale quantistico (quantum random oracle model). Questo modello assume che tutte le parti abbiano accesso a una funzione casuale perfetta che può essere interrogata in modo quantistico. Sebbene sia una costruzione teorica, fornisce una solida base per dimostrare che il sistema è sicuro contro qualsiasi possibile attacco che rispetti le leggi della meccanica quantistica. I ricercatori hanno dimostrato che la loro costruzione è efficiente, il che significa che il puzzle può essere creato rapidamente, e che rimane sicura anche se l'attaccante ha accesso a un gran numero di processori paralleli. Hanno provato che per qualsiasi ritardo desiderato, come un anno, il puzzle può essere generato in un tempo che cresce molto lentamente rispetto al ritardo, mentre la sua risoluzione richiede un tempo che cresce linearmente con il ritardo.

Le implicazioni di questa scoperta sono profonde per il futuro della comunicazione sicura. Essa apre la porta a nuovi tipi di protocolli crittografici che si basano sul tempo piuttosto che solo sulla difficoltà matematica. Ad esempio, potrebbe consentire la firma di contratti equi dove entrambe le parti hanno la garanzia che l'altra non possa ritirarsi una volta trascorso il tempo, o sistemi di voto sicuri dove i voti vengono conteggiati solo dopo una specifica scadenza. I ricercatori hanno inoltre osservato che il loro approccio evita la necessità di assunzioni matematiche complesse che potrebbero essere infrante dai futuri progressi informatici. Invece, la sicurezza si basa sulle proprietà fondamentali della meccanica quantistica, che si ritiene siano infrangibili.

Nella loro costruzione, i ricercatori hanno utilizzato un tipo specifico di stato quantistico noto come stato BB84, un metodo ben noto per codificare le informazioni nei sistemi quantistici. Hanno combinato questi stati con una serie di funzioni casuali per creare un puzzle che sia semplice da generare ma difficile da risolvere. Il puzzle consiste in un gran numero di questi stati quantistici, ognuno dei quali trasporta un pezzo dell'informazione nascosta. Chi risolve deve elaborare questi stati in un ordine specifico, e qualsiasi tentativo di saltare un passaggio o di elaborarli fuori ordine comporterà il fallimento nel recupero del messaggio. I ricercatori hanno dimostrato che la probabilità che un attaccante indovini la soluzione corretta senza compiere il lavoro è così piccola da essere effettivamente nulla per qualsiasi scopo pratico.

L'articolo chiarisce anche cosa non è possibile. Conferma che se il puzzle fosse un oggetto classico, o se chi risolve fosse un computer classico, la sicurezza crollerebbe. I risultati di impossibilità per i puzzle classici rimangono validi, e il lavoro dei ricercatori non cambia questo. Il progresso è specificamente nel regno quantistico, dove il puzzle stesso è uno stato quantistico e chi risolve è un computer quantistico. Questa distinzione è fondamentale, poiché evidenzia le capacità uniche dell'informazione quantistica di imporre vincoli che sono impossibili nel mondo classico.

La prova dei ricercatori è rigorosa e si basa su una serie di passaggi logici che si costruiscono l'uno sull'altro. Hanno prima dimostrato che un singolo puzzle quantistico è sicuro contro un attaccante che può effettuare un numero limitato di query. Successivamente, hanno esteso questo risultato per dimostrare che la sicurezza regge anche quando l'attaccante può utilizzare un numero polinomiale di processori paralleli, a condizione che sia limitato a una singola copia del puzzle. Infine, hanno dimostrato che il sistema è sicuro contro un attaccante che può utilizzare qualsiasi possibile strategia quantistica, incluse quelle che comportano l'entanglement del puzzle con altri sistemi quantistici. Il risultato è una prova completa che il puzzle a blocco temporale è sicuro nelle condizioni da loro definite.

Questo lavoro rappresenta un passo avanti significativo nel campo della crittografia quantistica. Dimostra che i limiti dell'informatica classica possono essere superati abbracciando le proprietà uniche della meccanica quantistica. La capacità di creare un puzzle a blocco temporale che sia sicuro contro attaccanti quantistici apre nuove possibilità per la comunicazione sicura. Sebbene la tecnologia sia ancora teorica, la prova che un tale sistema sia possibile fornisce una solida base per sviluppi futuri. I ricercatori hanno dimostrato che, con il giusto approccio, è possibile creare una capsula del tempo digitale che sia veramente protetta dal tempo, offrendo un nuovo livello di sicurezza per l'era digitale.