Algoritmi post-quantici: lattice-based

In principio ci fu la “Bomba”, la macchina calcolatrice ideata da Alan Turing in grado di decifrare i messaggi di enigma. All’epoca, enigma rappresentava il sistema crittografico più sicuro e usato dalle forze naziste per le comunicazioni militari, e garantiva un vantaggio notevole per le loro operazioni. Enigma si basa su un problema matematico che ha una complessità tale da non poter essere affrontata da un singolo individuo o da un gruppo di studiosi.

Per questo motivo Turing, analizzando il modello matematico che si pone alla base di enigma, ha progettato una macchina che implementasse al suo interno un algoritmo di risoluzione di tale problema, con l’aiuto dell’elettronica che permise di abbattere i tempi di esecuzione dell’algoritmo. Grazie a questa macchina, i crittografi alleati aumentarono la loro capacità computazionale e che gli permise di esplorare tutto lo spazio di ricerca delle soluzioni fino a trovare la risposta corretta. Questa invenzione fu una delle cause che permise agli alleati di vincere la guerra con la Germania nazista.

Algoritmi post quantici: il XXI secolo

Abbiamo un algoritmo di cifratura basato su un problema matematico non risolvibile con gli attuali strumenti in un lasso di tempo operativamente basso. L’attuale algoritmo che garantisce la sicurezza delle nostre comunicazioni è RSA (Rivest, Shamir Adleman), un sistema di cifratura asimmetrica che si basa sull’utilizzo dei numeri primi. In poche parole, Alice e bob scelgono due numeri primi diversi tra loro, questi numeri rappresentano la loro chiave privata. La chiave pubblica del sistema non è altro che il prodotto di questi due numeri.

La potenza di questo algoritmo risiede nel fatto che la fattorizzazione in numeri primi (cioè trovare le chiavi private) di un numero è attualmente un problema non risolvibile in tempo polinomiale (cioè il risultato arriva, ma non è detto che noi saremo ancora vivi per ammirarlo).

Quindi al momento non esiste una “Bomba” capace di rompere questo sistema?

Ehm, non proprio. Come posiamo leggere in diversi articoli, IBM è riuscita a creare il primo computer quantico, cioè un computer con elevate prestazioni computazionali e che metterebbero in ginocchio gli attuali sistemi di cifratura. Per questo motivo, le sfide matematiche odierne in ambito crittografico convergono sulla creazione di problemi ancora più complessi, cioè con una complessità computazionale più alta rispetto a quello dei moderni computer quantici.

Esistono diversi tipi di algoritmi post-quantici che si stanno studiando per capire se resistono o meno ad un attacco a forza bruta da parte di un computer quantico e sono spiegati perfettamente in questo articolo. Noi andremo invece ad analizzare la crittografia lattice-based che utilizza costrutti algebrici bidimensionali noti come “reticoli”, resistenti agli schemi di calcolo quantistici.

Un reticolo è una griglia infinita di punti. Il problema computazionale su cui si basa la tecnologia lattice-based è il “Shortest Vector Problem”, che richiede di individuare l’origine il punto nella griglia che si trova più vicino a un punto centrale fisso nello spazio. In SVP si cerca di trovare, data una base di un reticolo geometrico, un vettore non nullo di norma minima appartenente al reticolo; una sua approssimazione, molto utile in crittografia `e SVP γ, ovvero trovare il vettore non nullo più corto entro un’approssimazione γ. I due problemi sono entrambi ritenuti computazionalmente molto difficili.

Quali sono i vantaggi di SVP?

Come già detto, è un problema computazionalmente difficile, i migliori algoritmi post quantici per risolverlo hanno complessità di ordine esponenziale rispetto alla dimensione del reticolo. I calcoli vengono eseguiti facilmente, con un costo computazionale basso. Questo permetterebbe di eseguire operazioni di cifratura anche utilizzando dispositivi con un’esigua potenza di calcolo e di conseguenza più economici.

Inoltre bisogna ricordare che attualmente non si dispone di grandi alternative ad RSA. Queste alternative saranno effettivamente necessarie nel caso della scoperta di un algoritmo di fattorizzazione in tempo polinomiale. Un algoritmo di fattorizzazione in grado di operare in tempo polinomiale è già noto per computer quantistici; attualmente, però, non sono noti attacchi quantistici a SVP.

Infine, una proprietà molto interessante è che la difficoltà di una qualsiasi istanza del problema è la stessa del caso peggiore. Se si riuscisse a risolvere un’istanza di questo problema, saremmo in grado di risolvere tutte le istanze, ma allo stesso modo tutte le istanze hanno la stessa complessità del caso peggiore.

Articolo a cura di Jacopo Iezzi