Keywords: lattice based cryptography, fully homomorphic encryption, cloud computing, machine learning, circuit privacy, private information retrieval

Fully homomorphic encryption enables computation on encrypted data without leaking any information about the underlying data. In short, a party can encrypt some input data, while another party, that does not have access to the decryption key, can blindly perform some computation on this encrypted input. The final result is also encrypted, and it can be recovered only by the party that possesses the secret key.

In this thesis, we present new techniques/designs for FHE that are motivated by applications to machine learning, with a particular attention to the problem of homomorphic inference, i.e., the evaluation of already trained cognitive models on encrypted data.

First, we propose a novel FHE scheme that is tailored to evaluating neural networks on encrypted inputs. Our scheme achieves complexity that is essentially independent of the number of layers in the network, whereas the efficiency of previously proposed schemes strongly depends on the topology of the network.

Second, we present a new technique for achieving circuit privacy for FHE. This allows us to hide the computation that is performed on the encrypted data, as is necessary to protect proprietary machine learning algorithms. Our mechanism incurs very small computational overhead while keeping the same security parameters.

Together, these results strengthen the foundations of efficient FHE for machine learning, and pave the way towards practical privacy-preserving deep learning.

Finally, we present and implement a protocol based on homomorphic encryption for the problem of private information retrieval, i.e., the scenario where a party wants to query a database held by another party without revealing the query itself.

v -

Résumé

Le chiffrement totalement homomorphe permet d'effectuer des calculs sur des données chiffrées sans fuite d'information sur celles-ci. Pour résumer, un utilisateur peut chiffrer des données, tandis qu'un serveur, qui n'a pas accès à la clé de déchiffrement, peut appliquer à l'aveugle un algorithme sur ces entrées. Le résultat final est lui aussi chiffré, et il ne peut être lu que par l'utilisateur qui possède la clé secrète.

Dans cette thèse, nous présentons des nouvelles techniques et constructions pour le chiffrement totalement homomorphe qui sont motivées par des applications en apprentissage automatique, en portant une attention particulière au problème de l'inférence homomorphe, c'est-à-dire l'évaluation de modèles cognitifs déjà entrainé sur des données chiffrées.

Premièrement, nous proposons un nouveau schéma de chiffrement totalement homomorphe adapté à l'évaluation de réseaux de neurones artificiels sur des données chiffrées. Notre schéma atteint une complexité qui est essentiellement indépendante du nombre de couches dans le réseau, alors que l'efficacité des schéma proposés précédemment dépend fortement de la topologie du réseau.

Ensuite, nous présentons une nouvelle technique pour préserver la confidentialité du circuit pour le chiffrement totalement homomorphe. Ceci permet de cacher l'algorithme qui a été exécuté sur les données chiffrées, comme nécessaire pour protéger les modèles propriétaires d'apprentissage automatique. Notre mécanisme rajoute un coût supplémentaire très faible pour un niveau de sécurité égal. Ensemble, ces résultats renforcent les fondations du chiffrement totalement homomorphe efficace pour l'apprentissage automatique, et représentent un pas en avant vers l'apprentissage profond pratique préservant la confidentialité.

Enfin, nous présentons et implémentons un protocole basé sur le chiffrement totalement homomorphe pour le problème de recherche d'information confidentielle, c'est-à-dire un scénario où un utilisateur envoie une requête à une base de donnée tenue par un serveur sans révéler cette requête.

First of all, I would like to thank Michel Abdalla and Hoeteck Wee. Not only did they supervise this thesis and help me with research topics, but they also provided guidance and help throughout these years, and I greatly appreciate them as researchers and as persons. They form a fantastic pair of supervisors and I feel privileged for having the chance of working with them. In particular, I would like to thank Michel for recruiting me and for all the help he gave me when I moved to Paris, for giving always careful and measured suggestions, and for patiently guiding me towards this goal. And I want to thank Hoeteck for his volcanic enthusiasm, his astonishing dedication, and his relentless strive for perfection, for always pushing me during this thesis, and for asking a lot, but never too much.

A sincere acknowledgment to Jean-Sébastien Coron and Pierre-Alain Fouque for accepting to review this thesis. I am aware that it involves a lot of work, and I am grateful for their availability.

I would also like to thank Vadim Lyubashevsky, María Naya-Plasencia, and Pascal Paillier for accepting to be on my Ph.D. committee: having them in my jury is undoubtedly a privilege.

I want to thank David Pointcheval and all the members of the ENS Crypto team, for the interesting and insightful discussions about cryptography, research, and science in general, for the passionate discussions on how not to cook pasta (in the microwave, because that is morally wrong), and on how not to have pizza (with pineapple. No pineapple on the pizza. Ever.), but most of all for creating a wonderful and friendly environment, where I have always felt welcome and part of an amazing group. Being part of such a team, full of brilliant scientists, has been a true privilege for me and a way to constantly learn and improve myself. A very particular acknowledgment to Florian and Rafaël for enriching my French vocabulary... Too bad that most of the expressions you taught me cannot be repeated in public! :) I would like to sincerely thank all my coauthors: Florian Bourse, Rafaël Del Pino, Louis Goubin, Matthias Minihold, Anca Nitulescu, Michele Orrù, Pascal Paillier, and Hoeteck Wee. I learned a lot from all of you and I feel lucky for the chance of working together with you.

I am deeply thankful to Pascal Paillier, Louis Goubin, and all the guys at CryptoExperts for welcoming me during my internship and giving me the possibility to work on interesting and challenging research topics. I spent a lot of time with Pascal and I consider it a great privilege: he is a truly brilliant guy, and I have always been impressed by his excitement and his dedication to his projects, by the number of things he is able to manage in parallel, by his endless curiosity, and by the fact that he always finds time to discuss and work together, -ixx Acknowledgments despite being always tremendously busy. It is something that I have never taken for granted and that I am very grateful for.

I want to thank all the administrative staff of the DI and all the members of the SPI, for providing help with day-to-day problems, organization, and for making my experience easy and always enjoyable.

Over the course of these years, I have attended numerous "lattice and crypto meetings", often organized by ENS Lyon, and I want to thank Fabien Laguillaumie, Benoît Libert, Damien Stehlé, and all the crypto team there for always warm welcomes, insightful discussions, and tasty beers.

During my Ph.D., I have been lucky to be a fellow of the ECRYPT-NET project. It provided excellent conditions to carry out my research activities and gave me the opportunity to attend several interesting events about diverse aspects of cryptography and research. I would like to thank Saartje and all the administrative people who coordinated this project and made everything possible. Also, I would like to thank my "fellow fellows" scattered across Europe for the time we spent together. I am sincerely thankful to all my friends in Italy, with whom I managed to keep in contact despite the geographical distance. More in general, I would like to humbly thank all those who loved me and helped me along the way. Some of them have contributed by teaching me notions and helping with my studies and my culture. Some others have helped me grow and become an adult, which can be far more important. I owe them a lot, and to all of them goes my deepest gratitude. I simply cannot find the words to thank my family the way I should. My mother Marta and my grandmother Bianca have been a constant source of inspiration for me. They have always been there, through good and bad times, and I am absolutely sure I would have achieved nothing without them and the wonderful family they gave me. They made sacrifices for me, encouraged me to pursue my goals, helped me when I needed it, and stayed close to me even when my behavior or my temperament did not make it particularly easy. And even though my grandmother left us several years ago, I have always felt her presence, her support and her guidance, and I hope she is looking down at me with pride. Also, a heartfelt thank you to my uncle Beppe and my aunt Betti, for always being there in their discrete-but-present way.

Cryptography is usually perceived as a tool of war, involved in military operations or intelligence activities. From a long time ago, when it was used by Roman generals to securely send orders to the legions on the field, to the Second World War, with the Nazis using the famous Enigma machine to keep the Allied from understanding the content of their communications, to our days, when it is used to protect military secrets from being intercepted by spies or enemy states, or to communicate with James-Bond-like characters deployed on the field. Although this romantic aura surrounding cryptography has many elements of truth, this is far from being the entire picture. Cryptography is also used by common people, to carry out daily tasks that require some attention to concepts like privacy, integrity, and reliability. For example, almost everybody sends text messages or pictures from their phones. Despite the fact that cryptography is often used transparently in these cases (i.e., the users do not realize messages are encrypted/decrypted), nowadays it is normally the case that content travels through the internet in an encrypted version, so that a potential eavesdropper would gain no information from intercepting the message. Although some people would argue that this is paranoid, since their messages are not sensitive at all and they have nothing to hide1 , this is clearly not the case when it comes to sensitive applications like home banking. Even in this case, cryptography allows people to carry out daily life operations without the risk of information being stolen or falling in the hands of malicious criminals. Finally, cryptography is a tool that, in many cases, literally saves lives: it is used by whistle-blowers or activists to conceal their communications from repressive governments or organizations, thus protecting their physical safety.

More in general, the traditional goal of cryptography is to allow two parties to communicate over an insecure channel, in a way that preserves the confidentiality of the communication, and prevents anyone else from eavesdropping on the messages that are being exchanged. Historically, we usually refer to these parties as Alice and Bob, while the third party, referred to as the adversary, is usually called Eve.

What Alice and Bob would use is an encryption scheme, which intuitively is a protocol designed to allow for this protected communication, and consists of two procedures called encryption and decryption. Assuming Alice wants to send a message to Bob, she first applies the encryption procedure to the message, then sends the result to Bob who will apply the decryption procedure and recover the original message. This means that what passes through the insecure channel (and is thus potentially known to the adversary) is only the encryption of the message, called ciphertext. We are then in a situation where both Bob and the adversary know the ciphertext, so it must be the case that Bob knows something that the adversary does not, otherwise the adversary could simply proceed in the same way as Bob and recover the message. This extra piece of information is called the secret key. We can then assume that encryption and decryption are public procedures, and that the secret key is fed to them along with the message (for the encryption procedure) or the ciphertext (for the decryption), in order to obtain the expected result. We also assume that this secret key is shared between Alice and Bob. This corresponds to the case of private-key encryption, also referred to as symmetric encryption.

At this point, the reasonable question to ask is about the security of this encryption scheme: what does the adversary learn from seeing the ciphertext going through the com-munication channel? Ideally, we would like to answer "nothing", meaning that the ciphertext contains absolutely no information on the message. This notion is called information theoretic or perfect security, and can be achieved by a trivial scheme, known as one-time pad.

We now give an intuitive toy example of this scheme. Let us consider the case where Alice wants to send the message "iloveyou" to Bob, and let us assume that they had previously agree upon the secret key "4,7,2,9,5,8,7,1". They can then proceed as follows: for each character of the original message, they "shift" it by a number of spots which is given by the corresponding entry in the secret key (wrapping around when necessary, i.e., X → Y → Z → A → . . . ). Alice then does the following: Encryption: i l o v e y o u + + + + + + + + 4 7 2 9 5 8 7 1 m s q e j g v v

The message that is sent is then "msqejgvv". Upon receiving it, Bob performs the inverse operation: Decryption: m s q e j g v v --------4 7 2 9 5 8 7 1 i l o v e y o u This way of encrypting and decrypting things is perfectly secure, meaning that a party that does not have the secret key learns no information about the message (apart from its length). In fact, let us say that the adversary sees the ciphertext "msqejgvv". This could also correspond to the message "ihateyou" (under the key "4,11,16,11,5,8,7,1"), or "ihavenot" (under the key "4,11,16,9,5,19,7,2"), or "abcdefgh" (under the key "12,17,14,1,5,1,15,14"). In a nutshell, this ciphertext could represent any 8-character message, and is thus completely hiding what Alice wanted to communicate to Bob.

One could then think that this is everything we need from cryptography: we have a way to achieve perfect security, and this is sufficient. However, this is far from being the case. In fact, it is easy to see that in the previous example, the key had to be at least as long as the message it was intended to hide. Also these keys cannot be used more than once 2 , otherwise some dangerous attacks arise, that can compromise the security of the scheme. This means that Alice and Bob must be able to share a huge amount of secret bits, which quickly becomes impractical, or are limited to communicating short messages. Also, they have to agree on the secret key before communicating, either by meeting in person or in another way: this only adds to the impracticality of this system.

With the breakthrough discoveries of key exchange in 1976 by Diffie and Hellman [START_REF] Diffie | New Directions in Cryptography[END_REF], public-key encryption (also known as asymmetric encryption), and digital signatures in 1978 by Rivest, Shamir and Adleman [START_REF] Rivest | A Method for Obtaining Digital Signature and Public-Key Cryptosystems[END_REF], the scope of cryptology broadened considerably. In public-key cryptography, each party has a pair of keys: a public one and a private (or secret) one. The public one can be published, e.g., on the Internet, and allows anyone to encrypt a message, that can only be decrypted with the corresponding private key. In order to explain this concept, a famous analogy is often used: the public key corresponds to an open lock, whereas the private key corresponds to the lock's key. Publishing the public key is equivalent to making the open lock available; then anyone can write a message, put it in a box, and close the box with the provided lock. The sealed box is then sent to the recipient, who can open it with the appropriate key.

Computation outsourcing

A moment's thought reveals that there is a fundamental limit in the concept of encryption as it was presented. In fact, once something is encrypted, it can only be stored in order to be kept safe and retrieved at a later time, or it can be sent to someone who has the possibility (i.e., a suitable secret) to decrypt it and recover it. This means that the encrypted version of the data is completely useless to any party that does not hold the secret piece of information to decrypt it. On the bright side, this means that no unauthorized party can access the encrypted information; on the not-so-bright side, it also means that no party can perform operations on the encrypted data. The reason why we would like such a thing to be possible lies in the concept of computation outsourcing, i.e., when a party receives some input data

x, performs some computation on it, and returns the result.

Nowadays, everybody owns or produces enormous quantities of data, whether it be pictures, documents, bills, records, etc., and a big part of the users' activities are concentrated on small devices, with limited storage and limited computational capacities. This is one of the reasons why Cloud computing has gained a lot of momentum over the last years and is becoming a key paradigm in the way we interact with our data. In a nutshell, the model encompasses a user with limited capabilities and a powerful remote server (the Cloud), that has massive storage devices and powerful computing resources as its disposal. The idea is that the user uploads its data to the Cloud and then asks the Cloud to perform some task and return the result.

The issue with this model is clearly data privacy. In fact, the remote server is usually untrusted, meaning that it is run by a party that we do not know or control in any way, and whose honesty we cannot trust. The problem becomes even more evident if the date we are talking about consists of highly private and sensitive information like medical records, bank statements, personal communications, etc. This situation introduces a conflict: we can either take advantage of the Cloud computing paradigm, but we have to allow the Cloud to know our personal information, or we have to give up the potential of Cloud computing and perform all the computations locally, on trusted machines. For years, researchers have been trying to devise a way to reconcile the desire for data privacy and that for computation outsourcing, in order to obtain privacy-preserving computation outsourcing.

Homomorphic encryption

This part is a very general overview on the topic. These concepts are expanded, together with a more technical presentation, in Chapter 3.

A homomorphic encryption scheme is an encryption scheme that admits some kind of computations on encrypted data. In particular, given an input x encrypted as Enc (x), it should be possible to publicly compute Enc (f (x)) for a function f taken from some class of functions. The key point here is "publicly", meaning that carrying out this computation has to be possible without having access to any secret information. For a first trivial example, consider the following scenario: let us say that an encryption schemes consists of taking a message and adding a secret number S to it. Then an encryption of m 1 will be c 1 = m 1 + S, while an encryption of m 2 will be c 2 = m 2 + S. Then, any party that receives these two encryptions, can sum them together and obtain c = m 1 + m 2 + 2S, without knowing either m 1 , m 2 , or S. A party that knows S and receives the result c can simply subtract 2S (or take the result modulo S, if some other conditions hold) and recover m 1 + m 2 . The final result is that the operation of adding two numbers has been delegated to another party, without this party knowing the operands or the result.

The "scheme" used in this toy example is obviously insecure, but it turns out that many widely-used encryption schemes already have some homomorphic properties. For example, let us consider the famous RSA cryptosystem [START_REF] Rivest | A Method for Obtaining Digital Signature and Public-Key Cryptosystems[END_REF], in which an encryption of a message m is m e mod N , where e is a public exponent and N is a public modulus. It is easy to see that, given two ciphertexts c 1 = m e 1 mod N and c 2 = m e 2 mod N that encrypt messages m 1 and m 2 , we can multiply them together and obtain c = (m 1 m 2 ) e mod N , which is an encryption of m 1 m 2 . This means that we can homomorphically multiply the messages, meaning that we can take two ciphertexts, perform only public operations on them, and obtain an encryption of the product of whatever was encrypted in the ciphertexts, without knowing any message or any secret key. For this reason we say that the RSA cryptosystem is multiplicatively homomorphic. Another example is the well known El Gamal encryption scheme [START_REF] Elgamal | A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms[END_REF], which is also multiplicatively homomorphic. Notice that, for these schemes, we do not know how to perform an homomorphic addition, which amounts to computing a ciphertext that decrypts to the sum of the two original plaintexts.

Instead let us consider the famous Paillier cryptosystem [START_REF] Paillier | Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[END_REF], based on the decisional composite residuosity assumption. In this scheme, an encryption of a message m is of the form c = g m • r n mod n 2 , where g and n are public and r is random. In this case, a party that is given two ciphertexts c 1 , c 2 encrypting messages m 1 , m 2 , can compute c = c 1 • c 2 = g m 1 +m 2 • (r 1 r 2 ) n mod n 2 , which is a Paillier encryption of m 1 + m 2 . This means that we can homomorphically sum two ciphertexts and produce an encryption of the two original messages, without knowing them or any secret piece of information. We then say that the Paillier cryptosystem is additively homomorphic. Notice, however, that in this case we do not know how to homomorphically multiply two ciphertexts.

We call partially homomorphic encryption schemes those schemes that support either addition or multiplication, but not both. Schemes that are both additively and multiplicatively homomorphic are harder to come by. An example of such scheme is the DGHV encryption scheme [START_REF] Van Dijk | Fully Homomorphic Encryption over the Integers[END_REF], which will be described in details later in the manuscript (cf. Chapter 6). In most of these encryption schemes, a "noise" term is added during the encryption for security purposes. This noise (sometimes called "error") grows when performing homomorphic additions and multiplications, and must remain below a certain threshold in order for the ciphertext to be correctly decryptable. In the majority of the homomorphic schemes known so far, the way noise grows with multiplication is more severe than in the case of addition. For this reason, the most important metric when quantifying the hardness of homomorphically evaluating a circuit is its multiplicative depth.

Another important definition is that of somewhat homomorphic encryption (SHE) schemes. We use this term to refer to encryption schemes that can evaluate a certain number of operations on encrypted inputs, but for which proceeding further would result in losing decryption correctness, meaning that the result will not decrypt to what is expected. Every encryption scheme is instantiated with some parameters, e.g., the size of the primes which are used, the size of the secret key, etc. We say that a homomorphic encryption scheme is leveled if, for any multiplicative depth L fixed a priori, it is possible to find a set of parameters such that the encryption scheme instantiated with those parameters is able to homomorphically evaluate any circuit of depth L. It is easy to see that this is a stronger notion than that of somewhat homomorphic encryption scheme.

However, the main obstacle that researchers faced for more than 30 years (since the suggestion of [START_REF] Rivest | On Data Banks and Privacy Homomorphisms[END_REF]) was the following: in any case, the number of operations that can be evaluated is bounded. At some point, the noise level will become too large and it will be impossible to proceed without losing correctness. The goal of constructing a fully homomorphic encryption (FHE) scheme, i.e., a scheme that can homomorphically evaluate an unbounded number of operations, remained a dream for a long time, and some famous researchers claimed it was never going to be reached. The turning point came in 2009 with the breakthrough by Craig Gentry, then a Ph.D. student at Stanford under the supervision of Dan Boneh. In his dissertation [START_REF] Gentry | A fully homomorphic encryption scheme[END_REF], Gentry put forward the first plausible construction for an FHE scheme based on the hardness of some lattice problems, and that of the approximate GCD problem (cf. Chapter 2 for the details). This breakthrough had the effect of reigniting FHE as a topic of research, and since then many important results followed. Although the techniques improved greatly, and the schemes became simpler and more efficient, the original blueprint presented in Gentry's thesis continues to underlie all known FHE constructions.

The key idea that was proposed in Gentry's work is that of bootstrapping. By this term, we denote the process of refreshing a ciphertext in order to produce a new ciphertext that encrypts the same message, but with a lower level of noise so that more homomorphic operations can be evaluated on it. This operation is at the very core of any FHE schemes known to date, and consists of homomorphically evaluating the decryption circuit of the scheme. Roughly speaking, it is like decrypting the ciphertext with the secret key, and then re-encrypting the message, with the difference that the secret key is not known and it is replaced by an encryption of the secret key, called the bootstrapping key. This requires an additional hardness assumption, called circular security assumption, meaning that we must assume it is safe to publish an encryption of the secret key under itself. Although this assumption is still not well studied and understood, and it is sometimes regarded with suspicion, no attacks that exploit this extra piece of information have been proposed.

FHE in the user-server scenario

Fully homomorphic encryption has huge consequences in the world of delegated computations, as it essentially enables a user to safely hand all of its (encrypted) data to an untrusted remote party, and let it process the information, with the guarantee that the remote party will learn neither the input nor the output of the computation. Practical consequences are fairly easy to see; we present here some simple use cases:

• Emails could be stored encrypted, so that the email provider does not know the content of the messages. Also emails could be searchable, without the provider knowing what a user is looking for.

• Pictures could be uploaded to websites offering image processing capabilities, without the site learning the content of the original picture or that of the final picture.

• Medical data could be safely shared in order to extract statistics or make predictions on one's health condition, without revealing any sensitive information. For example, in the case of estimating the cost of a life insurance, this could be done by running an algorithm on encrypted data (the applicant's personal information), and returning an encrypted answer (the predicted cost of the insurance policy).

• One could even go so far as to imagining a completely homomorphic search engine, that can process encrypted search queries and return an encrypted list of matches.

The list of potential examples is unsurprisingly long, and the consequences of an introduction of FHE on a large scale would be very serious, with a strong enhancement of user's privacy. However, it might be worth pointing out something which might not be obvious at a first glance at the subject. While FHE certainly helps protecting user's privacy against a curious server, the fact that the server is no longer able to collect users' data would necessarily produce a change in the business plan of numerous internet companies. These enterprises normally provide services for free, in exchange for the possibility to harvest people's information in order to create tailored advertisement campaigns, extract statistics, . . .3 And while someone might argue that this is wrong on a moral ground and that anything that brings this to a stop is welcome, it is also true that companies need revenues for their survival. Preventing companies from generating profits from users' data would likely force them to adopt different strategies, such as that of making people pay for services that are normally expected to be free (rather, paid for through personal data), like email addresses, storage space, . . . This means that, just like any major technology, FHE has potentially serious and life-changing consequences, that have to be evaluated carefully, on the basis of the specific application, the privacy requirements, the costs, etc.

What currently keeps FHE from becoming a widespread tool is essentially efficiency. As we said before, all the solutions we know of for achieving the ability to perform unbounded computations are based on the operation of bootstrapping. Although this procedure has been improved and refined over the years, it remains costly and can considerably limit the efficiency of the scheme. A more viable alternative is that of relying on custom-made SHE instantiations, tailored to the specific application that is targeted. This solution is certainly less flexible, as it has to be adapted on a case-by-case basis, but offers the advantage that no bootstrapping is required. For real-world applications, SHE is usually the chosen approach, and more and more examples of practically efficient SHE are surfacing regularly.

User and server: different problems for different players

Since the user-server scenario is a world with two players, it is expectable that each of them has a different perspective, different security requirements, and different goals. We analyze them in the following.

The user's point of view

The user is mainly interested in having the privacy of his input data guaranteed by a strong encryption scheme, but is also concerned by the workload he faces in order to encrypt the input and decrypt the output. Another important point regards the communication complexity, or bandwidth usage: the user would like to minimize the amount of data he has to send to or download from the Cloud, which implies making ciphertexts as small as possible.

An emerging and fast-growing application that lies within the boundaries of Cloud computing is that of machine-learning-as-a-service (MLaaS), where a user submits data to a remote server, that applies a previously-trained predictive model (e.g., a neural network) to the data. The challenge, in this scenario, is usually represented by the complexity of the computations involved in the homomorphic evaluation of the predictive model, especially in the case of deep learning, where the depth of the circuit can be particularly large. For this kind of applications, the main goal is then to improve the efficiency in order to produce accurate results in a fast and reliable way.

The server's point of view

Although the previous part was mainly devoted to the user's needs and how to protect his input data, there can be security requirements from the server's side as well. In fact, a server might provide some data processing capabilities based on proprietary algorithms, that represent a key company asset and constitute sensitive intellectual property. A typical requirement is then that of circuit privacy [SYY99; IP07], meaning that the result returned by the server to the user at the end of the computation should leak no information on the algorithm (or circuit) that was applied to the encrypted inputs. In fact, it turns out that the noise term that is added for security purposes and that we mentioned before, not only grows with homomorphic operations, but changes in a way that somehow reflects (or depends on) the operations that are performed. Therefore, the noise contained in the final ciphertext that the user receives can leak information about how the result was produced, therefore jeopardizing the privacy of the algorithm. Instead, we would like the final result to contain no information at all on the computation, and we model this requirement as follows: let x be an input, encrypted as Enc (x), and let f be a function. Homomorphically evaluating f on Enc (x) means performing a certain number of homomorphic operations in order to produce a ciphertext that decrypts to f (x). The intuitive goal of circuit privacy is then for the outcome to "look like" a somewhat fresh encryption of f (x), which in turn guarantees that the result contains no information on f . The rough idea is that we want to keep the correct result, i.e., f (x), while removing all the information on f .

Our results

In this manuscript we propose contributions that improve the previous state of the art on both ends of the user-server use case.

A new framework for homomorphic evaluation of neural networks

With respect to the user's point of view, we propose a new framework for efficiently evaluating discretized neural networks on encrypted data. In this framework, the user encrypts his input data under a lattice-based encryption scheme, and sends the encrypted data to the other party. This party is able to homomorphically evaluate a neural network of arbitrary depth on the input, and finally returns the encrypted result. The substantial difference between our work [BMMP18] and previous works is that the instantiation of the encryption schemes, i.e., the parameters that define the scheme, does not have to depend on the network that Chapter 1

1. 4 Our results has to be evaluated. In previous works, the chosen approach was to tailor a somewhat homomorphic encryption scheme to a specific network, with parameters that were good enough for that application. The problem is that this solution is (1) not flexible, and (2) not suited for evaluating deep neural network, that would force to take extremely large and cumbersome parameters for correctness to hold, thus making the scheme completely inefficient and impractical.

On the other hand, our framework heavily relies on a recent and efficient implementation of the bootstrapping operation, through which we can refresh ciphertexts after the evaluation of each layer of the neural network. In turn, this allows us to "keep going with the computations", meaning that there is no a priori bound on the number of layers that can be evaluated. The disadvantage of this approach is that, in order to make our neural networks "FHE-friendly", we have to impose some limitations, namely the inputs and some internal values (weights and biases) have to be discretized. However, we note that this simplified model of neural networks has already been studied in the literature, and is known to achieve near-state-of-the-art performance.

A new technique for circuit privacy

With respect to the server's point of view, in [BPMW16] we propose a conceptually different approach to the problem of circuit privacy that, unlike previous works, is not based on annihilating the noise term by adding another large noise term to it (this technique is called noise flooding), or by using bootstrapping in order to "wash away" any trace of the previous computations. Instead, we directly analyze the distribution of the noise term and we show a way of removing the information on the circuit from the ciphertext in a simple and efficient way. In particular, we target the GSW FHE encryption scheme for branching program evaluation, and we introduce a modification that achieves circuit privacy essentially without worsening the overall efficiency of the scheme.

This work also gives better insights into the algebraic structure and the noise distribution in the GSW scheme, and provide new tools for analyzing noise randomization that could be of independent interest.

The fundamental downside of our approach is that it is fundamentally limited to the GSW encryption scheme, while it is not clear how to apply our techniques to other FHE schemes. In fact, although GSW is quite ubiquitous in the FHE world and it represents the most recent and asymptotically best instantiation of FHE, other schemes can be preferable and more efficient for specific applications.

Another limiting problem is that our technique only works in the honest-but-curious adversary model, i.e., we have to assume the adversary follows the protocol and play by the rules, but tries to extract as much information as it can from what it sees. This is opposed to the malicious adversary model, where the adversary can do whatever it wants and deviate in any way from the prescribed execution, including submitting malformed inputs. In the latter case, our technique breaks, as it relies on well-formed input ciphertexts.

A protocol for private information retrieval

Another contribution of this work is given by [BBB+17] and regards privacy-preserving interactions with a database held by another party. In particular, we devise a protocol for private information retrieval, meaning that a party A can query a database held by a party B, without B learning what A is looking for. We also show that, under appropriate conditions and with some formalization caveats, our protocol also achieves the property that A learns nothing more from the database than the records that match the query, thus achieving a stronger notion known as oblivious transfer. We also propose a C ++ implementation of the protocol that shows the practicality of our approach.

Other contributions

Apart from input data privacy, Cloud computing introduces another crucial challenge: can we trust the computation done by the Cloud? Can we be sure that the result is indeed the correct one and not some random or forged value? Outsourcing computations is clearly useless without a certain level of confidence in the correctness of the result, which is why we would like the Cloud to be able to "convince us" that the result is indeed valid, but without having to re-run the entire computation step by step.

In zero-knowledge (ZK) proofs (introduced in [GMR89]), a powerful prover can prove to a weaker verifier that a particular statement is true, without revealing why this is the case. More formally, given an NP language L with corresponding witness relation R, the prover will know a witness w that demonstrates the truth of a certain statement x ∈ L. With a zero-knowledge proof, the prover will be able to convince the verifier that the statement is indeed true, without revealing any information on the witness w. Non-interactive zero-knowledge proofs [START_REF] Blum | Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract)[END_REF] and succinct ZK arguments [START_REF] Kilian | A Note on Efficient Zero-Knowledge Proofs and Arguments (Extended Abstract)[END_REF][START_REF] Micali | CS Proofs (Extended Abstracts)[END_REF] were introduced shortly thereafter, but remained of mainly theoretical interest until more recently, when several breakthroughs have shown that these proofs can be used in practical applications (see e.g., Pinocchio [START_REF] Parno | Pinocchio: Nearly Practical Verifiable Computation[END_REF]).

A particularly interesting concept is that of SNARK, i.e., succinct non-interactive argument of knowledge. By this term, we denote a proof system which is non-interactive (it does not require multiple rounds of communication), complete (all correctly generated proofs are accepted), succinct (the size of the proof is linear in the security parameter), and knowledge-sound (for any prover able to produce a valid proof, there is an algorithm capable of extracting a witness for the statement). Recently, in two companion papers [BISW17; BISW18], Boneh et al. provided the first designated-verifier SNARKs construction based on lattice assumptions.

In [GMNO18] we build zero knowledge SNARKs (succinct non-interactive arguments of knowledge) from lattice assumptions for square span programs (SSPs), which are a way to characterize NP introduced in [START_REF] Danezis | Square Span Programs with Applications to Succinct NIZK Arguments[END_REF]. Compared with previous works, our result achieves zero-knowledge, relies on weaker assumptions, and is simpler and more efficient. Also, for a reasonable set of parameters, we achieve post-quantum security. In contrast, the size of our proofs is considerably larger than in previous works. Moreover, our construction is designated-verifier, meaning that the verification procedure requires access to some secret piece of information, as opposed to publicly verifiable, where the verification procedure can be run based solely on public information.

Organization of the manuscript

homomorphic encryption in details, and constitutes a sort of survey on the area; Chapter 4 addresses the problem of homomorphic evaluation of deep neural networks, and presents an efficient framework that allows one to evaluate an already-trained predictive model on encrypted inputs; Chapter 5 considers the other side of the coin for outsourced computations, and examines the problem of circuit privacy, resulting in a new and more efficient way of avoiding undesired leakages from the result of homomorphic computations; Chapter 6 presents the design and the concrete implementation of a protocol based on FHE for private information retrieval; finally, Chapter 7 draws some conclusions and outlines several questions that remain open and that can be the topic for extending the research presented in this manuscript.

Personal Publications

Notation and preliminaries

The notation used in this work is rather standard in cryptography and computer science: we explicitly define it here for completeness and to make this manuscript self-contained.

Mathematical notation

Sets, rings, integers

We denote the set of integers by Z, the set of non-negative integers by N, the set of reals by R and the set of integers modulo some q by Z q . We use T to indicate R/Z, i.e., the torus of real numbers modulo 1. We denote by {0, 1} n a bitstring of length n; sometimes we use B for {0, 1}. For any ring R, we use R [X] for polynomials in the variable X with coefficients in R. We use

