Il calcolo quantistico ha nel mondo informatico sia appassionati sostenitori che ne prevedono un impatto devastante sulla tecnologia, sia osservatori scettici che lo considerano tutt’al più una tecnica adatta ad affrontare alcuni problemi particolari.
Anche chi sostiene la seconda opinione, però, in genere non sottovaluta l’impatto del calcolo quantistico su alcune proprietà chiave per la sicurezza informatica, ovvero l’autenticità, confidenzialità ed integrità dei dati finora garantiti dalla crittografia. In questo articolo facciamo il punto sui rischi per la sicurezza sollevati dai più recenti risultati della ricerca sui metodi quantistici.
Le basi
Consideriamo uno spazio di dati di interesse, ad esempio l’insieme Z dei numeri interi. Algebricamente si tratta di un anello, ovvero di un insieme chiuso rispetto alle operazioni di somma e moltiplicazione: sommando o moltiplicando due numeri interi si ottiene ancora un intero. In questo spazio concettuale vogliamo risolvere un problema difficile, ad esempio calcolare i fattori primi di un numero intero arbitrario. Va notato che mentre Z ha ovviamente infiniti valori, è possibile considerare lo stesso problema anche in anelli finiti. Ad esempio Zq, l’anello finito dei resti delle divisioni degli interi per un dato intero q, comprende per definizione solo q valori, cioè {0,1,..,q-1}.
La meccanica quantistica permette di preparare (o, se preferite, programmare) un sistema fisico, l’hardware quantistico, composto di entita’ elementari dette quantum bit o qubit. Nello stato sovrapposto, ciascun qubit puo’ assumere contemporaneamente tutti i valori da 0 a 1. Impostando tutti i qubit in questo modo, si porta l’hardware quantistico in uno stato che rappresenta tutte le possibili soluzioni del problema. Nell’esecuzione del programma, si fa evolvere lo stato dell’hardware quantistico fino all’equilibrio energetico e poi lo si fa ripetutamente collassare in uno stato classico (non sovrapposto), misurando ogni volta l’energia corrispondente.
La previsione quantistica
Quest’ultima misura si può interpretare come una previsione quantistica che riguarda il problema. Se la costruzione dello stato iniziale è stata fatta correttamente e l’evoluzione energetica avviene senza interferenze, la densità di probabilità dell’energia risulta più elevata attorno al valore che corrisponde alla soluzione del problema originario; basta generare abbastanza previsioni quantistiche per identificarlo.
Per capire il motivo, va considerato che secondo la fisica classica un sistema fisico può trovarsi ad un dato momento in un solo stato tra i tanti possibili. Ogni stato corrisponde deterministicamente a un unico valore di energia, dato da una funzione energia E. Per esempio, una particella puntiforme di massa m posta a un’elevazione h dal suolo ha un’energia potenziale gravitazionale di mgh, dove g è l’accelerazione di gravità.
Quando un sistema si trova in uno stato quantistico, invece, non ha un’energia determinata univocamente. Se misuriamo l’energia dell’harware quantistico, facendolo collassare dallo stato sovrapposto a uno stato classico, il valore che otteniamo è uno tra i tanti possibili e corrisponde a uno degli autovalori della matrice H che rappresenta l’energia osservabile.
Ricordiamo che una matrice quadrata nxn A = {ai,j} e’ un insieme di n vettori riga {a1, a2, .. an} ciascuno dei quali ha n componenti {ai,1, ai,2,…ai,n}. Un numero λ , reale o complesso, è detto autovalore di una matrice quadrata A se esiste un vettore v tale che valga la relazione Av=λv. Il vettore v è detto autovettore di A corrispondente all’autovalore λ.
La matrice H, detta hamiltoniana quantistica, caratterizza ogni sistema quantistico, proprio come la funzione energia E caratterizza ogni sistema classico. Quando misuriamo l’energia dell’hardware quantistico possiamo ottenere il risultato hi con probabilità λi, per ciascun autovettore hi di H con autovalore λi (supponendo che l’autovalore λi abbia molteplicità 1). All’atto della misura, il sistema collassa nello stato classico corrispondente al vettore hi. Lo stato fondamentale e l’energia dello stato fondamentale di un sistema quantistico sono rispettivamente l’autovettore minimo ho di H e il corrispondente autovalore λo
Il numero e la distribuzione dei valori di energia λi di un sistema quantistico condiziona il numero k di misurazioni necessarie per identificare con la confidenza desiderata lo stato fondamentale (e quindi la soluzione al problema). La generazione di k previsioni quantistiche richiede k volte il tempo di preparazione ed evoluzione dello stato quantistico dell’hardware, ma è enormemente piu’ rapida dell’esplorazione classica dello spazio delle alternative per cercare quella buona, che puo’ essere polinomiale nella dimensione n dello spazio, n>>k.
Universalità del calcolo quantistico
Ovviamente, portare un hardware quantistico in uno stato voluto e impostare la funzione H che rappresenta l’evoluzione della sua energia sono compiti difficili. Non c’è un modo standard per generare lo stato quantistico di partenza corripondente a un dato problema da risolvere. Anzi, non è chiaro nè ai fisici nè agli informatici teorici quale sia la classe dei problemi che ammettono una rappresentazione come hamiltoniana di un sistema quantistico reale, e quindi sono attaccabili con meodi quantistici.
In altri termini, quali classi di hamiltoniane corrispondono ad effettive evoluzioni quantistiche di sistemi presenti in natura? Se rispondiamo “tutte” sosteniamo l’universalita’ del calcolo quantistico, ovvero la sua applicabilita’ a tutte le computazioni; se rispondiamo “solo alcune” confiniamo il calcolo quantistico a una classe – peraltro ancora ignota – di problemi.
Dal punto di vista del fisico sperimentale, gli stati quantistici sono delicati e la loro preparazione è soggetta ad errori (il rumore quantistico); peggio ancora, risulta difficile eliminare il rumore a posteriori senza invalidare lo stato quantistico. Non si tratta pero’ di una impossibilita’ di principio: gia’ trent’anni fa, nel 1995, Peter Shor dimostrò che è possibile eseguire un tipo di correzione degli errori che preserva gli stati quantistici.
Metodi quantistici e crittografia: la preistoria
In sicurezza informatica, il problema dell’universalita’ o meno del calcolo quantistico non si pone: sappiamo fin dal 1994 che il calcolo quantistico è applicabile a problemi di interesse per la protezione dei dati. Il risultato di Peter Shor, pubblicato trent’anni or sono [Shor, 1994] forniva proprio il metodo per calcolare i fattori primi degli interi usando previsioni quantistiche. L’ipotesi il problema della fattorizzazione di grandi numeri interi in due fattori primi sia difficile è alla base dell’algoritmo RSA (Rivest-Shamir-Adleman), che viene utilizzato dai protocolli applicativi come SSL/TLS e https per stabilire sessioni sicure su Internet. RSA si basa sull’esistenza di due chiavi distinte, denominate “diretta” e “inversa”, che vengono usate rispettivamente per cifrare e decifrare. Nonostante le due chiavi siano fra loro dipendenti, non è possibile risalire dall’una all’altra. Ciascun utente si crea autonomamente entrambe le chiavi, e ne rende pubblica una soltanto.
Così facendo si viene a creare un elenco a disposizione di tutti gli utenti che raggruppa tutte le chiavi dirette, mentre quelle inverse sono tenute segrete da cha hi le create e per decifrare messaggi cifrati con la corrispondente chiave pubblica. Per ottenere una sicurezza elevata è necessario utilizzare chiavi binarie di almeno 2048 bit. Le chiavi a 1024 bit, ancora oggi largamente utilizzate, non sono più consigliabili. La fattorizzazione (non-quantistica) di interi grandi, infatti, è progredita rapidamente con l’utilizzo di hardware dedicati, al punto che è possibile fattorizzare un intero di 1024 bit in un tempo contenuto e a un costo sostenibile per qualunque grande organizzazione o agenzia. Il tempo necessario per fattorizzare il prodotto di due numeri primi sufficientemente grandi è invece al di là delle capacità della maggior parte degli aggressori.
La ricottura quantistica
Le ridotte dimensioni dell’hardware quantistico disponibile hanno confinato per anni l’algoritmo di Shor nell’ambito delle curiosita’. Il primo numero intero fattorizzato in modo nativo su hardware quantistico con il metodo di Shor fu 21 = 7 × 3, che è stato fattorizzato nel 2012. Nell’aprile 2012, Xinhua Peng ha calcolato quantisticamente la fattorizzazione di 143 = 13 × 11, che corrisponde a una chiave di 8 bit. In seguito, pero’, la fattorizzazione degli interi con computer quantistici è stata e ibridata con tecniche di minimizzazione (la cosiddetta “ricottura quantistica” o “quantum annealing”) per ridurre il numero di qubit richiesti.
La ricottura è un metodo generale per trovare il minimo globale di una data funzione su un insieme di soluzioni candidate. Nei processori che la usano, l’hardware quantistico viene pretrattato per portarlo in uno stato di minima energia assoluta, in modo da richiedere pochi qubit anche per risolvere grandi istanze del problema. Nell’Aprile 2016 è stato fattorizzato con questa tecnica un numero intero di 18 bit (200.099) utilizzando un processore quantistico con ricottura D-Wave 2X. Qualche anno fa (nel 2021) è stato pubblicato un articolo che descrive la fattorizzazione con metodo ibrido dell’intero 1.099.551.473.989, che richiede 41 bit.
Poor man’s quantum resistance
È interessante notare che la crittografia simmetrica, che è basata sull’idea di un’unica chiave per definire una funzione di trasformazione invertibile usata sia per crittare che per decrittare, non è così vulnerabile alle tecniche quantistiche. Come abbiamo visto, i computer quantistici sono computazionalmente più potenti dei computer tradizionali solo per quei problemi che sappiamo tradurre in uno stato quantistico e nella sua evoluzione per generare le previsioni, e nessuno ha ancora sviluppato un metodo di previsione quantistica che funzioni contro la crittografia simmetrica. Vari centri di ricerca, compreso quello della Khalifa University [Edlebi, 2022] hanno proposto uso della crittografia simmetrica anche per le funzioni oggi svolte da quella asimmetrica come l’autenticazione, una tecnica che è a volte chiamata ‘quantum-resistenza dei poveri’.
Transizione all’approccio post-quantistico
Il lento ma continuo progresso delle tecniche di attacco quantistiche ha portato l’industria a cercare sostituti per gli attuali metodi di crittografia asimmetrica. Lo sforzo per mettere al sicuro la crittografia asimmetrica dagli attacchi quantistici è statio immane, con la partecipazione dei migliori scienziati a livello mondiale. L’ente di standardizzazione statunitense, il NIST, ha iniziato ad accettare proposte di standard di crittografia post-quantistica dal pubblico nel 2016, un processo che aveva già utilizzato in precedenza per lo standard di crittografia simmetrica AES e per lo standard di hashing SHA-3.
NIST ha identificato quattro algoritmi candidati per la standardizzazione nel 2022 e ha sviluppato tre bozze di Federal Information Processing Standards (FIPS) nel 2023. Dopo la revisione delle bozze FIPS basata sul feedback dei commenti pubblici, che si è conclusa a novembre dell’anno scorso. Il NIST ha poi condotto una revisione finale e un processo di approvazione per gli standard. La loro adozione richiedera’ modifiche fisiche a dispositivi come laptop, telefoni e qualsiasi altro dispositivo elettronico che debba comunicare in modo sicuro con altri dispositivi. Si tratta ovviamente di un cambiamento graduale: i primi computer quantistici saranno probabilmente affiliati ai governi e non disponibili agli hacker, e prenderanno di mira i segreti governativi, non le e-mail delle persone normali.
Trovare problemi che sono difficili anche per il calcolo quantistico
Come abbiamo visto il passo concettuale piu’ importante per diminuire il rischio di attacco quantistico a un sistema di crittografia è basarlo su un problema difficile per cui non è noto alcun metodo quantistico di calcolo. L’apprendimento con errori (LWE) è un problema matematico considerato adatto per creare algoritmi di crittografia quantum-resistenti. Si basa sull’idea di rappresentare la chiave attraverso un insieme di equazioni con errori. In altre parole, LWE è un modo per nascondere il valore di un segreto introducendovi del rumore. In termini più tecnici, si riferisce al problema computazionale di dedurre una funzione lineare su un anello finito da un insieme di campioni alcuni dei quali possono essere errati.
Più precisamente, il problema LWE è definito come segue. Detto Zq l’anello finito degli interi modulo q e Zqn l’insieme di vettori di lunghezza n in Zq bisogna calcolare una funzione lineare sconosciuta f da Zqn a Zq sulla base di un campione di coppie {x,y}, dove {x} appartiene a Zqn, y a Zq e con una certa probabilità (ma non sempre) vale y=f(x). Ilproblema richiede di trovare la funzione f, o una sua stretta approssimazione, con alta probabilità. LWE è stato introdotto nel 2005 da Oded Regev, che ha poi vinto il Premio Gödel 2018 per questo lavoro. Regev ha dimostrato che il problema LWE è difficile da risolvere quanto il problema di determinare il vettore piu’ corto in un reticolo arbitrario (Gap Shortest Vector Problem o GapSVP) sia nel caso peggiore sia nel caso medio [Regev, 2009].
Fondamenti di crittografia reticolare
In matematica, un reticolo è un insieme parzialmente ordinato di vettori in cui ogni coppia di elementi ammette sia un estremo inferiore (inf) che un estremo superiore (sup) appartenente al reticolo. Il reticolo piu’ noto ai non matematici è probabilmente quello Booleano, composto dai sottoinsiemi di un insieme dato (ad esempio, {abc}, {ab}. {ac}, {bc}, {a}, {b}, {c} e l’insieme vuoto ∅), in cui l’inf di due sottoinsiemi si ottiene per intersezione e il sup per unione [Damiani et al., 1994]. Vi sono pero’ anche reticoli composti da numeri interi: per esempio, l’insieme D = {1, 2, 3, 4, 6, 8, 12, 24} dei divisori di 24, con l’ordinamento a ≤ b se a | b (a divide b), è un reticolo i cui elementi sono scalari, ovvero monodimensionali.
Per capire la corrispondenza tra LWE e alcuni problemi reticolari notoriamente difficili, consideriamo lo Shortest Vector Problem o SVP: trovare il vettore piu’ corto di un reticolo arbitrario (dove la lunghezza del vettore è la sua norma euclidea). A parte l’enumerazione, che richiederebbe di elencare tutti i vettori del reticolo e paragonarne la lunghezza, sono stati studiati diversi approcci, che possono essere suddivisi in due classi di complessita’: gli algoritmi che richiedono tempo super-esponenziale e memoria polinomiale nella dimensione n del reticolo, e algoritmi che richiedono sia tempo che spazio esponenziale. La prima classe di algoritmi cerca di trovare una tecnica di ricerca piu’ efficace del campionamento casuale. Ad esempio, in un campionamento gaussiano si assume che la maggioranza dei vettori del reticoo abbia una lunghezza vicino a quella media, e solo pochi vettori abbiano lunghezza minima. La seconda classe di algoritmi si basa sul setacciamento reticolare, eliminando ad ogni passo un vettore che non è il minimo e tutti quelli piu’ lunghi di lui.
Una versione approssimata del problema SVP è trovare i vettori di un reticolo la cui lunghezza rimane entro un valore γ da quella del vettore minimo. Gli approcci più noti si basano sulla riduzione della base reticolare, ovvero sul passaggio a un sotto-reticolo piu’ piccolo dove risolvere il problema con la garanzia che la soluzione trovata sara’ entro γ da quella esatta. Per grandi valori du γ, l’algoritmo Lenstra–Lenstra–Lovász (LLL) [Smeets et al., 2010] può trovare una soluzione in un tempo polinomiale nella dimensione reticolare.
GapSVP-β
Il problema GapSVP-β consiste nel distinguere tra le istanze di SVP in cui la lunghezza del vettore più corto è al massimo 1 oppure è maggiore di un valore β, dove β può essere una funzione della dimensione n del reticolo . Data una base per il reticolo, l’algoritmo deve decidere se la lunghezza λ del vettore piu’ corto in quel reticolo è λ ≤1 o λ>β. La riduzione di Regev considera al variare di q il reticolo Zqn e riduce LWE al problema di calcolare la funzione f da Zxn a {1, β } sulla base di un campione di coppie {Zxn,y}, dove y è 1 oppure β e (non sempre, ma con una certa probabilità), vale f(Zxn) = y.
Il caso
Qualche tempo fa, è comparso un articolo a firma di Yilei Chen, un ricercatore cinese della Tsinghua University, che presenta un metodo quantistico per risolvere alcuni problemi difficili legati ai reticoli in tempo polinomiale. Non è la prima volta che qualcuno affaccia il dubbio di uno schricchiolio dell’impianto della crittografia reticolare: si sono già sentiti annunci di algoritmi quantistici per problemi reticolari, che si sono rivelati non corretti o corretti solo per semplici casi speciali [Suo et al., 2020].
L’idea alla base del tentativo di Yilei Chen di trovare un metodo quantistico per risolvere LWE consiste nell’uso di distribuzioni gaussiane complesse per rappresentare la distribuzione degli scostamenti dei campioni (x,y) dalla funzione lineare ignota che il problema LWE richiede di determinare. Nella teoria della probabilità, le variabili casuali complesse sono numeri complessi casuali le cui parti reale e immaginaria sono congiuntamente normali, cioè la cui norma ha una distribuzione gaussiana. L’idea di utilizzarle per rappresentare la statistica dei problemi LWE non è balzana: la letteratura su LWE ha investigato da tempo la nozione di variabili casuali subgaussiane (introdotta nel 2012 da Miccancio e Peikert) ovvero distribuzioni che, pur non essendo gaussiane esse stesse, sono legate ad una gaussiana di riferimento [Murphy e Player, 2019]. Nell’articolo di Yilei Chen, l’istanza di un problema LWE viene rappresentata come un campionamento gaussiano sulla parte puramente immaginaria di una distribuzione complessa, che serve a inizializzare lo stato di un sistema quantistico.
Il calcolo quantistico consiste nel partire da questi stati immaginari e far ripetutamente evolvere il sistema per ottenere hamiltoniane dal cui rilevamento si possano ricavare equazioni di vincolo sul segreto LWE e sui termini di errore. Se funzionasse, questo approccio potrebbe fornire un algoritmo quantistico per la risoluzione di LWE. Pochi giorni dopo la comparsa dell’artcolo di Yilei Chen, due revisori volontari, Hongxun Wu e (indipendentemente) Thomas Vidick hanno scoperto che l’articolo conteneva un errore significativo in un cruciale passaggio dagli stati del sistema quantistico ai coefficienti delle equazioni di vincolo sul segreto. L’errore conclamato pottebbe essere definito un “errore di cottura”, perche’ riguarda il passo di riduzione dal numero dei campioni del problema LWE a quello degli stati del sistema quantistico, fondamentale per tenere gestibile il numero dei qubit necessari.
Conclusioni
Dalle considerazioni svolte fin qui si capisce come affidarsi per garantire la confidenzialità dei dati a un problema difficile per cui non è ancora noto un attacco quantistico, ma per cui sono comunque noti risultati preliminari, possa nascondere dei rischi. Se fosse stato confermato, il risultato di Ylei Chen avrebbe creato un grosso problema per gli algoritmi crittografici post-quantistici che loro basano la loro sicurezza su problemi come LWE. Soprattutto, un solo ricercatore cinese avrebbe messo in pericolo in un colpo solo lo sforzo immane fatto dalla comunita’ scientifica (e dall’Occidente in particolare) per basare su problemi reticolari i nuovi standard di crittografia asimmetrica da usare su Internet.
Bibliografia
[Shor, 1994] Peter Shor, Algorithms for quantum computation: Discrete log and factoring, in Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, Santa Fe, IEEE Computer Society Press, Nov. 1994, pp. 124-134.
[Edlebi et al., 2022] Khouloud Eledleb, Chan Yeob Yeun, Ernesto Damiani, Yousof Al-Hammadi Empirical Studies of TESLA Protocol: Properties, Implementations, and Replacement of Public Cryptography Using Biometric Authentication January 2022 IEEE Access 10(7):1-1 DOI: 10.1109/ACCESS.2022.3152895 LicenseCC BY 4.0
[Regev, 2009] Regev, Oded. “On lattices, learning with errors, random linear codes, and cryptography.” Journal of the ACM (JACM) 56.6 (2009): 1-40.
[Damiani et al., 1994] Damiani, Ernesto, Ottavio D’Antona, and Francesco Regonati. “Whitney numbers of some geometric lattices.” Journal of Combinatorial Theory Series A 65.1 (1994): 11-25.
[Smeets et al., 2010] Smeets, I., Lenstra, A., Lenstra, H., Lovász, L., & van Emde Boas, P. (2010) “The history of the LLL-algorithm”. The LLL Algorithm: Survey and Applications, 1-17.
[Chen, 2024] Yilei Chen “Quantum Algorithms for Lattice Problems”, Tsinghua University, Shanghai Artificial Intelligence Laboratory, Shanghai Qi Zhi Institute
[Suo et al., 2020] Suo, J., Wang, L., Yang, S., Zheng, W., & Zhang, J. (2020). Quantum algorithms for typical hard problems: a perspective of cryptanalysis. Quantum Information Processing, 19, 1-26.
[Murphy and Player, 2019] Murphy, Sean, and Rachel Player. “Delta-subgaussian random variables in cryptography.” Australasian Conference on Information Security and Privacy. Cham: Springer International Publishing, 2019.
