An Operator-Norm Approach to Security with Quantum Advice

Nel mondo moderno della crittografia, la sicurezza si basa spesso sull'assunto che determinati enigmi matematici siano troppo difficili da risolvere rapidamente. Per testare ciò, i ricercatori immaginano un mondo idealizzato in cui una funzione si comporta come una macchina perfettamente casuale, rispondendo a ogni domanda con un risultato completamente imprevedibile. Questo è noto come modello dell'oracolo casuale (random oracle model). In questo panorama teorico, la forza di un sistema di sicurezza è misurata in base a quanto sforzo un attaccante deve impiegare per violarlo. Tuttavia, un attaccante astuto non parte sempre da zero. Può trascorrere mesi o anni in anticipo, utilizzando una potenza di calcolo massiccia per analizzare il sistema e memorizzare un riepilogo compresso delle proprie scoperte. Questo riepilogo è chiamato "consiglio" (advice). Quando l'attacco effettivo inizia, l'attaccante utilizza questo consiglio pre-calcolato per accelerare il processo, eludendo efficacementmente i limiti temporali che proteggono il sistema. Questo scenario è noto come sicurezza non uniforme, e rappresenta una delle minacce più realistiche alla privacy digitale.

La situazione diventa ancora più complessa quando entra in gioco l'informatica quantistica. Un computer quantistico può elaborare informazioni in un modo che gli consente di interrogare queste macchine casuali in una sovrapposizione di molti stati contemporaneamente. Se un attaccante può combinare un massiccio pre-calcolo classico con un computer quantistico per l'attacco finale, le regole della sicurezza cambiano completamente. Per anni, i ricercatori hanno faticato per calcolare esattamente quanto vantaggio fornisca questa combinazione all'attaccante. I metodi precedenti potevano fornire stime di sicurezza precise per alcuni tipi di attacchi, ma erano insufficienti per altri, in particolare quelli che coinvolgono compiti decisionali in cui l'attaccante deve scegliere tra due possibilità piuttosto che trovare un segreto specifico. Questo divario significava che le garanzie di sicurezza per importanti strumenti crittografici erano o troppo ampie per essere utili o troppo conservative per essere pratiche.

Un team di ricercatori ha ora sviluppato un nuovo approccio matematico per colmare questo divario, offrendo un modo più chiaro e preciso per misurare la sicurezza contro questi potenti attaccanti ibridi. Spostando la loro prospettiva dal conteggio delle probabilità all'analisi della "dimensione" degli operatori matematici che descrivono la strategia dell'attaccante, hanno creato un metodo unificato che funziona sia per i problemi di ricerca che per i giochi decisionali. Questa nuova tecnica permette loro di dimostrare che l'aggiunta di un semplice valore casuale, noto come "sale" (salt), a un sistema crittografico può neutralizzare efficacemente il vantaggio ottenuto dal pre-calcolo, anche quando l'attaccante ha accesso al consiglio quantistico. Il loro lavoro fornisce i primi limiti di sicurezza stretti per diversi problemi fondamentali, inclusa la sicurezza dei generatori di numeri casuali e la difficoltà di invertire le funzioni unidirezionali, mostrando esattamente quanto sale sia necessario per mantenere i sistemi sicuri.

Il cuore di questa svolta risiede nel modo in cui i ricercatori hanno scelto di guardare al problema. Invece di cercare di tracciare l'esatta percentuale di successo di un attaccante attraverso una serie di passaggi, hanno trattato l'intero attacco come un singolo oggetto matematico. Immaginate la strategia dell'attaccante come una macchina che prende un input e produce un output; i ricercatori hanno analizzato la massima "forza" possibile di questa macchina. Hanno scoperto che questa forza è direttamente limitata da quanta informazione l'attaccante potrebbe aver raccolto sul sistema casuale durante la sua fase di pre-calcolo. Collegando questo limite a un modello più semplice in cui l'attaccante è costretto a fissare determinate parti del sistema in anticipo, sono stati in grado di derivare una formula singola e coerente che si applica a tutti i tipi di attacchi. Questa visione unificata ha rivelato che i metodi precedenti avevano sottostimato il potere dell'attaccante nei giochi decisionali, portando a rivendicazioni di sicurezza eccessivamente ottimistiche.

Uno dei risultati più significativi riguarda l'uso del "salting". In crittografia, il salting consiste nell'aggiungere una stringa unica e casuale di dati a un messaggio prima che venga elaborato. Ciò assicura che, anche se due utenti hanno la stessa password, le loro versioni elaborate appariranno completamente diverse. I ricercatori hanno dimostrato che questa tecnica semplice è incredibilmente efficace contro gli attaccanti che si sono preparati in anticipo. Hanno dimostrato che, per gli attacchi basati sulle decisioni, il vantaggio guadagnato da un attaccante dal suo consiglio pre-calcolato diminuisce drasticamente all'aumentare della dimensione del sale. Nello specifico, hanno mostato che la probabilità di successo dell'attaccante è limitata da un valore che diminuisce con la radice quadrata della dimensione del sale, un risultato molto più forte di quanto precedentemente noto. Ciò significa che, scegliendo una lunghezza del sale ragionevole, i progettisti di sistemi possono garantire che anche un attaccante con un enorme computer quantistico e anni di pre-calcolo non possa violare il sistema con un successo significativo.

Il documento fornisce anche limiti precisi per sfide crittografiche specifiche e ben note. Ad esempio, hanno analizzato la sicurezza dei generatori pseudocasuali, che sono algoritmi utilizzati per creare sequenze di numeri che sembrano casuali ma che sono in realtà determinate da un seme segreto. Hanno dimostrato che la sicurezza di questi generatori è molto più forte di quanto precedentemente pensato, a patto che il sale sia sufficientemente grande. Allo stesso modo, hanno affrontato il problema della "scatola di Yao" (Yao's box), uno scenario teorico in cui un attaccante deve indovinare un bit nascosto basandosi su informazioni limitate. I loro nuovi limiti mostrano che la capacità di un attaccante di indovinare correttamente è strettamente vincolata dalla quantità di consiglio che possiede e dalla dimensione del sale. Questi risultati non sono solo miglioramenti teorici; offrono indicazioni concrete per gli ingegneri che costruiscono sistemi sicuri. I ricercatori hanno calcolato che, per raggiungere un determinato livello di sicurezza, i parametri del sistema, come la dimensione del sale e il numero di query che un attaccante può effettuare, devono seguire rapporti specifici.

Fondamentalmente, i ricercatori non si sono limitati a migliorare i numeri; hanno anche chiarito la relazione tra diversi tipi di attacchi. Hanno mostrato che la difficoltà di trovare un segreto specifico (un problema di ricerca) e la difficoltà di distinguere tra due opzioni (un problema decisionale) sono governate dagli stessi principi sottostanti quando è coinvolto il consiglio quantistico. Questa unificazione semplifica il panorama della sicurezza crittografica, permettendo una comprensione più coerente di come i computer quantistici possano minacciare gli attuali sistemi. Il loro lavoro conferma che, sebbene il consiglio quantistico sia una risorsa potente, non è invincibile. Con le contromisure corrette, come l'uso strategico del salting, la sicurezza dei sistemi digitali può essere mantenuta anche di fronte a queste minacce avanzate. Lo studio costituisce una prova rigorosa del fatto che le fondamenta matematiche della crittografia rimangono robuste, a patto che comprendiamo e teniamo conto delle piene capacità dei nostri avversari.