R N [X] to denote R [X] / X N + 1 , and Z N [X] to denote Z [X] / X N + 1 ,
and we write their quotient as

T N [X] = R N [X] /Z N [X],
i.e., the ring of polynomials in X quotiented by X N + 1 , with real coefficients modulo 1.

For two integers a, b such that a < b, we write {a, . . . , b} to denote the set of integers between a and b (a and b included). If a = 1, then we use [b] for {1, . . . , b}. For a finite set S, we denote its cardinality by |S|.

For x ∈ Z, x mod q denotes the remainder of the Euclidean division of x by q. For y ∈ R, |y| denotes its absolute value and log y its logarithm in basis 2, y is the smallest integer z such that y ≤ z, y is the biggest integer z such that z ≤ y, and y is the closest integer to y, with ties broken upward.

Vectors and matrices

Vectors are denoted by lower-case bold letters, like v, and are always columns. We indicate a vector v's i-th entry by v i (not in bold). We use v for the transpose of a vector v, which is then a row. For a vector v, we define the L p norm as Matrices are denoted by upper-case bold letters, like A, and we use A for the transpose of the matrix A. When a square matrix is invertible, we denote by A -1 its inverse. Sometimes we consider a n × m matrix as the ordered sequence of its columns: in this case we write A = (a 1 , . . . , a m ). We will also use 0 for either the zero-vector or the zero-matrix (it will be clear from the context), and I n for the n × n identity matrix.

v p = n i=1 |v i | p 1/p
For a d 1 -dimensional vector a and a d 2 -dimensional vector b, we write (a b) to denote the (d 1 + d 2 )-dimensional vector obtained by concatenating a and b. We will use a similar notation for concatenating matrices with matrices or matrices with vectors.

Distributions and probabilities

Given a set S, we write x ←$ S to indicate that x is sampled uniformly at random from S (independently of everything else). Similarly, if D is a probability distribution, then we Chapter 2

2.1 Notation and preliminaries write x ← D to denote that x is sampled according to D. We write Pr[X = x] to indicate the probability of a random variable X taking the value x. Given two distributions X, Y over a finite or countable domain D, their statistical distance is defined as ∆ (X, Y ) =

1 2 v∈D |X(v) -Y (v)|.
When it is clear from the context, we sometimes write "random" for "uniformly at random".

Asymptotic behaviors

When f and g are two functions N → R, we write f = O (g ) to indicate that there exist a constant c and an integer n 0 ∈ N such that for any integer

n ≥ n 0 , |f (n)| ≤ c • |g(n)|. We say that a function ε : N → [0, 1] is negligible (or 1 -ε is overwhelming) if, for any constant c ∈ N, there exists η 0 ∈ N such that for any η ≥ η 0 , ε ≤ 1 η c .

Algorithms

For simplicity, unless otherwise stated, we consider all the algorithms as probabilistic Turing machines. This means that we implicitly assume that they can use an additional tape containing random bits (also referred to as random coins). In the rest of this thesis, we use the term "PPT algorithm" for "Probabilistic Polynomial-Time algorithm", and we say an algorithm is efficient if it is a PPT algorithm. For an algorithm A, we write y ← A(x) to denote the fact that we run A on input x with fresh random coins and we obtain an output y. In case A is a deterministic algorithm, we will instead write y = A(x).

Provable security

Almost any problem can be solved if enough computational power or enough time is available, e.g., by enumerating and trying every possible solution until finding the right one (this approach is known as brute-force attack). With this in mind, the goal of provable security is then to assess the amount of effort required to solve a certain problem (i.e., break a certain system). A cryptosystem is deemed "secure" if breaking it would require an unreasonable effort (with regards to computations, elapsed time, data storage, . . . ) from a reasonable attacker. The choice of what is reasonable depends on the security model (e.g., what kind of adversary we are considering), and on the security guarantees that we require1 . These considerations are numerically represented by a security parameter, that we denote with κ: a cryptosystem provides κ bits of security if it requires 2 κ elementary operations to be broken. Although usually omitted in order to ease notation, all the integers, vectors, and matrices that we define will implicitly be a function of κ. However, sometimes we explicitly write that an algorithm (e.g., Setup) takes 1 κ as an argument. The reason for doing this is that we want the algorithm to run in a time that is polynomial in κ, so its input must have size κ.

The adversaries we consider in this work are PPT algorithms and we denote an adversary's advantage when attacking a scheme, a protocol, or a generic construction, by Adv.

Cryptographic primitives

In this part we give a basic introduction to secret-key and public-key encryption schemes, outline some generic algorithms and provide some definitions related to the security of encryption schemes.

Definition 2.2.1 (Secret-key encryption scheme). A secret-key encryption scheme consists of the following algorithms:

• KeyGen (1 κ ) → (k, pp): on input the security parameter κ, outputs the key k and some public parameters pp;

• Encrypt (k, m) → c: on input the key k and a message m, outputs a ciphertext c;

• Decrypt (k, c) → m: on input the key k and a ciphertext c, outputs a message m.

While in a secret-key encryption scheme the same key is used both for encrypting and decrypting, in a public-key encryption scheme there are two separate keys, a public and a private (or secret) one, which are used for encrypting and decrypting, respectively.

Definition 2.2.2 (Public-key encryption scheme). A public-key encryption scheme consists of the following algorithms:

• KeyGen (1 κ ) → (pk, sk, pp): on input the security parameter κ, outputs the public key pk, the secret key sk, and some public parameters pp;

• Encrypt (pk, m) → c: on input the public key pk and a message m, outputs a ciphertext c;

• Decrypt (sk, c) → m: on input the secret key sk and a ciphertext c, outputs a message m.

We now give a standard definition of security for an encryption scheme, namely that of indistinguishability under chosen-plaintext attacks (IND-CPA).

Definition 2.2.3 (Indistinguishability under chosen-plaintext attacks). For a public-key

encryption scheme E, we define IND-CPA security via the game depicted in Figure 2.1. Let

Adv IND-CPA A (κ) = Pr[IND-CPA E,κ ] - 1 2
be the advantage of an adversary A when playing the game

IND-CPA E,κ . We say that E is IND-CPA secure if, for any PPT adversary A, it holds that Adv IND-CPA A (κ) = negl(κ).
Chapter 2

Lattices

Game IND-CPA E,κ (pk, sk, pp) ← KeyGen (1 κ ) (m 0 , m 1 ) ← A (1 κ , pk, pp) b ←$ {0, 1} c ← E.Encrypt (pk, m b ) b ← A (1 κ , pk, pp, c) return b = b

Lattices

In this part we present some basic definitions about lattices and we recall several fundamental computational problems. 6 (Determinant of a lattice). Let Λ (B) be a lattice with rank n. We define the determinant of Λ, denoted as det (Λ), as the n-dimensional volume of its fundamental parallelepiped P (B). In symbols, we can write this as det (Λ) := det (B B). Definition 2.3.7 (Dual and orthogonal lattice). The dual of a lattice Λ ⊂ R n is defined as

Basic definitions

P (B) = {Bx : x ∈ R n , 0 ≤ x i < 1 ∀i} Definition 2.3.
Λ * := {v : v, Λ ⊆ Z} ,
i.e., the set of points whose inner products with the vectors in Λ are all integers. It is easy to verify that the dual of a lattice is still a lattice. Given a rank k matrix B ∈ R n×k , we define the q-ary orthogonal of a lattice Λ as

Λ ⊥ q (B) := {v ∈ Z n : B v = 0 mod q} . O b 1 b 2 b 1 b 2 Figure 2.2:
A two-dimensional lattice with two different bases.

Computational problems

In this part we recall several classical computational problems on lattices.

Definition 2.3.8 (Shortest Vector Problem (SVP)). Given an arbitrary basis B of some lattice Λ = Λ (B), find a shortest2 nonzero lattice vector, i.e., a vector v ∈ Λ such that v = λ 1 (Λ).

In the following, we present several approximation problems, parameterized by an approximation factor γ ≥ 1, usually taken as a function of the lattice dimension n, i.e., γ = γ (n). Definition 2.3.9 (Approximate Shortest Vector Problem (SVP γ )). Given an arbitrary basis B of a lattice Λ = Λ (B), find a nonzero vector v ∈ Λ such that v ≤ γ • λ 1 (Λ). Definition 2.3.10 (Decisional Approximate SVP (GapSVP γ )). Given an arbitrary basis B of a lattice Λ = Λ (B), where λ 1 (Λ) ≤ 1 or λ 1 (Λ) > γ, determine which is the case. Definition 2.3.11 (Approximate Shortest Independent Vector Problem (SIVP γ )). Given an arbitrary basis B of an n-dimensional lattice Λ = Λ (B), output a set S = {v 1 , . . . , v n } ⊂ Λ of n linearly independent lattice vectors such that

v i ≤ γ • λ i (Λ) for all i ∈ [n].
Definition 2.3.12 (Approximate Closest Vector Problem (CVP γ )). Given an arbitrary basis B of an n-dimensional lattice Λ = Λ (B) and a target vector t ∈ R n , find a vector v ∈ Λ

such that 0 < v -t ≤ γ • D (t, Λ) = γ • inf x∈Λ x -t .
∈ R n such that D (t, Λ) ≤ γ -1 • λ 1 (Λ), find a vector v ∈ Λ such that v -t = D (t, Λ).

Worst-case hardness

For a problem to be useful in cryptography, we require it to be hard on average, i.e., a random instance of this problem should be hard to solve. Instead, a more common definition of hardness is related to the worst case, i.e., a problem is hard if some instances of this problem are hard to solve. In [START_REF] Ajtai | Generating Hard Instances of Lattice Problems (Extended Abstract)[END_REF], Ajtai gave a connection between these two situations and proved that there are cryptographically useful problems that are hard on average, as long as certain lattice problems are hard in the worst case. This essentially makes implementing cryptosystems considerably easier, as one can just pick a random instance of the problem and be reasonably sure that this instance is hard. On the other hand, this does not happen with many number theory problems, where implementing requires checking that a specific instance of the problem is hard to break.

Gaussians

In this part, we introduce some notions about discrete Gaussian distributions that we will use throughout this work. Definition 2.3.14 (Gaussian function and discrete distribution). For any α > 0 the spherical Gaussian function with parameter α (omitted if 1) is defined as

ρ α (x) := exp -π x α 2
for any x ∈ R n . Given a lattice Λ ⊆ R n , a parameter r ∈ R, and a vector c ∈ R n , the spherical Gaussian distribution with parameter r and support Λ + c is defined as

D Λ+c,r (x) := ρ r (x) ρ r (Λ + c) , ∀x ∈ Λ + c
where ρ r (Λ + c) denotes v∈Λ+c ρ r (v).

Remark 2.3.15. Note that ρ r (x) = ρ r -1 x .

Definition 2.3.16 (Sub-Gaussian distribution). A distribution D is sub-Gaussian with parameter α if there exists M > 0 such that for all x ∈ R n ,

D (x) ≤ M • ρ α (x) .
We now report a very well known result about additivity of Gaussian distributions.

Lemma 2.3.17 (Pythagorean additivity of Gaussians). Let D 1 and D 2 be Gaussian distributions with parameters σ 1 and σ 2 , respectively. Then D + , obtained by sampling D 1 and D 2 and summing the results, is a Gaussian with parameter σ 2 1 + σ 2 2 . Another important quantity for a lattice Λ is its smoothing parameter. Roughly speaking, this can be seen as the minimum amount of Gaussian "blur" required to "smooth out" all the discrete structure of Λ. We now give a more formal definition. Definition 2.3.18 (Smoothing parameter [START_REF] Micciancio | Worst-Case to Average-Case Reductions Based on Gaussian Measures[END_REF]). For a lattice Λ ⊆ R n and a positive real ε > 0, the smoothing parameter η ε (Λ) is the smallest real r > 0 such that ρ 1/r (Λ * \ {0}) ≤ ε, where Λ * is defined as per Definition 2.3.7.

Short integer solution (SIS)

The short integer solution problem was first introduced in the work by Ajtai [START_REF] Ajtai | Generating Hard Instances of Lattice Problems (Extended Abstract)[END_REF], and has served as the foundation for one-way functions, collision-resistant hash functions, and other primitives. Definition 2.3.19 (The SIS problem). The short integer solution problem is parametrized by four integers: the lattice dimension n, the number of samples m, the modulus q, and the constraint β.

Given m uniformly random vectors a i ∈ Z n q , forming the columns of a matrix A ∈ Z n×m q , find a nonzero integer vector z ∈ Z m of norm z ≤ β such that

Az = i a i z i = 0 ∈ Z n q .
Note that it must be β < q, otherwise the vector (q, 0, . . . , 0) ∈ Z n q would always be a valid solution. On the other hand, β must be large enough that a solution is guaranteed to exist. For example, let m = n log q. Then, β ≥ √ m is enough to have this guarantee. In fact, there are more than q n vectors in {0, 1} m , so there must be two distinct vectors x, x ∈ {0, 1} m such that Ax = Ax . In turn, this means that A (xx ) = 0 ∈ Z n q . The conclusion is that the vector y = xx ∈ {-1, 0, 1} m is a solution of norm at most √ m = β. By the same argument, we can also conclude that the function

f A : {0, 1} m → Z n q f A (x) := Ax = i a i x i ∈ Z n q
is collision-resistant, assuming the hardness of the corresponding SIS problem. The reason is immediately clear: finding a collision means finding two distinct vectors x, x ∈ {0, 1} m such that Ax = Ax , but this immediately yields the solution xx to the SIS problem for the matrix A.

Learning with errors (LWE)

The learning with errors (LWE) problem was introduced by Regev in [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF], and has become one of the most known problems in lattice-based cryptography. It has been used to construct several cryptosystems, and it is believed to be hard even for quantum computers. This problem comes in two flavors, search and decision: we present them both in the following.

LWE is parameterized by two positive integers, n and q, and an error distribution χ over Z, usually a discrete Gaussian of width αq, 0 < α < 1. Definition 2.3.20 (LWE distribution). Given a secret vector s ∈ Z n q , the LWE distribution lwe s,χ over Z n q × Z q is sampled by picking a ←$ Z n q , an error e ← χ, and returning (a, b = s, a + e).

We now present the two versions of the LWE problem. Definition 2.3.21 (Search-LWE slwe n,q,χ,m ). Given m independent samples (a i , b i ) ← lwe s,χ , for a fixed s ←$ Z n q , find s. Definition 2.3.22 (Decisional-LWE dlwe n,q,χ,m ). Given m independent samples (a i , b i ) ∈ Z n q × Z q , where every sample is either distributed according to lwe s,χ for some fixed s ∈ Z n q or uniformly random in Z n q × Z q , distinguish which is the case.

Chapter 2

that R = Z [X] /f (X)
, with f some cyclotomic polynomial of degree n. Also, let q ≥ 2 be an integer modulus, and let R q = R/qR be the quotient ring. Finally, let χ be an error distribution over R. For a fixed secret s ∈ R q , the ring-LWE distribution ring-lwe s,χ is sampled by taking a ←$ R q , e ← χ, and outputting (a, b = s • a + e). All the computations are, as usual, done modulo q.

Analogously to what was done for LWE, we now present the two versions of the ring-LWE problem.

Definition 2.3.24 (Search ring-LWE). Given m independent samples (a, b) ← ring-lwe s,χ , for a fixed s ←$ R, find s.

Definition 2.3.25 (Decisional ring-LWE). Given m independent samples (a, b) ∈ R × R,
where every sample is either distributed according to rlwe s,χ for some fixed s ∈ R or uniformly random in R × R, distinguish which is the case.

The advantage of using ring-LWE instead of plain LWE is compactness and efficiency. In fact, in the case of ring-LWE, each sample gives a n-dimensional pseudorandom ring element b ∈ R, instead of just a pseudorandom scalar b ∈ Z q . We can thus say that a single ring-LWE sample with a ∈ R takes the place of n LWE samples with vectors a i ∈ Z n q . Moreover, thanks to techniques like FFT, the multiplication between ring elements can be performed in quasi-linear time. The essential drawback of ring-LWE is its conjectured hardness, which is not as well-established as for LWE. We will not give details about this, but refer the interested reader to specialized literature (e.g., [START_REF] Albrecht | On The Concrete Hardness Of Learning With Errors[END_REF][START_REF] Bonnoron | A Note on Ring-LWE Security in the Case of Fully Homomorphic Encryption[END_REF]). However, results on ring-LWE hardness are not conclusive and the question stands wide open, with some prominent figures in the community like Dan Bernstein notoriously expressing concerns (see e.g., [START_REF] Daniel | A subfield-logarithm attack against ideal lattices[END_REF]), and other famous researchers like Chris Peikert, Damien Stehlé, Vadim Lyubashevsky, and Léo Ducas usually more skeptical and less convinced that disastrous attacks really exist3 . In the past, this topic has even generated heated discussions (cf. e.g., [START_REF] Daniel | Soliloquy. Discussion on Google Groups[END_REF][START_REF] Daniel | Ideal-SVP attacks? Discussion on Google Groups[END_REF]), showing that the questions related to ideal lattice cryptography and its security are very important ones and need more attentive investigation.

Link between LWE and lattice-based problems

We now clarify the link between LWE and the lattice problems presented in Section 2.3.2.

Let A ←$ Z n×m q , and let Λ be the following lattice

Λ = Λ (A) := A v : v ∈ Z n q + qZ
m This is an m-dimensional q-ary lattice, since A has m rows and the lattice is defined modulo the integer q.

Let s ←$ Z n q , let χ be an LWE error distribution, e ← χ m , and b = A s + e ∈ Z m q . Now it is easy to see that, for sufficiently small error terms, the vector b is rather close to a specific vector (or point) of the lattice Λ, namely A s, whereas a random vector u ←$ Z m q will be far from Λ with high probability. We can then conclude that solving search-LWE amounts to solving an average instance of the BDD problem on the lattice Λ. In fact, once the vector A s ∈ Λ has been found, s can be trivially recovered, e.g., by Gaussian elimination.

Complexity assumptions

In this subsection, we list the complexity assumptions we rely on in this manuscript. This assumption simply says that the lattice problems presented in Section 2.3.2, despite having been studied intensively over the years, are intractable, except for very large approximation factors γ. We currently know of some polynomial-time algorithms, like the famous LLL algorithm by Lenstra, Lenstra, and Lovász [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF], that obtain only slightly subexponential approximation factors γ (n) = 2 Θ(n log log n/ log n) for all the problems stated in Section 2.3.2. When requiring polynomial (meaning poly (n)) or better factors γ, the algorithms we currently know either require superexponential 2 Θ(n log n) time or exponential 2 Θ(n) time and space. Between these two extremes, there are intermediate solutions that achieve γ = 2 k approximations factors in 2 Θ(n/k) time [START_REF] Schnorr | A hierarchy of polynomial time lattice basis reduction algorithms[END_REF].

Interestingly, this is also the state of the art for quantum algorithms, although some constant factors might be smaller. In a nutshell, quantum attacks on lattice problems do not achieve anything beyond generic quantum speedups, which justifies the following assumption. Assumption 2.4.2 (Quantum hardness of lattice problems). It is hard to solve the problems presented in Section 2.3.2, even with a quantum computer.

Most of the constructions presented in this manuscript will be based on the decisional LWE (dlwe) problem. In [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF], Regev proved the following theorem on the hardness of dlwe: Theorem 2.4.3 (Hardness of dlwe). For any m = poly (n), any modulus q ≤ 2 poly(n) , and any (discretized) Gaussian error distribution χ of parameter αq ≥ 2 √ n (where 0 < α < 1), solving the dlwe n,q,χ,m problem is at least as hard as quantumly solving GapSVP γ and SIVP γ on arbitrary n-dimensional lattices, for some γ = O (n/a). This justifies the following assumption: Assumption 2.4.4 (dlwe). For a correct choice of parameters, it is hard to break the dlwe problem defined in Definition 2.3.22.

Finally, we will use an assumption on the so-called approximate GCD problem: we now present the problem and the related assumption. The approximate-GCD problem (AGCD) was introduced in 2001 by Howgrave-Graham [START_REF] Howgrave-Graham | Approximate Integer Common Divisors[END_REF] and is parametrized by integers γ, η, ρ ∈ N.

Chapter 2

Complexity assumptions 23

Definition 2.4.5 (Approximate GCD distribution). The AGCD distribution agcd ρ (p, q 0 ) for a given η-bit integer p and a q 0 ←$ [0, 2 γ /p) is the set of integers x i = p • q i + r i , where q i ←$ [0, q 0 ) and r i ←$ [0, 2 ρ ).

Definition 2.4.6 (Approximate GCD problem). For a η-bit integer p and a uniformly chosen q 0 ←$ [0, 2 γ /p), given polynomially many samples from agcd ρ (p, q 0 ), find p.

Assumption 2.4.7 (Hardness of the approximate GCD problem). For appropriately set parameters γ, η, ρ ∈ N, it is hard to break the AGCD problem of Definition 2.4.6.

For a review on several kind of attacks to this problem, we refer the reader to, e.g., [How01; CH11; CMNT11; CNT12; CN12].

Chapter 3

Chapter 3

Fully homomorphic encryption

In this chapter we present fully homomorphic encryption in details, recalling its history from the first plausible construction, through successive improvements, to today's "almost practical" instantiations. We also go through several homomorphic cryptosystems that have been proposed, analyzing their pros and cons, in hope to give a sort of "bird's eye view" on this field. Some of the contents about this part are inspired by the PhD thesis of Tancrède Lepoint [START_REF] Lepoint | Design and Implementation of Lattice-Based Cryptography[END_REF]. We will conclude this chapter with a part on implementation, reviewing some libraries that have been developed over the years, and assessing their performances, their potential, and their limitations.

The idea is for this chapter to be of independent interest as a sort of survey on FHE.

Contents

Introduction

Homomorphic encryption is a kind of encryption that allows one to perform operations on ciphertexts based solely on publicly available information, and in particular without having access to any secret key. The reason why it is called "homomorphic" is that, roughly speaking, there exists a correspondence between the space of the messages and the space of the ciphertexts, in such a way that operations performed on ciphertexts are somehow reflected in operations on the messages they encrypt. For example, an additively homomorphic encryption scheme allows anyone to take a ciphertext c 1 encrypting a message m 1 , a ciphertext c 2 encrypting a message m 2 , and produce a ciphertext c + that decrypts to m 1 + m 2 . Analogously, a multiplicatively homomorphic encryption scheme allows one to produce a ciphertext c × that decrypts to m 1 • m 2 . And this is possible without having access to either m 1 or m 2 or any secret information. We say that an encryption scheme is partially homomorphic if it supports only some operations, but not others: for example, a scheme could support homomorphic addition but not multiplication.

In most of the homomorphic encryption schemes known to date, an error term is injected during the encryption procedure for security purposes. The reason is that these encryption schemes rely on the hardness of solving "noisy" problems, i.e., problems where the relations are not exact, but are perturbed by a moderate quantity of error. Combining multiple ciphertexts through homomorphic operations has the side effect of combining the noises as well, thus increasing the magnitude of the error in the resulting encryption. When the error grows beyond a certain threshold, correctness is lost, meaning that the decryption procedure will not return the expected result. We say that an encryption scheme is somewhat homomorphic if it can evaluate a certain number of homomorphic operations, before the error grows too much to maintain the correctness of the evaluation.

When practically instantiating an encryption scheme, one of the most delicate steps is that of choosing parameters. This usually requires finding a sensible trade-off between security and efficiency, and remains one of the potentially weak points for theoretically secure schemes. This is also the case for homomorphic encryption schemes, but in this case the problem of finding parameters is even more important. In fact, parameters like the size of the modulus or the standard deviation of noise terms define the threshold below which the noise must remain in order to guarantee a correct decryption. By doing so, these parameters control how many homomorphic operations can be carried out. We say that an encryption scheme is leveled homomorphic if, for any multiplicative depth L fixed a priori, we can find a set of parameters such that the encryption scheme instantiated with these parameters can evaluate any circuit with multiplicative depth equal to L. We stress that, in this setting, the bound on the number of operations has to be known at setup time, i.e., when setting the parameters. This means that the scheme will tend to be tailored for a specific application, rather than being a generic tool for evaluating any function.

