Michaël, Jacques Axel Nicolas

Ainsi

Wendy Miro

Nozomi, Nami, Marilou D Sara

Rama

Hyon-Song Léa

Pierre Maura

Adrien Diana

Liz

Yebin, Luis, Beatriz Alberto Sylvain

Jenny Jinoh

Mei- Hung Miso

Elvis Jan

Pablo Antonio

Emilio Anne Ludwig

Estefanía Emile Charline

Jin Paul

Geumbit, Hyewon, Tom Hye Joo

Jin

Bernard Merci Aussi Le Directeur

Françoise Soulès

Caroline De Maubus

Victor, Franck Alex Esposito

Martine Huve

Sabine Bienaimé

Jean-François Gonzales

Je

Mes Compagnons De Voyage Flavio

Lucho, Vinicius, Cassio, Igor, Celio, Ciro, Pedro Juan Raphael

Mario Flavia

Mes Amis Russes Anastasia

Alexei Gerard

Marta Luigi

Ted Davide

Federico

Umberto Sara

Matteo

Pietro Lorenzo

Alessandra Consuelo

Cruz & Trinidad

Gabriel & Élodie

Carlos & Alba

Mélanie, Perrine, Oliver, Gustav, Greta, Étienne, Joëlle Chers Sophie

Josette Marion

Raphaël, Joaquim Nina Benjamin

Marie Y Camilo

Juan Sebastián

Francisca Manuel

José Ignacio

Padres, Inés Mis

Rosa Clemente

Exequiel, Nicolás Lorenzo

Luisa

Daniel

Mi Sofía

Sobrina Emilia

Lors de son cours donné au Master d'Algèbre Appliquée à la Cryptographie de l'Université de Versailles, Louis Goubin m'a parlé pendant une pause café des schémas de chiffrement complètement homomorphe. J'avais déjà un haut degré d'admiration pour lui, son cours et sa personnalité, et quand il m'a proposé de travailler sous sa tutelle et sur ce sujet fantastique, ma réponse n'a pas tardé. Sa remarquable politesse, gentillesse, et finesse d'esprit sont couplés à une acuité et à une intuition exceptionnelle. Dès la première rencontre, on ne peut passer à coté de ces qualités, grâce à sa disponibilité et à son honnêteté. J'ai eu l'énorme chance de travailler avec un grand homme, et mon humble gratitude l'accompagnera pendant le reste de ma vie.

Les rapporteurs de ce manuscrit sont Duong Hieu Phan et Fabien Laguillaumie, professeurs à l'Université de Limoges et Lyon respectivement. Je vous remercie pour la lecture de ce manuscrit, et pour vos commentaires encourageants

Introduction

The word cryptography comes from the Greek kryptos and graphia -it means "hidden writing". Cryptography is the science of protecting sensitive information, as it allows to transform readable text into gibberish writings called ciphertexts. These random-looking messages can in turn be reversed into readable text, but only by those whose the message was intended for. The first transformation is called encryption, and the reverse transformation is called decryption (un-hiding). Disguising secrets is inherent to human nature: the first reported usage of secret writing dates back thousands of years. Since the famous Enigma machine used in World War II and its rotor solver1 , increasingly refined ways of hiding information and attacking ciphertexts are available, whose complexities escape by far the human scope. Today, cryptography is a machine's game, played billions of times a day in order to protect our data and communications. Recently, a new kind of encryption made its way into our cryptography toolkit, and exciting research has been conducted to defend and improve this new instrument: Fully Homomorphic Encryption (henceforth FHE).

A beautiful peculiarity of cryptography as a science is that the basic, invariant and common element in all its branches is information itself. It is fair to say that information is to cryptography as energy is to physics. A bit more far-fetched would be to say that Einstein's relativity is to physics as FHE is to cryptography, but, on the very least, it has been referred to as the holy grail of Cryptography.

Let us have a glance at this with the following question. Alice sends Bob a ciphertext c, duly encrypting a message m. If f (m) is some function of the message, can Bob deduce an encryption of f (m) with the sole knowledge of c? Much counterintuitively, the answer is yes for a special family of encryption schemes.

Oblivious cookie baking. Alice encrypts butter, sugar, eggs, flour and chocolate, she gives these cipher-ingredients to Bob and asks him to bake a chocolate cookie. Notice that Bob is not able to decrypt since he does not possess Alice's secret, thus he faces the task without awareness of the ingredients -and eventually does not know what a chocolate cookie is. Nonetheless, he does the baking and in the end, Alice decrypts the chocolate cookie and eats it with warm milk. Bob does not understand what has just happened, and there is no cookie for him since the result of his baking is only decryptable by Alice.

In 1978, two years after the revolutionary works of Diffie and Hellman, cryptographers Ronald Rivest, Len Adleman and Michael Dertouzos raised in [START_REF] Rivest | On Data Banks and Privacy Homomorphisms[END_REF] the question of performing arbitrary operations on ciphertexts, without access to the underlying data:

"Encryption is a well-known technique for preserving the privacy of sensitive information. One of the basic, apparently inherent, limitations of this technique is that an information system working with encrypted data can at most store or retrieve the data for the user; any more complicated operations seem to require that the data be decrypted before being operated on. This limitation follows from the choice of encryption functions used, however, and although there are some truly inherent limitations on what can be accomplished, we shall see that it appears likely that there exist encryption functions which permit encrypted data to be operated on without preliminary decryption of the operands, for many sets of interesting operations. These special encryption functions we call "privacy homomorphisms"; they form an interesting subset of arbitrary encryption schemes (called "privacy transformations")".

These encryption functions were at first called Privacy Homomorphisms, in the sense that given an encryption E(D) of some data D and a functionality f , it is possible to obtain an encryption of f (D) without knowing D nor any decryption secret, hence providing an homomorphism between message and ciphertext spaces. In fact, in some encryption schemes, plaintext and ciphertext messages lie in algebraic structures, like a ring or a group, and partial algebraic homomorphisms between the two can sometimes be constructed. In their seminal paper, they give four examples of simple (insecure) privacy homomorphisms, based on discrete-logarithms, RSA-like encryption, Chinese Remainder Theorem and Radix-n respectively (these last two are non-deterministic). Even before the existence of a secure privacy homomorphism was proven -or believed, for that matter -multiple applications arose specially in the context of outsourced processing. As a matter of fact, some years later there were several public encryption schemes already allowing this for some functionalities. For (a by now folklore) instance, basic RSA encryption happens to be multiplicative. If c 1 = m e 1 mod n and c 2 = m e 2 mod n, then c 3 = c 1 × c 2 mod n is an encryption of m 1 × m 2 . In classic cryptography, this is to be avoided at all costs: an attacker can construct a valid ciphertext by simply multiplying two or more encryptions -basic RSA is said to be malleable. In light of this, any privacy homomorphism is malleable.

Notice, however, that it is not clear how to construct a valid RSA encryption of m 1 + m 2 from c 1 , c 2 . Hence basic RSA is not known to be an almighty privacy homomorphism: in order to evaluate an arbitrary polynomial-time computation f defined as a circuit C with + and × gates, a full privacy homomorphism must at least describe two operations corresponding to these gates (or any other complete set of operations). Other partial privacy homomorphisms followed: Paillier, Okamoto-Uchiyama, Naccache-Stern, Cohen-Fischer, all of them achieving homomorphic addition or multiplication of messages, but not both. At this point, community was already on the search for almighty privacy homomorphisms, who were baptized as fully homomorphic encryption schemes.

The first example of an additively and multiplicatively homomorphic scheme is due to Boneh, Goh and Nissim. Their scheme, based on bilinear couplings in elliptic curves, was capable of evaluating any number of + gates, but only one × gate. This was a partial victory, since their scheme allows to evaluate all affine, bilinear and quadratic functionalities. Another effort was a scheme proposed by Fellows and Koblitz, based on the hardness of a membership problem in the ring F q [X 1 , • • • , X n ], however it suffered some attacks and is not considered secure.

All of these efforts and the apparent slippery of true FHE were coupled with some degree of skepticism. In spite of this, the quest continued until 2009, when Craig Gentry proposed the first fully homomorphic encryption scheme in his Ph.D. dissertation at Stanford University. In theory, his scheme is capable of homomorphically evaluating any polynomial-time functionality f over encrypted data. His merit does not only consist in having the insight to find the mathematical object that allowed the construction, but also proposing generic transformations between a family of weak homomorphic schemes -called somewhat homomorphic encryption (SHE) schemes -and a fully homomorphic encryption scheme. The schemes in this family must own a self-reference property called "bootstrapping" that allows to "clean" the output of a large circuit.

In [START_REF] Gentry | Computing on Encrypted Data[END_REF][START_REF] Gentry | A Fully Homomorphic Encryption Scheme[END_REF][START_REF] Gentry | Fully Homomorphic Encryption Using Ideal Lattices[END_REF][START_REF] Gentry | Computing Arbitrary Functions of Encrypted Data[END_REF], Gentry describes this revolutionary idea and gives an explicit construction of a family of SHE schemes relying on ideal lattices. This family is parameterized by the maximum depth of allowed circuits, and can be transformed into an FHE scheme. Consequently, Gentry had constructed the first blindfolded computing machine. Since his breakthrough, other schemes have been proposed, all of them following this blueprint.

In 2009, the theoretical playground in cryptographic security was fairly ready to the arrival of FHE, as malleability of ciphertexts was widely discussed. Homomorphic encryption allowed to relativise previous notions, in that it gives honest use of ciphertext modification and introduces new levels of security that are, and rightly so, considered to be grand contributions.

Two flat tires of this thrilling discovery are the ones of efficiency and underlying assumptions. Indeed, Gentry's ideal lattices scheme is complex and suffers from enormous ciphertext expansion and public-key size, and its celebrated bootstrapping procedure had to wait for two years to be actually implemented. On the other hand its security relied in, though reasonable and arguable, new assumptions. The fact that this scheme was not even remotely comparable to other encryption schemes provoked a second wave of skepticism, yet, thanks to enthusiastic scientific research, multiple optimizations and new candidates have been proposed to meet applications. There are now five independent families of homomorphic schemes, each member ad-dressing a different challenge from the community (efficiency, optimal depth of decryption, optimization for static functions, identity-based, attribute-based, support for multiple users, fast bootstrapping). We describe these families in this Introduction in 1. 5.

Today, we can encrypt, decrypt and add packages of binary messages in a matter of milliseconds, and multiply, bootstrap and relinearize in some seconds. Manifestly, this is sufficient for some growing set of exciting applications, see 1.3.

Overview of this Dissertation

In the rest of this Chapter, we describe some practical applications, report some connections with other cryptography fields, explain how proposals are today ordered into five branches, give a formal definition of FHE and list underlying computationallyhard problems.

In Chapter 2, we revisit Gentry's first FHE proposal based on ideal lattices. We also propose a proof-of-concept implementation and a digression about natural densities of some special sets of lattices.

Our main contributions are given in Chapters 3 and 4. In Chapter 3, we describe a key-recovery attack against Gentry's first scheme that, in spite of the enormous parameters selected for security and feasibility, recovers a secret-key of the scheme in sub-quadratic time with a reasonable number of decryption queries. This is the subject of a paper submitted to an international conference on Cryptography. In Chapter 4, we describe a technique of one-way gluing keys from different users of an FHE scheme, addressing for the first time a natural betrayal problem that arises in hierarchic scenarios. With this, we deal with a homomorphic proxy re-encryption paradigm we detected. To that end, we define the Excalibur property and show that the celebrated NTRU-based FHE of Lopez-Alt et al. displays it. We reproduce an article included in the proceedings of the Indocrypt 2016 conference [START_REF] Goubin | Blending FHE-NTRU Keys -The Excalibur Property[END_REF].

Finally, in Chapter 5, we report a C++ implementation of the FHE scheme of Brakerski, Gentry and Vaikuntanathan, which is believed to be one of the most promising candidates in terms of efficiency.

In addition, appendix A "Seeing the whole picture: An article reading guide" may be of help when approaching the disconcerting and multidimensional literature of fully homomorphic encryption.

Reported practical applications

In principle, all outsourced statistical analysis of sensible data can be performed homomorphically. This is now being done in some domains. We collect here some of the recent -public -applications.

Reported practical applications

Processing Genomic Data

Immense progress has been done in study of genomes, and large databases of human genomic data are essential to researchers. However, as pointed out in the report [START_REF] Ayday | The Chills and Thrills of Whole Genome Sequencing[END_REF], given a short DNA sequence of an individual, it is possible to search by pattern matching in available genomic databases, and eventually retrieve his whole sequence. With this, the individual privacy is highly invaded: the attacker may compute illness risks, physical characteristics and eventually identity (for instance having access to hospital or police records). For that reason, there is legal and ethic need to protect database volunteers. Researchers have recently propose to encrypt the human DNA sequence with a fully homomorphic encryption scheme, in order to conduct meaningful statistic experiences over the encrypted data. In [START_REF] Lauter | Private Computation on Encrypted Genomic Data[END_REF] and [START_REF] Kim | Private genome analysis through homomorphic encryption[END_REF], such homomorphic evaluations are performed, aiming to process encrypted genomic data. Authors present computational experiments and report correct and efficient evaluation of statistic tests such as Pearson's Goodness-of-Fit test, D � and r 2 measures for linkage disequilibrium, Estimation Maximization for haplotyping, and Cochran-Armitage tests. In the follow-up article [START_REF] Bos | Private Predictive Analysis on Encrypted Medical Data[END_REF], authors explain how to perform predictive analysis of encrypted genomic data. In addition, they provide a working implementation of an on-line privacy-respecting cardiovascular disease (such as heart failures) probability predictor.

Electronic voting

Recently in [START_REF] Chillotti | A Homomorphic LWE Based E-voting Scheme[END_REF], authors presented a new post-quantum e-voting protocol using lattice-based fully homomorphic encryption. Their scheme proves to be very transparent, since no additional verifications need to be taken care of when counting votes or revealing the final result of an election. Indeed, former protocols already proposed to count votes homomorphically, but relied on non-interactive zero-knowledge proofs carried out by several trustees for ballot validations, which looks like a tailbiting drawback. In [START_REF] Chillotti | A Homomorphic LWE Based E-voting Scheme[END_REF], only two trustees are required to give independent proofs of correct decryptions.

Targeted Advertising

Gender, age, location and known interests of an individual are currently been used to provide personalized advertising. Yet if a mobile phone sends the owner's location to an advertising provider who answers tailored ads, this provider can keep record of his client's activities. Ensuring privacy is thus paramount, and it can be done performing the advertising algorithms homomorphically in a certain scenario, see [START_REF] Lauter | Can Homomorphic Encryption Be Practical[END_REF]. Also in [START_REF] Jeckmans | Efficient Privacy-Enhanced Familiarity-Based Recommender System[END_REF], authors use secure multi-party computation protocols and somewhat homomorphic encryption to secure privacy when the user is asking recommendations for a given product to friendly users, preserving everyone's Chapter 1. Fully Homomorphic Encryption: A review anonymity.

Outsourced forensic image recognition

Detection of illegal images in a confiscated hard-drive is done by comparing the contents with a confidential database of hashes of known illegal images. From [START_REF] Bösch | SOFIR: Securely outsourced Forensic image recognition[END_REF] we quote: "The Dutch police, for example, owns a database consisting of hash values of so-called PIPs (Picture that Interests the Police), such as images showing glorification or overexposure of violence, indignity or pornographic content, like zoophilia and pedophilia. When the police confiscates equipment with data storage, the hash of each picture found in the storage is computed and looked up in the PIP database. If there are many matches, the police knows that the confiscated equipment contains PIPs and the investigation is continued manually to crosscheck."

To stop the distribution of such images inside a company's in-line traffic, for instance, it would be helpful to have remote access to this confidential databases, however law enforcement agencies refuse outsourcing at all costs to prevent ill use thereof. In this article, authors propose SOFIR, an on-line algorithm which encrypts databases and allows recognition of illegal images in a company's traffic, sending reports in real time while respecting privacy of other files.

Biometric authentication

Biometric authentication consists in identification of an individual using binary encodings of some biological attribute, such as fingerprints or retina. A scan allowing some small error can be performed in order to authenticate, followed by pattern matching against a database. In [YSK + 13] authors provide a privacy-preserving secure pattern-matching, optimized for biometric clearance.

1.4 Connections: FHE and ... As expected, fully homomorphic encryption did not land in a desert. It has proven to be closely connected to numerous problems and research subjects.

... Functional Encryption

A functional encryption scheme is a public-key encryption scheme allowing generation of special secret-keys such that, when used in decryption, the output is a specific function of the plaintext. Namely, for a valid function f there is a secret key sk f such that for a ciphertext c encrypting m, the decryption Dec(sk, c f ) 1.4. Connections: FHE and ... outputs f (m) and nothing more. This notion controls malleability, in as much as secrets must be possessed in order to learn more functions of the ciphertext. In opposition, FHE gives total freedom of computation, but the output is encrypted. Authors in [ABF + 13] provide a detailed study of this relationship and show that under certain assumptions, a functional encryption scheme supporting operations on two ciphertexts actually implies the construction of an FHE scheme.

... Cryptographic Obfuscation

Obfuscating a program is hiding the information embedded in the code, without hurting functionality. The obfuscated program behaves like a black-box implementation of the original one, in the sense that no information other than the input and output can be obtained from the program. With FHE it is possible to obfuscate some functionalities, but the result is by definition, encrypted, thus conditioned decryption may be necessary to perform the last step of the program, i.e. producing meaningful output. A natural idea is to hide this conditioned decryption inside the program. Heavily using FHE and cryptographic multilinear maps as building bricks, authors in [GGH + 13] proposed the first candidate for cryptographic obfuscation.

... Secure Multi-Party Computation

In a secure multi-party computation (MPC) protocol, two or more mutually distrusting parties wish to compute a function of their joint data. For instance, Alice holds some value x and Bob holds y, they want to perform some protocol such that they both learn f (x, y) and nothing more that can be deduced from their input and output. Using a variant of FHE called Multikey-FHE, authors in [START_REF] López-Alt | On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[END_REF] showed that the general MPC problem can be reduced to a specific MPC instance -the one of a joint decryption of a ciphertext in their scheme.

... Identity-/Attribute-Based Encryption

IBE is a scenario where the public-key of a user can be deduced from a tag such as a string (e.g. "Name.Surname", address, e-mail, phone number, subscription number). This was proposed in [START_REF] Shamir | Identity-Based Cryptosystems and Signature Schemes[END_REF], and it relies on an authority that distributes secret-keys to users corresponding to their public-key after proper clearance. Two constructions were proposed in 2001 using quadratic residues and Weil pairings of elliptic curves (see [START_REF] Cocks | An Identity Based Encryption Scheme Based on Quadratic Residues[END_REF] and [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF] respectively). In an attribute-based encryption scheme, decryption of a ciphertext is possible whenever the decryptor meets some predefined conditions. In other words, secret-keys depend on user's attributes, e.g. company, name, kind of subscription. The first ABE scheme was proposed in [START_REF] Sahai | Fuzzy Identity-Based Encryption[END_REF] (see [START_REF] Lee | A Survey on Attribute-based Encryption Schemes of Access Control in Cloud Environments[END_REF] for a nice survey). Hybrid schemes have been proposed in [START_REF] Gentry | Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based[END_REF]: Attribute-Based HE, Identity-Based FHE (IBFHE) and Multi-identity IBFHE. Interestingly, these constructions provide compilers that enhance any LWE-based FHE scheme with the desired property.

... Proxy Re-encryption

A proxy re-encryption procedure allows the public transformation of ciphertext c decryptable by Alice into a ciphertext c � decryptable by Bob. It is said to be multi-hop if this new ciphertext can be in turn re-encrypted for another party, and bidirectional if there are reverse transformations. This is useful in mail redirecting applications. It has been claimed (for instance in the seminal work [START_REF] Gentry | A Fully Homomorphic Encryption Scheme[END_REF]) that following the bootstrapping argument, FHE is the first candidate for multi-hop bidirectional proxy re-encryption. However, we point out in [START_REF] Goubin | Blending FHE-NTRU Keys -The Excalibur Property[END_REF] that this relies on a non-standard assumption. We propose an "automatic re-encryption" key-generation procedure that addresses this paradigm and, moreover, solves an interesting betrayal issue in hierarchic structures. This is detailed on Chapter 4.

The five families

To the date, there are five recognizable families of homomorphic schemes, addressing different security challenges, exhibiting fancy properties and competing for efficiency.

Ideal Lattices

The first proposal of a fully homomorphic scheme uses the notion of ideal lattices. These are regular lattices laying in the image of a ring homomorphism between R = Z[x]/(f (x)) and Z n for some monic polynomial f of degree n, when the homomorphism is fed with a principal ideal of R. By structure transport, this gives a nice representation of Z n , supporting addition, multiplication and basis reduction. With these three operations and careful sampling of two ideal lattices I, J, Gentry constructed the first fully homomorphic scheme in [START_REF] Gentry | A Fully Homomorphic Encryption Scheme[END_REF].

Simplified variants and new proposals follow with works of Smart and Vercauteuren with improvements by Stehlé, Steinfeld, Loftus and May. See [START_REF] Stehlé | Faster Fully Homomorphic Encryption[END_REF][START_REF] Loftus | On CCA-Secure Somewhat Homomorphic Encryption[END_REF].

As an homage to his dissertation, we devote Chapter 2 to the study of this scheme in sufficient level of detail. We consider this study to be rewarding and, contradicting the pro-FHE enthusiasm exposed in this Introduction, we propose a new key-recovery attack in Chapter 3 that reveals completely the secret key. We consider the relatively new and rarely used in cryptography problem of guessing a Z n -parallelepiped given a collection of points. We mention that authors in [START_REF] Loftus | On CCA-Secure Somewhat Homomorphic Encryption[END_REF] presented the only homomorphic scheme known to be CCA-1 secure so far.

The five families

Integers

Only a year after the first proposal, van Dijk, Gentry, Halevi and Vaikuntanathan proposed a fully homomorphic encryption scheme that used integers as plaintexts and ciphertexts, in [START_REF] Van Dijk | Fully Homomorphic Encryption over the Integers[END_REF]. This allowed a much better understanding of the efficiency gap between homomorphic and classic schemes, and conceptually suggests that FHE is not that artificial, as algorithms are simple to understand. This scheme has been revisited recently to support batching in [CCK + 13], allowing to pack ciphertexts and perform parallel homomorphic operations. However, to the date this family is not considered to be the most promising.

(Ring-)Learning with errors

Brakerski and Vaikuntanathan proposed a scheme based on the learning with errors problem, which has been deeply studied since its introduction by Regev in 2005 (see [START_REF] Regev | On Lattices, Learning with Errors, Random Linear Codes, and Cryptography[END_REF][START_REF] Regev | The learning with errors problem[END_REF]). This problem is conjectured to be hard to solve, and faces a polynomially large linear system in which every equation is almost correct -approximated up to some small error. Let us reproduce Regev's folklore example here; an instance of the LWE problem is to recover an integer vector s where "≈" means that the equation is correct up to an error of ±1. As the abstract of [START_REF] Brakerski | Fully Homomorphic Encryption Without Bootstrapping[END_REF] reads, "We present a radically new approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled fully homomorphic encryption schemes (capable of evaluating arbitrary polynomial-size circuits), without Gentry's bootstrapping procedure" They give constructions based in LWE and its ring variant, and introduced novel noise-management techniques called relinearization and modulus switching, which replace the bootstrapping procedure. In this scenario, homomorphic evaluation and decryption climb a ladder of decreasing moduli and scale the ciphertexts properly to ensure correctness. Also, in [START_REF] Brakerski | Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP[END_REF] Brakerski proposed a scheme in which the same modulus is used throughout evaluation; these schemes are called scale invariant. Some remarks and tweaks in this family bring a great deal of efficiency improvements, allowing for instance to bootstrap a ciphertext in less than 1s [START_REF] Ducas | FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second[END_REF] and subsequently in less than 0.1s [START_REF] Chillotti | Faster Fully Homomorphic Encryption: Bootstrapping in less than 0.1 Seconds[END_REF].

= (s 1 , s 2 , s 3 , s 4 ) ∈ Z 4 satisfying                    14s 1 + 15s

NTRU-based

The "N -th degree TRUncated" scheme is an efficient lattice based encryption scheme proposed in [START_REF] Hoffstein | NTRU: A Ring-Based Public Key Cryptosystem[END_REF]. For some time, due to absence of formal proofs, its security level was not clear. In 2011, Stehlé and Steinfeld [START_REF] Stehlé | Making NTRU as Secure as Worst-Case Problems over Ideal Lattices[END_REF] provided modifications that allowed to complete the proofs (more precisely, the use of cyclotomic rings and a power of 2 degree). In the groundbreaking article [START_REF] López-Alt | On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[END_REF], authors constructed an homomorphic scheme based on this encryption flavor. Their contribution is large: they achieve homomorphic support for multiple users proposing Multikey-FHE, conceive the notion of on-the-fly MPC, and propose a leading candidate for practical FHE. Based on this work, Goubin and V. propose in [START_REF] Goubin | Blending FHE-NTRU Keys -The Excalibur Property[END_REF] a method to blend NTRU keys together, addressing a betrayal problem in hierarchic encryption scenarios. For more on this see Chapter 4.

Approximate eigenvectors

In all previous BGV-like encryption schemes, ciphertext multiplication are seemingly complex, artificial procedures. Motivated by this, Gentry, Sahai and Waters in [START_REF] Gentry | Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based[END_REF] proposed a new generation of fully homomorphic schemes. Ciphertext and key representation is new, while security is still based on variants of the LWE problem. In this scheme, a secret-key is a vector v in Z n q with at least one large coefficient. A ciphertext C corresponding to this key is a n × n binary matrix over Z q for a large prime q, such that v is close to an eigenvector of C, the corresponding eigenvalue being the underlying plaintext m ∈ {0, 1}. In other words, m, C and v verify

C • v = m • v + e mod q
for small e ∈ Z n q . Homomorphic evaluation is simply given by matrix arithmetic, producing asymptotic improvements in efficiency: their construction is asymptotically faster than any previous FHE scheme (alas with a large constant keeping it out of the practical scope). To present their analysis, authors consider {NAND} as the complete set of operations to evaluate circuits. In addition, matrix multiplication is not commutative, and therefore some ways to multiply ciphertexts are better than others, regarding noise growth.

