Homomorphic encryption: new constructions and algorithms

The main focus of this thesis is the Fully homomorphic encryption} (FHE) primitive. This is a cryptographic technique that allows one to encrypt values in such a way that a party that does not own the secret key can still perform computations over encrypted values. To have an intuition, think the following (homomorphic) property: a + b = dec(enc(a) + enc(b)), where enc(.) and dec(.) are the encryption and decryption functions, respectively. An external (untrusted) party could evaluate enc(a) + enc(b), and by returning the result back to the user, the latter will be able to see result of the computation, even though she never published neither a or b. By extending this definition to additions and multiplications, and by allowing for the evaluation of arbitrary depth circuits, we precisely obtain FHE. The range of potential use cases of this technique is enormous: from privacy-preserving machine learning to private information retrieval, although it inherently introduces some computational overhead that prevents current solutions to be deployed as real world products -- the goal of this work is to speed up this process. After an initial introduction to lattice-based cryptography, the thesis is split into two parts: constructions and algorithms. In the first part we will begin by presenting how such schemes are built, starting from existing ones, and we will propose a generalization for these techiques. In particular, all standard FHE schemes are based on the hardness of the Learning with errors (LWE) problem. This problem can be seen from multiple perspectives, and we will take the lattice one. From a certain perspective, an LWE instance can be seen as a Bounded distance decoding (BDD) problem over a specific family of lattices, called q-ary lattices. Our objective is to generalize the lattice properties requires to build an FHE scheme, enabling the use of other lattice-based trapdoors. We will show how to do so, and we will give as an example a possible FHE scheme based on the Lattice isomorphism problem, that enables to sample BDD problems over any (meaningful) family of lattices, by hiding the BDD target in a (secret) rotation of the picked lattice. In the second part we will construct algorithms that allow to efficiently compute some function f(x), given an encrypted input x. We will present different contributions, mainly in the field of privacy-preserving machine learning. These algorithms allow one to classify encrypted data in such a way that the data owner only will be able to read the result of the classification. As a potential use case think of search engines that are able to return the results of some query, without being able to see what the user asked. Unfortunately, because of the overhead introduced by FHE, we need to take a step back and work on smaller problems. In particular, we will show how to efficiently classify images from the CIFAR-10 dataset with a drastically lower memory footprint but same performance as the state of the art. Some of the main issues are about how to perform an efficient convolution with encrypted data, and how nonlinear functions can be evaluated, having only access to additions and multiplications. Additionally, given the current interest in large language models, we will give some preliminary exploration of the Transformer architecture in FHE, allowing us to classify encrypted text from the SST-2 dataset. Lastly, we will deal with sorting algorithms for encrypted data. Standard results can not be applied in our domain, since most of the sorting algorithms are data-dependent; meaning that their behavior depends on the input data. Since, in our setting, inputs are encrypted, we can only evaluate oblivious algorithms. We will show how sorting for encrypted values can be made faster, with larger precision and with smaller memory requirements than the state-of-the-art.

Il tema principale di questa tesi è la primitiva crittografica chiamata Fully Homomorphic Encryption (FHE) (in italiano, cifratura omomorfa). Si tratta di una tecnica crittografica che consente di cifrare dei valori in modo tale che un'entità esterna, priva della chiave segreta, possa comunque eseguire operazioni sui dati cifrati. Per avere un’intuizione di base, si consideri la seguente proprietà (omomorfa): a + b = dec(enc(a)) + enc(b)), dove enc(.) e dec(.) sono le funzioni di cifratura e decifratura, rispettivamente. Un soggetto esterno (non fidato) può calcolare enc(a) + enc(b) e restituire il risultato all’utente, che potrà così ottenere l’esito della computazione pur non avendo mai rivelato né a né b. Estendendo questa definizione alle operazioni di somma e moltiplicazione, e permettendo la valutazione di qualsiasi algoritmo, si ottiene il concetto di FHE. Le potenziali applicazioni di questa tecnica sono numerosissime; tuttavia, essa introduce un pesante sovraccarico computazionale che, ad oggi, limita l’utilizzo pratico di FHE nel mondo reale. Lo scopo di questo lavoro è contribuire ad accelerare il percorso verso implementazioni realmente utilizzabili. In seguito ad una parte introduttiva alla crittografia basata sui reticoli (lattice-based cryptography), la tesi è suddivisa in due parti: costruzioni e algoritmi. Nella prima parte, presenteremo le modalità con cui tali schemi vengono costruiti, partendo da quelli esistenti, e proporremo una generalizzazione di queste tecniche. In particolare, tutti gli schemi FHE standard si basano sulla difficoltà del problema chiamato Learning with errors (LWE). Questo problema può essere visualizzato da diverse prospettive; noi seguiremo quella dei reticoli (lattices). Più precisamente, un’istanza di LWE può essere vista come un problema di Bounded distance decoding (BDD) su una specifica famiglia di reticoli, chiamati q-ary lattices. Il nostro obiettivo è generalizzare le proprietà dei reticoli necessarie alla costruzione di uno schema FHE, in modo da poter utilizzare altre tipologie di trapdoor basate su reticoli. Nella seconda parte, costruiremo algoritmi in grado di calcolare in modo efficiente una funzione f(x), dato un input cifrato x. Presenteremo diversi contributi, principalmente nell’ambito del privacy-preserving machine learning. Questi algoritmi consentono di classificare dati cifrati in modo tale che solo il proprietario dei dati possa leggere il risultato della classificazione. Un possibile caso d’uso è quello di motori di ricerca in grado di restituire i risultati di una query senza conoscere il contenuto della richiesta dell’utente. A causa del sovraccarico computazionale introdotto da FHE, è prima necessario concentrarsi su problemi di scala più ridotta. In particolare, mostreremo come sia possibile classificare in modo efficiente le immagini del dataset CIFAR-10, riducendo drasticamente i requisiti in termini di memoria ma senza sacrificare le prestazioni rispetto allo stato dell’arte. Inoltre, dato il crescente interesse verso i Large language models, proporremo una prima esplorazione dell’architettura Transformer in ambito FHE, applicata alla classificazione di testi cifrati del dataset SST-2. Infine, affronteremo il tema degli algoritmi di ordinamento per dati cifrati. I risultati classici nel campo dell'informatica teorica non possono essere applicati direttamente nel nostro contesto, poiché il loro comportamento dipende dai dati in ingresso. Nel nostro caso, i dati sono cifrati e quindi possiamo valutare soltanto oblivious algorithms, cioè algoritmi indipendenti dal contenuto dei dati. Mostreremo come l’ordinamento di valori cifrati possa essere reso più efficiente, con maggiore precisione e minori requisiti di memoria rispetto alle soluzioni attuali