FHE ML Dectorat Thesis
FHE ML Dectorat Thesis
FHE ML Dectorat Thesis
Michele Minelli
M. WEE Hoeteck
CNRS, École normale supérieure
Directeur de thèse
M. CORON Jean-Sébastien
Université du Luxembourg
Rapporteur
M. FOUQUE Pierre-Alain
Soutenue par Université de Rennes 1
Michele MINELLI Rapporteur
Michele MINELLI
— 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 chiffre-
ment totalement homomorphe qui sont motivées par des applications en apprentissage au-
tomatique, 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 chiffre-
ment 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.
— vii —
Acknowledgments
I’m not the smartest fellow in the world, but I can sure pick smart colleagues.
– Franklin D. Roosevelt
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,
— ix —
x 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 discus-
sions, 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.
In most of the manuscripts I have read, this section ends with some words about the
author’s significant other, and this will not be an exception. I want to express my deepest
gratitude to my wonderful girlfriend Amata for being an extraordinary person, and for
supporting me in her own very personal and absolutely marvelous way. You were and are
always there, and this means everything to me. I am incredibly lucky to have you by my
side, and now that this chapter of my life is reaching its conclusion, I am looking forward to
the next one. And I cannot wait to write it together with you.
Contents
Abstract v
Résumé vii
Acknowledgments ix
1 Introduction 1
1.1 Computation outsourcing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Homomorphic encryption . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 FHE in the user-server scenario . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 User and server: different problems for different players . . . . . . . . . . . . 7
1.3.1 The user’s point of view . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 The server’s point of view . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4.1 A new framework for homomorphic evaluation of neural networks . . . 8
1.4.2 A new technique for circuit privacy . . . . . . . . . . . . . . . . . . . . 9
1.4.3 A protocol for private information retrieval . . . . . . . . . . . . . . . 9
1.5 Other contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Organization of the manuscript . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Personal Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Preliminaries 13
2.1 Notation and preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Mathematical notation . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.3 Provable security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Cryptographic primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.2 Computational problems . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.3 Worst-case hardness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.4 Gaussians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.5 Short integer solution (SIS) . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3.6 Learning with errors (LWE) . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Complexity assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
— xi —
xii Contents
Notation 119
Abbreviations 121
Bibliography 125
1
Chapter 1
Chapter
Introduction
In this chapter, we introduce the topic of this thesis in the area of cryptography. First
of all, we motivate the interest for cryptography, we give some historical facts about this
science, and we introduce the main points of this thesis. Finally, we present the organization
of this manuscript.
Contents
1.1 Computation outsourcing . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Homomorphic encryption . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 FHE in the user-server scenario . . . . . . . . . . . . . . . . . . . . . 6
1.3 User and server: different problems for different players . . . . . . 7
1.3.1 The user’s point of view . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 The server’s point of view . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4.1 A new framework for homomorphic evaluation of neural networks . . . 8
1.4.2 A new technique for circuit privacy . . . . . . . . . . . . . . . . . . 9
1.4.3 A protocol for private information retrieval . . . . . . . . . . . . . . 9
1.5 Other contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Organization of the manuscript . . . . . . . . . . . . . . . . . . . . . 10
Personal Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
— 1 —
2 Chapter 1 Introduction
1
This way of thinking is widely regarded as dangerous in the crypto community, as it leads to an oversim-
plification 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.
3
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 theo-
retic or perfect security, and can be achieved by a trivial scheme, known as one-time pad.
Chapter 1
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:
i l o v e y o u
+ + + + + + + +
Encryption:
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:
m s q e j g v v
≠ ≠ ≠ ≠ ≠ ≠ ≠ ≠
Decryption:
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 once2 ,
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 [DH76],
public-key encryption (also known as asymmetric encryption), and digital signatures in 1978
by Rivest, Shamir and Adleman [RSA78], 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
2
Hence, the name “one-time pad”.
4 Chapter 1 Introduction
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.
Chapter 1
simply subtract 2S (or take the result modulo S, if some other conditions hold) and recover
m1 + m2 . 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 [RSA78], in which an encryption of a message
m is me mod N , where e is a public exponent and N is a public modulus. It is easy to see
that, given two ciphertexts c1 = me1 mod N and c2 = me2 mod N that encrypt messages
m1 and m2 , we can multiply them together and obtain cÕ = (m1 m2 )e mod N , which is
an encryption of m1 m2 . 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 [ElG84], 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 [Pai99], based on the decisional
composite residuosity assumption. In this scheme, an encryption of a message m is of the
form c = g m · rn mod n2 , where g and n are public and r is random. In this case, a party
that is given two ciphertexts c1 , c2 encrypting messages m1 , m2 , can compute cÕ = c1 · c2 =
g m1 +m2 · (r1 r2 )n mod n2 , which is a Paillier encryption of m1 + m2 . 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 ad-
dition 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 [DGHV10], 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 secu-
rity purposes. This noise (sometimes called “error”) grows when performing homomorphic
additions and multiplications, and must remain below a certain threshold in order for the ci-
phertext 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 opera-
tions 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
6 Chapter 1 Introduction
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 sug-
gestion of [RAD78]) 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 homo-
morphic 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 re-
searchers 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 [Gen09a], Gentry put forward the first plausible construc-
tion 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 ef-
ficient, 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.
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).
Chapter 1
• 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.
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 com-
puting 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.
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)
Chapter 1
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 evalu-
ation 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.
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.
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
Chapter 1
encrypted inputs; Chapter 5 considers the other side of the coin for outsourced computa-
tions, 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; Chap-
ter 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
[BPMW16] Florian Bourse, Rafaël del Pino, Michele Minelli, and Hoeteck Wee. “FHE
Circuit Privacy Almost for Free”. In: CRYPTO 2016, Part II. Ed. by Matthew
Robshaw and Jonathan Katz. Vol. 9815. LNCS. Springer, Heidelberg, Aug.
2016, pp. 62–89. doi: 10.1007/978-3-662-53008-5_3 (cit. on p. 9).
[BBB+17] Anthony Barnett, Charlotte Bonte, Carl Bootland, Joppe W. Bos, Wouter
Castryck, Anamaria Costache, Louis Goubin, Ilia Iliashenko, Tancrède Lep-
oint, Michele Minelli, Pascal Paillier, Nigel P. Smart, Frederik Vercauteren,
Srinivas Vivek, and Adrian Waller. Processing Encrypted Data Using Homo-
morphic Encryption. Workshop on Data Mining with Secure Computation,
SODA project. 2017 (cit. on p. 9).
[BMMP18] Florian Bourse, Michele Minelli, Matthias Minihold, and Pascal Paillier. Fast
Homomorphic Evaluation of Deep Discretized Neural Networks. CRYPTO
2018. https://eprint.iacr.org/2017/1114. 2018 (cit. on p. 8).
[GMNO18] Rosario Gennaro, Michele Minelli, Anca Nitulescu, and Michele Orrù. Lattice-
Based zk-SNARKs from Square Span Programs. ACM CCS 2018. https://
eprint.iacr.org/2018/275. 2018 (cit. on p. 10).
Chapter 2
Chapter 2
Preliminaries
In this chapter, we introduce the notation used in this manuscript, and give some defini-
tions and notions.
We begin with standard notation, then we give basic definitions about cryptographic
primitives and introduce the concept of provable security. After this, we give an introduction
to lattices, and we present some background notions that will be useful in the rest of the
manuscript, including the LWE problem and a brief overview on Gaussian distributions and
some of their properties. Finally, we conclude with hardness assumptions that will be used
throughout this work.
These preliminaries are inspired and adapted from several PhD theses’ preliminaries, such
as the ones by Florian Bourse [Bou17], Pierrick Méaux [Méa17], Alain Passelègue [Pas16],
Geoffroy Couteau [Cou17], and Fabrice Ben Hamouda–Guichoux [Ben16]. The part on
lattices is heavily inspired by Chris Peikert’s survey on the area [Pei15a].
Contents
2.1 Notation and preliminaries . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Mathematical notation . . .. . . . . . . . . . . . . . . . . . . . . . 14
2.1.2 Algorithms . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . 15
2.1.3 Provable security . . . . .. . . . . . . . . . . . . . . . . . . . . . 15
2.2 Cryptographic primitives . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 Lattices . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . 17
2.3.1 Basic definitions . . . . . .
. . . . . . . . . . . . . . . . . . . . . . 17
2.3.2 Computational problems . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.3 Worst-case hardness . . . .. . . . . . . . . . . . . . . . . . . . . . 19
2.3.4 Gaussians . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . 19
2.3.5 Short integer solution (SIS) . . . . . . . . . . . . . . . . . . . . . . 20
2.3.6 Learning with errors (LWE) . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Complexity assumptions . . . . . . . . . . . . . . . . . . . . . . . . . 22
— 13 —
14 Chapter 2 Preliminaries
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.
and for p = Œ, we define ÎvÎŒ = maxi |vi |. When we omit the subscript and simply write
ÎvÎ, we refer to the L2 norm of the vector v. Given two vectors of the same length a, b œ Rn ,
q
we use either Èa, bÍ or a · b to denote their inner (or dot) product iœ[n] ai bi .
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 = (a1 , . . . , am ). We will also use 0 for either the zero-vector or the zero-matrix (it will be
clear from the context), and In for the n ◊ n identity matrix.
For a d1 -dimensional vector a and a d2 -dimensional vector b, we write (aÎb) to denote
the (d1 + d2 )-dimensional vector obtained by concatenating a and b. We will use a similar
notation for concatenating matrices with matrices or matrices with vectors.
Chapter 2
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 n0 œ N such that for any integer n Ø n0 , |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 , Á Æ ÷1c .
2.1.2 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).
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.
1
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.
16 Chapter 2 Preliminaries
• KeyGen (1Ÿ ) ‘æ (k, pp): on input the security parameter Ÿ, outputs the key k and some
public parameters pp;
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.
• 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).
Game IND-CPAE,Ÿ
(pk, sk, pp) Ω KeyGen (1Ÿ )
(m0 , m1 ) Ω A (1Ÿ , pk, pp)
b Ω$ {0, 1}
c Ω E.Encrypt (pk, mb )
bÕ Ω A (1Ÿ , pk, pp, c)
return bÕ = b
Chapter 2
Figure 2.1: Game for IND-CPA security.
2.3 Lattices
In this part we present some basic definitions about lattices and we recall several fundamental
computational problems.
the lattice generated by the columns of B. The columns of B form a basis of the lattice.
In this work, we are only interested in full-rank lattices, i.e., those for which k = n
Remark 2.3.2. A lattice basis B is never unique: for any unimodular matrix U œ Zn◊n
(i.e., such that det (U) = ±1), the matrix B · U is also a basis of (B). In Figure 2.2 we
show a two-dimensional lattice with two different bases.
Definition 2.3.3 (Minimum distance). The minimum distance of a lattice is the length
of a shortest nonzero lattice vector:
⁄1 ( ) := min ÎvÎ
0”=vœ
Definition 2.3.4 (Successive minima). Given a lattice , its i-th successive minimum ⁄i ( )
is the smallest positive ¸ œ R such that has i linearly independent vectors of norm at most
¸.
Definition 2.3.5 (Fundamental parallelepiped). For any lattice basis B, we define
P (B) = {Bx : x œ Rn , 0 Æ xi < 1 ’i}
Definition 2.3.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 µ Rn is defined as
ú
:= {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 œ Rn◊k , we
define the q-ary orthogonal of a lattice as
q (B)
‹
:= {v œ Zn : B| v = 0 mod q} .
18 Chapter 2 Preliminaries
b2
b1
bÕ2
bÕ1
O
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 ( ).
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 = {v1 , . . . , vn } µ
of n linearly independent lattice vectors such that Îvi Î Æ “ · ⁄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 œ Rn , find a vector v œ
such that 0 < Îv ≠ tÎ Æ “ · D (t, ) = “ · inf xœ Îx ≠ tÎ.
Definition 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 œ Rn such that
D (t, ) Æ “ ≠1 · ⁄1 ( ), find a vector v œ such that Îv ≠ tÎ = D (t, ).
2
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.
2.3 Lattices 19
Chapter 2
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.
2.3.4 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 spher-
ical Gaussian function with parameter – (omitted if 1) is defined as
3 4
≠fi ÎxÎ
fl– (x) := exp
–2
for any x œ Rn . Given a lattice ™ Rn , a parameter r œ R, and a vector c œ Rn , the
spherical Gaussian distribution with parameter r and support + c is defined as
flr (x)
D +c,r (x) := , ’x œ +c
flr ( + c)
q
where flr ( + c) denotes vœ +c flr (v).
! "
Remark 2.3.15. Note that flr (x) = fl r≠1 x .
Definition 2.3.16 (Sub-Gaussian distribution). A distribution D is sub-Gaussian with pa-
rameter – if there exists M > 0 such that for all x œ Rn ,
D (x) Æ M · fl– (x) .
We now report a very well known result about additivity of Gaussian distributions.
Lemma 2.3.17 (Pythagorean additivity of Gaussians). Let D1 and D2 be Gaussian distri-
+ , obtained by sampling D and D
butions with parameters ‡1 and ‡2 , respectively. Then DÒ 1 2
and summing the results, is a Gaussian with parameter ‡12 + ‡22 .
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 [MR04]). For a lattice ™ Rn and a positive real
Á > 0, the smoothing parameter ÷Á ( ) is the smallest real r > 0 such that fl1/r ( ú \ {0}) Æ Á,
where ú is defined as per Definition 2.3.7.
20 Chapter 2 Preliminaries
Chapter 2
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-lwes,‰ ,
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 rlwes,‰ for some fixed s œ R or uni-
formly 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 œ Zq . We can thus say that a
single ring-LWE sample with a œ R takes the place of n LWE samples with vectors ai œ Znq .
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., [APS15; BF17]). 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., [Ber14]), 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.,
[BPL+15; BPDS16]), showing that the questions related to ideal lattice cryptography and
its security are very important ones and need more attentive investigation.
This is an m-dimensional q-ary lattice, since A| has m rows and the lattice is defined modulo
the integer q.
3
For example, in [Pei15b], Chris Peikert wrote “Healthy skepticism is always warranted (especially in cryp-
tography), but based on these new developments, I don’t believe our level of skepticism should rise much
from where it was before.”
22 Chapter 2 Preliminaries
Assumption 2.4.1 (Hardness of lattice problems). It is hard to solve the lattice problems
presented in Section 2.3.2.
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 ap-
proximation factors “. We currently know of some polynomial-time algorithms, like the
famous LLL algorithm by Lenstra, Lenstra, and Lovász [LLL82], 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 “ = 2k approximations factors in 2 (n/k) time [Sch87].
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 [Reg05], 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 Æ 2poly(n) , and
Ô
any (discretized) Gaussian error distribution ‰ of parameter –q Ø 2 n (where 0 < – < 1),
solving the dlwen,q,‰,m problem is at least as hard as quantumly solving GapSVP“ and SIVP“
on arbitrary n-dimensional lattices, for some “ = O Â (n/a).
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 [How01] and is parametrized by integers
“, ÷, fl œ N.
2.4 Complexity assumptions 23
Definition 2.4.5 (Approximate GCD distribution). The AGCD distribution agcdfl (p, q0 )
for a given ÷-bit integer p and a q0 Ω$ [0, 2“ /p) is the set of integers xi = p · qi + ri , where
qi Ω$ [0, q0 ) and ri Ω$ [0, 2fl ).
Definition 2.4.6 (Approximate GCD problem). For a ÷-bit integer p and a uniformly
chosen q0 Ω$ [0, 2“ /p), given polynomially many samples from agcdfl (p, q0 ), find p.
Assumption 2.4.7 (Hardness of the approximate GCD problem). For appropriately set
parameters “, ÷, fl œ N, it is hard to break the AGCD problem of Definition 2.4.6.
Chapter 2
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
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
Chapter 3
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 [Lep14]. 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
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 —
26 Chapter 3 Fully homomorphic encryption
3.1 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 speak-
ing, 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 en-
cryption scheme allows anyone to take a ciphertext c1 encrypting a message m1 , a ciphertext
c2 encrypting a message m2 , and produce a ciphertext c+ that decrypts to m1 + m2 . Analo-
gously, a multiplicatively homomorphic encryption scheme allows one to produce a ciphertext
c◊ that decrypts to m1 · m2 . And this is possible without having access to either m1 or m2
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 Der-
touzos in 1978 [RAD78] but, despite moderate progress [GM82; Pai99; BGN05; IP07], it
remained the “Holy Grail of cryptography” (cit. [Mic10]) until the breakthrough result of
Gentry in 2009 [Gen09b]. 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-
3.2 Homomorphic encryption scheme 27
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 ex-
isting 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 [Gen09b] and based on ideal lattices and the approximate GCD
Chapter 3
problem; “second generation” usually indicates constructions proposed in a sequence of works
by Brakerski and Vaikuntanathan [BV11a; BV11b] and based on the LWE problem; “third
generation” usually denotes the GSW FHE scheme by Gentry, Sahai, and Waters [GSW13]
and subsequent works (e.g., [AP14; HAO15]).
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.
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:
1 1 22
cÕ = Enc Dec sk , c , (3.2)
where boxed terms are encrypted. Equation (3.2) can be seen as being the encrypted “equiv-
alent” 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
1
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.3 Bootstrapping and key-switching 29
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,
1 2
cÕ = Decc sk (3.3)
1. The secret key sk is encrypted under itself, i.e., bk = Enc (sk, sk);
Chapter 3
! "
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.
For a more formal statement of this assumption, consider the following: let E be a ho-
momorphic encryption scheme, and let AdvIND-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:
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
30 Chapter 3 Fully homomorphic encryption
scheme will not be fully homomorphic but will achieve only a leveled homomorphism. Also,
note that switching to any previously-used key, e.g., sk1 æ sk2 æ · · · æ skN æ sk1 , 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 [Reg05]. 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 oper-
ates 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 Ω$ Znq
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 Ω$ Znq , e Ω ‰,
q"
and return c = a, b = Èsk, aÍ + e + m 2 œ Zn+1
q .
Dec (sk, c) æ mÕ : given the secret key sk and a ciphertext c = (a, b) œ Zn+1
q , compute b ≠
Èsk, aÍ and return m = 0 if this quantity is closer to 0 than to 2 . Otherwise return 1.
Õ q
Remark 3.3.4 (Extending the message space). Construction 3.3.3 can be trivially extended
to M = Zp , for q > p œ N. It is sufficient to multiply m by pq instead of 2q 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| < 2p
q
.
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 [GH10] for more details. This scheme is a public-key
encryption scheme à la [GGH97] 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,
Chapter 3
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 speak-
ing, 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.
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 Ω$ Znq , and a matrix A Ω$ Zm◊n q . Output a secret key sk = s, and
32 Chapter 3 Fully homomorphic encryption
Enc (pk, µ œ M) æ c : given a public key pk = (≠A, b) and a message µ, sample r Ω$ {0, 1}m
and return c = (c1 , c2 ) = (≠A| r, b| r + µ).
It is easy to see that the scheme is correct as long as 2e| r < 4q . We now detail how to per-
form 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 c1 = (c11 , c12 ) Ω Enc (pk, µ1 ) and
c2 = (c21 , c22 ) Ω Enc (pk, µ2 ), for messages µ1 , µ2 œ {0, 1}. Then c+ = (c11 + c21 , c12 + c22 )
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
where ri is the random binary vector used for encrypting µi . Again, the decryption will be
successful if 2e| (r1 + r2 ) < 4q .
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 = (c1 , c2 ), let ŝ := (sÎ1) and ĉ := (c1 Îc2 ).
Then decrypting amounts to computing Èŝ, ĉÍ and reducing modulo 2.
Next we recall the tensor (or Kronecker) product between two vectors v, w œ Znq :
2
v ¢ w = (vi · wj )i,j œ Znq .
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.
3.4 Three generations of FHE 33
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 [BV11a] 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 n2 /2) to the original n + 1.
Modulus switching. As we presented in the preceding part, second generation FHE
ciphertexts are vectors in Zq , where q is some modulus. These ciphertexts contain a certain
amount of noise for security purposes, and remain decryptable as long as the magnitude
Chapter 3
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 . In turn, this
L
means that a very large modulus q ¥ B 2 is required for correct decryption, thus affecting
L
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 [BGV12],
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 as before.
L
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).
Gadget matrix and (randomized) binary decomposition. The first ingredient for
this construction is the so-called gadget matrix, already introduced in [MP12]. Let q be a
modulus, such that ¸ = Álog qË; then the matrix is defined as G = g| ¢ In œ Zn◊n¸
q , where
1 2
g = 1, 2, 4, . . . , 2¸≠1 is the vector of the powers of 2. The matrix G is thus a block-diagonal
matrix: S T
1 2 · · · 2¸≠1 0 0 · · · 0 ··· 0 0 0 0
W
W0 0 · · · 0 1 2 ··· 2 ¸≠1 ··· 0 ··· 0 0 XX
G=W W .. .. .. .. .. .. .. .. .. .. .. .. .. X
X.
U. . . . . . . . . . . . . V
0 0 ··· 0 0 0 ··· 0 · · · 1 2 · · · 2¸≠1
The cryptosystem. We now describe the GSW encryption scheme according to the pre-
sentation in [AP14]. In particular, we will focus on a secret-key version of the scheme, with
message space M = Zq . 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 Ω$ Zn≠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
(n≠1)◊m
A Ω$ Zq , an error vector e Ω ‰m for some error distribution ‰, and output
A B
≠A
C= + µG œ Zn◊m .
s| A + e| q
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 Zq 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
q
ÎeÎŒ < .
2 |M|
Notice that for M = {0, 1}, we recover the well-known condition ÎeÎŒ < 4q .
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.
3.4 Three generations of FHE 35
KGen (1Ÿ ) æ (sk, pk, pp) : choose an integer n = n (Ÿ), a modulus q = q (Ÿ), and let ¸ =
(n≠1)◊m
Álog qË, and m = n¸. Sample a secret vector s Ω$ Zn≠1 q , a matrix A Ω$ Zq ,
an error vector e Ω ‰ for some error
m
A distribution
B ‰, and output the secret key
≠A
sk = ŝ := (sÎ1), the public key pk = | , and public parameters pp = (n, q).
s A + e|
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
A B
≠A
C= R + µG œ Zn◊m .
s A + e|
| q
Chapter 3
≠A
sk C = ŝ
| |
R + µG = e| R + µ ŝ| G,
s| A + e|
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
36 Chapter 3 Fully homomorphic encryption
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 œ Zr◊c q , when we write N = G
≠1 (M) œ {0, 1}r¸◊c , we
mean that the G (·) algorithm is applied independently to all the columns of M, and the
≠1
where Aú = A1 G≠1 (C2 ) + µ1 A2 , and eú | = e|1 G≠1 (C2 ) + µ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 C1 , C2 œ Zn◊mq , such that Ci is an encryption under sk of a message µi with
error vector ei , the error vector contained in C1 · G≠1 (C2 ) is
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
C2 · G≠1 (C1 ) leads to a result which is similar to Equation (3.4), but with a different
output noise. The choice of the order of the operands then depends on which of the two
ciphertexts has the highest noise, i.e., which one is “fresher”. Taking the noise growth formula
of Equation (3.5) into account, it is usually convenient to apply the G≠1 (·) operation to the
one that contains more noise.
Remark 3.4.3. Looking once again at the noise growth formula in Equation (3.5), it is easy
to see why this encryption scheme is not very well suited for large message spaces. In fact,
the term µ1 e2 can be very large if µ1 is in a large domain. Therefore, it is not uncommon
to see the GSW encryption scheme used only for messages in {0, 1} or {≠1, 0, 1}.
3.5 Advanced constructions 37
Chapter 3
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 Pi a share ski of the secret key sk. Then, each party can
encrypt its input xi 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 ski and in the end receives the result µ = f (x1 , . . . , xN ). 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.
2
Let n = 450 and q = 264 . 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.
3
This computation can even be delegated to another party, e.g., the Cloud.
38 Chapter 3 Fully homomorphic encryption
Fully homomorphic signatures The basic idea of this primitive, proposed by Gorbunov et
al. in [GVW15] 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.
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 gen-
erally 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.
Chapter 3
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
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. [CGGI16b; CGGI17], which will be central in our constructions. Finally, we present
Chapter 4
our contributions, explain in details our framework FHE-DiNN, and give some encouraging
experimental results obtained on a typical dataset.
Contents
4.1 Introduction to the problem . . . . . . . . . . . . . . . . . . . . . . . 42
4.2 Refresher on neural networks . . . . . . . . . . . . . . . . . . . . . . 43
4.2.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2.2 Neural networks’ layers . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2.3 Activation functions . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2.4 Perceptrons, multilayer perceptrons, and deep NNs . . . . . . . . . . 46
4.2.5 Training and evaluating neural networks . . . . . . . . . . . . . . . 47
4.2.6 MNIST: a typical dataset for NNs . . . . . . . . . . . . . . . . . . . 50
4.3 State of the art for privacy-preserving predictions . . . . . . . . . . 51
4.4 TFHE: a framework for efficient bootstrapping . . . . . . . . . . . . 52
4.4.1 LWE over the torus and related constructions . . . . . . . . . . . . . 52
4.4.2 External product and bootstrapping procedure . . . . . . . . . . . . 54
4.5 Our contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.5.1 Definition of a discretized neural network . . . . . . . . . . . . . . . 55
4.5.2 Simple conversion from a traditional NN to a DiNN . . . . . . . . . . 56
4.5.3 Homomorphic evaluation of a DiNN . . . . . . . . . . . . . . . . . . 56
4.5.4 Refinements of TFHE . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.5.5 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.5.6 Comparison with Cryptonets [DGL+16] . . . . . . . . . . . . . . . . 69
— 41 —
42 Chapter 4 Homomorphic evaluation of deep neural networks
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.
1
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.
4.2 Refresher on neural networks 43
We are then interested in designing an efficient framework for evaluating arbitrarily com-
plex neural networks over encrypted data.
– John Denker
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)
Chapter 4
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
nI real-valued inputs x = (x1 , . . . , xnI ) œ RnI and performs the following two computations:
q
1. It computes a value y = ni=1 I
wi xi + — œ R, which is a weighted sum of the inputs
with real values called weights (wi is the weight associated to the input xi ), and — œ R,
which is referred to as the bias of the neuron;
2. It applies a non-linear function f , called the activation function, and returns f (y).
q
A neuron’s output can conveniently be written as f (Èw, xÍ) = i=0 wi xi if one ex-
nI
tends the inputs and the neuron’s weight vectors by setting w = (—, w1 , . . . , wnI ) and
x = (1, x1 , . . . , xnI ). In the following, we will use W¸ = (w¸,1 , . . . , w¸,n2 ) to denote the
n1 ◊ n2 matrix composed of all the weights associated to the connections that go from layer
¸ ≠ 1 (containing n1 neurons) to layer ¸ (containing n2 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.
44 Chapter 4 Homomorphic evaluation of deep neural networks
Fully connected layer: in this kind of layer, every neuron takes all incoming signals as in-
puts.
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).
Max pooling layer: this layer has no learnable parameters. Given a window of size d1 ◊ d2 ,
one simply slides the window along the layer’s input and takes as output the maximum
among the d1 · d2 input values. Note that this kind of layers reduces the size of the
data, since it maps d1 · d2 values to just one.
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.
4.2 Refresher on neural networks 45
Step: for any input x œ R, this function is 0 if x < 0 and +1 if x Ø 0. It only discrimi-
nates 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.
Chapter 4
Sigmoid (or logistic): for any input x œ R, this function is defined as
1 ex
f (x) = = .
1 + e≠x ex + 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.
ex ≠ e≠x e2x ≠ 1
f (x) = tanh(x) = = .
ex + e≠x e2x + 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.
Square: for any input x œ R, this function is defined as f (x) = x2 . Although less common
than other functions, it has been employed, e.g., in [DGL+16]. It is continuous, non-
negative, differentiable, and even (i.e., f (≠x) = f (x)’x œ R). This function ignores
the sign of the input and only considers its magnitude.
46 Chapter 4 Homomorphic evaluation of deep neural networks
(a) sigmoid (x) (b) arctan (x) (c) tanh (x) (d) x2 (e) ReLU (x)
Rectifier: for any input x œ R, this function is defined as f (x) = ReLU(x) = max (0, x). It
has recently become one of the most widely used activation functions in the machine
learning community (e.g., [NH10; MHN13; ZRM+13]). It has the characteristic of
propagating positive values untouched, while completely disregarding negative ones.
An important thing to remember when using this function (and especially when imple-
menting 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 œ Rd to a vector softmax (x) œ (0, 1)d ,
such that its values add up to 1. Formally, given a vector x = (x1 , . . . , xd ) œ Rd , this
function is defined as
exi
softmax (x)i = qd xj
.
j=1 e
softmax is often used in multiclass classification problems, i.e., when the goal is to
classify input patterns into one of NC classes (with NC Ø 3), and has the effect of con-
verting “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
Ci , for i œ [NC ].
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., [Cyb89; Hor91]), states the
following:
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
Chapter 4
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., [HS06]), 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., [Avn16]), to even creating
new astonishing works of art (e.g., [MOT15a; MOT15b]). The potential of deep learning
is considered enormous, and new applications surface regularly, with active research still
happening in the field.
...
... ... . . . ...
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.
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.
L1 : this is one of the simplest loss functions, and it simply measures how far the predicted
value is from the correct one:
N
ÿ
L1 (y‚, y) = |y‚i ≠ yi |
i=1
L2 : similar to the previous one, but this time the differences are squared:
N
ÿ
L2 (y‚, y) = (y‚i ≠ yi )2
i=1
4.2 Refresher on neural networks 49
Mean Squared Error (MSE): similar to the previous one, but this time the value is averaged
on the training set:
1 ÿN
MSE (y‚, y) = (y‚i ≠ yi )2
N i=1
Cross-entropy (or log loss): this is one of the most well known and widely used cost func-
tions in the machine learning field. It measures the performance of a classification
model whose output is a probability value between 0 and 1.
N
ÿ
L (y‚, y) = ≠ y‚i log (yi )
i=1
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;
Chapter 4
2. Calculate the network output y = N (x) by feeding x forward and performing all the
computations until the output layer;
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 normal-
ization, 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.
an output layer composed of 10 neurons (one per possible digit or class). The output values
can be interpreted as scores2 given by the network, with the predicted class being the one
associated to the highest score.
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
Chapter 4
machines, neural networks, convolutional neural networks, etc. For a more complete review
of these approaches, we refer the reader to, e.g., [LBBH98]. Neural networks are known to
perform well on this dataset. For example, [LBBH98] proposes different architectures for
neural networks and obtains more than 97% of correct classifications. More recent works
even surpassed 99% of accuracy [CMS12]. For a nice overview on the results obtained on
this dataset and on the techniques that were used, we refer the reader to [LCB98].
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 [DGL+16] was the first initia-
tive 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
[BGV12] to the network inputs and propagating the signals across the network homomorphi-
cally, thereby consuming levels of homomorphic evaluation whenever non-linearities are met.
We remind the reader that, in neural networks, non-linearities come from activation func-
tions 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 fol-
lowed the same approach and improved it, typically by adopting higher degree polynomials
as activation functions for more training stability [ZYC16], or by renormalizing weighted
sums prior to applying the approximate function, so that its degree can be kept as low
as possible [CWM+17]. 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 computa-
tion, 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. There-
fore, 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].
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 lwes,‰
over Tn ◊ T is sampled by picking a Ω$ Tn , 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) Ω lwes,‰ and (u, v) Ω$ Tn+1 .
From now on, when mentioning the LWE problem, we will refer to this formulation over
the torus.
TLWE. TLWE is a generalization of LWE and Ring-LWE [LPR10].
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
Chapter 4
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.
Q R
1/Bg · · · 0
c .. .. .. d
c
c . . . d
d
c1/B ¸ ··· 0 d
c g d
c . .. .. d (k+1)¸◊(k+1)
H=c .
c . . . d œ TN [X]
d . (4.1)
c d
c 0 · · · 1/Bg d
c d
c .. .. .. d
a . . . b
0 · · · 1/Bg¸
Definition 4.4.5 (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 œ BN [X]k be a TLWE
54 Chapter 4 Homomorphic evaluation of deep neural networks
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.
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.
Chapter 4
Definition 4.5.1. A Discretized Neural Network (DiNN) is a feed-forward artificial neural
network 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}.
In particular, for a first attempt we chose {≠1, 1} as the input space and sign (·) as the
activation function for the hidden layers:
I
≠1, x < 0,
sign (x) = (4.2)
+1, x Ø 0.
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 .
4
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.
56 Chapter 4 Homomorphic evaluation of deep neural networks
x1
w1
x2 w2
y
.. ..
. .
Figure 4.5: Evaluation of a single neuron. The output value is y = sign (Èw, xÍ), where
wi are the discretized weights associated to the incoming wires and xi are the
corresponding input values.
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.
Enc (s, m): return (a, b), with a Ω$ Tn and b = Ès, aÍ + e + 2B+1 ,
m
where e Ω ‰‡
Chapter 4
Dec (s, (a, b)): return Â(b ≠ Ès, 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
m1 , m2 œ [≠B, B], any secret key s, any c1 = (a1 , b1 ) Ω Enc (s, m1 ), c2 = (a2 , b2 ) Ω
Enc (s, m2 ), and constant w œ Z, we have that
as long as (1) m1 + w · m2 œ [≠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 [CGGI16b] by a factor maxw Î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.
58 Chapter 4 Homomorphic evaluation of deep neural networks
2
3
1
+1
4
0
-4
-1
-3 -2 ≠1
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.
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 TN [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.
4.5.3.3 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
4.5 Our contributions 59
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 M1 and M2 , respectively.
We say that the homomorphic evaluation of the neural network is correct if the decryp-
tions 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 ci-
phertext 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 2M1 + 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
encryption5 .
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
Chapter 4
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 [≠M1 , M1 ]. The second one comes directly from the correctness of the boot-
strapping, 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 ‡M2 (cf. Theorem 2.3.17).
Then, the correctness of the encryption scheme ensures that the final ciphertexts are valid
encryptions of the scores.
“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:
A B
ÿ
ct = TLWE.Encrypt xi X i
,
i
where the xi ’s represent the values of the input neurons to be encrypted6 . This packing
technique is what made Ring-LWE an attractive variant to the standard LWE problem, as
was already presented in [LPR10], and is widely used in FHE applications to amortize the
cost of operations [HS14a; HS15].
Then, we observe that for each neuron in the first hidden layer, we can compute the
multisum with coefficients wi by scaling the input TLWE ciphertext by a factor
ÿ
wi X ≠i .
i
!q " !q " q
Indeed, it is easy to verify that the constant term of i
i xi X · i wi X
≠i is
i wi xi ,
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
q
change, we can precompute and store the FFT representation of the polynomials wi 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.
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.
Chapter 4
≠1
≠1 Nÿ
X i,
2B¸ + 1 i=0
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.
In order to compute this new function, they change the bootstrapping key to contain en-
cryptions of the values ssÕ , s(1 ≠ sÕ ), (1 ≠ s)sÕ , and (1 ≠ s)(1 ≠ sÕ ), 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
7
This can be circumvented by applying one last round of KeySwitch at the end of the protocol, if needed.
62 Chapter 4 Homomorphic evaluation of deep neural networks
Table 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 be-
tween the identity Idk+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
Chapter 4
encryptions in the bootstrapping key, and Abk is a bound on this noise. These
values were derived using the theorems for noise analysis in [CGGI17]
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 [Cho+15] with Tensorflow [MAP+15], 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).
Y
]0,
_
_ x < ≠2.5
hard_sigmoid (x) = 0.2 x + 0.5, ≠2.5 Æ x Æ 2.5 (4.4)
_
_
[1, x > 2.5
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.
8
This means that the number of values that the weights will be able to take will be fairly limited.
4.5 Our contributions 65
Table 4.3: The security parameters we use for the different kinds of ciphertexts. The esti-
mated security has been extracted from the plot in [CGGI16b] and later verified
with the estimator from Albrecht et al. [APS15].
Chapter 4
The starting point was the TFHE library by Chillotti et al., which is freely available on
GitHub [CGGI16a] and which was used to efficiently perform the bootstrapping operation.
The library takes advantage of FFT processors for fast polynomial multiplication and, al-
though not parallelized, achieves excellent timing results. We extended the code to apply
this fast bootstrapping procedure to our use case.
Parameters. We now present our setting of the parameters, following the notation of
[CGGI16b], 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:
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
66 Chapter 4 Homomorphic evaluation of deep neural networks
Table 4.4: Message space: theoretically required values and how we set them in our experi-
ments with FHE-DiNN.
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).
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 L2 -norms of the
weight vectors in each layer: for the network with 30 hidden neurons, we have maxw ÎwÎ2 ¥
119 for the first layer and ¥ 85 for the second layer; for the network with 100 hidden neurons,
we have maxw Î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,
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;
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.
9
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.
4.5 Our contributions 67
q
User q
Server
Enc( i)
i pi X · i wi X
≠i
1 TLWE 30 TLWE
Extract
30 N -LWE
Key Switching
30 n-LWE
Sign Bootstrapping
30 N -LWE
weighted sums
argmax Dec
7 10 scores 10 N -LWE
Figure 4.7: Refined homomorphic evaluation of a 784:30:10 neural network with activation
function sign. The 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.
Chapter 4
Table 4.5: Results of homomorphic evaluation of two DiNNs on the full test set. 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 net-
work. 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 [CGGI16b] (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:
10
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.
68 Chapter 4 Homomorphic evaluation of deep neural networks
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 (respec-
tively, 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 classi-
fication 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 one11 (cf. Table 4.5).
Remark 4.5.8. Using the modified version of the BlindRotate algorithm presented in Sec-
tion 4.5.4.4 decreases the number of wrong bootstrappings.
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 evalu-
ating 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).
11
In the remaining cases, the classifications were different but they were both wrong.
4.5 Our contributions 69
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., [CB16]) 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., [LBBH98]),
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
Chapter 4
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.
Neurons Size of ct. Accuracy Time enc Time eval Time dec
Cryptonets 945 586 MB 98.95% 122 s 570 s 5s
Cryptonetsı 945 73.3 kB 98.95% 0.015 s 0.07 s 0.0006 s
FHE-DiNN 30 30 ¥ 8.2 kB 93.71% 0.000168 s 0.49 s 0.0000106 s
FHE-DiNN 100 100 ¥ 8.2 kB 96.35% 0.000168 s 1.65 s 0.0000106 s
Table 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.
Contents
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Chapter 5
5.1.1 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.1.2 Technical overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.2 Additional preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.2.1 Randomized G≠1 (·) algorithm . . . . . . . . . . . . . . . . . . . . 76
5.2.2 Probability results . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.2.3 Results on lattices and Gaussian distributions . . . . . . . . . . . . . 77
5.2.4 Entropy and leftover hash lemma . . . . . . . . . . . . . . . . . . . 77
5.2.5 Permutation branching programs . . . . . . . . . . . . . . . . . . . 78
5.3 Core randomization lemma . . . . . . . . . . . . . . . . . . . . . . . 78
5.3.1 Proof of randomization lemma . . . . . . . . . . . . . . . . . . . . . 79
5.3.2 Rerandomizing LWE samples . . . . . . . . . . . . . . . . . . . . . 81
5.4 Our scheme: circuit-private homomorphic evaluation for GSW . . 82
5.4.1 Rerandomizing and scaling GSW ciphertexts . . . . . . . . . . . . . 82
5.4.2 Circuit privacy: definition and main theorem . . . . . . . . . . . . . 83
5.4.3 Modified Eval algorithm for the GSW encryption scheme . . . . . . . 84
5.4.4 Setting the parameters . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.4.5 Extension to arbitrary moduli and trapdoor matrices . . . . . . . . . 90
5.5 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
— 71 —
72 Chapter 5 Circuit privacy for homomorphic computations
5.1 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 [Gen09b].
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 propri-
etary 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 modulus-
to-noise ratio just to support homomorphic operations for circuits in NC1 (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 [DS16], which requires the additional assumption of
circular security (cf. Assumption 3.3.1).
1
Recall that LWE hardness depends on the modulus-to-noise ratio: the smaller the ratio, the harder the
problem.
5.1 Introduction 73
Both of the prior approaches have some theoretical and practical draw-backs, if we con-
sider FHE for NC1 circuits (the rest of the discussion also applies to leveled FHE for general
circuits). First, recall that we now have FHE for NC1 circuits under the LWE assump-
tion 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 modulus-
to-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 expen-
sive (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 weak-
nesses 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.
Chapter 5
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 poly-
logarithmic 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);
74 Chapter 5 Circuit privacy for homomorphic computations
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 V0 , V1 , C corresponding to encryptions of the input bits v0 , v1 , x.
In the [GSW13; BV14] FHE schemes, homomorphic evaluation is deterministic,
whereas in [AP14] and this work, homomorphic evaluation is randomized. In
particular, our construction introduces an additional small Gaussian shift on top
of [AP14].
• 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≠1rand (·) 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.
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.
5.1 Introduction 75
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
A B
A log q)
C= + µG œ Zn◊(n
s| A + e| q
where s œ Znq 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
A B
0
C· G≠1
rand (G) +
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≠1rand (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 · Grand (a · G) = a · G. Here, we crucially rely on the fact that the
≠1
Chapter 5
A B
! Õ" 0
C· G≠1
rand C + .
y|
We can handle homomorphic encryption as in GSW; this then readily extends to a circuit-
private homomorphic evaluation for branching programs, following [BV14; AP14].
Branching programs are a relatively powerful representation model. In particular, any
logarithmic space or NC1 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 au-
tomaton.
The key insight from Brakerski and Vaikuntanathan [BV14] is that when homomorphically
evaluating a branching program, we will only need to perform homomorphic additions along
with homomorphic multiplications of ciphertexts Vj , Ci where Vj is the encryption of an
intermediate computation and Ci is an encryption of the input variable xi . To obtain
decryption correctness with polynomial noise growth, they computed the product as
Ci · G≠1
det (Vj ),
where G≠1det (·) is the deterministic binary decomposition, cleverly exploiting the asymmetric
noise growth in GSW ciphertexts and the fact that the noise in Ci is smaller than that in
76 Chapter 5 Circuit privacy for homomorphic computations
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 yj| .
Interestingly, it turns out that computing the product as Ci · G≠1 rand (Vj ) instead of Vj ·
Grand (Ci ) is useful not only for polynomial noise growth, but also useful for circuit privacy.
≠1
Roughly speaking, the former hides which Vj 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: Vj could in principle encode information about
Ci , if the variable xi has been read prior to reaching the intermediate state encoded in
Vj , whereas to apply our randomization lemma, we crucially rely on independence between
Ci and Vj . The analysis proceeds by a careful induction argument showing that Vj looks
like a fresh GSW ciphertext independent of input ciphertexts C1 , . . . , 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.
such that x Ω Grand (v) is drawn from a distribution close to a Gaussian with parameter r =
≠1
OÂ (1) conditioned on Gx = v mod q, i.e., G≠1 (v) outputs a sample from the distribution
rand
D ‹ +G≠1 (v),r where G≠1det (·) denotes (deterministic) bit decomposition. We will also write
q det
X Ω G≠1 rand (M) to denote that the columns of the matrix X œ Z
m◊p are obtained by applying
In particular, using the exact sampler in [BLP+13, Section 5] (which is a variant of the
algorithm presented in [GPV08]), G≠1rand (v) outputs a sample from the discrete Gaussian
D ‹ +G≠1 (v),r .
q det
5.2 Additional preliminaries 77
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 Ω DZm ,r .
Chapter 5
1+Á
Lemma 5.2.6 ([Reg05, Claim 3.8]). Let ™ Zm be any lattice, c œ Rm , Á > 0 and
r Ø ÷Á ( ). Then
rm
flr ( + c) œ (1 ± Á) .
det ( )
Next, we state here a simplified version of the leftover hash lemma (originally introduced
by Impagliazzo et al. [ILL89]), which is sufficient for our use.
Lemma 5.2.8 (Leftover hash lemma [DRS04]). Let e be any random variable over Zm
q and
f : Zm
q æ Z k . Then
q
Ò
((Xe, X, f (e)) , (r, X, f (e))) Æ q n+k · 2≠HŒ (e) .
78 Chapter 5 Circuit privacy for homomorphic computations
• var : [L] æ [¸] is a function that associates the t-th tuple with an input bit xvar(t)
• fit,0 , fit,1 : [W ] æ [W ] are permutations that dictate the t-th step of the computation.
Q Û R
1 ! Õ "2
2≠ 1 Ô ln (2m (1 + 1/Á)) b
r Ø max a4 (1 ≠ Á) 2Á m
, 5(1 + ÎeÎ) ,
fi
then ! ! ""
(A, Ax, e| x + y) , A, u, eÕ < ÁÕ + 2Á
(n≠1)◊m
where x Ω G≠1rand (v), A Ω$ Zq , u Ω$ Zn≠1
q , y Ω DZ,r and eÕ Ω DZ,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 random-
ization in G≠1 rand (·) and the shift are both necessary.
First, the shift is necessary for both distributions to have the same support. For exam-
ple, e| G≠1rand ((1, 0, . . . , 0)) and e Grand (0) might lie in two different cosets of the lattice
| ≠1
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 Grand (0) will be even, for an even
| ≠1
q. The shift by a Gaussian over Z ensures that the support of the two distributions is Z.
5.3 Core randomization lemma 79
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≠1rand (·) 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 e1 (the first coordinate of e) and on 0. Instead, using
the randomized algorithm G≠1 rand (·), the center of both distributions will be 0.
Ò first prove that given e, the new error term e x + y is indeed a Gaussian with parameter
We |
Ô
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) œ Zm+1 , c
‚ = (c, 0) œ Zm+1 and ‚ = ‹ (G| ) ◊ Z. We want to show
Chapter 5
q
that 1 2
‚| D ‚
e , DZ,΂eÎr Æ 2Á
c,r
+‚
The support of e
‚| D ‚
c,r
+‚
is e
‚| ‚ + e
‚| c
‚ = e| ‹ q (G ) + Z + e c = Z. Fix some z œ Z. The
| |
Ó Ô
We define the lattice L = v œ ‚ : e ‚| v = 0 ; note that Lz = L + wz for any wz œ Lz .
Let uz = 2 e, then uz is clearly proportional to e
z ‚ ‚. Observe that uz is orthogonal
΂eΠr
to r≠1 Lz ≠ uz , indeed for any t œ r≠1 Lz we have e ‚| (t ≠ uz ) = 0. From this we have
fl (t) = fl (uz ) · fl (t ≠ uz ), and by summing for t œ r Lz :
≠1
1 2
fl(r≠1 Lz ) = fl (uz ) · fl r≠1 Lz ≠ uz
Observe that we have r≠1 Lz ≠ uz = r≠1 (L ≠ cÕ ) for some cÕ in the vector span of the lattice
L (because Lz ≠ ruz = L + wz ≠ ruz and e ‚| (wz ≠ ruz ) = 0). Thus using Lemmas 5.2.5
80 Chapter 5 Circuit privacy for homomorphic computations
Ô Ò
ln(2m(1+1/Á))
and 5.3.4 with r Ø 5 (1 + ÎeÎ) · fi Ø ÷Á (L), we obtain
fl(r≠1 Lz ) = fl(uz ) · flr (L ≠ cÕ )
5 6
1≠Á
œ , 1 · flr (L) · fl(uz )
1+Á
5 6 A B
1≠Á z
= , 1 · flr (L) · fl e
‚
1+Á ‚ Î2 r
Îe
5 6
1≠Á
= , 1 · flr (L) · fl΂eÎr (z)
1+Á
This implies that the statistical distance between e
‚| D ‚
c,r
+‚
and DZ,΂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 œ Zm , let L be as defined in Lemma 5.3.3. Then we
have: Û
Ô ln (2m (1 + 1/Á))
÷Á (L) Æ 5(1 + ÎeÎ) ·
fi
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
Q R
2
c .. d
c ≠1 . d
d œ Z(log q)◊(log q)
c d
B=c .. ..
c d
a . . b
≠1 2
Note that |e
‚| bk | Æ ÎeÎ Îbk Î since the last coefficient of bk is 0. Finally we obtain ⁄m (L) Æ
Ô
maxkÆm Îuk Î Æ 5(1 + ÎeÎ) and the result.
5.3 Core randomization lemma 81
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
| .
1 2
Lemma 5.3.5. Let Á > 0, r Ø ÷Á ‹ (G| )
q . For any c œ Rm , we have
1 2
HŒ D ‹ (G| )+c,r
q
Ø log (1 ≠ Á) + m log (r) ≠ m
The lattice ‹ (G| ) is generated by the basis In ¢ B, with B defined as above, which has
1q 2n
determinant 2log q = 2m . The result follows:
1 2
HŒ D ‹ (G| )+c,r
q
Ø log (1 ≠ Á) + m log (r) ≠ m
Chapter 5
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 Zq . Applying the leftover hash lemma (Lemma 5.2.8), we obtain
where u Ω$ Zn≠1
q . Now, using Lemma 5.3.3, we know that
! | "
e x + y, eÕ < 2Á
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 )
|
A B Ò
≠A
where C = Ω Enc (sk, 0), CÕ Ω Enc“ (sk, 0), with “ = r 1 + ÎeÎ2 .
s| A + e|
Ô
Proof. Fix v œ Zm
q and e such that ÎeÎ Æ C– m,
! Ô "
where C is as in Lemma 5.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≠Ÿ
(n≠1)◊m
where A Ω$ Zq , x Ω G≠1
rand (v) and y Ω DZ,r . From this we obtain that for e Ω
5.4 Our scheme: circuit-private homomorphic evaluation for GSW 83
DZm ,– :
! ! ""
(A, e, Ax, e| x + y) , A, e, u, eÕ
ÿ ! ! ""
= (A, Ax, w| x + y) , A, u, wÕ · Pr [e = w]
wœZm
ÿ ÿ
Æ 3 · 2≠Ÿ Pr [e = w] + Pr [e = w]
Ô Ô
ÎwÎ<C– m ÎwÎØC– m
# Ô $
Æ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.2.3
Ô
and have Pr [ÎeÎ > C– m] Æ 2≠ (m) Æ 2≠ (Ÿ) since m Ø Ÿ. By rewriting this distance we
have for any v œ Zmq
A A B B AA B B
0 ≠u
C· G≠1
rand (v) + ,C ¥s ,C
y s| u + eÕ
Chapter 5
AA A B B AA B BB
0 ≠AÕ (Ÿ)
C· G≠1
rand (V) + ,C , ,C Æ m(3 · 2≠Ÿ + 2≠ )
y| s| AÕ + eÕ|
holds:
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 [GHV10])
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.
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:
• [BV14] uses the deterministic G≠1det (·) whereas [AP14] introduced the randomized Grand (·)
≠1
for efficiency. Here, we crucially exploit the randomized Grand (·) for privacy.
≠1
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
5.4 Our scheme: circuit-private homomorphic evaluation for GSW 85
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 xf of the evaluation of on input
(x1 , . . . , x¸ ), the ciphertexts Ci encrypting xi 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 xf to this ciphertext and outputs
Cf = A ‚ f + xf G.
In other words,
A A BB
0
·i
ÿ̧ ÿ 1 2
Sim (1 , xf , (1 , . . . , 1 ) , (C1 , . . . , C¸ )) Ω
Ÿ ·1 ·¸
Ci · G≠1
rand (0) ≠ G≠1
rand (0) + | +xf G
i=1 t=1
yt
algorithm with a larger parameter r 2·i , and the sum of ·i samples from DZm ,rÔ2 is close
to a sample from DZm ,rÔ2·i .
Chapter 5
is statistically close to fresh GSW encryptions with a somewhat larger noise which depends
on the error in the input ciphertext and on ’.
1 2
Lemma 5.4.6. For any x, v0 , v1 œ {0, 1} and sk = ≠s, 1 Ω KGen (1Ÿ ), the following
holds: A A B B
0 ! "
C · Grand (V1 ) + (G ≠ C) · Grand (V0 ) +
≠1 ≠1
, C ¥s VxÕ , C
y |
A B
A
where Vb Ω Enc“ (sk, vb ) for b œ {0, 1}, C = + xG Ω Enc (sk, x), y Ω DZm ,rÔ2
s| A + e|
Ú 1 2
and VxÕ Ω Enc’ (sk, vx ), with ’ = “ 2 + 2r2 1 + ÎeÎ2 .
Proof. We begin with a simple identity which is useful in the remainder of the proof:
1 2
C · G≠1
rand (V1 ) + (G ≠ C) · Grand (V0 ) = A · Grand (V1 ) ≠ Grand (V0 ) + Vx
≠1 ‚ ≠1 ≠1
A B
A
where A
‚ = and V0 , V1 , C are as defined in the statement of the Lemma.
s A + e|
|
86 Chapter 5 Circuit privacy for homomorphic computations
C · G≠1
rand (V1 ) + (G ≠ C) · Grand (V0 )
≠1
1 2 1 2
= A
‚ + xG · G≠1 (V1 ) + (1 ≠ x) G ≠ A
rand
‚ · G≠1 (V0 )
rand
1 2
=A
‚ · G≠1 (V1 ) ≠ G≠1 (V0 ) + xV1 + (1 ≠ x) V0
rand rand
1 2
=A
‚ · G≠1 (V1 ) ≠ G≠1 (V0 ) + Vx
rand rand
Step 2. We now prove that, at each step of the evaluation, each entry of the encrypted
state Vt looks like a fresh GSW encryption of the corresponding entry of the state vt , 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 = -var1≠1 (i) fl
2 [t]-, for i in [¸] and t œ [L].
For any x1 , . . . , x¸ œ {0, 1}, any sk = ≠s, 1 Ω KGen (1Ÿ ), at each step t œ [L], for all
indexes w œ [W ], the following holds:
1 2 1 2
Vt [w] , (Ci )iœ[¸] ¥s CÕt,w , (Ci )iœ[¸]
A B
Ai
where Ci = + xi G Ω Enc (sk, xi ) for i œ [¸], CÕt,w Ω Encrt (sk, vt [w]) for
s| Ai + e|i
Ú 1 2
q¸
(t, w) œ [L] ◊ [W ] and rt = r 2 i=1 ·t,i 1 + Îei Î2 .
Proof. We prove this lemma by induction on t œ [L]. At step t > 1, for 1 index w œ [W2] we
use a series of hybrid distributions Ht,w,k for 0 Æ k Æ 2 to prove that Vt [w] , (Ci )iœ[¸] ¥s
1 2 1 2 1 2
CÕt,w , (Ci )iœ[¸] . In particular Ht,w,0 = Vt [w] , (Ci )iœ[¸] , and Ht,w,2 = CÕt,w , (Ci )iœ[¸] .
5.4 Our scheme: circuit-private homomorphic evaluation for GSW 87
where Ci Ω Enc (sk, xi ), yt,w Ω DZm ,rÔ2 and CÕt≠1,wb Ω Encrt≠1 (sk, vt≠1 [wb ]) for b œ {0, 1}.
By induction hypothesis we have Ht≠1,wb ,0 ¥s Ht≠1,wb ,2 for b œ {0, 1}, i.e.,
1 2 1 2
Vt≠1 [wb ] , (Ci )iœ[¸] ¥s CÕt≠1,wb , (Ci )iœ[¸]
where Ci Ω Enc (sk, xi ) and CÕt≠1,wb Ω Encrt≠1 (sk, vt≠1 [wb ]) for b œ {0, 1}.
We use the fact that applying a function to two distributions does not increase their statistical
distance to obtain Ht,w,0 ¥s Ht,w,1 .
Hybrid Ht,w,2 . Let 1 2
Ht,w,2 = CÕ , (Ci )iœ[¸]
Û 3 . .2 4
2 . .
with Ci Ω Enc (sk, xi ), CÕ Ω Enc’ (sk, vt≠1 [w— ]) and ’ = rt≠1 + 2r2 1 + .evar(t) . .
By Lemma 5.4.6 we have:
A A B B
1 2 1 2 1 2 0
Chapter 5
Cvar(t) · G≠1 CÕt≠1,w1 + G ≠ Cvar(t) · G≠1 CÕt≠1,w0 + | , (Ci )iœ[¸]
rand rand yt,w
1 2
¥s CÕ , (Ci )iœ[¸]
where Ci Ω Enc (sk, xi ), yt,w Ω DZm ,rÔ2 , CÕt≠1,wb Ω Encrt≠1 (sk, vt≠1 [wb ]) for b œ {0, 1} and
Û 3 . .2 4
2 . .
CÕ Ω Enc’ (sk, vt≠1 [w— ]). Note that vt≠1 [w— ] = vt [w] and rt = rt≠1 + 2r2 1 + .evar(t) . =
’ from which we have that CÕ and CÕt,w are identically distributed, and directly Ht,w,1 ¥s
Ht,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.
Hybrid H1,w,1 . We have G≠1 rand (V0 [wb ]) = Grand (v0 [wb ] · G) for b œ {0, 1}. Notice that
≠1
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
x1 , . . . , x¸ œ {0, 1}, the following holds:
Proof. As shown in Lemma 5.4.7, the final result of the homomorphic evaluation of the
branching program is of the form
A B
A
VL [0] ¥s + xf G
s| A + f |
Ú 1 2
(n≠1)◊m q¸
where A Ω$ Zq , f ΩD Zm ,r L
and rL = r 2 i=1 1 + Îei Î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
(n≠1)◊m
of the argument of G≠1rand (·). Let Ai,t , Ai,t Ω$ Zq
Õ , fi,f , fi,t
Õ Ω D Ô
Zm ,r 1+Îe Î
, then the
i
joint distribution of the output of Sim and ciphertexts (Ci )iœ[¸] is
A A B B
1 2 q¸ q·i 1 ≠1 2 0
S, (Ci )iœ[¸] = i=1 Ci t=1 Grand (0) ≠ Grand (0) + y| + xf G, (Ci )iœ[¸]
≠1
A A B A Bt B
q¸ q·i Ai,t AÕi,t
¥s + , (Ci )iœ[¸]
i=1 t=1 s| Ai,t + fi,t s| AÕi,t + fi,t
Õ
by Lemma 5.3.1 AA B B
A
¥s , (Ci )iœ[¸]
s| A + f |
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
(Ci )iœ[¸] , thus concluding the proof.
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.
5.4 Our scheme: circuit-private homomorphic evaluation for GSW 89
Using the same proof as Lemma 5.4.8 the final output will be
2L≠·
A B
ÿi ≠1 1 2 0
V2L≠·i [0] Ω VL [0] + Ci G≠1
rand (Vt [0]) ≠ G≠1
rand (Vt [0]) + |
yt,0
t=L
2L≠·
A B
ÿi ≠1 1 2 0
¥s VL [0] + Ci G≠1
rand (0) ≠ G≠1
rand (0) + |
yt,0
t=L
the G≠1
rand (·) algorithm with parameter rf instead of r.
Chapter 5
5.4.4 Setting the parameters
In this section we show that, for appropriate values of the parameters, the output of the
homomorphic evaluation VL [0] decrypts to (x1 , . . . , 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), Lmax = 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 lwen≠1,q,DZ,–
Ò
5 ln(2m(1+1/Á))
• rØ fi for the correctness of G≠1
rand (·) sampling
1 2≠ 1
• r Ø 4 (1 ≠ Á) (2ÁÕ )2 m
for the leftover hash lemma
90 Chapter 5 Circuit privacy for homomorphic computations
Ô Ò
ln(2m(1+1/Á))
• rØ 5 (1 + B) fi for Lemma 5.3.4
1Ô 2
• q= mr– (m Lmax ¸max )1/2 for the correctness of decryption
• Lmax = poly(n),
• ¸max = poly(n),
Ô
• – = ( n),
• r = Â (n),
1 2
• q = Â n5/2 · Lmax · ¸max , a power of 2.
Note that the ciphertext size grows with log Lmax . Correctness follows directly.
Lemma 5.4.9 (Correctness). For any branching program of length L on ¸ variables, any
x1 , . . . , x¸ œ {0, 1}, the result of the homomorphic evaluation Cf = Eval ( , (C1 , . . . , C¸ ))
decrypts to (x1 , . . . , x¸ ) with overwhelming probability, where Ci Ω Enc (sk, xi ) for i œ [¸]
and sk Ω KGen (1Ÿ ).
Proof. Lemma
Ú
5.4.7 shows that the noise distribution
Ú
of the output Cf of Eval has param-
q¸ 1 2 q¸ 1 2
2
eter rf = r 2 i=1 ·i 1 + Îei Î , that is r 2L i=1 1 + Îei Î2 because of the padding
we applied to . We have rf Æ r 2L¸ (1 + C 2 –2 m) with C the universal
1 constant defined
2
in Lemma 5.2.3. Using the bounds Lmax and ¸max we have rL = O r– (m Lmax ¸max )1/2 .
Â
Ô 1 2
Finally, by a tail cutting argument, q = Â (rL n) = Â n5/2 Lmax ¸max is enough for de-
cryption to be correct with overwhelming probability.
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 )
‹
‚| v = 0
◊Z:e
Let — Ø Îti Î, where T = {t1 , . . . , tm } 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
|
we can exhibit m small vectors ui = (ti , ≠t|i e) , i œ [m] which are of norm
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 pri-
vacy for arbitrary modulus q, and any matrix H with public trapdoor by setting the Gaussian
parameter of H≠1 (·) to r = Â (—n).
5.5 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 homomor-
Chapter 5
phic signatures [BGG+14; GVW15]. Another issue is that we need to pad the branching
program so that each variable appears the same number of times, thus decreasing the ef-
ficiency 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 [OPP14]: 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 [LMSV12];
here, the technique that [DS16] 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].
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 encryp-
tion from lattice assumptions, but the so-called homomorphic encryption over the inte-
gers, stemming from the assumed hardness of the approximate GCD problem (cf. Defini-
tion 2.4.6). Specifically, our encryption scheme will be a symmetric version of that presented
in [DGHV10], 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.
Contents
Chapter 6
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.1.1 Private information retrieval . . . . . . . . . . . . . . . . . . . . . . 97
6.1.2 Oblivious transfer . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.1.3 Our contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.2 Our protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.3 The DGHV encryption scheme and its extension . . . . . . . . . . . 104
6.4 Implementing our protocol . . . . . . . . . . . . . . . . . . . . . . . 106
6.4.1 How to choose the random polynomials for conjunction queries . . . . 108
6.4.2 Handling the “false positives” . . . . . . . . . . . . . . . . . . . . . 111
6.4.3 Concrete parameters and benchmarks . . . . . . . . . . . . . . . . . 111
6.5 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
— 93 —
94 Chapter 6 Private information retrieval through homomorphic encryption
6.1 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 allow-
ing members of criminal organizations to exchange messages without meeting in person and
without incurring the risk of being intercepted. Internet essentially underpins criminal activ-
ities 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 typi-
cally 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 fea-
tures (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 [Gre13], 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,
6.1 Introduction 95
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., [Ows13]) 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
Chapter 6
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 rep-
resented 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
96 Chapter 6 Private information retrieval through homomorphic encryption
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 develop-
ments 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 possibili-
ties 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 [CLT11], 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 corre-
sponds, 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.
6.1 Introduction 97
Chapter 6
and Orlandi [CO15], based on the hardness of the well-established DDH assumption [Bon98].
requirement, meaning that the server never learns the user’s query. This protocol is inspired
by [BGH+13].
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.
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 Table 6.2.
2. DE encrypts the inverted database under some secret key sk which is never revealed
6.2 Our protocol 99
ID Name Surname
1 John Doe
2 Marc Smith
3 John Smith
Table 6.1: Toy-example of database.
Feature ID
Name=John 1, 3
Name=Marc 2
Surname=Doe 1
Surname=Smith 2, 3
Table 6.2: Inverted database corresponding to the toy example in Table 6.1.
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
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 kDE 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.
Chapter 6
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:
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 poly-
nomial 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
1 2
EnckDE (I) , SigkJU (EnckDE (I)) ,
8. DE verifies JU’s signature and, if everything is correct, decrypts the polynomial, cal-
culates its roots (i.e., the IDs), and sends to FR the information on those records.
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.
6.2 Our protocol 101
Simple query
France Germany Judge
r Ω$ ZıN
y := H (›) · re
y
z := y d
z
st := z · r≠1
check_match (st)
›, st, supporting material
≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠æ
verify & sign
:= signed enc. of polynomial corresponding to st
Ω≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠
6. JU verifies the supporting material and proceeds if it is satisfied. If this is the case,
JU fetches the two encrypted polynomials p1 (x) and p2 (x) corresponding to search
tokens 1 and 2 , homomorphically multiplies them together, and signs the resulting
encryption of the polynomial p1 (x) · p2 (x). Notice that the roots of p1 (x) · p2 (x) will
be the union of the roots of p1 (x) and p2 (x). Finally, JU hands the signed polynomial
back to FR.
8. DE verifies JU’s signature and, if everything is correct, decrypts the polynomial, cal-
Chapter 6
culates its roots (i.e., the IDs), and sends to FR the information on those records.
3. FR and DE repeat twice the simple sub-protocol for oblivious computation of search
102 Chapter 6 Private information retrieval through homomorphic encryption
Disjunction query
France Germany Judge
r1 , r2 Ω$ ZıN
y1 := H (›1 ) · r1e
y2 := H (›2 ) · r2e
y1 , y2
z1 := y1d
z2 := y2d
z1 , z2
st1 := z1 · r1≠1
st2 := z2 · r2≠1
check_match (st1 )
check_match (st2 )
›1 , ›2 , st1 , st2 , supporting material
≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠æ
verify & sign
:= signed enc. of polynomial
Ω≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠≠
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 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.
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.
8. JU verifies the supporting material and proceeds if it is satisfied. If this is the case,
JU fetches the two encrypted polynomials p1 (x) and p2 (x) corresponding to search
tokens 1 and 2 , then picks fresh random polynomials r1Õ (x) and r2Õ (x), computes
q Õ (x) := p1 (x) · r1Õ (x) + p2 (x) · r2Õ (x), signs it, and hands it back to FR.
10. DE verifies JU’s signature and, if everything is correct, decrypts the polynomial, cal-
culates its roots (i.e., the IDs), and sends to FR the information on those records.
Chapter 6
104 Chapter 6 Private information retrieval through homomorphic encryption
Conjunction query
France Germany Judge
r1 , r2 Ω$ ZıN
y1 := H (›1 ) · r1e
y2 := H (›2 ) · r2e
y1 , y2
z1 := y1d
z2 := y2d
z1 , z2
st1 := z1 · r1≠1
st2 := z2 · r2≠1
check_match (st1 )
check_match (st2 )
pı := conjunction(st1 , st2 )
pı
KGen (1Ÿ ) æ (sk, x0 ) : generate a random prime p of size ÷ bits. Generate a random prime
s0 of size “ ≠ ÷ bits, and let x0 = s0 p be a public parameter. Return sk = p and x0 .
Enc (sk, µ œ {0, 1}) æ c : generate a random positive integer s of “ ≠÷ bits, a random integer
r in (≠2fl , 2fl ), and output the ciphertext
c = ps + 2r + µ.
6.3 The DGHV encryption scheme and its extension 105
Extending the message space. It turns out that extending the message space to Zq
for some integer q, is immediate1 . It is sufficient to change the encryption and decryption
algorithms as follows:
c = ps + qr + µ.
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 x0 output by the KGen procedure will finally become clear. Let
(sk, x0 ) Ω KGen (1Ÿ ).
Homomorphic addition. Given two messages µ1 , µ2 œ Zq , and two DGHV ciphertexts
c1 , c2 such that ci Ω Enc (sk, µi ), the ciphertext c+ := (c1 + c2 ) mod x0 is a DGHV cipher-
text of µ1 + µ2 .
Showing that this is the case just requires performing the calculations:
Chapter 6
c+ mod x0 = ps1 + qr1 + µ1 + ps2 + qr2 + µ2 mod s0 p
= p (s1 + s2 ) + (r1 + r2 ) q + (µ1 + µ2 ) mod s0 p
= p [(s1 + s2 ) mod s0 ] + (r1 + r2 ) q + µ1 + µ2 .
Zq , and two DGHV ciphertexts c1 , c2 such that ci Ω Enc (sk, µi ), the ciphertext c◊ := (c1 · c2 )
mod x0 is a DGHV ciphertext of µ1 · µ2 .
Once again, showing that this holds is rather easy:
c◊ mod x0 = p (s1 s2 p + s1 µ2 + s2 µ1 + s1 r2 q + s2 r1 q)
+ q (r1 r2 q + r1 µ2 + r2 µ1 ) + µ1 µ2 mod s0 p
= p [(s1 s2 p + s1 µ2 + s2 µ1 + s1 r2 q + s2 r1 q) mod s0 ] + q (. . . ) + µ1 µ2 .
Remark 6.3.1 (On reduction modulo x0 (cf.[DGHV10, Section 3.3.2])). Note that reducing
modulo x0 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.
• An instantiation of the DGHV encryption scheme for encrypting and decrypting inte-
gers, 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;
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)
[Gt12]. 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++ [DP18] which, among
others, contains an implementation of the hash functions SHA-2 and SHA-3. Particular
6.4 Implementing our protocol 107
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 [CLT11], 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
Chapter 6
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
108 Chapter 6 Private information retrieval through homomorphic encryption
• A browser application for the party that wants to execute a query (FR). This applica-
tion 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, encCoeff0 , encCoeff1 , . . .
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 [10], 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++” [Loh13]
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.
z := y d mod N
z
st = z · r≠1 mod N
Chapter 6
Figure 6.6: Screenshot of the querying party when performing a disjunctive query.
110 Chapter 6 Private information retrieval through homomorphic encryption
Figure 6.7: Screenshot of the trusted party (Judge) when processing a disjunctive query.
Figure 6.8: Screenshot of the responding party when disclosing the information after a dis-
junctive query.
6.4 Implementing our protocol 111
The random polynomials ri (x) are chosen such that their degrees respect deg (r1 (x)) =
deg (p2 (x)) ≠ 1 and deg (r2 (x)) = deg (p1 (x)) ≠ 1. This ensures that pÕ (x) is distributed
uniformly among all the polynomials of the same degree, as per [BGH+13, Lemma 2 and
Corollary 3]. Another important observation is about the roots of these random polynomials.
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.
Moreover, following an analogous reasoning, let R1 , R2 be the set of roots of random poly-
nomials r1 (x), r2 (x), respectively. It is obvious that any root that belongs to R1 fl R2 will
also be a root of pÕ (x). However, as already mentioned in Section 6.4.1, this will not be a
problem since R1 ™ F and R2 ™ 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 œ/ I1 fl I2 .
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 I1 fl I2 .
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
Chapter 6
1 2 1 2 1 2
(1) (1) (2) (2) (N_REPS) (N_REPS)
r1 (x), r2 (x) , r1 (x), r2 (x) , ..., r1 (x), r2 (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.
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])
• fl = 2Ÿ, to prevent
1 2the improved gcd attack by Chen and Nguyen [CN12], which has
complexity O 2fl/2
• “ = ÷ 2 Ê (log Ÿ), to prevent the orthogonal lattice attack. To be conservative, one can
take “ = 8÷ 2
• N = 104
• f = 2≠32 ¥ 10≠9.63
• Ÿ = 128
• k=3
• q ¥ 107.21
• fl = 256
• ÷ = 560
• “ = 2508800
In the polynomials representing the list of indices, each (encrypted) coefficient is approx-
imately 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
A B A B
1 1
N ·‹ 1+ · (size of enc. coefficient) ¥ 7.55 · ‹ 1 + GBytes,
naverage naverage
Total bandwidth
Simple query ¥ 1510 d KB
Conjunction query ¥ 6795 (d1 + d2 ) KB
Disjunction query ¥ 1510 (d1 + d2 ) KB
Simple query
3 · 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 (d1 + d2 ) KB)+1 bit+4096 bits+2 (3 · 755 (d1 + d2 ) KB + 2048 bits)
Disjunctive query
6.5 Discussions
The protocol we presented improves on the protocol currently in place for cross-border co-
Chapter 6
operation 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 ob-
tain the database records, in case the intersection is non-empty. These modifications clearly
114 Chapter 6 Private information retrieval through homomorphic encryption
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 lim-
its 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.
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.
Contents
Chapter 7
— 115 —
116 Chapter 7 Conclusions and open questions
7.1 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 neces-
sary 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 allow-
ing 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).
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 af-
ter 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, an-
other 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?
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.
Chapter 7
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.
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 homomor-
phic encryption scheme?
The implementation that we realized was based on the DGHV encryption scheme [DGHV10],
but there are plenty of other possibilities, like lattice-based encryption schemes that rely on
the LWE assumption (cf. Assumption 2.4.4).
— 119 —
120 Notation
Notation
General mathematical notation
:= “Is defined as”
N The set of natural numbers
Z The set of integer numbers
Zq 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
È·, ·Í The inner product
|S| The size (or cardinality) of a set S
ÁyË The smallest integer z such that z Ø y
ÂyÊ The biggest integer z such that z Æ y
ÂyË The closest integer to y, with ties broken upward
ηÎp,Œ Norms
x Ω$ S x is sampled uniformly at random from S
(X, Y ) The statistical distance between X and Y
N A neural network
O (·) , O (·) , (·) , Ê (·)
 Asymptotic notation