On the other hand, a fully homomorphic encryption (FHE) scheme is a homomorphic scheme that allows for the evaluation of arbitrarily complex computations over encrypted data. The problem of designing such scheme was suggested by Rivest, Adleman and Dertouzos in 1978 [START_REF] Rivest | On Data Banks and Privacy Homomorphisms[END_REF] but, despite moderate progress [GM82; Pai99; BGN05; IP07], it remained the "Holy Grail of cryptography" (cit. [START_REF] Micciancio | A first glimpse of cryptography's Holy Grail[END_REF]) until the breakthrough result of Gentry in 2009 [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF]. In the case of FHE, there is no need to set an a priori bound on the number of homomorphic operations, thus making the scheme more flexible. In contrast, FHE schemes tend to be considerably less efficient than leveled ones, which, for specific ap-plications, can be noticeably faster and, as a consequence, more appealing. In a nutshell, the matter boils down to a trade-off between flexibility on one side and efficiency/optimization on the other side.

Finally, we note that it is not rare to see in the literature leveled homomorphic encryption being called somewhat homomorphic encryption. Although the meaning is usually clear from the context, a somewhat homomorphic encryption scheme denotes a scheme with limited homomorphic properties, for example one that can only evaluate additions or multiplications.

Over the years, homomorphic encryption has been a very active field for research, and this has led to a long list of works and improvements, (e.g., [DGHV10; SS10; SV10; BV11a; BV11b; BGV12; GHS12; GSW13; BV14; AP14]). This comprised both theoretical works that put forth new ideas and constructions, and implementation works that optimized existing constructions with the goal of achieving the best possible efficiency.

The FHE constructions that we know of can roughly be divided into three groups, usually referred to as generations. "first generation" FHE usually denotes the one stemming directly from Gentry's seminal work [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] and based on ideal lattices and the approximate GCD problem; "second generation" usually indicates constructions proposed in a sequence of works by Brakerski and Vaikuntanathan [BV11a;[START_REF] Brakerski | Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages[END_REF] and based on the LWE problem; "third generation" usually denotes the GSW FHE scheme by Gentry, Sahai, and Waters [START_REF] Gentry | Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based[END_REF] and subsequent works (e.g., [START_REF] Alperin | Faster Bootstrapping with Polynomial Error[END_REF][START_REF] Hiromasa | Packing Messages and Optimizing Bootstrapping in GSW-FHE[END_REF]).

In the following, we review all three generations and try to explain the main ideas behind them and the principal changes and improvements when moving from one generation to another. Before doing so, we give some definitions and a high-level introduction to a key technique called bootstrapping, that remains at the very core of all currently known FHE schemes.

Homomorphic encryption scheme

A homomorphic (secret-key) encryption scheme E with message space M is composed of the following algorithms: E.KGen (1 κ ) → (sk, evk) : given the security parameter, output a secret key sk and an evaluation key evk.

E.Enc (sk, µ) → c : given the secret key sk and a message µ ∈ M, output a ciphertext c.

E.Dec (sk, c) → µ : given the secret key sk and a ciphertext c, output a message µ ∈ M.

E.Eval (evk, f, c 1 , . . . , c ) : given the evaluation key evk, a function f : M → M and ciphertexts c 1 , . . . , c , apply the function f on ciphertexts c i and output a ciphertext c f . We now give a fundamental definition for any FHE scheme, i.e., evaluation correctness. Definition 3.2.1 (Evaluation correctness). We say that the E.Eval algorithm correctly evaluates all functions in F if, for any function f ∈ F : M → M and respective inputs x 1 , . . . , x , it holds that

Pr[E.Dec (sk, E.Eval (evk, f, c 1 , . . . , c )) = f (x 1 , . . . , x )] = negl(κ) ,
where sk ← E.KGen (1 κ ), and c i ← E.Enc (sk, x i ) , ∀i ∈ [ ].

Bootstrapping and key-switching

Every FHE construction that we know of is based on "noisy" encryption, i.e., each ciphertext contains a certain amount of noise (or error) that is vital for the security of the scheme. Whenever performing homomorphic operations on ciphertexts, the noise term contained in the output ciphertext is larger than those in the input ciphertexts, as a result of some sort of interaction that happens during the homomorphic computation. We can then say that homomorphic operations make the error grow1 . We encounter problems when the noise grows beyond a certain threshold and makes the ciphertext "too noisy" to be correctly decrypted. This means that decrypting the ciphertext will produce a message which is different from the expected one; one can think of the noise becoming so large that it changes the value of the message.

A trivial solution is that, for a specific circuit that has to be homomorphically evaluated, one can choose the parameters of the encryption scheme so that this threshold is high enough to carry out all the computations that are needed. However, this bound has to be known in advance, before setting the parameters and instantiating the encryption scheme. Since homomorphic operations increase the noise in the ciphertexts, it is impossible to carry out an unbounded number of homomorphic operations without reaching the threshold and, therefore, loosing correctness. This remained a key obstacle on the path to FHE, until Gentry's original work [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] proposed a beautiful idea called bootstrapping.

Given a ciphertext c that encrypts a message m and that contains a large (but still within the threshold) noise e, if we had the correct secret key we could simply decrypt c, recover m, pick a smaller error e and re-encrypt m with this noise. In other words, if we had the secret key we could refresh a ciphertext by decreasing the noise it contains: this would open the way to unbounded computations. In fact, it would be sufficient to perform homomorphic operations and refresh the ciphertexts before loosing correctness. However, as previously stated, the goal with FHE is to publicly perform operations on encrypted data, i.e., without having access to private information, namely the secret key.

The key intuition for this bootstrapping procedure is to perform this decrypt-and-encrypt procedure homomorphically! In formulas, what we want to achieve is this

c = Enc (Dec (sk, c)) , ( 3.1)
i.e., produce a fresh ciphertext c that encrypts the same message as c, but with smaller noise. When moving to homomorphic operations, let us consider the following:

c = Enc Dec sk , c , (3.2)
where boxed terms are encrypted. Equation (3.2) can be seen as being the encrypted "equivalent" of Equation (3.1), where all the inputs and the outputs are encrypted. Two things are immediately noticeable: (1) this procedure requires an encryption of the secret key sk, and (2) the final result is not a fresh encryption c , but an encryption of an encryption, i.e., we added a layer of encryption. The second issue is due to the fact that the procedure outlined in Equation (3.2) was purposely inaccurate, and only meant to give an intuition. What happens in reality is that the ciphertext c is hardwired in the decryption circuit, so that the encryption of the secret key is the only input. The final output is then a ciphertext, without any additional layer of encryption, as was the case for Equation (3.1). In formulas,

c = Dec c sk (3.3)
In conclusion, what we need is for the encryption scheme to be able to homomorphically evaluate its decryption function.

As far as the encryption of the secret key is concerned, this term is usually referred to as

bootstrapping key (bk), and it appears to be necessary for the bootstrapping to work. The question is then the following:

Under which key should the secret key be encrypted?

There are two possibilities:

1. The secret key sk is encrypted under itself, i.e., bk = Enc (sk, sk);

2. The secret key sk is encrypted under another key sk , i.e., bk = Enc sk , sk .

The first alternative leads to the situation where the refreshed ciphertext c is encrypted under the same key as the original ciphertext c. This is advantageous because the secret key remains the same and there is no collection of keys to handle (see, e.g., [BGV12, Section 5.5]). However, following this alternative forces to make the so-called circular security assumption.

Assumption 3.3.1 (Circular security (informal)). It is safe to publish an encryption of the secret key sk under itself.

For a more formal statement of this assumption, consider the following: let E be a homomorphic encryption scheme, and let Adv IND-CPA A (x) be the advantage that the adversary A running on input x has when trying to break the semantic security of E (see Figure 2.1 for the depiction of the IND-CPA game). Then the circular security assumption can be formulated as follows: Assumption 3.3.2 (Circular security). For any PPT adversary A,

Adv IND-CPA A (1 κ , bk) -Adv IND-CPA A (1 κ ) = negl(κ) ,
where bk is a bootstrapping key for the scheme E.

It is currently unknown whether we can prove that revealing such an encryption is secure but, although this assumption is sometimes regarded with suspicion, no concrete attacks have ever been shown.

Instead, the second alternative (i.e., encrypting the secret key under a different key) leads to the situation where the refreshed ciphertext c is encrypted under a different secret key and, for this reason, this procedure is also referred to as key switching. It has the advantage of not requiring any circular security assumption, but it does require handling several keys and, above all, agreeing on these keys beforehand. Moreover, a fundamental limitation of this approach is about the number of operations that can be performed, that depends on the number of keys that were agreed upon in advance. In fact, if there are N keys available, it is clear that it will be possible to do at most N bootstrapping operations: this means that the scheme will not be fully homomorphic but will achieve only a leveled homomorphism. Also, note that switching to any previously-used key, e.g., sk 1 → sk 2 → • • • → sk N → sk 1 , anyway requires assuming circular security. The conclusion is that, as of today, the instantiation of a fully-fledged FHE scheme does require the circular security assumption. Any other approach will only achieve limited homomorphic properties, that will allow for the evaluation of a bounded circuit.

Finally, a note on efficiency: bootstrapping is a complex procedure, that involves the homomorphic computation of a somewhat intricate function. For this reason, it is not very efficient and remains one of the major bottlenecks in FHE implementations. Over the years, several works aimed at optimizing bootstrapping, both from the point of view of the running time and from that of when to perform this operation during the evaluation of a circuit (e.g., see [AP13; AP14; DM15; CGGI16b; CGGI17; ZYL+17; BLMZ17]).

We now present a basic version of a well-known encryption scheme based on the LWE assumption, usually referred to as the Regev encryption scheme [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. The ideas that this construction is based on will be re-used several times in this manuscript.

Construction 3.3.3 (Regev's symmetric encryption scheme). This encryption scheme operates on bits, i.e., the message space is M = {0, 1}. It is composed of the following algorithms:

KGen (1 κ ) → (sk, pp) : given the security parameter in unary, choose an integer n = n (κ), a modulus q = q (κ), an error distribution χ = χ (κ), and output a secret key sk ←$ Z n q and public parameters pp = (n, q, χ). In the following, pp is an implicit argument to all the algorithms.

Enc (sk, m ∈ M) → c : given the secret key sk and a message m, sample a ←$ Z n q , e ← χ,

and return c = a, b = sk, a + e + m q 2 ∈ Z n+1 q .
Dec (sk, c) → m : given the secret key sk and a ciphertext c = (a, b) ∈ Z n+1 q , compute bsk, a and return m = 0 if this quantity is closer to 0 than to q 2 . Otherwise return 1. Correctness and security of Construction 3.3.3 are straightforward: correctness holds as long as |e| < q 4 , whereas security comes directly from the LWE assumption. In particular, the term sk, a + e plays the role of a random mask for the message m. Remark 3.3.4 (Extending the message space). Construction 3.3.3 can be trivially extended to M = Z p , for q > p ∈ N. It is sufficient to multiply m by q p instead of q 2 during encryption, and round appropriately during decryption. Naturally, this implies a different condition on the error for correctness to hold: in this case, it is necessary that |e| < q 2p .

Three generations of FHE

After giving these introductory notions on FHE and a basic construction, we finally turn to analyzing the different generations of fully homomorphic encryptions.

First generation FHE

The first generation of FHE is that which stems directly from Gentry's seminal work (mainly his STOC paper [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] and his Ph.D. thesis [START_REF] Gentry | A fully homomorphic encryption scheme[END_REF]), and it was the first concrete proposal for an encryption schemes that allows for unbounded computation on encrypted data. We now give a brief and high-level presentation of this construction, and we refer the reader to the cited material and to [START_REF] Gentry | Implementing Gentry's Fully-Homomorphic Encryption Scheme[END_REF] for more details. This scheme is a public-key encryption scheme à la [START_REF] Goldreich | Public-Key Cryptosystems from Lattice Reduction Problems[END_REF] over ideal lattices in a polynomial ring R. In the ring R, two ideals I and J are chosen: the public key is a "bad basis" of the ideal lattice J, whereas the private key is a "good basis" of this ideal. Then, a single bit plaintext is embedded in R/I and added to an error term sampled from I. The sum is then reduced using the public key (i.e., the public basis of J), thus obtaining the ciphertext. This way, the message part and the error part are separated, which will be extremely important for homomorphic operations. If the error term is small enough, then the secret basis of J allows one to separate the fractional part of the ciphertext, thus recovering the plaintext and the error. On the other hand, if the error is too large, then this separation cannot be performed and the message is lost. The homomorphic operations are straightforward: homomorphic addition amounts to adding the two ciphertexts, whereas homomorphic multiplication amounts to multiplying the two ciphertexts. In the case of homomorphic addition, it is easy to see that, in the two ciphertexts, the message part and the error part can be treated separately. In the case of homomorphic product, the mixed terms are still in the ideal I, which means that they end up being part of the error of the output ciphertext. Naturally, all these operations yield correct results only if the final error is still small enough to allow for decryption. In particular, with this scheme, the noise is roughly doubled in case of an addition and squared in case of a multiplication. This work also introduced the concept of squashing the decryption circuit. Roughly speaking, the decryption function of the scheme was not simple enough to allow for a sufficient reduction of the noise in the bootstrapped ciphertexts. For this reason, this decryption function is replaced by a simpler one, under an additional security assumption, namely that the sparse subset sum problem (SSSS) is hard. The goal of subsequent works then became instantiating FHE from encryption schemes with simpler decryption circuits, in order to avoid this additional step and the need for additional assumptions.

Second generation FHE

Second generation FHE is mainly due to the works of Brakerski and Vaikuntanathan (BV) [BV11a; BV11b; BGV12], who constructed FHE based on standard assumptions supported by worst-case hardness, namely LWE (cf. Assumption 2.4.4). The original BV supports a message space M = {0, 1}, but can be easily extended to Z p for a sufficiently small integer p. It allows one to perform homomorphic additions and multiplications modulo two: it is easy to see that this is sufficient for building FHE, as a composition of these two operations is enough to evaluate any boolean circuit. We now present in details a public-key version of the BV scheme. Construction 3.4.1 (BV encryption scheme). This is a public-key encryption scheme that operates on bits, i.e., the message space is M = {0, 1}. Note that all the computations are done modulo q. It is composed of the following algorithms:

KGen (1 κ ) → (sk, pk, pp) : given the security parameter in unary, choose integers n = n (κ), m = m (κ), a modulus q = q (κ), and an error distribution χ = χ (κ) over the integers. Sample a vector s ←$ Z n q , and a matrix A ←$ Z m×n q . Output a secret key sk = s, and a public key pk = (-A, b = As + 2e), where e ← χ m . Also, output public parameters pp = (n, m, q), which are implicitly given as inputs to all the algorithms.

Enc (pk, µ ∈ M) → c : given a public key pk = (-A, b) and a message µ, sample r ←$ {0, 1} m and return c = (c 1 , c 2 ) = (-A r, b r + µ).
Dec (sk, c) → µ : given a secret key sk and a ciphertext c

= (c 1 , c 2 ) ∈ Z n+1 q , compute c 2 + sk, c 1 = s A r + 2e r + µ -s A r = 2e r + µ.
Return the parity of this result, i.e., return (2e r + µ) mod 2.

It is easy to see that the scheme is correct as long as 2e r < q 4 . We now detail how to perform homomorphic operations, namely additions and multiplications, with this encryption scheme.

Homomorphic addition. The homomorphic addition is trivial: let E be an instantiation of Construction 3.4.1, and let (sk, pk) ← E.KGen (1 κ ). Let c 1 = (c 11 , c 12 ) ← Enc (pk, µ 1 ) and

c 2 = (c 21 , c 22 ) ← Enc (pk, µ 2 ), for messages µ 1 , µ 2 ∈ {0, 1}. Then c + = (c 11 + c 21 , c 12 + c 22 )
is an encryption of µ 1 + µ 2 mod 2, as long as the error remains small enough.

In fact, the decryption of c + can be written as

c 12 + c 22 + sk, c 11 + sk, c 21 = • • • = 2e (r 1 + r 2 ) + (µ 1 + µ 2 ) ,
where r i is the random binary vector used for encrypting µ i . Again, the decryption will be successful if 2e (r 1 + r 2 ) < q 4 . We can immediately notice that performing an homomorphic addition increases the noise level in the output ciphertext: for this reason, the number of additions that can be evaluated is bounded a priori by the choice of the parameters for the scheme.

Homomorphic multiplication. The homomorphic multiplication is considerably trickier.

First of all, we can notice that the decryption procedure can be written as a single inner product: for a secret vector s and a ciphertext c = (c 1 , c 2 ), let ŝ := (s 1) and ĉ := (c 1 c 2 ). Then decrypting amounts to computing ŝ, ĉ and reducing modulo 2.

Next we recall the tensor (or Kronecker) product between two vectors v, w ∈ Z n q :

v ⊗ w = (v i • w j ) i,j ∈ Z n 2 q .
We also recall the mixed-product property of the tensor product: for appropriately sized vectors a,b,c,d

, a ⊗ b, c ⊗ d = a, c • b, d .
Then, it is immediate to see that the tensor product of two ciphertexts is an encryption of the product of the messages, under a different key (namely, the tensor product of the secret key with itself). In formulas:

ŝ ⊗ ŝ, ĉ1 ⊗ ĉ2 = ŝ, ĉ1 • ŝ, ĉ2 = (2 (•) + µ 1 ) • (2 (•) + µ 2 ) = 2 (•) + (µ 1 • µ 2 ) ,
where we use the symbol • to hide terms that we do not care about. In the end, the message part, i.e., the part which is not multiplied by 2, is (µ 1 • µ 2 ) as desired.

Once again, performing an homomorphic multiplication increases the noise level in the output ciphertext, so the number of multiplications that can be evaluated is bounded a priori by the choice of the parameters for the scheme.

However, the biggest problem with homomorphic multiplication is that, because of the tensor product, the size of the ciphertexts grows exponentially in the number of operations. This clearly impacts efficiency, as well as composability, meaning that the output ciphertexts are not in the same space as the input ones. In order to solve this issue, Brakerski and Vaikuntanathan [START_REF] Brakerski | Efficient Fully Homomorphic Encryption from (Standard) LWE[END_REF] propose a dimension reduction technique, which can be seen as an example of key switching; in the literature, this procedure is also referred to as relinearization. In a nutshell, by publishing an encryption of several terms in the original secret key ŝ under a different secret key t, they are able to re-linearize the ciphertext, going back from a quadratic size (roughly n 2 /2) to the original n + 1.

Modulus switching.

As we presented in the preceding part, second generation FHE ciphertexts are vectors in Z q , where q is some modulus. These ciphertexts contain a certain amount of noise for security purposes, and remain decryptable as long as the magnitude of this noise is below q/4. We also saw that homomorphic operations increase the noise level contained in ciphertexts; in particular, homomorphic addition roughly doubles the noise, while homomorphic multiplication roughly squares it. Let us say that the initial noise magnitude was B: after evaluating L multiplications, it will grow to B 2 L . In turn, this means that a very large modulus q ≈ B 2 L is required for correct decryption, thus affecting both efficiency (larger parameters mean the scheme is less efficient) and security (which is determined by the modulus-to-noise ratio). A substantial improvement came from [START_REF] Brakerski | Leveled) fully homomorphic encryption without bootstrapping[END_REF], where they proposed a modulus switching technique for better management of the noise growth. It essentially consists in scaling down the ciphertext after every multiplication by a certain scaling factor K. This means that the modulus goes from q to q/K, while the noise goes from B to B/K. Indeed, the ratio between modulus and noise remains the same, but this technique is helpful for choosing better parameters. In fact, let us consider a scaling factor K = B. After a multiplication, the noise becomes roughly B 2 , but gets scaled back down to B, together with the modulus, which becomes q/B. After L multiplications, the modulus will become q/B L , while the error will always be B. In conclusion, the condition to have decryption correctness is that the noise must be smaller than the modulus divided by 4. In this case, this means that it is sufficient to take q ≈ B L+1 , which is considerably better than having to take q ≈ B 2 L as before.

However, even if using the techniques described above helps with improving the capabilities of the scheme, homomorphic operations still increase the noise level. For this reason, the number of operations that can be evaluated remains bounded: constructing an FHE scheme (i.e., having the possibility of evaluating an unbounded number of operations) still requires using bootstrapping (cf. Section 3.3).

Third generation FHE

By "third generation FHE" we refer to a line of work initiated by Gentry, Sahai, and Waters (GSW) [START_REF] Gentry | Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based[END_REF], and prosecuted by several other works (e.g., [AP14; HAO15; KGV14]). These schemes are based on the so-called approximate eigenvector problem, and their main advantage is that they do not require any key switching for homomorphic multiplication. We now show a construction inspired by [START_REF] Gentry | Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based[END_REF], following the presentation of [START_REF] Alperin | Faster Bootstrapping with Polynomial Error[END_REF].

Gadget matrix and (randomized) binary decomposition. The first ingredient for this construction is the so-called gadget matrix, already introduced in [START_REF] Micciancio | Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller[END_REF]. Let q be a modulus, such that = log q ; then the matrix is defined as G = g ⊗ I n ∈ Z n×n q , where g = 1, 2, 4, . . . , 2 -1 is the vector of the powers of 2. The matrix G is thus a block-diagonal matrix:

G =       1 2 • • • 2 -1 0 0 • • • 0 • • • 0 0 0 0 0 0 • • • 0 1 2 • • • 2 -1 • • • 0 • • • 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 • • • 0 0 0 • • • 0 • • • 1 2 • • • 2 -1      
.

The cryptosystem. We now describe the GSW encryption scheme according to the presentation in [START_REF] Alperin | Faster Bootstrapping with Polynomial Error[END_REF]. In particular, we will focus on a secret-key version of the scheme, with message space M = Z q . The scheme is composed of the following algorithms:

KGen (1 κ ) → (sk, pp) : choose an integer n = n (κ), a modulus q = q (κ), and let = log q , and m = n . Sample a secret vector s ←$ Z n-1 q and output the secret key sk = ŝ := (s 1), and public parameters pp = (n, q). As usual, pp will be an implicit argument to all the algorithms. Enc (sk, µ ∈ M) → C : given a secret key sk and a message µ, sample a random matrix A ←$ Z

(n-1)×m q

, an error vector e ← χ m for some error distribution χ, and output

C = -A s A + e + µG ∈ Z n×m q .
Dec (sk, C) → µ : given a secret key sk and a ciphertext C, compute

sk C = ŝ -A s A + e + µG = e + µ ŝ G,
and return µ , the closest integer to ŝ G.

Condition for correct decryption. In order for the decryption procedure to return the correct value, it is necessary that the error is small enough, so that it does not perturb the final result. In particular, it is easy to imagine the space Z q divided into several segments, with each one corresponding to a possible plaintext value. The absolute value of the error will then have to be smaller than half the width of each segment. In conclusion, it must hold that e ∞ < q 2 |M| .

Notice that for M = {0, 1}, we recover the well-known condition e ∞ < q 4 . Extension to public-key setting. It is easy to turn the secret-key encryption scheme presented above into a public-key one. The main idea is that the LWE matrix that plays the role of the mask will be the public key; for encrypting, one will first re-randomize this public key by multiplying it by a random matrix with small entries, and then proceed as before. The decryption will work exactly like in the secret-key case. We now give the details of the public-key version of the GSW cryptosystem.

KGen (1 κ ) → (sk, pk, pp) : choose an integer n = n (κ), a modulus q = q (κ), and let = log q , and m = n . Sample a secret vector s ←$ Z n-1 q , a matrix A ←$ Z

(n-1)×m q , an error vector e ← χ m for some error distribution χ, and output the secret key sk = ŝ := (s 1), the public key pk = -A s A + e , and public parameters pp = (n, q).

As usual, pp will be an implicit argument to all the algorithms.

Enc (pk, µ ∈ M) → C : given a public key pk and a message µ, sample a random matrix R ←$ {0, 1} m×m , and output

C = -A s A + e R + µG ∈ Z n×m q .
Dec (sk, C) → µ : given a secret key sk and a ciphertext C, compute

sk C = ŝ -A s A + e R + µG = e R + µ ŝ G,
and return µ , the closest integer to ŝ G.

We now turn to homomorphic operations. In particular, we will describe how to perform addition and multiplication with encrypted inputs, which allow for the evaluation of any function.

Homomorphic addition. The homomorphic addition is trivial: given a ciphertext C 1 that encrypts a message µ 1 , and a ciphertext C 2 that encrypts a message µ 2 , the ciphertext

C + := C 1 + C 2 is an encryption of µ 1 + µ 2 (
provided that the errors in the input ciphertexts are not too big). In fact,

ŝ C + = ŝ (C 1 + C 2 ) = (e 1 + e 2 ) + (µ 1 + µ 2 ) ŝ G,
and one can recover µ 1 + µ 2 by rounding as before.

Noise growth formula for homomorphic addition. Although it is immediate, we report here for completeness the noise growth formula for the homomorphic addition of two GSW ciphertexts: given a common secret key sk, and two GSW ciphertexts C 1 , C 2 ∈ Z n×m q , such that C i is an encryption under sk of a message µ i with error vector e i , the error vector contained in

C + := C 1 + C 2 is e out = e 1 + e 2 .
This means that, for the GSW cryptosystem, the error in homomorphic additions is additive.

The G -1 (•) algorithm. Before describing the homomorphic multiplication, we introduce a key part of this construction, which is the

G -1 (•) algorithm. Let := log q , then G -1 (•) : Z n q → {0, 1} n is a deterministic algorithm defined as follows: G -1 (x) = y ⇐⇒ Gy = x, ∀x ∈ Z n q .
In a nutshell, G -1 (x) is simply the binary decomposition of x. In the literature, there exists also a randomized version of this algorithm, which will be extremely important in Chapter 5 and will be introduced there. A key feature of the G -1 (•) algorithm is that its output is a vector with small entries, whether they be binary or slightly larger (as will be the case in Chapter 5).

Note that, given a matrix M ∈ Z r×c q , when we write N = G -1 (M) ∈ {0, 1} r ×c , we mean that the G -1 (•) algorithm is applied independently to all the columns of M, and the resulting vectors are the columns of N. Homomorphic multiplication. The homomorphic multiplication is, once again, the tricky

part. Given a ciphertext C 1 = -A 1 s A 1 + e 1 + µ 1 G that encrypts a message µ 1 , and a ciphertext C 2 = -A 2 s A 2 + e 2
+ µ 2 G that encrypts a message µ 2 , then

C × = C 1 • G -1 (C 2 ) (3.4) is an encryption of µ 1 • µ 2 .
Verifying this fact is straightforward:

C 1 • G -1 (C 2 ) = -A 1 G -1 (C 2 ) s A 1 G -1 (C 2 ) + e 1 G -1 (C 2 ) + µ 1 -A 2 s A 2 + e 2 + µ 1 µ 2 G
This can be rewritten as

C 1 • G -1 (C 2 ) = -A * s A * + e * + µ 1 µ 2 G, where A * = A 1 G -1 (C 2 ) + µ 1 A 2 , and e * = e 1 G -1 (C 2 ) + µ 1 e 2 .
It is trivial to see that this decrypts to µ 1 µ 2 , as long as the new error is small enough.

Noise growth formula for homomorphic multiplication. We report here the analytical noise growth formula for a GSW multiplication: given a common secret key sk, and two GSW ciphertexts C 1 , C 2 ∈ Z n×m q , such that C i is an encryption under sk of a message µ i with error vector e i , the error vector contained in

C 1 • G -1 (C 2 ) is e out = e 1 G -1 (C 2 ) + µ 1 e 2 .
(3.5)

Remark 3.4.2. An important feature of this encryption scheme is the fact that its noise growth for homomorphic multiplication is asymmetric, i.e., it depends on the order of the operands. In fact, the second noise vector is multiplied as it is by the first message, while the first noise vector is multiplied by the second ciphertext, but after applying the G -1 (•) operation, which ensures the output is small. With this in mind, one can notice that also

C 2 • G -1 (C 1 )

Message packing

One of the most evident downsides of the GSW encryption scheme is its expansion factor when encrypting, meaning the ratio between the size of a ciphertext and the size of the plaintext. For example, with reasonable parameters, this problem can be as bad as requiring almost 1 Gbit to encrypt a single bit2 ! A work by Hiromasa et al. [START_REF] Hiromasa | Packing Messages and Optimizing Bootstrapping in GSW-FHE[END_REF] exploits the redundancy in the ciphertexts, and manages to amortize the size of an encryption by packing several messages in the same ciphertext. In particular, r plaintexts can be encrypted in a matrix of size (r + n)×(r + n) log q, which takes (r + n) 2 log 2 q bits of storage. This is a clear improvement on naively encrypting r plaintexts separately, which would take r • n 2 log 2 q bits of storage.

Advanced constructions

Although FHE has gained momentum only recently (the first construction having been proposed in 2009), a lot of research effort has been put on this topic, because of its novelty, the number of open questions, the vast number of results that can be achieved through FHE, and the important consequences that practical instantiations would have on people's lives. Apart from "basic" FHE schemes, where the operations are encryption, decryption, and circuit evaluation, some more advanced constructions have been proposed. Analyzing each of them in detail would require far too much space, and it is beyond the scope of this chapter. However, we quickly and informally introduce some interesting topics that FHE has been applied to, and we refer the interested reader to the referenced material for more details.

Threshold FHE A threshold FHE scheme with N parties is essentially an FHE scheme where key generation and decryption are no longer algorithms but N -party protocols. The basic idea is that, at the beginning, the parties engage in a multi-party computation (MPC) protocol that produces a common public key pk, a common evaluation key evk, and gives each party P i a share sk i of the secret key sk. Then, each party can encrypt its input x i under the common pk, and all the parties can independently and homomorphically evaluate a function f on these ciphertext3 . Finally the parties engage in another MPC protocol where each party participates with his share of the secret key sk i and in the end receives the result µ = f (x 1 , . . . , x N ). For more details on the topic, we refer the reader to e.g., [AJL+12; JRS17].

Multi-key FHE This primitive was introduced in [LTV12]

, with improved constructions later given e.g., in [CM15; MW16]. The basic idea is essentially to enable homomorphic computations over data encrypted under different keys. More in details, each party individually encrypts its input under its key, then broadcasts the ciphertext. Next, all the parties can homomorphically compute a multi-key encryption of the output, that, however, cannot be decrypted under any of the secret keys. Finally, the parties broadcast a partial decryption of the output obtained with their secret keys; these partial decryptions can be combined together in order to recover the output itself.

Fully homomorphic signatures

The basic idea of this primitive, proposed by Gorbunov et al. in [START_REF] Gorbunov | Leveled Fully Homomorphic Signatures from Standard Lattices[END_REF] is as follows. A signer signs some initial data x under its public key, and produces a signature σ x . Then, an untrusted party that only knows the public key, x, and σ x (but not the secret signing key), can apply an arbitrary function f to

x, and compute a corresponding signature σ f (x) for the value f (x). Finally, a verifier that is given the public key, f , f (x), and σ f (x) (but not x), can verify that f (x) is indeed the output of f applied to the input x that was signed at the beginning.

Libraries and practical implementations

Beside theoretical research, the field of homomorphic encryption has been strongly active with respect to implementation efforts. In fact, given the strongly applied nature of this sort of constructions, it is appropriate that the development of new mathematical techniques and theoretical breakthrough proceeds hand in hand with top quality implementation. On one hand, this contributes to assessing where we actually stand and how far the goal of practically usable homomorphic encryption is. On the other hand, this also helps pinpointing the limitations and the main difficulties still remaining, therefore suggesting to researchers and theoreticians where to concentrate their efforts. Although several implementations have been released over the years by numerous authors, via means like GitHub, we will consider only a few of them, in order to give a broad idea on the current state of the art on this matter. For more information about efforts to standardize and implement FHE, we refer the reader to [org].

In particular, in this section, we will focus on HElib [HS14a; HS14b; HS15], SEAL [START_REF] Hao Chen | Simple Encrypted Arithmetic Library (SEAL)[END_REF], and TFHE [CGGI16b; CGGI17; CGGI16a].

HElib. This library, authored mainly by Shai Halevi and Victor Shoup, implements the BGV scheme [START_REF] Brakerski | Leveled) fully homomorphic encryption without bootstrapping[END_REF] (which can be put in the category of "2nd generation FHE") and it is one of the most widely used libraries in applications. It allows for packing of ciphertexts and SIMD computations, amortizing the cost for certain tasks. It is able to perform additions and multiplications in an efficient way, but the bootstrapping operation is significantly slow. In practice, this library is often used as a somewhat homomorphic encryption scheme. One of the drawbacks of this library regards the parameter selection, which remains a complicated and error-prone operation. In fact, in [HS15, Appendix A], the authors note that "The BGV implementation in HElib relies on a myriad of parameters, some of which are heuristically chosen, and so it takes some experimentation to set them all so as to get a working implementation with good performance". SEAL. This library is written in C ++ 11 and implements the FV encryption scheme [START_REF] Fan | Somewhat Practical Fully Homomorphic Encryption[END_REF]. It should be noted that this scheme is already implemented in [BEHZ16; Lep16], both of which use the ideal lattice library NFLlib [START_REF] Aguilar Melchor | NFLlib: NTT-Based Fast Lattice Library[END_REF]. Unlike in HElib, with the SEAL library it is considerably easier to set good parameters for the performance and the security of the implemented scheme. TFHE. This library implements a generalized version of the GSW encryption scheme [GSW13; AP14], and thus belongs to the category of "3rd generation FHE". The library features a very efficient operation bootstrapping, with timings that are in the order of fractions of a second on average machines. As a downside, this bootstrapping operation has to be applied after computing every gate of the circuit. When used for realizing an FHE scheme, this library is more efficient than HElib. However, for simple tasks requiring small computational depth, HElib used as a somewhat homomorphic encryption scheme will generally perform better. Moreover, TFHE is currently not capable of amortizing large SIMD computations as well as HElib does. However, it should be noted that the code of TFHE is still largely under development, and more features (e.g., multithreading) are likely to be added soon. TFHE will be at the core of our construction in Chapter 4. Therefore, it will be analyzed more in details there.

FHE constructions from non-lattice assumptions

For completeness, we also mention that there are other constructions of fully homomorphic encryption schemes which are not based on lattice assumptions. This line of work is usually referred to as FHE over the integers. Notably, this is the case for the DGHV scheme [DGHV10; CMNT11; CCK+13; NK15], which relies on the assumed hardness of the approximate GCD problem (cf. Definition 2.4.6). The DGHV scheme is central in the constructions presented in Chapter 6, so we refer the reader to this chapter for its presentation and the details on this instantiation of FHE.

Chapter 4

Chapter 4

Homomorphic evaluation of deep neural networks

In this chapter we address the challenge of homomorphically and efficiently evaluating a (deep) neural network. First, we give an introduction to the problem and some potential applications; then, we provide some necessary background notions on neural networks and we review the current state of the art for privacy-preserving evaluation of these models. We then move on to presenting a fast framework for FHE and bootstrapping by Chillotti et al. [START_REF] Chillotti | Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds[END_REF][START_REF] Chillotti | Faster Packed Homomorphic Operations and Efficient Circuit Bootstrapping for TFHE[END_REF], which will be central in our constructions. Finally, we present our contributions, explain in details our framework FHE-DiNN, and give some encouraging experimental results obtained on a typical dataset.

Introduction to the problem

Machine Learning As a Service (MLAS) refers to a cluster of applications where a remote entity provides a service that can be accessed through the Internet and that takes advantage of some machine learning algorithm to provide a result to the users' queries. This type of applications is becoming more and more popular because of its versatility and the impressive performance (e.g., better-than-human accuracies) that can be achieved.

A typical use-case involves a user (client) and a remote service (server), with the client uploading some data to the server, which runs some predictive model on it and returns some answer to the client. For a more concrete example, let us consider the following situation: Alice is a user who would like to assess her medical condition through an online diagnosis service1 . In order to do so, she connects to a remote server, that we will call RemoteDoc, uploads her medical data and fills in some form where she answers several questions about her lifestyle and her habits. Then, RemoteDoc processes this information and, based on an archive of past diagnosis that was used for training some predictive model, returns an evaluation on Alice's situation. Optionally, RemoteDoc charges Alice with a fee for using the service. It is easy to see that this model of interaction might have tremendous consequences on Alice's privacy: the data she submits is likely to contain extremely sensitive information, that she does not want to disclose. Note that here we are not concerned about an external intruder, since we can safely assume that the channel through which Alice and RemoteDoc communicate is secure (e.g., via HTTPS); in this case, the problem is represented by disclosing private information to RemoteDoc itself. In this situation, there seems to be an unsolvable conflict: on one hand, Alice wants to keep her medical information private, while on the other hand she wants to obtain a reliable diagnosis, that necessarily has to be based on true data and honest answers.

Of course, a trivial solution would be that of evaluating RemoteDoc's predictive model locally on Alice's machine. We assume this is either infeasible (because of high computational or storage requirements) or forbidden (because the model is considered as sensitive intellectual property, or because the remote server wants to charge the user with a fee per every request) and we focus on the situation where the evaluation has to take place remotely, i.e., on RemoteDoc's side. Homomorphic encryption offers an elegant way to solve this apparent paradox, by allowing Alice to submit encrypted data which is then blindly processed by RemoteDoc; the encrypted result (i.e., the encrypted diagnosis) is then sent back to Alice, who proceeds to decrypting and recovering the result. This way, the evaluation takes place on the server side and still RemoteDoc learns nothing on Alice's medical data, since all it sees is encryptions produced with a secret key that never leaves Alice's controlled domain. Another bonus of using homomorphic encryption is that it achieves non-interactivity: Alice submits an input and later receives an output, without the need for any additional communications between her and the remote party.

The "predictive models" we are referring to are often neural networks, which are trained on pairs consisting of some input and the expected output, and then evaluated on some fresh input (i.e., an input that has possibly never been seen before) to obtain a predicted output.

We are then interested in designing an efficient framework for evaluating arbitrarily complex neural networks over encrypted data.

Refresher on neural networks

Neural networks are the second best way of doing just about anything.

-John Denker

In this section we give some necessary background notions on neural networks.

Basic definitions

Giving a proper, formal definition of a neural network is not an easy task and the literature contains several attempts at doing so. For example, we can consider the following: Definition 4.2.1 (Artificial neural network). An artificial neural network (ANN, or simply NN) is a computing system that attempts to identify underlying relationships in a set of data, by mimicking the way a biological brain works. It is composed of a population of (artificial) neurons arranged in layers that process information (inputs, which can be seen as stimuli) coming from the external world.

We now proceed to giving a necessary mathematical background on NNs, and how they are trained and evaluated.

Computation performed by a neuron. Each neuron of which a NN is composed accepts n I real-valued inputs x = (x 1 , . . . , x n I ) ∈ R n I and performs the following two computations:

1. It computes a value y = n I i=1 w i x i + β ∈ R, which is a weighted sum of the inputs with real values called weights (w i is the weight associated to the input x i ), and β ∈ R, which is referred to as the bias of the neuron;

It applies a non-linear function f , called the activation function, and returns f (y).

A neuron's output can conveniently be written as f ( w, x ) = n I i=0 w i x i if one extends the inputs and the neuron's weight vectors by setting w = (β, w 1 , . . . , w n I ) and x = (1, x 1 , . . . , x n I ). In the following, we will use W = (w ,1 , . . . , w ,n 2 ) to denote the n 1 × n 2 matrix composed of all the weights associated to the connections that go from layer -1 (containing n 1 neurons) to layer (containing n 2 neurons). The vectors w ,i 's will contain the weights associated to the i-th neuron of the -th layer. When computing the output given by the network when presented with an input pattern x, we will usually write N (x).

Neural networks could in principle be recurrent systems (see, e.g., [Hop88; Jor89; Elm90]), as opposed to the purely feed-forward ones, where each neuron is evaluated only once. In this work, we consider only feed-forward networks, as they are more widely used, easier to understand, and simpler to evaluate homomorphically.

Neural networks' layers

The neurons of a NN are organized in successive layers, which are categorized according to their activation function. Neurons of one layer are connected to the neurons of the next layer by paths that are associated to weights. An input layer composed of the network's inputs, as well as an output layer made of the network's output values, are also added to the network. Internal layers are called hidden, since they are not directly accessible from the external world. Neural networks are usually composed of layers of various types. The "fusion" of diverse building blocks helps unlocking the full potential of neural networks, while keeping their size reasonable. We now provide a short description of the most widely used layer types:

Fully connected layer: in this kind of layer, every neuron takes all incoming signals as inputs.

Convolutional layer: this layer's learnable parameters consist of (a set of) small filters, called kernels, which are nothing more than a small matrix of values. The layer's output is then computed by "sliding" these matrices along the layer's input and computing the dot product between the input and the kernel. In Figure 4.1 we show an example of this computation. Note that this kind of layer can reduce the size of the data, depending on how the borders are handled (e.g., one could cut them, or pad them with zeros, or adopt other strategies). Mean pooling layer: this layer is similar to the max pooling one, except that it takes the average of the values instead of their max. Just like the previous kind of layer, it reduces the size of the data.

Max pooling layer

Activation functions

A key ingredient for the construction of an effective neural network is the choice of a neuron's activation function. This essentially determines how the neuron reacts to the inputs and what kind of information it forwards to the following layers. Roughly speaking, it serves as a mean to highlight some characteristics of the data over some others: for example, we might be interested in just separating positive values from negative ones (sign function), or we might want to give importance to whether the value's magnitude exceeds a certain threshold or not (function with a saturation point), and so forth. Several activation functions have been studied and used in the literature: we now list some of them and try to briefly outline some of their features.

Step: for any input x ∈ R, this function is 0 if x < 0 and +1 if x ≥ 0. It only discriminates between positive and negative values, completely disregarding their magnitudes.

It presents an inherent problem, which is the fact that its derivative is zero almost everywhere. The reason why this represents a problem will be clear in Section 4.2.5, when we will outline a classical method for training a neural network.

Sign: for any input x ∈ R, this function is -1 if x < 0 and +1 if x ≥ 0. It is very similar to the step function, with the exception that negative values here do give a contribution, which is the opposite of that given by positive values. Like the previous one, its derivative is zero almost everywhere.

Sigmoid (or logistic): for any input x ∈ R, this function is defined as

f (x) = 1 1 + e -x = e x e x + 1
.

It is continuous, bounded in the range (0, 1), differentiable, and has a non-negative derivative at each point. This function can be seen as a continuous approximation of the step function.

Hyperbolic tangent: for any input x ∈ R, this function is defined as

f (x) = tanh(x) = e x -e -x e x + e -x = e 2x -1 e 2x + 1 .
It is continuous, bounded in the range (-1, 1), differentiable, and has a non-negative derivative at each point. This function can be seen as a continuous approximation of the sign function.

Arctangent: for any input x ∈ R, this function is defined as f (x) = arctan(x). It is continuous, bounded in the rangeπ 2 , π 2 , differentiable, and has a non-negative derivative at each point. This function can be seen as a scaled continuous approximation of the step function.

Square: for any input x ∈ R, this function is defined as f (x) = x 2 . Although less common than other functions, it has been employed, e.g., in [START_REF] Dowlin | CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy[END_REF]. It is continuous, nonnegative, differentiable, and even (i.e., f (-x) = f (x)∀x ∈ R). This function ignores the sign of the input and only considers its magnitude. An important thing to remember when using this function (and especially when implementing neural networks in software) is that it is unbounded, thus applying it multiple times without any form of rescaling or data normalization can quickly increase the values and produce overflows.

Softmax: this is a special kind of activation function since, unlike the previous ones, it is not defined on a single value but on a vector of values. It can be seen as a generalization of the logistic function, and it maps a vector x ∈ R d to a vector softmax (x) ∈ (0, 1) d , such that its values add up to 1. Formally, given a vector

x = (x 1 , . . . , x d ) ∈ R d , this function is defined as softmax (x) i = e x i d j=1 e x j .
softmax is often used in multiclass classification problems, i.e., when the goal is to classify input patterns into one of N C classes (with N C ≥ 3), and has the effect of converting "scores" into probabilities, while having no effect on the ordering of the values. Also, given the presence of the exponential function, it has the effect of "spreading" the outputs, by assigning high probabilities to the heaviest values and separating them from the others. Given these features, it is mostly used for the output layer of a neural network, when the goal is to output the probability that the pattern belongs to class

C i , for i ∈ [N C ].
Some commonly used activation functions are plotted in Figure 4.2.

Perceptrons, multilayer perceptrons, and deep NNs

Historically, one of the first results towards building neural networks was the perceptron, introduced by Frank Rosenblatt [START_REF] Rosenblatt | The Perceptron, a Perceiving and Recognizing Automaton Project Para[END_REF]. A perceptron is essentially a neural network composed solely of an input layer and an output layer, i.e., without any hidden layer. Rosenblatt proved that a perceptron converges to the correct solution in a finite number of steps, provided that a correct solution exists. However, the perceptron model is greatly limited by the fact that it can learn only linearly separable functions so, for example, it can learn the AND and the OR function, but not the XOR. Also, this limitation makes it useless for classification problems with three or more classes. Decisive progress in the field of machine learning was made with the introduction of the multilayer perceptron, i.e., a neural network with at least one hidden layer. A famous result, known as the universal approximation theorem (see, e.g., [START_REF] Cybenko | Approximation by superpositions of a sigmoidal function[END_REF][START_REF] Hornik | Approximation Capabilities of Multilayer Feedforward Networks[END_REF]), states the following: Theorem 4.2.2 (Universal approximation theorem (informal)). A neural network with a single hidden layer that contains a finite amount of neurons can approximate any continuous function.

It is then clear that neural networks have a huge potential, but this theorem does not specify precisely how many neurons there must be in the single hidden layer of the network. It turns out that, for complex function, this quantity can grow exponentially and quickly make the problem of training and evaluating the model infeasible.

Deep neural networks.

A way to solve this issue is represented by deep neural networks (deep NNs), i.e., neural networks that comprise several hidden layers stacked one on top of the other (for a visual example, see Figure 4.3). These layers of non-linearities allow the network to extract increasingly complex features of the input patterns and can lead to a better ability to generalize (i.e., to learn the underlying structures and relationships in the dataset), especially in the case of more complex tasks.

The term "deep learning" was introduced to the machine learning community in 1986, and to artificial neural networks in 2000, but it was only starting from 2006 that, mainly thanks to the works of Hinton and Salakhutdinov (e.g., [START_REF] Hinton | Reducing the Dimensionality of Data with Neural Networks[END_REF]), this area became a prominent field of research. More specifically, Salakhutdinov (advised by Hinton) has the merit of shifting the computationally intense process of training a deep network from a CPU to a GPU, thus taking advantage of the large number of cores available on these boards and, in turn, fostering the development of specifically designed hardware for machine learning. From that moment, deep learning has been applied with impressive results to a vast number of problems: from speech recognition (e.g., [HDY+12; Rav17; ZPB+17]), to image classification (see e.g., [LBBH98; Kag]), from adding colors to black & white images (e.g., [START_REF] Avni | Two Weeks of Colorizebot -Conclusions and Statistics[END_REF]), to even creating new astonishing works of art (e.g., [START_REF] Mordvintsev | DeepDream -A code example for visualizing Neural Networks[END_REF][START_REF] Mordvintsev | Inceptionism: Going Deeper into Neural Networks[END_REF]). The potential of deep learning is considered enormous, and new applications surface regularly, with active research still happening in the field.

Training and evaluating neural networks

In this section we give an overview of the algorithms for training and evaluating a neural network, i.e., we explain how to construct a model from a training set and later evaluate its performance on a test set.

The way a neural networks extracts (or approximates) the underlying relationships in a set of data is by learning. This means that the network is presented with several examples, i.e., several input patterns and the corresponding expected outputs, and learns a mapping from the input space to the output space. It is worth noting that this goes well beyond the simple storage and successive retrieval of information. In other words, the networks does not (or, at least, should not) learn the example "by heart", but it should be able to generalize, i.e., extract general relationships that pertain to the data and not to the specific . . . . . . . . . examples. In fact, once trained, the network should be able to give correct answers even when presented with input patterns that were not used during the training phase. It is simple to see an analogy with the way a human brains evolves during the course of a person's life: through examples and by experiencing different situations, it learns how to behave and how to respond to new stimuli.

For a neural network, we can distinguish between supervised and unsupervised learning: in the first case, the network is given a set of pairs composed of an input and an expected output, whereas in the second case, the network is only given input patterns and has to organize itself in order to infer a function that describes hidden structures in the data. In this work, we will focus exclusively on supervised learning.

Error (or cost) function. Given a neural network, we can define a function L ( y, y) that measures some notion of error between the expected output y and the actual network's output y. This function is sometimes referred to as the cost function or the loss function. Choosing an appropriate loss function is extremely important, as this defines the quantity that the training phase will try to minimize. We now present some typical loss functions that can be used when training a neural network; in the following, N indicates the number of training samples, i.e., the number of pairs (input, expectedOutput) in the training set.

L 1 : this is one of the simplest loss functions, and it simply measures how far the predicted value is from the correct one:

L 1 ( y, y) = N i=1 | y i -y i | L 2 :
similar to the previous one, but this time the differences are squared:

L 2 ( y, y) = N i=1 ( y i -y i ) 2
Mean Squared Error (MSE): similar to the previous one, but this time the value is averaged on the training set:

MSE ( y, y) = 1 N N i=1 ( y i -y i ) 2
0/1-loss: this function gives a simple hit-or-miss measurement of the loss:

L ( y i , y i ) = 0, y i = y i 1, y i = y i ∀i ∈ [N ]
Cross-entropy (or log loss): this is one of the most well known and widely used cost functions in the machine learning field. It measures the performance of a classification model whose output is a probability value between 0 and 1.

L ( y, y) = - N i=1 y i log (y i )
Once an appropriate loss function has been chosen (perhaps through trial-and-error), it is possible to proceed with the real training. Here is an high-level overview of the procedure:

1. Present an input pattern x to the network; 2. Calculate the network output y = N (x) by feeding x forward and performing all the computations until the output layer;

3. Compute the loss L ( y, y);

4. Modify the weights of the network in order to reduce the error;

5. Repeat for all the samples in the training set.

Clearly, Item 4 is the key one, and the obvious question is how to modify the network parameters in order to reduce the loss. Roughly speaking, the answer is that the weights have to be moved in the direction opposed to that of the gradient of the loss function, calculated with respect to the weights. In fact, the final goal is to find a set of weights that minimize the loss. In Algorithm 1 we show a basic and unoptimized version of the gradient descent algorithm. It is easy to see that this procedure is rather inefficient: in fact, it needs to process all the N training samples before updating the weights; in other words, the weights are updated only M times, where M is the number of iterations of the algorithm, usually called epochs.

An alternative approach is that of updating the weights after each training sample. This technique goes by the name of stochastic gradient descent (SGD) and it is a method for approximating the "true" gradient by the gradient at a single training sample. This way, the weights are updated in a "less precise", heuristic way, but more frequently. This method is also used for the so-called online learning, i.e., when new training samples keep coming in, and they are used to continuously "update" the network.

A trade-off between these extremes is the batched gradient descent: in this case, the training set is divided into a number of batches (the size of which becomes a parameter for the training), and the weights are updated after processing each batch. This method offers a good compromise between the accuracy of the gradient computation and the speed of convergence of the procedure, making it widely used for training neural networks.

Several optimizations are possible: learning rate decay, weight regularization, data normalization, SGD with momentum, . . . . These enhancements are extremely useful for training effective networks and can often improve the results dramatically. For an exhaustive review on this topic, we refer the interested reader to one of the many resources available in the machine learning literature. for all i ∈ [N ] do 3:

compute y i = N (x i ) by feeding x forward through the network

4:
compute the loss L ( y i , y i ) update the weights by setting

W j = W j -ε • ∆W j N 12:
end for 13: end for

MNIST: a typical dataset for NNs

A classical problem for neural networks is that of image classification, i.e., classifying images based on what they depict. In particular, a well studied problem in the machine learning literature is that of digit recognition. The MNIST (Modified National Institute of Standards and Technology) dataset contains images representing digits that have been handwritten by more than 500 different writers, and is commonly used as a benchmark for machine learning systems [START_REF] Lecun | Gradient-Based Learning Applied to Document Recognition[END_REF]. It contains 60000 training images (i.e., used for building, or training, the model) and 10000 testing images (i.e., used for evaluating the model's performance). In Figure 4.4 we show, as an example, some of the images that compose the MNIST dataset. The format of the images is 28 × 28 and the value of each pixel represents an 8-bit level of gray. Moreover, each image is labeled with the digit is depicts; this serves both during the training phase for "telling the network" which is the expected output, and during the testing phase for verifying if the classification was correct or not. A typical neural network for the MNIST dataset has 28 • 28 = 784 input nodes (one per pixel), an arbitrary number of hidden layers, each of which is composed of an arbitrary number of neurons, and finally Over the years, the MNIST dataset has been a typical benchmark for classifiers, and many approaches have been applied: linear classifiers, principal component analysis, support vector machines, neural networks, convolutional neural networks, etc. For a more complete review of these approaches, we refer the reader to, e.g., [START_REF] Lecun | Gradient-Based Learning Applied to Document Recognition[END_REF]. Neural networks are known to perform well on this dataset. For example, [START_REF] Lecun | Gradient-Based Learning Applied to Document Recognition[END_REF] proposes different architectures for neural networks and obtains more than 97% of correct classifications. More recent works even surpassed 99% of accuracy [START_REF] Cireşan | Multi-column Deep Neural Networks for Image Classification[END_REF]. For a nice overview on the results obtained on this dataset and on the techniques that were used, we refer the reader to [START_REF] Lecun | THE MNIST DATABASE of handwritten digits[END_REF].

State of the art for privacy-preserving predictions

We now turn to the problem of homomorphically making predictions on input data. In a nutshell, given a model N , the goal is to take an encryption of an input pattern Enc (x) and return an encrypted answer c such that Dec (c) = N (x), i.e., the evaluation of the model N on the input x. This problem has already been addressed in the past, mainly via multiparty computation (MPC), Yao's garbled circuits [START_REF] Andrew | How to Generate and Exchange Secrets (Extended Abstract)[END_REF], and homomorphic encryption (see, e.g., [START_REF] Bost | Machine Learning Classification over Encrypted Data[END_REF], SecureML [START_REF] Mohassel | SecureML: A System for Scalable Privacy-Preserving Machine Learning[END_REF], PICS [START_REF] Makri | PICS: Private Image Classification with SVM[END_REF], MiniONN [START_REF] Liu | Oblivious Neural Network Predictions via MiniONN Transformations[END_REF], DeepSecure [START_REF] Bita Darvish Rouhani | DeepSecure: Scalable Provably-Secure Deep Learning[END_REF], Gazelle [START_REF] Juvekar | Gazelle: A Low Latency Framework for Secure Neural Network Inference[END_REF]). In the case of MPC, a possible architecture is the following: a party A holds the input data x, a party B holds the trained model N , and they engage in a protocol that, through several round of interactions, allows A to obtain N (x). The main drawback of this approach is essentially that it requires interactivity between the parties, meaning that there are several points in time where the client A is involved in the protocol, as opposed to a simpler case where A sends the input and later receives the output. Even though practical performances of MPC-based solutions have largely surpassed those of FHE-based solutions, they incur issues like network latencies and high bandwidth usage. Because of these downsides, FHE-based solutions appear more scalable for real-life applications, even though MPC-based solutions might be faster for specific instantiations.

As far as FHE-based solutions are concerned, Cryptonets [START_REF] Dowlin | CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy[END_REF] was the first initiative to address the challenge of achieving blind, non-interactive classification. The main idea consists in applying a leveled somewhat homomorphic encryption scheme such as BGV [START_REF] Brakerski | Leveled) fully homomorphic encryption without bootstrapping[END_REF] to the network inputs and propagating the signals across the network homomorphically, thereby consuming levels of homomorphic evaluation whenever non-linearities are met. We remind the reader that, in neural networks, non-linearities come from activation functions which are usually picked from a small set of non-linear functions of reference (logistic sigmoid, hyperbolic tangent, . . . ) chosen for their mathematical convenience. To optimally accommodate the underlying SHE scheme, Cryptonets replace their standard activation by the (depth 1) square function, which only consumes one level of homomorphic multiplication but does not resemble the typical sigmoidal shape. A number of subsequent works have followed the same approach and improved it, typically by adopting higher degree polynomials as activation functions for more training stability [START_REF] Zhang | Privacy Preserving Deep Computation Model on Cloud for Big Data Feature Learning[END_REF], or by renormalizing weighted sums prior to applying the approximate function, so that its degree can be kept as low as possible [START_REF] Chabanne | Privacy-Preserving Classification on Deep Neural Network[END_REF]. Practical experiments have shown that training can accommodate approximated activations and generate NNs with very good accuracy.

However, this approach suffers from an inherent limitation: the homomorphic computation, local to a single neuron, depends on the total number of levels required to implement the network, which is itself roughly proportional to the number of its activated layers. Therefore, the overall performance of the homomorphic classification heavily depends on the total multiplicative depth of the circuit and rapidly becomes prohibitive as the number of layers increases. This approach does not scale well and is not adapted to deep neural networks, that can contain tens, hundreds or sometimes thousands of layers [HZRS15; ZK16].

TFHE: a framework for efficient bootstrapping

In 2016, Chillotti et al. proposed a framework [START_REF] Chillotti | Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds[END_REF] (later refined in [START_REF] Chillotti | Faster Packed Homomorphic Operations and Efficient Circuit Bootstrapping for TFHE[END_REF]) that improved dramatically the performances of FHE and, particularly, those of the bootstrapping operation. These works propose an alternative -although equivalent to the traditional one3 -representation of the LWE problem (cf. Section 2.3.6) over the torus (i.e., the reals modulo 1) and feature an improved bootstrapping procedure that is considerably more efficient than the previous state of the art. In the following, we review some of the contributions introduced by these works, that will be of key importance for our constructions. For all the details, we refer the reader to [CGGI16b; CGGI17].

LWE over the torus and related constructions

In this section we present the formulation of the LWE problem over the torus, and we introduce related constructions that will be used in the rest of this chapter.

LWE over the torus. First, we provide a definition of the LWE problem [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] over the torus T = R/Z. Definition 4.4.1 (LWE over the torus). Let n be a positive integer and χ be a probability distribution over R for the noise. For any vector s ∈ {0, 1} n , the LWE distribution lwe s,χ over T n × T is sampled by picking a ←$ T n , an error e ← χ, and returning (a, b = s, a + e). Then the LWE assumption states that, for some fixed s ∈ {0, 1} n , it is hard to distinguish between (a, b) ← lwe s,χ and (u, v) ←$ T n+1 .

From now on, when mentioning the LWE problem, we will refer to this formulation over the torus. T N [X] (k+1) ×(k+1) be as in Equation (4.1). We say that Dec H,β,ε (v) is a decomposition algorithm on the gadget H with quality β and precision ε if and only if for any TLWE sample v ∈ T N [X] k+1 , it publicly and efficiently outputs a small vector u ∈ R As already stated, the biggest limitation of using a somewhat homomorphic encryption scheme and then evaluating non-linear activation functions is that the overall efficiency of the scheme depends on the total multiplicative depth that is needed to evaluate the entire neural network. This way, choosing the parameters for the scheme quickly becomes prohibitive as the depth of the network increases.

(k+1) such that u ∞ ≤ β and u • H -v ∞ ≤ ε. Furthermore, the expectation of u • H -v must be 0 when v is uniformly distributed in T N [X] k+1 . H =               1/B g • • • 0 . . . . . . . . . 1/B g • • • 0 . . . . . . . . . 0 • • • 1/B g . . . . . . . . . 0 • • • 1/B g               ∈ T N [X] (k+1) ×(k+1) . ( 4
Instead, we propose a scale-invariant approach to the problem, i.e., each neuron's output is refreshed through bootstrapping, resulting in that arbitrarily deep networks can be homomorphically evaluated. Of course, the entire homomorphic evaluation of the network will still take time proportional to the number of its neurons or, if parallelism is involved, to the number of its layers. However, evaluating one neuron is now essentially independent of the dimensions of the network: it just relies on system-wide parameters.

We start by proposing a new model of neural network, which is designed to be FHEfriendly, and we explain the procedure to homomorphically evaluate it on encrypted inputs; finally, we present some improvements on the TFHE framework and show experimental results obtained on the MNIST dataset.

Definition of a discretized neural network

First of all, we recall that state-of-the-art fully homomorphic encryption schemes cannot support operations over real messages. Traditional neural networks have real-valued weights, and this incompatibility motivates investigating alternative architectures. In particular, for a first attempt we chose {-1, 1} as the input space and sign (•) as the activation function for the hidden layers:

sign (x) = -1, x < 0, +1, x ≥ 0. ( 4.2)
These choices are inspired by the fact that the model was designed with the idea of performing homomorphic evaluations over encrypted input. As a consequence, we wanted the message space to be as small as possible, which, in turn, would allow us to increase the efficiency of the overall evaluation. We also note that using an activation function whose output is in the same range as the network's input allows us to maintain the same semantics across different layers. In our case, what enters a neuron is always a weighted sum of values in {-1, 1}. In order to make the evaluation of the network compatible with FHE schemes, discretizing the input space is not sufficient: we also need to have discrete values for the weights of the network4 .

Simple conversion from a traditional NN to a DiNN

In this subsection we show a very simple method to convert an already-trained canonical neural network (i.e., with real weights) into a DiNN. This method is not guaranteed to be the best way to obtain such a conversion; it indeed introduces a visible loss in the classification accuracy and would probably be best used as a first step in the conversion procedure. However, we remind the reader that this work is aimed at the homomorphic evaluation of a network, thus we decided not to put too much effort in the construction of a sophisticated cleartext model. This procedure allows us to obtain a network which respects our constraints and that can be evaluated over encrypted inputs, so it is sufficient for our purposes.

It turns out that the only thing that we need to do is discretizing the weights and biases of the network. To this purpose, we define the function

processWeight (w, τ ) = τ • w τ (4.3)
where τ ∈ N is a parameter that controls the precision of the discretization. In the following, we implicitly take all the weights as discretized after being processed through the formula in Equation (4.3). After fixing a value τ , the network obtained by applying processWeight (•, τ ) to all the weights and biases is a DiNN. The parameter τ has to be chosen carefully, since it defines the message space that our encryption scheme must support. Thus, we want the bound on w, x to be small for all neurons, where w and x are the discretized weights and the inputs associated to the neuron, respectively. In Figure 4.5, we show the evaluation of a single neuron: we first compute w, x , which we refer to as a multisum, and then apply the sign function to the result.

Homomorphic evaluation of a DiNN

We now give a high level description of our procedure to homomorphically evaluate a DiNN, called FHE-DiNN. We basically need two ingredients: we need to be able to compute the multisum between the encrypted inputs and the weights and we need to homomorphically extract the sign of the result. In order to maintain the scalability of our scheme across the layers of a given DiNN, we perform a bootstrapping operation for every neuron in hidden layers. This ensures that the ciphertext encrypting the sign of the result after applying one layer of the DiNN can be used for further computations without an initially fixed limit on Chapter 4

4.5 Our contributions 57 the number of layers that the network can contain. Hence we can choose parameters that are independent of the number of layers and evaluate arbitrarily deep neural networks.

Evaluating the multisum

In our framework, the weights of the network are available in clear, so we can evaluate the multisum just by using homomorphic additions. The only things that need our attention are the message space of our encryption scheme, which has to be large enough to accommodate for all possible values of the multisums, and the noise level that might grow too much and lead to incorrect results.

Extending the message space. In order for our FHE scheme to be able to correctly evaluate the multisum, we need all the possible values of the multisum to be inside our message space. To this end, we extend our LWE encryption scheme as follows. This idea was already used in previous works such as [PW08; KTX08; ABDP15; ALS16].

Dec (s, c 1 + w • c 2 ) = Dec (s, (a 1 + w • a 2 , b 1 + w • b 2 )) = m 1 + w • m 2 as long as (1) m 1 + w • m 2 ∈ [-B, B]
, and (2) the noise did not grow too much.

The first condition is easily met by choosing B ≥ w 1 for all weight vectors w in the network (e.g., we can take the max).

Fixing the noise. Increasing the message space has an impact on the choice of parameters. Evaluating the multisum with a given weight vector w means that, if the standard deviation of the initial noise is σ, then the standard deviation of the output noise can be as high as w 2 • σ (see Lemma 2.3.17), which in turn means that our initial standard deviation must be smaller than the one in [START_REF] Chillotti | Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds[END_REF] by a factor max w w 2 . Moreover, for correctness to hold, we need the noise to remain smaller than half a slice of the torus. As we are splitting the torus into 2B +1 slices rather than 2, we need to further decrease the noise by a factor B. Special attention must be paid to security: taking a smaller noise might in fact compromise the security of the scheme. In order to mitigate this problem, we can increase the dimension of the LWE problem n, but this in turn induces more noise overhead in the bootstrapping procedure due to rounding errors. each tick of the top part of the wheel is mapped to its sign which is +1 and each tick of the bottom part to -1. This can roughly be seen as embedding the wheel back to the torus.

Homomorphic computation of the sign function

We take advantage of the flexibility of the bootstrapping technique introduced by Chillotti et al. [START_REF] Chillotti | Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds[END_REF] in order to perform the sign extraction and the bootstrapping at the same time. Concretely, in the call to BlindRotate, we change the value of testVector to

-1 2B + 1 N -1 i=0 X i .
Then, if the value of the phase b -s, a is between 1 and N (positive), the output will be an encryption of 1, otherwise if it is between N + 1 and 2N (negative), the output will be an encryption of -1.

In order to give more intuition, we present an illustration of the bootstrapping technique in Figure 4.6. The first step of the bootstrapping basically consists in mapping the torus T to an object that we will refer to as the wheel. This wheel is split into 2N "ticks" that are associated to the possible values that are encrypted in the bootstrapped ciphertext. The bootstrapping procedure then consists in choosing a value for each tick, rotating the wheel by b -s, a ticks counter-clockwise, and picking the value of the rightmost tick. We note that the values on the wheel are encoded in the testVector variable, which contains values for the ticks on the top part of the wheel. The bottom values are then fixed by the anticyclic property of T N [X] (the value at tick N + i is minus the value at tick i).

From now on, we say that a bootstrapping is correct if, given a valid encryption of a message µ, its output is a valid encryption of sign (µ) with overwhelming probability.

Scale-invariance

If the parameters are set correctly then, by using the two operations described above, we can homomorphically evaluate neural networks of any depth. In particular, the choice of parameters is independent of the depth of the neural network. This result cannot be achieved with previous techniques relying on somewhat homomorphic evaluations of the network. In fact, they have to choose parameters that accommodate for the whole computation, whereas our method only requires the parameters to accommodate for the evaluation of a single neuron. The rest of the computation follows by induction. More precisely, our choice of parameters only depends on bounds on the norms ( • 1 and • 2 ) of the input weights of a neuron. In the following, we denote these bounds by M 1 and M 2 , respectively.

We say that the homomorphic evaluation of the neural network is correct if the decryptions of its output scores are equal to the scores given by its evaluation in the clear with overwhelming probability. Then, the scale-invariance is formally defined by the following theorem: Theorem 4.5.3 (Scale-invariance of our homomorphic evaluation). For any DiNN of any depth, any correctly generated bootstrapping key bk and keyswitching key ksk, and any ciphertext c, let σ be a Gaussian parameter such that the noise of Bootstrap (bk, ksk, c) is sub-Gaussian with parameter σ. Then, if the bootstrapping is correct on input ciphertexts with sub-Gaussian noise of parameter σ M 2 and message space larger than 2M 1 + 1, the result of the homomorphic evaluation of the DiNN is correct.

Proof. The proof is a simple induction on the structure of the neural network. First, the correctness of the evaluation of the first layer is implied by the choice of parameters for the encryption 5 .

If the evaluation is correct for all neurons of the -th layer, then the correctness for all neurons of the ( + 1)-th layer follows from the two observations made in the previous subsections:

• The result of the homomorphic evaluation of the multisum is a valid encryption of the multisum;

• The result of the bootstrapping is a valid encryption of the sign of the multisum.

The first fact is implied by the choice of the message space, since the multisum value is contained in [-M 1 , M 1 ]. The second one comes directly from the correctness of the bootstrapping, because the homomorphic computation of the multisum on ciphertexts with sub-Gaussian noise of parameter σ yields a ciphertext with sub-Gaussian noise of parameter at most σM 2 (cf. Theorem 2.3.17).

Then, the correctness of the encryption scheme ensures that the final ciphertexts are valid encryptions of the scores.

Refinements of TFHE

In this section, we present several improvements that helped us achieving better efficiency for the actual FHE-DiNN implementation. These various techniques can without any doubt be applied in other FHE-based applications.

Reducing bandwidth usage

One of the drawbacks of our evaluation process is that encrypting individual values for each input neuron yields a very large ciphertext, which is inconvenient from a user perspective, as a high bandwidth requirement is the direct consequence. In order to mitigate this issue, we "pack" multiple values into one ciphertext. We use the standard technique of encrypting a polynomial (using the TLWE scheme instead of LWE) whose coefficients correspond to the different values we want to encrypt:

ct = TLWE.Encrypt i x i X i ,
where the x i 's represent the values of the input neurons to be encrypted 6 . This packing technique is what made Ring-LWE an attractive variant to the standard LWE problem, as was already presented in [START_REF] Lyubashevsky | On Ideal Lattices and Learning with Errors over Rings[END_REF], and is widely used in FHE applications to amortize the cost of operations [START_REF] Halevi | Algorithms in HElib[END_REF][START_REF] Halevi | Bootstrapping for HElib[END_REF].

Then, we observe that for each neuron in the first hidden layer, we can compute the multisum with coefficients w i by scaling the input TLWE ciphertext by a factor

i w i X -i .
Indeed, it is easy to verify that the constant term of i x i X i • i w i X -i is i w i x i , and we can obtain an LWE encryption of this value by invoking Extract. Remark 4.5.4. We note that this computation is actually equivalent to doing the multisum directly on LWE ciphertexts, so the resulting noise growth of this approach is exactly the same as before. We end up saving bandwidth usage (by a factor up to N , the degree of the polynomials) basically for free. Furthermore, as the weights of the neural network never change, we can precompute and store the FFT representation of the polynomials w i X -i , thus saving time during the online classification.

In a nutshell, we reduce the size of the ciphertexts for N elements from N LWE ciphertexts to 1 TLWE ciphertext. In terms of numbers of elements in T, the cost dropped from N (n+1) to N (k + 1).

We remark that the resulting ciphertext is an LWE ciphertext in dimension N , and not the original n, thus requiring key-switching to become a legitimate ciphertext. However, this is not a problem thanks to the trick presented in the following subsection.

Moving KeySwitch around

The main goal of key-switching here is to reduce the LWE dimension. The benefits in memory usage and efficiency of this reduction are extremely important, since the size of the bootstrapping key, the final noise level, and the number of external products (the most costly operation) all depend linearly on this parameter. However, we noticed that reducing this dimension in the beginning of the bootstrapping procedure instead of the end gave much better results, hence the new bootstrapping function:

Bootstrap = Extract • BlindRotate • KeySwitch.
The intuition is that, with this technique, the noise produced by KeySwitch will not be multiplied by w 2 when performing the computation of the multisum, but will only be added at the end. Basically, we moved the noise of the output ciphertext produced by KeySwitch to an overhead noise.

Doing this, we reverse the usage of the two underlying LWE schemes: everything is now done on high dimensional N -LWE, whereas the low dimensional n-LWE scheme is only used during the bootstrapping operation. Since the noise in the key-switching key is not used for any computation anymore, we can allow it to be bigger, thus reducing the dimension we need for the same security to hold and, in turn, gaining in time per bootstrapping.

The only downside is that working with higher dimensional N -LWE samples means slightly more memory usage for the server, bigger output ciphertext7 , and slightly slower addition of ciphertexts. However, as this operation is instantaneous when compared to other operations such as bootstrapping, this is not an issue.

Dynamically changing the message space

In Section 4.5.3, we showed how to evaluate the whole neural network by induction, using a message space of 2B + 1 slices, where B is a bound on the values of the multisums across the whole evaluation. However, in order to be able to reduce the probability of errors along the way, we are able to use different message spaces for each layer of the DiNN, and adapt the number of slots to the values given by the local computations, depending on the values of the weights w. In order to do so, we change the value of testVector to

-1 2B + 1 N -1 i=0 X i ,
where B is now indexed by the current layer , and is a bound on the values of the multisums for the next layer + 1. The point of this manoeuvre is that if the number of slots is smaller, the slices are bigger, and the noise would have to be bigger in order to change the plaintext message. This trick might seem superfluous, because it decreases a probability that is already negligible. However sometimes, in practical scenarios, the correctness of the scheme is relaxed, and this trick allows us to obtain results closer to the expected values without costing any extra computation or storage.

Alternative BlindRotate implementations

Following the technique of [START_REF] Tanping | Faster Bootstrapping with Multiple Addends[END_REF], we try to gain efficiency in the bootstrapping by reducing the number of external products that we have to compute. In order to do so, they slightly unfold the loop computing X s,a in the BlindRotate algorithm. They group the terms of the sum two by two, using the following formula for each of the new terms:

X as+a s = ss X a+a + s(1 -s )X a + (1 -s)s X a + (1 -s)(1 -s ).
In order to compute this new function, they change the bootstrapping key to contain encryptions of the values ss , s(1s ), (1s)s , and (1s)(1s ), thus expanding the size of the bootstrapping key by a factor 2. Using this idea, they cut the number of iterations of the loop by half, thus computing only half the amount of external products, which is the most costly operation of the bootstrapping. However, by doing so, they introduce the ACC ← ((X a 2i +a 2i+1 -1)bk 3i + (X a 2i -1)bk 3i+1 + (X a 2i+1 -1)bk 3i+2 ) ACC 4: end for 5: return ACC computation of 4 scalings of TGSW ciphertexts (which are matrices) by constant polynomials, and 3 TGSW additions, when TFHE's BlindRotate only needed 1 scaling of a TLWE ciphertext, and 1 TLWE addition. Another benefit is that the homomorphic computation of s, a induces rounding errors on only n/2 terms instead of n. The noise of the output ciphertext is also different. On the bright side, the technique of [START_REF] Tanping | Faster Bootstrapping with Multiple Addends[END_REF] reduces the noise induced by the precision errors during the gadget decomposition by a factor 2. On the other hand, it increases the noise coming from the bootstrapping key by a factor 2.

In this work, we suggest to use another formula in order to compute each term of the slightly unfolded sum. Observing that ss + s(1s ) + (1s)s + (1s)(1s ) = 1, we can save 1 element in the bootstrapping key:

X as+a s = ss (X a+a -1) + s(1 -s )(X a -1) + (1 -s)s (X a -1) + 1.
The resulting BlindRotate algorithm is described in Algorithm 2. Having a 1 in the decomposition is a valuable advantage, because it means that we can move it out of the external product and instead add the previous value of the accumulator to the result. Thus, efficiencywise, we halved the number of external products at the cost of only 3 scalings of TGSW ciphertexts by constant polynomials, 2 TGSW additions, and 1 TLWE addition. We note that while multiplying naively by a monomial might be faster than multiplying by a degree 2 polynomial, the implementation pre-computes and stores the FFT representation of the bootstrapping keys in order to speed up polynomial multiplication. Thus, multiplying by a polynomial of any degree has the same cost. The size of the bootstrapping key is now 3/2 times larger than the size of the one in TFHE, which is a compromise between the two previous methods. As in [START_REF] Tanping | Faster Bootstrapping with Multiple Addends[END_REF], the noise induced by precision errors and roundings is halved compared to TFHE. On the other hand, now we increase the noise coming from the bootstrapping key by a factor 3 instead. However, we note that it is possible to reduce this noise without impacting efficiency by reducing the noise in the bootstrapping key, trading off security (depending on what the bottleneck for security of the scheme is, this could come for free), whereas in order to reduce the noise induced by the precision errors, efficiency will be impacted. We recapitulate these numbers in Table 4.1.

We note that this idea could be generalized to unfoldings consisting of more than two terms, yielding more possible trade-offs, but we did not explore further because of the dissuasive exponential growth in the number of operands in the general formula.

Experimental results

We implemented the proposed approach to test its accuracy and efficiency. This section is divided into two main parts: the first one describes the training of the neural network over data in the clear and the second one details the results obtained when evaluating the network over encrypted inputs.

Pre-processing the MNIST database

In order to respect the constraint of having inputs in {-1, 1}, we binarized all the images with a threshold value equal to 128: any pixel whose value is smaller than the threshold is mapped to -1; the others are mapped to +1. This actually reduces the amount of information available, as each 8-bit grayscale value is clamped to a single bit, and one could wonder if this could impact the accuracy of the classification. Although this is possible, a quick visual inspection of the result shows that the digits depicted in the images are still clearly recognizable.

Building a DiNN from data in the clear

In order to train the neural network, we first chose its topology, i.e., the number of hidden layers and neurons per hidden layer. We experimented with several values, always keeping in mind that a smaller number of neurons per layer is preferable: having more neurons means that the value of the multisum will be potentially higher, thus requiring a larger message space in the homomorphic evaluation, which in turn forces to choose bigger parameters for the scheme. After some tries, we decided to show the feasibility of our approach through the homomorphic evaluation of two neural networks. Both have 784 neurons in the input layer (one per pixel), a single hidden layer, and an output layer composed of 10 neurons (one per class). The difference between the two models is the size of the hidden layer: the first network has 30 neurons, while the second has 100.

In order to build a DiNN, we use the simple approach described in Section 4.5.2: we (1) train a traditional neural network (i.e., with real weights and biases), and then we (2) discretize all the values by applying the function in Equation (4.3). For step (1) we take advantage of the library keras [START_REF] Chollet | [END_REF] with Tensorflow [START_REF] Abadi | TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems[END_REF], which offers a simple and highly customizable framework for defining, training and evaluating even complex models of neural networks. Through a fairly simple Python script and in little time, we are able to define and train our models as desired. Given its similarity with (a scaled and shifted version of) the sign function, as an activation function we used the version of hard_sigmoid defined in Tensorflow and whose formula is in Equation (4.4).

hard_sigmoid (x) =        0, x < -2.5 0.2 x + 0.5, -2.5 ≤ x ≤ 2.5 1, x > 2.5 (4.4)
The reason behind this choice is that we know we will substitute this activation function with the true sign (x). Thus, using a function which is already similar to it helps reducing the errors introduced by this switch.

Once we obtain the trained model, we proceed to choose a value τ ∈ N and discretize the weights and the biases of the network, as per Equation ( 4.3), thus finally obtaining a DiNN that we can later evaluate over encrypted inputs. The choice of τ is an important part of the process: on one hand, picking a very small value will give little resolution to the network8 , potentially degrading the accuracy largely; on the other hand, picking a very large value will minimize the loss in accuracy but increase the message space that we will need to support for homomorphic evaluation, thus forcing us to choose larger parameters and making the overall evaluation less efficient. Also, note that it is possible to choose different values of the parameter τ for different layers of the network. Although there might be better choices, we did not invest too much efforts in optimizing the cleartext model and simply chose the value τ = 10 for both layers of each model. Finally, we switched all the activation functions from hard_sigmoid (•) to sign (•). In order to assess the results of the training and how the accuracy varies because of these changes, in Table 4.2 we report the accuracies obtained on the MNIST test set. Note that these values are referred to the evaluation over cleartext inputs.

Classifying encrypted inputs

Implementing the homomorphic evaluation of the neural network over encrypted input was more than a mere coding exercise, but allowed us to discover several interesting properties of our DiNNs. The starting point was the TFHE library by Chillotti et al., which is freely available on GitHub [START_REF] Chillotti | TFHE: Fast Fully Homomorphic Encryption Library over the Torus[END_REF] and which was used to efficiently perform the bootstrapping operation. The library takes advantage of FFT processors for fast polynomial multiplication and, although not parallelized, achieves excellent timing results. We extended the code to apply this fast bootstrapping procedure to our use case.

Original

Parameters. We now present our setting of the parameters, following the notation of [START_REF] Chillotti | Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds[END_REF], to which we refer the reader for extra details. In Table 4.3 we highlight the main security parameters regarding our ciphertexts, together with an estimate of the security level that this setting achieves. Other additional parameters, related to the various operations we need to perform, are the following:

• Degree of the polynomials in the ring: N = 1024;

• Dimension of the TLWE problem: k = 1;

• Basis for the decomposition of TGSW ciphertexts: B g = 1024;

• Length of the decomposition of TGSW ciphertexts: = 3;

• Basis for the decomposition during key switching: 8;

• Length of the decomposition during key switching: t = 5; With this choice of parameters, we achieve a minimum security level of 80 bits and a single bootstrapping operation takes roughly 15 ms on a single core of an Intel Core i7-4720HQ CPU @ 2.60GHz. Also, we note that by exploiting the packing technique presented Finally, we calculated the maximum value of the norms of the weight vectors associated to each neuron, both for the first and the second layer. These values, which can be computed at setup time (since the weights are available in the clear), define the theoretical bounds on the message space that our scheme should be able to support. In practice, we evaluated the actual values of the multisums on the training set, and took a message space slightly larger9 than what we computed. We note that with this method, it is possible that some input could make the multisum go out of bounds, but this was not observed when evaluating the network on the test set. Moreover, this allows us to take a considerably smaller message space in some cases, and thus reduce the probability of errors. In Table 4.4 we report the theoretical message space we would need to support and the message space we actually used for our implementation.

In order to pinpoint our noise parameters, we also calculated the maximum L 2 -norms of the weight vectors in each layer: for the network with 30 hidden neurons, we have max w w 2 ≈ 119 for the first layer and ≈ 85 for the second layer; for the network with 100 hidden neurons, we have max w w 2 ≈ 69 for the first layer and ≈ 60 for the second layer.

Evaluation.

Our homomorphic evaluation follows the outline presented in Figure 4.7 in order to classify an encrypted image, 1. Encrypt the image as a TLWE ciphertext; 2. Multiply the TLWE ciphertext by the polynomial which encodes the weights associated to the hidden layer. This operation takes advantage of FFT for speeding up the calculations;

3. From each of the so-computed ciphertexts, extract a 1024-LWE ciphertext, which encrypts the constant term of the result;

4. Perform a key switching in order to move from a 1024-LWE ciphertext to a 450-LWE one;

5. Bootstrap to decrease the noise level. By setting the testVector, this operation also applies the sign function and changes the message space of our encryption scheme for free. The second column gives the number of disagreements (images classified differently) between the evaluation in the clear and the homomorphic one; the numbers in parentheses give the disagreements in favor of the cleartext evaluation and those in favor of the homomorphic evaluation, respectively. The third column gives the number of wrong bootstrapping, i.e., when the sign is flipped. The fourth value gives the number of disagreements in which at least one bootstrapping was wrong. Finally, the last column gives the time required to classify a single image.

6. Perform the multisum of the resulting ciphertext and the weights leading to the output layer, through the technique showed in Section 4.5.3.110 7. Return the 10 ciphertexts corresponding to the 10 scores assigned by the neural network. These ciphertext can be decrypted and the argmax can be computed to obtain the classification given by the network.

In Table 4.5 we present the complete results of our experiments, both when using the original BlindRotate algorithm from [START_REF] Chillotti | Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds[END_REF] (denoted by or) and when using the modified algorithm presented in Section 4.5.4.4 (denoted by un, unfolded).

The homomorphic evaluation of the network on the entire test set was compared to its classification in the clear and we observed the following facts: Remark 4.5.5. The accuracy achieved when classifying encrypted images is close to that obtained when classifying images in the clear.

In the case of the network with 30 hidden neurons, we obtain a classification accuracy of 93.55% in the clear (cf. Table 4.2) and of 93.71% homomorphically. In the case of the network with 100 hidden neurons, we have 96.43% accuracy in the clear and 96.35% on encrypted inputs. These gaps are explained by the following observations. Remark 4.5.6. During the evaluation, some signs are flipped during the bootstrapping but this does not significantly harm the accuracy of the network.

We use aggressive internal parameters (e.g., N and, in general, all the parameters that control the precision) for the homomorphic evaluation, knowing that this could sometimes lead the bootstrapping procedure to return an incorrect result when extracting the sign of a message. In fact, we conjectured that the neural network would be resilient to perturbations and experimental results proved that this is indeed the case: when running our experiment over the full test set, we noticed that the number of wrong bootstrappings is 3383 (respectively, 9088) but this did not change the outcome of the classification in more than 196 (respectively, 105) cases (cf. Table 4.5).

Remark 4.5.7. The classification of an encrypted image might disagree with the classification of the same image in the clear but this does not significantly worsen the overall accuracy.

This is a property that we expected during the implementation phase and our intuition to explain this fact is the following: the network is assigning 10 scores to each image, one per digit, and when two scores are close (i.e., the network is hesitating between two classes), it can happen that the classification in the clear is correct and the one over the encrypted image is wrong. But the opposite can also be true, thus leading to classifying correctly an encrypted sample that was misclassified in the clear. We experimentally verified that disagreements between the evaluations do not automatically imply that the homomorphic classification is worse than the one in the clear: out of 273 (respectively, 127) disagreements, the classification in the clear was correct 105 (respectively, 61) times, against 121 (respectively, 44) times in favor of the homomorphic one 11 (cf. Table 4.5). Before stating some open problems, we conclude with the following note: using a bigger neural network generally leads to a better classification accuracy, at the cost of performing more calculations and, above all, more bootstrapping operations. However, the evaluation time will always grow linearly with the number of neurons. Although it is true that evaluating a bigger network is computationally more expensive, we stress that the bootstrapping operations are independent of each other and can thus be performed in parallel. Ideally, parallelizing the execution across a number of cores equal to the number of neurons in a layer (30 or 100 in our work) would result in that the evaluation of the layer would take roughly the time of a bootstrapping (i.e., around 15 ms).

Future directions and open problems. This work opens a number of possibilities and, thus, raises several interesting open problems. The first one is about the construction of our DiNNs. In this work, we did not pay too much attention to this step and, as a consequence, we considerably worsened the accuracy when moving from a canonical neural network to a DiNN. In order to improve the classification given by these discretized networks, it would be interesting to train a DiNN, rather than simply discretizing an already-trained model. Using discrete values and the sign function for the activation makes some calculations (e.g., some derivatives) impossible. Techniques to overcome these limitations have already been proposed in the literature (e.g., [START_REF] Courbariaux | BinaryNet: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1[END_REF]) and they can be applied to our DiNNs as well. Also, another potentially interesting approach would be mixing these two ways of constructing a DiNN, for example by first discretizing a given model and then training the resulting network to refine it. Another natural question is whether we can batch several bootstrappings together, in order to improve the overall efficiency of the evaluation. Moreover, the speed of the evaluation would benefit from taking advantage of multi-core processing units, like GPUs.

Most interestingly, our FHE-DiNN framework is flexible and can be adapted to more generic cognitive architectures: we leave this as an interesting open problem. In particular, excellent results have been obtained by using Convolutional Neural Networks (see e.g., [START_REF] Lecun | Gradient-Based Learning Applied to Document Recognition[END_REF]), and we believe that trying to apply FHE-DiNN to these models would be an interesting line of research. Achieving this goal would require extending the current capabilities of FHE. For example, we would need to be able to homomorphically evaluate the max function, which is required to construct the widely-used max pooling layers. To the best of our knowledge, a technique for an efficient homomorphic evaluation of the max function is currently not known. Finally, the methodology presented in this work is by no means limited to image recognition, but can be applied to other machine learning problems as well.

Comparison with Cryptonets [DGL+16]

We now give a complete comparison between our framework FHE-DiNN and Cryptonets, with respect to communication complexity (i.e., size of ciphertexts), classification accuracy, and timings.

In Cryptonets, propagated signals are reals properly encoded into compatible plaintexts and a single encrypted input (i.e., an image pixel) takes 2 • 382 • 8192 bits (= 766 kB). Therefore, an entire image takes 28 • 28 • 766 kB ≈ 586 MB. However, with the same storage requirements, Cryptonets can batch 8192 images together, so that the amortized size of an encrypted image is reduced to 73.3 kB. In the case of FHE-DiNN, we are able to exploit the batching technique on a single image, resulting in that each encrypted image takes ≈ 8.2 kB. In the case of Cryptonets, the complete homomorphic evaluation of the network takes 570 seconds, whereas in our case it takes 0.49 s (or 1.6 s in the case of a slightly larger network). However, it should be noted that (a) the networks that we use for our experiments are considerably smaller than that used in Cryptonets, so we also compare the time-per-neuron and, in this case, our solution is faster by roughly a factor 36; moreover (b) once again Cryptonets support image batching, so 8192 images can be classified in 570 seconds, resulting in only 0.07 s per image. Cryptonets' ability to batch images together can be useful in some applications where the same user wants to classify a large number of samples together. In the simplest case where the user only wants a single image to be classified, this feature does not help. Regarding classification accuracy, the NN used by Cryptonets achieves 98.95 % of correctly classified samples, when evaluated on the MNIST dataset. In our case, a loss of accuracy occurs due to the preliminary simplification of the MNIST images, and especially because of the discretization of the network. We stress however that our prime goal was not accuracy but to achieve a qualitatively better homomorphic evaluation at the neuron level.

Finally, we also achieve scale-invariance, meaning that we can keep on computing over the encrypted outputs of our network, whereas Cryptonets are bounded by the initial choice of parameters. In Table 4.6 we present a detailed comparison with Cryptonets.

Introduction

As presented in Chapter 3, a fully homomorphic encryption (FHE) scheme is an encryption scheme which supports computation on encrypted data: given a ciphertext that encrypts some data µ, one can compute a ciphertext that encrypts f (µ) for any efficiently computable function f , without ever needing to decrypt the data or know the decryption key. FHE has numerous theoretical and practical applications, the canonical one being to the problem of outsourcing computation to a remote server without compromising one's privacy. In 2009, Gentry put forth the first candidate construction of FHE based on ideal lattices [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF]. Since then, substantial progress has been made [DGHV10; SS10; SV10; BV11a; BV11b; BGV12; GHS12; GSW13; BV14; AP14], offering various improvements in conceptual and technical simplicity, efficiency, security guarantees, assumptions, etc; in particular, Gentry, Sahai and Waters presented a very simple FHE (hereafter called the GSW cryptosystem) based on the standard learning with errors (LWE) assumption.

Circuit privacy. An additional requirement in many FHE applications is that the evaluated ciphertext should also hide the function f , apart from what is inevitably leaked through the outcome of the computation f (µ); we refer to this requirement as circuit privacy [SYY99; IP07]. In the context of outsourcing computation, a server may wish to hide its proprietary algorithm from the client, while in the context of homomorphic evaluation of neural networks, a company might want to protect the "internal details" of the cognitive model, such as its topology, the weights, . . . In fact, training an effective neural network is usually a complex and time-consuming procedure, where considerable effort is invested to achieve small improvements that make one's product better than those of the competitors. In these situations, protecting the privacy of these trade secrets becomes of vital importance for the profitability of the product. Circuit privacy is also a requirement when we use FHE for low-communication secure two-party computation. In all existing FHE schemes, there is a "noise" term in the ciphertext, which is necessary for security. The noise grows and changes as a result of performing homomorphic operations and, in particular, could leak information about the function f . The main challenge for achieving FHE circuit privacy lies precisely in avoiding the leakage from the noise term in the evaluated ciphertext.

Prior works. Prior works achieve circuit privacy by essentially canceling out the noise term in the evaluated ciphertext. There are two main approaches for achieving this. The first is "noise flooding" introduced in Gentry's thesis, where we add a much larger noise at the end of the computation; in particular, the noise that is added needs to be super-polynomially larger than the noise that accumulates amidst homomorphic operations, which in turn requires that we start with a super-polynomial modulus-to-noise ratio1 . This is a fairly mild assumption for the early constructions of FHE schemes, which required a quasi-polynomial modulusto-noise ratio just to support homomorphic operations for circuits in NC 1 (i.e., circuits of logarithmic depth). The second is to decrypt and re-encrypt the evaluated ciphertext, also known as bootstrapping in the FHE literature. This can be achieved securely without having to know the secret key in the clear in one of two ways: (i) with the use of garbled circuits [OPP14; GHV10], and (ii) via homomorphic evaluation of the decryption circuit given an encryption of the secret key under itself [START_REF] Ducas | Sanitization of FHE Ciphertexts[END_REF], which requires the additional assumption of circular security (cf. Assumption 3.3.1).

Both of the prior approaches have some theoretical and practical draw-backs, if we consider FHE for NC 1 circuits (the rest of the discussion also applies to leveled FHE for general circuits). First, recall that we now have FHE for NC 1 circuits under the LWE assumption with a polynomial modulus-to-noise ratio [BV14; AP14], and we would ideally like to achieve circuit privacy under the same assumption. Relying on noise flooding for circuit privacy would require quantitatively stronger assumptions with a super-polynomial modulusto-noise ratio, which in turn impacts practical efficiency due to the use of larger parameters. Similarly, the use of bootstrapping for circuit privacy can also be computationally expensive (indeed, the bootstrapping operation is the computational bottleneck in existing FHE schemes, cf. [DM15; HS15]). Moreover, realizing bootstrapping via an encryption of the secret key requires an additional circular security assumption (cf. Assumption 3.3.1), which could in turn also entail the use of larger parameters in order to account for potential weaknesses introduced by circular security. Realizing bootstrapping via garbled circuits avoids the additional assumption, but is theoretically and practically unsatisfying as it requires encoding the algebraic structure in existing FHEs as boolean computation, and sacrifices the multi-hop property in that we can no longer perform further homomorphic computation on the evaluated ciphertexts.

Our results

Our main result is a circuit-private FHE for NC 1 circuits -and a circuit-private leveled FHE for general circuits -under the LWE assumption with a polynomial modulus-to-noise ratio, and whose efficiency essentially matches that of existing variants of the GSW cryptosystem in [START_REF] Brakerski | Lattice-based FHE as secure as PKE[END_REF][START_REF] Alperin | Faster Bootstrapping with Polynomial Error[END_REF]; in other words, we avoid noise flooding or bootstrapping and obtain circuit privacy almost for free.

We obtain our main result via a conceptually different approach from prior works: instead of canceling out the noise term in the evaluated ciphertext, we directly analyze the distribution of the noise term (prior works on FHE merely gave a bound on the noise term). Concretely, we show that adding a small noise in each step of homomorphic evaluation in the GSW cryptosystem already hides the computation itself which yields circuit privacy. Along the way, we gain better insights into the algebraic structure and the noise distribution in GSW scheme and provide new tools for analyzing noise randomization which we believe could be of independent interest.

As an immediate corollary, we obtain a two-party protocol for secure function evaluation where Alice holds x, Bob holds a branching program f , and we want Alice to learn f (x) while protecting the privacy of x and f to the largest extent possible, that is, Bob learns nothing about x and Alice learns nothing about f (apart from a bound on the size of f ). Our protocol achieves semi-honest security under the standard LWE assumption with polynomial hardness, and where the total communication complexity and Alice's computation are polylogarithmic in the size of f . The core of our analysis is a variant of the Gaussian leftover hash lemma [AGHS13; AR13]: given a "small" vector e and any vector v, we have

e • G -1 rand (v) + y ≈ s e where • G -1
rand (v) outputs a random short vector x satisfying Gx = v mod q according to a discrete Gaussian with parameter r = O (1);

plaintext v out = v x = xv 1 + (1 -x)v 0 [GSW13; BV14] V out = C • G -1 det (V 1 ) + (G -C) • G -1 det (V 0 ) [AP14] V out = C • G -1 rand (V 1 ) + (G -C) • G -1 rand (V 0 ) [this work] V out = C • G -1 rand (V 1 ) + (G -C) • G -1 rand (V 0 ) +    0 y   
Table 5.1: The first row of the table shows the plaintext computation that happens at each step of the evaluation of a branching program (cf. Section 5.4.3.1). The next three rows describe how this computation is carried out homomorphically on ciphertexts V 0 , V 1 , C corresponding to encryptions of the input bits v 0 , v 1 , x.

In the [GSW13; BV14] FHE schemes, homomorphic evaluation is deterministic, whereas in [START_REF] Alperin | Faster Bootstrapping with Polynomial Error[END_REF] and this work, homomorphic evaluation is randomized. In particular, our construction introduces an additional small Gaussian shift on top of [START_REF] Alperin | Faster Bootstrapping with Polynomial Error[END_REF].

• both y and e are drawn from discrete Gaussians with parameter O (r • e ) (the norm of e will be slightly larger than that of y).

We stress that the distribution of e is independent of v and that the norm of y, e are polynomially related to that of e . Indeed, a similar statement is true via noise flooding, where we pick y, e to have norm super-polynomially larger than that of e . Using this leftover hash lemma to hide the argument of G -1 rand (•) is new to this work and will be crucial in proving circuit privacy. In Table 5.1 we show a comparison with previous works on how to perform a step of computation for branching program evaluation.

Technical overview

We proceed with a technical overview of our construction. We build up to our main construction in three steps.

Generating fresh LWE samples. How do we generate a fresh LWE sample from a large but bounded number of samples? That is, we need to randomize (A, s A + e ). The first idea, going back to [Reg05; GPV08; ACPS09] is to choose x according to a discrete Gaussian with parameter r = O (1) and a small "smoothing" noise y from a discrete Gaussian with parameter O (r • e ) and output

Ax, (s A + e )x + y

The vector Ax is statistically close to uniform (by leftover hash lemma), and the error e x + y in the resulting sample is statistically close to a discrete Gaussian with parameter O (r • e ). We stress that the norm of y is polynomially related to that of e, which is better than naive noise flooding. One draw-back compared to noise flooding is that the error in the new sample leaks e . In the case of generating fresh LWE samples, we just need to repeat the process to generate many more samples than what we started out with.

Randomizing GSW ciphertexts. Next, we note that the above idea can also be used to randomize GSW ciphertexts. Recall that a GSW encryption of a message µ is of the form

C = A s A + e + µG ∈ Z n×(n log q) q
where s ∈ Z n q is the secret key and G is the "powers of 2" gadget matrix. We can randomize C to be a fresh encryption of µ by computing

C • G -1 rand (G) + 0 y
where G -1 rand (G) is chosen according to a discrete Gaussian of parameter r satisfying G • G -1 rand (G) = G and y is again a small smoothing noise vector. Here, we need an extension of the previous lemma showing that each coordinate in e • G -1 rand (G) + y is statistically close to a discrete Gaussian; this in turn follows from an extension of the previous lemma where the vector x is drawn from discrete Gaussian over the coset of a lattice (cf. Lemma 5.3.3). And again, the norm of y is polynomially related to that in e, which is better than naive noise flooding.

Scaling GSW ciphertexts. More interesting, given a constant a ∈ {0, 1}, we can scale a GSW encryption of µ to obtain a fresh encryption of a • µ while revealing no information about a beyond what is leaked in a • µ. In particular, if µ = 0, then the resulting ciphertext should completely hide a. To achieve this, we simply proceed as before, except we use

G -1 rand (a • G) so that G • G -1 rand (a • G) = a • G.
Here, we crucially rely on the fact that the error e • G -1 rand (a • G) + y in the resulting ciphertext is independent of a. Circuit-private homomorphic evaluation. The preceding construction extends to the setting where we are given a GSW encryption C of a instead of a itself, so that we output

C • G -1 rand C + 0 y .
We can handle homomorphic encryption as in GSW; this then readily extends to a circuitprivate homomorphic evaluation for branching programs, following [BV14; AP14]. Branching programs are a relatively powerful representation model. In particular, any logarithmic space or NC 1 computation can be carried out by a family of polynomial-size branching programs. Branching programs can also directly capture several representation models often used in practice such as decision trees, OBDDs, and deterministic finite automaton.

The key insight from Brakerski and Vaikuntanathan [START_REF] Brakerski | Lattice-based FHE as secure as PKE[END_REF] is that when homomorphically evaluating a branching program, we will only need to perform homomorphic additions along with homomorphic multiplications of ciphertexts V j , C i where V j is the encryption of an intermediate computation and C i is an encryption of the input variable x i . To obtain decryption correctness with polynomial noise growth, they computed the product as

C i • G -1 det (V j ),
where G -1 det (•) is the deterministic binary decomposition, cleverly exploiting the asymmetric noise growth in GSW ciphertexts and the fact that the noise in C i is smaller than that in

Probability results

We will also need the following probability results. Lemma 5.2.2 (Simplified version of [Pei10, Theorem 3.1]). Let ε > 0, r 1 , r 2 > 0 be two Gaussian parameters, and Λ ⊆ Z m be a lattice. If

r 1 r 2 √ r 2 1 +r 2 2 ≥ η ε (Λ), then ∆ y 1 + y 2 , y ≤ 8ε,
where

y 1 ← D Λ,r 1 , y 2 ← D Λ,r 2 , and y ← D Λ, √ r 2 1 +r 2 2 .
Lemma 5.2.3 ([AP14, Lemma 2.1]). There exists a universal constant C > 0, such that

Pr x > Cr √ m ≤ 2 -Ω(m) ,
where x ← D Z m ,r .

Results on lattices and Gaussian distributions

Finally, we recall some additional results.

Lemma 5.2.4 ([MR07, Lemma 3.3]).

Let Λ be any rank-m lattice and ε be any positive real.

Then

η ε (Λ) ≤ λ m (Λ) • ln (2m (1 + 1/ε)) π , where λ m (Λ) is the m-th successive minimum of the lattice Λ (cf. Definition 2.3.4). Lemma 5.2.5 ([GPV08, Corollary 2.8]). Let Λ ⊆ Z m be a lattice, 0 < ε < 1, r > 0. For any vector c ∈ R m , if r ≥ η ε (Λ), then we have ρ r (Λ + c) ∈ 1 -ε 1 + ε , 1 • ρ r (Λ) . Lemma 5.2.6 ([Reg05, Claim 3.8]). Let Λ ⊆ Z m be any lattice, c ∈ R m , ε > 0 and r ≥ η ε (Λ). Then ρ r (Λ + c) ∈ r m det (Λ) (1 ± ε) .

Entropy and leftover hash lemma

Here, we recall the definition of min-entropy and a version of the leftover hash lemma.

Definition 5.2.7 (Min-entropy). The min-entropy of a random variable X is defined as

H ∞ (X) := -log max x Pr[X = x] .
Next, we state here a simplified version of the leftover hash lemma (originally introduced by Impagliazzo et al. [START_REF] Impagliazzo | Pseudo-random Generation from one-way functions (Extended Abstracts)[END_REF]), which is sufficient for our use. Lemma 5.2.8 (Leftover hash lemma [START_REF] Dodis | Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data[END_REF]). Let e be any random variable over Z m q and f : Z m q → Z k q . Then ∆ ((Xe, X, f (e)) , (r, X, f (e))) ≤ q n+k • 2 -H∞(e) .

Permutation branching programs

Here we recall the definition of a permutation branching program, that we also call simply branching program, and sometimes abbreviate as BP.

Definition 5.2.9 (Permutation branching program). A permutation branching program Π

of length L and width W with input space {0, 1} is a sequence of L tuples of the form (var (t) , π t,0 , π t,1 ), where

• var : [L] → [ ]
is a function that associates the t-th tuple with an input bit x var(t)

• π t,0 , π t,1 : [W ] → [W ] are permutations that dictate the t-th step of the computation.

On input (x 1 , . . . , x ), Π outputs 1 iff

π L,x var(L) (• • • (π 1,x var(1) (1)) • • • ) = 1.
Following [BV14; IP07], we will evaluate Π recursively as follows. We associate each t ∈ [L] with the characteristic vector v t ∈ {0, 1} W of the current "state", starting with v 0 = (1, 0, . . . , 0). We can then compute the w-th entry of v t (denoted by v t [w]): for all

t ∈ [L], w ∈ [W ], v t [w] = v t-1 π -1 t,x var(t) (w) = x var(t) • v t-1 π -1 t,1 (w) + 1 -x var(t) • v t-1 π -1 t,0 (w) . (5.1)

Core randomization lemma

We are now ready to state and prove our main randomization lemma for LWE samples. Note that in the remainder of this chapter, we set q to be a power of 2, and m = n log q. We discuss the use of a q which is not a power of 2 in Section 5.4.5.

Lemma 5.3.1 (Core randomization lemma). Let ε, ε > 0, r > η ε Λ ⊥ q (G ) be a Gaussian parameter. For any e ∈ Z m q , v ∈ Z n q , if r ≥ max   4 (1 -ε) 2ε 2 -1 m , √ 5(1 + e ) ln (2m (1 + 1/ε)) π   , then ∆ (A, Ax, e x + y) , A, u, e < ε + 2ε where x ← G -1 rand (v), A ←$ Z (n-1)×m q , u ←$ Z n-1 q , y ← D Z,r and e ← D Z,r √ 1+ e 2 .
Asymptotically, r = Θ ( e √ κ) is enough to obtain negligible statistical distance.

Remark 5.3.2 (on the necessity of randomization). We note here that the use of randomization in G -1 rand (•) and the shift are both necessary. First, the shift is necessary for both distributions to have the same support. For example, e G -1 rand ((1, 0, . . . , 0)) and e G -1 rand (0) might lie in two different cosets of the lattice e Λ ⊥ q (G ), depending on the value of e: if the first coordinate of e is odd and all the others are even, then e G -1 rand ((1, 0, . . . , 0)) will be odd, while e G -1 rand (0) will be even, for an even q. The shift by a Gaussian over Z ensures that the support of the two distributions is Z.

Proving that e Λ ⊥ q (G ) = Z with overwhelming probability over the choice of e is still an open question that would remove the necessity of the shift, thus proving circuit privacy for standard GSW only using randomized G -1 rand (•). Finally, the randomization of G -1 rand (•) is necessary for both distributions to have the same center. Using the same example, e G -1 det ((1, 0, . . . , 0)) + y and e G -1 det (0) + y would be two Gaussians, centered respectively on e 1 (the first coordinate of e) and on 0. Instead, using the randomized algorithm G -1 rand (•), the center of both distributions will be 0.

Proof of randomization lemma

We first prove that given e, the new error term e x + y is indeed a Gaussian with parameter r 1 + e 2 . This proof is inspired by [START_REF] Aggarwal | A Note on Discrete Gaussian Combinations of Lattice Vectors[END_REF], which in turn is an improvement of [START_REF] Agrawal | Discrete Gaussian Leftover Hash Lemma over Infinite Domains[END_REF], but it is different in two aspects: on one hand, in [START_REF] Aggarwal | A Note on Discrete Gaussian Combinations of Lattice Vectors[END_REF] the proof is done for the specific case where x is drawn from a Gaussian over a coset of Z m ; on the other hand, they consider the more general case of an ellipsoidal Gaussian distribution.

Lemma 5.3.3 (adapted from [AR13, Lemma 3.3]). Let ε, r > 0. For any e ∈ Z m , c ∈ R m , if r ≥ √ 5(1 + e ) • ln(2m(1+1/ε)) π , then ∆ e x + y, e < 2ε where x ← D Λ ⊥ q (G )+c,r , y ← D Z,r , and e ← D Z,r √ 1+ e 2 .
Asymptotically, r = Θ( e √ κ) is enough to obtain negligible statistical distance. We stress that the distribution of e does not depend on the coset c.

Proof. Let e = (e, 1) ∈ Z m+1 , c = (c, 0) ∈ Z m+1 and Λ = Λ ⊥ q (G ) × Z. We want to show that ∆ e D Λ+ c,r , D Z, e r ≤ 2ε

The support of e D Λ+ c,r is e Λ + e c = e Λ ⊥ q (G ) + Z + e c = Z. Fix some z ∈ Z. The probability mass assigned to z by e D Λ+ c,r is proportional to ρ r (L z ), where

L z = v ∈ Λ + c : e v = z We define the lattice L = v ∈ Λ : e v = 0 ; note that L z = L + w z for any w z ∈ L z . Let u z = z e 2 r
e, then u z is clearly proportional to e. Observe that u z is orthogonal to r -1 L z -u z , indeed for any t ∈ r -1 L z we have e (tu z ) = 0. From this we have

ρ (t) = ρ (u z ) • ρ (t -u z )
, and by summing for t ∈ r -1 L z :

ρ(r -1 L z ) = ρ (u z ) • ρ r -1 L z -u z
Observe that we have r -1 L z -u z = r -1 (Lc ) for some c in the vector span of the lattice L (because L zru z = L + w zru z and e (w zru z ) = 0). Thus using Lemmas 5.2.5 and 5.3.4 with r ≥

√ 5 (1 + e ) • ln(2m(1+1/ε)) π ≥ η ε (L), we obtain ρ(r -1 L z ) = ρ(u z ) • ρ r (L -c ) ∈ 1 -ε 1 + ε , 1 • ρ r (L) • ρ(u z ) = 1 -ε 1 + ε , 1 • ρ r (L) • ρ z e 2 r e = 1 -ε 1 + ε , 1 • ρ r (L) • ρ e r (z)
This implies that the statistical distance between e D Λ+ c,r and D Z, e r is at most 1 -1-ε 1+ε ≤ 2ε.

In order to conclude the previous proof, we now give a bound on the smoothing parameter of the lattice L. Lemma 5.3.4. Let ε > 0. For any e ∈ Z m , let L be as defined in Lemma 5.3.3. Then we have:

η ε (L) ≤ √ 5(1 + e ) • ln (2m (1 + 1/ε)) π
Proof. We use Lemma 5.2.4 to bound the smoothing parameter of L. Since Λ = Λ ⊥ q (G )×Z is of dimension m + 1 and L is the sublattice of Λ made of the vectors that are orthogonal to e, we have that L is of dimension m. We thus exhibit m independent short vectors of L to obtain an upper bound on λ m (L). We first define the matrix

B =        2 -1 . . . . . . . . . -1 2        ∈ Z (log q)×(log q)
and remark that it is a basis for the lattice Λ ⊥ q (g ). The lattice Λ is then generated by the columns of the matrix: The final proof of Lemma 5.3.1 will necessitate a call to the leftover hash lemma, so before continuing we analyze the min-entropy of x ← D Λ ⊥ q (G )+c,r . Lemma 5.3.5. Let ε > 0, r ≥ η ε Λ ⊥ q (G ) . For any c ∈ R m , we have

B = (b 1 | . . . | b m+1 ) = I n ⊗ B 0 0 1 ∈ Z (m+1)×(m+1) For k ≤ m let u k = b k -b m+1 • e b k ,
H ∞ D Λ ⊥ q (G )+c,r ≥ log (1 -ε) + m log (r) -m Proof. For any v ∈ Λ ⊥ q (G ) + c D Λ ⊥ q (G )+c,r (v) ≤ D Λ ⊥ q (G )+c,r (v 0 ), for v 0 the point of Λ ⊥ q (G ) + c closest to 0 = ρ r (v 0 ) ρ r (Λ ⊥ q (G ) + c) ≤ 1 ρ r (Λ ⊥ q (G ) + c) , since ρ r (v 0 ) < 1 ≤ (1 -ε) r m det Λ ⊥ q (G ) , by Lemma 5.2.6 since r ≥ η ε Λ ⊥ q (G )
The lattice Λ ⊥ q (G ) is generated by the basis I n ⊗ B, with B defined as above, which has determinant 2 log q n = 2 m . The result follows:

H ∞ D Λ ⊥ q (G )+c,r ≥ log (1 -ε) + m log (r) -m
We are now ready to prove Lemma 5.3.1.

Proof. The proof is done in two steps. First, by Lemma 5.3.5, we know that x has min entropy at least log(1ε) + m log(r)m ≥ (n + 1) log(q) -2 log(ε ) -2. Moreover, e x + y is in Z q . Applying the leftover hash lemma (Lemma 5.2.8), we obtain ∆ ((A, Ax, e x + y) , (A, u, e x + y)) < ε where u ←$ Z n-1 q . Now, using Lemma 5.3.3, we know that ∆ e x + y, e < 2ε

Summing the two statistical distances concludes the proof.

Rerandomizing LWE samples

We finally describe a simple application of Lemma 5.3.1. Generating fresh LWE samples for a fixed secret s from a bounded number of samples is very useful, for example to build a public key encryption scheme from a symmetric one. It has already been shown in the succession of papers [Reg05; GPV08; ACPS09] that multiplying a matrix of m LWE samples (A, s A+e ) by a discrete Gaussian x ← D Z m ,r and adding another Gaussian term y ← D Z,r to the error part yields a fresh LWE sample (a , s a + e ) with a somewhat larger Gaussian noise e . Here we have shown that picking x according to a discrete Gaussian distribution over a coset c of Λ ⊥ q (G ) is enough for this rerandomization process. Moreover, we show that the distribution of the final error is independent of the coset c, which will come in handy for hiding homomorphic evaluations. We note that this could be extended to any other lattice with a small public basis (cf. Section 5.4.5), but we mainly focus on Λ ⊥ q (G ) because this is sufficient for our use.

Our scheme: circuit-private homomorphic evaluation for GSW

In this section, we prove that a slight modification of the GSW encryption scheme is enough to guarantee circuit privacy, i.e., that an evaluation of any branching program does not reveal anything more than the result of the computation and the length of the branching program, as long as the secret key holder is honest.

Rerandomizing and scaling GSW ciphertexts

First, we show how we can rerandomize and scale a GSW ciphertext. In the following we write Enc γ (sk, µ) to denote that, when calling the encryption algorithm, the error is sampled from a discrete Gaussian distribution with parameter γ. We let α be the parameter of fresh ciphertexts, and implicitly use Enc (sk, µ) to denote Enc α (sk, µ). Recall from Section 3.4.3 that the form of a GSW ciphertext is

C = -A s A + e + µG.
Using the rerandomization of LWE samples presented in Section 5.3.2, it is possible to generate a fresh encryption of 0 by computing C • G -1 rand (V), where C is an encryption of 0 and V is any matrix in Z n×m q . Lemma 5.4.1. Let r > 0. For any V ∈ Z n×m q , if r = Ω α √ κ m log m , with α being the Gaussian parameter of fresh encryptions, then

C • G -1 rand (V) + 0 y , C ≈ s C , C where C = -A s A + e ← Enc (sk, 0), C ← Enc γ (sk, 0), with γ = r 1 + e 2 .
Proof. Fix v ∈ Z m q and e such that e ≤ Cα √ m, where C is as in Lemma 5. Pr [e = w]

≤ 3 • 2 -κ + Pr e ≥ Cα √ m ≤ 3 • 2 -κ + 2 -Ω(κ)
In the left operand of the third equation we bound the statistical distance by 3 • 2 -κ and in the right operand we bound it by 1. To obtain the last inequality we use Lemma 5.

and have Pr

[ e > Cα √ m] ≤ 2 -Ω(m) ≤ 2 -Ω(κ) since m ≥ κ. By rewriting this distance we have for any v ∈ Z m q C • G -1 rand (v) + 0 y , C ≈ s -u s u + e , C
By writing V = (v 1 | . . . | v m ) and y = (y 1 , . . . , y m ), we have

C • G -1 rand (V) + 0 y = C • G -1 rand (v 1 ) + 0 y 1 | . . . | C • G -1 rand (v m ) + 0 y m
We define the distributions (D i ) 0≤i≤m in which the first i columns of C • G -1 rand (V) + 0 y are replaced with "fresh" -u s u + e and we obtain through a hybrid argument that

∆ C • G -1 rand (V) + 0 y , C , -A s A + e , C ≤ m(3 • 2 -κ + 2 -Ω(κ) )
As a direct corollary we remark that the scaling of a GSW encryption C of µ by a bit a,

defined as C • G -1 rand (a • G) + 0 y
, where y ← D Z m ,r , does not depend on a, but only on aµ.

Circuit privacy: definition and main theorem

We now state our definition of circuit privacy, similar to [IP07, Definition 7], which is stronger than the one given in [Gen09a, Definition 2.1.6] in the sense that it is simulation based, but weaker in the sense that we leak information about the length of the branching program.

Definition 5.4.2 (Simulation-based circuit privacy). We say that a homomorphic encryption scheme E is circuit private if there exists a PPT algorithm Sim such that for any branching program Π of length L = poly (κ) on variables, any x 1 , . . . , x ∈ {0, 1}, the following holds:

(E.Eval (evk, Π, (C 1 , . . . , C )) , C 1 , . . . , C , 1 κ , sk) ≈ s Sim 1 κ , Π (x 1 , . . . , x ) , 1 L , (C 1 , . . . , C ) , C 1 , . . . , C , 1 κ , sk where sk ← E.Setup (1 κ ), C i ← E.Enc (sk, x i ) for i ∈ [ ].
We can now state our main theorem:

Theorem 5.4.3 (Main theorem). There exists a fully homomorphic encryption scheme for branching programs that is circuit private and whose security is based on the LWE assumption with polynomial noise-to-modulus ratio.

Remark 5.4.4. The aforementioned scheme is also multi-hop (see definition in [START_REF] Gentry | i-Hop Homomorphic Encryption and Rerandomizable Yao Circuits[END_REF])

for branching programs, as long as the noise does not grow beyond q/4. This means that the output of an evaluation can be used as input for further computation, while the property of circuit privacy is maintained for every hop. More in detail, the evaluation can be carried out by multiple parties and any subset of these parties is not able to gain information about the branching program applied by an evaluator which is not in the subset, beside its length, input and output, even given access to the secret key.

Modified

Eval algorithm for the GSW encryption scheme

Homomorphic evaluation for branching programs

Here we present our Eval (Π, (C 1 , . . . , C )) algorithm (note that it does not require any evaluation key), which homomorphically evaluates a branching program Π over ciphertexts C 1 , . . . , C . The first state vector is encrypted without noise: the initial encrypted state vector is V 0 = (G, 0, . . . , 0), i.e. V 0 [1] = G and V 0 [w] = 0, for 2 ≤ w ≤ W . Note that G and 0 are noiseless encryptions of 1 and 0, respectively. The encrypted state vector is then computed at each step by homomorphically applying Equation (5.1) and adding a noise term: for t ∈ [L] and w ∈ [W ]

V t [w] ← C var(t) •G -1 rand V t-1 π -1 t,1 (w) + G -C var(t) •G -1 rand V t-1 π -1 t,0 (w) + 0 y t,w (5.2) where y t,w ← D Z m ,r √ 2 . The output of the evaluation algorithm is V L [0] ∈ Z n×m q .
Remark 5.4.5 (Comparison with [BV14; AP14]. Cf. also Table 5.1). The differences between our homomorphic evaluation procedure and the previous ones are as follows:

• We added an additional Gaussian noise to the computation, as captured in the boxed term;

• [START_REF] Brakerski | Lattice-based FHE as secure as PKE[END_REF] uses the deterministic G -1 det (•) whereas [START_REF] Alperin | Faster Bootstrapping with Polynomial Error[END_REF] introduced the randomized G -1 rand (•) for efficiency. Here, we crucially exploit the randomized G -1 rand (•) for privacy.

Simulator. Towards proving circuit privacy, we need to specify a simulator Sim. We first describe a simulator that is given access to the number of times each variable is used and prove that its output distribution is statistically close to the result of Eval (Lemma 5.4.8). We can then pad the branching program so that each variable is used the same number of times. Given the security parameter κ, the length L of the branching program Π, the number of times τ i that Π uses the i-th variable, the final value x f of the evaluation of Π on input (x 1 , . . . , x ), the ciphertexts C i encrypting x i for i ∈ [ ], Sim mimics the way error grows in the states of Eval by doing τ i dummy steps of computation with the i-th variable. This gives a new encryption A f of 0 with the same noise distribution as the ciphertext output by the Eval procedure. Sim then adds the message part x f to this ciphertext and outputs

C f = A f + x f G.
In other words,

Sim (1 κ , x f , (1 τ 1 , . . . , 1 τ ) , (C 1 , . . . , C )) ← i=1 τ i t=1 C i • G -1 rand (0) -G -1 rand (0) + 0 y t +x f G where y t ← D Z m ,r √ 2 for t ∈ [L]
. We note that the sum of 2τ i samples G -1 rand (0) can be sampled at once using the G -1 rand (•) algorithm with a larger parameter r √ 2τ i , and the sum of τ i samples from D Z m ,r √ 2 is close to a sample from D Z m ,r √ 2τ i .

Proof of circuit privacy

We proceed to establish circuit privacy in two steps. We first analyze how the ciphertext distribution changes in a single transition, and then proceed by induction to reason about homomorphic evaluation of the entire branching program.

Step 1. We begin with the following lemma, which is useful for analyzing the output of Equation (5.2). Roughly speaking, this lemma says that if at step t, the state vector consists of fresh GSW encryptions with some noise parameter ζ, then at step t + 1, the state vector is statistically close to fresh GSW encryptions with a somewhat larger noise which depends on the error in the input ciphertext and on ζ.

Lemma 5.4.6. For any x, v 0 , v 1 ∈ {0, 1} and sk = -s, 1 ← KGen (1 κ ), the following holds:

C • G -1 rand (V 1 ) + (G -C) • G -1 rand (V 0 ) + 0 y , C ≈ s V x , C
where

V b ← Enc γ (sk, v b ) for b ∈ {0, 1}, C = A s A + e + xG ← Enc (sk, x), y ← D Z m ,r √ 2 and V x ← Enc ζ (sk, v x ), with ζ = γ 2 + 2r 2 1 + e 2 .
Proof. We begin with a simple identity which is useful in the remainder of the proof:

C • G -1 rand (V 1 ) + (G -C) • G -1 rand (V 0 ) = A • G -1 rand (V 1 ) -G -1 rand (V 0 ) + V x
where A = A s A + e and V 0 , V 1 , C are as defined in the statement of the Lemma.

We now proceed to proving circuit privacy. We will first prove the following lemma, which states that the Eval algorithm presented in Section 5.4.3.1 only leaks the final result of the evaluation and the number of times each variable is used. Lemma 5.4.8. Let E be the GSW scheme defined in Section 3.4.3 with evaluation defined as in this section, and Sim be the corresponding simulator. Then for any branching program Π of length L = poly(κ) on variables, such that the i-th variable is used τ i times, and any x 1 , . . . , x ∈ {0, 1}, the following holds:

(E.Eval (Π, (C 1 , . . . , C )) , C 1 , . . . , C , 1 κ , sk) ≈ s Sim 1 κ , Π (x 1 , . . . , x ) , (1 τ 1 , . . . , 1 τ ), (C 1 , . . . , C ) , C 1 , . . . , C , 1 κ , sk where sk ← E.KGen (1 κ ), C i ← E.Enc (sk, x i ) for i in [ ].
Proof. As shown in Lemma 5.4.7, the final result of the homomorphic evaluation of the branching program Π is of the form

V L [0] ≈ s A s A + f + x f G where A ←$ Z (n-1)×m q , f ← D Z m ,r L and r L = r 2 i=1 1 + e i 2 τ i .
Now we prove that the output of Sim is statistically close to the same distribution. This proof follows from the fact that scaling GSW ciphertexts yields a result which is independent of the argument of

G -1 rand (•). Let A i,t , A i,t ←$ Z (n-1)×m q , f i,f , f i,t ← D Z m ,r
√ 1+ e i , then the joint distribution of the output of Sim and ciphertexts

(C i ) i∈[ ] is S, (C i ) i∈[ ] = i=1 C i τ i t=1 G -1 rand (0) -G -1 rand (0) + 0 y t + x f G, (C i ) i∈[ ] ≈ s i=1 τ i t=1 A i,t s A i,t + f i,t + A i,t s A i,t + f i,t , (C i ) i∈[ ] by Lemma 5.3.1 ≈ s A s A + f , (C i ) i∈[ ]
by Lemma 5.2.2 and summing uniform variables.

The result is the same as the joint distribution of the output of Eval and ciphertexts (C i ) i∈[ ] , thus concluding the proof.

We are now ready to prove Theorem 5.4.3. Main theorem. Theorem 5.4.3 follows from Lemma 5.4.8 by tweaking the Eval algorithm of E: it is sufficient that this algorithm pads the branching program Π so that each variable is used L times. This padding is done by using the identity permutation for all steps after the L-th. After this proof, we discuss more efficient ways to pad branching program evaluations. It is easy to see that this step is enough to reach the desired circuit privacy property: the only information leaked besides the final result is τ i = L.

Padding branching program evaluations. In order to pad a branching program Π that uses the i-th variable τ i times to one that uses the i-th variable L times, we add Lτ i steps, using the identity permutation at each one of these. Given V L [0] the final result of the computation, this padding corresponds to steps t ∈ [L + 1, 2Lτ i ] defined as follows:

V t [0] ← V t-1 [0] + C i G -1 rand (V t-1 [0]) -G -1 rand (V t-1 [0]) + 0 y t,0
Using the same proof as Lemma 5.4.8 the final output will be

V 2L-τ i [0] ← V L [0] + C i 2L-τ i -1 t=L G -1 rand (V t [0]) -G -1 rand (V t [0]) + 0 y t,0 ≈ s V L [0] + C i 2L-τ i -1 t=L G -1 rand (0) -G -1 rand (0) + 0 y t,0
Observe that by using Lemma 5.2.2 we have that

2L-τ i -1 t=L G -1 rand (0) -G -1 rand (0) ≈ s D Λ ⊥ q (G ),r f 2L-τ i -1 t=L 0 y t,0 ≈ s D Z m ,r f
Where r f = r 2 (Lτ i ). We can thus do all the steps at once by outputting

V L [0] + C i • X + 0 y f , where X ← D m Λ ⊥ q (G ),r f
and y f ← D Z m ,r f . We note that X can be sampled using the G -1 rand (•) algorithm with parameter r f instead of r.

Setting the parameters

In this section we show that, for appropriate values of the parameters, the output of the homomorphic evaluation V L [0] decrypts to Π (x 1 , . . . , x ) with overwhelming probability and guarantees circuit privacy.

We first recall the bounds on the parameters needed for both correctness and privacy. Let n = Θ (κ), q = poly (n), m = n log q, α be the Gaussian parameter of fresh encryptions, r be the parameter of G -1 rand (•). Let B = Θ (α √ m) be a bound on the norm of the error in fresh encryptions (using a tail cutting argument we can show that B = Cα √ m is sufficient to have a bound with overwhelming probability), L max = poly(n) be a bound on the size of the branching programs we consider and max = poly (n) an upper bound on their number of variables. Let ε = O (2 -κ ) and ε = O (2 -κ ).

We have the following constraints:

• α = Ω ( √ m) for the hardness of lwe n-1,q,D Z,α

• r ≥ 5 ln(2m(1+1/ε)) π for the correctness of G -1 rand (•) sampling

• r ≥ 4 (1 -ε) (2ε ) 2 -1 m for the leftover hash lemma • r ≥ √ 5 (1 + B) ln(2m(1+1/ε))
π for Lemma 5.3.4

• q = Ω √ mrα (m L max max ) 1/2 for the correctness of decryption

We can thus set the parameters as follows:

• n = Θ(κ),

• L max = poly(n),

• max = poly(n),

• α = Θ( √ n),
• r = Θ (n),

• q = Θ n 5/2

= O rα (m L max max ) 1/2 .
Finally, by a tail cutting argument, q = Θ (r L √ n) = Θ n 5/2 L max max is enough for decryption to be correct with overwhelming probability.

Extension to arbitrary moduli and trapdoor matrices

In this paragraph we show how to instantiate our proofs in a more generic setting.

Our GSW ciphertext rerandomization can be straightforwardly adapted to any matrix H and modulus q, as long as the lattice Λ ⊥ q (H ) has a small public basis, i.e., a small public trapdoor. Observe that the conditions needed to apply GSW ciphertext rerandomization are given in Lemma 5.3.4, which bounds the smoothing parameter of the lattice

L = v ∈ Λ ⊥ q (H ) × Z : e v = 0
and in Lemma 5.3.5 which gives the min-entropy of a Gaussian over Λ ⊥ q (H ). Let β ≥ t i , where T = {t 1 , . . . , t m } is the public trapdoor of H (i.e., T is a small basis of Λ ⊥ q (H )), we show that the previous two lemmas can be proven for H and the parameter r only grows by a factor β.

First, observe that Lemma 5.3.4 aims to find m small independent vectors in L. By noticing that

L = (v, -v e) : v ∈ Λ ⊥ q (H )
Chapter 5

Discussions 91

we can exhibit m small vectors u i = (t i , -t i e) , i ∈ [m] which are of norm

u i ≤ t i (1 + e ) ≤ β (1 + e )
This bound is the one we obtain in Lemma 5.3.4 for Λ ⊥ q (G ) where T = √ 5.

Second, we show that the bound on the min-entropy of Lemma 5.3.5 can be expressed as a function of β, by simply using the fact that det (T) ≤ T m = β m . From this we have the following bound on the min-entropy:

H ∞ D Λ ⊥ q (H )+c,r ≥ log (1 -ε) + m log (r) -m log (β)
This bound is slightly worse than the one we obtain in Lemma 5.3.5 for G (where we had 2 instead of β). However this is not a problem as it is a weaker bound than the one obtained in Lemma 5.3.4.

By using these two lemmas we can rerandomize GSW ciphertexts and ensure circuit privacy for arbitrary modulus q, and any matrix H with public trapdoor by setting the Gaussian parameter of H -1 (•) to r = Θ (βn).

Discussions

We conclude with some considerations and a critical analysis of the results presented in this part of the manuscript. Finally we state some open problems and outline possible directions for future research.

A draw-back of our approach is that it is specific to the GSW cryptosystem and variants there-of, whereas previous approaches based on noise flooding and bootstrapping are fairly generic. Nonetheless, we stress that the GSW cryptosystem turns out to be ubiquitous in many applications outside of FHE, including attribute-based encryption and fully homomorphic signatures [START_REF] Boneh | Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits[END_REF][START_REF] Gorbunov | Leveled Fully Homomorphic Signatures from Standard Lattices[END_REF]. Another issue is that we need to pad the branching program so that each variable appears the same number of times, thus decreasing the efficiency of the evaluation for no real reason. However, one can argue that the impact on efficiency is fairly limited, especially in comparison with generic homomorphic operations. We are optimistic that the additional insights we gained into the noise distributions of GSW ciphertexts will find applications outside of FHE.

Open problems. We conclude with several open problems pertaining to FHE circuit privacy. The first is to achieve circuit privacy against malicious adversaries [START_REF] Ostrovsky | Maliciously Circuit-Private FHE[END_REF]: namely, the result of a homomorphic evaluation should leak no information about the circuit f , even if the input ciphertexts are maliciously generated. Our analysis breaks down in this setting as it crucially uses fresh uniform randomness in the input ciphertexts for left-over hash lemma, and the fact that the noise in the input ciphertexts are small (but does not need to be discrete Gaussian). Another goal is to achieve circuit-private CCA1-secure FHE [START_REF] Loftus | On CCA-Secure Somewhat Homomorphic Encryption[END_REF]; here, the technique that [START_REF] Ducas | Sanitization of FHE Ciphertexts[END_REF] uses to achieve circuit privacy cannot obtain such a result since giving out an encryption of the secret key violates CCA1-security. A third major open problem is to extend the techniques in this work to other FHE schemes, such as those in [BV11a; DM15; HS15].

Introduction

The unstoppable diffusion of new technologies has undeniably changed many aspects of our lives, both in the positive and in the negative. Cryptography in particular can be seen as a double-edged tool: on one hand, it offers effective ways of protecting one's privacy from malicious eavesdroppers, whereas on the other hand, it can help shielding criminals from law enforcement agencies, by making their communications secure and untraceable.

Organized crime (OC) is becoming increasingly diverse in its methods, group structures and impact on society. A new criminal landscape is emerging, marked increasingly by highly mobile and flexible groups operating in multiple jurisdictions and criminal sectors. Internet and mobile technologies have emerged as key facilitators for organized crime, because of the possibility that they offer to communicate in a rapid, efficient, and covert way, thus allowing members of criminal organizations to exchange messages without meeting in person and without incurring the risk of being intercepted. Internet essentially underpins criminal activities like high-tech cybercrime, payment card fraud, audio and visual piracy, drug smuggling, THB (trafficking in human beings), facilitation of illegal immigration, supply of counterfeit commodities, and many other illicit activities.

Especially after the 9/11 terrorist attacks, the old-fashioned manual work of analyzing links between actors and putting them in a graph was no longer suited to the amount of data that had to be processed. A need for more sophisticated techniques to navigate large datasets emerged, and a key role in this sense is played by social network analysis (SNA). This kind of techniques aims at extracting information about social structures through the use of network and graph theories. Concretely, it means that law enforcement agencies have the possibility to collect data about private individuals, analyze the relationships that link them, and investigate their social behavior in order to establish if they pose any threat to the society. In fact, although electronic communications have made organized crime activities less visible to authorities targeting criminal assets, the increasing usage of the Internet and of mobile communications offers new opportunities to investigators to detect signals and to pre-empt organized crime activities, as well as to co-operate effectively and efficiently. For example, new technologies can be used for scanning "weak OC signals", in order to search, fuse, and interpret data collected from several diverse sources. These sources typically include databases of call detail records of many (potentially all) telephone companies in a country, databases of financial transactions (banks, credit cards, etc.), databases of vehicle registrations (linking car plates to the vehicle's owner), databases of biometric features (DNA, fingerprints, etc.), and national databases that contain many details about each citizen (like date and place of birth, job, annual income, etc.).

However, while carrying out their duty, police forces have to comply with the law, and democratic systems protect the rights of citizens, the privacy of their personal data, and that of their communications. Wide-range scanning for weak organized crime signals is typically incompatible with the legal constraints, because it would unduly give power to the executive arm and thereby limit personal freedom. This kind of aggressive behavior from national agencies has already been reported, e.g., by the famous revelations made by former CIA employee and NSA contractor Edward Snowden [START_REF] Greenwald | NSA collecting phone records of millions of Verizon customers daily[END_REF], who exposed pervasive mass surveillance programs. These revelations led to thorough discussions on investigation policies and, to some extent, to their revision. Generally speaking, currently standing laws prescribe that interference with the right to privacy and to the protection of personal data should be necessary and proportionate to the legitimate goal they are aimed at, and not excessive, arbitrary, or discriminatory. Also, it is worth noting that failing to comply with laws and regulations would expose police forces to legal sanctions and public protests, but could also have the disastrous side effect of totally invalidating legal cases against OC members, who are known to benefit from top-quality legal assistance. Extensive surveillance: an example from the news. As an example of how extensive investigations can lead to issues with freedom and privacy, let us consider the following case, which happened in the United States [And10]. Between 2009 and 2010, 16 robberies were carried out in rural locations of Arizona by two men, known as "the High Country bandits". Although bank surveillance footage was available to investigators, this proved to be of little use, since both men were using jackets, ski masks, and gloves. After bringing the FBI into the case, the investigators found a witness who said that he had noticed a suspicious man hanging out by the bank a couple of hours before the robbery, while talking on a cell phone. The FBI then asked a judge to approve a full cell tower dump, which is a procedure in which wireless operators turn over the records of every cell phone that registered with a particular tower at a particular time. This procedure was approved and executed for the four most rural locations where robberies had taken place, in order to minimize the number of extraneous telephone numbers that would show up in the tower dumps. It should be noticed at this point that tower dumps are obtained without a warrant: they use a "court order", which still implies some judicial supervision, but to a much lesser extent than an ordinary warrant (there is no need for a "probable cause"). This implies that the government could potentially access location information for a vast number of people, without having any warrant. In particular, during the investigations on the robberies, the FBI received more than 150 000 telephone numbers from these tower dumps. Intersecting the records that had been registered in the locations of the robberies gave one specific phone number that, through more interaction with a judge, finally gave a name. Subsequent investigations led to the capture of both perpetrators, thus solving the crime. Although the conclusion of the investigation was positive, this story leads to some privacy-related questions. In fact, several judges (e.g., [START_REF] Owsley | The Fourth Amendment Implications of the Government's Use of Cell Tower Dumps in its Electronic Surveillance[END_REF]) state that these tower dumps are to be considered "searches" under the Fourth Amendment, and thus require a full warrant backed by evidence of "probable cause". Also, the Supreme Court has ruled [Uni12] that warrantless GPS tracking of a suspect is not allowed. In the case of tower dumps, it is true that they do not provide the precision of GPS tracking, but it is equally true that they compromise the privacy of many people, and not just one. Furthermore, those whose records are collected in the process are never notified of the fact.

From this story, it is clear that there is a potential conflict between the need to conduct thorough investigations and data privacy rules, also because the rules and their interpretation are not always clear and agreed upon. Such data privacy rules are even more stringent when it comes to the collaboration between investigators from different agencies and countries, because of organizational issues, bureaucratic hurdles, differences in legislations, different political views of the respective governments, . . . . There is then a conflict between safety and privacy, and the fundamental paradox that arises from this picture is that protecting some rights (privacy) makes it more difficult to protect other rights (security).

Use-case: cross-border cooperation between law-enforcement agencies.

A typical case of how privacy related regulations can get in the way of police investigations is represented by cross-border collaboration between law enforcement agencies, i.e., a situation where two agencies, based in two different countries, want to exchange information, or to make the information they possess available to partner agencies. Note that here we are not concerned with how a certain set of records was obtained; in this use case we focus on how these records can be shared while respecting the citizens' privacy to the greatest possible extent. This use case is already regulated by a EU framework that was introduced in 2008 by EU Council Decision 2008/615/JHA [08a] and EU Council Decision 2008/616/JHA [08b], which applied the previously established Prüm Convention [Uni05] to all the member states. These decisions describe a framework in which member states can grant one another access rights to their automated DNA analysis files, automated dactyloscopic identification systems or vehicle registration data via a two-step process: the first step is a hit/no-hit system, that returns whether the query has a match in the target database (and whose result should be available in less than 15 minutes); in case of a positive answer, the second step is a request for specific personal data related to the result of the query.

The framework currently in place still presents issues regarding the protection of citizens' privacy; for example, the country that hosts the database receives queries in the clear. This amounts to knowing what the other country is looking for, which, in some cases, might be undesirable. Also, the cryptographic standards which are used (AES 256, RSA 1024, SHA1) are not sufficiently adequate and do not take into account the most recent developments in research, as far as constructions and cryptanalysis are concerned. Moreover, at the time the decisions were produced, several cryptographic primitives like Fully Homomorphic Encryption (FHE) were not known to exist, so the results that can be achieved now are largely more sophisticated than what was imaginable in 2008. Thanks to the new possibilities opened by progresses in cryptographic research, the privacy model can be considerably strengthened, in order to achieve a framework that allows for the exchange of information without compromising the citizens' right to privacy.

Problem statement and overview of the results. We now proceed to outlining the problem we consider and the goals we want to achieve. As in [START_REF] De Cristofaro | Efficient Techniques for Privacy-Preserving Sharing of Sensitive Information[END_REF], we assume a party, say France (FR), wants to query a database held by another party, say Germany (DE), on a certain input XYZ; furthermore, we assume that both countries recognize the authority of a trusted party, say a Judge (JU). The basic property that we want to achieve is that DE should not learn FR's query, i.e., XYZ. The solution that we propose actually achieves more than this, namely

• FR learns no more than whether there is a hit/no-hit on the data XYZ and, if authorized by JU, which records match XYZ;

• DE does not learn anything (not even XYZ), but the possible data it would be legally obliged to provide after a successful match;

• JU learns the query XYZ but not the associated data (i.e., to whom the profile corresponds, etc.), even if he allows the query.

As already stated, the hit/no-hit part should complete in less than 15 minutes. The rest of the protocol is not strictly time-bounded by any regulation, and this kind of application is usually not time-critical. Nevertheless, we consider that the protocol should complete in a reasonable amount of time, in order to provide necessary information in a timely and usable manner.

We now introduce two fundamental cryptographical primitives, called Private information retrieval and Oblivious transfer, which are tightly linked to the problem at hand.

Private information retrieval

In cryptography, a private information retrieval (PIR) protocol is a protocol that allows a user to retrieve an item from a database hosted on a server, without revealing to the server which item is retrieved.

It is trivial to notice that there is an immediate protocol that provides perfect security for the user: the server simply sends the entire database to the user, who is then able to read the information it needs. Obviously, this reveals nothing about the user's query, since nothing is submitted to the server. However, it is clear that this kind of protocol is likely to be totally impractical for any realistic use-case because of the communication costs. The goal then becomes to design a protocol with a lower communication complexity; in this sense, [START_REF] Di Crescenzo | Single Database Private Information Retrieval Implies Oblivious Transfer[END_REF] defines as non-trivial any protocol whose communication complexity is less than the size of the entire database. The problem of PIR was introduced by Chor et al. in 1995 [START_REF] Chor | Private Information Retrieval[END_REF] in the information-theoretic setting, and by Kushilevitz and Ostrovsky in 1997 [START_REF] Kushilevitz | Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval[END_REF] in the computational setting. Several protocol were presented in subsequent works, e.g., [START_REF] Julien | A New Efficient All-Or-Nothing Disclosure of Secrets Protocol[END_REF][START_REF] Chang | Single Database Private Information Retrieval with Logarithmic Communication[END_REF][START_REF] Lipmaa | An Oblivious Transfer Protocol with Log-Squared Communication[END_REF].

Note, however, that PIR protocols do not ensure server security, meaning that the user can retrieve more than what it queries for. This enhanced security guarantee is captured by the definition of oblivious transfer, which is presented next.

Oblivious transfer

In private information retrieval protocols, the security requirement is that the server should not learn the user's query. However, nothing is said about what the user is allowed to learn, which could be more than what he queries for. In fact, in the most trivial protocol where the entire database is sent from the server to the user, it is clear that the user can learn all the records. Instead, oblivious transfer (OT) introduces a new security requirement. Let us consider the case where a server is holding a database with records x 1 , x 2 , . . . , x n and a user wants to learn x i for some i. At the end of the OT protocol, the server should not learn i, whereas the user should not learn x j for any j = i. This is called 1-out-of-n oblivious transfer, the simplest case being n = 2, i.e., the server has a database with two records and the user obliviously obtains one of the two. An important result by Crepeau [START_REF] Crépeau | Equivalence Between Two Flavours of Oblivious Transfers[END_REF] showed that 1-out-of-2 OT and 1-out-of-n OT are equivalent. In the literature, several OT protocols have been presented, culminating in a very simple and efficient proposal by Chou and Orlandi [START_REF] Chou | The Simplest Protocol for Oblivious Transfer[END_REF], based on the hardness of the well-established DDH assumption [START_REF] Boneh | The decision Diffie-Hellman problem[END_REF].

Our contributions

In this part of the manuscript, we present a protocol that allows a user to retrieve a record from a database held by a server, without revealing which record has been queried. Furthermore, the user learns only the record (or records, in case of multiple matches), that corresponds to its query. This means that our protocol respects the security requirements of oblivious transfer. However, the specific application for which the protocol is designed takes into account that the user can submit several queries (provided they are authorized by the trusted party, referred to as "the Judge"). This means that, through several executions, the querying party can learn up to the entire database. For this reason, we can say that this is an oblivious transfer protocol if a single execution is considered, whereas the definition is not clear in case of multiple executions. In any case, the protocol always achieves the PIR requirement, meaning that the server never learns the user's query. This protocol is inspired by [START_REF] Boneh | Private Database Queries Using Somewhat Homomorphic Encryption[END_REF].

The basic principle of this use case consists in using homomorphic encryption (HE) to encrypt databases, while enabling data aggregation in the Cloud (for authorized users). Figure 6.1 gives a high-level intuition on the steps of the protocol.

Our protocol

We now describe our protocol for private information retrieval. Initially, all the operations will be described at a high level; then we will provide implementation details regarding each one of them.

In our protocol, we consider three actors: the querying party (France, or FR), the responding party (Germany, or DE), and the trusted party (Judge, or JU). We assume that the database held by DE is structured as follows: each record is composed of a unique ID (w.l.o.g., we can assume it is numerical), and by a number of fields corresponding to some features (e.g., the person's name, surname, car plate, phone number, address, ...). The protocol then goes through a one-time setup phase as follows:

1. As a first step of the protocol, DE generates the inverted database, which is a dataset where each occurrence of each feature is associated to all the IDs that match. For example, consider the toy-example of database in Table 6.1; then the inverted database will look like that presented in to any other party. In particular, the part "Feature=..." is converted into a search token via a pseudo-random function (PRF), whereas the IDs are considered as roots of a polynomial p(x), which is subsequently encrypted coefficient by coefficient. For example, an entry in the encrypted inverted database might look like

( PRF k DE ("DNA D19S433 = 7.8") , Enc k DE (I) )
where I is the set of indices in the database of the individuals for which the DNA marker D19S433 is equal to 7.8, encrypted with a key k DE only known to DE.

The so-computed encrypted inverted database can then be safely published onto the Cloud and made accessible to anyone. The underlying assumption is that it reveals no information to anyone who does not hold the secret key or does not interact "properly" with DE to obtain the disclosure of relevant information.

These steps have to be performed at the beginning of the protocol (setup time), and every time the database needs to be updated. Note that, in this latter case, it is possible to update only parts of the encrypted inverted database, thus saving bandwidth.

After the setup has been completed, FR (i.e., the querying party) can interact with the other actors of the protocol in order to obtain an answer to a certain query. The steps are different for different types of queries. In details, we consider three possible requests, called simple query (FR wants all the records that match a certain condition ξ), disjunction query (all the records that match at least one of two conditions, i.e., ξ 1 ∨ξ 2 ), and conjunction query (all the records that match simultaneously two conditions, i.e., ξ 1 ∧ ξ 2 ). We now describe the steps of the protocol for each of these cases.

Simple query. In the case of a simple query, the protocol proceeds as follows:

3. FR and DE engage in a simple sub-protocol that allows them to obliviously compute the search token Θ corresponding to FR's query ξ. This means that, on private inputs ξ for FR and sk for DE, FR will be able to compute a search token which is a function of ξ and sk, without learning anything on sk, and without revealing anything on ξ.

Referring to the example presented before, FR and DE can obliviously compute PRF k DE ("DNA D19S433 = 7.8") 4. After obtaining the search token Θ, FR can check whether there is a match for it in the inverted database, which is publicly available. Notice that this will give FR no information on the records that match (if any), because the inverted database is encrypted. If there is no match, the protocol terminates.

5. After verifying that there is a match, FR sends relevant information to the the trusted party JU. This will include the query itself and the search token, together with some supporting evidence that demonstrates why the query is legal and should be allowed.

6. The trusted JU verifies that the supporting material is indeed acceptable from a legal point of view and, if satisfied, fetches from the inverted database the encrypted polynomial corresponding to the search token, signs it with his secret key, and hands it back to FR. Again, with reference to the example shown before, JU will send

Enc k DE (I) , Sig k JU (Enc k DE (I)) ,
where k JU is JU's secret key.

7. FR forwards this signed encrypted polynomial to DE.

8. DE verifies JU's signature and, if everything is correct, decrypts the polynomial, calculates its roots (i.e., the IDs), and sends to FR the information on those records.

These steps are summarized and depicted in Figure 6.2.

An attentive reader might have noticed that there is a simple cheating strategy for FR: when interacting with JU, it could present a legally valid query, together with a random search token. This way, the trusted JU might be tricked into authorizing something different from what it thinks. In reality, it will be clear in the section about implementing the protocol that JU has an easy way of verifying that the search token indeed corresponds to the query, thus preventing this kind of attack. Disjunction query. In the case of a disjunction query with conditions ξ 1 and ξ 2 , the protocol proceeds as follows:

3. FR and DE repeat twice the simple sub-protocol for oblivious computation of search tokens. At the end of this phase, FR will have search tokens Θ 1 and Θ 2 , corresponding to conditions ξ 1 and ξ 2 .

4. After obtaining the tokens, FR checks in the inverted database. If neither of the tokens gives a match, then the protocol terminates, because the union of the two results is guaranteed to be empty.

5. After verifying that there is a match, FR sends relevant information to JU. This will include both queries and both search tokens, together with material to support the case.

Disjunction query

France Germany Judge -----------------------------------------→ verify & sign Σ := signed enc. of polynomial ← -----------------------------------------Σ verify & find roots disclose information Figure 6.3: Protocol for the case of a disjunction query. tokens. At the end of this phase, FR will have search tokens Θ 1 and Θ 2 , corresponding to conditions ξ 1 and ξ 2 .

r 1 , r 2 ←$ Z N y 1 := H (ξ 1 ) • r e 1 y 2 := H (ξ 2 ) • r e 2 y 1 , y 2 z 1 := y d 1 z 2 := y d 2 z 1 , z 2 st 1 := z 1 • r -1 1 st 2 := z 2 • r -1 2 check_match (st 1 ) check_match (st 2 ) ξ 1 , ξ 2 , st 1 , st 2 , supporting material
4. After obtaining the tokens, FR checks in the inverted database. If at least one the tokens gives no match, then the protocol terminates, because the intersection of the two results is guaranteed to be empty. If this is not the case, then it is possible that the intersection is non-empty.

5. FR and DE engage in a sub-protocol to verify whether the intersection is non-empty. First, FR picks two random (not encrypted) polynomials r 1 (x) and r 2 (x), under some conditions that will be explained in the part regarding the implementation. Then, it homomorphically computes the polynomial q(x)

:= p 1 (x) • r 1 (x) + p 2 (x) • r 2 (x).
Notice that (a) the polynomial q(x) is computed from both encrypted and not encrypted polynomials, but the result is an encrypted polynomial, and (b) the set of roots of q(x) is at least composed of the intersection of those of p 1 (x) and p 2 (x), but could potentially be larger. In fact, for example it might happen that r 1 (x) and r 2 (x) have a root in common, which is not a root of either p 1 (x) or p 2 (x): if this happens, then this operation has introduced a spurious root, that needs to be handled with great care. The reason is that introducing such a root amounts to adding an unrelated ID to the list of results, thus creating a false positive. Also, it can happen that a spurious root is introduced even if there is no common root among the polynomials. We address the issue and propose a solution in Section 6.4.2. Finally, FR sends q(x) to DE.

6. DE decrypts q(x) with its secret key, computes its roots and sends 1 to FR if there is at least one root (cf. Sections 6.4.1 and 6.4.2 for more details); otherwise DE sends 0.

7. If FR receives 0, then the protocol terminates, as the intersection is empty. If this is not the case, FR sends relevant information to JU. This will include both queries and both search tokens, together with material to support the case.

8. JU verifies the supporting material and proceeds if it is satisfied. If this is the case, JU fetches the two encrypted polynomials p 1 (x) and p 2 (x) corresponding to search tokens Θ 1 and Θ 2 , then picks fresh random polynomials r 1 (x) and r 2 (x), computes

q (x) := p 1 (x) • r 1 (x) + p 2 (x) • r 2 (x)
, signs it, and hands it back to FR.

9. FR forwards this signed encrypted polynomial to DE.

10. DE verifies JU's signature and, if everything is correct, decrypts the polynomial, calculates its roots (i.e., the IDs), and sends to FR the information on those records.

These steps are presented in Figure 6.4. Since the polynomials r 1 (x) and r 2 (x) need not be encrypted, a linearly homomorphic encryption scheme is sufficient for these steps to go through.

In conclusion, we need an encryption scheme that can encrypt integers modulo some prime q and can support at least one homomorphic multiplication between ciphertexts. Also, there is no need for a public-key encryption scheme, as the polynomials will be encrypted under DE's secret key. In the following, we present the DGHV encryption scheme [START_REF] Van Dijk | Fully Homomorphic Encryption over the Integers[END_REF], that we extend and use to instantiate our protocol.

Z q , and two DGHV ciphertexts c 1 , c 2 such that c i ← Enc (sk, µ i ), the ciphertext c

× := (c 1 • c 2 ) mod x 0 is a DGHV ciphertext of µ 1 • µ 2 .
Once again, showing that this holds is rather easy:

c × mod x 0 = p (s 1 s 2 p + s 1 µ 2 + s 2 µ 1 + s 1 r 2 q + s 2 r 1 q) + q (r 1 r 2 q + r 1 µ 2 + r 2 µ 1 ) + µ 1 µ 2 mod s 0 p = p [(s 1 s 2 p + s 1 µ 2 + s 2 µ 1 + s 1 r 2 q + s 2 r 1 q) mod s 0 ] + q (. . . ) + µ 1 µ 2 .
It then follows that c × mod p mod q = µ 1 µ 2 , provided that r 1 r 2 q 2 < p.

Remark 6.3.1 (On reduction modulo x 0 (cf.[DGHV10, Section 3.3.2])). Note that reducing modulo x 0 is not necessary for correctness or security to hold. This operation is merely useful for efficiency, i.e., for reducing the size of the ciphertext. In the original paper, the authors remark that publishing an exact multiple of the secret p makes the approximate GCD problem "clearly easier". However, they also note that no attack is known to work for this "easier case" and not for the general one.

Implementing our protocol

The components that had to be developed in order to fully implement the protocol are:

• An instantiation of the DGHV encryption scheme for encrypting and decrypting integers, and for performing the required homomorphic operations on ciphertexts;

• A hash function, that will be used for the part related to search token computation and signatures;

• A sub-protocol for oblivious computation of the search tokens that, starting from FR's and DE's private inputs (i.e., the query ξ and the secret exponent d, respectively), allows FR to compute the search token without revealing anything on ξ, and without learning anything on d;

• A signature scheme for JU to sign encrypted polynomials and other parties to verify the signatures;

• A way to allow all the actors to communicate with each other.

As a coding language, we chose C ++ , in order to benefit from both the speed that is usually associated to C implementations, and from higher level constructs that are usually linked to object-oriented languages. Since the DGHV encryption scheme requires handling large integers, we implemented it from scratch by taking advantage of GMP (the GNU multiple precision arithmetic library) [START_REF] Granlund | GNU MP: The GNU Multiple Precision Arithmetic Library[END_REF]. This library also provides several remarkably useful features, such as the generation of (probably) prime numbers through the Miller-Rabin primality test, the computation of the modular inverse of an integer, etc.

For the hash function component, we exploited the library Crypto ++ [START_REF] Dai | Crypto++ Project[END_REF] which, among others, contains an implementation of the hash functions SHA-2 and SHA-3. Particular attention should be given to how we hash strings and polynomials, keeping in mind that the result must be numerical, in order for the protocol to go through. For the string case, we proceed as follows: through the functions provided by Crypto ++ , we calculate the hash of a string as a raw sequence of bytes. Then, via a simple C ++ function, we convert this byte sequence to hexadecimal form, and we use the resulting string to initialize an integer in base 16. The result is then mpz_class(hash::sha3_256(myString), 16), where mpz_class is the type that GMP associates with integers of arbitrary size. Providing a sensible and secure hash of an encrypted polynomial can result in a tricky task. For example, one could provide a separate hash for each encrypted coefficient. Although very simple, this approach leads to an immediate attack: if the encrypted coefficients are hashed and signed one by one, a simple shuffle will result in a validly signed encrypted polynomial, which is different from the initial one. This amounts to forging a signed encrypted polynomial. An alternative approach would be that of simply concatenating all the encrypted coefficients (which, as DGHV ciphertexts, are simple integers) into a single string and hash it. The drawback of this approach is that, in case of very long polynomials, this string can exceed the maximum string length permitted by the C ++ standard. Also, the string would have to be stored in the RAM memory, thus consuming a considerable amount of resources. A viable approach seems the following: hash the first coefficient, concatenate the second coefficient, hash the result, concatenate the third coefficient, hash the result, and so on. Although there is apparently no clear reason not to follow this way, we decided to take full advantage of the interface provided by Crypto ++ to do the following: given an encrypted polynomial, described as a sequence of encrypted coefficients, we construct a "SHA object", which is updated with all the coefficients one by one. In the end, when all the encrypted coefficients have been processed, we produce the final digest as a raw sequence of bytes. Then, analogously to what described before, we convert it to an hexadecimal string, and we use the result to initialize an integer in base 16.

For search token calculations, as in [START_REF] De Cristofaro | Efficient Techniques for Privacy-Preserving Sharing of Sensitive Information[END_REF], we use RSA decryption algorithm as a PRF. Given a string ξ and a hash function H, the search token associated to ξ will be (H (ξ)) d mod N , where d is the secret RSA exponent and N is the RSA modulus. In Figure 6.5 we show a simple protocol between Alice (that holds ξ) and Bob (that holds d), that allows Alice to recover (H (ξ)) d mod N without learning anything about d and without revealing anything about ξ. We naturally assume that the public RSA exponent e and the RSA modulus N are known to Alice (and to everybody else).

As a signing mechanism, we employ RSA signatures: we then assume JU is equipped with a private key (i.e., a secret exponent), whereas its public key (i.e., a public exponent) is known to all the parties. Then, signing any message m simply consists in taking the hash of m and raising it to the secret exponent. Verification is as immediate as raising this signature to JU's public exponent and checking that the result corresponds to the hash of the message m.

In order to provide the actors with a way to communicate with each other, we implemented a series of simple web servers, that listen for requests and serve them accordingly. For the demo that we coded and successfully demonstrated during several review meetings, everything was running locally on a simple laptop computer. However, the modular structure of the application makes it easy to deploy its different components to remote hosting services. The structure of the system is the following:

• A web server for the party that own the database (DE). This server will expose a service that receives requests and performs several actions, like raising the input to the secret exponent d, or verifying signatures and disclosing information.

• A browser application for the party that wants to execute a query (FR). This application will take some input (e.g., through a keyboard), and perform all the operations that the querying party has to go through during the protocol (blinding the query, unblinding the answer for calculating the search token, calculating the conjunction of two polynomials, submitting requests to the trusted party, . . . ). This component will also take care of rendering the information that is received from the party that owns the database, i.e., it will provide a visual representation of the records that match the query.

• A web server for the trusted party (JU). This server will expose a service that receives queries from the querying party and, after verifying that the case has valid legal grounds (this part is obviously omitted), proceeds with signing encrypted polynomials and sends back the result to the querying party. This signed material will allow for the disclosure of relevant information.

• A web server for the encrypted inverted database. This server is actually performing no "active operation". Everything it does is exposing a list of encrypted records in the form of searchToken, encCoeff 0 , encCoeff 1 , . . .

In the demo, this component was not properly implemented: the encrypted inverted database simply resides on the local machine.

For setting up and running web servers, we used Flask [START_REF]web development, one drop at a time[END_REF], a Python framework that allows one to simply set up a web server that listens on a predefined port and, upon receiving requests, runs a Python script in order to serve them. The basic architectural concept is that the C ++ executable provides all the functions that are necessary to all the parties to engage in the protocol, and the Python scripts interface with this executable (e.g., by passing command line arguments) to perform the actions that are required. Messages between the parties are encoded in JSON format, which makes it easy to serialize and deserialize any kind of object, in several coding languages. For this part, we used "JSON for modern C ++ " [START_REF] Lohmann | JSON for modern C++[END_REF] which, through a single header file, provides all the functions that are needed to serialize and deserialize objects in a fast and simple way. In order to mimic the communication process, i.e., sending and receiving files containing messages, JSON files were placed in specific folders that acted like communication channels between the parties. Naturally, this means that a real deployment of the protocol should take into account elements like network latency and failures. However, given the current state of the art for internet connections (e.g., extremely fast connections through optical fiber), we do not expect this to be a major hurdle. Finally, in Figures 6.6 to 6.8 we present screenshots of the web interface we developed, that show the perspective of the querying party, the trusted party, and the responding party, during the execution of a disjunctive query.

How to choose the random polynomials for conjunction queries

When performing a conjunctive search query ξ 1 ∧ ξ 2 , the protocol requires choosing two random polynomials r 1 (x), r 2 (x), and then computing p (x) := p 1 (x) • r 1 (x) + p 2 (x) • r 2 (x), where p 1 (x), p 2 (x) are the polynomials whose roots are the indices that match queries ξ 1 , ξ 2 . In order to decrease the probabilities of having spurious roots (cf. Section 6.4.2), we define a set of "good roots" G and a set of "fake roots" F. We assume that the description of these sets is public, meaning that any party can distinguish if a root belongs to G or to F. Good roots are those that correspond to indices which appear in the database, whereas fake roots do not. When choosing the random polynomials, we will take them so that their roots are in F. Any potential collision between the roots will introduce an additional root in the polynomial p (x), but will be automatically ignored because it belongs to F. However, it turns out this is not enough to prevent false positives.

Handling the "false positives"

As already mentioned in Sections 6.2 and 6.4.1, the way we handle conjunction queries might introduce spurious roots. In details, let p 1 (x) and p 2 (x) be two polynomials whose roots are the elements of the set I 1 and I 2 , respectively. Then, if we pick two random polynomials r 1 (x) and r 2 (x), we have that the set of roots of p (x) := p 1 (x) • r 1 (x) + p 2 (x) • r 2 (x) is at least I 1 ∩ I 2 . This is obvious for the following reason: ∀y ∈ I 1 ∩ I 2 , we have q(y) = p 1 (y) • r 1 (y) + p 2 (y) • r 2 (y) = 0 • r 1 (y) + 0 • r 2 (y) = 0.

Moreover, following an analogous reasoning, let R 1 , R 2 be the set of roots of random polynomials r 1 (x), r 2 (x), respectively. It is obvious that any root that belongs to R 1 ∩ R 2 will also be a root of p (x). However, as already mentioned in Section 6.4.1, this will not be a problem since R 1 ⊆ F and R 2 ⊆ F, meaning that this kind of root will be rejected because it belongs to the set of "fake roots". However, it can also happen that there exists a y such that p (y) = 0, y ∈ G, y / ∈ I 1 ∩ I 2 . This means that the root is accepted as corresponding to a record in the database (because it belongs to G), but it represents a false positive, because it does not belong to I 1 ∩ I 2 . Avoiding this situation is extremely important, since allowing this would be the equivalent of "framing an innocent". In order to prevent this from happening, we chose to do the following: we repeat the entire procedure several times and, in the end, we take the intersection of the results. This means that we fix a parameter N_REPS and then we pick random polynomials r (1) 1 (x), r (x) , compute p (1) (x), p (2) (x), . . . , p (N_REPS) (x) as shown before, and then take the intersection of their roots (that belong to the set of good roots G). It is easy to see that the probability of introducing spurious roots decreases rapidly as N_REPS increases. In the implementation, we take N_REPS = 3.

Concrete parameters and benchmarks

We now give the concrete parameters used in the implementation, and an analysis of the communication complexity of the protocol. The timings clearly depend on the environment in which the protocol is deployed, i.e., on the distance between the parties, and especially on the speed of the network. Beyond the notation already used in this chapter, we also denote by N the number of records in the database, by ν the number of features per record (e.g., DNA markers, fingerprint details, car plate numbers, . . . ), by n the number of records associated to each tag (in the inverted database), by k the number of linear combinations used for conjunctive queries (previously called N_REPS), and by f the maximum probability of false positives that we are willing to tolerate.

The parameters must satisfy the following relationships:

• q ≥ N f 1/k (see [BGH+13, Lemma 1])
• ρ = 2κ, to prevent the improved gcd attack by Chen and Nguyen [START_REF] Chen | Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers[END_REF], which has complexity O 2 ρ/2

• η > 2ρ + 2 log q, to ensure correct decryption after a single multiplication

• γ = η 2 ω (log κ), to prevent the orthogonal lattice attack. To be conservative, one can take γ = 8η 2

In the implementation, we choose the following settings:

• N = 10 4

• f = 2 -32 ≈ 10 -9.63

• κ = 128

This leads to the following choice of parameters:

• k = 3

• q ≈ 10 7.21

• ρ = 256

• η = 560

• γ = 2508800

In the polynomials representing the list of indices, each (encrypted) coefficient is approximately 2508800 bit long. Since JSON encodes all the values as text characters (using base 10 representation), the size of each encrypted coefficient is approximately 755 KBytes.

Assuming each record in the database has ν features, the total size of the inverted database is thus

N • ν

Bandwidth requirements

Given the description of the protocol presented above, it is now easy to compute the communication complexity of the protocol, for each possible type of query. The final results are presented in Table 6.3.

Discussions

The protocol we presented improves on the protocol currently in place for cross-border cooperation between law enforcement agencies, since it preserves the privacy of the querying party's request. However, our protocol still presents issues and missing features, that we address in the following.

First of all, giving the querying party the ability of knowing whether the intersection is empty or not without the trusted party's authorization, is potentially dangerous because it might cause unwanted leakages. The idea behind this was to limit the need for trusted party's involvement in the protocol to the actual information disclosure moment, in order to limit the workload of the "Judge". A possible fix for this potential issue is that of not allowing any decryption on the responding partner's side without a trusted signature. This would mean that the querying partner has first to obtain a "preliminary authorization" for knowing whether the intersection is empty or not, and then a "final authorization" to obtain the database records, in case the intersection is non-empty. These modifications clearly depend on the legal constraints that one wants to enforce. An alternative solution is that of discarding the step that aims at computing whether there is a match, and execute the protocol until the end in any case. There is, of course, a trade-off: on one hand, this limits the workload of the Judge to having to compute just one signature, and it also solves the problem of the leakage that we described above; on the other hand, this might lead to performing "useless" computations, that would have been avoided, had the querying party known that the intersection is empty.

Another potential flaw in the protocol that we presented is that, after computing the search token, the querying partner is able to determine how many matches there are just by looking at the encrypted inverted database. In fact, it is sufficient to count the number of (encrypted) coefficients to determine the degree of the polynomial and, thus, the number of roots, i.e., the number of record IDs. This clearly does not reveal anything on the records themselves, but for some reasons one might want to avoid leaking this piece of information. In order to achieve this goal, the simplest strategy appears that of padding the degree of the polynomials by adding roots in F to the real IDs. This way, we can enforce the constraint that all the polynomials have the same degree, thus leaking no information about the number or real database records.

Finally, one might want to combine more than two queries, in any potential way. For example, given requests ξ 1 , ξ 2 , ξ 3 , one might want to obtain the records that match ξ 1 ∧ξ 2 ∧ξ 3 , or (ξ 1 ∨ ξ 2 ) ∧ ξ 3 . This is clearly possible by executing several times the protocol that we presented, but intermediate queries might not be allowed by the trusted Judge. For example, in order to obtain the records that match (ξ 1 ∨ ξ 2 ) ∧ ξ 3 , one might execute the protocol to obtain the matches for (ξ 1 ∨ ξ 2 ), then execute it again to obtain the records that match ξ 3 , and then manually compute the intersection. However, this reveals more than computing the final result directly, and this might break some constraints. The solution is to tweak the choice of parameters so that more homomorphic operations are allowed (for example, in order to support more multiplications). If one wants to enable an unbounded number of unions and intersections, then bootstrapping appears to be necessary.

Conclusions

If introduced on a large scale and in real-world scenarios, fully homomorphic encryption (FHE) would have enormous consequences for people's privacy, allowing them to use remote services hosted on untrusted servers, without disclosing personal information. As of today, the main obstacle towards this goal is efficiency: existing solutions provide all the necessary features, but they remain generally cumbersome when trying to achieve full-fledged FHE, that allows for unbounded computations. A more viable alternative is instantiating application-specific somewhat homomorphic encryption (SHE) schemes, that do not rely on bootstrapping, and that allow for the computations required by that particular application. Naturally, this depends on the application itself, and on how complex the computational tasks are.

In this manuscript, we first surveyed the area of FHE (cf. Chapter 3), and then we presented some works aimed at improving FHE both from a theoretical and a practical point of view.

In Chapter 4, we presented a new framework for evaluating a neural network on encrypted inputs, thus making sure that the user's data is not accessible to the server, while still allowing the user to obtain predictions based on previously-trained and remotely-held cognitive models.

In Chapter 5, we focused on the problem of circuit privacy. We improved on previous works from the point of view of simplicity and efficiency, in order to provide servers with an easy way to ensure that the results of homomorphic computations do not leak information about the algorithm that has been applied. This is particularly interesting from the viewpoint of a company, wanting to provide users with data processing services, without revealing potentially critical and proprietary algorithms. The result that we obtain, with some caveats, is that the final result of the computation looks (almost) like a fresh ciphertext of the result, thus making sure that no information on how this result was derived (i.e., the algorithm) is contained therein.

Finally, in Chapter 6, we presented and implemented a protocol for private information retrieval. The project's goals are mainly to (1) improve upon the protocol currently in place at European level for cross-border cooperation between law enforcement agencies, and (2) to demonstrate that homomorphic encryption can be practical for certain applications. In this work, we do not take advantage of homomorphic encryption schemes stemming from the assumed hardness of lattice problems, but we focus on a different class of schemes, arising from the assumed hardness of the approximate GCD problem (cf. Definition 2.4.6).

Open questions

Given the double nature (both theoretical and practical) of the works proposed, there are a number of questions that remain open, and that can serve as guidelines for future research. Some of these questions were already mentioned in the related chapters of this manuscript: we report them here for better clarity.

Homomorphic evaluation of neural networks

Question 7.1. In the framework that we proposed, called FHE-DiNN, we are able to homomorphically evaluate a neural network only after a severe simplification of the model.

Chapter 7

7.2 Open questions 117

Namely, we have to discretize the inputs, the weights and biases. Moreover, we are limited to considering the sign as an activation function. Although it has been shown in the literature that this is already enough to achieve near state-of-the-art results, this is indeed an important limitation. The natural question is then whether we can avoid some (potentially all) of these constraints, towards the goal of homomorphically evaluating any neural network, with real inputs, reals weights and biases, and any activation function.

Question 7.2. As a complement (or an alternative) to the previous question, from a practical point of view, can we design an automated "compiler" that, given as input an already trained neural network, returns a neural network that can be evaluated on encrypted inputs? That is, designing a complete ecosystem of softwares that takes care of all the steps of the interaction: encrypting the inputs (on the user's side), evaluating the network (on the server's side), and then decrypting the results (back on the user's side).

Question 7.3. In the approach that we proposed, we apply the bootstrapping function after processing every neuron. Since this operation is heavy and time-consuming, is there a way to reduce the number of bootstrappings needed to evaluate an entire network? Also, another strong optimization regards parallelization: all the bootstrappings are independent, so we could take advantage of powerful GPUs in order to perform several of these operations together, thus saving in execution time.

Question 7.4. Another open question regarding bootstrapping is the following: can we batch several of these operations together, so that the cost for bootstrapping N neurons is less than N times the cost of a single bootstrapping?

Circuit privacy

Question 7.5. The first open question that comes to mind is whether (and how) our technique based on a Gaussian leftover hash lemma can be extended to FHE schemes other than GSW. For example, the so-called second generation FHE is usually more efficient for specific applications: can our approach be extended to such schemes? More importantly, can we blend the results on homomorphic evaluation of deep neural networks presented in Chapter 4 together with the technique for circuit privacy showed in Chapter 5?

Question 7.6. The threat model that we consider in our work is that of a honest-but-curious adversary. Can we extend our technique to be secure against malicious adversaries, that can deviate from the prescribed protocol, send malformed inputs, . . . ? There appear to be essentially two roads to this goal: we can either (1) have a way to prove or to check that the input values are well formed, and reject them if they are not, or (2) enhance our technique so that the result leaks no information on the computation, regardless of the input that has been submitted.

Question 7.7. Can we achieve CCA1-secure FHE? We note that this is not possible for those approaches that rely on bootstrapping, since publishing the bootstrapping key violates the CCA1 security requirements.

Private information retrieval

Question 7.8. What exactly are the legal constraints that the protocol has to satisfy?

Given the goal of the project, i.e., to improve upon the way information is currently exchanged between law enforcement agencies across borders, it is important to pinpoint exactly the legal constraints. For example, is it acceptable to be able to check whether the intersection of two queries is empty or not, without the trusted party's authorization? As it was underlined in Chapter 6, there is a trade-off between how strict the security model is, and how heavy the workload for the trusted party is. Defining this and other constraints can help understand how the protocol should behave. Question 7.9. Would the protocol be more efficient if implemented with another homomorphic encryption scheme?

The implementation that we realized was based on the DGHV encryption scheme [START_REF] Van Dijk | Fully Homomorphic Encryption over the Integers[END_REF], but there are plenty of other possibilities, like lattice-based encryption schemes that rely on the LWE assumption (cf. Assumption 2.4.4).

Notation

Notation

General mathematical notation :=

"Is defined as"

N

The set of natural numbers

Z

The set of integer numbers

Z q

The set of integer numbers modulo q

R

The set of real numbers

T

The torus, i.e., the set of integers modulo 1 log Base-2 logarithm v A (column) vector v A transposed vector (i.e., a row vector)

A A matrix R A ring R [X]
The set of polynomials in X with coefficients in R Dans cette thèse, nous présentons des nouvelles techniques et constructions pour le chiffrement totalement homomorphe qui sont motivées par des applications en apprentissage automatique, en portant une attention particulière au problème de l'inférence homomorphe, c'est-à-dire l'évaluation de modèles cognitifs déjà entrainé sur des données chiffrées.

Premièrement, nous proposons un nouveau schéma de chiffrement totalement homomorphe adapté à l'évaluation de réseaux de neurones artificiels sur des données chiffrées. Notre schéma atteint une complexité qui est essentiellement indépendante du nombre de couches dans le réseau, alors que l'efficacité des schéma proposés précédemment dépend fortement de la topologie du réseau.

Ensuite, nous présentons une nouvelle technique pour préserver la confidentialité du circuit pour le chiffrement totalement homomorphe. Ceci permet de cacher l'algorithme qui a été exécuté sur les données chiffrées, comme nécessaire pour protéger les modèles propriétaires d'apprentissage automatique. Notre mécanisme rajoute un coût supplémentaire très faible pour un niveau de sécurité égal. Ensemble, ces résultats renforcent les fondations du chiffrement totalement homomorphe efficace pour l'apprentissage automatique, et représentent un pas en avant vers l'apprentissage profond pratique préservant la confidentialité.

Enfin, nous présentons et implémentons un protocole basé sur le chiffrement totalement homomorphe pour le problème de recherche d'information confidentielle, c'est-à-dire un scénario où un utilisateur envoie une requête à une base de donnée tenue par un serveur sans révéler cette requête.

Mots Clés

chiffrement à base de réseaux euclidiens, chiffrement totalement homomorphe, informatique en nuage, apprentissage automatique, confidentialité du circuit, recherche d'information confidentielle.

Abstract

Fully homomorphic encryption enables computation on encrypted data without leaking any information about the underlying data. In short, a party can encrypt some input data, while another party, that does not have access to the decryption key, can blindly perform some computation on this encrypted input. The final result is also encrypted, and it can be recovered only by the party that possesses the secret key.

In this thesis, we present new techniques/designs for FHE that are motivated by applications to machine learning, with a particular attention to the problem of homomorphic inference, i.e., the evaluation of already trained cognitive models on encrypted data.

First, we propose a novel FHE scheme that is tailored to evaluating neural networks on encrypted inputs. Our scheme achieves complexity that is essentially independent of the number of layers in the network, whereas the efficiency of previously proposed schemes strongly depends on the topology of the network.

Second, we present a new technique for achieving circuit privacy for FHE. This allows us to hide the computation that is performed on the encrypted data, as is necessary to protect proprietary machine learning algorithms. Our mechanism incurs very small computational overhead while keeping the same security parameters.

Together, these results strengthen the foundations of efficient FHE for machine learning, and pave the way towards practical privacy-preserving deep learning.

Finally, we present and implement a protocol based on homomorphic encryption for the problem of private information retrieval, i.e., the scenario where a party wants to query a database held by another party without revealing the query itself.

,

  and for p = ∞, we define v ∞ = max i |v i |. When we omit the subscript and simply write v , we refer to the L 2 norm of the vector v. Given two vectors of the same length a, b ∈ R n , we use either a, b or a • b to denote their inner (or dot) product i∈[n] a i b i .

Figure 2 . 1 :

 21 Figure 2.1: Game for IND-CPA security.

Definition 2 .

 2 3.13 (Approximate Bounded Distance Decoding Problem (BDD γ )). Given an arbitrary basis B of an n-dimensional lattice Λ = Λ (B) and a target vector t

Assumption 2 . 4 . 1 (

 241 Hardness of lattice problems). It is hard to solve the lattice problemspresented in Section 2.3.2.

Figure 4 .

 4 Figure 4.1: Example of convolution between an input I and a kernel K.

:

  this layer has no learnable parameters. Given a window of size d 1 × d 2 , one simply slides the window along the layer's input and takes as output the maximum among the d 1 • d 2 input values. Note that this kind of layers reduces the size of the data, since it maps d 1 • d 2 values to just one.

Figure 4 . 2 :

 42 Figure 4.2: Some possible activation functions for a neuron.

Figure 4 .

 4 Figure 4.3: A generic feed-forward neural network of arbitrary depth d: one input layer, followed by d hidden layers of variable size, and one output layer.

Algorithm 1

 1 Gradient descent Input: a neural network N with d hidden layers, a loss function L, training samples (x i , y i ) for i ∈ [N ], a prescribed number of iterations M , a learning rate ε ∈ R Output: a trained neural network N * 1: for all epoch ∈ [M ] do 2:

Figure 4 . 4 :

 44 Figure 4.4: Some images from the MNIST dataset

TLWE.Definition 4 . 4 . 4 (

 444 TLWE is a generalization of LWE and Ring-LWE[START_REF] Lyubashevsky | On Ideal Lattices and Learning with Errors over Rings[END_REF]. Definition 4.4.2 (TLWE). Let k ≥ 1 be an integer, N be a power of 2 and χ be an errordistribution over R N [X]. A TLWE secret key s ∈ B N [X] k is a vector of k polynomials over Z N [X]with binary coefficients. The TLWE distribution tlwe s,χ is sampled by picking a ←$ T N [X] k , an error e ← χ, and returning (a, b = s • a + e). Given a message encoded as a polynomial µ ∈ T N [X], a fresh TLWE encryption of µ under the key s is obtained by taking (a, b) + (0, µ), where (a, b) ← tlwe s,χ , and 0 is a vector of k zero-polynomials. Remark 4.4.3. Notice that if N is large and k = 1, then TLWE becomes Ring-LWE with binary secret, whereas if N = 1 and k is large, then TLWE becomes the standard LWE problem with binary secret. With this definition, one can define the search and the decision versions of the TLWE problem, analogously to what was done for LWE in Definitions 2.3.21 and 2.3.22.TGSW. TGSW is a generalized version of the GSW FHE scheme [GSW13; AP14] (cf. Section 3.4.3). It can roughly be seen as the matrix version of the TLWE scheme, just like GSW can be seen the matrix-equivalent of LWE. A key difference is in the gadget decomposition, which in TGSW is approximated, whereas in the classical GSW cryptosystem this operation is exact. Approximate gadget decomposition [CGGI16b, Definition 3.7]). Let H ∈

.1) Definition 4 . 4 . 5 (

 445 TGSW [CGGI16b, Definition 3.9]). Let and k ≥ 1 be two integers, α ≥ 0 be a noise parameter, H the gadget defined in Equation (4.1), and let s ∈ B N [X] k be a TLWE

Definition 4 .

 4 5.1. A Discretized Neural Network (DiNN) is a feed-forward artificial neuralnetwork whose inputs are integer values in {-I, . . . , I} and whose weights are integer values in {-W, . . . , W }, for some I, W ∈ N. For every neuron of the network, the activation function maps the inner product between the incoming inputs vector and the corresponding weights to integer values in {-I, . . . , I}.

Figure 4 . 5 :

 45 Figure 4.5: Evaluation of a single neuron. The output value is y = sign ( w, x ), where w i are the discretized weights associated to the incoming wires and x i are the corresponding input values.

Construction 4 . 5 . 2 (

 452 Extended LWE-based private-key encryption scheme). Let B be a positive integer and let m ∈ [-B, B] be a message. Then we split the torus into 2B + 1 slices, one for each possible message, and we encrypt and decrypt as follows:Setup (κ): for a security parameter κ, fix n = n (κ) , σ = σ (κ); return s ←$ T n Enc (s,m): return (a, b), with a ←$ T n and b = s, a + e + m 2B+1 , where e ← χ σ Dec (s, (a, b)): return (bs, a ) • (2B + 1) An input message is mapped to the center of its corresponding torus slice by scaling it by 1/ (2B + 1) during encryption, and decoded by scaling it by 2B + 1 during decryption. Correctness of homomorphically evaluating the multisum. Note that ciphertexts can be homomorphically added and scaled by a known integer constant: for any two messages m 1 , m 2 ∈ [-B, B], any secret key s, any c 1 = (a 1 , b 1 ) ← Enc (s, m 1 ), c 2 = (a 2 , b 2 ) ← Enc (s, m 2 ), and constant w ∈ Z, we have that

Figure 4 . 6 :

 46 Figure 4.6: On the left, we show the first step of the bootstrapping, which consists in mapping the torus (the continuous circle) to the wheel (the 2N ticks on it) by rounding to the closest tick. Each slice corresponds to one of the possible results of the multisum operation. On the right we show the final result of the bootstrapping:each tick of the top part of the wheel is mapped to its sign which is +1 and each tick of the bottom part to -1. This can roughly be seen as embedding the wheel back to the torus.

Remark 4 . 5 . 8 .

 458 Using the modified version of the BlindRotate algorithm presented in Section 4.5.4.4 decreases the number of wrong bootstrappings.

  since e b m+1 = 1 we directly have e u k = 0 and thus u k ∈ L. The vectors u 1 , . . . , u m are linearly independent since span (u 1 , . . . , u m , b m+1 ) = span (b 1 , . . . , b m , b m+1 ) = R m+1 (which comes from the fact that B is a basis of an (m + 1)dimensional lattice). We now bound the norm of u k : u k ≤ b k + b m+1 e b k = √ 5(1 + e ) Note that | e b k | ≤ e b k since the last coefficient of b k is 0. Finally we obtain λ m (L) ≤ max k≤m u k ≤ √ 5(1 + e ) and the result.

  2.3. Then by applying Lemma 5.3.1 with r = Ω α √ κ m log m and ε = ε = 2 -κ we have ∆ (A, Ax, e x + y) , A, u, e < 3 • 2 -κ where A ←$ Z (n-1)×m q , x ← G -1 rand (v) and y ← D Z,r . From this we obtain that for e ← D Z m ,α : ∆ (A, e, Ax, e x + y) , A, e, u, e = w∈Z m ∆ (A, Ax, w x + y) , A, u, w • Pr [e = w]

Figure 6

 6 Figure 6.1: Outline of the steps of the ADOC protocol.

Figure 6 .

 6 Figure 6.7: Screenshot of the trusted party (Judge) when processing a disjunctive query.

Figure 6 . 8 :

 68 Figure 6.8: Screenshot of the responding party when disclosing the information after a disjunctive query.

Simple query 3 • 4 •

 34 2048 bits + 2 • ((755 d) KB + 2048 bits) where d = n + 1 is the degree of the polynomial associated to the search token. Conjunctive query 4•2048 bits+3 (755 (d 1 + d 2 ) KB)+1 bit+4096 bits+2 (3 • 755 (d 1 + d 2 ) KB + 2048 bits) where d 1 = n 1 + 1, d 2 = n 2 + 1 are the decrees of the polynomials associated to the search tokens. Disjunctive query 2048 bits + 4096 bits + 2 (755 (d 1 + d 2 ) KB + 2048 bits) where d 1 = n 1 + 1, d 2 = n 2 + 1 are the decrees of the polynomials associated to the search tokens.

  Figures

3.1 Introduction .

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26 3.2 Homomorphic encryption scheme

  . . . . . . . . . . . . . . . . . . . .

27 3.3 Bootstrapping and key-switching

  . . . . . . . . . . . . . . . . . . . .

28 3.4 Three generations of FHE

  . . . . . . . . . . . . . . . . . . . . . . . .

	30 3.4.1 First generation FHE . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.4.2 Second generation FHE . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4.3 Third generation FHE . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.4.4 Message packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
	3

.5 Advanced constructions

  . . . . . . . . . . . . . . . . . . . . . . . . .

37 3.6 Libraries and practical implementations

  . . . . . . . . . . . . . . . .

38 3.7 FHE constructions from non-lattice assumptions

  . . . . . . . . . . . 39

	-25 -

Algorithm 2

 2 Alternative BlindRotate algorithm. Input: an n-LWE ciphertext (a, b) with coefficients in Z 2N , a (possibly noiseless) TLWE encryption C of testVector, the bootstrapping key bk such that for all i in [n/2], bk 3i , bk 3i+1 , and bk 3i+2 are respectively TGSW encryptions of s 2i s 2i+1 , s 2i (1s 2i+1 ), and s 2i+1 (1s 2i )

Output: a TLWE encryption of X b-s,a • testVector 1: ACC ← X b • C 2: for i = 1 . . . n/2 do 3:

Table 4 .

 4 1: Comparison of the three alternative BlindRotate algorithms. n denotes the LWE dimension after keyswitching; δ refers to the noise introduced by rounding the LWE samples into [2N ] before we can BlindRotate; N is the degree of the polynomials in the TLWE scheme; k is the dimension of the TLWE cipher-

texts; ε is the precision (1/2β) /2 of the gadget matrix (tensor product between the identity Id k+1 and the powers of 1/2β arranged as -dimensional vector (1/2β, . . . , (1/2β) ) ); σ bk is the standard deviation of the noise of the TGSW encryptions in the bootstrapping key, and A bk is a bound on this noise. These values were derived using the theorems for noise analysis in

[START_REF] Chillotti | Faster Packed Homomorphic Operations and Efficient Circuit Bootstrapping for TFHE[END_REF]

Table 4 .

 4 2: Accuracy obtained when evaluating the models in the clear on the MNIST test set. The first value refers to the evaluation of the model as output by the training; the second refers to the model where all the values for weights and biases have been discretized; the third refers to the same model, but with sign (•) as the activation function for all the neurons in the hidden layer.

	30 neurons 100 neurons	NN 94.76 % 96.75 %	DiNN + hard_sigmoid 93.76 % (-1 %) 96.62 % (-0.13 %)	DiNN + sign 93.55 % (-1.21 %) 96.43 % (-0.32 %)
	Ciphertext input keyswitching key bootstrapping key	Dimension α 1024 2 -30 450 2 -17 1024 2 -36	Estimated security > 150 bits > 80 bits > 100 bits

Table 4 .

 4 3: The security parameters we use for the different kinds of ciphertexts. The estimated security has been extracted from the plot in[START_REF] Chillotti | Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds[END_REF] and later verified with the estimator from Albrecht et al.[START_REF] Albrecht | On The Concrete Hardness Of Learning With Errors[END_REF].

Table 4 .

 4 4: Message space: theoretically required values and how we set them in our experiments with FHE-DiNN.

	1 st layer 2 nd layer	FHE-DiNN 30 max w w 1 theor. 2338 4676 399 798	exp. 2500 800	FHE-DiNN 100 max w w 1 theor. 1372 2744 488 976	exp. 1800 1000
	in Section 4.5.4.1, we save a factor 172 in the size of the input ciphertext: instead of having 784 • (450 + 1) torus elements (corresponding to a 450-LWE ciphertext for each of the 784 pixels in an image), we now have only 2 • 1024 torus elements (corresponding to the two polynomials that form a TLWE sample).

Table 4 .

 4 Enc(i p i X i ) • i w i X -iThe whole image (784 pixels) is packed into 1 TLWE ciphertext to minimize bandwidth usage. After evaluation, the user recovers 10 ciphertexts corresponding to the scores assigned by the network to each digit.

			User		Server
	7	argmax	1 TLWE 10 scores	Dec	30 TLWE Extract 30 N -LWE Key Switching 30 n-LWE Sign Bootstrapping 30 N -LWE 10 N -LWE weighted sums
	Figure 4.7: Refined homomorphic evaluation of a 784:30:10 neural network with activation function sign. Accur. Disag. Wrong BS Disag. (wrong BS) Time 30 or 93.71% 273 (105-121) 3383/300000 196/273 0.515 s 30 un 93.46% 270 (119-110) 2912/300000 164/270 0.491 s 100 or 96.26% 127 (61-44) 9088/1000000 105/127 1.679 s 100 un 96.35% 150 (66-58) 7452/1000000 99/150 1.64 s

5: Results of homomorphic evaluation of two DiNNs on the full test set.

Neurons Size of ct. Accuracy Time enc Time eval Time dec

	Cryptonets	945	586 MB	98.95%	122 s	570 s	5 s
	Cryptonets	945	73.3 kB	98.95%	0.015 s	0.07 s	0.0006 s
	FHE-DiNN 30 FHE-DiNN 100	30 100	≈ 8.2 kB ≈ 8.2 kB	93.71% 96.35%	0.000168 s 0.000168 s	0.49 s 1.65 s	0.0000106 s 0.0000106 s

Table 4 .

 4 6: Comparison with Cryptonets and its amortized version (denoted by Cryptonets ).

	FHE-DiNN 30 and FHE-DiNN 100 refer to neural networks with one hidden layer composed of 30 and 100 neurons, respectively.

  • L max • max , a power of 2.Note that the ciphertext size grows with log L max . Correctness follows directly. For any branching program Π of length L on variables, any x 1 , . . . , x ∈ {0, 1}, the result of the homomorphic evaluation C f = Eval (Π, (C 1 , . . . , C )) decrypts to Π (x 1 , . . . , x ) with overwhelming probability, where C i ← Enc (sk, x i ) for i ∈ [ ] and sk ← KGen (1 κ ).Proof. Lemma 5.4.7 shows that the noise distribution of the outputC f of Eval has parameter r f = r 2 i=1 τ i 1 + e i 2 , that is r 2L i=1 1 + e i 2because of the padding we applied to Π. We have r f ≤ r 2L (1 + C 2 α 2 m) with C the universal constant defined in Lemma 5.2.3. Using the bounds L max and max we have r L

	Lemma 5.4.9 (Correctness).

Table 6

 6

	.2.

Table 6 .

 6 1: Toy-example of database.

	Feature Name=John Name=Marc Surname=Doe Surname=Smith	ID 1, 3 2 1 2, 3

Table 6 .

 6 2: Inverted database corresponding to the toy example in Table6.1.

  average is the average number of records associated to a tag. KB Conjunction query ≈ 6795 (d 1 + d 2 ) KB Disjunction query ≈ 1510 (d 1 + d 2 ) KB Table 6.3: Communication complexity of our PIR protocol.

	6.5 Discussions	113
	Simple query	Total bandwidth ≈ 1510 d
	1 + where n Chapter 6 1 n average • (size of enc. coefficient) ≈ 7.55 • ν 1 + 1 n average GBytes,

This way of thinking is widely regarded as dangerous in the crypto community, as it leads to an oversimplification of the very complex problem of "right to privacy". Also, it is safe to assume that everyone has something they are embarrassed, ashamed, or frightened of. And that everyone has secrets.

Hence, the name "one-time pad".

As the saying goes, "If you do not pay for the product, then you are the product".

For example, spending a year to decrypt a friend's message could be pointless, but spending a year to decipher a valuable industrial or military secret might be perfectly acceptable.

Note that we do not ask for "the shortest", as a shortest vector is never unique. For a vector v that satisfies the condition, the lattice vector -v does as well.

For example, in[START_REF] Peikert | What does GCHQ's "cautionary tale" mean for lattice cryptography? Blog post[END_REF], Chris Peikert wrote "Healthy skepticism is always warranted (especially in cryptography), but based on these new developments, I don't believe our level of skepticism should rise much from where it was before."

The way, i.e., the amount by which, the noise grows depends on the specific encryption scheme and also on which operation is homomorphically performed.

3.4 Three generations of FHE

Let n = 450 and q = 2 64 . Then a ciphertext is a matrix with nm = n • n log q elements in Zq, which take n • n log q • log q bits of space. With the given numbers, this amounts to 0.772 Gbit.

This computation can even be delegated to another party, e.g., the Cloud.

We are not suggesting this is a good practice or an advisable/reliable way to obtain a medical evaluation. This is just an example to show some privacy-related implications of using web services.

Or probabilities, if the softmax function is applied.

If the framework is implemented with precision of ϕ bits, then switching from one representation to the other is just a matter of multiplying or dividing by 2 ϕ and rounding.

As all the computations are done over the torus (i.e., modulo 1), scaling a ciphertext by any integer factor preserves the relations that make the decryption correct. However, this does not hold for non-integer factors.

If it is not, we can bootstrap all input ciphertexts in order to ensure this holds.

If the number of input neurons is bigger than the maximal degree of the polynomials N , we can pack the ciphertext by groups of N , compute partial multisums with our technique, and aggregate them afterwards

This can be circumvented by applying one last round of KeySwitch at the end of the protocol, if needed.

This means that the number of values that the weights will be able to take will be fairly limited.

As we do not achieve perfect correctness with our parameters, the message can be shifted. This fact has to be taken into account when choosing the number of slots.

Note that we do not apply any activation function to the output neurons: we are only interested in being able to retrieve the scores and sorting them to recover the classification given by the network.

Recall that LWE hardness depends on the modulus-to-noise ratio: the smaller the ratio, the harder the problem.

It should be noted, however, that a way to perform the bootstrapping operation and, thus, turn the DGHV into an FHE scheme is known only for q =

Acknowledgments

I'm not the smartest fellow in the world, but I can sure pick smart colleagues.

-Franklin D. Roosevelt

key. We say that C ∈ T [X] (k+1) ×(k+1) is a fresh TGSW sample of a polynomial µ ∈ R/H ⊥ with noise parameter α if and only if C = Z+µH, where each row of Z ∈ T N [X] (k+1) ×(k+1) is a TLWE encryption of the zero polynomial with Gaussian noise parameter α.

From a TLWE encryption c of a polynomial µ ∈ T N [X] under a TLWE key s we can extract a LWE encryption c = Extract (c) of the constant term of µ under an extracted key s = ExtractKey (s). For the details of the algorithms Extract and ExtractKey, we refer the reader to [CGGI16b, Definition 4.1].

External product and bootstrapping procedure

The core idea for the efficiency of the new bootstrapping procedure is the so-called external product , that performs the following mapping:

Roughly speaking, the external product of a TGSW encryption of a polynomial µ 1 ∈ T N [X] and a TLWE encryption of a polynomial

Now the bootstrapping procedure of an n-LWE sample (here, n denotes the dimension) consists of the following three functions:

On input TGSW encryptions of (s i ) i∈ [n] , a (possibly noiseless) TLWE encryption of Then we can define a function Bootstrap (•, •, •) that takes as input a bootstrapping key bk, a keyswitching key ksk, and a ciphertext and outputs a new ciphertext. Roughly speaking,

We note that BlindRotate works on LWE samples with values in [2N ] instead of T, thus the first step is to map T to [2N ] by multiplying and rounding.

Our contributions

In this section we present our contributions for privacy-preserving evaluation of neural networks.

Chapter 5

Circuit privacy for homomorphic computations

In the context of secure computation outsourcing, protecting the input data is only one side of the coin. On the other side, it might be that the party that performs the computation wants to keep the circuit it evaluates (i.e., the algorithm) private. In fact, it turns out that, without appropriate countermeasures, the output of an homomorphic computation can leak information on the computation itself, thus potentially compromising the privacy of an algorithm which could be a sensitive intellectual property. In this chapter of the manuscript, we address the problem of "circuit privacy", and we show how to efficiently eliminate this leakage, thus providing a way for a party to perform a homomorphic computation without revealing more than its result and some generic side information.

V j . To obtain circuit privacy, we will compute the product as

Note that we made two modifications:

• First, we switched to a randomized G -1 rand (•). The use of a randomized G -1 rand (•) for homomorphic evaluation was first introduced in [AP14], but for the very different purpose of a mild improvement in the noise growth (i.e., efficiency); here, we crucially exploit randomization for privacy.

• Next, we introduced an additional Gaussian shift y j . Interestingly, it turns out that computing the product as

rand (C i ) is useful not only for polynomial noise growth, but also useful for circuit privacy. Roughly speaking, the former hides which V j is used, which corresponds to hiding the intermediate states that lead to the final output state, which in turn hides the branching program.

We highlight a subtlety in the analysis: V j could in principle encode information about C i , if the variable x i has been read prior to reaching the intermediate state encoded in V j , whereas to apply our randomization lemma, we crucially rely on independence between C i and V j . The analysis proceeds by a careful induction argument showing that V j looks like a fresh GSW ciphertext independent of input ciphertexts C 1 , . . . , C apart from some dependencies on the norm of the noise terms in the input ciphertexts (see Lemma 5.4.7 for a precise statement). These dependencies mean that homomorphic evaluation leaks the number of times each variable appears in the branching program, but that can be easily fixed by padding the branching program.

Additional preliminaries

In this section we give some additional notions that are needed to properly understand the following. These preliminaries are local to this part.

Randomized G -1 (•) algorithm

First of all, we introduce a randomized version of the G -1 (•) algorithm already mentioned in Section 3.4.3. This algorithm and its properties will be fundamental for our construction.

Definition 5.2.1 (The

det (•) denotes (deterministic) bit decomposition. We will also write X ← G -1 rand (M) to denote that the columns of the matrix X ∈ Z m×p are obtained by applying the algorithm separately to each column of a matrix M ∈ Z n×p q . In particular, using the exact sampler in [BLP+13, Section 5] (which is a variant of the algorithm presented in [START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]), G -1 rand (v) outputs a sample from the discrete Gaussian

Chapter 5

Additional preliminaries

Showing this identity is correct just requires performing the calculations:

Then we observe that by applying Lemma 5.2.2 we have

where

We now have

By additivity of variance on independent variables, we obtain that

Step 2. We now prove that, at each step of the evaluation, each entry of the encrypted state V t looks like a fresh GSW encryption of the corresponding entry of the state v t , even given the GSW encryptions of the input bits, except for a small correlation in the noise.

Lemma 5.4.7 (Distribution of the result of Eval). For any branching program Π of length

L on variables, we define τ t,i to be the number of times the i-th variable has been used after t steps of the evaluation, i.e., τ t,i = var -1 (i)

, for all indexes w ∈ [W ], the following holds:

Proof. We prove this lemma by induction on t ∈

Hybrid H t,w,0 . Let w b = π -1 t,b (w) for b ∈ {0, 1}. We write w β to denote w x var(t) , i.e. w 0 or w 1 , depending on the value of the variable which is used at time t.

where C i ← Enc (sk, x i ) and y t,w ← D Z m ,r √ 2 . Hybrid H t,w,1 . We set

where

We use the fact that applying a function to two distributions does not increase their statistical distance to obtain H t,w,0 ≈ s H t,w,1 .

By Lemma 5.4.6 we have:

where

ζ from which we have that C and C t,w are identically distributed, and directly H t,w,1 ≈ s H t,w,2 . We note that this recursive formula does not apply to step t = 0, we thus use t = 1, w ∈ [W ] as the base case. We only describe the steps that differ from the case t > 1.

Hybrids H 1,w,2 . The proof for H 1,w,1 ≈ s H 1,w,2 is identical to the one of Lemma 5.4.6 except for the fact that the ciphertext V x from the proof is now of the form v 0 [w β ] G. The resulting ciphertext C 1,w is now only the sum of two encryptions of 0 and v 0 [w β ] and has a Gaussian parameter r 2 1 + e var(1) 2 = r 1 . This implies H 1,w,1 ≈ s H 1,w,2 .

Chapter 6

Private information retrieval through homomorphic encryption

In this chapter we present an implementation of homomorphic encryption, applied to the problem of private information retrieval (PIR). In particular, we will design and implement a protocol that allows a client to query a remote database held by a server, with the guarantees that the server does not learn the query. Also, the client learns nothing more than the answer to its request (or the fact that the request has no answer at all). This last remark seems to imply that our protocol actually achieves the security requirements of oblivious transfer, but we will discuss this matter in the following.

The implementation of the protocol will not use instantiations of homomorphic encryption from lattice assumptions, but the so-called homomorphic encryption over the integers, stemming from the assumed hardness of the approximate GCD problem (cf. Definition 2.4.6). Specifically, our encryption scheme will be a symmetric version of that presented in [START_REF] Van Dijk | Fully Homomorphic Encryption over the Integers[END_REF], extended to support a message space larger than just {0, 1}.

This work was done within a European project, and it aimed at showing that homomorphic encryption can be practical for some use-cases. -------------------------------→ verify & sign Σ := signed enc. of polynomial corresponding to st ← - ----------------------------------------Σ verify & find roots disclose information Figure 6.2: Protocol for the case of a simple query.

6. JU verifies the supporting material and proceeds if it is satisfied. If this is the case, JU fetches the two encrypted polynomials p 1 (x) and p 2 (x) corresponding to search tokens Θ 1 and Θ 2 , homomorphically multiplies them together, and signs the resulting encryption of the polynomial p 1 (x) • p 2 (x). Notice that the roots of p 1 (x) • p 2 (x) will be the union of the roots of p 1 (x) and p 2 (x). Finally, JU hands the signed polynomial back to FR.

7. FR forwards this signed encrypted polynomial to DE. 8. DE verifies JU's signature and, if everything is correct, decrypts the polynomial, calculates its roots (i.e., the IDs), and sends to FR the information on those records.

These steps are presented in Figure 6.3. In order for these steps to go through, the encryption scheme used for implementing the protocol must support at least one homomorphic multiplication.

Conjunction query. This is the most problematic case, because it turns out that FR is not able to verify on its own whether there is a match for conditions ξ 1 ∧ξ 2 . In fact, verifying that there is a match for each of the two conditions is necessary but not sufficient to guarantee that the intersection of the results is non-empty. In order to solve this issue, we have to complicate the protocol and introduce one more round of interaction between FR and DE. The steps are as follows:

3. FR and DE repeat twice the simple sub-protocol for oblivious computation of search

Conjunction query

France

Germany Judge -----------------------------------------

The DGHV encryption scheme and its extension

Here we present a basic secret-key version of the DGHV encryption scheme with message space M = {0, 1} (as given in [START_REF] Van Dijk | Fully Homomorphic Encryption over the Integers[END_REF]), and we show how it can be simply extended to support a larger message space. We remind the reader that we are not interested in building a fully homomorphic encryption scheme, so we will not focus on the bootstrapping procedure.

For a security parameter κ, the encryption scheme is parametrized by integers η = η (κ) , γ = γ (κ) , ρ = ρ (κ). The scheme is then composed of the following algorithms:

KGen (1 κ ) → (sk, x 0 ) : generate a random prime p of size η bits. Generate a random prime s 0 of size γη bits, and let x 0 = s 0 p be a public parameter. Return sk = p and x 0 .

Enc (sk, µ ∈ {0, 1}) → c : generate a random positive integer s of γ -η bits, a random integer r in (-2 ρ , 2 ρ ), and output the ciphertext c = ps + 2r + µ.

Chapter 6

6.3 The DGHV encryption scheme and its extension 105

Dec (sk, c) → µ : output µ = (c mod p) mod 2.

For the choice of parameters, [START_REF] Van Dijk | Fully Homomorphic Encryption over the Integers[END_REF] suggests the following:

• ρ = ω (log κ) to protect against brute-force attacks on the noise;

• η ≥ ρ • Θ κ • log 2 κ in order to support homomorphisms for deep enough circuits to evaluate the squashed decryption circuit;

• γ = ω η 2 • log κ to thwart various lattice-based attacks on the underlying approximate GCD problem.

Extending the message space. It turns out that extending the message space to Z q for some integer q, is immediate 1 . It is sufficient to change the encryption and decryption algorithms as follows:

Enc (sk, µ ∈ Z q ) → c : generate a random positive integer s of γη bits, a random integer r in (-2 ρ , 2 ρ ), and output the ciphertext c = ps + qr + µ.

Dec (sk, c) → µ : output µ = (c mod p) mod q.

In order to ensure correct decryption, we need qr < p. This essentially guarantees that the term qr remains untouched after the reduction modulo p. If this condition does not hold, we can write qr = kp + t, with k ≥ 1 and t < p. The ciphertext can then be written as c = (s + k) p + t + µ. When reducing modulo p, we are left with t + µ, which is not guaranteed to be congruent to µ modulo q.

We now analyze how to perform homomorphic operations on DGHV ciphertexts. In this part, the role of the term x 0 output by the KGen procedure will finally become clear. Let (sk, x 0 ) ← KGen (1 κ ).

Homomorphic addition.

Given two messages µ 1 , µ 2 ∈ Z q , and two DGHV ciphertexts

Showing that this is the case just requires performing the calculations:

It then follows that

provided that (r 1 + r 2 ) q < p. Chapter 7

Chapter 7 Conclusions and open questions

In this chapter we summarize the contributions presented in this manuscript, we draw some conclusions, and we outline some questions that remain open. We also try to put the contributions in perspective and to analyze their impact on the field of cryptology.

List of Illustrations