Crittografia nell’era Quantum
La seguente rubrica mira ad approfondire le implicazioni che i recenti sviluppi nell’ambito del calcolo quantistico (Quantum Computing) possono avere sulla Crittografia, da sempre elemento cardine nel quadro delle competenze di Telsy.
La rubrica, a cura del Gruppo di Ricerca in Crittografia di Telsy, tratta il tema principalmente da due punti di vista. La prima sezione è dedicata alla descrizione dei fondamenti del calcolo quantistico e delle implicazioni crittografiche che ne derivano mentre la successiva è focalizzata su una possibile risposta a questa minaccia, ovvero la Post-Quantum Cryptography (PQC).
Quantum Computing
Se da un lato si associa a fisica classica la scienza che affronta lo studio dei fenomeni naturali a livello macroscopico, con fisica quantistica si identifica la scienza che si occupa di comprendere i fenomeni microscopici.
Il premio Nobel per la fisica Richard Feynman è stato il primo a proporre un modello di calcolo basato su questi fenomeni microscopici dando origine al quantum computing.
Un computer quantistico è strutturalmente diverso da un computer classico.
L’elemento di maggior distinzione si identifica nella differente unità di informazione adottata da un processore quantistico: il qubit o bit quantistico.
Con l’articolo del 1996 “A fast quantum mechanical algorithm for database search”, l’informatico indiano-americano Lov K. Grover ha evidenziato le potenzialità del calcolo quantistico nell’ambito degli algoritmi di ricerca.
Tale contributo ha un impatto non trascurabile sulla crittografia oggi in uso.
Con l’articolo del 1995 “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, l’informatico statunitense Peter Shor ha descritto un algoritmo quantistico in grado di rompere lo schema RSA ed il protocollo Diffie-Hellman, fondamenta della maggior parte dei sistemi di comunicazione sicura oggi in uso.
Per comprendere le sfide legate alla realizzazione di un computer quantistico è necessario distinguere qubit fisico e qubit logico. All’interno di un processore quantistico, ciascun qubit fisico è un’entità instabile in corrispondenza con lo stato quantistico di un fenomeno microscopico.
Più qubit fisici vengono fatti interagire per stabilizzare un unico stato quantistico detto qubit logico.
Post-Quantum Cryptography
La Post-Quantum Cryptography (PQC) è una risposta classica all’avvento del calcolo quantistico.
Si occupa del design di schemi crittografici a chiave pubblica implementabili su elaboratori classici e resistenti anche ad attacchi di tipo quantistico.
La valutazione del NIST nell’ambito della crittografia Post-Quantum si è concentrata su meccanismi di scambio chiave crittografica con proprietà differenti da quelle garantite dal paradigma (pre-quantum) Diffie Hellman, detti Key Encapsulation Mechanisms (KEM).
Ciò fa sì che la transizione all’era post quantum non sia priva di ostacoli.
Gli schemi di firma digitale garantiscono all’informazione integrità, autenticità e non ripudio.
Quelli ad oggi maggiormente diffusi (EdDSA, ECDSA, RSA) sono vulnerabili agli attacchi di un computer quantistico, per questo motivo il NIST ha avviato un processo di standardizzazione di algoritmi di firma Post-Quantum.
Le funzioni one-way sono funzioni matematiche facili da calcolare ma computazionalmente difficili da invertire e rappresentano oggi la base per costruire schemi crittografici asimmetrici sicuri, da RSA e Diffie-Hellman agli algoritmi di crittografia Post-quantum.
I reticoli sono strutture matematiche sulle quali è possibile definire problemi computazionali ritenuti difficili anche per un computer quantistico e su cui si basa la sicurezza di numerosi schemi crittografici post-quantum facenti parte del processo di standardizzazione del NIST.
Il Learning With Errors è un problema algebrico che si basa sull’idea di rendere difficile un sistema di equazioni random aggiungendo ad esso del rumore. Ritenuto un problema difficile da risolvere, è oggi la base della sicurezza di alcuni degli schemi standardizzati dal NIST appartenenti alla lattice-based cryptography.
Nel contesto del processo di standardizzazione del NIST per l’individuazione e l’analisi di soluzioni di Post-Quantum Cryptography (PQC), il primo esito cruciale è rappresentato dalla selezione del meccanismo di incapsulamento chiave (KEM) CRYSTALS-Kyber.
Kyber è uno schema crittografico a chiave pubblica che consente a due parti di derivare un segreto comune con cui proteggere lo scambio di informazione.
Il primo degli schemi di firma digitale Post-Quantum selezionati dal NIST per la standardizzazione è CRYSTALS-Dilithium, basato sulla costruzione denominata “Fiat-Shamir with Aborts” introdotta nel 2009 dal matematico ucraino-statunitense Vadim Lyubashevsky.
Il secondo degli schemi di firma digitale Post-Quantum selezionati dal NIST per la standardizzazione è Falcon, basato sul framework GPV per la costruzione di firme “hash-and-sign” sui reticoli introdotto nel 2008 da Gentry, Peikert e Vaikuntanathan.
Con il termine del terzo round della competizione post-quantum e la successiva selezione degli algoritmi vincitori, il NIST aveva annunciato un quarto round al fine di differenziare le assunzioni di sicurezza degli schemi selezionati.
Tra gli schemi rimanenti, sono stati ritenuti ammissibili solo quelli relativi alla negoziazione chiave. Il NIST ha quindi ritenuto necessario avviare un nuovo processo focalizzato sulla selezione di firme digitali.
I codici nascono nel contesto delle telecomunicazioni per individuare e correggere gli errori che possono verificarsi su un canale rumoroso, e su di essi oggi possono essere costruiti problemi computazionali difficili da risolvere anche per un computer quantistico, base di alcuni dei principali schemi di crittografia post-quantum.
Il Syndrome Decoding Problem (SD) è il problema matematico che sta alla base dei crittosistemi McEliece (1978) e Niederreiter (1986) che hanno dato origine alla branca della crittografia post-quantum detta code-based cryptography.
Il più conservativo tra gli schemi di incapsulamento chiavi post quantum analizzati dal NIST è Classic McEliece, basato sullo schema di Neiderreiter (1986) definito su codici di Goppa.
Le funzioni di hash crittografiche sono coinvolte nella maggior parte dei protocolli di comunicazione attualmente utilizzati e a partire da esse è possibile costruire schemi di firma digitale post-quantum.
Lo schema XMSS è un primo esempio di firma digitale basato interamente sulle funzioni di hash crittografiche e standardizzato dal NIST.
La Few Time Signature FORS rappresenta l’ultimo tassello necessario alla costruzione della firma post-quantum hash-based stateless SPHINCS+.
I sistemi multivariati sono sistemi polinomiali difficili da risolvere e rappresentano oggi una delle basi della costruzione di firme digitali post-quantum.
Lo schema UOV (Unbalanced Oil and Vinegar) rappresenta oggi una delle proposte più solide ed efficienti per la costruzione di firme digitali multivariate.
A partire da uno schema di identificazione su sistemi multivariati è possibile costruire firme digitali multivariate post-quantum.