Negli ultimi anni il mondo accademico, industriale e governativo ha investito energie e risorse nel campo della computazione quantistica, in computer che sfruttano i fenomeni della meccanica quantistica per risolvere problemi matematici difficili o impraticabili per i computer convenzionali.
Se la produzione su larga scala di computer quantistici dovesse mai avviarsi, saranno in grado di frantumare molti dei sistemi di crittografia a chiave pubblica (o asimmetrica) attualmente in uso. Ciò comprometterebbe seriamente la riservatezza e l’integrità delle comunicazioni digitali su Internet e altrove.
In tale contesto, l’obiettivo della crittografia post-quantum (o quantum-safe) è sviluppare cifrari che siano sicuri, sia da attacchi di crittoanalisi condotti con computer quantistici, sia classici, e che possano interagire nel contempo con i protocolli e le reti di comunicazione esistenti.
Se da un lato la crittografia a chiave pubblica, a doppia chiave per la cifratura/decifratura, possa essere messa in serio pericolo dall’avvento dei computer quantistici, la crittografia simmetrica (o privata) e le funzioni di hash si basano su problemi resistenti agli algoritmi quantistici. Tra questi, la minaccia maggiore ai cifrari simmetrici è rappresentata dall’algoritmo di Grover (ideato da Lov Grover nel 1996 presso i Bell Labs1). Tale algoritmo in esecuzione su un computer quantistico consente di eseguire ricerche di un elemento all’interno di una lista non ordinata di lunghezza N, in un tempo proporzionale alla radice quadrata di N. Al contrario, su un computer classico il tempo sarebbe proporzionale a N. Ciò vuol dire che per ottenere lo stesso livello di sicurezza occorre raddoppiare la lunghezza della chiave.
Tra gli algoritmi a chiave simmetrica, l’Advanced Encryption Standard (AES), il Blowfish, il Twofish o il Serpent, con una lunghezza della chiave superiore o uguale a 256 bit e sotto opportune condizioni, potranno dimostrarsi quantum-safe.
Sul fronte della crittografia asimmetrica, invece, la prospettiva è meno rassicurante. I crittosistemi a chiave pubblica vengono utilizzati principalmente per svolgere due compiti fondamentali, lo scambio sicuro di chiavi, per il loro successivo impiego con cifrari simmetrici, e la firma digitale.
Tra i cifrari a chiave pubblica più noti ed attualmente in uso, rientrano:
- RSA, basato sul problema della fattorizzazione dei numeri interi;
- crittografia a curve ellittiche, che fonda la sua sicurezza sulla difficoltà di eseguire determinate operazioni sui punti di questa tipologia di curve;
- Diffie-Hellman, incentrato sulla difficoltà di calcolo del logaritmo discreto su alcuni gruppi ciclici.
Verso ciascuno di essi è possibile condurre agevolmente un attacco di crittoanalisi, decrittandone l’informazione senza l’uso della chiave, mediante l’algoritmo di Shor (ideato da Peter Shor nel 19942) in esecuzione su un computer quantistico. Il motivo per il quale l’algoritmo di Shor è in grado di “rompere” i sistemi crittografici a chiave pubblica è la conseguenza del fatto che essi si basano su problemi con complessità computazionale non polinomiale, risolvibili da un calcolatore quantistico in un tempo polinomiale. Nello specifico, dato un intero N l’algoritmo di Shor lo fattorizza in un tempo polinomiale in log (N), mentre su un computer classico il tempo è esponenziale in N.
Motivato da queste considerazioni, lo statunitense National Institute of Standards and Technology (NIST) ha intrapreso la selezione di algoritmi crittografici a chiave pubblica quantum-safe al termine di una call pubblica, annunciata durante la PQCrypto conference del 2016 ed avviata a dicembre dello stesso anno.
L’invito ha raccolto 82 algoritmi candidabili che attraverso processi di revisione paritaria e round di selezione ne ha ristretto il campo, per volgere al termine, presumibilmente entro il 2024, con il rilascio di uno standard.
I nuovi cifrari saranno adottati dagli Stati Uniti in analogia a precedenti iniziative per l’introduzione del Data Encryption Standard (DES) e dell’AES.
Tra le classi di algoritmi post-quantum che si stanno dimostrando le più promettenti si annoverano gli algoritmi basati sui “codici correttori d’errore” (Code-based cryptography) che, introdotti nel 1978 dall’americano Robert McEliece3 per la crittografia a chiave pubblica, non ebbero molta fortuna per via dell’eccessiva dimensione della chiave. Gli stessi, oggi contano varianti capaci di offrire dimensioni delle chiavi notevolmente ridotte e competitive. Questi algoritmi si basano sulla difficoltà di compiere ricerche all’interno di un insieme enorme non-ordinato di numeri. È stato teoricamente provato, altresì, che essi appartengono alla classe di problemi cosiddetti NP (Non-deterministic Polynomial) che potrebbero resistere alla computazione quantistica.
Una seconda classe, Multivariate Cryptography4, si basa sulla difficoltà di risolvere sistemi di equazioni algebriche quadratiche in molte variabili (NP-hardness).
Una terza classe è quella basata sul concetto algebrico di “reticolo” (Lattice-based cryptography), comprese le varianti basate sul problema del “learning with errors”, che consiste nella ricostruzione di una funzione da alcune sue imprecise valutazioni5. Tale formulazione ha consentito di definire taluni algoritmi innovativi per la crittografia asimmetrica, corredati di severe dimostrazioni di sicurezza.
L’implementazione di nuovi cifrari a chiave pubblica quantum-safe rappresenta oggi uno sforzo ineludibile. La pervasività dell’uso degli attuali algoritmi a chiave pubblica tocca la quotidianità di ciascuno, dalla navigazione sicura su Internet ai sistemi di sicurezza bancari, dalla firma digitale alle crypto-valute.
Una corsa contro il tempo per taluni, mentre per altri occorrerà ancora del tempo affinché la potenza computazionale di un computer quantistico possa raggiungere il livello necessario per rendere obsoleti gli standard attuali.
Nel frattempo, però, nel settore privato colossi quali Google e IBM conducono esperimenti volti ad acquisire la cosiddetta “supremazia quantistica”, sfidandosi reciprocamente nel conseguimento di nuovi e sempre più ambiziosi primati computazionali. Inoltre, con lo stesso scopo, in ambito internazionale, super-potenze quali Stati Uniti e Cina, nonché l’Unione Europea, stanno operando investimenti sempre maggiori per lo sviluppo di piani di ricerca nel settore del quantum computing. La Cina, ad esempio, ha recentemente reso nota l’intenzione di realizzare entro il 2020, a Hefei, un laboratorio nazionale per le scienze dell’informazione quantistica, a cui sarà assegnato un budget pluriennale pari a ben dieci miliardi di dollari6.
Nel contempo, in ambito europeo, la neo presidente della Commissione Europea, Ursula von der Leyen, si è pronunciata sul tema affermando che il quantum computing rientra tra le priorità dell’Unione e manifestando la volontà di sostenere le iniziative di sviluppo in tale ambito, rendendo anche disponibili le risorse computazionali europee al mondo accademico e della ricerca, attraverso il cloud. A tal scopo, l’Unione ha messo a disposizione un miliardo di dollari da impiegare entro i prossimi dieci anni7, per lo sviluppo di taluni progetti già individuati.
In tale contesto, la ragione che è alla base della spasmodica “corsa” degli attori statuali e privati, volta a raggiungere la citata supremazia nel campo del quantum computing, è riscontrabile nelle parole che Mike McCaul8, politico nordamericano e membro dell’American Enterprise Institute, pronunciò nel 2018 riguardo la concorrenza nel campo del quantum computing degli Stati Uniti con avversari globali quali Cina, Russia, Corea del Nord e Iran: “Ritengo che qualunque super-potenza raggiunga in anticipo sulle altre tale traguardo, si doterebbe della prima bomba nucleare digitale”.
1 Grover, “A fast quantum mechanical algorithm for database search”, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, p. 212, 1996.
2 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, pp. 124-134, 1994.
3 McEliece, “Public-Key System Based on Algebraic Coding Theory”, DSN Progress Report 44, pp. 114-116, 1978.
4 Matsumoto, Imai, “A class of asymmetric cryptosystems based onpolynomials over finite rings”, IEEE International Symposium on InformationTheory, Abstract of Papers, pp.131-132, 1983.
5 Goldreich, Goldwasser, Halevi, “Public-key cryptosystem from lattice reductions problem”, in Proc. of Crypto ’97, volume 1294 of LNCS pp. 112-131, IACR, Springer-Verlag, 1997.
6https://itbrief.com.au/story/apac-jumps-on-quantum-computing-bandwagon
7https://www.ilsole24ore.com/art/la-cina-l-occidente-e-sfida-globale-big-...
8https://fedmanager.com/news/congressman-quantum-computing-equivalent-to-...
Foto: IBM