Pr [E] The probability of the event E
HŒ (X) The min entropy of X
General cryptographic notation
Ÿ The security parameter
c
¥ Computationally indistinguishable
¥s Statistically indistinguishable
H A hash function
D A discrete Gaussian
pk A public key
sk A secret key
evk An evaluation key
ksk A key-switching key
bk A bootstrapping key
Notation specific to Chapter 5
G The gadget matrix
G≠1det (·) Bit decomposition
G≠1 (·) Randomized bit decomposition
fl The Gaussian function
A lattice
⁄i ( ) The i-th minimum of
det ( ) The determinant of
÷Á ( ) The smoothing parameter of
Abbreviations
— 121 —
List of Illustrations
Figures
2.1 Game for IND-CPA security. . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 A two-dimensional lattice with two different bases. . . . . . . . . . . . . . . . 18
Tables
4.1 Comparison of the three alternative BlindRotate algorithms. . . . . . . . . . . 63
4.2 Accuracy obtained when evaluating the models in the clear on the MNIST
test set. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.3 The security parameters we use for the different kinds of ciphertexts. . . . . . 65
4.4 Message space: theoretically required values and how we set them in our
experiments with FHE-DiNN. . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.5 Results of homomorphic evaluation of two DiNNs on the full test set. . . . . . 67
4.6 Comparison with Cryptonets and its amortized version (denoted by Cryptonetsı ). 70
— 123 —
Bibliography
[08a] Council Decision 2008/615/JHA of 23 June 2008 on the stepping up of cross-
border cooperation, particularly in combating terrorism and cross-border crime.
http : / / eur - lex . europa . eu / legal - content / EN / TXT / ?uri = celex :
32008D0615. 2008 (cit. on p. 96).
[08b] Council Decision 2008/616/JHA of 23 June 2008 on the implementation of
Decision 2008/615/JHA on the stepping up of cross-border cooperation, par-
ticularly in combating terrorism and cross-border crime. http://eur- lex.
europa.eu/legal-content/EN/TXT/?uri=celex:32008D0616. 2008 (cit. on
p. 96).
[10] Flask (a Python microframework): web development, one drop at a time. http:
//flask.pocoo.org/. 2010 (cit. on p. 108).
[ABDP15] Michel Abdalla, Florian Bourse, Angelo De Caro, and David Pointcheval. “Sim-
ple Functional Encryption Schemes for Inner Products”. In: PKC 2015. Ed. by
Jonathan Katz. Vol. 9020. LNCS. Springer, Heidelberg, Mar. 2015, pp. 733–
751. doi: 10.1007/978-3-662-46447-2_33 (cit. on p. 57).
[ACPS09] Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. “Fast Cryp-
tographic Primitives and Circular-Secure Encryption Based on Hard Learning
Problems”. In: CRYPTO 2009. Ed. by Shai Halevi. Vol. 5677. LNCS. Springer,
Heidelberg, Aug. 2009, pp. 595–618 (cit. on pp. 74, 81).
[AGHS13] Shweta Agrawal, Craig Gentry, Shai Halevi, and Amit Sahai. “Discrete Gaus-
sian Leftover Hash Lemma over Infinite Domains”. In: ASIACRYPT 2013,
Part I. Ed. by Kazue Sako and Palash Sarkar. Vol. 8269. LNCS. Springer, Hei-
delberg, Dec. 2013, pp. 97–116. doi: 10.1007/978-3-642-42033-7_6 (cit. on
pp. 73, 79).
[AJL+12] Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod
Vaikuntanathan, and Daniel Wichs. “Multiparty Computation with Low Com-
munication, Computation and Interaction via Threshold FHE”. In: EURO-
CRYPT 2012. Ed. by David Pointcheval and Thomas Johansson. Vol. 7237.
LNCS. Springer, Heidelberg, Apr. 2012, pp. 483–501 (cit. on p. 37).
[Ajt96] Miklós Ajtai. “Generating Hard Instances of Lattice Problems (Extended Ab-
stract)”. In: 28th ACM STOC. ACM Press, May 1996, pp. 99–108 (cit. on
pp. 19, 20).
[ALS16] Shweta Agrawal, Benoît Libert, and Damien Stehlé. “Fully Secure Func-
tional Encryption for Inner Products, from Standard Assumptions”. In:
CRYPTO 2016, Part III. Ed. by Matthew Robshaw and Jonathan Katz.
Vol. 9816. LNCS. Springer, Heidelberg, Aug. 2016, pp. 333–362. doi: 10.1007/
978-3-662-53015-3_12 (cit. on p. 57).
— 125 —
126 Bibliography
[And10] Nate Anderson. How “cell tower dumps” caught the High Country Bandits
— and why it matters. Ars Technica. https : / / arstechnica . com / tech -
policy/ 2013/08 /how- cell - tower- dumps- caught- the- high- country-
bandits-and-why-it-matters/. 2010 (cit. on p. 95).
[AP13] Jacob Alperin-Sheriff and Chris Peikert. “Practical Bootstrapping in Quasilin-
ear Time”. In: CRYPTO 2013, Part I. Ed. by Ran Canetti and Juan A. Garay.
Vol. 8042. LNCS. Springer, Heidelberg, Aug. 2013, pp. 1–20. doi: 10.1007/
978-3-642-40041-4_1 (cit. on p. 30).
[AP14] Jacob Alperin-Sheriff and Chris Peikert. “Faster Bootstrapping with Polyno-
mial Error”. In: CRYPTO 2014, Part I. Ed. by Juan A. Garay and Rosario
Gennaro. Vol. 8616. LNCS. Springer, Heidelberg, Aug. 2014, pp. 297–314. doi:
10.1007/978-3-662-44371-2_17 (cit. on pp. 27, 30, 33, 34, 38, 53, 72–77,
84).
[APS15] Martin R. Albrecht, Rachel Player, and Sam Scott. On The Concrete Hardness
Of Learning With Errors. Cryptology ePrint Archive, Report 2015/046. http:
//eprint.iacr.org/2015/046. 2015 (cit. on pp. 21, 65).
[AR13] Divesh Aggarwal and Oded Regev. “A Note on Discrete Gaussian Combi-
nations of Lattice Vectors”. In: CoRR abs/1308.2405 (2013). url: http://
arxiv.org/abs/1308.2405 (cit. on pp. 73, 79).
[Avn16] Amir Avni. Two Weeks of Colorizebot - Conclusions and Statistics. http :
/ / whatimade . today / two - weeks - of - colorizebot - conclusions - and -
statistics/. 2016 (cit. on p. 47).
[BBB+17] Anthony Barnett, Charlotte Bonte, Carl Bootland, Joppe W. Bos, Wouter
Castryck, Anamaria Costache, Louis Goubin, Ilia Iliashenko, Tancrède Lep-
oint, Michele Minelli, Pascal Paillier, Nigel P. Smart, Frederik Vercauteren,
Srinivas Vivek, and Adrian Waller. Processing Encrypted Data Using Homo-
morphic Encryption. Workshop on Data Mining with Secure Computation,
SODA project. 2017 (cit. on p. 9).
[BEHZ16] Jean-Claude Bajard, Julien Eynard, Anwar Hasan, and Vincent Zucca. A Full
RNS Variant of FV like Somewhat Homomorphic Encryption Schemes. Cryp-
tology ePrint Archive, Report 2016/510. http://eprint.iacr.org/2016/
510. 2016 (cit. on p. 38).
[Ben16] Fabrice Ben Hamouda–Guichoux. “Diverse modules and zero-knowledge”. The-
ses. PSL Research University, July 2016. url: https : / / tel . archives -
ouvertes.fr/tel-01492851 (cit. on p. 13).
[Ber14] Daniel J. Bernstein. A subfield-logarithm attack against ideal lattices. Blog post.
http://blog.cr.yp.to/20140213-ideal.html. 2014 (cit. on p. 21).
[BF17] Guillaume Bonnoron and Caroline Fontaine. “A Note on Ring-LWE Security
in the Case of Fully Homomorphic Encryption”. In: INDOCRYPT 2017. Ed.
by Arpita Patra and Nigel P. Smart. Vol. 10698. LNCS. Springer, Heidelberg,
Dec. 2017, pp. 27–43 (cit. on p. 21).
[BFM88] Manuel Blum, Paul Feldman, and Silvio Micali. “Non-Interactive Zero-
Knowledge and Its Applications (Extended Abstract)”. In: 20th ACM STOC.
ACM Press, May 1988, pp. 103–112 (cit. on p. 10).
127
[BGG+14] Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko,
Gil Segev, Vinod Vaikuntanathan, and Dhinakaran Vinayagamurthy. “Fully
Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Gar-
bled Circuits”. In: EUROCRYPT 2014. Ed. by Phong Q. Nguyen and Elisa-
beth Oswald. Vol. 8441. LNCS. Springer, Heidelberg, May 2014, pp. 533–556.
doi: 10.1007/978-3-642-55220-5_30 (cit. on p. 91).
[BGH+13] Dan Boneh, Craig Gentry, Shai Halevi, Frank Wang, and David J. Wu. “Pri-
vate Database Queries Using Somewhat Homomorphic Encryption”. In: ACNS
13. Ed. by Michael J. Jacobson Jr., Michael E. Locasto, Payman Mohassel,
and Reihaneh Safavi-Naini. Vol. 7954. LNCS. Springer, Heidelberg, June 2013,
pp. 102–118. doi: 10.1007/978-3-642-38980-1_7 (cit. on pp. 98, 111, 112).
[BGN05] Dan Boneh, Eu-Jin Goh, and Kobbi Nissim. “Evaluating 2-DNF Formulas on
Ciphertexts”. In: TCC 2005. Ed. by Joe Kilian. Vol. 3378. LNCS. Springer,
Heidelberg, Feb. 2005, pp. 325–341 (cit. on p. 26).
[BGV12] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. “(Leveled) fully
homomorphic encryption without bootstrapping”. In: ITCS 2012. Ed. by Shafi
Goldwasser. ACM, Jan. 2012, pp. 309–325 (cit. on pp. 27, 29, 31, 33, 38, 52,
72).
[BISW17] Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu. “Lattice-Based
SNARGs and Their Application to More Efficient Obfuscation”. In: EURO-
CRYPT 2017, Part III. Ed. by Jean-Sébastien Coron and Jesper Buus Nielsen.
Vol. 10212. LNCS. Springer, Heidelberg, Apr. 2017, pp. 247–277 (cit. on p. 10).
[BISW18] Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu. “Quasi-Optimal
SNARGs via Linear Multi-Prover Interactive Proofs”. In: EUROCRYPT 2018,
Part III. Ed. by Jesper Buus Nielsen and Vincent Rijmen. Vol. 10822. LNCS.
Springer, Heidelberg, Apr. 2018, pp. 222–255. doi: 10 . 1007 / 978 - 3 - 319 -
78372-7_8 (cit. on p. 10).
[BLMZ17] Fabrice Benhamouda, Tancrède Lepoint, Claire Mathieu, and Hang Zhou. “Op-
timization of Bootstrapping in Circuits”. In: 28th SODA. Ed. by Philip N.
Klein. ACM-SIAM, Jan. 2017, pp. 2423–2433 (cit. on p. 30).
[BLP+13] Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien
Stehlé. “Classical hardness of learning with errors”. In: 45th ACM STOC. Ed.
by Dan Boneh, Tim Roughgarden, and Joan Feigenbaum. ACM Press, June
2013, pp. 575–584 (cit. on p. 76).
[BMMP18] Florian Bourse, Michele Minelli, Matthias Minihold, and Pascal Paillier. Fast
Homomorphic Evaluation of Deep Discretized Neural Networks. CRYPTO
2018. https://eprint.iacr.org/2017/1114. 2018 (cit. on p. 8).
[Bon98] Dan Boneh. “The decision Diffie-Hellman problem”. In: Third Algorith-
mic Number Theory Symposium (ANTS). Vol. 1423. LNCS. Invited paper.
Springer, Heidelberg, 1998 (cit. on p. 97).
[Bou17] Florian Bourse. “Functional Encryption for Inner-Product Evaluations”. The-
ses. Université de recherche Paris Sciences et Lettres, Dec. 2017. url: https:
//hal.archives-ouvertes.fr/tel-01665276 (cit. on p. 13).
128 Bibliography
[BPDS16] Daniel J. Bernstein, Chris Peikert, Léo Ducas, and Damien Stehlé. Ideal-SVP
attacks? Discussion on Google Groups. https://groups.google.com/forum/
#!topic/cryptanalytic-algorithms/y-wAnhmGsIo. 2016 (cit. on p. 21).
[BPL+15] Daniel J. Bernstein, Chris Peikert, Vadim Lyubashevsky, Thomas Wunderer,
and Jean-François Biasse. Soliloquy. Discussion on Google Groups. https :
/ / groups . google . com / forum / # ! topic / cryptanalytic - algorithms /
GdVfp5Kbdb8. 2015 (cit. on p. 21).
[BPMW16] Florian Bourse, Rafaël del Pino, Michele Minelli, and Hoeteck Wee. “FHE
Circuit Privacy Almost for Free”. In: CRYPTO 2016, Part II. Ed. by Matthew
Robshaw and Jonathan Katz. Vol. 9815. LNCS. Springer, Heidelberg, Aug.
2016, pp. 62–89. doi: 10.1007/978-3-662-53008-5_3 (cit. on p. 9).
[BPTG15] Raphael Bost, Raluca Ada Popa, Stephen Tu, and Shafi Goldwasser. “Machine
Learning Classification over Encrypted Data”. In: NDSS 2015. The Internet
Society, Feb. 2015 (cit. on p. 51).
[BV11a] Zvika Brakerski and Vinod Vaikuntanathan. “Efficient Fully Homomorphic
Encryption from (Standard) LWE”. In: 52nd FOCS. Ed. by Rafail Ostrovsky.
IEEE Computer Society Press, Oct. 2011, pp. 97–106 (cit. on pp. 27, 31, 33,
72, 91).
[BV11b] Zvika Brakerski and Vinod Vaikuntanathan. “Fully Homomorphic Encryp-
tion from Ring-LWE and Security for Key Dependent Messages”. In:
CRYPTO 2011. Ed. by Phillip Rogaway. Vol. 6841. LNCS. Springer, Heidel-
berg, Aug. 2011, pp. 505–524 (cit. on pp. 27, 31, 72).
[BV14] Zvika Brakerski and Vinod Vaikuntanathan. “Lattice-based FHE as secure as
PKE”. In: ITCS 2014. Ed. by Moni Naor. ACM, Jan. 2014, pp. 1–12 (cit. on
pp. 27, 72–75, 78, 84).
[CB16] Matthieu Courbariaux and Yoshua Bengio. “BinaryNet: Training Deep Neural
Networks with Weights and Activations Constrained to +1 or -1”. In: CoRR
abs/1602.02830 (2016). url: http://arxiv.org/abs/1602.02830 (cit. on
p. 69).
[CCK+13] Jung Hee Cheon, Jean-Sébastien Coron, Jinsu Kim, Moon Sung Lee, Tan-
crède Lepoint, Mehdi Tibouchi, and Aaram Yun. “Batch Fully Homomorphic
Encryption over the Integers”. In: EUROCRYPT 2013. Ed. by Thomas Jo-
hansson and Phong Q. Nguyen. Vol. 7881. LNCS. Springer, Heidelberg, May
2013, pp. 315–335. doi: 10.1007/978-3-642-38348-9_20 (cit. on p. 39).
[CGGI16a] I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène. TFHE: Fast Fully
Homomorphic Encryption Library over the Torus. https : / / github . com /
tfhe/tfhe. 2016 (cit. on pp. 38, 65).
[CGGI16b] Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène.
“Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Sec-
onds”. In: ASIACRYPT 2016, Part I. Ed. by Jung Hee Cheon and Tsuyoshi
Takagi. Vol. 10031. LNCS. Springer, Heidelberg, Dec. 2016, pp. 3–33. doi:
10.1007/978-3-662-53887-6_1 (cit. on pp. 30, 38, 41, 52–54, 57, 58, 65, 67).
129
[CGGI17] Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène.
“Faster Packed Homomorphic Operations and Efficient Circuit Bootstrap-
ping for TFHE”. In: ASIACRYPT 2017, Part I. Ed. by Tsuyoshi Takagi and
Thomas Peyrin. Vol. 10624. LNCS. Springer, Heidelberg, Dec. 2017, pp. 377–
408 (cit. on pp. 30, 38, 41, 52, 63).
[CGKS95] Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. “Private
Information Retrieval”. In: 36th FOCS. IEEE Computer Society Press, Oct.
1995, pp. 41–50 (cit. on p. 97).
[CH11] Henry Cohn and Nadia Heninger. Approximate common divisors via lattices.
Cryptology ePrint Archive, Report 2011/437. http : / / eprint . iacr . org /
2011/437. 2011 (cit. on p. 23).
[Cha04] Yan-Cheng Chang. “Single Database Private Information Retrieval with Log-
arithmic Communication”. In: ACISP 04. Ed. by Huaxiong Wang, Josef
Pieprzyk, and Vijay Varadharajan. Vol. 3108. LNCS. Springer, Heidelberg,
July 2004, pp. 50–61. doi: 10.1007/978-3-540-27800-9_5 (cit. on p. 97).
[CHH+16] Hao Chen, Kyoohyung Han, Zhicong Huang, Amir Jalali, and Kim Laine. Sim-
ple Encrypted Arithmetic Library (SEAL) v2.3.0. https://www.microsoft.
com/en-us/research/project/simple-encrypted-arithmetic-library/.
2016 (cit. on p. 38).
[Cho+15] François Chollet et al. Keras. https://github.com/keras-team/keras. 2015
(cit. on p. 64).
[CLT11] Emiliano De Cristofaro, Yanbin Lu, and Gene Tsudik. “Efficient Techniques
for Privacy-Preserving Sharing of Sensitive Information”. In: Trust and Trust-
worthy Computing - 4th International Conference, TRUST 2011, Pittsburgh,
PA, USA, June 22-24, 2011. Proceedings. Ed. by Jonathan M. McCune, Boris
Balacheff, Adrian Perrig, Ahmad-Reza Sadeghi, M. Angela Sasse, and Yolanta
Beres. Vol. 6740. Lecture Notes in Computer Science. Springer, 2011, pp. 239–
253. doi: 10.1007/978-3-642-21599-5_18. url: http://dx.doi.org/10.
1007/978-3-642-21599-5_18 (cit. on pp. 96, 107).
[CM15] Michael Clear and Ciaran McGoldrick. “Multi-identity and Multi-key Leveled
FHE from Learning with Errors”. In: CRYPTO 2015, Part II. Ed. by Rosario
Gennaro and Matthew J. B. Robshaw. Vol. 9216. LNCS. Springer, Heidelberg,
Aug. 2015, pp. 630–656. doi: 10.1007/978-3-662-48000-7_31 (cit. on p. 37).
[CMNT11] Jean-Sébastien Coron, Avradip Mandal, David Naccache, and Mehdi Tibouchi.
“Fully Homomorphic Encryption over the Integers with Shorter Public Keys”.
In: CRYPTO 2011. Ed. by Phillip Rogaway. Vol. 6841. LNCS. Springer, Hei-
delberg, Aug. 2011, pp. 487–504 (cit. on pp. 23, 39).
[CMS12] D. Cire an, U. Meier, and J. Schmidhuber. “Multi-column Deep Neural Net-
works for Image Classification”. In: ArXiv e-prints (Feb. 2012). arXiv: 1202.
2745 [cs.CV] (cit. on p. 51).
130 Bibliography
[CN12] Yuanmi Chen and Phong Q. Nguyen. “Faster Algorithms for Approximate
Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over
the Integers”. In: EUROCRYPT 2012. Ed. by David Pointcheval and Thomas
Johansson. Vol. 7237. LNCS. Springer, Heidelberg, Apr. 2012, pp. 502–519
(cit. on pp. 23, 112).
[CNT12] Jean-Sébastien Coron, David Naccache, and Mehdi Tibouchi. “Public Key
Compression and Modulus Switching for Fully Homomorphic Encryption over
the Integers”. In: EUROCRYPT 2012. Ed. by David Pointcheval and Thomas
Johansson. Vol. 7237. LNCS. Springer, Heidelberg, Apr. 2012, pp. 446–464
(cit. on p. 23).
[CO15] Tung Chou and Claudio Orlandi. “The Simplest Protocol for Oblivious
Transfer”. In: LATINCRYPT 2015. Ed. by Kristin E. Lauter and Fran-
cisco Rodríguez-Henríquez. Vol. 9230. LNCS. Springer, Heidelberg, Aug. 2015,
pp. 40–58. doi: 10.1007/978-3-319-22174-8_3 (cit. on p. 97).
[Cou17] Geoffroy Couteau. “Zero-Knowledge Proofs for Secure Computation”. Theses.
PSL research University, Nov. 2017. url: https : / / hal . inria . fr / tel -
01668125 (cit. on p. 13).
[Cré88] Claude Crépeau. “Equivalence Between Two Flavours of Oblivious Transfers”.
In: CRYPTO’87. Ed. by Carl Pomerance. Vol. 293. LNCS. Springer, Heidel-
berg, Aug. 1988, pp. 350–354 (cit. on p. 97).
[CWM+17] Hervé Chabanne, Amaury de Wargny, Jonathan Milgram, Constance Morel,
and Emmanuel Prouff. “Privacy-Preserving Classification on Deep Neural Net-
work”. In: IACR Cryptology ePrint Archive 2017 (2017), p. 35 (cit. on p. 52).
[Cyb89] G. Cybenko. “Approximation by superpositions of a sigmoidal function”. In:
Mathematics of Control, Signals and Systems 2.4 (Dec. 1989), pp. 303–314.
issn: 1435-568X. doi: 10.1007/BF02551274. url: https://doi.org/10.
1007/BF02551274 (cit. on p. 47).
[DFGK14] George Danezis, Cédric Fournet, Jens Groth, and Markulf Kohlweiss. “Square
Span Programs with Applications to Succinct NIZK Arguments”. In: ASI-
ACRYPT 2014, Part I. Ed. by Palash Sarkar and Tetsu Iwata. Vol. 8873.
LNCS. Springer, Heidelberg, Dec. 2014, pp. 532–550. doi: 10.1007/978-3-
662-45611-8_28 (cit. on p. 10).
[DGHV10] Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. “Fully
Homomorphic Encryption over the Integers”. In: EUROCRYPT 2010. Ed. by
Henri Gilbert. Vol. 6110. LNCS. Springer, Heidelberg, May 2010, pp. 24–43
(cit. on pp. 5, 27, 39, 72, 93, 103–106, 118).
[DGL+16] Nathan Dowlin, Ran Gilad-Bachrach, Kim Laine, Kristin Lauter, Michael
Naehrig, and John Wernsing. CryptoNets: Applying Neural Networks to En-
crypted Data with High Throughput and Accuracy. Tech. rep. Feb. 2016.
url: https : / / www . microsoft . com / en - us / research / publication /
cryptonets - applying - neural - networks - to - encrypted - data - with -
high-throughput-and-accuracy/ (cit. on pp. 45, 52, 69).
131
[JRS17] Aayush Jain, Peter M. R. Rasmussen, and Amit Sahai. Threshold Fully Ho-
momorphic Encryption. Cryptology ePrint Archive, Report 2017/257. http:
//eprint.iacr.org/2017/257. 2017 (cit. on p. 37).
[JVC18] Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan.
“Gazelle: A Low Latency Framework for Secure Neural Network Inference”.
In: CoRR abs/1801.05507 (2018). arXiv: 1801.05507. url: http://arxiv.
org/abs/1801.05507 (cit. on p. 51).
[Kag] Kaggle. Digit recognizer. https://www.kaggle.com/c/digit- recognizer
(cit. on p. 47).
[KGV14] Alhassan Khedr, Glenn Gulak, and Vinod Vaikuntanathan. SHIELD: Scal-
able Homomorphic Implementation of Encrypted Data-Classifiers. Cryptology
ePrint Archive, Report 2014/838. http://eprint.iacr.org/2014/838. 2014
(cit. on p. 33).
[Kil92] Joe Kilian. “A Note on Efficient Zero-Knowledge Proofs and Arguments (Ex-
tended Abstract)”. In: 24th ACM STOC. ACM Press, May 1992, pp. 723–732
(cit. on p. 10).
[KO97] Eyal Kushilevitz and Rafail Ostrovsky. “Replication is NOT Needed: SINGLE
Database, Computationally-Private Information Retrieval”. In: 38th FOCS.
IEEE Computer Society Press, Oct. 1997, pp. 364–373 (cit. on p. 97).
[KTX08] Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa. “Concurrently Se-
cure Identification Schemes Based on the Worst-Case Hardness of Lattice
Problems”. In: ASIACRYPT 2008. Ed. by Josef Pieprzyk. Vol. 5350. LNCS.
Springer, Heidelberg, Dec. 2008, pp. 372–389 (cit. on p. 57).
[LBBH98] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. “Gradient-Based Learning
Applied to Document Recognition”. In: Proceedings of the IEEE 86.11 (Nov.
1998), pp. 2278–2324 (cit. on pp. 47, 50, 51, 69).
[LCB98] Y. LeCun, C. Cortes, and C.J.C. Burges. THE MNIST DATABASE of hand-
written digits. http://yann.lecun.com/exdb/mnist/. 1998 (cit. on p. 51).
[Lep14] Tancrède Lepoint. “Design and Implementation of Lattice-Based Cryptogra-
phy”. Theses. Ecole Normale Supérieure de Paris - ENS Paris, June 2014. url:
https://tel.archives-ouvertes.fr/tel-01069864 (cit. on p. 25).
[Lep16] T. Lepoint. FV-NFLlib. GitHub repository. https : / / github . com /
CryptoExperts/FV-NFLlib. 2016 (cit. on p. 38).
[Lip04] Helger Lipmaa. An Oblivious Transfer Protocol with Log-Squared Communi-
cation. Cryptology ePrint Archive, Report 2004/063. http://eprint.iacr.
org/2004/063. 2004 (cit. on p. 97).
[LJLA17] Jian Liu, Mika Juuti, Yao Lu, and N. Asokan. “Oblivious Neural Network
Predictions via MiniONN Transformations”. In: ACM CCS 17. Ed. by Bhavani
M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu. ACM Press,
Oct. 2017, pp. 619–631 (cit. on p. 51).
[LLL82] A. K. Lenstra, H. W. Lenstra, and L. Lovász. “Factoring polynomials with
rational coefficients”. In: MATH. ANN 261 (1982), pp. 515–534 (cit. on p. 22).
135
[LMSV12] Jake Loftus, Alexander May, Nigel P. Smart, and Frederik Vercauteren. “On
CCA-Secure Somewhat Homomorphic Encryption”. In: SAC 2011. Ed. by Ali
Miri and Serge Vaudenay. Vol. 7118. LNCS. Springer, Heidelberg, Aug. 2012,
pp. 55–72 (cit. on p. 91).
[Loh13] Niels Lohmann. JSON for modern C++. https://github.com/nlohmann/
json. 2013 (cit. on p. 108).
[LPR10] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. “On Ideal Lattices
and Learning with Errors over Rings”. In: EUROCRYPT 2010. Ed. by Henri
Gilbert. Vol. 6110. LNCS. Springer, Heidelberg, May 2010, pp. 1–23 (cit. on
pp. 21, 53, 60).
[LTV12] Adriana López-Alt, Eran Tromer, and Vinod Vaikuntanathan. “On-the-fly
multiparty computation on the cloud via multikey fully homomorphic encryp-
tion”. In: 44th ACM STOC. Ed. by Howard J. Karloff and Toniann Pitassi.
ACM Press, May 2012, pp. 1219–1234 (cit. on p. 37).
[MAP+15] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen,
Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, San-
jay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard,
Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Lev-
enberg, Dan Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah,
Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Tal-
war, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas,
Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu,
and Xiaoqiang Zheng. TensorFlow: Large-Scale Machine Learning on Hetero-
geneous Systems. Software available from tensorflow.org. 2015. url: https:
//www.tensorflow.org/ (cit. on p. 64).
[MBG+16] Carlos Aguilar Melchor, Joris Barrier, Serge Guelton, Adrien Guinet, Marc-
Olivier Killijian, and Tancrède Lepoint. “NFLlib: NTT-Based Fast Lattice Li-
brary”. In: CT-RSA 2016. Ed. by Kazue Sako. Vol. 9610. LNCS. Springer,
Heidelberg, Feb. 2016, pp. 341–356. doi: 10.1007/978-3-319-29485-8_20
(cit. on p. 38).
[Méa17] Pierrick Méaux. “Hybrid fully homomorphic framework”. Theses. Université de
recherche Paris Sciences et Lettres, Dec. 2017. url: https://hal.archives-
ouvertes.fr/tel-01665358 (cit. on p. 13).
[MHN13] Andrew L. Maas, Awni Y. Hannun, and Andrew Y. Ng. “Rectifier nonlinearities
improve neural network acoustic models”. In: in ICML Workshop on Deep
Learning for Audio, Speech and Language Processing. 2013 (cit. on p. 46).
[Mic10] Daniele Micciancio. “A first glimpse of cryptography’s Holy Grail”. In: Com-
mun. ACM 53.3 (2010), p. 96. doi: 10.1145/1666420.1666445. url: http:
//doi.acm.org/10.1145/1666420.1666445 (cit. on p. 26).
[Mic94] Silvio Micali. “CS Proofs (Extended Abstracts)”. In: 35th FOCS. IEEE Com-
puter Society Press, Nov. 1994, pp. 436–453 (cit. on p. 10).
136 Bibliography
[RSA78] Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. “A Method for Ob-
taining Digital Signature and Public-Key Cryptosystems”. In: Communica-
tions of the Association for Computing Machinery 21.2 (1978), pp. 120–126
(cit. on pp. 3, 5).
[Sch87] C.P. Schnorr. “A hierarchy of polynomial time lattice basis reduction algo-
rithms”. In: Theoretical Computer Science 53.2 (1987), pp. 201–224. issn: 0304-
3975. doi: https://doi.org/10.1016/0304-3975(87)90064-8. url: http:
//www.sciencedirect.com/science/article/pii/0304397587900648 (cit.
on p. 22).
[SS10] Damien Stehlé and Ron Steinfeld. “Faster Fully Homomorphic Encryption”.
In: ASIACRYPT 2010. Ed. by Masayuki Abe. Vol. 6477. LNCS. Springer,
Heidelberg, Dec. 2010, pp. 377–394 (cit. on pp. 27, 72).
[SSTX09] Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. “Efficient
Public Key Encryption Based on Ideal Lattices”. In: ASIACRYPT 2009. Ed.
by Mitsuru Matsui. Vol. 5912. LNCS. Springer, Heidelberg, Dec. 2009, pp. 617–
635 (cit. on p. 21).
[Ste98] Julien P. Stern. “A New Efficient All-Or-Nothing Disclosure of Secrets Pro-
tocol”. In: ASIACRYPT’98. Ed. by Kazuo Ohta and Dingyi Pei. Vol. 1514.
LNCS. Springer, Heidelberg, Oct. 1998, pp. 357–371 (cit. on p. 97).
[SV10] Nigel P. Smart and Frederik Vercauteren. “Fully Homomorphic Encryption
with Relatively Small Key and Ciphertext Sizes”. In: PKC 2010. Ed. by Phong
Q. Nguyen and David Pointcheval. Vol. 6056. LNCS. Springer, Heidelberg, May
2010, pp. 420–443 (cit. on pp. 27, 72).
[SYY99] Tomas Sander, Adam Young, and Moti Yung. “Non-Interactive CryptoCom-
puting For NC1”. In: 40th FOCS. IEEE Computer Society Press, Oct. 1999,
pp. 554–567 (cit. on pp. 8, 72).
[Uni05] European Union. Prüm Convention. http://register.consilium.europa.
eu/doc/srv?l=EN&f=ST%2010900%202005%20INIT. 2005 (cit. on p. 96).
[Uni12] Supreme Court of the United States. United States v. Jones. https://www.
supremecourt.gov/opinions/11pdf/10-1259.pdf. 2012 (cit. on p. 95).
[Yao86] Andrew Chi-Chih Yao. “How to Generate and Exchange Secrets (Extended
Abstract)”. In: 27th FOCS. IEEE Computer Society Press, Oct. 1986, pp. 162–
167 (cit. on p. 51).
[ZK16] Sergey Zagoruyko and Nikos Komodakis. “Wide Residual Networks”. In: CoRR
abs/1605.07146 (2016). url: http://arxiv.org/abs/1605.07146 (cit. on
p. 52).
[ZPB+17] Ying Zhang, Mohammad Pezeshki, Philemon Brakel, Saizheng Zhang, César
Laurent, Yoshua Bengio, and Aaron C. Courville. “Towards End-to-End
Speech Recognition with Deep Convolutional Neural Networks”. In: CoRR
abs/1701.02720 (2017). arXiv: 1701.02720. url: http://arxiv.org/abs/
1701.02720 (cit. on p. 47).
139
[ZRM+13] M.D. Zeiler, M. Ranzato, R. Monga, M. Mao, K. Yang, Q.V. Le, P. Nguyen,
A. Senior, V. Vanhoucke, J. Dean, and G.E. Hinton. “On Rectified Linear
Units For Speech Processing”. In: 38th International Conference on Acoustics,
Speech and Signal Processing (ICASSP). Vancouver, 2013 (cit. on p. 46).
[ZYC16] Qingchen Zhang, Laurence T. Yang, and Zhikui Chen. “Privacy Preserving
Deep Computation Model on Cloud for Big Data Feature Learning”. In: IEEE
Transactions on Computers 65.5 (2016), pp. 1351–1362. issn: 0018-9340. doi:
doi.ieeecomputersociety.org/10.1109/TC.2015.2470255 (cit. on p. 52).
[ZYL+17] TanPing ZHOU, XiaoYuan YANG, LongFei LIU, Wei ZHANG, and Yi-
Tao DING. Faster Bootstrapping with Multiple Addends. Cryptology ePrint
Archive, Report 2017/735. http://eprint.iacr.org/2017/735. 2017 (cit.
on pp. 30, 61, 62).
Résumé Abstract
Le chiffrement totalement homomorphe permet Fully homomorphic encryption enables computation
d’effectuer des calculs sur des données chiffrées sans on encrypted data without leaking any information
fuite d’information sur celles-ci. Pour résumer, un about the underlying data. In short, a party can en-
utilisateur peut chiffrer des données, tandis qu’un crypt some input data, while another party, that does
serveur, qui n’a pas accès à la clé de déchiffrement, not have access to the decryption key, can blindly per-
peut appliquer à l’aveugle un algorithme sur ces en- form some computation on this encrypted input. The
trées. Le résultat final est lui aussi chiffré, et il ne final result is also encrypted, and it can be recovered
peut être lu que par l’utilisateur qui possède la clé only by the party that possesses the secret key.
secrète.
In this thesis, we present new techniques/designs for
Dans cette thèse, nous présentons des nouvelles tech- FHE that are motivated by applications to machine
niques et constructions pour le chiffrement totalement learning, with a particular attention to the problem of
homomorphe qui sont motivées par des applications homomorphic inference, i.e., the evaluation of already
en apprentissage automatique, en portant une atten- trained cognitive models on encrypted data.
tion particulière au problème de l’inférence homomor-
phe, c’est-à-dire l’évaluation de modèles cognitifs déjà First, we propose a novel FHE scheme that is tailored
entrainé sur des données chiffrées. to evaluating neural networks on encrypted inputs.
Our scheme achieves complexity that is essentially
Premièrement, nous proposons un nouveau schéma independent of the number of layers in the network,
de chiffrement totalement homomorphe adapté à whereas the efficiency of previously proposed schemes
l’évaluation de réseaux de neurones artificiels sur des strongly depends on the topology of the network.
données chiffrées. Notre schéma atteint une complex-
ité qui est essentiellement indépendante du nombre Second, we present a new technique for achieving cir-
de couches dans le réseau, alors que l’efficacité des cuit privacy for FHE. This allows us to hide the com-
schéma proposés précédemment dépend fortement de putation that is performed on the encrypted data, as
la topologie du réseau. is necessary to protect proprietary machine learning
algorithms. Our mechanism incurs very small com-
Ensuite, nous présentons une nouvelle technique pour putational overhead while keeping the same security
préserver la confidentialité du circuit pour le chiffre- parameters.
ment totalement homomorphe. Ceci permet de cacher
l’algorithme qui a été exécuté sur les données chiffrées, Together, these results strengthen the foundations of
comme nécessaire pour protéger les modèles proprié- efficient FHE for machine learning, and pave the way
taires d’apprentissage automatique. Notre mécanisme towards practical privacy-preserving deep learning.
rajoute un coût supplémentaire très faible pour un
niveau de sécurité égal. Ensemble, ces résultats ren- Finally, we present and implement a protocol based
forcent les fondations du chiffrement totalement ho- on homomorphic encryption for the problem of private
momorphe efficace pour l’apprentissage automatique, information retrieval, i.e., the scenario where a party
et représentent un pas en avant vers l’apprentissage wants to query a database held by another party with-
profond pratique préservant la confidentialité. out revealing the query itself.