Certified Randomness with Optimal Rate

Nel mondo digitale, la fiducia è una merce fragile. Quando votiamo online, generiamo codici segreti per l'attività bancaria o eleggiamo leader per reti decentralizzate, ci affidiamo a una casualità che sia veramente imprevedibile. Se questa casualità è prevedibile o influenzata, l'intero sistema crolla. Per decenni, gli scienziati hanno cercato un modo per generare tale casualità senza dover confidare nella macchina che la sta generando. Lo scenario ideale prevede un dispositivo che produca una sequenza di bit — zeri e uno — che sia così caotica e uniforme che nessuno, nemmeno il proprietario del dispositivo, avrebbe potuto indovinare il risultato in anticipo. Questo è il santo graal della "casualità certificata": una garanzia matematica che l'output sia veramente casuale, verificabile da chiunque, senza richiedere un preesistente seme segreto.

La sfida è sempre stata che i metodi esistenti producevano o una casualità debole che poteva essere facilmente manipolata, o richiedevano a un essere umano fidato di fornire un piccolo numero iniziale casuale. Un nuovo studio di Siddhartha Jain, Saachi Mutreja e Bhaskar Roberts affronta questo limite fondamentale. Hanno sviluppato un protocollo che consente a un computer quantistico di dimostrare di aver generato una sequenza di bit con una casualità quasi perfetta, anche se il computer è malizioso e la persona che controlla il risultato è completamente deterministica, non possedendo numeri casuali propri. Questa svolta rimuove la necessità di alcun punto di partenza fidato, raggiungendo un tasso di casualità che è il più alto possibile dal punto di vista teorico.

I ricercatori hanno lavorato all'interno di un framework noto come modello dell'oracolo casuale quantistico, un contesto teorico in cui tutte le parti hanno accesso a una funzione pubblica, perfettamente casuale, che funge da hash universale. In questo ambiente, hanno costruito un sistema in cui un prover quantistico può generare una lunga sequenza di bit e fornire una breve prova che la sequenza sia genuinamente casuale. L'innovazione chiave è che il verificatore, che controlla la prova, non deve essere esso stesso casuale; può essere un algoritmo fisso e deterministico. I tentativi precedenti di raggiungere ciò avevano fallito nel garantire un'alta qualità della casualità o si affidavano al fatto che il verificatore avesse un piccolo seme casuale fidato per avviare il processo. Il nuovo protocollo elimina completamente quel seme, dimostrando che un verificatore deterministico può comunque essere convinto della casualità di una lunga sequenza generata da un dispositivo quantistico non fidato.

Per comprendere la portata di ciò, bisogna osservare cosa accade quando un sistema non è perfettamente casuale. Se una sequenza di bit è solo "debolmente" casuale, potrebbe apparire caotica, ma potrebbe comunque essere influenzata verso certi schemi, rendendola vulnerabile alla previsione. I ricercatori hanno dimostrato che il loro metodo garantisce un livello di entropia, o disordine, che è quasi massimo. In termini pratici, questo significa che per una sequenza di una specifica lunghezza, il numero di bit che sono veramente imprevedibili è quasi uguale alla lunghezza totale della sequenza. L'unica minuscola perdita di casualità è un valore logaritmico, che è inevitabile a causa della natura delle leggi della fisica e del calcolo. Questo è un enorme miglioramento rispetto ai metodi precedenti, che spesso producevano sequenze in cui la quantità di casualità garantita era una minuscola frazione della lunghezza totale.

