Lattice-based Cryptography

Abstract

Lo scopo di questa tesi è di fornire un'introduzione alla crittografia basata sui reticoli. La sicurezza della maggior parte dei crittosistemi a chiave pubblica attualmente in uso è legata a due problemi matematici difficili da risolvere a livello computazionale: il problema della fattorizzazione intera ed il problema del logaritmo discreto. Tuttavia, con l'avanzamento della ricerca sul computer quantistico e con la pubblicazione, nel 1994, dell'algoritmo di Shor, che permette di risolvere questi problemi in una quantità di tempo polinomiale, a patto di avere a disposizione un computer quantistico, è stato necessario trovare dei problemi matematici che risultino difficili da risolvere anche con l'ausilio di tale computer. Gli schemi crittografici che si basano su questi problemi computazionali formano la cosiddetta post-quantum cryptography; tra gli approcci adottati rientra la crittografia basata sui reticoli. Dopo aver introdotto il concetto di reticolo ed averne studiato le principali proprietà, tra le quali assume particolare importanza la nozione di base, analizzeremo i problemi computazionalmente difficili definiti sui reticoli, gli algoritmi che tentano di fornire delle soluzioni a questi problemi, sottolineando la loro dipendenza dalla base che si ha a disposizione, ed infine gli algoritmi che cercano di trasformare una base cattiva in una base buona, permettendo di trattare meglio il reticolo in questione. Presenteremo inoltre un'ulteriore problema computazionalmente difficile che, sebbene a prima vista possa sembrare estraneo ai reticoli, presenta in realtà profondi legami con essi, motivo per cui diversi schemi basano la loro sicurezza su questo problema. Concluderemo con la descrizione dei principali schemi crittografici basati sui reticoli, alcuni dei quali sono ritenuti sicuri anche di fronte ad un attacco ad opera di un computer quantistico e sono quindi stati selezionati per una futura standardizzazione.

The aim of this thesis is to give an introduction to lattice-based cryptography. Cryptography studies the techniques that ensure secure communication between two people in the presence of adversarial behavior. The security of most public key cryptosystems currently in use is linked to two computationally hard mathematical problems: the integer factorization problem and the discrete logarithm problem. However, due to the advancement of research on the quantum computer and due to the publication, in 1994, of Shor's algorithm, which allows to solve both the problem of integer factorization and that of the discrete logarithm in a polynomial amount of time, provided that a quantum computer is available, it was necessary to find mathematical problems that are difficult to solve even with the aid of a quantum computer. Cryptographic schemes based on these computational problems form the so-called post-quantum cryptography; lattice-based cryptography is part of it. After introducing the concept of lattice and studying its main properties, among which the notion of basis, we will analyze the main computationally hard problems based on lattices, the algorithms that try to solve these problems, underlining their dependence on the basis of the lattice, and finally the algorithms that try to transform a bad basis into a good basis. We will also present an additional computationally hard problem that may seem unrelated to lattices but actually presents deep relationships with them, hence several schemes base their security on this problem. We will conclude with the description of the main lattice-based cryptographic schemes, some of which are safe against an attack by a quantum computer and have therefore been selected for future standardization.