 |
| IBM Q System One, prototipo di computer quantistico |
di Mario Raso
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
Labs
[1]). 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 1994
[2]) 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 McEliece [3] 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
Cryptography
[4], 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 valutazioni [5]. 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 dollari [6].
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 anni [7], 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 McCaul [8], 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”.
Bibliografia
e sitografia:
- Grover, “A fast quantum mechanical algorithm for database search”, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, p. 212, 1996.
- 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.
- McEliece, “Public-Key System Based on Algebraic Coding Theory”, DSN Progress Report 44, pp. 114-116, 1978.
- Matsumoto, Imai, “A class of asymmetric cryptosystems based onpolynomials over finite rings”, IEEE International Symposium on InformationTheory, Abstract of Papers, pp.131-132, 1983.
- 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.
Nessun commento:
Posta un commento