Il protocollo funziona in due fasi principali. Per prima cosa, il dispositivo quantistico genera una fonte "debolmente" casuale utilizzando una specifica costruzione matematica che è stata dimostrata sicura contro gli attacchi quantistici. Questa fonte non è ancora abbastanza buona per applicazioni ad alto rischio. Nella seconda fase, il dispositivo fa passare questa fonte attraverso una funzione di compressione, che agisce come un filtro. Questo filtro condensa la fonte debole in una sequenza di bit più corta e molto più forte. I ricercatori hanno dimostrato che anche se un avversario tenta di manipolare il processo scegliendo input specifici o osservando il comportamento della funzione, non può forzare l'output finale a essere prevedibile. La sequenza finale mantiene un alto livello di min-entropia, una misura di quanto sia difficile indovinare l'esito più probabile, anche quando l'avversario ha visto l'intera cronologia dell'interazione.

Un componente critico di questo lavoro è il concetto di min-entropia "condizionata". In molte applicazioni del mondo reale, come un faro di casualità pubblica che trasmette un nuovo numero casuale ogni ora, la sicurezza del numero corrente dipende dal fatto che non possa essere previsto anche se un attaccante conosce tutti i numeri precedenti. I ricercatori hanno dimostrato che il loro protocollo garantisce che ogni nuovo impulso di casualità sia imprevedibile, anche quando condizionato a tutti i messaggi e i dati che sono venuti prima. Ciò è essenziale per applicazioni come l'elezione dei leader nelle reti blockchain o la generazione di stringhe casuali comuni per protocolli crittografici, dove l'integrità del round corrente dipende dall'imprevedibilità del passato.

Il team ha anche affrontato i limiti del proprio lavoro con rigorosa onestà. Hanno dimostrato che è impossibile ottenere una casualità uniforme perfetta con un verificatore deterministico se all'avversario è permesso di operare per un tempo polinomiale. Un attaccante potrebbe teoricamente utilizzare una tecnica chiamata campionamento a rifiuto (rejection sampling) per fissare un piccolo numero di bit nell'output, efficacemente "truccando" il sistema per produrre un risultato leggermente distorto. Tuttavia, i ricercatori hanno dimostrato che il loro protocollo raggiunge il miglior risultato possibile sotto questi vincoli: garantisce che il numero di bit che possono essere fissati da un attaccante sia così piccolo che la casualità rimanente è comunque sufficiente per tutti gli scopi crittografici pratici. La perdita è trascurabile e la sicurezza regge contro qualsiasi avversario con capacità di calcolo realistiche.

Questo lavoro ha implicazioni immediate per il futuro della comunicazione sicura e dei sistemi decentralizzati. Rimuovendo la necessità di un seme fidato, il protocollo permette la creazione di fari di casualità che possono essere eseguiti su un singolo dispositivo quantistico non fidato. Tale faro potrebbe pubblicare periodicamente numeri casuali freschi e imprevedibili che chiunque può verificare. La sicurezza di questi numeri non dipenderebbe dall'onestà dell'operatore del dispositivo, ma dalle leggi della meccanica quantistica e dalla struttura matematica del protocollo stesso. Sebbene l'attuale implementazione si basi su modelli teorici, il percorso verso l'applicazione pratica è più chiaro che mai, offrendo un modo per generare la casualità affidabile di cui la moderna società digitale ha disperatamente bisogno senza richiederci di fidarci della macchina.

Lo studio rappresenta una risposta definitiva a una domanda posta da ricercatori precedenti riguardo ai limiti della casualità certificata. Conferma che, sebbene la perfetta uniformità sia matematicamente irraggiungibile per un verificatore deterministico, un livello di casualità che è effettivamente indistinguibile dalla perfezione è ottenibile. I ricercatori non hanno solo migliorato il tasso di casualità; hanno ridefinito i confini di ciò che è possibile in un ambiente privo di fiducia. La loro costruzione fornisce una garanzia di sicurezza robusta e incondizionata nel modello dell'oracolo casuale quantistico, stabilendo un nuovo standard per il modo in cui intendiamo la casualità nell'era quantistica. Il risultato è un protocollo che è sia teoricamente solido che praticamente rilevante, colmando il divario tra la teoria quantistica astratta e le concrete necessità di un'infrastruttura digitale sicura.