Definition of FHE

We give in this section a theoretical definition of homomorphic encryption. Let us first remark why we use circuits instead of general functions.

Circuits versus functions

Homomorphically solving a maze runs in worst-case complexity. Suppose that P is a 2-D labyrinth solver algorithm. It receives the plot of a maze M and a point x inside the maze, and the algorithm outputs a path from x to the exterior of the maze, or the symbol ⊥ if there is no exit. Typically, such algorithm must test conditions such as "if the point y ∈ M has already been visited", or "if this is a dead end". If for any reason the maze walls, its inside points and the position of the player are probabilistically encrypted, such comparisons become comparison or identity circuits with an encrypted output. The whole algorithm can be carried out homomorphically and it actually produces the correct (encrypted) output, but because of this lack of decision it runs in its worst-case complexity, outputting the path as a complicated polynomial expression depending on all points of the maze. The same applies when running set or graph algorithms homomorphically. This is why we only consider being able to evaluate circuits of fixed depth, instead of general functions or procedures. To avoid this paradigm for the moment, all research in homomorphic encryption embraces this consideration.

Definitions

Let us now give some definitions.

Definition 1.6.1 (HE). An homomorphic encryption scheme is a public-key encryption scheme E with four PPT algorithms with polynomial complexity in the security parameter λ:

-Keygen: λ � → (sk, pk), generates a key pair.

-Enc: (pk, π) � → ψ, encrypts a message π under public-key pk.

-Dec: (sk, ψ) � → π, decrypts a ciphertext ψ under secret-key sk.

-Eval: (pk, C, ψ 1 , . . . , ψ t ) � → ψ, where C is a circuit that belongs to a set of allowed circuits C, evaluates the circuit C gate by gate on inputs ψ 1 , . . . , ψ t .

The evaluation algorithm should describe how to perform addition and multiplication gates (or any other complete set of operations). If the resulting ciphertext decrypts to the desired message, we say that the scheme is correct. Let C be a collection of circuits: Definition 1.6.2 (Correct HE). An HE scheme is correct for all circuits in C if for all C ∈ C, (sk, pk) ← Keygen(1 λ ) and for all plaintexts π 1 , . . . , π t , if ψ i ← Enc(pk, π i ) for i = 1, . . . , t, then

ψ ← Eval(pk, C, ψ 1 , . . . , ψ t ) implies Dec(sk, ψ) = C(π 1 , . . . , π t ).
The decryption algorithm can be itself written as a circuit D; if the scheme correctly evaluates D it will be later possible to introduce the bootstrapping procedure. Hence the following definition: Definition 1.6.3 (Compact HE). An homomorphic encryption scheme is compact if there is a polynomial f such that for any value of λ, the algorithm Dec E may be computed by a circuit of depth ≤ f (λ).

I.e. an homomorphic encryption scheme is compact if its decryption algorithm is of reasonable size. Definition 1.6.4 (Compact evaluation). An homomorphic scheme compactly evaluates a set of circuits C if it is compact and correct for all circuits in C. Definition 1.6.5 (FHE). A Fully Homomorphic Encryption Scheme is an homomorphic scheme that compactly evaluates all circuits. Definition 1.6.6 (Levelled FHE). A family of HE schemes {E (d) , d ∈ N} is levelled fully homomorphic if (i) they all have the same decryption circuit D (ii) for each d ∈ N, E (d) compactly evaluates every circuit of depth ≤ d and all algorithms have polynomial complexity.

Security definitions

Consider the following game between parties A and B.

Game 1.6.1. Let E be a public key encryption scheme of plaintext space P and algorithms E.Keygen, E.Enc, E.Dec. Let A, B be two parties.

1. A generates (pk, sk) ← E.Keygen(λ) and publishes pk.

For

Adv(B, E, λ) = |Pr(b = b � ) -1/2|.
Definition 1.6.8 (Semantic security). We say that E is semantically secure against CPA,CCA1,CCA2 if it is not possible for a CPA,CCA1,CCA2 (respectively) adversary to win the game with a non negligible advantage and polynomial time in λ.

For a homomorphic scheme, consider the following game.

Game 1.6.2. Let H be a homomorphic encryption scheme of plaintext space P and algorithms H.Keygen, H.Enc, H.Dec, H.Eval. Let A, B be two parties.

1. A generates (pk, sk) ← H and publishes pk.

2. For i from 1 to t, B asks A to decrypt a ciphertext ψ i , and A answers H.Dec(sk, ψ i ). This step can be repeated after the challenge, with new ciphertexts not matching the challenge ciphertext.

3. (Challenge) B generate two sets of plaintexts (π 0i ) k i=1 , (π 1i ) k i=1 ∈ P k and an allowed circuit C and sens them to A, who chooses b ∈ R {0, 1}, computes

ψ * R ← -H.Eval(pk, C, (ψ bi ) k i=1 )
where ψ bi = Enc(pk, π bi ) and sends ψ * to B. It is not difficult to show with an hybrid argument that an algorithm breaking the (homomorphic) semantic security with advantage ε can be used to break the (classical) semantic security with advantage ε/k. The hybrid argument "travels" through the gates of the chosen circuit and estimates the advantage. Therefore, to prove the semantic security of an homomorphic scheme, it suffices to prove the semantic security in the classical sense.

The bootstrapping procedure and other techniques

In all known homomorphic schemes, the encryption procedure adds random noise to plaintexts. If the norm of this noise is beyond a certain threshold, the resulting ciphertext does not decrypt to the expected underlying plaintext. In addition, every homomorphic evaluation results in a growth of the corresponding noise. This limits the maximum depth achieved for correct evaluation of circuits at parameter setting time, and hence something must be done to achieve true FHE. Gentry achieves this with his most groundbreaking idea: If an homomorphic scheme E can homomorphically evaluate its own decryption circuit D E , one can use E to construct other schemes capable of homomorphically evaluate any circuit of fixed depth, i.e.to construct a family of levelled FHE schemes. Thereafter, this achieves a theoretical construction of an FHE scheme.

Definition 1.7.1 (Bootstrappable scheme). Let E be an homomorphic encryption scheme with compact evaluation of circuits in C, and let D be its decryption circuit. We say that E is bootstrappable if D ∈ C E . This self-reference property permits to implement an algorithm that can "update" or "clean" noisy ciphertexts, the price being a change of keys. In effect, let π be a plaintext and suppose that a ciphertext ψ encrypting π is the output of an homomorphic circuit of high depth allowed by the scheme. The ciphertext can be used in homomorphic computations, but not for long, since adding too much gates would trespass the maximum allowed depth. Is it possible to obtain another ciphertext ψ � that also encrypts π and such that it is useful for more homomorphic operations than ψ? In general, it is straightforward to construct other ciphertexts encrypting the same thing because of malleability -just "add" encryptions of 0 or "multiply" encryptions of 1. Gentry's idea is far more deep: encrypt ψ with another public key (obtaining two layers of encryption) and homomorphically run the decryption circuit over this message and encryptions of the first key. The result is a new encryption of π under a new key. 1: Set ψ 2 ← Enc(pk � , ψ)

2: Set ψ � ← Eval(pk � , D E , τ, ψ 2 ). 3: Output ψ � .

Circular security

The bootstrapping procedure uses public encryptions of secret-keys. Addressing this, in [START_REF] Brakerski | Fully Homomorphic Encryption from ring-LWE and Security for Key-Dependent Messages[END_REF] Brakerski and Vaikuntanathan proposed the first homomorphic encryption scheme proven to be Key-Dependent Message secure, and in particular, circular secure.

Hard problems used in FHE

As any other encryption scheme, FHE schemes need supposedly (or proven) hard underlying problems. They enjoy many of them, mostly coming from lattice-based cryptography. We list and define these problems here. For the sake of completeness, let us define a lattice. More details are given in 3.2.2 of Chapter 2.

A lattice L of R n is a discrete subgroup of (R n , +) which spans R m as a R-vector space. The integer m is called the dimension of L. A lattice may be described in terms of a linearly independent set B ⊂ L ⊂ R n , which Z-spans L and R-spans R n . The set B is called a basis of L. All bases of L have cardinality m, and if m = n we say that L is a full-rank lattice.

Let B(r) denote the closed R n -ball centered at 0 of radius r with respect to the Euclidean norm ||x|| 2 := � � n i=1 x 2 i . For a lattice L of dimension m, define the sequence of successive minima as λ 1 (L) = min v∈L\{0} ||v|| 2 and for i = 2, . . . , m,

λ i (L) = min v∈L\B(λ i-1 (L)) ||v|| 2 .
All of the following problems are lattice-based.

Problem Problem 1.8.7 (LWE). Let q be an integer and χ be an error distribution on Z. Let s ← Z n q be a secret vector, and define A q,χ as the distribution that first sets a R ← -Z n q , e ← χ and then outputs (a, a • s + e). The Learning With Errors Problem is to deduce s given polynomially many samples of A q,χ . Its decision variant (called Decision-LWE) consists in distinguishing m samples of A q,χ from uniformly random samples of Z n q × Z q .

Problem 1.8.8 (RLWE). The Ring-LWE Problem is the analog of LWE but replacing Z n q with the polynomial ring R q = Z q [x]/(f (x)) where f is a monic n-th degree polynomial. Typically, f (x) = x n + 1 and n is a power of 2 (therefore, f is the 2n-th cyclotomic polynomial)

The following are two integer-based problems. The first was used in the construction of FHE over the integers, while the second is a combinatorial problem needed to "squash" the decryption circuit of Gentry's ideal lattice scheme, in order to make it bootstrappable.

Problem 1.8.9 (AGCD). The Approximate Greatest Common Divisor Problem is to find a secret number p given a list of m integers of the form x i = q i p + r i for integers q i , r i sampled from possibly different distributions over Z.

Problem 1.8.10 (SSSP). The Sparse Subset Sum Problem consists in deciding whether a set of integers contains a small subset such that the sum of its elements equals 0 in Z q . More precisely, given a set A of t integers, the SSSP asks to decide if there is a subset A � ⊂ A of cardinality at most s � t such that � a∈A � a ≡ 0 mod q.

Finally, we describe polynomial ring problems. For a distribution ξ over a ring R, let ξ × be the distribution that samples repeatedly from ξ until the output is invertible.

Problem 1.8.11 (DSPR φ,q,ξ ). Let φ be a monic polynomial of degree n, q ∈ Z a prime and ξ a distribution over the ring R q = Z q [x]/(φ(x)). The Decisional Small Polynomial Ratio problem is to distinguish between (i) a polynomial h of the form h = g/f where g ← ξ and f ← ξ × , and (ii) a polynomial h � sampled uniformly at random from R q .

We propose in [START_REF] Goubin | Blending FHE-NTRU Keys -The Excalibur Property[END_REF] two new factorization problems in cyclotomic rings, that support the security in our solution to the betrayal problem. We call these problems the Special Factors Problem and the ξ × -Common Divisor Problem.

Problem 1.8.12 (SFP). Let ξ be a distribution on some ring R. Remark. In Chapter 4 and in [START_REF] Goubin | Blending FHE-NTRU Keys -The Excalibur Property[END_REF], these two problems are called the "Small Factors Problem" and the "invertible Gaussian GCD Problem". This is because the specialness of polynomials a, b in our cyclotomic ring scenario is that they have small l 2 norm.

Conclusion

In this Chapter, we approached the area of fully homomorphic encryption. We highlighted some practical applications, relations to other cryptographic properties, and described how different generations of proposals are ordered today in five branches. Also, we defined fully homomorphic encryption from the theoretical point of view and discussed some computational problems that lay in the foundations of these constructions. We believe that this review is of help to FHE-neophyte readers; to more informed readers wishing to follow the vast FHE literature in a certain angle (efficiency, applications, security, etc), please refer to appendix A, where we cite important references in a list arrangeable by different criteria.

Introduction

In this Chapter, we revisit Gentry's ideal lattice homomorphic scheme. It has been widely mentioned that this scheme, while achieving fully homomorphic encryption for the first time, is not even remotely competitive with contemporary encryption schemes regarding efficiency. The main bottleneck is ciphertext and public-key size, which grows exponentially with the level of security. Nonetheless, understanding the scheme's construction is very rewarding and we firmly believe that it deserves study, at least with similar deepness than later homomorphic schemes. New cryptographic ideas and mathematical birds live here, and it would be a pity to pass them by because the scheme does not meet our prompt needs.

Our objective is to present the scheme in a sufficient level of detail, as a tribute to Gentry's original Ph.D. dissertation. The first idea leading to the solution is remarkably simple: it reduces the so-called Holy Grail of Cryptography quest to the problem of finding an algebraic ring with some class of ideals that support hard problems for security and specific operations. Of course, it would be terribly unfair to state that Gentry's contribution relied on finding a proper ring for a generic construction. But still, his solution can be understood with the following image.

Ideal + lattices = Ideal Lattices. A cryptographer C with infinite amounts of intelligence and ignorance is asked to solve the fully homomorphic encryption problem. To solve this, he would most likely invent algebra, take a ring R and define the following encryption scheme:

Let I be some ideal of R, let m ∈ R/I an encoding of a message, and define ciphertext Enc(m) = m + i where i ∈ I. This is indeed homomorphic, since if ⊕, ⊗ denote both ring operations,

Enc(m) ⊕ Enc(m � ) encrypts m ⊕ m � , Enc(m) ⊗ Enc(m � ) encrypts m ⊗ m � .
He would then search for a ring R that enjoys

• random efficient sampling of α + I for α ∈ R/I to encrypt 1 , • an "ideal annihilation" procedure m + xI � → m to decrypt,
• connection to hard problems.

If in addition C met another cryptographer C � with unbounded knowledge of recent research, he would be inclined to believe that the answer may be found in lattice-based cryptography. This was, in fact, the solution to the FHE problem: use polynomial rings and specialize the latter basic construction using two sets of ideal lattices.

A study on some natural densities. Sampling random coprime lattices has some subtleties. We collect some results and quantify the structure of random bases in Hermite Normal Forms, which represent special bases for lattices.

Overview of this Chapter. In section 2.2, we define ideal lattices. In 2.3 we reconstruct Gentry's basic somewhat homomorphic scheme, which supports a bounded amount of homomorphic operations. A discussion of the underlying security follows in section 2.4, and a proof-of-concept implementation is presented in 2.6. We finish with the study of natural densities of some lattice bases in 2.5.

Preliminaries

: Ideal lattices 2.2.1 Lattices Definition 2.2.1 (Lattice). A lattice in R n is a discrete subgroup of (R n , +) which spans R m as a R-vector space.
Every lattice L has a minimal subset of m elements B ⊂ L such that L = � b∈B Zb. When n ≥ 2 there is an infinite number of such sets and we call them bases of L. The integer m does not depend on the chosen basis and is called the rank of L, therefore, to describe a lattice, only one basis is required.

b 1 b 2 3b 1 + 5b 2 5b 1 + 8b 2
P (B) =    � 1≤i≤m x i b i ∈ R n ; x i ∈ [-1/2, 1/2)   
By definition, the volume of P (B) equals the determinant of the lattice:

det(L) = R n -measure(P (B)) for all basis B.
Let L be a full rank lattice. If x ∈ R n , we note by x mod L the equivalence class of x in the quotient group R n /L. We use the fundamental parallelepiped P (B) as the set of representatives of the equivalence classes when describing L with the basis B. Therefore, it is natural to note by x mod B the single element in the intersection (x mod L) ∩ P (B). To reduce a vector x ∈ R n modulo B, use Z-linear combinations of vectors in B to find the equivalent vector inside P (B). In other words,

Lemma 2.2.1. Let x ∈ R n and B a basis of a full-rank lattice L. Then x mod B = x -B�B -1 x�, where �v� := (�v 1 �, �v 2 �, • • • , �v n �) is the closest Z n vector to v.
Proof : The invertibility of B comes from the fact that det L � = 0. We have

x -B�B -1 x� = B(B -1 x -�B -1 x�) = By, where y = B -1 x -�B -1 x� is a R n -vector with coordinates in [-1/2, 1/2). �
In the scheme, two coprime lattices I, J will define the plaintext and ciphertext space respectively. Definition 2.2.2 (Relatively prime lattices). Two lattices L, L � of Z n are relatively prime (or coprime) if their sum is Z n . We note this (L, L � ) = 1. Keys in Gentry's scheme are lattice bases, which we identify with square matrices. The private-key is a "good" basis in the orthogonality defect sense and the public key is an eccentric, large basis of the same lattice. More precisely, this large basis is the Hermite Normal Form of the lattice.

Definition 2.2.3 (Hermite Normal Form

). A square matrix H ∈ M n×n (Z) of en- tries h ij is in Hermite Normal Form if 1.
H is lower triangular, semi-positive definite: h kk ≥ 0 and h ij = 0 for i < j.

2. The pivot (first nonzero entry) of a column is strictly below the pivots of precedent columns.

3. Entries to the right of pivots are zero and elements to the left of pivots are nonnegative, strictly smaller than the pivot.

x mod B b 1 b 2 Figure 2.2: A basis modular reduction in R 2
For instance, the following matrices are in HNF.

    
17 0 0 0 2 3 0 0 50 0 51 0 6 6 6 7

     ,          
12 0 0 0 0 0 -1 0 0 0 0 0 10 13 0 0 0 0 1 2 4 0 0 0 78 -26 10 0 0 0 13 13 1 14 0 0

          .
A lattice is uniquely defined by a matrix in HNF, and according to this we will define the HNF of a lattice as its unique basis in HNF. This allows us in section 2.3.5 to provide a characterization of coprime lattices.

Notation

In this Chapter, all lattices are of full rank (m = n) unless stated otherwise. In addition, if

B = {b 1 , • • • , b n } ⊂ L
is a basis of the lattice L, we will not distinguish between B and the matrix

B = (b 1 |b 2 | • • • |b n ).
We note by I n the n × n identity matrix and e k the k-th column of I n .

Ideal lattices

Let G be an additive group and α : G → (R n , +) a group homomorphism, then α(G) is a lattice. This happens because α transports the additive structure of G to points in R n in order to generate linear integer combinations of them. Of course, this can also be performed with rings, considering the additive operation, and it proves to be fruitful as it allows to define R n -products (if α is suitable) and ideal lattices.

Definition 2.2.4 (Ideal lattice).

Let A be a ring and α : A → R n and additive ring homomorphism. An ideal lattice of R n is a lattice of the form α(I) for a principal ideal I ⊂ A.

Remark. A definition with non-principal ideals seems worthy of attention. However we will not address this, since in polynomial quotient rings the non-principal case can be regarded as a linear algebra problem considering reduction of union of basis coming precisely from principal ideals.

Polynomial principal ideal lattices

Consider the ring R = Z[x]/(f (x))
where f is a monic polynomial of degree n, and the natural homomorphism α : R → Z n given by

α : a(x) = a 0 + a 1 x + • • • + a n-1 x n-1 � → a = (a 0 , . . . , a n-1 ).
We can now define a precise ideal lattice: if I = (v) is a principal ideal of R, then α(I) is a lattice of R n with a remarkable basis:

Lemma 2.2.2. Let v ∈ R, I = (v) and v i = v × X i mod f (X) for i = 1, . . . , n -1.
Then a basis of the ideal lattice α(I) is given by a linearly independent subset of

rot(v) := {v, v 1 , v 2 , • • • , v n-1 }. Proof : If w ∈ (v), then w = v × a = v × � � n-1 i=0 a i X i � for some a ∈ A. Hence α(w) = � n-1 i=0 a i v i ∈ rot(v). Conversely, if (the vector) w ∈ rot(v), then w = � n-1 i=0 a i α(v i ) = α(P ) for P = � n-1 i=0 a i v i . �
Remark. The ideal lattice α(I) may not be of full rank (hence the "given by a linearly independent set of" statement). For instance

, if R = Z[x]/(x n -1) then the ideal lattice α((1 +x+x 2 +• • •+x n-1
)) is of rank 1. This happens because the polynomial 1

+ x + x 2 + • • • + x n-1 is not invertible in R.
We do not worry much about this, and we will deal only with full-rank lattices, thanks to the choice of the polynomial ring and the ideal generator.

From now on, we will not distinguish between the polynomial w ∈ R and the corresponding vector α(w) ∈ Z n . Sometimes, we will not distinguish between a polynomial ideal (v) and the corresponding ideal lattice α((v)).

Definition 2.2.5 (Rotation basis). The set {v

i = v × x i mod f (x); i = 0, . . . , n -1} is called the rotation basis of (v). The matrix rot(v) = (v|v 1 | . . . |v n-1 ) is called the rotation matrix of v. Proposition 2.2.3 (Inversing rotation matrices). Let v ∈ R × . Then rot(v) × rot(v -1 ) = I n . Proof: It follows directly from the fact that for every a, b ∈ Z n , a×b = rot(a)b = rot(b)a. �. Example 2.2.1. If n = 4 and R = Z[x]/(x 4 + 2), the ideal lattice α((v)) where v(x) = 1 + x 2 = (1, 0, 1, 0) is generated by v(x) mod f (X) = 1 + x 2 = (1, 0, 1, 0), xv(x) mod f (X) = x + x 3 = (0, 1, 0, 1), x 2 v(x) mod f (X) = -2 + x 2 = (-2, 0, 1, 0), x 3 v(x) mod f (X) = -2x + x 3 = (0, -2, 0, 1),
i.e. by the columns of the matrix

rot(1 + x 2 ) =      1 0 -2 0 0 1 0 -2 1 0 1 0 0 1 0 1      .
This matrix is invertible, and therefore the corresponding ideal lattice is of full-rank, with det(rot(1 + x 2 )) = 9. Let us give another example which we will find very often in fully homomorphic encryption schemes, in various forms.

Example 2.2.2. If f (x) = x n -1, the rotation of a polynome a(x) � → xa(x) mod f corresponds to a coefficient-wise rotation of α(a): (a 0 , . . . , a n-2 , a n-1 ) � → (a n-1 , a 0 , . . . , a n-2 ), therefore the ideal lattice (a) is generated by the columns of the circulant matrix rot(a 0 , . . . , a n-1 ) =         a 0 a n-1 a n-2 • • • a 1 a 1 a 0 a n-1 a 2 a 2 a 1 a 0 a 3 . . . . . . . . . a n-1 a n-2 a n-3 • • • a 0         .
Lattices generated by circulant bases (or equivalently, ideal lattices of the ring Z[x]/(x n -1)) are called cyclic lattices. They verify the following property: if (a 1 , a 2 , . . . , a n ) ∈ L then (a 2 , a 3 , . . . , a n , a 1 ) ∈ L. Notice also that all of these lattices contain vectors in the lines spanned by (1, 1, 1, . . . , 1) and (1, -1, 1, . . . , ±1).

Ring operations in Z n

Given that we identified

Z n � R = Z[x]/(f (x))
, ring operations are inherited by structure transport. This way, for all v, w ∈ Z n we define

addition v + w := α(v(x) + w(x)), product v × w := α(v(x) × w(x))
Of course, the first operation is usual addition in Z n and the second operation is a convolution product in Z n . A third operation was already discussed, that allows to reduce a vector in R n modulo a basis B of a lattice L. We are now ready to define the scheme.

The basic homomorphic scheme

The scenario of this scheme is as follows -We fix a dimension n ≥ 2 and a monic polynomial f of degree n,

-let R = Z[x]/(f (x)),
-let I be an ideal lattice with a base B I , -let J be an ideal lattice relatively prime to I (i.e. I + J = Z n ), with two bases B sk J , B pk J , and finally -choose an algorithm Samp : Z n /(I) → Z n that given a vector x, samples randomly from x + (I).

The plaintext space in the scheme is Z n ∩P (B I ) (a small, quite orthogonal parallelepiped) and ciphertext space is Z n ∩P (B pk J ) (a huge, very eccentric parallelepiped). The elements n, f, I, J, B I are all public, and the keys are

pk = {B pk J }, sk = {B sk J }.
The successive choices of f, I, B sk J , B pk are essential and non-trivial to understand and eventually implement the scheme. Let us give a second look at these elements in secure scenarios:

-n is large to prevent lattice reduction attacks (n ≥ 2 9 avoids LLL and BKZ reduction, for instance), -f is of the form X n + h(X) where deg(h) is small (for instance h(X) = -1), in order to control product norms, -the parallelepiped B I consists of small vectors (the binary case is I = (2) and

B I = 2I n ),
-B sk J is quite orthogonal, with large volume and P (B sk J ) contains P (B I ),

-B pk J is on the contrary, very eccentric (it is defined by large and almost parallel vectors), -the algorithm Samp : P → Z n randomly chooses a representative of x + I inside a ball of fixed radius l Samp contained in P (B sk J ).

The scheme is described in 6.

Algorithm 2 Gentry's homomorphic ideal lattice scheme

1: function Keygen(λ) 2:
Generate B sk J and B pk J randomly from a security parameter.

3: end function --- 4: function Enc(pk,π ∈ P (B I )) 5:
To encrypt message π, compute ψ ← Samp(π) mod B pk J and output ψ. It is an integer vector of the form π + i + j where i ∈ I, j ∈ J, and it is inside P (B pk J ). 6: end function ---7: function Dec(sk,ψ)

8:

To decrypt ψ, compute

µ = (ψ mod B sk J ) mod B I = (ψ -B sk J �(B sk J ) -1 ψ�) mod B I and output µ. 9: end function --- 10: function Eval((pk,C,ψ 1 , • • • , ψ t ) 11:
Perform the circuit C on inputs ψ 1 , • • • , ψ t replacing each "+" and "×" gate of C by addition and multiplication modulo B pk J respectively. Output the result. 12: end function

Does it work? Why does it work?

Before looking at correctness of the algorithms, we will have a glance at what happens when a plaintext is encrypted, then decrypted. Suppose I = α((2)). Let π be a plaintext (π is a binary vector). The first step of encryption is to define π � ← Samp(π). Thus, π � = π + i for i ∈ I (a binary vector plus multiples of 2 component wise), in clear, π � = π mod I. The next step is to reduce π � mod B pk J . This will map π � to a point ψ = π � + j for j ∈ J. As the generating vectors in B pk J are long and almost parallel, it is more than likely that this point ψ will be very far along the direction e n and outside P (B sk J ): this is the ciphertext. To decrypt, the first step is to recover π � from ψ. As ψ = π � mod J, the reduction ψ mod B sk J will output π � if and only if π � ∈ P (B sk J ).

This is ensured by

Samp(P (B I )) ⊂ P (B J ) sk .
Then, recovering π is easy. This is why the sampling procedure outputs must be l 2bounded by a constant l Samp . What about homomorphic operations of ciphertexts? Will they decrypt correctly? Let ψ 1 = Enc(pk, π 1 ), ψ 2 = Enc(pk, π 2 ). Then

ψ 1 + ψ 2 = (π 1 + π 2 ) + i � + j � for some i � ∈ I, j � ∈ J, (2.1)
ψ 1 × ψ 2 = (π 1 × π 2 ) + i �� + j �� for some i �� ∈ I, j �� ∈ J, (2.2)
i.e. they will decrypt to

π 1 + π 2 and π 1 × π 2 respectively if and only if (π 1 + π 2 ) + i � ∈ P (B J ) sk and (π 1 × π 2 ) + i �� ∈ P (B J ) sk .
As P (B J ) sk is bounded in R n , it is not possible to carry out an arbitrary number of correct homomorphic operations, since at some point the latter vectors will get out of P (B J ) sk , ruining decryption. This also means that the growth of the Z n operations will directly affect the number of homomorphic operations that can be correctly performed. In the next section, we will describe kind choices to this end, that look out to security as well.

Key generation and correctness of the algorithms

We will explain how to choose parameters and generate keys to ensure correctness of the scheme and its homomorphic operations.

Choice of the polynomial ring

The choice R = Z[x]/(f (x)) has consequences in the overhead of operations in Z n . For instance, if f has lots of monomials, the product of two polynomials a, b ⊂ R is likely to have larger l 2 norm than when using a sparse polynomial f , since the reduction modulo f involves more euclidean divisions. For monic polynomials of degree n, let us define the product overhead

λ(f ) := max u,v∈Z[x]/(f (x)) ||u × v|| 2 ||u|| 2 ||v|| 2 .
A good choice of ring involves a polynomial with small product overhead. The reader may consult [START_REF] Gentry | A Fully Homomorphic Encryption Scheme[END_REF], § 7.4 for more details. We highlight the fact that if f is of the form f

(x) = x n -h(x) for a polynomial of degree ≤ n/2, then λ(f ) ≤ c √ n
for some constant c depending on f . For instance,

λ(x n ± 1) = √ n.
For completeness, let us prove this.

Lemma 2.3.1. Let R = Z[x]/(x n -1). If a × b = z = (z 0 , • • • , z n-1 ) ∈ R, then z k = n-1 � j=0 a k-j mod n b j and ||z|| 2 ≤ √ n ||a|| • ||b||.
Proof : Given that X n+k ≡ X k mod (X n -1) (the following are equations in the ring),

n-1 � i,j=0 a i b j X j+i =   n-1 � j=0 n-j-1 � i=0 + n-1 � j=0 n-1 � i=n-j   a j b i-j X i+j = n-1 � i=0 i � j=0 a j b i-j X i + n-1 � i=0 n � j=i+1 a j b n+i-j X i = n-1 � i=0 X i   n-1 � j=0 a j b i-j mod n   .
In consequence, z i , the coefficient of X i in z, is the scalar product between a and rotations of b. The result is given as an application of Cauchy-Schwartz inequality. �

As an easy corollary, we have that if f (X) = X nm for m ∈ Z, then

z k = k � j=0 a k-j b j + m � j=k+1 a n+k-j b j and ||z|| ≤ C(m) ||a|| • ||b|| for some constant C(m) such that √ n ≤ C(m) ≤ � n|m|. As noted in section 3.2.3, for R = Z[x]/(x n -1) the ideal lattices are cyclic (or circulant): if (a 1 , • • • , a n ) ∈ L, then (a n , a 1 , • • • , a n-1 ) ∈ L.
This choice is elegant and allows to apply the very developed theory of circulant matrices, see for instance [START_REF] Gray | Toeplitz and Circulant Matrices: A Review[END_REF]. In this chapter, we will fix f (x) = x n -1.

Lattice I: choice of the plaintext space

In Gentry's scheme, the message space is (a subset of)

P = Z n mod B I = Z n ∩ P (B I ),
where B I is a matrix whose columns Z-span I. Here are four examples in

Z 3 .    2 0 0 0 2 0 0 0 2    ,    d 1 0 0 0 d 2 0 0 0 d 3    ,    t 11 t 12 t 13 0 t 22 t 23 0 0 t 33    ,    r 1 r 3 r 2 r 2 r 1 r 3 r 3 r 2 r 1    .
In the first case, plaintext space P is {0, 1} 3 . In the second and third case, a message is a vector (x 1 , x 2 , x 3 ) whose components verify

|x i | < |d i | for i = 1, 2,

Lattice J: ciphertext space

The lattice J must be chosen relatively prime to I and have two bases -a small, quite orthogonal B sk J and a large, eccentric B pk J . Let us begin by giving following characterization of relatively prime lattices: Proposition 2.3.2. Let L, L � be two lattices of Z n and B, B � their respective bases.

Recall that e i is the i-th column of the identity I n . The following statements are equivalent:

(i) L + L � = Z n .
(ii) (Bézout's identity for lattices) There are two matrices M, M � with integer entries such that BM + B � M � = I n .

(iii) Let H and H � be the Hermite normal forms of B and B � respectively. The respective diagonal elements of H, H � are relatively prime.

Proof : The equivalence (i)⇔(ii) comes from the fact that if L, L � are relatively prime, then one can write each column of the identity matrix as a linear integer combination of elements in B ∪ B � , thus generating Z n . The equivalence (i)⇔(iii) is simply the fact that H, H � are bases of L, L � in triangular form. Indeed, suppose that (i) holds, then for 1 ≤ k ≤ n, e k is a linear integer combination of columns of (H|H � ), and because of the triangular structure this combination is of the form

e k = k � i=1 α i h i + β i h � i .
In particular, 1 = α k H kk + β k H � kk , proving (iii). Conversely, if (iii) holds, one can perform column operations to the rectangular matrix (H|H � ) following Bézout's identity between corresponding columns, resulting in a rectangular matrix with 1's in the diagonal, consequently, its columns generate Z n . �

Corollary. Let L, L � be two lattices in Z n . If (det(L), det(L � )) = 1 then (L, L � ) = 1.
Remark. The converse is not true. For instance, the lattices of Z 2 generated by {2e 1 , 3e 2 } and {3e 1 , 2e 2 } are relatively prime but they have equal determinants.

Let us come back at our choice of a binary plaintext I = (2). Is it easy to find an ideal lattice J = α((v)) relatively prime to I, i.e. such that det J is odd? A probability result states that the distribution of determinants of uniformly random matrices is not uniformly distributed in Z (this distribution is an interesting problem, see [START_REF] Cicuta | Probability density of determinants of random matrices[END_REF]). In fact, the Hermite normal form of a uniformly random matrix follows a structured distribution. Asymptotically (in a bound on entry-wise uniform samplings), for a matrix M there are around 40% chances that the first n -1 diagonal elements of the HNF(M ) are 1 and the last equals | det(M )|. We quantify this distribution in section 2.5. We also compute the natural density of matrices in M n×n (Z) with odd determinant, which answer the former question. Let δ n denote this density, then we show in 2.5 that

δ n = |SL n (F 2 )| 2 n 2 = n � i=1 � 1 - 1 2 i � ,
i.e. this density is between lim n→∞ δ n ≈ 0.28 and δ 2 ≈ 0.38.

Generating the bases

We address now the "shape" of bases B sk J , B pk J and the method to generate them. Because of how decryption works, P (B sk J ) must contain a large R n -ball, which in turn must contain the set Samp(P). Indeed, if a message x ∈ P = {0, 1} n is such that Samp(x) � ∈ P (B sk J ), then Dec(sk, Enc(pk, x)) � = x. On the contrary, the "public" base B pk J must be large and eccentric, imitating the shape of a very long segment in R n , to ensure that the encryption Samp(x) mod B pk J is very far away (and in particular, different modulo B I ) from Samp(x).

We already assumed that n is large so no lattice reduction is available (in order to generate the quite orthogonal B sk J ). Instead, one can simply generate this matrix using the rotation basis of a suitable polynomial. In point of fact, choose a secret vector v sk of large l 2 norm and next to the direction e 1 = (1, 0, • • • , 0) (or any other axis) and set J = α((v sk )), B sk J = rot(v sk ). To generate the public key, just compute the Hermite normal form of B sk J . As a minor detail, note that if

v sk = (v 1 , . . . , v n ) ∈ Z n , then both s = v 1 +• • •+v n and d = -v 1 + v 2 -v 3 -. . . (-1) n v n divide det(rot(v sk )) (s
B sk J ← 0 3: while (det(B sk J ) = 0 mod 2) do 4:
Sample v sk ← Z n such that v sk is close to a R n axis and ||v sk || 2 � l Samp 5:

Set B sk J = rot(v sk ) 6:
end while 7:

B pk J = HNF(B sk J ) 8:
Output (B sk J , B pk J ) 9: end function Example 2.3.1. Let n = 7 and sample v sk = (18, -3, 0, 0, 1, 0, -1) (or the polynomial 18 -3X + X 4 -X 6 ) which is close to the direction e 1 (notice also that s = 15 and d = 21 are odd). The key generation algorithm outputs

B sk J = rot(v sk ) =            18 -1 0 1 0 0 -3 -3 18 -1 0 1 0 0 0 -3 18 -1 0 1 0 0 0 -3 18 -1 0 1 1 0 0 -3 18 -1 0 0 1 0 0 -3 18 -1 -1 0 1 0 0 -3 18            , B pk J =            1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 516180659 338284094 98416679 286516904 328581644 458971154 573665415            .
Now, det J = 573665415 is odd, therefore (I, J) = 1 (we also have the minor details (18 -3 + 1 -1)|573665415 and (-18 -3 -1 + 1)|573665415). Notice how the entries of the last column of B pk J are large in comparison to the secret vector.

Role of the representative sampling function

To encrypt a message π ∈ {0, 1} n , one computes Enc(π) = Samp(π) mod B pk J , where Samp is a randomized procedure that chooses a representative of the class π + I. In the absence of this sampling, the scheme would be deterministic. A huge comeback, since it would allow to solve equations on ciphertexts. Indeed, suppose that the encrypting equation was simply Enc(π) = π mod B pk J , then we have Enc(pk, x) = x for every x ∈ {0, 1} n ∩ P (B pk J ) (for instance x ∈ {0, e n }). Therefore, the role of this function is to randomize encryption and separate the message from the eccentric parallelepiped P (B pk J ) while keeping the parity of the coordinates, in order that mod B pk J reduction outputs a very far away point of Z n and, above all, not equivalent to π modulo 2 (i.e. modulo B I ).

In fact, we have {0, 1} n ∩ P (B pk J ) = {0, e n }, it hence suffices to take Samp as a distribution that outputs randomly a representative of π + (I) in a ball of radius l Samp . Gentry proposes l Samp = n.

Correctness of encryption and decryption

The size of the private key ||v sk || 2 and radius of the sampling l Samp must be chosen to ensure correctness of decryptions.

Proposition 2.3.3. Let (sk, pk) ← Keygen(λ). If P (B sk J ) ⊃ Samp({0, 1} n ), then Dec(sk, Enc(pk, x)) = x for all x ∈ {0, 1} n .
Proof: Let x ∈ {0, 1} n and suppose that the representative x + i = Samp(x) lays in the interior of P (B sk J ). To encrypt, one performs

x Samp ---→ x + i mod B pk J ------→ x + i + j = y ∈ P (B pk J ),
where i ∈ R I, j ∈ R J. Decryption gives

y mod B sk J -----→ y -j � mod B I -----→ y -j � -i � ,
where i � ∈ I, j � ∈ J. The reduction y mod B sk J outputs the only representative of y in P (B sk J ), and by hypothesis x + i is inside P (B sk J ), thus yj � = x + i and j = j � . Also yj � mod B I = x + i mod B I = x. � On the contrary, if x + i � ∈ P (B sk J ), the reduction y mod B sk J outputs a point z ∈ Z n that does not match x + i since z ∈ P (B sk J ), ruining decryption.

Example 2.3.2. In the example 2.3.1 above, the sampling radius must not exceed ||v sk ||/2 ≈ 9.15. As a matter of fact, our choice of v sk ensures correctness of decryptions since 9.15 > 7 = n, i.e. P (B sk J ) ⊃ Samp({0, 1} n ) (however, as we will see in the next section, this choice does not allow homomorphic operations). Let us encrypt the message π = (1, 1, 0, 1, 0, 0, 1) under the public key of example 2.3.1. We first sample a representative of π + I contained within a ball of radius 7 centered at 0: -2, 1) (notice that parity is respected and the point is not close to the stable direction e 7 ). We then compute the representative of this vector within P (B sk J ) and output Enc(pk, (1, 1, 0, 1, 0, 0, 1)) = (0, 0, 0, 0, 0, 0, -107133622) = ψ.

Samp(π) = (1, -1, 4, 1, 4,
To decrypt this message, first compute (0, 0, 0, 0, 0, 0, -107133622) mod

B sk J = (1, -1, 4, 1, 4, -2, 1)
and output this point modulo 2. We find the message x = (1, 1, 0, 1, 0, 0, 1).

Correctness of homomorphic operations

As we discuss here, in order to securely evaluate circuits of high depth, the size of public keys and ciphertexts must be very large. This is a major drawback of the scheme. Let (pk, sk) ← Keygen, x, x � be two messages in {0, 1} n and let i, i � ∈ I, j, j � ∈ J such that Enc(pk, x) = x + i + j, Enc(pk, x � ) = x � + i � + j � . To verify correctness of homomorphic addition, the vector s ∈ Z n given by s = Enc(pk, x) + Enc(pk, x � ) must be a valid ciphertext and correctly decryptable in the sense of section 2.3.8. In clear,

s = (x + x � ) + (i + i � ) + (j + j � ),
and with the same reasoning as before, the image of s under Dec(sk, •)

will not output x + x � mod 2 if (x + x � ) + (i + i � ) lies outside P (B sk J ). Given that ||(x + x � ) + (i + i � )|| ≤ 2l Samp , homomorphic addition is correct if l Samp < ||v sk ||/4
, where v sk is an edge of B sk J . In general, to ensure correctness of k fan-in homomorphic addition

Dec(sk, Enc(pk, x 1 ) + • • • + Enc(pk, x k )) = x 1 + • • • + x k mod 2 for all tuple of vectors x 1 , • • • , x k in {0, 1} n , the condition is l Samp < ||v sk || 2k .
In our example 2.3.1, not even an homomorphic addition can be supported since n = 7 � < 1 4 ||v sk || ≈ 4.58. More precisely, for the secret key v sk = (18, -3, 0, 0, 1, 0, -1), one homomorphic addition can be carried out if Samp outputs vectors within a ball of radius 4.

Of course, to support homomorphic multiplication of two ciphertexts, the inequality between ||v sk || and l Samp is far more restrictive. Consider the same scenario as before and p = Enc(pk, x) × Enc(pk, x � ), i.e. ,

p = (x + i) × (x � + i � ) + j(x � + i � ) + j � (x + i) ∈ Z n .
For correct decryption, the point (x + i) × (x � + i � ) must lie within the secret parallelepiped. Applying the product overhead inequality

||a × b|| ≤ √ n||a|| × ||b|| for all a, b in Z n , this is verified if 2 √ n(l Samp ) 2 < ||v sk ||. To perform a k-fan-in multiplication gate, one needs 2n k-1 2 (l Samp ) k < ||v sk ||.
In our 7-th dimensional example with l Samp = n, this is ||v sk || > 260, meaning that to support a single multiplication, the entries in the last row of a public key base are 56-bit integers. For n = 334 (preventing current lattice reductions in the average case), supporting a single multiplication needs a public base of vectors with 7335-bit integers. 40 2.4. Security

Maximum depth of allowed circuits

With the previous reasoning we quantify the maximum depth for correct evaluation. As we will see, an increase in the maximum depth needs a drastic growth of key sizes.

Theorem 2.3.4. Let v sk be a secret key vector (i.e. B sk J = rot(v sk )). The maximum depth that can be correctly homomorphically evaluated is

d max = log 2 log 2 (||v sk ||) -log 2 log 2 ( √ nl Samp ),
with at most √ n addition fan-in and 2 product fan-in.

Proof: Let r i ≥ 1 be a superior bound to the l 2 norm of outputs on level i of the circuit C. Suppose that C is of depth d max and set r 0 = l Samp . At level i -1 for i ≥ 1,

• ||v 1 + • • • + v � √ n� || ≤ √ n • r i , • ||u × v|| ≤ √ n ||u|| • ||v|| ≤ √ n • r 2 i .
Therefore the output of gates at level i can be bounded by

√ n • r 2 i . Therefore r i-1 ≤ √ n • r 2 i and r 0 ≤ √ nr 2 1 ≤ √ n 1+2 r 2 2 ≤ • • • ≤ √ n 1+2+•••+2 k-1 r 2 k k = √ n 2 k -1 r 2 k k ≤ ( √ nr k ) 2 k .
For the evaluation to be correct al level d max we must have r dmax ≤ ||v sk || 2 i.e.

l Samp ≤ ( √ n||v sk || 2 ) 2 dmax . �
Said otherwise, the secret key size ||v sk || 2 is super-exponential in the maximum depth.

Security

The Ideal Coset Problem

Gentry's scheme semantic security is based on the Ideal Coset Problem (ICP). It is the problem of distinguishing between a valid encryption and a random vector in the eccentric parallelepiped P (B pk J ).

Definition 2.4.1 (ICP). Let R = Z[x]/(f (x))
for a monic polynomial f of degree n, and let I, J be relatively prime ideal lattices. Let Samp be an algorithm that, on input x, samples a representative of the class x+I.

Let b R ← -{0, 1} and (B sk J , B pk J ) ← Keygen(λ). -If b = 0, let x R ← -and set v � ← Samp(x) mod B pk J .
Chapter 2. Gentry's ideal lattices scheme

-If b = 1, let v R ← -R mod B pk J .
The Ideal Coset Problem is to guess b with the knowledge of (v, B pk J ).

If the image of Samp samples from a ball of too small radius, solving ICP is easy. Gentry reduces the semantic security of the homomorphic scheme to the Ideal Coset Problem.

Theorem 2.4.1. If A is an algorithm that breaks the semantic security of the ideal lattice homomorphic scheme with advantage ε, then there is an algorithm B that solves ICP with advantage ε/2.

Proof: Suppose an attacker Bob wants to solve ICP. He uses the algorithm A, which asks B to send the encryption of one of two messages π 0 or π 1 . Bob defines a bit β and sends Enc(π β ) to algorithm A. The algorithm outputs a guess β � to the challenge, which will be correct with an advantage ε. Bob answers the ICP challenge with the bit β ⊕ β � . Indeed, if b = 0, Bob's simulation is perfect: the message given to Bob from the ICP instance is of the form ψ ← π β + v × s mod B pk J and therefore of the form Enc(π β ). The algorithm A will output the correct β � = β with an advantage of ε, thus giving an advantage of ε pour B. If b = 1, the advantage of Bob is 0 since ψ is a uniformly random element of the parallelepiped P (B pk J ). Hence Bob total advantage is ε/2. �

The ratio between the size of λ 1 (J) (the norm of the smallest vector of J) and the sampling radius l Samp is crucial to conserve the difficulty of this problem. If fact, if λ 1 (J)/l Samp ≥ 2 n , one can find the nearest lattice element j ∈ J to the challenge v (using variants of LLL and Babai's nearest plane algorithm). If dist(j, t) > l Samp , then v was generated uniformly, and if dist(j, t) < l Samp then more than likely v is an actual encryption.

There are no known attacks for l Samp = poly(n), λ 1 (J) = 2 O( √ n) , and controlling the value λ 1 (J) is possible via a spectral analysis of rotation matrices (see [START_REF] Ogura | An Improvement of Key Generation Algorithm for Gentry's Homomorphic Encryption Scheme[END_REF]).

Natural density of some classes of lattices

We are motivated by the choice of I, J, which are meant to be relatively prime lattices. Practical questions arise, for instance, how "dense" is the set of relatively prime lattices in the set of pairs of random lattices? As stated before, each lattice of Z n is uniquely defined by a matrix in Hermite Normal Form. This allows to imagine a random lattice sampler:

Definition 2.5.1. Let H n (t) be the distribution that samples n positive integers d 1 , . . . , d n uniformly in {1, . . . , t} and (n 2n)/2 integers a ij for i = 1, . . . , n and j = i + 1, . . . , n uniformly in {-t, . . . , t} for a large integer B, and then outputs the Hermite Normal Form of the following matrix

           d 1 a 1,2 a 1,3 • • • a 1,n-1 a 1,n 0 d 2 a 2,3 • • • a 2,n-1 a 2,n 0 0 d 3 • • • a 3,n-1 a 3,n . . . . . . . . . . . . 0 0 0 • • • d n-1 a n-1,n 0 0 0 • • • 0 d n           
.

Let ||•|| max be the component-wise max norm defined by ||M || max := max i,j |M ij |. Let also B t be the ball of matrices centered at 0 with radius t with respect to the max norm, then image of this sampler is the set of all random matrices in HNF lying inside the ball B t , or equivalently, all lattices with det(L) ≤ t n . In this section we aim to quantify some probability distributions on random lattices, i.e. random Hermite Normal Forms. These results aim to give intuition on the more complex problem of studying the distribution of relatively prime random ideal lattices. Let us first define the natural density of a set of matrices. t n 2 , when the limit exists.

Natural density of diagonal elements of HNF's

Here, we show that uniformly random HNF matrix in the sense of the sampler H n follows a very different structure as the HNF of a uniformly random matrix. In [START_REF] Maze | Natural density distribution of Hermite normal forms of integer matrices[END_REF], authors prove the following: Theorem 2.5.1. (i) The natural density of matrices having at least one zero in the diagonal of their HNF is zero.

(ii

) Let (d 1 , • • • , d n-1 ) ∈ (N * ) n .
The natural density of matrices having a HNF of the form

HNF(A) =            d 1 * * • • • * * 0 d 2 * • • • * * 0 0 d 3 • • • * * . . . . . . . . . . . . 0 0 0 • • • d n-1 * 0 0 0 • • • 0 β            , where β = | det(A)| � n-1 i=1 d i , is equal to δ(d 1 , • • • , d n-1 ) = (ζ(n) • ζ(n -1) • ... • ζ(2) • d n 1 • d n-1 2 • ... • d 2 n-2 • d n-1 ) -1 .
The proof of this theorem relies on two fundamental observations: (a) The natural density of k-tuples (r 1 , . . . , r k ) with pgcd(r 1 , . .

. , r k ) = d is (ζ(k) • d k ) -1
where ζ is the Riemann Zeta function and (b) if E is a set of elements of Z n , then U E := {U e, e ∈ E} has the same natural density that E, where U is any unimodular matrix. The proof is interesting, see [START_REF] Maze | Natural density distribution of Hermite normal forms of integer matrices[END_REF].

In this fashion, if by uniformly random lattice we mean the lattice generated by the columns of a uniformly random matrix, then the natural density of lattices L whose HNF diagonal elements are

d 1 = d 2 = • • • = d n-1 = 1 and d n = det(L) is ( � ∞ k=2 ζ(k)
) -1 = 0.436.... Hence, it is likely that public bases of Gentry scheme have "1" entries almost everywhere in the diagonal, and large divisors of the determinant near the tail. In our implementation, we observed precisely this behavior.

Natural density of coprime lattices

Now, let I be a fixed lattice generated by the columns of A, and let φ denote Euler's totient function. We prove the following: Proposition 2.5.2. Let B ← H n . The probability that the lattice J generated by B is coprime to I verifies

1 det I ≤ P((I, J) = Id) ≤ ϕ(det I) det I ,
with equality at left if det I is a power of 2 and equality at right if the diagonal elements of HNF(I) are pairwise coprime.

Proof: From proposition 2.3.2 we know that (I, J) = 1 if and only if (A kk , B kk ) = 1 for all 0 ≤ k ≤ n. Hence

P((I, J) = Id) = P(∀ 0 ≤ k ≤ n : (A kk , B kk ) = 1) = n � k=1 P((A kk , B kk ) = 1) = n � k=1 ϕ(A kk ) A kk = 1 det(I) n � k=1 ϕ(A kk ).
where ϕ(x) is Euler's totient function (the amount of integers relatively prime to and smaller than x). Note that ϕ(ab) ≥ ϕ(a)ϕ(b) (with equality if (a, b) = 1), and the result follows. � Remark. A plaintext space B I for Gentry's scheme which gives a good probability involves a choice of I such that det(I) is a product of n (not necessarily distinct) prime numbers p 1 , . . . , p n , each one greater than an integer αn, and such that HNF(I) = H verifies H ii = p i . The probability then gives

P((I, J) = Id) = n � i=1 � 1 - 1 p i � > � 1 - 1 αn � n > exp(-1/α).
For instance, if α = 1, then the probability of sampling an ideal lattice J relatively prime to I is greater than 1/e ≈ 36.79%.

We consider now the natural density of two coprime HNF's:

Proposition 2.5.3. Let H ← H n , H � ← H n .
The natural density of coprime matrices H and

H � is δ((H, H � ) = Id) = � 6 π 2
� n .

Proof: If follows directly from the fact that the natural density of relatively prime integers is 6/π 2 . �

Natural density of odd ideal lattices

Let us say that an ideal lattice is odd if it is relatively prime to the ideal lattice (2). Therefore, L is odd if all diagonal entries of HNF(L) are odd, or equivalently, if det L is odd. If lattices are sampled via a uniformly random matrix, it suffices to compute the natural density of matrices with odd determinant. Lemma 2.5.4. The natural density of matrices in M n×n (Z) with odd determinant is

δ n = |SL n (F 2 )| 2 n 2 = n � i=1 � 1 - 1 2 i
� .

Proof: We wish to compute

δ n (t) = 1 t n 2 #{M ∈ M n×n (Z), |m ij | ≤ t ∀i, j, det(M ) ≡ 1 mod 2}
and δ n := lim t→∞ δ n (t). We first perform a reduction modulo 2 and work in F 2 , this eliminates the dependency on the radius t:

δ n = 1 2 n 2 #{M ∈ M n×n (F 2 ), det(M ) = 1(mod 2)}.
We hence see that the natural density δ n is exactly the proportion of invertible elements of M n×n (F 2 ). One can actually count this elements: let (x 1 , • • • , x n ), x i ∈ {0, 1} n be the columns of a matrix in M n×n (F 2 ). Then if this matrix is invertible, the family (x 1 , • • • , x n ) is linearly independent. Thus, for the first column there are 2 n -1 choices since it can be zero. The second column must not verify an equation of the form e 1 x 1 = x 2 by independence, hence there are 2 n -2 choices.

The third column must not verify an equation of the form e 1 x 1 + e 2 x 2 = x 3 , and thus there are 2 n -4 choices. Continuing the argument, the column x k must be linearly independent of the precedent k -1 columns, i.e. a choice between 2 n -2 k-1 elements. This way,

#{M ∈ M n×n (F 2 ), det(M ) = 1} = n-1 � i=0 (2 n -2 i ),
and the result follows. � Note that, for all n ≥ 2, δ n is a strictly decreasing sequence, from where we conclude 0.28 ≈ lim k→∞ δ k < δ n < δ 2 ≈ 0.38.

Remark on natural density of circulant matrices with odd determinant

Let L be an ideal lattice and let R L its rotation basis. The set of bases of L is exactly

B(L) = R L • GL n (Z),
i.e. , the set of all matrices of the form R L U where U is a unimodular matrix. If the set of circulant matrices is not uniformly distributed in M n×n (Z), the latter lemma may not be relevant: the parity of the determinant may have a very different distribution when constrained to cyclic matrices. In a more direct approach, the determinant of circulant matrices can be written in terms of the generating polynomial. Indeed, if

M = rot(x 0 , x 1 , • • • , x n-1 ), we have M = x 0 Id +x 1 T + x 2 T 2 + x n-1 T n-1 where T =            0 0 • • • 0 1 1 0 • • • 0 0 0 1 0 0 . . . . . . . . . . . . 0 0 0 0 0 0 • • • 1 0            .
The eigenvalues of T are n-th roots of unity µ k = e (2πi/n)k , k = 0, . . . , n -1, and therefore the eigenvalues of M are

λ k = x 0 + x 1 µ k + x 2 µ 2 k + • • • + x n-1 µ n-1 k .
As the determinant is the product of eigenvalues, parity may be established with a deeper analysis of vanishing sums of roots of unity. In other words, the proportion of circulant integer matrices with odd determinant amongst all circulant integer matrices is given by

1 2 n × #{(x 0 , . . . , x n-1 ) ∈ {0, 1} n : n-1 � k=0 n-1 � i=0 x i µ i k = 0 mod 2}
For more on vanishing sums of roots of unity, the reader may refer to [CJ76, Len78, LL00, Ste08, Eve99]. Finally, we state that if the set of circulant matrices up to multiplication by a unimodular matrix is a topological cover of the set of all matrices, then the answer relates to lemma 2.5.4. Unfortunately, this exits the scope of this Dissertation.

Proof-of-concept implementation

We coded a working instance of Gentry's ideal lattice homomorphic scheme in C with the GMP large numbers library. In the first place, we needed to build linear algebra and lattice layers. Note that, in order to compute basis reductions, we needed to calculate Q-inverses of matrices, therefore with the type mpf t of GMP. For completeness, let us enumerate some of the functions we implemented.

Basic functions

A large integer number (having up to millions of bits) is defined in GMP by the prefix mpz t, and a floating point number (with a user-predefined precision) by the prefix mpf t. Some of the functions we implemented follow.

FFT(mpf t &v[N]) (v ← FFT(v)) FastMatrixVector(mpz t A[N][N],mpz t x[N],mpz t b[N]) (b ← Ax) MultiplyCtxt(mpz t x[N],mpz t y[N],mpz t prod[N]) (prod ← x×y mod B pk J ) MultiplyZn(mpz t x[N],mpz t y[N],mpz t prod[N]) (prod ← x × y ∈ Z n ) RandomBinaryVector(mpz t x[N]) (x R ← -{0, 1} n ) RandomVector(mpz t x[N],int lambda) (x R ← -Z n bounded by λ) RintVector(mpz t X[N],mpf t x[N]) (nearest integer vector) Det(mpz t A[N][N],mpz t d) (d ← det(A)) HNF(mpz t &A[N][N]) (A ← HNF(A)) Inverse(mpz t A[N][N],mpf t Ainv[N][N]) (Ainv ← A -1 ) ModBasis(mpz t v,mpz t A[N][N],mpf t Ainv[N][N]) (v ← v -A�A -1 v�). MatrixProduct(mpz t A[N][N],mpz t B[N][N],mpz t P[N][N]) (P ← AB) PALU(mpz t P[N][N],mpz t A[N][N],mpf t L[N][N],mpf t U[N][N]) (P A = LU decomposition) RandomUnimodular(mpz t A[N][N]) (A ∈ R GL(n, Z)) RotationMatrix(mpz t v,mpz t A[N][N]) (A ← rot(v)) Solve(mpz t A[N][N],mpf t x[N],mpz t b[N]) (Solve Ax = b) Transpose(mpz t A[N][N]) (A ← t A)
At key-generation, one must generate a random vector v close enough to Ze 1 and define the secret and public bases as the rotation matrix of v and its Hermite normal form. Also, to test is two lattices are prime, the determinant can be computed. Finally, to test a variant of the key-generation procedure where one randomizes the secret key (instead of computing the HNF) we wrote a function that generates unimodular matrices. See algorithms 4 and 5.

This algorithm runs in cubic complexity, which is enough for our implementation since HNF's are only computed in key-generation time. We mention that better algorithms are reviewed in [START_REF] Pernet | Fast computation of Hermite normal forms of random integer matrices[END_REF].

Algorithm 4 Unimodular Matrix Generator

1: procedure UnimodularMatrixGen Require: A bound B ∈ R + Ensure: A unimodular matrix U such that max i,j |u i,j | ≥ B 2: for 0 ≤ i ≤ N -1 and 0 ≤ j ≤ N -1 do 3: if (i = j) then u ii R ← -{-1, 1} 4: else if (i > j) then u ij ∈ R [[-� 3 √ B�, � 3 √ B�]] 5: else u ij = 0 6: end if 7:
end for 8:

while (max i,j |u i,j | < B) do

9: i ∈ R [[0, N -1]], i � ∈ R [[0, N -1]] \ {i} 10: λ ∈ R [[-� 3 √ B�, � 3 √ B�]]
11:

Row(i) ← Row(i) -λ×Row(i � ) 12: j ∈ R [[0, N -1]] 13: j � ∈ R [[0, N -1]] \ {j} 14: µ ∈ R [[-� 3 √ B�, � 3 √ B�]] 15:
Column(j) ← Column(j � ) -µ×Column(j)

16:

SwapRows(i, i � ) 17:
SwapColumns(j, j � ) 18:

end while 19: end procedure

Scheme algorithms

With these functions, the scheme can be described neatly:

KeyGen(int lambda, mpz t BJsk[N][N],mpz t BJpk[N][N]) { mpz t v[N]; InitVector(v);
RandomVector(v,lambda); while("v is far from every axis") { for k from 0 to N -1 do 3:

RandomVector(v,lambda); } RotationMatrix(v,BJsk); RotationMatrix(v,BJpk); HNF(BJpk); } Encrypt(mpz t pi[N], mpz t Bp[N][N], mpf t Bpinv[N][N]) { Samp(pi,Bp); ModBasis(pi,Bp,Bpinv); } Decrypt(mpz t psi[N], mpz t Bs[N][N], mpf t Bsinv[N][N]) { ModBasis(psi,
while ∃i > k, m ik � = 0 do 4: j � ← such that m j � k = min j≥k (m jk ) 5:
Swap rows j � and k 6:

for l from max(k -1, 0) to N -1 do 7:

Row(l) ← Row(l) -λRow(k) where λ = �m lk /m kk � 8:

end for 9:

end while 10:

if m kk < 0 then Row(k) ← (-1)×Row(k) 11: end if 12:
end for � M is now upper triangular 13:

for k from N -1 to 0 (decreasing) do 14:

for l from max(k -1, 0) to 0 (decreasing) do Output M 19: end function

Performances

Because of the size of public keys, our implementation operates up to n = 200, which is clearly too small to avoid lattice reduction attacks (i.e. recover B sk J from B pk J ). For a choice of parameters allowing depth-2 circuits, we have the performances in seconds given in figure 2 Encryption, addition, multiplication, and decryption took < 0.1 seconds in this setting, but we point out that for larger values of n this performances must be taken into account. For instance, authors in [START_REF] Gentry | Implementing Gentry's Fully-homomorphic Encryption Scheme[END_REF] report 3-minute encryptions and keygeneration for large dimensions in the somewhat homomorphic scheme. We highlight also that when converted into FHE, key-generation and re-crypt procedures took 2.2 hours and 31 minutes, respectively. Multiplication of ciphertexts consists exactly in one polynomial product (where inputs are very sparse) and one basis reduction. The efficiency bottleneck manifests for larger values of n and other choices of the polynomial ring (where fresh ciphertexts are not sparse). Notice also that key generation essentially computes (B sk J ) -1 and HNF(B sk J ) (the inversion of a matrix in Hermite normal form being easy). Above n = 256, the size of matrices and, over all, the floating point precision required, makes our key generation algorithm no longer capable of outputting keys that correctly evaluate homomorphic circuits. A series of tweaks to improve efficiency must be applied. However we only intended to provide a proof-of-concept implementation, since other homomorphic schemes are far more efficient and deserve better analysis. See Chapter 5 for our implementation of the Brakerski-Gentry-Vaikunthanatan scheme, for instance.

We also tested circuit evaluation with artificial keys, for the sake of completeness. To this end we considered the following variant of the scheme (Gentry's first tweak), where no matrix inversion is needed. Note by v sk the first column of B sk J . As rot(v sk ) = B sk J , only v sk needs to be stocked in memory. It is easy to see that for every

a, b ∈ Z n , a × b = rot(a)b = rot(b)a. Now suppose that w ∈ Q n is such that w × v sk = 1 ∈ R. For 0 ≤ k ≤ n -1, we have w × (X k v sk ) = X k ,
and therefore w × rot(v sk ) = Id, hence rot(w) = (B sk J ) -1 . With this notations, the decryption equation becomes

Dec(ψ) = (ψ -v sk × �w × ψ�) mod 2.
When R = Z[x]/(f (x)), in order to compute w = (v sk ) -1 , just apply the Extended Euclidean algorithm on inputs v sk and f (x). This variant reduces considerably the size of keys, however, the floating point precision is still of order about log det J to ensure correct decryptions. With this tweak, we evaluated circuits to give in table 2 In an application of depth 10 with n = 1024, we estimate that the secret key in our implementation is of Euclidean norm O(2 1.1•10 8 ), which corresponds to about 14MB of data. This agrees to [START_REF] Gentry | Implementing Gentry's Fully-homomorphic Encryption Scheme[END_REF] where authors report a public-key size of 70MB for n = 2048. In contrast, they implement the full scheme (bootstrapping included) and they use highly optimized algorithms to compute resultants and arithmetic in Z[x]/(f (x)).

Conclusion

In this Chapter, we described in detail the first FHE scheme ever constructed, as an homage to Craig Gentry's dissertation. We verified with a C+gmp implementation its huge handicap in efficiency, and agreed to the fact that it is not remotely competitive with other FHE schemes. Finally, we gave a digression about the probabilistic structure of some classes of random lattices.

Chapter 3 A Key-Recovery Attack Against Gentry's Ideal Lattice Scheme via ad-HPP

The contents of this Chapter include an article submitted to an international conference. This is joint work with Louis Goubin and Cyril Hougounenq.

Introduction

A parallelepiped of R n , or parallelotope, is the polytope obtained when translating a point of R n successively in n independent directions. It is the set delimited by 2n hyperplanes of dimension n -1 such that there are exactly n different pairs of parallel hyperplanes. Consider the following.

Adaptive Hidden Parallelepiped Problem (ad-HPP): Let P be a secret parallelepiped in R n centered at 0 with vertices in Z n . Let χ be the indicator function of P . Given adaptive access to χ and a superior bound D on the diameter of P , recover P .

Gentry's celebrated first fully homomorphic scheme relies on ideal lattices of R n . In particular, the keys (sk, pk) are two parallelepipeds of the same volume, such that sk is quite orthogonal and small, and pk is eccentric and large (it may look like a long segment of R n ). The latter one is public and it serves to encrypt messages, implying that any attacker may use it to try and recover information about sk or the underlying message. In this article we show that an attacker having access to adaptive decryption queries may construct a function that matches the indicator function of sk in all points of R n with overwhelming probability. With sufficient amount of queries they can use any algorithm solving ad-HPP to find the vertices of sk, or approximate its shape with some precision, which can be enough to recover the parallelepiped.

Fully Homomorphic Encryption. In a groundbreaking sequence of articles [START_REF] Gentry | A Fully Homomorphic Encryption Scheme[END_REF][START_REF] Gentry | Fully Homomorphic Encryption Using Ideal Lattices[END_REF], Gentry constructed the first fully homomorphic encryption (FHE) scheme. An FHE scheme is a regular public key encryption scheme that allows public processing of ciphertexts, without access to decryption secrets. More precisely, it allows to publicly transform a set of ciphertexts into a new one that encrypts any desired polynomial function on the underlying plaintexts. FHE finds several modern applications, and exciting research has been performed since 2009. In order to fulfill the needs of these applications and to compete with contemporary encryption schemes, optimizations, modifications and new proposals have been appearing in order to improve efficiency and security. Today, there are five families of homomorphic schemes, based on ideal lattices, integers, NTRUEncrypt, (Ring) Learning With Errors and Approximate Eigenvalues, respectively. Some constructions are better in security, others in efficiency, and others exhibit fancy properties (let us highlight the Multikey FHE scheme of Lopez-Alt et al. [START_REF] López-Alt | On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[END_REF], the provable circular-secure of Brakerski et al. [START_REF] Brakerski | Fully Homomorphic Encryption from ring-LWE and Security for Key-Dependent Messages[END_REF], and the attribute-based of Gentry et al. [START_REF] Gentry | Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based[END_REF]). Recent proposals greatly outperform the original ideal lattices scheme as they are better in efficiency, more suited for applications and less complex in structure. We review the first scheme in section 3.3, in order to present our key-recovery attacks in section 3.4.

FHE and chosen ciphertext attacks.

It is known that FHE schemes cannot resist CC-2 attacks, i.e. when an adversary aims to decrypt a challenge ciphertext with the help of an oracle that decrypts ciphertexts under the corresponding key. The reason for this is that despite the attacker is not allowed to submit the challenge, she can transform it into a different ciphertext using identity homomorphic operations (such as m � → m ⊕ 0) and submit the result. Of course, this does not mean that the secret of the oracle can be retrieved by the adversary in a CC attack. Precisely, the aim of this paper is to show that the original scheme proposed by Gentry allows an attacker to recover the secret key in polynomial time.

Our Contributions. We first show how to use an ad-HPP solver to recover a secret key of Gentry's scheme. We propose two algorithms that solve ad-HPP. Our first proposal consists in guessing sufficiently many points near the boundary and then approximating an edge of the parallelepiped (which recovers the full secret by rotations). It uses O(n 2 log D) adaptive calls to χ. Our second and more promising proposal imitates the effect of gravity, bouncing repeatedly against ∂P and converging to a vertex. To this end, after n bounces the attacker computes the (n-1)-surface generated by the n bouncing points, and repeats the process starting from the center of the hyperrectangle formed by these points. We prove that �log(D)� repetitions are enough to output a vertex, and that two neighbor vertices can be found adaptively by submitting O(n log 3 (D)) points to χ. With this, retrieving a secret-key of Gentry's scheme can be done with O(n log 3 n) adaptive calls to the oracle. We give a complete analysis and proof of our attack.

Related Work. The Hidden Parallelepiped Problem has already been used in cryptanalysis in its non-adaptive form, i.e. , guess the parallelepiped given a list of random uniformly distributed points in its interior, without access to the indicator function or the integer vertices hypothesis. In [START_REF] Nguyen | Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures[END_REF], Nguyen and Regev introduced a nice algorithm solving the Hidden Parallelepiped Problem based on an optimization problem on a n-hypercube after proper transformations. We refer to it as the Nguyen-Regev algorithm. They applied it to cryptanalyze NTRU and GGH signature schemes, reporting full recovery of NTRU secret keys using only 400 message-signature pairs for advised parameters. In the adaptive version of HPP we introduce, the attacker may generate a list of interior points using the indicator function and feed the NR algorithm to find the parallelepiped. However, a large number of points is required to proceed. Authors overcome this using known symmetries on NTRU lattices, which allow to generate a number of signatures from a given message-signature list. Unfortunately, these symmetries are not present in Gentry's ideal lattices. Some other key-recovery attacks against homomorphic encryption schemes have been published, we mention [START_REF] Dahab | Adaptive Key Recovery Attacks on NTRU-Based Somewhat Homomorphic Encryption Schemes[END_REF] and [START_REF] Loftus | On CCA-Secure Somewhat Homomorphic Encryption[END_REF]. The latter includes an attack to a variant of Gentry's scheme that turns out to be isomorphic to the I = (2) case. In contrast, to the best of our knowledge, our proposal is the first direct key-recovery attack to the scheme.

Overview of this chapter. In sections 3.2 and 3.3 we review some concepts and revisit Gentry's scheme, for the sake of completeness and independence of the Chapters. In section 3.4 we describe our key recovery attack, and present some numerical evidence in section 3.5.

Preliminaries

Notation

Vectors in R n are noted with an arrow: � a, canonical vectors in R n are noted by bold letters: e 1 = (1, 0, 0, . . . , 0). If S if a set of vectors of R n , �S� denotes the vector space generated by elements in S, and �S� ⊥ is the orthogonal complement of �S�. If E is a set, e $ ← -E means that e was sampled randomly from E using the uniform distribution. Unless stated otherwise, the norm in R n is the Euclidean

norm ||� x|| 2 = � � i x 2 i .
If P is a polytope, ∂P denotes its boundary. The (n -1)-th dimensional hyperplanes delimiting the interior of a parallelepiped are called facets, and the lines connecting two consecutive vertices are called edges. Two vertices are said to be neighbors if there is an edge that connects them. Overloading notation, if p(x) is a polynomial of degree n -1, its coefficient vector α(p) will be also noted p. If (g) is an ideal in R, the ideal lattice α((g)) will be also noted (g). The rotation basis of (g) is denoted by rot(g). Bases of ideal lattices will be noted with bold letters. All lattices in this article are of full rank, we identify their bases with square invertible matrices. Let I n be the n × n identity matrix.

Lattices

Definition 3.2.1 (Lattice). A lattice in R n is a discrete subgroup of (R n , +) which spans R m as a R-vector space.

Every lattice L has a minimal subset of m elements B ⊂ L such that L = � b∈B Zb. When n ≥ 2 there is an infinite number of such sets and we call them bases of L. The integer m does not depend on the chosen basis and is called the rank of L, therefore, to describe a lattice, only one basis is required. Given a basis of rank m in matrix form

B = (b 1 |b 2 | • • • |b m ), the quantity |det(B)| := � det( t BB
) is an invariant of L, which we note by det L. Let the fundamental parallelepiped of the basis B be the translated convex hull delimited by the column vectors in B. We note this parallelepiped by

P (B) = � � 1≤i≤m x i b i ∈ R n ; x i ∈ [-1/2, 1/2[ � .
By definition, the volume of P (B) equals the determinant of the lattice: det(L) = meas n (P (B)) for any basis B. Let L be a full rank lattice. If x ∈ R n , we note by x mod L the equivalence class of x in the quotient group R n /L. We use the fundamental parallelepiped P (B) as the set of representatives of the equivalence classes when describing L with the basis B. Therefore, it is natural to note by x mod B the singleton in (x mod L) ∩ P (B). To reduce a vector x ∈ R n modulo B, use Z-linear combinations of vectors in B to find the equivalent vector inside P (B). In other words, Lemma 3.2.1. Let x ∈ R n and B a basis of a full-rank lattice L. Then x mod B = x -B�B -1 x�, where �v� := (�v 1 �, �v 2 �, • • • , �v n �) is the closest Z n vector to v.

In the scheme, two coprime lattices I, J will define the plaintext and ciphertext space respectively. Definition 3.2.2 (Relatively prime lattices). Two lattices L, L � of Z n are relatively prime (or coprime) if their sum is Z n . We note this (L, L � ) = 1. Keys in Gentry's scheme are lattice bases. The private-key is a "good" basis in the orthogonality defect sense and the public key is an eccentric, large basis of the same lattice. More precisely, this large basis is the Hermite Normal Form of the lattice.

Polynomial ideal lattices

Let (R, +, ×) be a commutative ring and α : R → R n an additive group homomorphism, then α(R) is a lattice. This yields because α transports the additive structure of R to points in R n in order to generate linear integer combinations of them.

Definition 3.2.3 (Ideal lattice). Let A be a commutative ring and α : A → R n an additive ring homomorphism. An ideal lattice of R n is a lattice of the form α(I) for a principal ideal I ⊂ A.

Consider the ring R = Z[x]/(f (x)) where f is a monic polynomial of degree n, and the natural homomorphism α : R → Z n given by α : a(x) = a 0 + a 1 x + • • • + a n-1 x n-1 � → (a 0 , . . . , a n-1 ). We can now define a precise ideal lattice: if I = (v) is a principal ideal of R, then α(I) is a lattice of R n with a remarkable basis:

Lemma 3.2.2. Let v ∈ R, I = (v) and v i = v × X i mod f (X) for i = 1, . . . , n -1.
Then a basis of the ideal lattice α(I) is given by a linearly independent subset of rot(v

) := {v, v 1 , v 2 , • • • , v n-1 }.
Definition 3.2.4 (Rotation basis). The set {v i = v × x i mod f (x); i = 0, . . . , n -1} is called the rotation basis of (v). The matrix rot(v) = (v|v 1 | . . . |v n-1 ) is called the rotation matrix of v.

Proposition 3.2.3 (Inversing rotation matrices

). Let v ∈ R × . Then rot(v) × rot(v -1 ) = I n .

Key-Recovery Attacks against SHE schemes

In the chosen ciphertext (CC) model, an attacker faces an oracle possessing a secret who publishes a challenge -the encryption of a random message r -and the goal of the attacker is to guess the message. To this end they engage in exchanges, in which the attacker submits a set of ciphertexts of his choice (different from the challenge ciphertext) and the oracle responds with the decryption of each ciphertext. The publication of the challenge can occur after or before the exchanges (which is referred to as CCA-1 or CCA-2). The attack is successful whenever the adversary is able to guess r with better probability than a third party who guesses the plaintext without access to any decryption oracle. If in the course of these exchanges, the attacker reconstructs the oracle's secret, the attack is said to be a Key-Recovery (KR) attack. This is evidently stronger than a CC attack. To the date, a number of KR attacks against SHE schemes have been published, including one against the Gentry-Halevi variant of Gentry's ideal lattice scheme [START_REF] Loftus | On CCA-Secure Somewhat Homomorphic Encryption[END_REF]. As this variant is essentially homomorphic to the I = (2) Gentry's scheme, their attack applies in this case, as mentioned in the abstract of [START_REF] Loftus | On CCA-Secure Somewhat Homomorphic Encryption[END_REF]. The attack we propose is, to the best of our knowledge, the first direct KR attack to [START_REF] Gentry | A Fully Homomorphic Encryption Scheme[END_REF][START_REF] Gentry | Fully Homomorphic Encryption Using Ideal Lattices[END_REF].

Let us specify the KR game addressed by our attack. Let E = (Keygen, Enc, Dec) be a public encryption scheme and let (sk, pk) ← Keygen(1 λ ). Let O be an oracle that possesses sk and assume there is an adversary A with knowledge of every public element of the scheme.

Key-Recovery Game.

1. A generates a ciphertext c and sends it to O.

O computes the underlying plaintext m and sends it to A.

3. Repeat the two last steps � times.

4.

A makes a guess sk � , and wins if sk � = sk.

We say that the attack is successful if A wins the game with better probability than a random guesser.

Gentry's ideal lattice basic scheme

With the homomorphism Z n � R = Z[x]/(f (x)), ring operations are inherited by structure transport. This way, for all v, w ∈ Z n and a basis B we define addition v + w := α(v(x)+w(x)), product v×w := α(v(x)×w(x)), and basis reduction v mod B := v -B�B -1 v�. We are now ready to define the scheme. The scenario of this scheme is as follows -Fix a dimension n ≥ 2 and a monic polynomial f of degree n. To prevent lattice reduction attacks, n must be sufficiently large.

-Let R = Z[x]/(f (x)). In order to control the norm of products, f is of the form X n + h(X) where deg(h) is small (for instance h(X) = -1).

-Let I be an ideal lattice with a basis B I . The binary plaintext setting is set with I = (2), although we do not limit ourselves to this case.

-Let J be an ideal lattice relatively prime to I, with two bases B sk J , B pk J . The secret B sk J is quite orthogonal, with large volume such that P (B sk J ) contains P (B I ), and B pk J is very eccentric (defined by large and almost parallel vectors).

-Choose an algorithm Samp : Z n /(I) → Z n that given a vector x, samples randomly from x + (I). The samples should lie inside a ball of fixed radius l Samp contained in P (B sk J ).

The plaintext space in the scheme is P := Z n ∩ P (B I ) (a small, quite orthogonal parallelepiped) and ciphertext space is Z n ∩ P (B pk J ) (a huge, very eccentric parallelepiped). The elements n, f, I, J, B I are all public, and the keys are pk = {B pk J }, sk = {B sk J }. The scheme is described in 6.

Algorithm 6 Gentry's homomorphic ideal lattice scheme

1: function Keygen(λ) 2:
Generate B sk J and B pk J randomly from a security parameter. 3: end function ---4: function Enc(pk,π ∈ P (B I ))

5:

To encrypt message π, compute ψ ← Samp(π) mod B pk J and output ψ. It is an integer vector of the form π + i + j where i ∈ I, j ∈ J, and it is inside P (B pk J ). 6: end function ---7: function Dec(sk,ψ)

8: To decrypt ψ, compute µ = (ψ mod B sk J )mod B I = (ψ -B sk J �(B sk J ) -1 ψ�)mod B I and output µ. 9: end function --- 10: function Eval(pk,C,ψ 1 , • • • , ψ t ) 11:
Perform the circuit C on inputs ψ 1 , • • • , ψ t replacing each "+" and "×" gate of C by addition and multiplication modulo B pk J respectively. Output the result. 12: end function

The attack

We assume that the secret basis is the rotation matrix of a secret polynomial, i.e. B sk J := rot(v sk ) (this is the setting proposed in [START_REF] Gentry | A Fully Homomorphic Encryption Scheme[END_REF] and maintained in later revisions). In other words, the secret basis is generated by any of its elements. This implies that the full parallelepiped may be retrieved when a vector along any edge is known. We first show that any algorithm solving ad-HPP may be used to recover a secret vector in Gentry's scheme: to this end we define a function Z n → {0, 1} that matches the indicator function of P (B sk J ) over Z n with overwhelming probability, and estimate the diameter bound D using public values.

Reduction to ad-HPP

In order to recover the secret key B sk J of the scheme, first remark that only an edge of P (B sk J ) is sufficient, since it allows to find a polynomial that generates the basis by rotations. Recall that the ciphertext space is P (B pk J ). The decryption equation of a ciphertext ψ ∈ P (B pk J ) with secret-key

B sk J is Dec(B sk J , ψ) = (ψ mod B sk J ) mod B I .
Now, consider the function g : Z n → P (B I ):

g : x � → (x mod B I ) -Dec(B sk J , x).
However, note that x may not lie in the ciphertext space, and the decryption query may be refused depending on the setting. Addressing this, define θ :

Z n → P (B I ) as θ = g • mod B pk J .
It follows that θ(x) = 0 for all x ∈ P (B sk J ) and, with overwhelming probability, θ(y) � = 0 if y � ∈ P (B sk J ). Finally, define χ : Z n → {0, 1} as follows

x � → χ(x) = � 1 if θ(x) = 0, 0 if θ(x) � = 0.
This function matches the indicator function of P (B sk J ) in R n with overwhelming probability. Remark also that the attacker can estimate the diameter as D ≈ 2

√ n • ||v sk || 2 , or using only public values,

D ≈ √ n • Vol(P (B sk J )) 1/n = √ n • | det P (B sk J )| 1/n = √ n • | det P (B pk J )| 1/n .
For correct evaluation of k successive multiplications,

||v sk || 2 = O(n k ), hence log D = O(log n).
The attacker guesses the secret key feeding (χ, D) to an algorithm solving ad-HPP.

Feeding Nguyen-Regev's algorithm and Random Scattering

We first propose a method that solves ad-HPP using the well-known Nguyen-Regev algorithm, and a second proposal that collects information about the facets of P . We point out that these two methods require a large number of decryption queries.

Authors in [START_REF] Nguyen | Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures[END_REF] solve non adaptive HPP given a list of uniformly random points in the interior of the secret parallelepiped. They first perform a transformation to obtain a list of points inside a hypercube of dimension n and then they recover the shape with a multivariate optimization problem, solving by gradient descent. This gives a first approach to solve ad-HPP in a non adaptive manner: just ask the decryption of a uniform set of points inside a ball of radius D/2. In the case of Nguyen and Regev, the knowledge of a point inside a NTRU parallelepiped implies the knowledge of a number of different points. This is because of symmetries in NTRU lattices: as stated in [START_REF] Nguyen | Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures[END_REF], from a list of 400 points inside the parallelepiped, it is possible to generate 100,400. In Gentry's ideal lattices, however, no such symmetries are present. According to their experimental analysis in GGH signatures, over 200,000 uniformly distributed points are needed to disclose a secret parallelepiped of diameter ≈ 4n in dimension n = 400. Gentry's parallelepiped has diameter O(n k ) where k is the maximum allowed depth of evaluation circuits, drastically increasing the number of required samples. Nevertheless, we point out that new samples can be generated using homomorphic evaluations, although disturbing the uniformity assumption of Nguyen-Regev algorithm. We leave the analysis of this possibility as an open problem.

In the second method we propose, the attacker finds K = O(n) points near a neighborhood of ∂P and fit an hyperplane between them in order to approximate a facet. They repeat the process in other O(n) directions, and then solve linear systems to find approximation of vertices.

To find a single point near ∂P , the attacker starts from 0, chooses a random direc-

i = � d + � r i for i = 1, . . . , K -1 with ||� r i || 2 � || � d|| 2
(in order to avoid other facets). Another approach to find points near a facet is to perform the dichotomy search inside a cylinder B n (0, r) × � � d � for r > √ n. Once K points near each facet are found, the attacker fits an hyperplane (for instance using linear least squares). The procedure finds an approximation of a vertex in O(n 2 log D) calls to the indicator function χ.

There are many possible descriptions and optimizations of this algorithm, which cost more calls to χ but gives more precision in the approximation of vertices. We state that this can be carried out in O(n 2 log D) calls to χ and the result are points at distance at most O(n) from vertices. As this method requires too many queries and the algorithm analysis is straightforward, we focus on our next proposal.

Falling towards vertices

In this approach, the attacker travels onto vertices imitating the effect of gravity and bouncing against ∂P . This is achieved with a first stage of successive falls to find a vertex V , and a second stage to find a neighbor vertex V � of V . Let us first expose the algorithms and then describe our attack.

-Touch Border: Starting from a point inside P and considering a direction � u, it performs a binary search to find the closest integer point to the boundary ∂P in that direction.

-Bounces: Using Touch Border, it finds n integer points close to ∂P that form an hyperrectangle that roughly points to the vertex.

-Find Vertex: Uses Bounces repeatedly to find a vertex of P .

-Find Neighbor Vertex: Given a vertex V , it outputs another vertex V � connected to V by an edge.

Algorithm 7 Finding a point near ∂P Require: An indicator function χ of a parallelepiped P , the diameter D of P , a point x 0 ∈ P , and a vector � u. Ensure: Two points x ∈ P and y � ∈ P such that d(x, y) < √ n and (x 0 , x, y) are collinear up to translation of √ n.

1: function Touch Border(x 0 , � u)

2: � u ← � u/||� u|| 3: Let x 1 ← x 0 + D� u � Notice that x 1 � ∈ P 4:
return Touch Border Rec(x 0 , x 1 , � u)

Let y ← �x in + ||xout-x in || 2 � u � 11:
if (χ(y) = 1) then 12:

Return Touch Border Rec(y, x out , � u)

= { � v 1 , • • • � v n-1 } ⊂ R n and a vector � u ∈ R n independent from E. Ensure: A set of n points S ⊂ Z n such that d(y, ∂P ) <
√ n for all y ∈ S.

1: function Next Point(x ∈ Z n , � u) 2:
Outputs y, the integer point closest to the segment {x + λ� u/||� u|| : 1 ≤ λ ≤ 2 √ n}.

3: end function 4: function Bounces(x, � u, � v 1 . . . , � v n-1 )
5:

y 0 ← x 6: � v 0 ← � u 7: for i = 1 to n do 8: if χ(Next Point(y i-1 , � v i-1 )) = 1 then (y i , •) ←Touch Border(y i-1 , � v i-1 ) 9: else if χ(Next Point(y i-1 , -� v i-1 )) = 1 then (y i , •) ←Touch Border(y i-1 , -� v i-1 ) 10: else y i = y i-1 11: end if 12:
end for

13:

return {y 1 , . . . , y n } 14: end function Algorithm 9 Fall onto a vertex Require: A parallelepiped P centered at O, the diameter D of P , and a set of

orthogonal vectors {� u, � v 1 . . . , � v n-1 }. Ensure: A point in Z n 1: function Find Vertex(� u, � v 1 . . . , � v n-1 ) 2:
{y 1 , . . . , y n } ←Bounces(O, � u, � v 1 . . . , � v n-1 )

3:

x ← (y 1 + y n )/2

4:

� u � ← -→ Ox � Note that � u � is not necessarily orthogonal to { � v 1 , . . . , � v n-1 } 5: return Find Vertex Rec(x, � u � , � v 1 , . . . , � v n-1 ) 6: end function --- 7: function Find Vertex Rec(x, � u � , � v 1 , . . . , � v n-1 ) 8: {y 1 , . . . , y n } ←Bounces(x, � u � , � v 1 , . . . , � v n-1 ) 9: if (y 1 = y n ) then 10:
return y n 11:

else 12:

x ← (y 1 + y n )/2

A vertex V � such that ||V � -V || < L. 1: function Find Neighbor Vertex(V, L) 2: � u ← V -O. 3: � v $ ← -�� u � ⊥ 4:
return Find Neighbor Vertex Rec(O, V, � u, � v, L, 0, 1)

5: end function --� Look by dichotomy a direction that leads to a neighbor vertex

6: function Find Neighbor Vertex Rec(O, V, � u, � v, L, a, b) 7: t ← a+b 2 8: � w ← (1 -t)u + tv 9:
Compute W � , an orthogonal base of �w� ⊥ 10:

V � ←Find Vertex(O, � w, W � ) 11: if V = V � then return Find Neighbor Vertex Rec(V, � u, � v, L, a+b 2 , b) 12: else if ||V � -V || < L then return V � . 13:
else return Find Neighbor Vertex Rec(V, � u, � v, L, a, a+b 2 )

14:

end if 15: end function

Falling towards V

We now detail the algorithms, prove their correctness and state their complexity. The aim is to find a vertex of P . First choose a set of orthogonal vectors � u, � v 1 , . . . , � v n-1 and start from the center of the parallelepiped, denoted O. Using algorithm 7, find a point y 1 ∈ P along O + �� u� such that dist(y 1 , ∂P ) < √ n. From y 1 , repeat the procedure advancing in the inward pointing direction in {-� v 1 , � v 1 }: again use algorithm 7 along y 1 +�� v 1 � to find a point y 2 ∈ P such that dist(y 2 , ∂P ) < √ n (if there are no inward pointing directions, simply set y 2 = y 1 ). Continuing recursively, at step k we have a point y k near the boundary, from which we choose an inward pointing direction in {� v k , -� v k }. If no such directions are available, set y k+1 = y k , else travel with algorithm 7 along y k + �� v k � to find a point y k+1 near ∂P . This procedure performs n steps and outputs n points near the boundary. The fall is detailed in algorithm 8. The next step is to compute c = (y 1 + y n )/2 and repeat the fall starting from c in the direction � u � = -→ Oc while maintaining the previous directions � v 1 , . . . , � v n-1 . Continue recursively and stop when there are no inward pointing, norm growing directions. The whole procedure is detailed in algorithm 9. We show in theorem 3.4.3 that this procedure stops, and outputs a vertex in O(n log 2 (D)) calls to χ. Proof. Let k be the number of recursive calls to Touch Border. At each step the function computes a candidate to a point near the border, and reduces by 2 that distance, which is initially less than D.

Let us discuss the correctness of the Find Vertex algorithm. Without loss of generality take the canonical vectors � u = e 1 , � v 1 = e 2 , . . . , � v n-1 = e n . Let O be the center of P , and define S 0 ←Bounces(O, e 1 , e 2 , . . . , e n ). Recall that S 0 is a set of n points very close to ∂P , generated by bouncing against ∂P successively along the directions e 1 , . . . , e n . Parse S 0 = {x

(0) 1 , . . . , x (0)
n }, and note that the sequence ||x

(0) 1 ||, . . . , ||x (0)
n || is strictly increasing with overwhelming probability, unless we have reached a vertex. Now, set c 0 ← (x

(0) 1 +x (0) n )/2, u 0 =
--→ Oc 0 and define recursively for i ≥ 1:

S i = {x (i) 1 , . . . , x (i) n } ← Bounces(c i-1 , � u i-1 , e 2 , . . . , e n ), c i ← (x (i) 1 + x (i) n )/2 u i ← -→ Oc i Proposition 3.4.2.
The program Find Vertex outputs a point in Z n in a finite number of steps.

Proof. The algorithm outputs a point when there are no inward-pointing and normgrowing directions available (by convexity of the parallelepiped this is a vertex). Before this happens, the integer sequence of bouncing points norms

||x (0) 1 ||, . . . , ||x (0) n ||, ||x (1)
1 ||, . . . , ||x (1) n ||, ||x (2)
1 ||, . . . ||x (2) n ||, . . . is strictly increasing and bounded by D/2.

We quantify in the following theorem the ratio of diameters of two successive hyperrectangles containing the bounces in the process of finding a vertex.

Theorem 3.4.3. For all k ≥ 0, let d k := dist(x (k) 1 , x (k) n ). Then d k+1 ≤ d k /2.
Proof. At any iteration of the algorithm, we have an initial point c and suppose without loss of generality that the given set of vectors to perform a fall from c is {� u, e 2 , . . . , e n }, where � u is independent from {e 2 , . . . , e n }. Let x 1 , . . . , x n be the bouncing points obtained after n bounces. Recall that by construction, we have

               x 1 = c + λ 1 � u, x 2 = x 1 + λ 2 e 2 , x 3 =
x 2 + λ 3 e 3 , . . .

x n = x n-1 + λ n e n ,

Length of binary searches in the neighbor algorithm

Proposition 3.4.5. Let P be a parallelepiped centered in O with a known vertex V . Let � v = --→ OV , and � u $ ← -�� v� ⊥ . Then, with overwhelming probability, there is a vector

� w ∈ {(1 -t)v + tu : t ∈ [0, 1]} such that a fall inside P in the direction � w converges to a neighbor of V . Proof. Consider a linear transformation ψ : [-1, 1] n → P such that ψ((1, 1, . . . , 1)) = V . Let � a = ψ -1 (� v), � b = ψ -1 (� u). Now, let f : [0, 1] → R n such that f (t) := t� a + (1 -t) � b.
With overwhelming probability, � b is not normal to a cube's facet, and in this case as f (1) = � a and f (0) = � b, by continuity of f it follows that there is a value t 0 such that f (t 0 ) has exactly one negative and n -1 positive non-zero coordinates (i.e. , f (t 0 ) points inside a neighbor hyperoctant). Now, note that a fall inside the cube towards a direction � d = (d 1 , d 2 , . . . , d n ) converges with overwhelming probability to the vertex (sign(d 1 ), sign(d 2 ), . . . , sign(x n )) where sign(x) = x/|x|. With this, a fall towards f (t 0 ) converges to a neighbor C of (1, 1, . . . , 1), thus a fall inside the parallelepiped towards � w = ψ(f (t 0 )) converges to V � = ψ(C), a neighbor of V .

This vector �

w can be found by dichotomy, which is what we propose in algorithm 10. Moreover, our numerical analysis of section 3.5 suggests that in dimension n = 512 there are about 64% chances that this dichotomy ends in less than 7 steps, and about 77% in less than 11 (compared to the theoretical log(D) ≈ k log(512) steps where k is the maximum allowed depth of the scheme). In dimension n = 1024, we report 42% and 57%, respectively. With this method, only one additional complete fall is necessary to find a neighbor vertex, the falls converging elsewhere can be discarded after one bounce against ∂P because of too small or excessive distances from V .

Summing up all procedures, the attacker may find two adjacent vertices V 1 , V 2 in O(n log 3 D) calls to χ as follows:

1. V 1 ←Find Vertex(O, e 1 , . . . , e n ). 2. V 2 ←Find Neighbor Vertex(V, αD/ √ n) with a constant α � 1
With two neighbor vertices, the attacker finally establishes

v sk = V 1 -V 2 .

Length of binary searches in the neighbor algorithm

Our algorithm 10 uses binary searches to find a direction leading to a neighbor vertex. In theory, these searches finds such a direction in log D steps. However, we conducted experiments and found that even in high dimensions, the search has good chances of succeeding in very few steps. Consider the hypercube [-1, 1] n and let v = (1, 1, . . . , 1) be the already found vertex. It is clear that the neighbors of v are the n elements of {-1, 1} n that possess only one negative coordinate, and that a fall towards direction (u 1 , . . . , u n ) inside the hypercube converges towards (sign(u 1 ), . . . , sign(u n )). Therefore, take a random vector � v ∈ �� u� ⊥ , the goal is to find an element f (t 0 ) in the set {f (t) = (1t)u + tv, t ∈ [0, 1]} with exactly one negative coordinate. We implemented the dichotomy in C++, and obtained apparent bounds for the parameter t 0 depending on the dimension, as well as the expected number of dichotomic tries. In the table below, k is the number of dichotomic steps performed. For each setting, we performed 10,000,000 searches. A success is when a search outputs a vector with only one negative coordinate before k recursions.

n Notice how the interval size containing the desired parameter diminishes as the dimension grows. We point out that if the linear transformation between the parallelepiped and the hypercube is almost homothetic up to rotations (for instance in Gentry's setting), a similar behavior should be observed when performing the binary search inside the parallelepiped.

[

Conclusion

We proposed a new key recovery attack on Gentry's ideal lattice fully homomorphic scheme, based on the adaptive Hidden Parallelepiped Problem. We proposed two solutions, one of them exposing the secret in O(n log 3 D) adaptive calls to the decryption oracle. It would be interesting to see an implementation, and to analyze the possibility of determining points inside the parallelepiped with help of homomorphic operations. We point out that the gap between theoretical and practical analysis is large. For instance, evidence in appendix B suggests that finding a new direction costs less than 10 parameter searches, with good probability, thus relaxing a log(D) factor. It is also safe to assume that the complexity of Bounces is a great deal lower than O(n log D), since each search starts from points progressively away from the origin. With this, we estimate that for an application of the scheme in n = 334 (safe against lattice reduction attacks) of depth d, the number of decryption queries is about 2500d 2 to recover a secret key with good probability. It would be of interest to apply this attack to other lattice based encryption schemes with smaller parameters.

Introduction

Is it possible to avoid betrayal in a hierarchic scenario? Imagine a chain of users equipped with a public-key encryption scheme, where high level users can decrypt ciphertexts intended to all lower level users in the chain. This is trivial to construct using any public-key cryptosystem E: just transfer low-level secret-keys to upper levels following the hierarchy. The evident drawback is that high-level users can betray their children and distribute their secrets to other parties. Using a proxy re-encryption procedure or multiple trapdoors is hence preferred, because parents do not have direct knowledge of their children's secrets. A proxy re-encryption scheme is a cryptosystem that allows a public transformation of ciphertexts such that they become decryptable to an authorized party. This is a particular case of a cryptosystem allowing delegation of decryption, which finds applications in mail redirection, for instance. In this Chapter, we give a solution to the betrayal issue in another perspective, relying on a new property we found in the well-known modified NTRU encryption scheme, and which we refer to as "Excalibur". Basically, this feature allows to generate a secret-key that decrypts encryptions under multiple public-keys and behaves like a regular key of the cryptosystem.

The Excalibur Property. A public-key encryption scheme E = (Keygen, Enc, Dec) with plaintext space M has the Excalibur property if there is an algorithm that allows two users Alice and Bob with key-pairs (sk old A , pk old A ) and (sk B , pk B ) respectively to forge a new key-pair for Alice (sk A , pk A ) such that -Alice's key sk A can decrypt ciphertexts in Enc(pk A , M) ∪ Enc(pk B , M).

-Bob cannot decrypt ciphertexts in Enc(pk A , M).

-Alice cannot generate a secret-key sk � B that is able to decrypt ciphertexts in Enc(pk B , M) but is not able to decrypt ciphertexts in Enc(pk A , M) (i.e. she cannot give away access to Bob's secret without leaking her own).

The intuition is that sk A is a one-way expression of (sk old A , sk B ). As Alice owns decryption rights over Bob's ciphertexts, this can be seen as automatic proxy reencryption, in the sense that the re-encryption procedure is the identity. The idea is to "glue" Alice and Bob secret-keys together, resulting on a master key given to Alice. This Excalibur master key can be separated into factors only by Bob, hence the name of the feature: Bob plays the role of young Arthur, who is the only man in the kingdom able to separate Excalibur from the stone. Moreover, Alice can glue her key to an upper user's key, who inherits decryption over Bob's ciphertexts, and so forth, and if we suppose that no user is willing to give away own secrets, this achieves automatic N -hop re-encryption and sets a hierarchic chain.

We therefore have a scheme in which a single private-key can decrypt messages under multiple public-keys, and we will see that if a group of low-level users cheated in the joint key generation of this private-key (in order to sabotage or harden decryption), the secret-key holder may be able to trace it back to the wrongdoers, by simply testing decryptions and looking at the private-key's coefficients. In a sense, this is the inverse setting of a public-key traitor tracing scheme, where there are multiple secret-keys associated with a single public-key, and such that if a group of users collude in creating a new private-key achieving decryption with the public-key, it is possible to trace it to its creators, see for instance [START_REF] Boneh | An Efficient Public Key Traitor Tracing Scheme[END_REF].

Three main advantages of this property over the trivial transfer of keys, over re-encryption schemes and over multiple trapdoor schemes are (i) there are no extra space or time costs: as soon as the keys are blended, the resulting key-pair acts as a fresh one and no ciphertext modification is necessary, (ii) our key generation procedure can be plugged directly into the (multikey) NTRU-based fully homomorphic encryption scheme, supporting homomorphic operations and automatic N -hop re-encryption and (iii) a user with a powerful key does not need to handle a "key ring" of secret-keys of her children; her key-pair (sk, pk) acts as a regular NTRU key. In contrast, the classical proxy re-encryption scenario is more flexible; a user can agree a decryption delegation at any moment to any user, whereas in our proposal once the keys are blended, modifications in hierarchy involve new key generations. This is why our proposal is more suitable to a rigid pre-defined hierarchic scenario.

Modified NTRU. The NTRUEncrypt cryptosystem is a public-key encryption scheme whose security is based on short vector problems on lattices. Keys and ciphertexts are elements of the polynomial ring Z[X]/�φ(x)� where φ(x) = x n -1, and coefficients are considered modulo a large prime q. This scheme was defined in 1996 by Hoffstein, Pipher, Silverman and gained much attention since its proposal because of its efficiency and hardness reductions. In [START_REF] Stehlé | Making NTRU as Secure as Worst-Case Problems over Ideal Lattices[END_REF], Stehlé and Steinfeld provided modifications to the scheme in order to give formal statistic proofs, which ultimately led to support homomorphic operations with an additional assumption in [START_REF] López-Alt | On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[END_REF]. Among these modifications, we highlight the change of ring and parameters restrictions: R = Z[x]/�φ(x)� where now φ(x) = x n + 1, n is a power of not want to trust individual secrets to each other. To achieve this joint key generation, we rely on multiparty protocols in the polynomial ring R q = F q [x]/(x n + 1) in both the secret and shared setting. To this end, we describe two multiplication protocols between mutually distrusting Alice and Bob:

1. Secret inputs setting : Alice and Bob hold f, g ∈ R q respectively. They exchange random polynomials and at the end Alice learns f g + r ∈ R q where r is a random polynomial known by Bob, and Bob learns nothing.

2. Additively shared inputs setting : Alice and Bob hold f A , g A ∈ R q and f B , g B ∈ R q respectively such that f = f A + f B and g = g A + g B . They exchange some random polynomials, and at the end Alice and Bob learn π A , π B respectively such that π A + π B = f g ∈ R q . Revealing π A or π B to each other does not leak information about the input shares.

Let us illustrate how to use these protocols in Alice's key generation. Suppose that Bob keys were previously generated. Generating Alice's secret-key is fairly easy: Informally, if β ∈ R q is Bob's secret-key, let Alice and Bob sample random α A , α B ∈ R q respectively, with small coefficients. They perform the first protocol on inputs f = α A and g = β, and Bob chooses r = α B β. At the end, Alice learns γ = α A β + α B β = αβ ∈ R q , and Bob learns nothing. One may stop here and let Alice compute her public-key pk A = 2hγ -1 ∈ R q for suitable h ∈ R q , but she may cheat and generate other NTRU fresh keys (sk A , � pk � A ) and then distribute freely Bob's secret γ. This is why the public-key is also generated jointly, and moreover, the public-key will be generated before the secret-key, this way Alice must first commit to a public-key pk A .

Fully Homomorphic Encryption. Fully Homomorphic Encryption schemes allow public processing of encrypted data. Since Gentry's breakthrough in [START_REF] Gentry | Computing on Encrypted Data[END_REF][START_REF] Gentry | A Fully Homomorphic Encryption Scheme[END_REF][START_REF] Gentry | Fully Homomorphic Encryption Using Ideal Lattices[END_REF], there has been considerable effort to propose FHE schemes that are efficient [HS14, BGH13b, GHS12c, GHS12b, GHS12a, GHPS12, GH11b, ASP14, ASP13], secure [GH11a, BV11b, BV11a, Bra12, ASP14], and having other properties [START_REF] Brakerski | Fully Homomorphic Encryption from ring-LWE and Security for Key-Dependent Messages[END_REF][START_REF] Gentry | Fully Homomorphic Encryption Without Squashing Using Depth-3 Arithmetic Circuits[END_REF][START_REF] Brakerski | Packed Ciphertexts in LWE-Based Homomorphic Encryption[END_REF][START_REF] Gentry | Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based[END_REF]. We highlight the existence of Multikey FHE schemes, in which some ciphertexts can only be decrypted with the collaboration of multiple key-holders. This was first constructed in [START_REF] López-Alt | On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[END_REF], and it reduces the general multiparty computation problem to a particular instance. We encourage the reader to see the latest version of this article.

All of the above schemes have a PPT encryption algorithm that adds random "noise" to the ciphertext, and propose methods to add and multiply two ciphertexts. With these methods they give an (homomorphic) evaluation algorithm of circuits. The noise in ciphertexts grows with homomorphic operations (especially with multiplication gates) and after it reaches a threshold, the ciphertext can no longer be decrypted. Thus, only circuits of bounded multiplicative degree can be evaluated: these schemes are referred to as leveled FHE schemes. Gentry proposed a technique called "bootstrapping" that transform a ciphertext into one of smaller noise that encrypts the same message, therefore allowing more homomorphic computations. This (algorithmically expensive) technique remains the only known way to achieve pure FHE scheme from a leveled FHE scheme. In order to do this, the decryption circuit of the leveled scheme must be of permitted depth and the new scheme relies on non-standard assumptions.

Nevertheless, leveled FHE schemes with good a priori bounds on the multiplicative depth do satisfy most applications requirements, see [YSK + 13]. We suggest that the use of our protocols in the LATV scheme use the leveled version, but as pointed out in [START_REF] López-Alt | On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[END_REF], the scheme can be transformed into a fully homomorphic scheme by boostrapping and modulus reduction techniques, both adaptable to the use of Excalibur keys.

FHE and bidirectional multi-hop re-encryption paradigm. It has been widely mentioned (for instance in the seminal work [START_REF] Gentry | A Fully Homomorphic Encryption Scheme[END_REF]) that a fully homomorphic encryption scheme allows bidirectional multi-hop proxy re-encryption. The argument is similar to the celebrated bootstrapping procedure: let c be an encryption of m using Bob's secret-key s B . First publish τ , an encryption of s B under Alice's public-key, then homomorphically run the decryption circuit on c and τ , the result is an encryption of m decryptable by Alice's secret-key. However, we point out that this is pure re-encryption only if Alice never gets access to τ , since she can decrypt and learn s B directly. This restriction tackles the pure re-encryption definition, and in light of this the NTRU-based FHE scheme with the Excalibur property may be a starting point to clear out this paradigm (as it satisfies the pure definition, but fails to be bidirectional).

Our contributions. In this chapter, we propose a key generation protocol that allows to glue NTRU secret-keys together in order to equip a hierarchic chain of users, such that a given user has the ability to decrypt all ciphertexts intended to all lower users in the chain, and she cannot give away secrets without exposing her own secret-key. This procedure can be plugged directly into the (multikey) FHEscheme by Lopez-Alt et al. , it is compatible with homomorphic operations and has no space costs or ciphertext transformations, and important users do not have to handle key rings. To achieve this, we describe two-party computations protocols in cyclotomic polynomial rings that may be of independent interest. We base the semantic security on the hardness of RLWE and DSPR problems, and the semihonest and malicious security in a new hardness assumption which we call "Small Factors Assumption". In this assumption we define the "Small GCD Problem" and we show that any algorithm solving this problem can be used to break the semantic security of the modified NTRU scheme.

Preliminaries

Notation

Let q be a large prime. We let the set {-�q/2�, . . . , �q/2�} represent the equivalence classes of Z/qZ, and both notations [x] q or x mod q represent modular reduction of x into this set. For a ring A, A × stands for the group of units (or invertible elements) of A, �a� or (a) is the ideal generated by a ∈ A. Also, we denote by F k the finite field of k elements, for k = q l ∈ Z. The notation e ← ξ indicates that the element e is sampled according to the distribution ξ, and e R ← -S means that e was sampled from the set S using the uniform distribution. Similarly, A R ⊂ S means that each a ∈ A was sampled uniformly at random on S. Finally, let R def = Z[x]/(x n + 1), we identify an element of R with its coefficient vector in Z n , and for v(x) = v 0 +v 1 x+• • •+v n-1 x n-1 in R, we denote by ||v|| ∞ , ||v|| 2 its l ∞ , l 2 norm respectively.

The quotient ring R q

Operations in the modified NTRU scheme are between elements of R q def = F q [x]/(x n + 1), the ring of polynomials modulo Φ 2n (x) = x n + 1 (i.e. Φ 2n is the 2n-th cyclotomic polynomial) and coefficients in F q , where n is a power of 2 and q is a large prime. Addition and multiplication of polynomials are performed modulo Φ 2n (x) and modulo q. The ring R q is not a unique factorization domain, in fact, small units of this ring serve as NTRU secret-keys. The Chinese remainder theorem shows that the group of units is large, and thus y = ru ∈ R q where r ∈ R q is a random element and u is a unit is a good masking of u: it is unfeasible to recover u from y for large n. Let us collect some lemmas related to the set of invertible elements of R q . Lemma 4.2.1. Let q ≥ 3 be a prime number and Φ n (x) ∈ Z[x] be the n-th cyclotomic polynomial. Then Φ n (x) is irreducible over F q if and only if q is a generator of the group (Z/nZ) × . Lemma 4.2.2. If n > 2 is a power of 2, then (Z/2nZ) × is not cyclic and therefore Φ 2n (x) = x n + 1 is not irreducible over F q . In addition, x n + 1 decomposes into l distinct irreducible factors over F q for prime q ≥ 3:

Let (φ i ) l i=1 ⊂ F q [x] respectively such that x n + 1 = � l i=1 φ i (x) over F q .
Then we have a ring isomorphism π :

F q [x] (x n + 1) → l � i=1 F q [x] (φ i (x)) where F q [x] (φ i (x)) � F q deg φ i . Corollary. Card(R × q ) = � l i=1 � q deg φ i -1 � .
The proofs are straightforward. In the original modifications in [START_REF] Stehlé | Making NTRU as Secure as Worst-Case Problems over Ideal Lattices[END_REF], q = 1 mod 2n and hence x n + 1 splits into n distinct linear factors, yielding Card(R q ) × = (q -1) n .

Modified NTRU encryption

Enc(pk, m): Sample polynomials s, e ← ḠK . For message m ∈ {0, 1}, output c = m + 2e + s • pk mod q.

Dec(sk, c): For a ciphertext c ∈ R q , compute µ = c • sk ∈ R q and output m = µ mod 2.

The multikey property

We describe a decryption property that states that one can decrypt a ciphertext with the secret-key required for decryption, or a small polynomial multiple of it.

Lemma 4.3.1. Let (f, h) ← Keygen(1 κ ), m ∈ {0, 1} and let c ← Enc(h, m). Let θ ∈ R be a M -bounded polynomial satisfying θ mod 2 = 1. If M < (1/72)(q/n 2 K 2 ), then Dec(f, c) = Dec(θ • f, c) = m.
Proof: There exist K-bounded polynomials s, e such that c = m + hs + 2e. Decryption works since

[f c] q = [f m + f hs + 2f e] q = [f m + 2gs + 2f e] q
and supposing there is no wrap-around modulo q in the latter expression, we have [f c] q mod 2 = f c mod 2 = m. If we replace f by θ • f and try to decrypt, we have θf c = θf m + 2θgs + 2θf e, and then again, if there is no wrap-around modulo q (i.e. if M is small enough), θf c mod 2 = m is verified. To ensure that there is no wrap-around modulo q, one has to give an a priori relation between K, n and M . In fact, using corollary 4.2.3, we have ||gs|| ∞ < nK 2 and ||f e|| ∞ < n(2K + 1)K, and thus ||f c|| ∞ < 2nK 2 + 2n(2K + 1)K + K.

Decryption using f is correct if 2nK 2 +2n(2K +1)K +K < q/2, and decryption using θf is correct if nM (2nK 2 + 2n(2K + 1)K + K) < q/2. Therefore, decryption using f is ensured by 36nK 2 < q/2, decryption using θf is ensured by 36n 2 M K 2 < q/2. � Corollary (The multikey property). Let (f 1 , h 1 ) and (f 2 , h 2 ) be valid keys, m 1 , m 2 ∈ {0, 1} and let

c 1 ← Enc(h 1 , m 1 ), c 2 ← Enc(h 2 , m 2 ). Let f ← f 1 • f 2 ∈ R q . Then Dec( f , c 1 ) = m 1 , Dec( f , c 2 ) = m 2
provided that K is small enough.

Proof: Apply 4.3.1 with f = f 1 and θ = f 2 for the first equation and f = f 2 , θ = f 1 for the second. �

We can of course extend this facts to show that a highly composite key of the form f = � l i=1 f i ∈ R q can decrypt all messages decryptable by any of f i : Just apply lemma 4.3.1 with f = f i and θ = f /f i , provided good a priori bounds: In fact || f || ∞ ≤ n l-1 K l , therefore decryption with this key is ensured by n l-1 K l � q. their analysis, our system (n = 2m) escapes the polynomial-time scope. Let us write the system in clear:

∀i ∈ {0, . . . , n -1}, ||a i || ∞ < K and ||b i || ∞ < K,                c 0 = a 0 b 0 -a 1 b n-1 -a 2 b n-2 -. . . -a n-1 b 1 , c 1 = a 0 b 1 + a 1 b 0 -a 2 b n-1 -. . . -a n-1 b 2 , c 2 = a 0 b 2 + a 1 b 1 + a 2 b 0 -. . . -a n-1 b 3 , . . . c n-1 = a 0 b n-1 + a 1 b n-2 + a 2 b n-3 + . . . + a n-1 b 0 .
As this is an under-determined system, the linearization Z i,j = a i b j results in a linear system with too many degrees of freedom to select the correct solution; this is not better than guessing in the initial quadratic system. On the other hand, this system presents cyclic anti-symmetry, which one could exploit to find a solution. However, it is not clear how to use the additional symmetry to make progress in finding solutions (this is also the case when trying to solve lattice problems in the particular case of ideal lattices).

From another point of view, if nothing was required from a, b, we are given an element c and a test routine T : R → {0, 1} that outputs 1 if the input is b and 0 otherwise (in our scenario, the test routine is to simply try out the extracted key β = b via decryptions). An algorithmic issue arises again: There is a degree of freedom of one ring unit in the small factors problem, and an algorithm must exclude trivial factorizations of c: for instance, if nothing was required for a and b, the size of the candidates list for (a, b) is at least the number of units of R q , since it contains all pairs (a, b) = (cu, cu -1 ) for invertible u ∈ R q . Using the K-boundedness of a, b, the list is to be reduced rejecting all incorrect pairs. To optimize up the rejection, we suggest a study of the distribution χ def = ( ḠK ) -1 , which samples e according to ḠK and then outputs e -1 ∈ R q if e is invertible.

If a, b were sampled using another distribution, distinguishing c = a • b ∈ R q from random may be achievable. For instance, if a, b coefficients were sampled with Bernoulli trials, we detected some linear correlation between the coefficients of c in this case. See appendix C.

Two-party multiplication protocols in R q

In this section we introduce two protocols to jointly achieve multiplication in the quotient ring between two mutually distrusting parties. We distinguish two settings, the "secret inputs" (which is the classical MPC scenario) and the "shared inputs" which supposes that both parties have additive shares of some elements. The latter setting, however, can be regarded as a classical MPC computing a quadratic expression of the inputs.

Secret inputs setting

Alice and Bob hold f ∈ R q and g ∈ R q respectively. The following protocol allows them to multiply these elements: Alice will learn f g +r ∈ R q where r is a polynomial chosen by Bob. The reason of this is that if Alice learns f g, she can compute g = f g/f . The utility of this protocol may seem questionable, in the sense that it transfers Alice's obliviousness from g to r, nevertheless we will see that careful selection of r will allow the two parties to generate Alice's NTRU keys. This protocol is inspired on [START_REF] Atallah | Secure multi-party computational geometry[END_REF], where authors propose a protocol to compute scalar products as a building block to perform much more complex functionalities. It is detailed in algorithm 11.

Algorithm 11 Excalibur -TMP Require: Alice holds f ∈ R q , Bob holds g ∈ R q . Let p, m be public integers. Ensure: Alice learns f g + r ∈ R q where Bob knows r ∈ R q 1: Alice generates m random polynomials {f 1 , . . . ,

f m } R ⊂ R q such that � m i=1 f i = f . 2: Bob generates m random polynomials {r 1 , . . . , r m } R ⊂ R q and r def = � m i=1 r i . 3: for i = 1, . . . , m do 4:
Alice generates a secret random number k, 1 ≤ k ≤ p.

5:

Alice generates random polynomials v 1 , • • • , v p , sets v k = f i , and send all these polynomials to Bob.

6:

Bob computes the products and masks them: For all j = 1, . . . , p z i,j = v j g + r i .

7:

Alice extracts z i,k = f i g + r i from Bob with a 1-out-of-p OT protocol. 8: end for 9: Alice computes � m i=1 z i,k = f g + r.

Note that throughout the protocol, Bob always computed products of random polynomials, and to guess the value of f he has to perform ≈ p m additions. Lemma 4.5.1. If it is not feasible to compute O(p m ) additions in R q , and if the RLWE assumption holds for q, φ(x) = x n + 1 and uniform χ over R q , TMP securely outputs f g + r to Alice and r to Bob in the presence of semi-honest parties.

Proof: In this model, both parties follow exactly the protocol but try to learn as much information as possible from their transcript of the protocol. Let view A , view B be the collection of learned elements by Alice and Bob respectively. We have that view B contains only polynomials v (i) j indistinguishable from uniform (since they were sampled by semi-honest Alice), and these elements are independent from Bob's input, samplings, and computations. Therefore, to learn f , he needs to perform ≈ p m additions. On the other hand Alice wants to learn g or r and she only has m pairs of the form (f i , f i g + r i ) (and the output which is the component-wise sum of these), which by the RLWE assumption are indistinguishable from (f i , u i ) for uniform u i . In other words, the view of each adversary contains her input, her output, and a list of polynomials indistinguishable from random by construction. We can construct simulators S A , S B of protocol TMP for both parties, and it follows immediately that the views of Alice and Bob are indistinguishable from the simulators. � Remark: If both parties are malicious but they do not want to leak their own inputs, at the end of the protocol they learn nothing about the other party's input.

This holds because Alice may deviate from the samplings, but she sends pm random elements computationally hiding f , Bob will process these pm elements (deviating as much as he wants from the actual required computation) and send m elements computationally hiding g and r to Alice via the OT protocol, thus Bob learns nothing. In this case, deviations from the protocol may cause the output to be incorrect. We do not worry much about this as soon as Bob's input is safe, since we will see that it will result in invalid keys for Alice and the honest party will know that the other is malicious.

Shared inputs setting

In this setting, two parties share two elements of R q additively, and they want to compute shares of the product of these elements. Let Alice and Bob hold x A , y A and x B , y B respectively such that x = x A + x B and y = y A + y B .

We propose a protocol SharedTMP, at the end of which Alice and Bob will learn additive shares π A , π B respectively of the product:

π A + π B = xy ∈ R q . Algorithm 12 Excalibur -SharedTMP Require: Alice holds (x A , y A ) ∈ R 2 q , Bob holds (x B , y B ) ∈ R 2 q such that x = x A + x B , y = y A + y B Ensure: Alice learns π A ∈ R q , Bob learns π B ∈ R q such that π A + π B = xy 1: Alice samples r A R ← -R q , Bob samples r B R ← -R q 2:
Alice and Bob perform TMP(x A , y B ) using Bob's randomness r B , thus Alice learns u A = x A y B + r B and Bob learns nothing. 3: Bob and Alice perform TMP(x B , y A ) using Alice's randomness r A , thus Bob learns u B = x B y A + r A and Alice learns nothing. 4: Alice computes the share

π A = x A y A + u A -r A ∈ R q 5: Bob computes the share π B = x B y B + u B -r B ∈ R q Note that π A + π B = (x A + x B )(y A + y B ) = xy.
Since they only communicate in steps 2 and 3, security is reduced to two independent instances of the TMP protocol. We also have the following observation: 4.6. Excalibur key generation Lemma 4.5.2. Let Alice and Bob perform SharedTMP on some non-trivial inputs, learning at the end π A and π B respectively. Even if Alice reveals π A to Bob, he cannot deduce Alice's inputs.

Proof: This follows directly from the randomness of u Ar A . �

Excalibur key generation

We present our main contribution, three protocols Keygen pk , Keygen sk and a validation protocol, to be performed by Alice and Bob that will generate the public and the (blended) private-key of Alice, in that order. Let us first give an informal outline of the protocol. Bob has already generated his key-pair (β, 2hβ -1 ) ∈ R q × R q . They want to compute a new key-pair (sk A , pk A ) = (αβ, 2g(αβ) -1 ) ∈ R q × R q for Alice, which correctly decrypts encryptions under pk B since it contains the factor β.

-Excalibur generation of pk A 1. They share polynomials α, g, r of R q additively, such that α = 1 mod 2.

2. They perform SharedTMP to obtain shares of αr, gr. Alice reveals her shares to Bob.

3. Bob computes 2(gr) • (αr) -1 • β -1 = 2g(αβ) -1 in R q and broadcasts the result.

-Excalibur generation of sk A (to be performed after publication of pk A )

1. Let α A + α B = α denote the same additive sharing of α than in the previous steps, where Alice holds α A and Bob holds α B . Alice and Bob perform TMP on entries α A , β respectively, and Bob chooses r = α B β as the randomness in the protocol.

2. At the end of the protocol, Alice learns α A β + r = αβ = sk A ∈ R q , and Bob learns nothing.

-Validation protocol : Alice and Bob run tests to be convinced that the keys are well formed and behave as claimed.

The protocols are described formally in algorithms 13, 14, 15 and 16. If protocol 13 was carried out properly, a ciphertext encrypted with pk A is correctly decrypted by any secret-key having the factor αβ and reasonable coefficient size. Remark that in step 2, Bob received the element z = α • r: this does not allow to deduce a functional equivalent of the secret-key αβ, since r has large coefficients. Also, chances are overwhelmingly high that this element is in fact invertible in view of section 4.2.2.

Algorithm 13 Excalibur -Keygen pk

Require: Bob already has his own key-pair (sk B , pk B ) = (β, 2hβ -1 ) ∈ R q × R q . Ensure: A public-key for Alice pk A 1: Alice and Bob sample random shares of elements in R q :

-Alice samples Alice reveals her shares, thus Bob learns z, w. 3: Bob checks: If z is not invertible in R q , restart the protocol. 4: Bob computes 2w(zβ) -1 = 2g(αβ) -1 and publishes it as pk A , along with a NIZK proof showing that z, w come from step 2 and that pk A is well-formed. Once the keys are generated, they must pass a series of decryption and a wellformedness test. This is described in algorithms 15 and 16. First, Alice checks if her new secret-key works as expected, and then she convinces Bob, via a game of decryptions that she is indeed capable of decrypting ciphertexts encrypted under Proof: Let us focus first in Bob's chances on learning α (or a functional equivalent of the form θ • α for small θ ∈ R q ). Recall that

s A ← ḠK , r A R ← -R q , g A ← ḠK -Bob samples s B ← ḠK , r B R ← -R q , g B ← ḠK Let α = 2(s A + s B ) + 1, r = r A + r B , g = g A + g B denote
               pk B = 2hβ -1 , pk A = 2g(αβ) -1 , z = α • r, w = g • r, α = 2(s A + s B ) + 1.
Let us focus on Bob's view of the protocol:

V = {(s B , r B , g B , z B , w B , z A , w A , β, pk B ), pk A , α • r, g • r} ⊂ R q .
What Bob is curious about: Any element of the set

U = {α, g, r, s A , g A , r A } ⊂ R q .
The parentheses in V indicate that he sampled or received the elements contained, and the rest are results of joint computation. The knowledge of any element in U allows Bob to deduce Alice's secret-key α, and only the last three elements pk A , α • r, g • r of V depend on elements in U . Thus, extracting α is equivalent to solve the following system of equations in the unknowns (X, Y, Z) = (α, r, g): Let us now focus in Alice chances of learning Bob's secret.

     b 1 = XY, b 2 = ZY, b 3 = ZX -1 , where b 1 = α • r, b 2 = g •
Alice's view of the protocol:

W = {(s A , r A , g A , z A , w A ), pk B , pk A , αβ} ⊂ R q .
What Alice is curious about: Any element of the set

Q = {α, β, h, s B , {w B , z B }, {w, z}}.
First, extracting α or β directly from α • β is exactly the small factors Problem. Using the only three sensitive elements of W , she faces the following system of equations in (X,

Y, Z) = (h, β, α)      a 1 = XY -1 , a 2 = (ZY ) -1 , a 3 = ZY,
where a 1 = pk B /2, a 2 = pk A /2g, a 3 = αβ. After elimination of the third equation since a 3 = a -1 2 , Alice also faces the small GCD problem (actually, mapping Y � → Y -1 , Z � → Z -1 yields to the same gcd problem faced by Bob). � 2. Participates in SharedTMP((2s A , r A ), (2s B +1, r B )) and learns z A , participates in SharedTMP((g A , r A ), (g B , r B )) and learns w A , then sends z A , w A to Bob.

As discussed in section 4. If she uses the correct value of 2s A (i.e. the same as in step 2), she learns the correct output αβ. If she inputs another value x � = 2s A , she does learn a functional equivalent of Bob secret (namely, (x + 2s B + 1)β), but she is not able to decrypt encryptions under the already published pk A , failing the verification procedure.

Malicious Bob, semi-honest Alice

Now suppose the inverse case, where Alice follows the protocol strictly and Bob is protecting β and guessing α, deviating as much as he wants from the protocol but fulfilling (B1) to (B4). We begin by saying that (B3) is unavoidable (unless the presence of a zero-knowledge proof that Bob's polynomials are of the right size), but Alice can tell if Bob overloaded the secret-key αβ simply looking at the coefficients.

Let us now summarize Bob's participation in the key generation:

1. Samples s B ← ḠK , r B R ← -R q , g B ← ḠK .
Trivial sampling may compromise sensible elements as before. He must ensure the randomness of α, r if he wants to protect these elements, and on the other hand Alice will know if he deviates from a K-bounded sampling (just looking at the coefficients in α • β. Therefore, he gains nothing in deviating from a K-bounded sampling. ). As his secret-key contains the factors β and αβ, he can decrypt both Bob's and Alice's ciphertexts. This shows that easy modifications to the protocol allows to generate a chain of users, each one inheriting the previous user decryption rights. From corollary 4.3.1, it is easy to see that the length of such a chain is at most ≈ log(q/nK) to ensure decryptions (this matches the maximum number of keys on the multikey LATV FHE scheme for the same parameters). We point out that intersecting chains are also possible, meaning that a user can glue her secret-keys to two or more upper-level users and even if they collude they are not able to extract his key. This comes from an easy generalization of our Ḡ× K -GCD problem.

Participates in SharedTMP((2s

Plugging in LATV-FHE

Because of the form of an Excalibur key, i.e. (sk, pk) = ( � r i=1 α i , 2g

� r i=1 α -1 i ), the inclusion of our protocols into the Multikey FHE scheme from [START_REF] López-Alt | On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[END_REF] is immediate. The only missing element are the evaluation keys, which can be generated easily by the secret-key holder after the (Excalibur) key generation: they are "pseudo-encryptions" of the secret-key sk under the public-key pk. This achieves a somewhat homomorphic encryption scheme in the chain of users, where in addition they can combine ciphertexts generated by any public-key.

Conclusion

In this Chapter, we proposed a new protocol to generate NTRU keys with additional decryption rights, allowing to form a hierarchic chain of users. We motivated such a procedure because it avoids betrayal naturally, and since it applies to the FHE-NTRU scheme, it may contribute to clear the bootstrapping-like re-encryption paradigm, since it is to our knowledge the first FHE scenario featuring (the pure definition of) proxy re-encryption. In this light, it concurs with other proxy reencryption schemes, as, while being rigid, ciphertext transformation is no necessary at all, since decryption rights are defined in key-generation time. We used two-party computation protocols as building blocks, and relied the semantic security on the well-known RLWE and DSPR assumptions, and security in presence of semi-honest parties on a hardness assumption in cyclotomic polynomial rings.

Introduction

The Brakerski-Gentry-Vaikuntanathan scheme has been praised as the most auspicious in terms of efficiency amongst other homomorphic schemes. Its structure allows to use the corresponding Galois group in order to pack ciphertexts and perform parallel operations in the style of SIMD techniques.

In this Chapter we provide a description and a working implementation of the Brakerski-Gentry-Vaikuntanathan homomorphic scheme, using C++ with the multiple precision library GMP and additional support to complex numbers. In order to handle ciphertext noise, we use the scale and modulus switching techniques. This chapter is motivated by the article [START_REF] Costache | Which Ring Based Somewhat Homomorphic Encryption Scheme is Best?[END_REF], where authors compare ring-based homomorphic schemes. In an appendix, they list security parameters; we follow these suggestions in our implementation.

The well-known HElib "Homomorphic Encryption library" (https://github. com/shaih/HElib) also implements BGV homomorphic scheme. Of course, this implementation with highly optimized routines outperforms ours.

The scheme

We present here a full description of the BGV homomorphic scheme. First let us precise the ring framework.

Parameters

Consider the following parameters and plaintext/ciphertext spaces.

N

-A power of 2. R -The cyclotomic ring Z[x]/(x N + 1). L -The desired homomorphic depth. p ∈ N -The plaintext modulus. R p -The plaintext space Z p [x]/(x N + 1) p 0 , . . . , p L-1 -L primes s.t. p i ≡ 1 mod 2N q 0 , . . . , q L-1 -The "chain of moduli". For k from 0 to L -1, q k = � k j=0 p j . R q -The polynomial ring Z q [x]/(x N + 1), for any q. This is the chain of ciphertext spaces.

For our implementations, p ∈ {2, 101, 2 32 } (binary, small alphabet and 32-bit plaintext space). In the scheme, a message must be encoded into one or several plaintexts m ∈ R p � (-p/2, p/2] N . Before defining decryption, let us slightly jump ahead. Fresh ciphertexts are elements of R q L , and upon multiplication, they jump to smaller ciphertext spaces. This way, the scheme operates in L -1 levels of "decreasing" polynomial cyclotomic rings as follows :

'Fresh' ciphertext space = R q L-1 -→ R q L-2 -→ • • • -→ R q 1 -→ R q 0 .
Ciphertexts in the last ring cannot be used to multiply, however they can still be used in homomorphic additions. This chain of moduli allows therefore to perform L -1 multiplications.

More precisely, ciphertexts consist in a pair of polynomials in these spaces, along with two tags, one indicating the level of this ciphertext and another one representing an approximation of the noise. See 5.2.3 below.

An important remark is that the primes p 0 , . . . , p L-1 are chosen to satisfy p i ≡ 1 mod 2N , implying the existence of a primitive 2N -th root of unity in Z p i (this will prove helpful in order to compute number theoretic transform of polynomials). As suggested in [START_REF] Costache | Which Ring Based Somewhat Homomorphic Encryption Scheme is Best?[END_REF], we require in addition that p i ≡ 1 mod p, in order to simplify the scaling operation (and slightly control noise growth).

Key Generation

-sampling from Z p [x]/(x N + 1)
Toward defining key generation, four random samplings of elements in R q are defined: U q -The uniform distribution on R q � {-q/2, . . . , q/2 -1} N . HWT (h) -Samples a Z N vector with h non-zero entries in {-1, +1}.

ZO(ρ) -Samples a Z N vector, where each coordinate is 1 or -1 with probability ρ/2 each and is 0 with probability 1ρ. DG q (σ 2 ) -Let N (0, σ 2 ) denote the Gaussian distribution on real numbers, with zero-mean and variance σ 2 . DG q (σ 2 ) draws a real vector from N (0, σ 2 ) N , rounds it to the nearest integer vector, and outputs the result modulo q.

With this, the key generation procedure outputs a sparse polynomial as the secret-key and a pair of uniform-looking elements of R q L-1 as the public-key. See algorithm 17. a ← U q L-1 .

Algorithm 17 BGV -Key Generation

5:

e ← DG(σ 2 ) � σ 2 = 1.3 is suggested in [CS16]. 6: Set b ← [a • sk + pe] q L-1 7:
Output secret key sk and public key pk = (a, b)

8: end function

Keys are therefore of the form (s, (a, b)) ∈ R p × R 2 q L-1 such that bsa is a polynomial with small coefficients and equivalent to 0 modulo p.

Encryption and decryption

Ciphertexts are of the form ((c 0 , c 1 ), ν, t) ∈ R 2 × R × [0, L]: (c 0 , c 1 ) is the ring gibberish, ν is a bound for the noise of the ciphertext and t indicates the multiplication level. Therefore, (c 0 , c 1 ) ∈ R qt . To encrypt a message m ∈ R p , do as described in algorithm 18.

Algorithm 18 BGV -Encryption and Decryption

1: function Enc(pk, m ∈ R p )

2:
Define v, e 0 , e 1 , c 0 , c 1 ∈ R 3:

v ← ZO(ρ) � ρ is not important, 0.5 is suggested

4:

e 0 ← DG q L-1 (σ 2 )

5:

e 1 ← DG q L-1 (σ 2 )

6: This indeed defines ciphertext multiplication, but fails to meet the required FHE compactness as ciphertexts (and decryption circuits) grow after each product.

c 0 ← [b • v + p • e 0 + m] q L-1 7: c 1 ← [a • v + p • e 1 ] q L-
To overcome this, authors in [START_REF] Brakerski | Fully Homomorphic Encryption Without Bootstrapping[END_REF] propose a relinearization procedure. This needs the publishing of circular ciphertexts, somehow encrypting sk 2 . This public information looks a list of public keys, but for whom the attribute b is not exactly a valid ciphertext, but "almost" encryptions of the new key "sk • sk" in base-T decomposition for some T . To see how to generate these lists, see algorithm 19.

Algorithm 19 BGV -Key-Switching Procedure for i = 0 to θ -1 do � Let θ = �log T (q L-1 )� 3:

a i ← U q L-1
4:

e ← DG q L-1 (σ 2 )

5:

b i ← [a i • sk + p • e i + T i • sk � ] q L-1 6:
end for

c 1 ← d 1 + � d 2,i • a i 5:
ν � = ν + B(t)

6:

Output ciphertext c = (c 0 , c 1 , t, ν � ) � SwitchKey does not modify the level t.

7: end procedure

The additive noise depends on the level:

B(t) = 8 √ 3 pσN T �log T q t �
There is a common confusion between this operation, called Key Switching and Modulus Switching. They are independent: modulus switching is a noise management technique, based on the fact that two ciphertexts can be just multiplied, or they can be translated into another ciphertext space via scaling and then be multiplied, with smaller error growth (see the latter equation). In our implementation, we adopt the scaling variant proposed in [START_REF] Costache | Which Ring Based Somewhat Homomorphic Encryption Scheme is Best?[END_REF], in which an auxiliary modulus Q is introduced. This operation aims to reduce noise/modulus ratio, and as a positive side effect it reduces ciphertext sizes. This implies that, somehow counter-intuitively, multiplications near the end of the circuit take considerably less time.

BGV Homomorphic operations

With these procedures we are ready to describe how to perform homomorphic operations. See algorithms 20 and 21.

Algorithm 20 BGV -Homomorphic Operations 1: procedure AddCipher(cipher a,cipher b) a ←ReduceLevel(a, t) Let P = Q/q t 4:

For i = 1, 2 compute small δ i such that � δ i = -c i mod P δ i = 0 mod p

5:

Define c � 0 ← (c 0 + δ 0 )/P, c � 1 ← (c 1 + δ 1 )/P 6:

and ν � ← ν/P + B scale � B scale is an additive global constant.

7:

Output ciphertext c � ← (c � 0 , c � 1 , t, ν � ) 8: end procedure --------1: procedure Scale(cipher c, t out ∈ N)

2:

Define c � ← c c � 0 ← c 0 mod q t � 7:

c � 1 ← c 1 mod q t � 8: c ← (c � 0 , c � 1 , t � , ν) 9:
Output c � 10:

end if 11: end procedure

Implementation

We programmed the above procedures in C++ with the gmp large numbers library. As figure 5.3 display, we implemented various classes. We distinguish the cryptography layer (two top floors) and the ring arithmetic layer (first and second floors).

params.h

FFTMul.h

Ring.h Sampling.h key.h cipher.h switchingkey.h BGV.h

Math Layers

The basic bricks aim to support necessary operations in the polynomial ring R q . We define N as a (global, constant) power of 2 and M = 2N , but use the modulus q as an argument to our functions, since it decreases from one level to another. We propose four bricks params.h, Ring.h, Sampling.h and FFT.h.

Overall parameters

The most basic layer contains all parameters for the implementation. Even if bricks are portable, we regroup all parameters in params.h for testing different sets thereof. This way, to instance the first set of parameters provided in fined as the sum of k independent, uniformly distributed random variables in (0, 1). The mean and variance of an Irwin-Hall distribution are k/2 and k/12 respectively, and the probability density function approaches the normal p.d.f. as k grows. We used a value of k according to the desired variance σ 2 , i.e. k = 12 • σ 2 , with proper scaling and translating.

Fast polynomial multiplication

In FFTMul.h, we implement Cooley-Tukey's recursive algorithm to compute the FFT's of polynomials, in time O(N log N ). The complex numbers are defined with the mpc.h library, and we fix a precision in bits in params.h, which grows with the input size of coefficients. See algorithm 22. The Free statements in the algorithm are advised in order to avoid memory allocation problems. To soften the butterfly, we omitted the product ω • ω n , instead we precomputed all 2N -th roots of unity and choose ω using the relation ω k n = ω 2N k/n 2N .

Cryptography layers

Key object

The class key.h has three attributes and three member functions: RecFFT(n/2, a 0 , y 0 )

9:
RecFFT(n/2, a 1 , y 1 ) 10:

(Free a 0 , a 1 ) 11:

ω ← 1 12:

for k = 0 to n/2 -1 do � Butterfly (Free y 0 , y 1 , ω)

Performance

We selected sets of parameters from [START_REF] Costache | Which Ring Based Somewhat Homomorphic Encryption Scheme is Best?[END_REF] and performed an evaluation of different depth-L circuits. This tests were run on a desktop computer running at 2.70 GHz.

A consideration about the choice of the degree N : For each suggested value of N , we chose the smallest power of 2 greater than the given value. Since our polynomial product runs in O(N log N ), allowing smaller values of N can fasten the algorithms in a factor of at most 2. In view of this, we have included the factor α = (value of N )/(suggested value of N ).

Conclusion

In this Chapter we described our implementation of the BGV fully homomorphic scheme. We correctly evaluated circuits up to depth 30, and we acknowledge that other implementations (such as HElib) outperform ours by far. In contrast, we did not analyze the mean timings with respect to packs of ciphertexts or depth level: We only provided timings of the worst case (i.e. fresh ciphertext multiplication with no packing). However, with this analysis and considering optimization of our functions, our timings should be divided by a factor at least the number of packed ciphertexts times the ratio of l = 1 and l = L multiplication timings, giving an acceleration factor of about 10 3 for homomorphic product. 3,e,i Bootstrapping in less than a second [START_REF] Halevi | Bootstrapping for HElib[END_REF] 3,e Bootstrapping for HElib [START_REF] Kim | Private genome analysis through homomorphic encryption[END_REF] 3,i,a Private genome analysis through HE [START_REF] Lauter | Private Computation on Encrypted Genomic Data[END_REF] 3 We also recommend the lecture of the following articles, which are related to or have implications on FHE: U ← U ∪ {z} 5: end for 6: Apply a random permutation to the set U 7: Output U .

Jaccard Similarity

With this one can compute the homomorphic Jaccard index of two sets, which is defined as J(A, B) = #(A ∩ B) #(A ∪ B) .

This can be done with 2n 2 + 3n calls to the equality circuit as written. Noticing that #(A ∪ B) = #(A) + #(B) + #(A ∩ B), this can be reduced to n 2 + 3n calls.

C.2 φ(x) = x n + 1 (rLWE ring)

Proposition C.2.1. Let α(x), β(x) two polynomials of degree n-1 and with random coefficients in {0, 1}. Each coefficient was sampled using independent coin tosses with probability p of being 1. Let γ(x) = α(x)β(x) mod (x n + 1). Then each coefficient of γ is sampled as the substraction of two binomial distributions. Moreover, if γ k denotes the k-th coefficient of γ(x), we have

     E(γ k ) = p 2 (2k + 2 -n), Var(γ k ) = np 2 (1 -p 2 ), Corr(γ a , γ b ) = � 1 -2 b-a n � 2p 1+p if a < b.
Proof: The setting is the same, but now the coefficients of γ(x) are

γ k = n-1 � i=0 α i β k-i[n] • π k (i) where π k (i) = � 1 if i ≤ k, -1 if i > k.
By linearity and independence, we have

E(γ k ) = p 2 n-1 � i=0 π k (i) = p 2 (2k + 2 -n), Var(γ k ) = E(γ 2 k ) -p 4 (2k + 2 -n) 2 , E(γ 2 k ) = n-1 �

5 1. 2

 52 's ideal lattice basic scheme . . . . . . . . . . . . . . . . . . . 3.4 The attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Reduction to ad-HPP . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . Overview of this Dissertation . . . . . . . . . . . . . . . . 8 1.3 Reported practical applications . . . . . . . . . . . . . . . 8 1.4 Relations: FHE and ... . . . . . . . . . . . . . . . . . . . . 10 1.4.1 ... functional encryption . . . . . . . . . . . . . . . . . . . . 10 1.4.2 ... cryptographic obfuscation . . . . . . . . . . . . . . . . . 11 1.4.3 ... secure multi-party computation . . . . . . . . . . . . . . 11 1.4.4 ... identity-/attribute-based encryption . . . . . . . . . . . 11 1.4.5 ... proxy re-encryption . . . . . . . . . . . . . . . . . . . . . 12 1.5 The five families . . . . . . . . . . . . . . . . . . . . . . . . 12 1.5.1 Ideal Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.5.2 Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.5.3 (Ring-)Learning with errors . . . . . . . . . . . . . . . . . . 13 1.5.4 NTRU-based . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.5.5 Approximate eigenvectors . . . . . . . . . . . . . . . . . . . 14 1.6 Definition of FHE . . . . . . . . . . . . . . . . . . . . . . . 15 1.6.1 Circuits versus functions . . . . . . . . . . . . . . . . . . . . 15 1.6.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.6.3 Security definitions . . . . . . . . . . . . . . . . . . . . . . . 17 1.7 The bootstrapping procedure and other techniques . . . 18 1.7.1 Circular security . . . . . . . . . . . . . . . . . . . . . . . . 19 1.8 Hard problems used in FHE . . . . . . . . . . . . . . . . . 19 1.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Figure 1 . 1 :

 11 Figure 1.1: An easy maze

4 .

 4 B makes a guess b � ∈ {0, 1} and wins if b � = b.

  Figure 1.2 show this idea.

Figure 1 . 2 :

 12 Figure 1.2: The re-encrypt procedure

  Let a, b ∈ ξ × and let c = a • b ∈ R. The Special Factors Problem consists in finding a, b given c and a test function T : R → {0, 1} that outputs 1 if the input is in {a, b} and 0 otherwise. Problem 1.8.13 (ξ × -CDP). Let ξ be a distribution on some ring R. Let a, b ← ξ × and y R ← -R. Let u = a • y ∈ R and v = b • y ∈ R. The ξ × -Common Divisor Problem is to guess (a, b, y) given (u, v) and a test function T : R → {0, 1} that outputs 1 if the input is in {a, b, y} and 0 otherwise.

Figure 2 .

 2 Figure 2.1: A lattice of R 2 and two bases. Given a basis of rank m in matrix form B = (b 1 |b 2 | • • • |b m ), the quantity |det(B)| := � det( t BB) is an invariant of L, which we note by det L. Let the

Definition 2 . 5 . 2 (

 252 Matrix natural density). Let S ⊂ M n (Z) be a subset of integer matrices. Let σ max : N → N be the counting function σ max (t) := #(S ∩ B t ). The natural density of S is δ(S) := lim t→∞ σ max (t)

Algorithm 5

 5 Bs,Bsinv); Mod2(psi); } Hermite Normal Form Require: M is a non-singular N × N matrix 1: function HNF(M ) 2:

  ) ← Row(l) -λRow(k) where λ = �m lk /m kk �

Contents 3 . 1

 31 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.2.2 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.2.3 Polynomial ideal lattices . . . . . . . . . . . . . . . . . . . . 61 3.2.4 Key-Recovery Attacks against SHE schemes . . . . . . . . . 62 3.3 Gentry's ideal lattice basic scheme . . . . . . . . . . . . . 62 3.4 The attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.4.1 Reduction to ad-HPP . . . . . . . . . . . . . . . . . . . . . 64 3.4.2 Feeding Nguyen-Regev's algorithm and Random Scattering 65 3.4.3 Falling towards vertices . . . . . . . . . . . . . . . . . . . . 66 3.4.4 Proofs of algorithms . . . . . . . . . . . . . . . . . . . . . . 68 3.5 Length of binary searches in the neighbor algorithm . . 71 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

  Proposition 3.4.1. The Touch Border algorithm has a complexity of O(log D) calls to χ.

the shared elements. 2 :

 2 Alice and Bob perform SharedTMP twice to obtain shares of z = α • r and w = g • r.

2 :

 2 Algorithm 14 Excalibur -Keygen sk Require: Bob's secret-key β and the same sharing of α = 2(s A + s B ) + 1 than in protocol 13. Ensure: A secret-key for Alice sk A = αβ 1: Bob computes r := (2s B + 1)β ∈ R q Alice and Bob perform the protocol TMP(2s A , β), and Bob uses r as the random polynomial. At the end Alice knows 2s A β + r = αβ ∈ R q .

Figure 4 .

 4 Figure 4.1: M. and G. perform Excalibur Keygen sk

  r, b 3 = βpk A /2. We can eliminate the third equation noting that b 1 b 3 = b 2 , and thus Bob faces the Small GCD Problem of section 4.4.2.

1: function KeyGen(1 λ ) 2 :

 2 Define sk, e, a, b ∈ R 3: sk ← HWT (h) � h = 64 is suggested in [CS16].

2 : 4 :

 24 c 0 , c 1 , L -1, B clean ) � B clean is a noise norm upper bound for correct decryption9:Output c 10: end function --------1: function Dec(sk, c ∈ R 2 × R × N) Parse c = (c 0 , c 1 , t, ν) 3: Set m � ← [c 0c 1 • sk] qt� A "verify noise" procedure may be performed hereOutput m � mod p 5: end function5.2.4 Relinearization and Modulus switchingIt is possible to define multiplication of ciphertexts now, but for correct decryption this would need powers of the secret key. Let us explain this, consider two fresh ciphertexts encrypting m, m � respectively under the same public key:c = (c 0 , c 1 , ν, t) such that [c 0c 1 • sk] qt = m mod p, c � = (c � 0 , c � 1 , ν, t) such that [c � 0c � 1 • sk] qt = m � mod p.Then it is clear that the "extended ciphertext" D defined as followsD = (d 0 , d 1 , d 2 , ν D , t D ) such that      d 0 = [c 0 • c � 0 ] qt d 1 = [c 0 c � 1 + c 1 c � 0 ] qt d 2 = [c 1 • c 1 ] qtverifies the "extended decryption equation" [d 0 + d 1 sk + d 2 sk 2 ] qt = m • m � mod p.

  1: procedure SwitchKeyGen(sk,sk � ) 2:

2 :

 2 end procedure --------The following is the first variant proposed in[START_REF] Costache | Which Ring Based Somewhat Homomorphic Encryption Scheme is Best?[END_REF]. It is the last step in ciphertext multiplication. The polynomials d 0 , d 1 , d 2 are three ring elements containing the coefficients of 1, sk, sk 2 in the product (c 0skc 1 )(c � 0skc � 1 ) for ciphertexts (c 0 , c 1 , etc) and (c � 0 , c � 1 , etc), while t, ν are level and noise tags. --------1: procedure SwitchKey(swk, d 0 ∈ R, d 1 ∈ R, d 2 ∈ R, t, ν) Write d 2 component-wise in base T : d 2 = d 2,0 , d 2,1 , . . . , d 2,θ-1 3: c 0 ← d 0 + � d 2,i • b i 4:

5 :

 5 0 ← a.c 0 + b.c 0 mod q t 7:c.c 1 ← a.c 1 + b.c 1 mod q t procedure MulCipher(cipher a,cipher b, switchingkey swk)2: t ← min(a.t, b.t) Define c, d 0 , d 1 , d 2 6: d 0 ← a.c 0 • b.c 0 7: d 1 ← a.c 0 • b.c 1 + a.c 1 • b.c 0 8: ν ← a.ν • b.ν � Noisegrows exponentially 9: c ←SwitchKey(swk, d 0 , d 1 , d 2 , t, ν) 10: c ←ReduceLevel(c, t -1) � Reducing modulus (next product will be faster) -Scaling ciphertexts 1: procedure ScaleVariant(cipher c, Q ∈ N) � This is the variant proposed in [CS16] Require: Q|q c.t , P ≡ 1 mod p.

2 :

 2 Parse c = (c 0 , c 1 , t, ν) 3:

c 4 : 2 :: end if 4 :

 424 � .t ← t out � c � is a clone of c, but assigned to the new level Output ScaleVariant(c � , q c.t ) 5: end procedure � (Remark that qc.t satisfies both requirements of ScaleVariant)--------1: procedure ReduceLevel(cipher c, t � ∈ N) if c.t ≤ t � then return c 3if c.ν > B then c ←Scale(c, t � )

Figure 5 .

 5 Figure 5.1: BGV implementation: C++ Class dependencies

5 Figure 5 . 2 :

 552 Figure 5.2: First five Irwin-Hall probability density functions.

/ 2 :

 2 /in key.h mpz class sk[N] //The secret key mpz class a[N],b[N] //The public key pair (a,b) void key::Print(); void key::KeyGen(); //Generates a key-pair Algorithm 22 Recursive FFT 1: procedure RecFFT(n, (a[0], • • • a[n -1]), (y[0], • • • y[n -1])) � Puts the FFT of � a in � y. Require: Primitive n-th root of unity ω n if n = 1 then 3: y[0] ← a[0]

�

  a 0 ← (a[0], a[2], • • • , a[n -2]) � Even part of a 7: � a 1 ← (a[1], a[3], • • • , a[n -1])� Odd part of a 8:

  ← y 0 [k] + ωy 1 [k] 14: y[k + n/2] ← y 0 [k]ωy 1 [k]

4 :I ← I ∪ {z} 5 :

 45 [Gen10a, Mic01, GN08, LPR13, Vai12, Sil13, MP12, HRSV11, KMR11, Mic11, Pei16]. Algorithm 23 Homomorphic Intersection 1: I ← ∅ 2: for i from 1 to n do 3: z ← in(a i , B) • a i end for 6: Output I. Algorithm 24 Homomorphic Union 1: U ← A 2: for i from 1 to n do 3: z ← NOT in(b i , A) • b i 4:

p 4 �

 4 i α j )E(β k-i[n] β k-j[n] )π k (i)π k (j) = p 4 � i,j<n;i� =j π k (i)π k (j) + p 2 n � i=0 π k (i) 2 ; = p 4 ((2k + 2n) 2n) + p 2 n,yielding the claimed expression for Var(γ k ). Now, let a < b, thenE(γ a γ b ) = � i,j<n E(α i α j β a-i[n] β b-j[n] )π a (i)π b (j) = i� =j;a-i� =b-j[n] π a (i)π b (j) + p 3 n-1 � l=0 π a (l)π b (l) + p 3 n-1 � l=0 π a (l)π b (ba + l[n])= p 4 S 1 + p 3 (S 2 + S 3 ).

  l)π b (l) = n -2(ba).It holds thatπ b (ba + l[n]) = � 1 if ba + l[n] ≤ b -1 if ba + l[n] > b = � π a (l) if l < n -(ba) 1 if l ≥ n -(ba) ,

  3 A Key-Recovery Attack Against Gentry's Ideal Lattice Scheme via ad-HPP 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Polynomial ideal lattices . . . . . . . . . . . . . . . . . . . . . 3.2.4 Key-Recovery Attacks against SHE schemes . . . . . . . . . . 3.3 Gentry

  i from 1 to t, B asks A to decrypt a ciphertext ψ i , and A answers E.Dec(sk, ψ i ). These exchanges cannot be repeated after the challenge ciphertext.3. (Challenge) B generates two plaintexts π 0 , π 1 ∈ P and sends them to A, who chooses b ∈ R {0, 1}, and sets ψ * ← E.Enc(pk, π b ). She sends ψ * to B. 4. B wins if he guesses the value of b.

	Definition 1.6.7. Let b � ∈ {0, 1} be B's final guess in the game. The advantage of B is defined by

  1.8.1 (SVP,γ-SVP). Given a lattice L, the Shortest Vector Problem is to find a non-zero vector v ∈ L of smallest possible norm ||v|| 2 = λ 1 (L). The γ-SVP variant is to find a non-zero vector of norm at most γ • λ(L). (GapSVP β ). Given a lattice L and β ∈ R + , the Gap Shortest Vector Problem is to decide whether λ 1 (L) ≤ 1 or λ 1 (L) ≥ β Problem 1.8.3 (CVP). Given a lattice L and a vector v ∈ R n (not necessarily in L), the Closest Vector Problem is to find the vector in L closest to v. The CVP γ variant consists in finding a vector in L with at distance at most γ from v. Given a lattice L of dimension n, the Smallest Independent Vectors Problem is to find n linearly independent lattice vectors v 1 . . . , v n such that max i ||v i || 2 ≤ λ n (L). The γ-SIVP variant is to find n l.i. vectors such that max i ||v i || 2 ≤ γλ n (L)

	Problem 1.8.2 Problem 1.8.4 (BDDP). The Bounded Distance Decoding Problem consists in solv-
	ing the closest vector problem with the promise that min l∈L ||v -l|| 2 ≤ λ 1 (L)/2.
	Problem 1.8.5 (SIVP). Problem 1.8.6 (SBP). Given a basis B of a lattice L, the Shortest Basis Problem
	consists in outputting a basis B � of the same lattice such that the length of vectors
	in B � is as short as possible.
	In 2005, Regev introduced the celebrated Learning With Errors Problem as a gen-
	eralization of the parity learning problem. He proved that LWE is hard if GapSVP γ
	and SIVP are quantum-hard.

  3 and {|x 3 | < |t 33 |, |x 2 | < |t 22 | + |t 23 |, |x 1 | < |t 11 | + |t 12 | + |t 13 |}, respectively. The binary case I = (2), B I = 2I n and P = {0, 1} n suffices for applications and is the simplest to analyze. We will of course adopt this choice, however, it raises the nontrivial question of studying the distribution of lattices that are relatively prime to α((2)).

	See next section.

  and d are eigenvalues of rot(v sk ) with corresponding eigenvectors � k e k and � k (-1) k e k respectively). Therefore, if the sampled secret vector corresponds to an even value of s or d, it can be ruled out since the determinant of rot(v sk ) is even.Let us give a toy example.

	Algorithm 3 Key Generation for Gentry's IL homomorphic scheme

Require: Security parameter λ, parameters n, l Samp Ensure: Key-pair B sk J , B pk J 1: function Keygen(λ)

2:

Table 2 .

 2 .6.3.

	Function	n = 32 n = 64 n = 128 n = 200
	HNF[s]	<0.1	<0.1	8	993
	Inverse[s] <0.02	2	42	2507
	KeyGen[s]	<0.02	2	50	3516

1: Timings of Gentry's key-generation procedure in toy settings

Table 2 .

 2 .2 the required size of ||v sk || to perform 1.000.000 correct successive evaluations when l Samp = n.

	l Samp = n	Depth 2 Depth 3 Depth 5
	n = 10 (toy)	2 34	2 46	2 70
	n = 32	2 40	2 61	2 103
	n = 64	2 56	2 74	2 158
	n = 128 (very small)	2 64	2 88	2 257

2: Reported secret key Euclidean size in Gentry's tweaked scheme.

  To search the remaining points near the facet, they can repeat this procedure using small perturbations of � d of the form � d

tion � d ∈ R n and tests integer points near � � d � (i.e.inside the cylinder B n (0, √ n)×� � d �). They can find a point lying within distance of at most √ n of ∂P in O(log D) calls to the membership function χ, since dist(O, ∂P ) ≤ D/2.

  The center O and a vertex V of a parallelepiped P . A superior bound L. Ensure:

		Algorithm 10 Finding a neighbor vertex
		Require:
	13: 14:	-→ Ox return Find Vertex Rec(x, � u � , � � u � ← v 1 , . . . , � v n-1 )
	15:	end if
	16: end function

  min t 0 , max t 0 ] Mean(t 0 ) k ≤ 7 success rate k ≤

					10 success rate
	256	[0.600,0.688]	0.630	79.8%	87.8%
	512	[0.602,0.669]	0.631	64.2%	76.6%
	1024	[0.610,0.659]	0.632	42.6%	57.3%
	2048	[0.614,0.650]	0.634	19.9%	30.3%
		Table 3.1: Direction searching in the dichotomy of algorithm 10.

5 :

 5 Alice verifies Bob's proof. If it is not correct, abort the protocol.

  5, TMP and SharedTMP are secure if Bob is honest, in the sense that either Alice learns the correct output, or either she learns indistinguishable from random elements, but she learns nothing about Bob's input. She is limited to alter the inputs of both instances of SharedTMPand then giving wrong z A or w A to Bob. Nevertheless if she inputs different r A 's in both protocols or if she changes the values of z A , w A before sending them to Bob, from the linearity of shares and the randomness of Bob's entries it follows that this sabotages the relation wz -1 = gα -1 , needed for correctness of decryption. In other words, in order to ensure (A1) and (A2), she is forced to maintain the input r A for both instances of SharedTMPand send the correct output to Bob.

3. Participates in TMP({2s A }, {2s B + 1}) and learns αβ.

  A , r A ), (2s B +1, r B )) and learns z B , participates in SharedTMP((g A , r A ), (g B , r B )) and learns w B .Suppose Alice and Bob perform the latter protocols, such that Alice has now a private-key of the form sk A = αβ where β is Bob's secret-key. Alice can repeat the protocol with a third user Charlie (with slight coefficients size modifications at the validation protocol), who at the end receives a pair of keys of the form (sk C , pk C ) = (αβγ, 2g C (αβγ) -1

	4.8 Extensions
	4.8.1 Chains of keys
	As noted in section 4.5, because of Alice's randomness in SharedTMP, either
	Bob obeys the protocol and receives the correct outputs, either he deviates
	92

Table 5 .

 5 7: BGV algorithms performance in user seconds.

	Z 2 32	L = 30 {0, 1} Z 101	Z 2 32	L = 20 {0, 1} Z 101	Z 2 32	L = 10 {0, 1} Z 101	Z 2 32	Z 101
	19.1 18.3	9.17 8.88	8.44 8.09	8.03 7.64	3.69 3.39	2.558 2.295	6.33 5.88	3.11 2.91	2.21 2.013	1.91 1.79	0.72 0.65	47
	2418.9	1271.1	1170.39	1113.5	509.22	355.1	315	145.6	101.1	35.71	15.09	12.75
	103.3	50.858	46.81	16.49	6.55	5.142	12.66	6.23	4.449	3.82	1.38	1.04
	59.4	29.47	27.13	7.89	3.41	2.295	6.12	3.00	2.005	1.73	0.62	0.49
	6749.9	3242.0	2984.1	2531.8	1163.4	804.3	649.9	318.2	226.4	79.99	33.21	28.39
	1.78	1.82	1.48	1.19	1.21	1.05	1.18	1.22	1.05	1.17	1.01	1.08

Table A .

 A 2 -continued from previous page

	Year Reference	Tags	Title
		[CLT14]	2,p,i	Scale-Invariant FHE over the Integers
		[LN14]	3,e,i	A Comparison of [...] FV and YASHE
		[HS14]	3,i	Algorithms in HElib
		[FGP14]	p	Efficiently Verifiable Computation on Encrypted Data
		[SV14]	1,a,e	Fully homomorphic SIMD operations
	2015	[CCF + 15]	e	How to Compress Homomorphic Ciphertexts
		[CM15]	3,p	Multi-identity and Multi-key Leveled FHE from LWE
		[DGM15]	3,4,s	Adaptive Key Recovery Attacks on NTRU [...]
		[DM15]

  ,4,a,i Private Computation on Encrypted Genomic Data

		[VYY15]	i	HEtest: A HE Testing Framework
	2016	[ABD16]	4,s	A subfield lattice attack on overstretched [...]
		[CDPR16]	4,s	Recovering Short Generators of Principal Ideals [...]
		[CGGI16a]	5,e,i	Bootstrapping in less than 0.1 second
		[CGGI16b]	3,a	A Homomorphic LWE Based E-voting Scheme
		[CS16]	e	Which Ring Based SHE Scheme is Best

For excellent surveys on history of cryptography, see[START_REF] Kahn | The codebreakers : the story of secret writing[END_REF][START_REF] Singh | The Code Book: The Secret History of Codes and Codebreaking[END_REF].

C would understand on-the-spot that an homomorphic encryption scheme cannot be deterministic, since it would be possible to solve equations on ciphertexts.

(hence φ is the 2n-th cyclotomic polynomial), and the large prime modulus is such that x n + 1 splits into n different factors over F q (namely, q = 1 mod 2n). We will consider the modified NTRU scheme, but we believe that, possibly via a stretching of parameters, the original NTRU may also exhibit the Excalibur property.Excalibur key generation. The way to glue two secret-keys is very simple: just multiply them together! Indeed, the modified NTRU scheme offers a fruitful property: If one replaces a secret-key with a small polynomial multiple of it, decryption still works. If this polynomial multiple is itself a secret-key, then by symmetry decryption with the resulting key will be correct in the union of ciphersets decryptable by one key or another. However, addressing the main point of this Chapter, parties must multiply the involved polynomials using multiparty protocols, since they do

Remerciements

for λ i ∈ Q, and let c � = (x 1 + x n )/2, � u � = -→ Oc � . The next step is to perform a new fall starting from c � , with initial direction � u � . After n new bounces against the wall (in the same directions than the previous step) we will have points

y 1 + β 2 e 2 , y 3 = y 2 + β 3 e 3 , . . .

First perform the translation y � 1 = y 1β 1 � u � , y � 2 = y 2β 1 � u � , . . . , y � n = y nβ 1 � u � . We therefore have that dist(y � 1 , y � n ) = dist(y 1 , y n ) and y � 1 = c � . Consider H, the nhyperrectangle formed by x 1 , . . . , x n . With the given translation y � 1 lies at its center. Notice also that every point y � 2 , . . . , y � n lies inside of this hyperrectangle, because if there is a point y � i � ∈ H, the straight line connecting O and y i has a segment outside the parallelepiped, contradicting the convexity of P . In particular, y � n ∈ H, therefore its distance to the center is less than half the diameter of H. In other words,

completing the proof.

Corollary. The Find Vertex algorithm outputs a vertex of P after at most �log(D)� recursive calls.

Proof. After k iterations, d k ≤ d 0 2 k < D 2 k , and d k < 1 is therefore reached after at most �log D� iterations. The fact that this sequence converges to a vertex of P follows immediately by convexity of P . Proposition 3.4.4. The Find Vertex algorithm has a complexity of O(n log 2 D) calls to χ.

Proof. At the first iteration of Bounces we have the bound d 1 ≤ D. Since at each step we divide d i by 2, then the number of steps is less than log D. The most costly operation of Find Vertex is Bounces, who needs n calls to Touch Border. Therefore, Bounces has a complexity of O(n log(D)) calls to χ.

Falling towards V �

When a vertex V is found, one can repeat algorithm 9 to fall into a neighbor vertex, given a proper initial direction to fall into. Let us explain how to establish this direction and justify the correctness of our method.

Chapter 4 A betrayal problem -The Excalibur Property

The contents of this Chapter include an article published in the Proceedings of Indocrypt 2016. This is joint work with Louis Goubin.

Bounded discrete Gaussian samplings on Z[x]/(x n + 1)

Let n be a power of 2 and q a prime number, R = R 0 def = Z[x] (x n +1) and as before R q def = Fq[x] (x n +1) . The modified NTRU scheme uses a particular distribution in R q , which we refer to as K-bounded by rejection discrete Gaussian, serving to sample both message noises and secret-keys. Definitions follow. Definition 4.2.1. Let G r be the discrete Gaussian distribution over R, centered about 0 and of standard deviation r.

Sampling from G r can be done in polynomial time, for instance approximating with Irwin-Hall distributions and outputting the nearest integer vector. Consider the following definitions from [START_REF] López-Alt | On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[END_REF]:

). For any polynomials s, t ∈ R,

Corollary. Let χ be a K-bounded distribution over R and let s 1 , . . . , s l ← χ. Then � l i=1 s i is (n l-1 K l )-bounded.

Modified NTRU encryption

We review the modified NTRU encryption scheme as presented in [START_REF] López-Alt | On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[END_REF], and we insist on the multi-key property. The message space is {0, 1} and the ciphertext space is

(x n +1) . Let q be a large prime, 0 < K � q, n be a power of 2 and ḠK be the K-bounded by rejection discrete Gaussian. A key-pair (sk, pk) is a tuple of polynomials in R q , the secret-key being K-bounded.

Keygen(1 κ ):

Step 1. Sample a polynomial f ← ḠK . Set sk = 2f + 1, if sk is not invertible in R q start again.

Step 2. Sample a polynomial g ← ḠK and set pk = 2g • sk -1 ∈ R q .

Step 3. Output (sk, pk).

Hardness assumptions

The modified NTRU-FHE scheme semantic security is based on the celebrated Ring Learning With Errors problem (RLWE) and the new Small Polynomial Ratio problem (SPR). For the original modified NTRU parameters, the decisional SPR problem reduces to RLWE, but not a single homomorphic operation can be assured. A stretch of parameters is needed to overcome this, though it severely harms the statistic proofs of Stehlé and Steinfeld. The DSPR assumption states that the decisional SPR problem with stretched parameters is computationally hard. We adopt this same assumption, and in addition, we base the security of the honest-but-curious model on two problems that involve decomposing a polynomial into bounded factors. In the first, one wants to factorize a polynomial in R q into two K-bounded polynomials, given the information that this is possible. In the second, one wants to extract a common factor of two polynomials such that the remaining factors are K-bounded. We first describe the DSPR assumption and then our "Small Factors" assumption.

Small Polynomial Ratio Problem, from [LATV12]

In [START_REF] Stehlé | Making NTRU as Secure as Worst-Case Problems over Ideal Lattices[END_REF] Stehlé and Steinfeld based the security of the modified NTRU encryption scheme on the Ring Learning With Errors (RLWE) problem [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF]. They showed that the public-key pk = 2g •sk -1 ∈ R q is statistically close to uniform over R q , given that g and f � = (sk-1)/2 were sampled using discrete Gaussians. Their results holds if (a) n is a power of 2, (b) x n + 1 splits over n distinct factors over R q (i.e. q = 1 mod 2n) and (c) the Gaussian error distribution has standard deviation of at least poly(n) √ q. However, these distributions seem too wide to support homomorphic operations in the NTRU-FHE scheme. To overcome this, authors in [START_REF] López-Alt | On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[END_REF] defined an additional assumption which states that if the Gaussian is contracted, it is still hard to distinguish between a public-key and a random element of R q (even if the statistic-closeness result does not hold).

Definition 4.4.1 (DSPR Assumption). Let q ∈ Z be a prime integer and ḠK denote the K-bounded discrete Gaussian distribution over R 0 = Z[X]/(x n + 1) as defined in 4.2.4. The decisional small polynomial ratio assumption says that it is hard to distinguish the following two distributions on R q : (1) A polynomial h = [2gf -1 ] q ∈ R q where f � , g were sampled with ḠK and f = 2f � + 1 is invertible over R q , and (2)

Finally, in a work by Bos et.al. [START_REF] Bos | Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme[END_REF], authors achieved to base the security on RLWE alone, alas achieving multikey FHE for a constant number of keys, a property inherent to any FHE scheme (as proved in the latest version of [START_REF] López-Alt | On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[END_REF]).

Small factorizations in the quotient ring

In addition to the RLWE and DSPR assumptions, we rely the semi-honest security on the hardness of the following problems. Let us define the distribution Ḡ× K which samples repeatedly from ḠK until the output is invertible over R q .

Small Factors Problem: Let a, b ← Ḡ× K and let c(x) = a(x) • b(x) ∈ R q . Find a(x) and b(x), given c(x) and a test routine T : R q → {0, 1} that outputs 1 if the input is in {a, b} and 0 otherwise.

Find a(x), b(x) and y(x), given u(x), v(x) and a test routine T : R q → {0, 1} that outputs 1 if the input is in {a, b, y} and 0 otherwise. Proposition 4.4.1. An algorithm solving the Ḡ× K -GCD problem can be used to break the semantic security of the NTRU scheme.

Proof: Given only a public-key of the form pk = [2ab -1 ] q where a is the secretkey, sample p R ← -R q and define (u � , v � ) = (ab -1 p, p). Define also T : R q → {0, 1} that for input α ∈ R q , samples random r R ← -{0, 1}, checks if Dec(α, Enc(pk, r)) ? = r and outputs 1 if α pass several such tests. Note that u � = ay � and v � = by � for y = b �-1 p, therefore seeding u � , v � , T to such algorithm outputs a, b, y � . � Small Factors Assumption: For the modified NTRU parameters, it is unfeasible to solve the small factors problem.

In the absence of a formal proof, let us motivate the hardness of the small factors problem. The SF problem is equivalent to solve a quadratic system of equations over F q with additional restrictions on the unknowns. Indeed, each coefficient of c(x) is a quadratic form on coefficients of a(x), b(x):

where σ k (i) = +1 if i ≤ k and -1 otherwise, the unknowns a i , b j follow a Gaussian distribution about 0 and are bounded in magnitude by K. As K � q, one can consider the equations over the integers. This results in a Diophantine quadratic system of n equations in 2n variables. Quadratic systems of m equations with n unknowns can be the Achilles heel for strong cryptographic primitives, as they can be attacked in the very overdetermined (m ≥ n(n -1)/2) or very under-determined (n ≥ m(m+1)) cases in fields with even characteristic. In [START_REF] Thomae | Solving Underdetermined Systems of Multivariate Quadratic Equations Revisited[END_REF], authors adapt an algorithm of Kipnis-Patarin-Goubin [START_REF] Kipnis | Unbalanced Oil and Vinegar Signature Schemes[END_REF] to odd characteristic fields and show a gradual change between the determined case (m = n, exp(m) runtime) and the massively under-determined case (n ≥ m(m + 1), poly(n) runtime). According to pk A and under pk B . As we will see, this validation protocol avoids malicious activity.

Algorithm 15 Excalibur -Validation function (performed by Alice)

for i from 1 to k do

end for

k ), and for each i = 1, . . . , k he computes ciphertexts c

He send all ciphertexts to Alice. 3: For each i = 1, . . . , k, Alice compute µ

. She sends all plaintexts to Bob. 4: For each i = 1, . . . , k, Bob checks if µ

Security

We first discuss the honest-but-curious model, where the protocol is strictly followed but parties try to learn secrets. Then we look at the malicious model, where one party does not follow the protocol properly, in order to steal secrets or to sabotage the key generation.

Honest-but-curious model

In this model, we suppose that Alice and Bob follow exactly the instructions in algorithms 13, 14, 15 and 16 but they try to learn about each other's secret with all collected information.

Proposition: If Alice is able to extract Bob's key from the protocol, she can solve the Small Factors Problem or the Ḡ× K -GCD Problem. If Bob is able to extract Alice's key, he can solve the Ḡ× K -GCD Problem.

Security against one malicious party

We consider the presence of one malicious adversary, a party that deviates as much as she wants from the protocol, but has a list of paramount objectives which she is not willing to sacrifice. We suppose that one of the two parties strictly follows the protocol and the other one is malicious, given the objectives below. We consider the presence of only one somewhat malicious adversary, given that both parties have concurrent objectives (for instance, Bob is trying to protect his key, and Alice to extract it from the protocols). In other words, (B4) to learn α.

We will show that either the keys will be correctly generated or one party will not fulfill all of her objectives.

Malicious Alice, semi-honest Bob

Suppose that Bob is strictly following the protocol and Alice may deviate from the protocol but wants to fulfill (A1) to (A4). Let us summarize Alice's participation in the key generation:

Trivial samplings of these elements may ultimately leak α to Bob. For instance, if

there is risk of mod q wrap-around in the decryption procedure with sk A . As she is sampling only shares of elements, she cannot force algebraic relations with them: regardless of her samples, α, g, r will remain indistinguishable from random. and receives random outputs, from which he cannot deduce secret values and which sabotage key generation. Also, if he uses different r B 's in both instances, Alice will not be able to decrypt since the decryption relation wz -1 = gα -1 is not fulfilled (and he remains oblivious of r A , not being able to force this relation). Hence, he is forced to follow SharedTMP and use the same r B in both instances if he wants to fulfill (B1). A contains the factor β, thus by randomness of s A , β � = θβ and R � = ωβ for small θ and ω. Also, as long as the polynomials sk � A and sk � A • pk � A are of the right form, she does not care about how Bob computed pk � A , as decryption of encryptions under pk � A work as claimed. If on the contrary a single decryption fails or if sk � A or sk � A • pk � A have large coefficients, she can claim one of the following Bob's wrongdoings: Either he did not include β, either he included θβ for too large θ, either he sabotaged entirely the key generation in a change of input or inside a multiparty multiplication protocol. This allows to conclude that if Bob fails to give what is expected, the output keys will be rejected by Alice, who discovers Bob's maliciousness after the validation protocol 16.

Receives z

We should point out another strategy that Bob could maliciously try. When generating Alice's secret-key, he could simply ignore Alice's input share 2s A , and thus the protocol gives Alice the key sk � A = α � β, for an α � ∈ R × q of Bob's choice. Bob, who received no output from the protocol, can reconstruct this key, thus gaining Alice's secret. However, this key will be rejected by Alice since it cannot be associated with the previously generated pk A = 2g(αβ) -1 . To avoid this rejection, Bob should have published pk � A = 2g � (α � β) -1 instead, but it is easy to see that this publication would contradict the NIZK proof of step 4 of algorithm 13: Because of the way SharedTMP works, Bob has no way of choosing α � of his choice in the expression z = αr. In view of this, passing the validation protocol with such a key is overwhelmingly unlikely.

Chapter 5

The promising BGV scheme: an implementation The gmp parameters cannot be set globally, this is why we include a function SetParameters() in the BGV.h file that sets all remaining parameters.

Ring of polynomials

The file Ring.h provides all necessary functions on polynomials: addition, componentwise reduction modulo q, component-wise decomposition in base T (for key switching), prime numbers generator of a given number of bits and congruent to 1 modulo 2N , and fast multiplication in the ring (via the number theoretic transform).

Sampling

The file Sampling.h includes four different samplings over R q : //in Sampling

Switching-key object

In order to relinearize an already evaluated ciphertext, for which decryption would normally need powers of the secret key, some information about the Key Switching procedure must be published (see 5.2.4). We decided to create an independent class switchingkey.h to contain this information, rather than including this into the key.h class. The reason for this is that this special key is the largest object of the scheme and its handling can be certainly optimized. It contains two attributes

//in switchingkey.h mpz class a[theta][N]; mpz class b[theta][N];

//We introduced the parameter theta=log T(q L-1) for memory allocation. void switchingkey::Print(); void switchingkey::Verify(); //Verify the correctness of semi-encryptions, see 5.2.4.

The BGV scheme

Linking to all previous classes, the BGV.h is at user-end and contains the cryptographic functions, as key-generation, encryption, decryption, homomorphic evaluation and some test routines;

Appendix A

Seeing the whole picture: An article reading guide

Approaching fully homomorphic encryption literature can be very disconcerting. Several teams of expert cryptography research have published hundreds of articles since 2009, and partly because of the speed of advancements, understanding the different lines of work and their relationships is not an easy task. We will list here some of the principal articles, ordered by chronology and battlefronts: efficiency, security, applications, implementations and displaying other properties. We begin by stating that we highly recommend the lecture of On data banks and Privacy Homomorphisms, by Adleman, Dertouzos and Rivest [START_REF] Rivest | On Data Banks and Privacy Homomorphisms[END_REF].

Tag Ref. 1,i Implementing Gentry's FHE scheme [START_REF] Lauter | Can Homomorphic Encryption Be Practical[END_REF] 3,a,i Can homomorphic encryption be practical? [START_REF] Scholl | Improved Key Generation for Gentry's Fully Homomorphic Encryption Scheme[END_REF] 1,e,i Improved Key Generation for Gentry's FHE scheme 2012 [START_REF] Brakerski | Fully Homomorphic Encryption Without Bootstrapping[END_REF] 3,p,e FHE without bootstrapping [START_REF] Brakerski | Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP[END_REF] e FHE without modulus switching from classical GapSVP [START_REF] Boneh | Targeted Malleability: Homomorphic Encryption for Restricted Computations[END_REF] p,s Targeted Malleability: HE for Restricted Computations [START_REF] Fan | Somewhat Practical Fully Homomorphic Encryption[END_REF] 3,e, Somewhat practical FHE [START_REF] Gentry | Fully Homomorphic Encryption with Polylog Overhead[END_REF] 3,e FHE with Polylog overhead [START_REF] Gentry | Ring Switching in BGV-Style Homomorphic Encryption[END_REF] 3,e Ring Switching in BGV-Style HE [START_REF] Loftus | On CCA-Secure Somewhat Homomorphic Encryption[END_REF] 1,s On CCA-Secure SHE [START_REF] Coron | Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers[END_REF] 2,e,i,s Public Key Compression and Modulus Switching [...] 2013 [START_REF] Alperin-Sheriff | Practical Bootstrapping in Quasilinear Time[END_REF] 1,e Practical Bootstrapping in Quasilinear Time [BGH + 13a] 3,a Private Database Queries Using SHE [START_REF] Bos | Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme[END_REF] 3,s Improved Security for a Ring-Based FHE scheme [START_REF] Bos | Private Predictive Analysis on Encrypted Medical Data[END_REF] 1,a,i Private Predictive Analysis on Encrypted Medical Data [BLP + 13] 3,s Classical Hardness of LWE [START_REF] Brakerski | Packed Ciphertexts in LWE-Based Homomorphic Encryption[END_REF] 3,p,e Packed Ciphertexts in LWE-Based HE [CCK + 13] 3,e,p Batch FHE over the Integers [FSF + 13] 3,i Towards practical program execution over FHE schemes [START_REF] Gentry | Field Switching in BGV-style Homomorphic Encryption[END_REF] 3,e,s Field Switching in BGV-style Homomorphic Encryption [START_REF] Jeckmans | Efficient Privacy-Enhanced Familiarity-Based Recommender System[END_REF] 3,a Efficient privacy-enhanced [...] recommender system [START_REF] Van De Pol | Estimating Key Sizes for High Dimensional Lattice-Based Systems[END_REF] 3

Homomorphic operations on sets

In this appendix, we describe how to handle homomorphic operations over sets of data, where cardinality and order of the elements are kept private. We give circuits that perform equality and membership tests, cardinality, union, intersection and Jaccard similarity.

Context and encoding conventions

We suppose that there are multiple users holding sets of similar data (i.e. all sets are made of lists of names, or account numbers, etc). Users want to store their data in the cloud, in order to perform homomorphic evaluations on two different sets as wholes. They do not want to leak the cardinality of their sets, nor any ciphertext identification. We suppose that -Each element of a set can be encoded using κ bits with non-zero Hamming weight.

-There is a null element encoded with κ zero bits.

-Encryption of a set is performed element-wise, padding with encryptions of null until a number n of elements is reached, and then permuting randomly the ciphertexts.

-Decryption is performed element-wise.

For instance, if κ = 4 and n = 8, the set S = {1001, 0110} is encrypted by a set C = {c 1 , c 2 , . . . , c 8 } such that two elements in C are encryptions of "1001" and "0110" and the rest are encryptions of null="0000".

Equality circuits

Let a, b ∈ {0, 1} κ be two plaintexts. The equality circuit is the bitwise computation of NXOR, followed by the AND of all outputs:

The multiplicative depth of this circuit is �log κ�. Let Eq 0 = Eq(a, 0) the function that tests if a is the null element. It can be performed with the following circuit Eq 0 (a) = NOT (AND κ i=1 NOT(a

Another possible equality circuit involves computing the Hamming distance of a and b:

Cardinality Let E = {c 1 , . . . , c n } a cipherset. To homomorphically compute the cardinality of the underlying set, one can simply perform #(E) = Eq 0 (c 1 ) + Eq 0 (c 2 ) + • • • + Eq 0 (c n ), which will return an encryption of the number of non zero integers in the underlying set counting repetitions.

Membership

Let E = {c 1 , . . . , c n } a cipherset and z a ciphertext. Then in(z, E) = Eq(z, c 1 ) + Eq(z, c 2 )

Intersection and union

Let A = {a 1 , . . . , a n }, B = {b 1 , . . . , b n } be two ciphersets. One can compute the intersection and union with the following algorithms:

The intersection algorithm outputs a set of n ciphertexts, which are encryptions of 0 or encryptions of elements in the underlying intersection.

The union algorithm outputs a set of 2n ciphertexts, which are encryptions of 0 or encryptions of elements in the underlying union, using n 2 calls to the equality circuit.

Appendix C

Coefficient correlation in the Small Factors Problem

In this Appendix, we quantify the linear correlation between any two coefficients of the known polynomial in the Small Factors Problem, when instantiated with Bernoulli sampling of the factors. We shall see that this correlation is inversely proportional to the sparseness of the secret factors, and for inattentive selection of parameters this could help to attack SFP.

Preliminaries

A discrete random variable θ is a Bernoulli trial with parameter p if it produces only two outcomes, one with probability p and the other with probability 1

For i = 1, . . . , n, let θ i be independent Bernoulli trials with the same parameter p, and let χ = � n i=1 θ i . Then χ follows the Binomial distribution with parameters n, p.

C.1 φ(x) = x n -1 (NTRU ring) Proposition C.1.1. Let α(x), β(x) two polynomials of degree n-1 and with random coefficients in {0, 1}. Each coefficient was sampled using independent coin tosses with probability p of being 1. Let γ(x) = α(x)β(x) mod (x n -1). Then each coefficient of γ follows a binomial distribution of parameters n, p 2 . The linear correlation coefficient between two distinct coefficients is 2p p+1 .

Proof: For 0 ≤ i, j ≤ n -1, let α i , β j be the independent Bernoulli trials of parameter p used to generate the polynomials α(x) = � n-1 i=0 α i x i and β(x) = � n-1 j=0 β j x j . For k = 0, . . . , n -1 let γ k ∈ Z be the random variable defined by the equation

Expanding the right-hand product and performing modular reduction gives

Note that the random discrete variables Z i,k := α i β k-i are Bernoulli trials of parameter p 2 (as they are a product of two independent B.t.). This allows to compute

From this is is clear that every pair γ a , γ b for a � = b consists of dependent random variables. We compute the covariance of this pair: let ξ c be the characteristic function of the condition c

and

Replacing these expressions we obtain Our contributions include a key-recovery attack against the ideal lattices FHE scheme and a new security conception inside hierarchic structures, avoiding betrayal between users to some extent, while maintaining the homomorphic encryption flexibility and also addressing an homomorphic re-encryption paradigm we detected. We also describe a working implementation of a recent proposal. This research was done in the Laboratoire de Mathématiques de Versailles, under supervision of Prof. Louis Goubin.