Ilaria Chillotti
email: ilaria.chillotti@kuleuven.be

Nicolas Gama
email: nicolas@inpher.io

Mariya Georgieva
email: mariya@inpher.io

Malika Izabachène
email: malika.izabachene@cea.fr

TFHE: Fast Fully Homomorphic Encryption over the Torus

Keywords: Fully Homomorphic Encryption, Bootstrapping, Lattices, LWE, GSW, Boolean circuit, deterministic automata

This work describes a fast fully homomorphic encryption scheme over the torus (TFHE), that revisits, generalizes and improves the fully homomorphic encryption (FHE) based on GSW and its ring variants. The simplest FHE schemes consist in bootstrapped binary gates. In this gate bootstrapping mode, we show that the scheme FHEW of [29] can be expressed only in terms of external product between a GSW and a LWE ciphertext. As a consequence of this result and of other optimizations, we decrease the running time of their bootstrapping from 690ms to 13ms single core, using 16MB bootstrapping key instead of 1GB, and preserving the security parameter. In leveled homomorphic mode, we propose two methods to manipulate packed data, in order to decrease the ciphertext expansion and to optimize the evaluation of look-up tables and arbitrary functions in RingGSW based homomorphic schemes. We also extend the automata logic, introduced in [31], to the efficient leveled evaluation of weighted automata, and present a new homomorphic counter called TBSR, that supports all the elementary operations that occur in a multiplication. These improvements speed-up the evaluation of most arithmetic functions in a packed leveled mode, with a noise overhead that remains additive. We finally present a new circuit bootstrapping that converts LWE ciphertexts into low-noise RingGSW ciphertexts in just 137ms, which makes the leveled mode of TFHE composable, and which is fast enough to speed-up arithmetic functions, compared to the gate bootstrapping approach. Finally, we provide an alternative practical analysis of LWE based schemes, which directly relates the security parameter to the error rate This work was done while I. Chillotti was a PhD student in the Laboratoire de Mathématiques de Versailles, UVSQ (Versailles, France) and while M. Georgieva worked in Gemalto (Meudon, France).

of LWE and the entropy of the LWE secret key, and we propose concrete parameter sets and timing comparison for all our constructions.

Introduction

This paper is the complete and extended version of the two papers [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF] and [START_REF] Chillotti | Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[END_REF] published by the same authors at Asiacrypt 2016 and Asiacrypt 2017, respectively. It unifies the work presented in both, completes the proofs, adds some further explanations of the results and experimentally validates the Gaussian output noise heuristic.

Since Gentry introduced in 2009 [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] the concept of bootstrapping, and proved that fully homomorphic encryption was achievable in polynomial time, many constructions have appeared, involving new mathematical and algorithmic concepts, improving efficiency and memory requirements. Nowadays, the most promising constructions [START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF][START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF][START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF] rely on two lattice-based problems: approximate-GCD, presented by Howgrave-Graham in 2001 [START_REF] Howgrave-Graham | Approximate integer common divisors[END_REF], and Learning With Errors (LWE), presented by Regev in 2005 [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] and its ring variants [START_REF] Stehlé | Efficient public key encryption based on ideal lattices[END_REF][START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF].

The literature distinguishes two families of homomorphic encryption schemes: leveled (LHE) and fully (FHE) homomorphic encryption. Informally, in LHE, for each function, there exist parameters that can homomorphically evaluate it. In FHE, a single parameter set allows to evaluate any function. With this (generalized) definition, FHE can be viewed as a particular case of LHE. For a given security parameter, and also a class of functions to evaluate in the LHE case, the quality of a homomorphic scheme is measured in terms of expressivity of its elementary operations, key size, running time per elementary operation, and ciphertext overhead. In this work, we improve them all, both from a theoretical point of view, by abstracting the GSW construction, and by extending homomorphic operations to new computational models, coming from weighted automata theory, and also from a practical point of view, by providing complete algorithms and concrete parameters, as well as an opensource implementation.

Most naive homomorphic schemes use Gaussian noise to mask the plaintext, and the noise variance grows after each operation, until it reaches critical levels. As per [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF], bootstrapping a ciphertext consists in homomorphically decrypting it, using a homomorphic encryption of its own secret key. In the end, we get an encryption of the same plaintext, but which noise only depends on the decryption circuit. The output noise is independent from the input noise, which confers to bootstrapping the unique ability to reduce the noise of a ciphertext. The simplest FHE schemes contain a single elementary operation: a NAND gate followed by a bootstrapping. Any polynomial time function can indeed be systematically written as a polynomial number of NAND gates, which can be evaluated homomorphically one by one using this bootstrapped NAND operation. Between 2009 and 2015, the running time and memory requirements to achieve this bootstrapped NAND gate has decreased across multiple generations of constructions, for instance a BGV-based [START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF] bootstrapping in the Helib library [START_REF] Halevi | Helib -an implementation of homomorphic encryption[END_REF] and a GSW-based [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF] bootstrapping in the FHEW library [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF]. The last one obtains one bootstrapped NAND gate in 0.69ms single core, using a 1GB bootstrapping key, and with a ciphertext overhead of 10000 for at least 100 bits of security.

In this work, we present a gate bootstrapping algorithm, implemented in the TFHE library [START_REF] Chillotti | TFHE: Fast fully homomorphic encryption library[END_REF], that decreases these requirements to 13ms single core, using a 16MB bootstrapping key, with the same ciphertext overhead and a higher security parameter.

Despite these optimizations, bootstrapped bit operations are still about one billion times slower than their plaintext equivalents. Other trade-offs have been proposed, where elementary homomorphic operations consist of vectorial arithmetic, which covers a large number of real life applications, in statistics or physics. The possibility to batch these operations in a SIMD manner (introduced in [START_REF] Smart | Fully homomorphic simd operations[END_REF], [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF]) compensates for the slow homomorphic operations, and provides a consequent apparent speed-up per element. Also, packing multiple plaintext bits on the same ciphertext asymptotically reduces the ciphertext expansion to a constant.

The efficiency of these schemes crucially relies on the fact that plaintext computations are expressed on a ring structure, where addition is invertible, and also that it supports enough parallelism to fill all the computation slots. Note that this model doesn't apply for highly non-linear computations involving comparisons, tropical algebra, optimization on graphs, etc... We show how to use the computation slots at their maximal capacity, even if the function itself is not SIMD, or has very few bits of output. Section 5 explains our horizontal and vertical packing using a homomorphic lookup table evaluation to illustrate our packing method. In FHE mode, we also provide a circuit bootstrapping procedure, that takes a LWE ciphertext as input, reduces its noise, and converts it back to an GSW ciphertext suitable for subsequent packed operations. This allows us for instance to evaluate an arbitrary function from {0, 1} 10 → {0, 1} in 340µs and to bootstrap the output in 137ms, thus improving upon all alternatives that output a bootstrapped GSW ciphertext. Both the gate bootstrapping and circuit bootstrapping constructions are described in Section 7 of the paper.

Finally, we give a abstract view of our constructions. By simply changing a fundamental building block called the phase, we can obtain FHE cryptosystems based not only on LWE, RingLWE, Module-LWE, but also scale-invariant versions based on the approx-GCD, or on the NTRU function. We show how to instantiate a canonical version, based on RingLWE, directly from the two user parameters: security parameters, and depth of circuit in the case of LHE. We reduce the number of parameters to avoid dependency loops between them, and we keep the remaining ones as intrinsic as possible, to ease their setup: for example, scale invariant versions of lattice problems are expressed on the torus, Gaussian noises are represented by their standard deviation or their variance, the size of the key is measured in bits. In the last sections, we explain how to calculate the parameters using bounds coming from state-of-the-art cryptanalysis, and we provide the concrete values that we implement in the open source library TFHE [START_REF] Chillotti | TFHE: Fast fully homomorphic encryption library[END_REF].

We provide the results and experimental running time at the end on the paper.

Background

In this section, we introduce some fundamental concepts that are used in the rest of the paper. In particular, we describe and revisit the LWE problem [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] before giving its generalization in Section 3. We start by fixing some notations.

Notations. In the rest of the paper, we denote the security parameter as λ. We denote as B the set {0, 1} without any structure and by T the real Torus R/Z, the set of real numbers modulo 1. We denote by Z N [X] the ring of polynomials Z[X]/(X N + 1). T N [X] denotes R[X]/(X N + 1) mod 1 and B N [X] denotes the polynomials in Z N [X] with binary coefficients. We denote by E p the set of vectors of dimension p with entries in E and by M p,q (E) the set of p × q-size matrices with elements in E. Definition 2.1 (R-module). Let (R, +, ×) be a commutative ring. We say that a set M is a R-module when (M, +) is an abelian group, and when there exists an external operation • (product) which is bi-distributive and homogeneous. Namely, ∀r, s ∈ R and x, y ∈ M , 1 R • x = x, (r + s) • x = r • x + s • x, r • (x + y) = r • x + r • y, and (r × s) • x = r • (s • x).

Remark 1. A R-module M shares many arithmetic operations and constructions with vector spaces: vectors M p or matrices M p,q (M ) are also R-modules, and their left dot product with a vector in R p or left matrix product in M k,p (R) are both well defined. By construction, any abelian group is a Z-module by iteration of its own law. In this paper we largely use the torus T, which is a Z-module. It is not a ring since the mod 1 projection is not compatible with the real product. For instance, the product 0 × 1 2 , where 0 and 1 2 are seen as elements of T, is undefined in T. Instead, the external product • between an element of Z and an element in T is correctly defined (0 • 1 2 , where 0 ∈ Z and 1 2 ∈ T, is equal to 0 ∈ T). More importantly, we recall that for all positive integers N and k, (T N [X] k , +, •) is a Z N [X]-module.

Probability distributions

Most FHE schemes hide the plaintext with Gaussian noise. In this paper, we always quantify this noise via its standard deviation or its variance. The variance of a Gaussian distribution is equal to its average square norm divided by the dimension, so working with it leads to propagation formula that are natural. Most importantly, it avoids the additional √ 2π factors (related to the noise parameter), which have often been a source of confusion in concrete implementations.

Gaussian Distributions Let k ≥ 1 and σ ∈ R + . For all x, c ∈ R k , we denote by ρ σ,c (x) = exp(-xc 2 /2σ 2 ) the Gaussian function of center c and standard deviation σ. If c is omitted, then it is implicitly set to 0. Let S be a subset of R k , then ρ σ,c (S) denotes x∈S ρ σ,c (x), if S is discrete, or x∈S ρ σ,c (x) • dx, if S is measurable.

For all closed (continuous or discrete) additive subgroup M ⊆ R k , ρ σ,c (M ) is finite, and defines a (restricted) Gaussian Distribution D M,σ,c of standard deviation σ and center c over M , with the density function D M,σ,c (x) = ρ σ,c (x)/ ρ σ,c (M ). Let L be a discrete subgroup of M , then the Modular Gaussian distribution D M/L,σ,c over M/L exists and is defined by the density D M/L,σ,c (x) = D M,σ,c (x + L).

Subgaussian Distributions A distribution X over R is σ-subgaussian if and only if it satisfies the Laplace-transformation bound. Namely for all t ∈ R, the expectation verifies E(exp(tX)) ≤ exp(σ 2 t 2 /2). Equivalently, the tails of X are bounded by the Gaussian function of standard deviation σ: ∀x > 0, P(|X| ≥ x) ≤ 2 exp(-x 2 /2σ 2 ). As an example, the Gaussian distribution of standard deviation σ (i.e. parameter √ 2πσ), the equi-distribution on {-σ, σ}, and the uniform distribution over [-√ 3σ, √ 3σ], which all have standard deviation σ, are σ-subgaussian 6 . If X and X are two independent σ and σ -subgaussian variables, then for all α, β ∈ R, αX + βX is α 2 σ 2 + β 2 σ 2 -subgaussian.

Concentrated distribution on the Torus

In general, distributions over the torus do not have expectation nor variance: for instance, it would be impossible to define the expectation of the uniform distribution over T. However, when the support of the distribution is concentrated on a small interval, it is still possible to uniquely define these notions. A distribution X on the torus is concentrated if and only if its support is included in a ball of radius 1 4 of T, up to a negligible amount. In this case, we define the variance Var(X ) and the expectation E(X ) of X as respectively Var(X ) = min x∈T X |x -x| 2 and E(X ) as the position x ∈ T which minimizes this expression. This definition of expectation by an optimization formula yields the same result as if we lift the distribution over any real interval of length < 1 2 , and compute its real expectation modulo 1. By extension, we say that a distribution X over T n or T N [X] k is concentrated if and only if each coefficient has an independent concentrated distribution on the torus. Then the expectation E(X ) is the vector of expectations of each coefficient, and Var(X ) denotes the maximum of each coefficient variance. These expectation and variance over T follow the same linearity rules than their classical equivalent over the reals. Fact 2.2. Let X 1 , X 2 be two independent concentrated distributions on either T, T n or T N [X] k , and

e 1 , e 2 ∈ Z such that X = e 1 • X 1 + e 2 • X 2 remains concen- trated, then E(X ) = e 1 •E(X 1 )+e 2 •E(X 2 ) and Var(X ) ≤ e 2 1 •Var(X 1 )+e 2 2 •Var(X 2
), up to negligible amounts. Also, subgaussian distributions with small enough parameters are necessarily concentrated:

Fact 2.3. Every distribution X on either T, T n or T N [X] k where each coefficient is σ-subgaussian where σ ≤ 1/ 32 ln(2)(λ + 1) is a concentrated distribution: a fraction ≥ 1 -2 -λ of its mass is in the interval [-1 4 , 1 4 ].

Distance and Norms

We denote as • p and • ∞ the standard norms for scalars and vectors over the real field or over the integers. By extension, the norms P (X) p and P (X) ∞ of a real or integer polynomial P are the norms of its coefficient vector. If P is a polynomial mod X N -1, we take the norm of its unique representative of degree ≤ N -1. If x is an vector in T k , we note x p = min u∈x+Z k ( u p ) is the p-norm of the representative of x with all coefficients in ] -1 2 , 1 2 ]. It satisfies the separation and the triangular inequalities, but it is not a norm because it lacks homogeneity 7 , and T k is not a vector space either. Instead, it is sub-homogeneous, i.e. it satisfies the property m • x p ≤ |m| x p , ∀m ∈ Z. By extension, we define P p for a polynomial P ∈ T N [X] as the p-norm of its unique representative in R[X] of degree ≤ N -1 and with coefficients in ] -1 2 , 1 2 ]. The notion of Lipschitz function always refers to the ∞ -distance: a function

f : T m → T n is said to be κ-Lipschitz if f (x) -f (y) ∞ ≤ κ x -y ∞ for all inputs x, y, where • ∞ is the -infinity norm. Definition 2.4 (Infinity norm over M p,q (T N [X])). Let A ∈ M p,q (T N [X]).
We define the infinity norm of A as

A ∞ = max i∈[[1,p]] j∈[[1,q]] a i,j ∞ .

Learning With Errors problem revisited

The Learning With Errors (LWE) problem was introduced by Regev in 2005 [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. The Ring variant of the same problem, called RingLWE, was introduced by Lyubashevsky, Peikert and Regev in 2010 [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF]. Both variants are nowadays extensively used for the constructions of lattice-based Homomorphic Encryption schemes. In the original definition [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF], a LWE sample has its right hand side on the torus and it is defined using continuous Gaussian distributions. Here, we work entirely on the real torus, employing the same formalism as the Scale Invariant LWE scheme in [START_REF] Cheon | Fully homomophic encryption over the integers revisited[END_REF], or LWE scale-invariant normal form in [START_REF] Chillotti | A homomorphic lwe based e-voting scheme[END_REF]. Without loss of generality, we refer to it as LWE.

Definition 2.5 ((Scale-Invariant) LWE (adapted from [START_REF] Cheon | Fully homomophic encryption over the integers revisited[END_REF]). Let n ≥ 1 be an integer, s be in Z n and ξ a distribution over R. We define LWE s,ξ as the distribution over T n ×T obtained by sampling a pair (a, b), where the left member a ∈ T n is chosen uniformly random and the right member b = a • s + e. The error e is a sample from the distribution ξ. Let S be a distribution over Z n . We can define the two following problems.

-Search problem: given arbitrarily many independent LWE s,ξ , find s ← S.

-Decision problem: distinguish, given arbitrarily many independent samples, between LWE s,ξ samples and uniformly random samples from T n × T, for a fixed s ← S.

Both the LWE search or decision problems are reducible to each other, and their average case is asymptotically as hard as worst-case lattice problems [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF].

In practice, both problems are also intractable, and their hardness increases with the entropy of the key set S (i.e. n if keys are binary) and α ∈]0, η ε (Z)[. Let s ∈ S be a fixed secret, we call phase the secret linear function ϕ s from T n × T to T defined as ϕ s (a, b) = b -s • a. In this case, if we compute the phase of a sample from the LWE s,ξ distribution, the result is the error e, which is very small. In other words, samples from the distribution LWE s,ξ are approximations of the kernel of the phase. We also remark that with this definition of phase, for all µ ∈ T, the trivial element (0, µ) is a preimage of µ by ϕ s .

This allows to reconstruct a symmetric-key variant Regev's encryption scheme [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. Given a discrete message space M ∈ T (for instance {0, 1 2 }), a message µ ∈ M is encrypted as an approximation of a random preimage ϕ -1 s (µ). Concretely, we sum the trivial element (0, µ) to a LWE s,ξ sample. The semantic security of the scheme is by definition equivalent to the LWE decisional problem. To decrypt a sample c = (a, b), we compute the phase ϕ s (c), which gives µ plus the error, and we round it to the nearest element in M. Decryption is correct with overwhelming probability 1 -2 -p provided that the Gaussian parameter α is O(R/ √ p) where R is the packing radius of M.

Regev's encryption scheme has also an asymmetric variant, where the public key is a list of random LWE s,ξ samples. Then, to encrypt a message µ ∈ M, one chooses a small random subset of the elements of the public key, and sums it to the trivial LWE sample (0, µ) of µ.

Homomorphic arithmetic on the torus

In this section we describe the generalizations of the LWE problem and of the GSW construction over the real torus T.

TLWE

In this section, we present a generalization of the LWE problem, following the footprint of [START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF] (that defined the General LWE problem) and [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF]. We call this generalization TLWE.

In the previous example, the phase was derived from the settings of the LWE cryptosystem. In TLWE, the phase becomes the central building block. All other notions are deduced from the algebraic properties of this linear function: message space, ciphertext space, encryption, decryption. In particular, this abstraction allows to unify every scale-invariant FHE scheme, based not only on LWE, RingLWE, Module-LWE [START_REF] Langlois | Worst-case to average-case reductions for module lattices[END_REF], but also on other problems like Approx-GCD or NTRU.

Definition 3.1 (Abstract TLWE problems). Let I be an ideal of Z[X], we call R = Z[X]/I and T I [X] = T[X]/I. A phase function is a Lipschitz morphism from a R-module M to T I [X].
The general TLWE problem is parametrized by an error distribution ξ on M , and a family (ϕ s ) s∈S of phase functions, indexed by a secret s. The homogeneous TLWE distribution for the secret s is U ker(ϕs) + ξ (sum of the uniform distribution over ker(ϕ s ) and an error from ξ). TLWE is λ-secure if neither of the following two problems can be solved in less than 2 λ bit operations, or with advantage 2 -λ by any PPT8 adversary:

-TLWE decision problem: given arbitrarily many samples in M , distinguish if they come from the uniform distribution on M or from U ker(ϕs) +ξ for a particular but unknown secret phase ϕ s . -TLWE search problem: given arbitrarily many samples from U ker(ϕs) +ξ for a particular secret phase ϕ s , find s.

If we instantiate this definition with I = (X + 1), then we get R = Z and T I [X] = T, and obtain scalar schemes. Setting M = T n+1 and the phase as ϕ s (a, b) = b -sa, we retrieve the previous scale-invariant LWE. By choosing instead M = (Z/qZ) n+1 with phase ϕ s (a, b) = (b -sa)/q and discrete Gaussian error, we retrieve the well known LWE mod q. If we set M = T and take ϕ s (x) = p.x where p is a secret integer, then the TLWE problem consists in recognizing approximations of multiples of 1/p, so the TLWE abstraction can express cryptosystems based on the (dual) approx-GCD problem. Now, if we take a different ideal, for instance I = (X N + 1), then the canonical choice for a phase: ϕ s (a, b) = b -sa expresses RingLWE and Module-LWE [START_REF] Langlois | Worst-case to average-case reductions for module lattices[END_REF], depending on the dimension of a. But again, other choices of phases are possible, for instance

ϕ (f,g) : T N [X] 2 → T N [X]
, (x, y) → f x -gy for small secret polynomials f, g, would allow to build FHE over scale invariant version of NTRU. Definition 3.2 (Canonical TLWE problem). Let k ≥ 1 be an integer, N be a power of 2 and α ∈ R ≥0 be a standard deviation. The canonical TLWE instantiation is the following: the secret key space S is composed by the binary vectors s ∈ B N [X] k that we assume to be uniformly chosen with n ≈ kN bits of entropy 9 . The phase ϕ s is defined over

M = T N [X] k × T N [X] by ϕ s ((a, b)) = b -s • a. It is by definition n-Lipschitz. The error distribution ξ is (0, D T N [X],α ) where D T N [X],α is the modular Gaussian distribution of standard deviation α over T N [X]
. By definition, a homogeneous TLWE sample can be constructed as (a, s • a + e) where a is uniformly drawn in T N [X] k (or in a sufficiently dense submodule 10 ) and e ← D T N [X],α .

Furthermore, we define as trivial the samples having the mask a = 0 and noiseless the samples having the standard deviation α = 0. Definition 3.2 can be viewed as the analogue of the General-LWE problem of [START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF] over the torus. It considers a continuum among anticyclic Module-LWE instances, between LWE (for N = 1) and RingLWE (for k = 1). However, we restrict the definition of canonical TLWE problem to only these particular cyclotomic instances, because they are the most efficient to implement with fast fourier transform. Also, the Gaussian error distribution can be sampled directly on the coefficients of the polynomials, rather than the general definition on the Lagrange basis.

If for all secret s, the distributions U ker ϕs + ξ is concentrated, Regev's cryptosystem can be abstracted as follow:

-The message space is the image T I [X] of ϕ s , -The ciphertext space is the domain M of ϕ s .

-The encryption of µ is an approximation of a random preimage ϕ -1 s (µ). Abstractly, a sample from U ϕ -1 s (µ) +ξ, and in the canonical form, the sum of the trivial sample (0, µ) plus a homogeneous sample from U ker(ϕs) +ξ.

-The (approximate) decryption of a ciphertext c is its image ϕ s (c).

From a practical point of view, the fact that the phase is κ-Lipschitz (with small κ) makes this decryption resilient to numerical errors, and allows to work with approximations. This cryptosystem is also additively homomorphic, by linearity of the phase. However, this cryptosystem is noisy, in a sense that after 9 An equivalence between LWE and binLWE, i.e. LWE with binary secret has been proven in [START_REF] Brakerski | Classical hardness of learning with errors[END_REF][START_REF] Micciancio | On the hardness of learning with errors with binary secrets[END_REF] encrypting and decrypting a message µ, the result is not exactly µ, but a close approximation µ + e where e ← ξ is a small error. There are use-cases, like floating point computations [START_REF] Cheon | Homomorphic encryption for arithmetic of approximate numbers[END_REF] or in general differential privacy, where these approximations of the plaintext are considered valid. However, if we need an exact result, we have two options. The first one is the historical choice in Regev cryptosystem: restrict the message space to a discrete subset, whose packing radius is larger than the amplitude of ξ, and retrieve the exact plaintext by rounding the phase. If rounding is easy to setup in practice, its non-linearity complicates the correctness analysis, especially when the current sample is not fresh, but rather a linear combination of previous samples. Also, restricting the message space prevents some floating point applications and bounds plaintext operations to just small abelian groups. The second option, consists in taking E(ξ) = 0, and thus, the plaintext becomes the expectation of the phase. This option does not require to restrict the message space and works with infinite precision over the continuous one. Furthermore, the continuity and linearity of the expectation ease the analysis of morphism properties and of the noise propagation, but it requires to properly define the probability space Ω, which we do now. Definition 3.3 (The Ω-probability space). Since samples are either independent (random, noiseless, or trivial) fresh c ← TLWE T N [X],s,α (µ), or linear combination c = p i=1 e i •c i of other samples, the probability space Ω is the product of the probability spaces of each individual fresh samples c with the TLWE distributions defined in definitions 3.2, and of the probability spaces of all the coefficients (e 1 , . . . , e p ) ∈ Z N [X] p or Z p that are obtained with randomized algorithm.

In other words, instead of viewing a TLWE sample as a fixed value which is the result of one particular event in Ω, we will consider all the possible values at once, and make statistics on them.

We now define some important functions on TLWE samples: message, error, noise variance, and noise norm. These functions are well defined mathematically, and can be used in the analysis of various algorithms. However, they cannot be directly computed or approximated in practice. Definition 3.4. Let c be a random variable ∈ T N [X] k+1 , which we will interpret as a TLWE sample. All probabilities are on the Ω-space. We say that c is a valid TLWE sample if and only if there exists a key s ∈ B N [X] k such that the distribution of the phase ϕ s (c) is concentrated. If c is trivial, all keys s are equivalent, else the mask of c is uniformly random, so s is unique. We then define:

the message of c, denoted as msg(c) ∈ T N [X] is the expectation of ϕ s (c); the error, denoted Err(c), is equal to ϕ s (c) -msg(c); -Var(Err(c)) denotes the variance of Err(c), which is by definition also equal to the variance of ϕ s (c);

finally, Err(c) ∞ denotes the maximum amplitude of Err(c) (possibly with overwhelming probability) 11 .

Unlike the classical decryption algorithm, the message function can be viewed as an ideal black box decryption function, which works with infinite precision even if the message space is continuous. Provided that the noise amplitude remains smaller than 1 4 , the message function is perfectly linear. Using these intuitive and intrinsic functions will considerably ease the analysis of all algorithms in this paper. In particular, we have the following fact concerning linear combinations of TLWE samples.

(c) ∞ ≤ p i=1 e i 1 • Err(c i ) ∞ . If the last bound is < 1
4 , then c is necessarily a valid TLWE sample (under the same key s).

TGSW

As presented in previous section, TLWE samples can be linearly combined to obtain a new sample encrypting the linear combination of the messages. But when it comes to non linear operations on the samples, TLWE seems to miss some properties. In order to repair this lack, several schemes based on the different variants of LWE have been proposed. Between them, the most known solutions are the BGV constructions [START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF] and the GSW constructions [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF]. We focus on this latter and on the improvements proposed in [START_REF] Alperin-Sheriff | Faster bootstrapping with polynomial error[END_REF]. The security of GSW is based on the LWE problem and the construction is fully homomorphic. In this section we present a generalized scale invariant version of the FHE scheme GSW [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF], that we call TGSW (in the same line as TLWE). The scheme relies on a gadget decomposition function, which we also extend to polynomials. But most importantly, the novelty is that our function is an approximate decomposition, up to some precision parameter. This allows to improve running time and memory requirements for a small amount of additional noise. Definition 3.6 (Abstract Gadget Decomposition). Let M be a R-module (as in Definition 3.1). We say that an efficient algorithm Dec H,β, (v) is a valid decomposition on the gadget H ∈ M with quality β ∈ R >0 and precision ∈ R >0 if and only if, for any TLWE sample v ∈ T N [X] k+1 , it efficiently and publicly outputs a small vector u ∈ R such that u ∞ ≤ β and u • H -v ∞ ≤ . Furthermore, the expectation of u • H -v must to be equal to 0 when v is uniformly distributed in M .

To fix the ideas, we give an efficient canonical example of gadget decomposition, whose purpose is to decompose canonical TLWE ciphertexts. Overall, the canonical gadget is a block diagonal matrix, each column block containing a geometric decreasing sequence of constant polynomials in T ⊆ T N [X], and the corresponding decomposition function is the greedy algorithm.

In theory, decomposition algorithms should be randomized to ensure that the distribution of all error coefficients remain independent. In practice, our average case theorems already rely on an independence Heuristic 3.11 that we describe later in this section, which explains why we use a deterministic canonical decomposition.

Lemma 3.7 (Canonical Gadget Decomposition). Let M = T N [X] k+1 be the domain of the canonical TLWE, and and B g be two positive integers, the canonical gadget are the = (k + 1) rows of the matrix H ∈ M (k+1) ,k+1 (T N [X]) as in [START_REF] Albrecht | Homomorphic encryption security standard[END_REF].

H =              1/B g .
0 . . . 1/B g              ∈ M (k+1) ,k+1 (T N [X]). (1)
Then for β = B g /2 and = 1/2B g , Algorithm 1 is a valid Dec H,β, .

Algorithm 1 Gadget Decomposition of a TLWE sample

Input: A TLWE sample (a, b) = (a1, . . . , a k , b = a k+1 ) ∈ TN [X] k × TN [X] Output: A combination [u1,1, . . . , u k+1, ] ∈ R (k+1)
1: For each ai choose the unique representative N -1 j=0 ai,jX j , with ai,j ∈ T, and set āi,j the closest multiple of 1 B g to ai,j 2: Decompose each āi,j uniquely as p=1 āi,j,p

for i = 1 to k + 1 4: for p = 1 to 5: ui,p = N -1 j=0 āi,j,pX j ∈ R 6: Return (ui,p) i,p Proof. Let v = (a, b) = (a 1 , . . . , a k , b = a k+1 ) ∈ T N [X] k+1 be a TLWE sample, given as input to Algorithm 1. Let u = [u 1,1 , . . . , u k+1, ] ∈ R (k+1) be the corresponding output by construction u ∞ ≤ B g /2 = β. Let dec = u • H -v. For all i ∈ [[1, k + 1]] and j ∈ [[0, N -1]], we have by construction deci,j = p=1 u i,p • 1 B p g -a i,j = āi,j -a i,j .
Since āi,j is defined as the nearest multiple of 1 B g on the torus, we have |ā i,j -

a i,j | ≤ 1/2B g = .
The decomposition error dec has therefore a concentrated distribution when v is uniform. We now verify that it is zero-centered. We call f the function from T to T which rounds an element x to its closest multiple of 1 B g and the function g the symmetry defined by g(x) = 2f (x) -x on the torus. We easily verify that the E( deci,j ) is equal to E(a i,j -f (a i,j )) when a i,j has uniform distribution, which is equal to E(g(a i,j ) -f (g(a i,j ))) when g(a i,j ) has uniform distribution, also equal to E(f (a i,j ) -a i,j ) = -E( deci,j ). Thus, the expectation of dec is 0.

We are now ready to define TGSW samples, and to extend the notions of phase of valid sample, message and error of the samples. Definition 3.8 (Abstract TGSW samples). Consider the TLWE cryptosystem of error distribution ξ and of secret phase ϕ s on the R-module M , and its associated gadget decomposition Dec H,β,ε over H ∈ M . We say that C ∈ M is a fresh TGSW sample of µ ∈ R if and only if C = Z +µ • H where each element of Z ∈ M is an Homogeneous TLWE sample (of 0) and error ξ. Reciprocally, we say that an element C ∈ M is a valid TGSW sample for the key s if and only if there exists a unique polynomial µ ∈ R (modulo H •R) such that each row of C -µ • H is a valid TLWE sample of 0 for the key s. We call the polynomial µ the message of C, and we denote it by msg(C). By extension, the phase of C denoted as ϕ s (C) ∈ T I [X] is the vector of the TLWE phases of each row of C. In the same way, we define the error of C, denoted Err(C), as the list of the TLWE errors of each row of C.

If one instantiate the previous definition with the canonical TLWE (Definition 3.2) and the canonical decomposition algorithm (Lemma 3.7), one obtains the canonical TGSW samples over T N [X] (k+1) , of binary key s ∈ B N [X] k , and Gaussian error of standard deviation α. Fresh canonical TGSW samples of a message µ ∈ Z N [X] are denoted TGSW s,α (µ). Since TGSW samples are essentially vectors of TLWE samples, they are naturally compatible with linear combinations. And both phase and message functions remain linear. Fact 3.9. Given p valid TGSW samples C 1 , . . . , C p of messages µ 1 , . . . , µ p under the same key, and with independent error coefficients, and given p integer polynomials e 1 , . . . , e p ∈ R, the linear combination

C = p i=1 e i • C i is a sample of µ = p i=1 e i • µ i , with variance Var(C) = p i=1 e i 2 2 • Var(C i ) 1/2
and noise infinity norm

Err(C) ∞ = p i=1 e i 1 • Err(C i ) ∞ .
Also, the phase is still (1 + kN )-Lipschitz for the infinity norm.

Fact 3.10. For all A ∈ M p,k+1 (T N [X]), ϕ s (A) ∞ ≤ (1 + kN ) A ∞ ,
where the key s is with binary coefficients.

Heuristic In order to characterize the average case behaviour of our homomorphic operations, we shall rely on the heuristic assumption of independence below. This heuristic will only be used for practical average-case bounds. Our worst-case theorems and lemmas based on the infinite norm do not use it at all. Assumption 3.11 (Independence Heuristic). All the coefficients of the errors of TLWE or TGSW samples that occur in all the linear combinations we consider are independent and concentrated. More precisely, they are σ-subgaussian where σ is the square-root of their variance.

This assumption allows us to bound the variance of the noise instead of its norm, and to provide realistic average-case bounds which often correspond to the square root of the worst-case ones. The error can easily be proved subgaussian, since each coefficient is always obtained by convolving Gaussians or zero-centered bounded uniform distributions. What remains heuristic is the independence between all the coefficients. Indeed, dependencies between coefficients may affect the variance of their combinations in both directions. The independence of coefficients can be proved if we add enough entropy in the decomposition algorithm (and if we increase all the other parameters to compensate), but as noticed in [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF], this work-around seems just to be a proof artifact, and is experimentally not needed. Since our average-case corollaries should reflect practical results, we leave the independence of subgaussian samples as a heuristic assumption. In Section 8, we show an experimental validation of our independence assumption.

Products

Linear operations are not sufficient to achieve Fully Homomorphic Encryption. The original definition of GSW in [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF] proposed a construction to achieve a homomorphic internal product between the integer messages of two GSW ciphertexts (which live in the ring R). Due to an asymetry in the noise propagation, it was noticed in [START_REF] Gorbunov | Attribute-based encryption for circuits[END_REF], [START_REF] Brakerski | Lattice-based FHE as secure as PKE[END_REF] and [START_REF] Alperin-Sheriff | Faster bootstrapping with polynomial error[END_REF] that GSW ciphertext are particularly suited to evaluate long chains of products, or branching programs. In [START_REF] Brakerski | Lattice-based fully dynamic multi-key FHE with short ciphertexts[END_REF], the authors noticed that for these circuits, a large part of the computations in the GSW internal product was subsequently unused, if the final goal was just to decrypt the message. Not performing these computations yields a huge polynomial speedup. In this section, we provide an intrinsic explanation for the correctness of these partial computations, by defining an external product between a TGSW ciphertext and a TLWE samples, and prove that it is homomorphic to the external R-module product between the two plaintexts. A direct comparison between the external and internal product algorithms retroactively explains the speed-up of [START_REF] Brakerski | Lattice-based fully dynamic multi-key FHE with short ciphertexts[END_REF]. It also emphasizes the asymmetric nature of TGSW products: the reason why branching algorithms or long chains of fresh multiplications are much more efficient to evaluate with GSW than balanced binary trees, is not only the asymmetry in the noise propagation, but also because only the first ones can be mapped to the simple plaintext external product. Definition 3.12 (External product). We define the product as

: TGSW × TLWE -→ TLWE (A, b) -→ A b = Dec H,β, (b) • A,
where Dec H,β, is the gadget decomposition described in Algorithm 1.

The formula is almost identical to the classical product defined in the original GSW scheme in [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF], except that only one vector needs to be decomposed. For this reason, the following theorem shows that we get almost the same noise propagation formula, with an additional term that comes from the approximations in the decomposition.

Err(A b) ∞ ≤ (k + 1) N β Err(A) ∞ + µ A 1 (1 + kN ) + µ A 1 Err(b) ∞
= z b + (0, µ b ), where z b is a TLWE encryption of 0. Let Err(A) ∞ = ϕ s (Z A ) ∞ = η A Err(b) ∞ = ϕ s (z b ) ∞ = η b . Let u = Dec H,β, (b) ∈ R (k+1) . By definition A b is equal to A b = u • A = u • Z A + µ A • (u • H).
From definition 3.6, we have that u

• H = b + dec , where dec ∞ = u • H -b ∞ ≤ . So A b = u • Z A + µ A • (b + dec ) = u • Z A + µ A • dec + µ A • z b + (0, µ A • µ b ). Then the phase (linear function) of A b is ϕ s (A b) = u • Err(A) + µ A • ϕ s ( dec ) + µ A • Err(b) + µ A µ b .
Taking the expectation, we get that msg(A b) = 0 + 0 + 0 + µ A µ b , and so

Err(A b) = ϕ s (A b) -µ A µ b .
Then thanks to Fact 3.10, we have

Err(A b) ∞ ≤ u • Err(A) ∞ + µ A • ϕ( dec ) ∞ + µ A • Err(b) ∞ ≤ (k + 1) N βη A + µ A 1 (1 + kN ) dec ∞ + µ A 1 η b .
The result follows.

We similarly obtain the more realistic average-case noise propagation, based on the independence heuristic 3.11, by bounding the Gaussian variance instead of the amplitude.

Corollary 3.14 (Average-case External Product). Under the same conditions of Theorem 3.13 and under Heuristic 3.11, we have that

Var(Err(A b)) ≤ (k+1) N β 2 Var(Err(A))+(1+kN ) µ A 2 2 2 + µ A 2 2 Var(Err(b)). Proof. Let ϑ A = Var(Err(A)) = Var(ϕ s (Z A )) and ϑ b = Var(Err(b)) = Var(ϕ s (z b ))
. By using the same notations as in the proof of theorem 3.13 we have that the error of

A b is Err(A b) = u • Err(A) + µ A • ϕ s ( dec ) + µ A • Err(b)
and thanks to assumption 3.11 and lemma 3.10, we have :

Var(Err(A b)) ≤ Var(u • Err(A))) + Var(µ A • ϕ( dec )) + Var(µ A • Err(b)) ≤ (k + 1) N β 2 ϑ A + (1 + kN ) µ A 2 2 2 + µ A 2 2 ϑ b .
The last corollary describes exactly the classical internal product between two TGSW samples, already presented in [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF][START_REF] Alperin-Sheriff | Faster bootstrapping with polynomial error[END_REF][START_REF] Gama | Structural lattice reduction: Generalized worst-case to average-case reductions[END_REF][START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF] with adapted notations. As we mentioned before, it consists in (k + 1) independent computations of the product. As for the external product, we analyze the noise growth in both worst and average case.

Corollary 3.15 (Internal Product). Let the product

: TGSW × TGSW -→ TGSW (A, B) -→ A B =    A b 1 . . . A b (k+1)    =    Dec H,β, (b 1 ) • A . . . Dec H,β, (b (k+1) ) • A    ,
with A and B two valid TGSW samples of messages µ A and µ B respectively and

b i corresponding to the i-th line of B. Then A B is a TGSW sample of message µ A • µ B and Err(A B) ∞ ≤ (k + 1) N β Err(A) ∞ + µ A 1 (1 + kN ) + µ A 1 Err(B) ∞ in the worst case. If Err(A B) ∞ ≤ 1/4 we are guaranteed that A B is a valid TGSW sample.
Furthermore, by assuming the heuristic 3.11, we have that

Var(Err(A B)) ≤ (k+1) N β 2 Var(Err(A))+(1+kN ) µ A 2 2 2 + µ A 2 2 Var(Err(b))
in the average case.

Proof. Let A and B be two TGSW samples, and µ A and µ B their message. Let h i denote the i-th row of the gadget matrix H. By definition, the i-th row of

B encodes µ B • h i , so the i-th row of A B encodes (µ A µ B ) • h i . This proves that A B encodes µ A µ B . Since the internal product A B consists in (k + 1)
independent runs of the external products A b i , the noise propagation formula directly follows from Theorem 3.13 and Corollary 3.14.

CMux gate

With the homomorphic operations described until now it is possible to construct small circuits. To ease these constructions, we now define the controlled selector gate (or CMux gate where C stands for controlled), which can be considered as the bridge between the external product arithmetic, and high level circuits.

The CMux gate has three input slots and one output slot: one control input slot represented by a TGSW sample on the integer message space (here restricted to {0, 1}), two data input slots each carrying a TLWE sample on the continuous message space T N [X], and one data output slot, also of type TLWE. The controlled MUX gate CMux(C, d 1 , d 0 ) homomorphically outputs either the message of d 1 or d 0 depending on the Boolean value in C, without decrypting any of the three cipertexts. In practice, it returns C (d 1 -d 0 ) + d 0 .

In leveled circuits, the rule to build valid circuits using CMux gates (Figure 1) is that all control wires (TGSW) are freshly generated by the user, and the data input ports of our gates can be either freshly generated or connected to a data output or to another gate. In Section 6.2, we propose an efficient way to transform a TLWE sample in a TGSW sample, in order to make the circuits entirely composable (and so relax the condition requiring freshly generated control wires). Proof. The formulas for the noise in the worst and average cases are a consequence of Theorem 3.13 and Corollary 3.14. However, we need to explain why there is a max instead of the sum we would obtain by blindly applying these results. -

Lemma 3.16 (CMux gate). Let d 0 , d 1 ∈ TLWE s (T N [X]) and C ∈ TGSW s ({0, 1}). Then msg(CMux(C, d 1 , d 0 )) = msg(C)?msg(d 1 ):msg(d 0 ). Fur- thermore -Err(CMux(C, d 1 , d 0 )) ∞ ≤ max( Err(d 0 ) ∞ , Err(d 1 ) ∞ ) + η(C), -Var(Err(CMux(C, d 1 , d 0 ))) ≤ max(Var(Err(d 0 )), Var(Err(d 1 ))) + ϑ(C), in the conditions of Assumption 3.11, where η(C) = (k + 1) N β Err(C) ∞ + (kN + 1) and ϑ(C) = (k + 1) N β 2 Var(Err(C)) + (kN + 1) 2 . TGSW µC ηC , ϑC TLWE µd 0 ηd 0 , ϑd 0 TLWE µd 1 ηd 1 , ϑd 1 0 1 TLWE µ = µC • (µd 1 -µd 0 ) + µd 0 η = max(ηd 0 , ηd 1 ) + O(ηC ) ϑ = max(ϑd 0 , ϑd 1 ) + O(ϑC )
Let d = d 1 -d 0 , recall that in the proof of Theorem 3.13, the expression of C d is Dec H,β, (d) • Z C +µ C dec +µ C z d +(0, µ C •µ d ), where C = Z C +µ C •H and d = z d + (0, µ d ), Z C
Dec H,β, (d) • Z C of norm ≤ (k + 1) N βη C ; -µ C dec of norm ≤ (kN + 1) ; -z d0 + µ C (z d1 -z d0 ), which is either z d1 or z d0 , depending on the value of µ C ; -(0, µ d0 + µ C • (µ d1 -µ d0
)), which is the trivial sample of the output message µ C ?µ d1 :µ d0 , and is not part of the noise.

Thus, summing the three terms concludes the proof. For the average case, the formula is proven in the same way by using the results of Corollary 3.14 and replacing all norm inequalities by variance inequalities.

Notations In the rest of the paper, the notation TLWE is used to denote the (canonical scalar) binary TLWE problem (i.e. the LWE problem described in Section 2). To distinguish it from the Ring mode, we introduce the notation TRLWE. The TGSW samples are only used in ring mode, but we use the notation TRGSW to keep uniformity with the TRLWE notation. Furthermore, we distinguish the TLWE keys from the TRLWE keys by using the respective notations K and K, instead of the generic s used until now. We also use the following convention in the rest of the paper: for all n = kN , a binary vector K ∈ B n can be interpreted as a TLWE key, or alternatively as a TRLWE key K ∈ B N [X] k having the same sequence of coefficients. Namely, K i is the polynomial 4 Building blocks for TFHE TLWE and TRLWE samples are largely used in the rest of the paper, and the schemes we describe switch from a type to another constantly. To do that, three basic tools are used: the key switching, the sample extraction and the blind rotation. Each one of them is described in detail in next sections.

Key Switching revisited

We revisit the well-known key switching procedure, largely described in the literature. The principal interest of key switching, as the name suggests, is to switch between keys in different parameter sets.

We show that this procedure has a larger potential. It allows to switch between the scalar and polynomial message spaces T and T N [X], and more generally, it has the ability to homomorphically evaluate linear morphisms f from any Z-module T p to T N [X]. We define two key switching flavors, one for a publicly known f , and one for a secret f encoded in the key switching key.

In the following, we denote PubKS(f, KS, c) and PrivKS(KS (f ) , c) the output of Algorithm 2 and Algorithm 3, taking in input the functional key switching keys KS and KS (f ) respectively and a TLWE ciphertext c.

As the inputs and the outputs are instantiated with different parameter sets and we want to keep the same name for the variables n, N, α, , B g , . . . , we add an under bar to the output parameters to distinguish them from the input parameters. From now on, we use the letter γ to indicate the standard deviation of the key-switching key. The variable t represents the precision of the binary decomposition.

Algorithm 2 TLWE-to-T(R)LWE Public Functional Key Switching

Input: p TLWE ciphertexts c (z) = (a (z) , b (z) ) ∈ TLWE K (µz) for z = 1, . . . , p, a public R-Lipschitz morphism f : T p → TN [X], and KSi,j ∈ T(R)LWE K ( K i 2 j ). Output: A T(R)LWE sample c ∈ T(R)LWE K (f (µ1, . . . , µp)) 1: for i ∈ [[1, n]] do 2: Let ai = f (a (1)
i , . . . , a

(p) i ) 3: let ãi be the closest multiple of 1 2 t to ai, thus ãi -ai ∞ < 2 -(t+1) 4:
Binary decompose each ãi = t j=1 ãi,j • 2 -j where ãi,j ∈ BN [X] 5: end for 6: return (0, f (b (1)

, . . . , b (p) )) -n i=1 t j=1 ãi,j • KSi,j Theorem 4.1. (Public Key Switching) Given p TLWE ciphertexts c (z) ∈ TLWE K (µ z ), a public R-Lipschitz morphism f : T p → T N [X] of Z-modules, and KS i,j ∈ T(R)LWE K,γ ( Ki 2 j ) with standard deviation γ, Algorithm 2 outputs a T(R)LWE sample c ∈ T(R)LWE K (f (µ 1 , . . . , µ p )) such that: -Err(c) ∞ ≤ R Err(c) ∞ + ntN A KS + n2 -(t+1) (worst case), -Var(Err(c)) ≤ R 2 Var(Err(c)) + ntN ϑ KS + n2 -2(t+1) (average case),
where A KS and ϑ KS = γ 2 are respectively the amplitude and the variance of the error of KS.

Proof. Let c be the output of Algorithm 2 and b = f (b (1) , . . . , b (p) ) then

ϕ K (c) = b - n i=1 t j=1 ãi,j • ϕ K (KS i,j ) = b - n i=1 t j=1 ãi,j ( K i 2 j -Err(KS i,j )) = b - n i=1 K i ãi - n i=1 t j=1 ãi,j Err(KS i,j ) = b - n i=1 K i a i - n i=1 t j=1 ãi,j Err(KS i,j ) + n i=1 K i • (a i -ãi ) = f (b (1) , . . . , b (p) ) - n i=1 f (a (1)
i , . . . , a

(p) i )K i - n i=1 t j=1 ãi,j Err(KS i,j ) + n i=1 K i • (a i -ãi ) = f (b (1) , . . . , b (p) ) - n i=1 K i (a (1) i , . . . , a (p) i )
-

n i=1 t j=1 ãi,j Err(KS i,j ) + n i=1 K i • (a i -ãi ) = f (ϕ K (c (1) )), . . . , ϕ K (c (p) )) - n i=1 t j=1 ãi,j Err(KS i,j ) + n i=1 K i • (a i -ãi )
Applying the expectation on each side, we obtain msg(c) on the left, and f (µ 1 , . . . , µ p ) on the right, since all the error terms have expectation 0 and f is linear. For the worst-case bound, we obtain that:

Err(c) ∞ = ϕ K (c) -msg(c) ∞ ≤ f (Err(c (1) ), . . . , Err(c (p) )) ∞ + ntN A KS + N n2 -(t+1) ≤ R Err(c) ∞ + ntN A KS + N n2 -(t+1)
since f is R-Lipschitz. For the average-case, we have a similar proof:

Var(Err(c)) = Var(ϕ K (c) -msg(c)) ≤ Var(f (Err(c (1) ), . . . , Err(c (p) ))) + ntN ϑ KS + N n2 -2(t+1) ≤ R 2 Var(Err(c)) + ntN ϑ KS + N n2 -2(t+1) .
Remark 2. The TLWE-to-T(R)LWE public key switching procedure we described, allows to switch between the scalar message space T and the polynomial message space T N [X]. The same procedure can be used to perform a TLWE-to-TLWE public key switching and switch between scalar message spaces. Here is why we put parentheses around the R of T(R)LWE. In practice, the key switching key is composed by TLWE encryptions of the old secret key, and the noise growth formulas remain the same, with the factor N equal to 1. We use the TLWE-to-TLWE public key switching in Section 5.3. Furthermore, observe that the public key-switching procedure can be used from TRLWE to TRLWE: in this case the function f is just the identity function.

We have a similar result when the function is private. In this algorithm, we extend the input secret key K by adding a (n + 1)-th coefficient equal to -1, so that ϕ K (c) = -K • c.

Algorithm 3 TLWE-to-T(R)LWE Private Functional Key Switching

Input: p TLWE ciphertexts c (z) ∈ TLWE K (µz), a key switching key KS (f ) z,i,j ∈ T(R)LWE K (f (0, . . . , 0, K i 2 j , 0, . . . , 0)) where f : T p → TN [X] is a secret R-Lipschitz morphism and K i 2 j is at position z (also, Kn+1 = -1 by convention). Output: A T(R)LWE sample c ∈ T(R)LWE K (f (µ1, . . . , µp)). 1: for i ∈ [[1, n + 1]], z ∈ [[1, p]] do 2: Let c(z) i be the closest multiple of 1 2 t to c (z) i , thus |c (z) i -c (z) i | < 2 -(t+1) 3:
Binary decompose each c(z

) i = t j=1 c(z) i,j • 2 -j where c(z) i,j ∈ {0, 1} 4: end for 5: return -p z=1 n+1 i=1 t j=1 c(z) i,j • KS (f ) z,i,j Theorem 4.2. (Private Key Switching) Given p TLWE ciphertexts c (z) ∈ TLWE K (µ z ), and
KS (f ) i,j ∈ T(R)LWE K,γ (f (0, . . . , Ki 2 j , . . . , 0)) where f : T p → T N [X] is a private R-Lipschitz morphism of Z-modules, Algorithm 3 outputs a T(R)LWE sample c ∈ T(R)LWE K (f (µ 1 , . . . , µ p )) such that: -Err(c) ∞ ≤ R Err(c) ∞ + (n + 1)R2 -(t+1) + pt(n + 1)A KS (worst-case), -Var(Err(c)) ≤ R 2 Var(Err(c)) + (n + 1)R 2 2 -2(t+1) + pt(n + 1)ϑ KS (average case),
where A KS and ϑ KS = γ 2 are respectively the amplitude and the variance of the error of KS (f ) .

Proof. Let c be the output of Algorithm 3 and b = f (b (1) , . . . , b (p) ) then:

ϕ K (c) = - p z=1 n+1 i=1 t j=1 c(z) i,j • ϕ K (KS (f ) z,i,j ) = - p z=1 n+1 i=1 t j=1 c(z) i,j f (0, . . . , K i 2 j , . . . , 0) + Err(KS (f ) i,j ) = - p z=1 n+1 i=1 t j=1 c(z) i,j f (0, . . . , K i 2 j , . . . , 0) - p z=1 n+1 i=1 t j=1 c(z) i,j Err(KS (f ) z,i,j ) We set KS = p z=1 n+1 i=1 t j=1 c(z) i,j Err(KS (f ) z,i,j ). Then: = - n+1 i=1 p z=1 f (0, . . . , t j=1 c(z) i,j K i 2 j , . . . , 0) -KS = - n+1 i=1 p z=1 f (0, . . . , K i • c(z) i , . . . , 0) - n+1 i=1 p z=1 f (0, . . . , K i • (c (z) i -c (z) i ), . . . , 0) -KS = - n+1 i=1 K i f (c (1)
i , . . . , c

(z) i , . . . , c (p) i ) - n+1 i=1 K i f (c (1)
i -c

(1) i , . . . , c(p) i -c (p) i ) -KS = f (- n+1 i=1 K i c (1)
i , . . . , -

n+1 i=1 K i c (p) i ) - n+1 i=1 K i f (c (1)
i -c

(1) i , . . . , c(p) i -c (p) i ) -KS = f (ϕ K (c (1) ), . . . , ϕ K (c (p) )) - n+1 i=1 K i f (c (1)
i -c

(1) i , . . . , c(p) i -c (p) i ) -KS = f (µ 1 + Err(c (1) ), . . . , µ p + Err(c (p) )) - n+1 i=1 K i f (c (1)
i -c

(1) i , . . . , c(p) i -c (p) i ) -KS
By linearity of f and since the expectation of the error terms are 0, the message of the right side is equal to f (µ 1 , . . . , µ p ). For the worst-case bound on the noise, as f is R-Lipschitz, we obtain:

Err(c) ∞ = ϕ K (c) -msg(c) ∞ ≤ R Err(c) ∞ + (n + 1)R2 -(t+1) + pt(n + 1)A KS
The proof for the variance is similar.

Sample Extraction.

A TRLWE message is a polynomial with N coefficients, which can be viewed as N slots over T. It is easy to homomorphically extract a coefficient as a scalar TLWE sample with the same key. We recall that a binary TLWE key K ∈ B n can be interpreted as a TRLWE key K ∈ B N [X] k having the same sequence of coefficients, and vice-versa. Given a TRLWE sample c = (a, b) ∈ TRLWE K (µ) and a position p ∈ [0, N -1], we call SampleExtract p (c) the TLWE sample (a, b) where b = b p and a N (i-1)+j+1 is the (p -j)-th coefficient of a i (using the N -antiperiodic indexes). This extracted sample encodes the p-th coefficient µ p with at most the same noise variance or amplitude as c. In the rest of the paper, we will simply write SampleExtract(c) when p = 0.

In Section 5, we show how the KeySwitching and the SampleExtract procedures are used to efficiently pack data, unpack and move data across the slots, and how it differs from usual packing techniques.

Blind Rotate

The BlindRotate algorithm multiplies the polynomial encrypted in the input TRLWE ciphertext by an encrypted power of X. The effect produced is a rotation of the coefficients. The algorithm consists in two parts. The first one (line 3) is the rotation by a known power of X The second one (loop at line 4) is the rotation by a secret power of X, which is performed by using the CMux gate, described in Section 3.4.

Algorithm 4 BlindRotate

Output: A TRLWE sample of X -ρ • v where ρ = b -p i=1 si.ai mod 2N with key K 3: ACC ← X -b • c 4: for i = 1 to p 5: ACC ← CMux(Ci, X a i • ACC, ACC) 6: return ACC Theorem 4.3. Let H ∈ M (k+1) ,k+1 (T N [X]
) the gadget matrix and Dec H,β, its efficient approximate gadget decomposition algorithm with quality β and precision defining TRLWE and TRGSW parameters. Let α ∈ R ≥0 be a noise parameter, K ∈ B n be a TLWE secret key and K ∈ B N [X] k be its TRLWE interpretation. Given one sample c ∈ TRLWE K (v) with v ∈ T N [X], p + 1 integers a 1 , . . . , a p and b ∈ Z/2N Z, and p TRGSW ciphertexts C 1 , . . . , C p , where each

C i ∈ TRGSW K,α (s i ) for s i ∈ B. Algorithm 4 outputs a sample ACC ∈ TRLWE K (X -ρ • v) where ρ = b - -Err(ACC) ∞ ≤ Err(c) ∞ + p(k + 1) N βA C + p(1 + kN ) (worst case), -Var(Err(ACC)) ≤ Var(Err(c))+p(k +1) N β 2 ϑ C +p(1+kN ) 2 (average case),
where ϑ C = α 2 and A C are the variance and amplitudes of Err(C i ).

Proof. Theorem 4.3 follows from the fact that algorithm 4 calls p times the CMux evaluation.

We define BlindRotate(c, (a 1 , . . . , a p , b), (C 1 , . . . , C p )), the procedure described in Algorithm 4 that outputs the TRLWE sample ACC as in Theorem 4.3.

Leveled Homomorphic Encryption

The main goal of Homomorphic Encryption is to perform computations on encrypted data. In previous sections we described all the different tools to manipulate the ciphertexts. In this section we show how to use them to construct homomorphic circuits. In particular, we describe the evaluation of a random function via its look-up table and we propose two packing techniques that can be used to accelerate the evaluation.

Various packing techniques have already been proposed for homomorphic encryption: the Lagrange embedding in Helib [START_REF] Halevi | Algorithms in helib[END_REF][START_REF] Halevi | Helib -an implementation of homomorphic encryption[END_REF], the diagonal matrices encoding in [START_REF] Hiromasa | Packing messages and optimizing bootstrapping in gsw-fhe[END_REF] or the CRT encoding in [START_REF] Smart | Fully homomorphic encryption with relatively small key and ciphertext sizes[END_REF][START_REF] Smart | Fully homomorphic SIMD operations[END_REF][START_REF] Benarroch | Fhe over the integers: Decomposed and batched in the post-quantum regime[END_REF]. The message space is often a finite ring (e.g. Z/pZ), and the packing function is in general chosen as a ring isomorphism that preserves the structure of (Z/pZ) N . This way, elementary additions or products can be performed simultaneously on N independent slots, and thus, packing is in general associated to the concept of batching a single operation on multiple datasets. These techniques can have some limitations, especially if in the whole program, each function is only run on a single dataset, and most of the slots are unused. This is particularly true in the context of GSW evaluations, where functions are split into many branching algorithms or automata, that are each executed only once.

In the rest of the paper, packing refers to the canonical coefficients embedding function, that maps N TLWE messages µ 0 , . . . , µ N -1 ∈ T into a single TRLWE message µ(X) = N -1 i=0 µ i X i . This function is a Z-module isomorphism. Messages can be homomorphically unpacked from any slot using the (noiseless) SampleExtract procedure, described in Section 4.2. Reciprocally, we can repack, move data across the slots, or clear some slots by using our public functional key switching from Algorithm 2 to evaluate respectively the canonical coefficient embedding function (i.e. the identity), a permutation, or a projection. Since these functions are 1-Lipschitz, by Theorem 4.1, these keyswitch operations only induce a linear noise overhead. It is arguably more straightforward than the permutation network technique used in Helib. But as in [START_REF] Benarroch | Fhe over the integers: Decomposed and batched in the post-quantum regime[END_REF][START_REF] Cheon | Batch fully homomorphic encryption over the integers[END_REF][START_REF] Coron | Scale-invariant fully homomorphic encryption over the integers[END_REF], our technique relies on a circular security assumption, even in the leveled mode since our keyswitching key encrypts its own key bits 12 .

We now analyze how packing can speed-up TRGSW leveled computations, first for look-up tables or random functions, and then for most arithmetic functions.

Arbitrary functions and Look-Up Tables

The first class of functions we analyze are arbitrary functions f : B d → T s . Such functions can be expressed via a Look-Up Table (LUT), containing the list of 2 d input values (each one composed by d bits) and corresponding LUT values for the s sub-functions (1 element in T per sub-function f j ). We denote the LUT values with σ j,h ∈ T, where j ∈ [[0, s -1]] is the sub-function index, and

h ∈ [[0, 2 d -1]] is the input index.
In order to compute f (x) = (f 0 (x), f 1 (x), . . . , f s-1 (x)), where x = d-1 i=0 x i 2 i is a d-bit integer, the classical evaluation of such function, as proposed in [START_REF] Brakerski | Lattice-based FHE as secure as PKE[END_REF][START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF], consists in evaluating the s sub-functions f 0 , f 1 , . . . , f s-1 separately. Each of them consists in a binary decision tree composed by 2 d -1 CMux gates. The total complexity of the classical evaluation requires therefore to execute about s • 2 d CMux gates. Let's call o j = f j (x) ∈ T the j-th output of f (x), for j = 0, . . . , s -1. Figure 2 summarizes the idea of the computation of o j .

In this section we present two techniques, that we call horizontal and vertical packing, that can be used to improve the evaluation of a LUT. The packing technique is the same in both cases: the idea is to pack N TLWE messages inside the polynomial coefficients of a single TRLWE ciphertext. The names horizontal and vertical refer to the two different ways to use such packing. Intuitively, they describe in which sense the data of the LUT are packed and manipulated in order to evaluate the function f .

Horizontal packing corresponds exactly to batching. In fact, it exploits the fact that the s sub-functions evaluate the same CMux tree, with the same inputs but with the different LUT values corresponding to the s truth tables. For each of the 2 d possible input values, we pack the LUT values of the s sub-functions in the first s slots (i.e. in the first s coefficients of the polynomial) of a single TRLWE ciphertext (the remaining N -s are unused). By using a single 2 d size CMux tree to select the right ciphertext, we obtain the s slots all at once, which is overall s times faster than the classical evaluation.

On the other hand, our vertical packing is very different from the batching techniques. The basic idea is to pack several LUT values of a single sub-function in the same ciphertext, and to use both CMux and blind rotations to extract the desired value. Unlike batching, this can also speed up functions that have only a single bit of output.

In the following we detail these two techniques. They can be used both separately or combined, depending on the application. Remark 3. In order to evaluate f (x), the total amount of homomorphic CMux gates to be evaluated is s(2 d -1). If the function f is public, trivial samples of the LUT values σ j,0 , . . . , σ j,N -1 are used as inputs in the CMux gates. If f is private, the LUT values σ j,0 , . . . , σ j,N -1 are given encrypted. An analysis of the noise propagation in the binary decision CMux tree has already been given in [START_REF] Gama | Structural lattice reduction: Generalized worst-case to average-case reductions[END_REF] and [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF].

1 . . . 1 σ 0,2 d -3 . . . σ s-1,2 d -3 σ j,2 d -3 0 . . . 1 σ 0,2 d -2 . . . σ s-1,2 d -2 σ j,2 d -2 1 . . . 1 σ 0,2 d -1 . . . σ s-1,2 d -1 σ j,2 d -1 0
Horizontal Packing (or Batching) The idea of the horizontal packing is to evaluate all the outputs of the function f together, instead of evaluating all the f j separately. This is possible by using TRLWE samples, as the message space is T N [X]. In fact, we could encrypt up to N LUT values σ j,h (for a fixed h ∈ [[0, 2 d -1]]) per TRLWE sample and evaluate the binary decision tree as described before. The number of CMux gates to evaluate is s N (2 d -1). This technique is optimal if the size s of the output is a multiple of N . Unfortunately, s is in general ≤ N and the number of gates to evaluate remains 2 d -1. The evaluation of the function f is then only s times faster than the non-packed approach. As not all the slots are used, this technique it is not optimal if s is small. The elementary Lemma 5.1 specifies the noise propagation and it follows immediately from Lemma 3.16 and from the construction of the binary decision CMux tree, which has depth d.

Lemma 5.1 (Horizontal Packing -Batching). Let d 0 , . . . , d 2 d -1 be TRLWE samples 13 such that d h ∈ TRLWE K ( s j=0 σ j,h X j ) for h ∈ [[0, 2 d -1]].
Here the σ j,h are the LUT values relative to an arbitrary function f :

B d → T s . Let C 0 , . . . , C d-1 be TRGSW samples, such that C i ∈ TRGSW K (x i ) with x i ∈ B (for i ∈ [[0, d -1]]), and x = d-1 i=0 x i 2 i .
Let d be the TRLWE sample output by the f evaluation of the binary decision CMux tree for the LUT (described in figure 2). Then, using the same notations as in Lemma 3.16 and setting msg(d) = f (x):

-Err(d) ∞ ≤ A TRLWE + d • ((k + 1) N βA TRGSW + (kN + 1) ) (worst case), -Var(Err(d)) ≤ ϑ TRLWE + d • ((k + 1) N β 2 ϑ TRGSW + (kN + 1) 2 ) (average case),
where A TRLWE and A TRGSW are upper bounds of the infinite norm of the errors of the TRLWE samples and the TRGSW samples respectively and ϑ TRLWE and ϑ TRGSW are upper bounds of their variances.

Vertical Packing In order to improve the evaluation of the LUT, we propose a second optimization called Vertical Packing. As for the horizontal packing we use the TRLWE encryption to encode N values at the same time. But now, instead of packing the LUT values σ j,h with respect to a fixed h ∈ [[0, 2 d -1]] i.e. "horizontally", we pack N values σ j,h "vertically", with respect to a fixed j ∈ [[0, s -1]]. Then, instead of just evaluating a full CMux tree, we use a different approach.

If the LUT values are packed in "boxes", our technique first uses a packed CMux tree to select the right box, and then, a blind rotation (Algorithm 4) to find the right element inside the selected box. Figure 3 gives a schematic overview of the entire procedure.

Now, suppose that one wants to evaluate the function f , or just one of its sub-functions f j , on a fixed input x = d-1 i=0 x i 2 i . We assume the LUT associated to f j is known as in figure 2. The output of f j (x) is just the LUT value σ j,x at position x.

Let δ = log 2 (N ). We analyze the general case where 2 d is a multiple of N = 2 δ . The LUT of f j , which is a column of 2 d values, is now packed as 2 d /N TRLWE ciphertexts d 0 , . . . , d 2 d-δ -1 , where each d k encodes N consecutive LUT values σ j,kN , . . . , σ j,(k+1)N -1 . To retrieve f j (x), we first need to select the block that contains σ j,x . This block has index p = x/N , whose bits are the d -δ most significant bits of x. Since the TRGSW encryptions of these bits are among our inputs, one can use a CMux tree to select this block d p . Then, σ j,x is the ρ-th coefficient of the message of d p where ρ = x mod N = δ-1 i=0 x i 2 i . The bits of ρ are the δ least significant bits of x, which are also available as TRGSW ciphertexts in our inputs. We can therefore use a blind rotation (Algorithm 4) to homomorphically multiply d p by X -ρ , which brings the coefficient σ j,x in position 0, and finally, we extract it with a SampleExtract. Algorithm 5 details the evaluation of f j (x).

The entire cost of the evaluation of f j (x) with Algorithm 5 consists in 2 d N -1 CMux gates and a single blind rotation, which corresponds to δ CMux gates. Overall, we get a speed-up by a factor N on the evaluation of each partial function, so a factor N in total. i=0 xi2 i via vertical packing technique. After "vertically" packing the LUT values σ j,h (for h ∈ [[0, 2 d -1]]) in groups of size N , inside TRLWE samples, a CMux tree, a blind rotation and a sample extract are evaluated. The CMux tree is initially used to select the TRLWE sample containing the output value. Then the output value is moved in the place of the constant coefficient of the TRLWE message by using the blind rotation (Algorithm 4) and extracted by using the sample extraction (Section 4.2). The bits of x are given as TRGSW samples and the final result oj = fj(x) is extracted as a TLWE sample. In our example, we fixed 2 d = 4N .

TRLWE K ( N -1 i=0 σ j,pN +i X i ) for p ∈ [[0, 2 d N -1]] 14 . Let C 0 , . . . , C d-1 be TRGSW samples, such that C i ∈ TRGSW K (x i ), with x i ∈ B and i ∈ [[0, d -1]].
Then algorithm 5 outputs a TLWE sample c such that msg(c) = f j (x) = o j where x = d-1 i=0 x i 2 i and using the same notations as in Lemma 3.16 and Theorem 4.3, we have:

-Err(d) ∞ ≤ A TRLWE + d • ((k + 1) N βA TRGSW + (1 + kN ) ) (worst case), -Var(Err(d)) ≤ ϑ TRLWE + d • ((k + 1) N β 2 ϑ TRGSW + (1 + kN ) 2 ) (average case),
where A TRLWE and A TRGSW are upper bounds of the infinite norm of the errors in the TRLWE samples ant the TRGSW samples respectively, while ϑ TRLWE and ϑ TRGSW are upper bounds of the variances.

Algorithm 5 Vertical Packing LUT of f j : B d → T (calling algorithm 4) Proof. The proof follows immediately from the results of lemma 3.16 and theorem 4.3, and from the construction of the binary decision CMux tree. In particular, the first CMux tree has depth (d-δ) and the blind rotation evaluates δ CMux gates, which brings a total factor d in the depth. As the CMux depth is the same as in horizontal packing, the noise propagation matches too. Remark 4. As previously mentioned, the horizontal and vertical packing techniques can be mixed together to improve the evaluation of f . This combination is optimal in the case where s and d are both small or if 2 d • s > N . In particular, if we pack x = s coefficients horizontally and y = N/x coefficients vertically, we need 2 d /y -1 CMux gates plus one vertical packing LUT evaluation in order to evaluate f , which is equivalent to log 2 (y) CMux evaluations. The result is composed of the first x TLWE samples extracted. A practical example of the combination of the two techniques is given in Section 5.3.

Input: A list of 2 d N TRLWE samples dp ∈ TRLWEK ( N -1 i=0 σj,pN+iX i ) for p ∈ [[0, 2 d N - 1]],

Deterministic automata

It is folklore that every deterministic program which reads its input bit-by-bit in a pre-determined order, uses fewer than B bits of memory, and produces a Boolean answer, is equivalent to a deterministic automata of at most 2 B states (independently of the time complexity). This is in particular the case for every Boolean function of p variables, that can be trivially executed with p -1 bits of internal memory by reading and storing its input bit-by-bit before returning the final answer. It is of particular interest for most arithmetic functions, like addition, multiplication, or CRT operations, whose naive evaluation only requires O(log(p)) bits of internal memory.

But when message space is not binary, and several bits are packed together as we show in previous sections, a more powerful tool is needed to manage the evaluations in an efficient way.

In this section we review deterministic Weighted Finite Automata (det-WFA), a generalization of deterministic Finite Automata (det-FA) obtained by adding a weight in each transition. We detail the use of det-WFA to evaluate specific arithmetic functions largely used in applications, such as addition (and multi-addition), multiplication, squaring, comparison and max, etc. We refer to [START_REF] Buchsbaum | On the determinization of weighted finite automata[END_REF] and [START_REF] Droste | Weighted automata and weighted logics[END_REF] for further details.

Definition 5.3 (Deterministic weighted finite automata (det-WFA)).

A deterministic weighted finite automaton (det-WFA) over a group (S, ⊕) is a tuple A = (Q, i, Σ, T ), where Q is a finite set of states, i is the initial state, Σ is the alphabet, T ⊆ Q × Σ × S × Q is the set of transitions. Every transition itself is a tuple t = q σ,ν -→ q from the state q to the state q by reading the letter σ with weight w(t) equal to ν, and there is at most one transition per every pair (q, σ).

Let P = (t 1 , . . . , t d ) be a path, with t j = q j-1 σj ,νj -→ q j . The word σ = σ 1 . . . σ d ∈ Σ d induced by P has weight w(σ) equal to d j=1 w(t j ), where the w(t j ) are all the weights of the transitions in P : σ is called the label of P . Because the automaton is deterministic, every label induces a single path (i.e. there is only one possible path per word).

Remark 5. In our applications, we fix the alphabet Σ = B. Definition 5.3 restraints the WFA to the deterministic complete accessible (the non-deterministic case is not supported), and universally accepting case (i.e all the words are accepted). In the general (non-deterministic) case, the additive group would be replaced by the second law of a semi-ring (S, •, ⊕), and we would sum the weights, using the first law, of all accepting paths. However, since non-determinism is not supported, we want to keep the definition as simple as possible. In the rest of the paper we set (S, ⊕) as (T N [X], +).

-Err(d) ∞ ≤ d • ((k + 1) N βA TRGSW + (kN + 1) ) (worst case), -Var(Err(d)) ≤ d • ((k + 1) N β 2 ϑ TRGSW + (kN + 1) 2 ) (average case),
where A TRGSW is an upper bound on the infinite norm of the error in the TRGSW samples and ϑ TRGSW is an upper bound of their variance. Moreover, if all the words connecting the initial state to a fixed state q ∈ Q have the same length, then the upper bound on the number of CMux evaluated by Algorithm 6 decreases to |Q|.

Proof. Let q ∈ Q be a state, and σ a binary word, there exists a unique path starting from q and labelled by σ. We note w(q, σ) the weight of this path. Algorithm 6 evaluates the weights backwards from the last letter σ d-1 of the word to the first one. The invariant of the the main loop is that for all j in [0, d] and q ∈ Q, if q is accessible at depth j, c j,q is a TRLWE K sample of w(q, (σ j , . . . , σ d-1 )). Its error amplitude satisfies

Err(c j,q ) ∞ ≤ (d -j)(k + 1) N βA TRGSW + (d -j)(kN + 1) ,

Algorithm 6 Evaluation of a det-WFA

Input: A det-WFA A = (Q, i, B, T ). T0(q) and T1(q) denote the states that are reached when reading a binary letter from the state q, and w0(q) and w1(q) the weight of these transitions. d valid TRGSWK samples C0, . . . , C d-1 of the bits of a word σ = σ0 . . . σ d-1 . Output: A TRLWE encryption of w(σ)

1: for each q ∈ Q accessible at depth d do 2: set c d,q := 0 3: end for 4: for j = d -1 down to 0 do 5:

for each q ∈ Q accessible at depth j do 6:

set cj,q := CMux Cj, c j+1,T 1 (q) + (0, w1(q)), c j+1,T 0 (q) + (0, w0(q)) .

7:

end for 8: end for 9: return c0,i and its error variance satisfies

Var(Err(c j,q )) ≤ (d -j)(k + 1) N β 2 ϑ TRGSW + (d -j)(kN + 1) 2 .
For j = d, the invariant is true, because step 2 initializes the TRLWE K samples to zero. It is the weight of the empty word, and the error is null. Assuming by induction that the invariant holds at depth j + 1, we analyze what happens at line 6 on iteration j on state q.

Consider the two transitions q 0,w0(q) -→ T 0 (q) and q 1,w1(q) -→ T 1 (q), where T 0 (q) and T 1 (q) denote the states that are reached when reading a binary letter from the state q, and w 0 (q) and w 1 (q) denote the weights of these transitions. If q is accessible at depth j, then T 0 (q) and T 1 (q) are both accessible at depth j + 1, and encode respectively w(T 0 (q), (σ j+1 . . . σ d-1 )) and w(T 1 (q), (σ j+1 . . . σ d-1 )). Therefore, after applying the CMux, the message of c j,q is w(q, (σ j . . . σ d-1 )). By applying the noise propagation inequalities of Lemma 3.16, we have that Err(c j,q ) ∞ ≤ Err(CMux(C j , c j+1,T1(q) + (0, w 1 (q)), c j+1,T0(q) + (0, w 0 (q)))) ∞ ≤ max( Err(c j+1,T1(q) ) ∞ , Err(c j+1,T0(q) ) ∞ )

+ (k + 1) N β Err(C j ) ∞ + (kN + 1)
in the worst case, and Var(Err(c j,q )) ≤ Var(Err(CMux(C j , c j+1,T1(q) + (0, w 1 (q)), c j+1,T0(q) + (0, w 0 (q)))))

≤ max(Var(Err(c j+1,T1(q) )), Var(Err(c j+1,T0(q) ))) + (k + 1) N β 2 Var(Err(C j )) + (kN + 1) 2 in the average case, which prove that the invariant holds at depth j, and thus, for all j ∈ [0, d]. Since the initial state i is accessible at depth j = 0, this proves that the final result is c 0,i encodes w(i, σ) = w(σ), with the bounds announced in the theorem.

For the complexity, in the worst case, the main for-each loops over all states q ∈ Q and all depths j ∈ [0, d -1], which represents d|Q| CMux evaluations. If, by the last condition of the theorem, each state is accessible only at a single depth, then all for-each ranges are disjoint subsets of Q, so the total number of CMux evaluated is ≤ |Q|.

Remark 6. This algorithm can also evaluate regular Deterministic Finite Automata (det-FA): in this case the weight of all transitions at depth d -1 that reach a final state is 0.5, and all other weights are 0.

In the following sections we explain in detail how to use det-WFA to evaluate efficiently the functions computing the maximal value and the multiplication between two d-bits integers.

Max In order to evaluate the Max function of two d-bit integers

x = d-1 i=0 x i 2 i and y = d-1 i=0 y i 2 i , with x i , y i ∈ B for i ∈ [[0, d-1]],
we construct a det-WFA that takes in input all the bits of x and y, and outputs the maximal value between them. The idea is to enumerate the x i and y i , starting from the most significant bits down to the least significant ones. The det-WFA described in Figure 4 has 3 principal states (noted A, B, E) and 4 intermediary states (noted (A), (B), (E, 1), (E, 0)), that keep track of which number is the maximum, and in case of equality what is the last value of x i . A weight + 1 2 X i is added on all the transitions that reads the digit 1 from the maximum.

• • • A E B (A) (E, 0) (E, 1) (B) A E B • • • xi yi 1 0 1, + 1 2 X i 0 1, + 1 2 X i 0 1, + 1 2 X i 0 1 0 0 1 1, + 1 2 X i 0
Fig. 4. Max: det-WFA -The states A and (A) mean that y is the maximal value, the states B and (B) mean that x is the maximal value, and finally, the states E, (E, 1) and (E, 0) mean that x and y are equal on the most significant bits. If the current state is A or B, the following state remains the same. The initial state is E. If the current state is E, after reading xi there are two possible intermediate states: (E, 1) if xi = 1 and (E, 0) if xi = 0. After reading the value of yi, the 3 possible states A, B and E are possible. The det-WFA is repeated as many times as the bit length of the integers evaluated and the weights are given in clear.

Remark 7. In practice, to evaluate the MAX function, we convert the det-WFA in a circuit that counts 5d CMux gates. Roughly speaking, we have to read the automata in the reverse. We initialize 5 states A, B, E 0 , E 1 , E as null TRLWE samples. Then, for i from d -1 to 0, we update the states as follows:

               E 0 := CMux(C y i , A + (0, 1 2 X i ), E); E 1 := CMux(C y i , E, B); A := CMux(C y i , A + (0, 1 2 X i ), A); E := CMux(C x i , E 1 + (0, 1 2 X i ), E 0 ); B := CMux(C x i , B + (0, 1 2 X i ), B).
Here the C x i and C y i are TRGSW encryptions of the bits x i and y i respectively, and they are the inputs. The output of the evaluation is the TRLWE sample E, which contains the maximal value encoded as i zi 2 .X i , where z i is the i-th output bit.

Overall, the next lemma, which is a direct consequence of Theorem 5.4, shows that the Max can be computed by evaluating only 5d CMux gates, instead of Θ(d 2 ) with classical deterministic automata. Here A TRGSW and ϑ TRGSW are upper bounds of the amplitude and of the variance of the errors in the TRGSW samples.

In a similar way, it is possible to construct a det-WFA for the comparison between two integers x and y, answering is x > y or not. The result is computed by evaluating 4d CMux gates (and just 3d gates in the case of gate bootstrapping).

Multiplication For the multiplication we use the same approach and we construct a det-WFA which maps the schoolbook multiplication. We illustrate the construction on the example of the multiplication between two 2-bits integers x = x 1 x 0 and y = y 1 y 0 . As shown in the top part of Figure 5, after an initial step of bit by bit multiplication, a multi-addition (shifted of one place on the left for every line) is performed. The bits of the final result m = m 3 m 2 m 1 m 0 are computed as the sum of each column with carry. The det-WFA computes the multiplication by keeping track of the partial sum of each column in the states, and by using the transitions to update these sums. For the multiplication of 2-bits integers, the automaton (described in the bottom part of Figure 5) has 6 main states (i, c 0 , c 10 , c 11 , c 20 , c 21 ), plus 14 intermediary states (noted with capital letters and parenthesis) that store the last bit read.

y1 y0 × x1 x0 x0y1 2 x0y0 1 + x1y1 4 x1y0 3 m3 m2 m1 m0 i (A1) (A0) c0 (B1) (B0) (C1) (C0) (D11) (D10) (D01) (D00) c11 c10 (E11) (E10) (E01) (E00) c21 c20 1 0 1 , + 1 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 , + 1 2 X 0 / 1 , + 1 2 X 1 , + 1 2 X 0 1 0 1 0 1 0 1 , + 1 2 X 3 0 , + 1 2 X 2 0 / 1 , + 1 2 X 2 1 , + 1 2 X 2 0 1 0 x0 y0 x0 y1 x1 y0 x1 y1
Fig. 5. Schoolbook 2-bits multiplication and corresponding det-WFA

The value of the j-th (for j ∈ [[0, 3]]) output bit is put in a weight on the last transition of each column. The final weight is the result of the multiplication.

For the generic multiplication of two d-bits integers, we can upper bound the number of states by 4d 3 , instead of Θ(d 4 ) with one classical automata per output bit. Indeed, each column of the multiplication holds a partial sum that ranges between 0 and 2d. It takes less than d multiplications to update each column sum, so the WFA needs 2d 2 states per column, so 4d 3 states in total. For a more precise number of states we wrote a C++ program to eliminate unreachable states and refine the leading coefficient, but the average behaviour is still in O(d 3 ). The depth is 2d 2 and the noise evaluation can be easily deducted by previous results. The same principle can be used to construct the multiaddition, and its det-WFA is slightly simpler (one transition per bit in the sum instead of two).

Bit Sequence Representation

We now present another design which is specific to the multi-addition (or its derivatives), but which is faster than the generic construction with det-WFA. The idea is to build an homomorphic scheme that can represent small integers, say between 0 and N = 2 p , and which is dedicated to only the three elementary operations used in the multi-addition algorithm, namely:

1. Extract any of the bits of the value as a TLWE sample; 2. Increment the value by 1; 3. Integer division of the value by 2.

We now explain the basic idea, and then, we show how to implement it efficiently on TRLWE ciphertexts.

We represent integers modulo 2N , with N = 2 p , by using their Bit Sequence Representation (BSR). For j ∈ [[0, p]] and k, l ∈ Z, we call B (l) j,k the j-th bit of l + k in the little endian signed binary representation (Figure 6).

For each integer k ∈ Z, (B

(l) 0,k , B (l) 1,k , ..., B (l)
p,k ) is the (little endian signed) binary representation of l + k mod 2N . When k is not specified, B (l) j represents the binary sequence of all the j-th bits of integers l, l + 1, l + 2, . . ..

Let l = 0. Observe that B (0) 0

= (0, 1, 0, 1, ...) is 2-periodic, B (0) 1
= (0, 0, 1, 1, 0, 0, 1, 1...) is 4-periodic and, more generally, for all j ∈ [[0, p]] and l ∈ Z, B (l) j is 2 j -antiperiodic (f (x -2 j ) = N OT f (x)) and it is the left shift of B (0) j by l positions. Therefore, it suffices to have 2 j ≤ N consecutive values of the sequence to (blindly) deduce all the remaining bits.

We now suppose that an integer l ∈ [[0, N -1]] is represented by its BSR, defined as We now explain how to compute BSR(l + 1) (increment) and BSR( l/2 ) (divide by 2) using only copy and negations operations on bits at a fixed position which does not depend on l (blind computation). Then, we show how to represent these operations homomorphically on TRLWE ciphertexts.

BSR(l) = [B (l) 0 , . . . , B (l) p ].
0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 ← B (l) 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 ← B (l) 1 2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 ← B (l) 2 3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 ← B (l) 3 ↑ j l
r0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 r1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 r2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 r3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 r0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 r1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 r2 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 r3 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 ↓ •X -5 ↓ π div2
r 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 r 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 r 2 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 r 3 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 r 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 r 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 r 2 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 r 3 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 Fig. 7. TBSRexample of addition +5 and division by 2.

[[0, p -1]], we represent B (l) j with the polynomial

µ j = N -1 k=0 1 2 B (l) j,k • X k
and we represent the last B (l)

p with the polynomial

µ p = N -1 k=0 1 2 B (l) p,k - 1 4 • X k .
This simple rescaling between the bit representation BSR(l) and the torus representation M = [µ 0 , . . . , µ p ] is bijective.

The increment operation described in previous section for the BSR consists in a cyclic shift of coefficients. It correspond to the multiplication by X (or to a power of X) in the TBSR encoding, which has a similar behaviour on coefficients of torus polynomials.

The integer division by two immediately rewrites into an affine function thanks to the TBSR encoding. It transforms the coefficients (µ j,k ) j∈[ [1,p]],k∈{0,2,...,2N -2} ∈ T pN into (µ 0 , . . . , µ p ) as follow:

π div2 :        µ j,k = µ j+1,2k for j ∈ [0, p -2], k ∈ [0, N -1] µ p-1,k = µ p,2k + 1 4 for k ∈ [0, N -1] µ p,k = -1 4 for k ∈ [0, N 2 -1] µ p,N/2+k = µ p,2k for k ∈ [0, N 2 -1]
The output of the division by two is still an integer in [[0, N ]], as the input. Finally, we call TBSR ciphertext of an unknown integer l ∈ [0, N -1] a vector C = [c 0 , ..., c p ] of TRLWE ciphertexts of message [µ 0 , . . . , µ p ]. Definition 5.6 (TBSR encryption). We define the TBSR encryption as follows.

-Parameters and keys: TRLWE parameter N with secret key K ∈ B N [X], and a circular-secure keyswitching key KS K→K,γ from K to itself, noted just KS. -TBSRSet(l): return a vector of trivial TRLWE ciphertexts encoding the torus representation of [B

(l) 0 , . . . , B (l)
p ]. -TBSRBitExtract j (C): Return SampleExtract(c j ) (Section 4.2) when j < p. 15-TBSRIncrement(C): Return X -1 • C. -TBSRDiv2(C): Use KS to evaluate π div2 homomorphically on C. Since it is a 1-Lipschitz affine function, this consists in applying the public functional KeySwitch to KS, the linear part of π div2 and C, and then, translate the result by the constant part of π div2 .

The following theorem is a direct consequence of Theorem 4.1 (with n = N ). The correctness of the result has already been discussed. Theorem 5.7 (TBSR operations). Let N , K and KS be TBSR parameters and keys as defined before, and let C be a TBSR ciphertext of l ∈ [[0, N -1]] with noise amplitude η (and noise variance ϑ). Then for j ∈ [[0, p -1]], TBSRBitExtract j (C) is a TLWE K ciphertext of the j-th bit of l, over the message space {0, 1 2 }, with noise amplitude (resp. variance

) ≤ η (resp. ≤ ϑ). If l ≤ N -2 (if l = N -1 the result is not determined), TBSRIncrement(C) is a TBSR ciphertext of l + 1 with noise amplitude (resp. variance) ≤ η (resp. ≤ ϑ). C = TBSRDiv2(C) is a TBSR ciphertext of l/2 such that: -Err(C ) ∞ ≤ Err(C) ∞ + N 2 tA KS + N 2 -(t+1) (worst-case), -Var(Err(C )) ≤ Var(Err(C)) + N 2 tϑ KS + N 2 -2(t+1) (average case),
where A KS and ϑ KS are the amplitude and variance of the key-switching key KS, respectively.

Using the TBSR counter for a multi-addition or a multiplication. The TBSR counter allows to perform a multi-addition or multiplication using the school-book elementary algorithms (see Algorithm 7 and Algorithm 8). This leads to a leveled multiplication circuit (with KeySwitching) which is quadratic instead of cubic with weighted automata.

The following lemma analyzes the case of the multiplication and the result described is a consequence of Theorem 4.1. The correctness of the result can be deducted from the construction, presented in Algorithm 8 (with N > 2d).

The formulas for the multi-addition can be easily found, and the correctness comes from the construction (Algorithm 7, with N > 2m).

Lemma 5.8. Let N ,B g , and KS be TBSR and TRGSW parameters with the same key K. We suppose that each TBSR ciphertext has p ≤ 1 + log(N ) TRLWE ciphertexts. Let (A i ) and (B i ) for i ∈ [0, d -1] be TRGSW-encryptions of the bits of two d-bits integers (little endian), with the same noise amplitude A (resp. variance ϑ).

Then, Algorithm 8 computes all the bits of the product within 2d 2 p CMux and (2d -2)p public key-switching, and the output ciphertexts satisfy:

-Err(Out) ∞ ≤ 2d 2 ((k+1) N βA+(kN +1) )+(2d-2)(N 2 tA KS +N 2 -(t+1) ), -Var(Err(Out)) ≤ 2d 2 ((k + 1) N β 2 ϑ + (kN + 1) 2 ) + (2d -2)(N 2 tϑ KS + N 2 -2(t+1) ),
where A KS and ϑ KS are the amplitude and variance of the key-switching key KS, respectively.

Improving TBSR with horizontal packing.

Algorithm 7 TBSR multi-addition

Input: The bitwise TRGSW-encryption (Ai,j) i∈[0,m-1],j∈[0,d-1] of m integers a0, . . . , am-1 of d-bits each Output: bitwise LWE encryptions of the sum Out0, . . . , Out d+log 2 (m) .

1: C ← TBSRSet(0) 2: for j = 0 to d -2 do 3: for i = 0 to m -1 do Sum the j-th column 4:

C ← CMux(Aj,i, TBSRIncr(C), C); 5:

end for 6:

Outi ← TBSRBitExtract0(C); Extract Outi = the lsb 7:

C ← TBSRDiv2(C); and compute the carry 8: end for 9: for i = 0 to m -1 do Sum the last column 10: First improvement: If the domain of the integers is [0, y -1] where xy = N , we can use Horizontal packing to pack x different polynomials mod X y + 1 in a single TRLWE ciphertext mod X N + 1. We just replace the shift by X -1 by a multiplication by X -x . This allows to store the p = log 2 (y) + 1 sequences in only p/x TRLWE ciphertexts, and this provides a factor x speedup compared to the basic scheme. For instance, if N = 1024 and the domain of the BSR integers is [0, 127], which is enough to perform a multiplication with a 64 bit number, the 8 sequences can be packed in a single TRLWE ciphertext (x = 8,y = 128).

C ← CMux(A d,i ,
Second improvement: Even if the domain is as large as [0, N -1], the first bit sequences have a small period. It is therefore possible to use the previous improvement to encode many of the first sequences as a single ciphertext, and leave the last N -antiperiodic one alone on its ciphertext. For instance, if N = 1024, the first 8 sequences B

9 are 512-periodic/antiperiodic, and can be packed on a single TRLWE ciphertext. Finally, the lase sequence B (l) 1 0 is 1024-antiperiodic, and stays alone. As long as periodic sequences use the {0, 1 2 } message space, and anti-periodic sequences use {- 1 4 , 1 4 } (and the constant terms of f div2 are updated accordingly), all TBSR computations over [0, 1023] can be done in only 3 TRLWE ciphertexts instead of 11, which gives a time-speedup of a factor 11/3 = 3.66 compared to the basic scheme.

Bootstrapping

The schemes and the techniques described in the previous sections can be used in a leveled context, where the depth of the circuit to be evaluated is known 1: C ← TBSRSet(0) 2: for j = 0 to d -1 do 3: for i = 0 to j do 4:

C ← CMux(Ai, CMux(Bj-i, TBSRIncr(C), C), C); 5:

end for 6:

Outj ← TBSRBitExtract0(C); 7:

C ← TBSRDiv2(C); 8: end for 9: for j = d to 2d -3 do 10:

for i = j -d + 1 to d -1 do 11: C ← CMux(Ai, CMux(Bj-i, TBSRIncr(C), C), C); 12:
end for 13:

Outj ← TBSRBitExtract0(C); 14:

C ← TBSRDiv2(C); 15: end for 16:

C ← CMux(A d-1 , CMux(B d-1 , TBSRIncr(C), C), C); 17: Out 2d-2 ← TBSRBitExtract0(C); 18: Out 2d-1 ← TBSRBitExtract1(C);
19: return Out in advance. We now present two bootstrappings. The fastest one, in the lineage of [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] and [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF] must be performed after each gate in a circuit, and is therefore denoted as gate-bootstrapping. The second one, which we describe in Subsection 6.2, allows to execute a larger leveled circuit between each bootstrapping, and is therefore denoted circuit bootstrapping.

Gate bootstrapping (TLWE-to-TLWE)

Given a TLWE sample TLWE K (µ) = (a, b), the gate bootstrapping procedure constructs an encryption of µ under the same key K but with a fixed amount of noise. As in [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF], we use TRLWE as an intermediate encryption scheme to homomorphically evaluate the phase, but we use the external product from theorem 3.13 with a TRGSW encryption of the key K. Definition 6.1 (Bootstrapping key). Let K ∈ B n , K ∈ B N [X] n and α be a standard deviation. We define the bootstrapping key BK K→K ,α as the sequence of n TGSW samples where BK i ∈ TRGSW K ,α (K i ). Theorem 6.2 (Bootstrapping TLWE-to-TLWE). Let H be the gadget matrix in M ( k+1) ¯ , k+1 (T N [X]) and Dec H, β,¯ its efficient approximate gadget decomposition algorithm, with quality β and precision ¯ defining TRLWE and TRGSW parameters. Let K ∈ B n and K ∈ B n be two TLWE secret keys, and K ∈ B N [X] k Algorithm 9 Bootstrapping TLWE-to-TLWE (calling algorithm 4)

Input: A constant µ1 ∈ T, a TLWE sample c = (a, b) ∈ TLWE K,η (x • 1 2 ), with x ∈ B a bootstrapping key BK K→ K, ᾱ = (BKi) i∈[[1,n]] , Output: A TLWE sample c = (ā, b) ∈ TLWEK ,η (x • µ1) 1: Let µ = 1 2 µ1 ∈ T (Pick one of the two possible values) 2: Let b = 2 N b and ãi = 2 N a i ∈ Z for each i ∈ [[1, n]] 3: Let v := (1+X+ . . . +X N -1 ) • X N 2 • µ ∈ T N [X] 4: ACC ← BlindRotate((0, v), (ã1, . . . , ãn, b), (BK1, . . . , BKn)) 5: Return (0, µ) + SampleExtract(ACC)
be the TRLWE interpretation of the key K, and let ᾱ ∈ R ≥0 be a standard deviation. Let BK K→ K, ᾱ be a bootstrapping key, composed by the n TRGSW encryptions BK i ∈ TRGSW K, ᾱ(K i ) for i ∈ [ [1, n]]. Given one constant µ 1 ∈ T, and one sample c ∈ T n+1 whose coefficients are all multiples of 1 2 N , Algorithm 9 outputs a TLWE sample c ∈ TLWEK(µ) where µ = 0 iff |ϕ K (c)| < 1 4 , µ = µ 1 otherwise and such that:

-Err(c) ∞ ≤ n( k + 1) ¯ N β ĀBK + n(1 + k N )¯ (worst case), -Var(Err(c)) ≤ n( k + 1) ¯ N β2 θBK + n(1 + k N )¯ 2 (average case),
where ĀBK is the amplitude of BK and θBK its variance s.t.

Var(Err(BK K→ K, ᾱ)) = ᾱ2 .

Proof. By using the definitions of b and ã given at line 2 of the Algorithm 9, we define φ def = bn i=1 ãi s i mod 2N . We have

ϕ - φ 2N = b - 2N b 2N + n i=1 a i - 2N a i 2N K i ≤ 1 4N + n i=1 1 4N ≤ n + 1 4N = δ.
(2) And if the coefficients ã1 , . . . , ãn , b ∈ 1 2N Z/Z, then ϕ = φ 2N . In all cases, |ϕ -

φ 2N | < δ. At line 3, the test vector v := (1+X+ . . . +X N -1 ) • X N 2 • µ is defined such that for all p ∈ [0, 2 N ], the constant term of X p • v is either µ if p ∈]] N 2 , 3 N 2 ]
], and -µ otherwise.

At line 4, a blind rotation (Algorithm 4) is applied to the test vector. The result is msg(ACC) = X -φ • v and the error (from the results shown in Theorem 4.3 and as the TRLWE encryption of the test vector is noiseless trivial) is:

-Err(ACC) ∞ ≤ n( k + 1) ¯ N β ĀBK + n(1 + k N )¯ , in the worst case, -Var(Err(ACC)) ≤ n( k + 1) ¯ N β2 θBK + n(1 + k N )¯ 2 , in the average case.
The SampleExtract at line 5 doesn't add any noise, so the error after bootstrapping remains the same as after the blind rotation.

have an efficient bootstrapping between TLWE and TRGSW ciphertexts. Fast bootstrapping procedures have been proposed in [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF][START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF], and the external product 3.12 from [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF][START_REF] Brakerski | Lattice-based fully dynamic multi-key FHE with short ciphertexts[END_REF] has contributed to accelerate leveled operations. Unfortunately, these bootstrapping cannot output GSW ciphertexts. Previous solutions proposed in [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF][START_REF] Alperin-Sheriff | Faster bootstrapping with polynomial error[END_REF][START_REF] Gama | Structural lattice reduction: Generalized worst-case to average-case reductions[END_REF] based on the internal product are not practical. In this section, we propose an efficient technique to convert back TLWE ciphertexts to TRGSW (running in 137ms, on a 64-bit (single core) Intel Core i7-4910MQ at 2.90GHz laptop, for 152-bits of security, see Sections 7 and 8). We call it circuit bootstrapping.

Our goal is to convert a TLWE sample with large noise amplitude over some binary message space (e.g amplitude 1 4 over {0, 1 2 }), into a TRGSW sample with a low noise amplitude < 2 -20 over the integer message space {0, 1}.

In all previous constructions, the TLWE decryption consists in a circuit, which is then evaluated using the internal addition and multiplication laws over TRGSW ciphertexts. The target TRGSW ciphertext is thus the result of an arithmetic expression over TRGSW ciphertexts. Instead, we propose a more efficient technique, which reconstructs the target directly from its very sparse internal structure. Namely, a TRGSW ciphertext of a message µ ∈ {0, 1} is a vector of (k + 1) TRLWE ciphertexts. Each of these TRLWE ciphertexts encrypts the same message as µ • h i , where h i is the corresponding line of the gadget matrix H. Depending on the position of the row (which can be indexed by u ∈ [1, k + 1] and j ∈ [1, ]), this message is µ -K u • Bg -j where K u is the u-th polynomial of the secret key and K k+1 = -1. So we can use times the TLWE-to-TLWE bootstrapping of [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF] to obtain a TLWE sample of each message in {µBg -1 , . . . , µB - g }. Then we use the private key-switching technique to "multiply" these ciphertexts by the secret -K u , to reconstruct the correct message (Figure 8).

Our circuit bootstrapping, detailed in Algorithm 11, crosses 3 levels of noise and encryption. Each level has its own key and parameters set. In order to distinguish the different levels, we use an intuitive notation with bars. The upper bar will be used for level 2 variables, the under bar for the level 0 variables and level 1 variables will remain without any bar. The main difference between the three levels of encryption is the amount of noise supported. Indeed, the higher the level is, the smaller is the noise. Level 0 corresponds to ciphertexts with very large noise (typically, α ≈ 2 -11 ). Level 0 parameters are very small, computations are almost instantaneous, but only a very limited amount of linear operations are tolerated. Level 1 corresponds to medium noise (typically, α ≈ 2 -30 ). Ciphertexts in level 1 have medium size parameters, which allows for relatively fast operations, and for instance a leveled homomorphic evaluation of a relatively large automata, with transition timings described in Section 5 of [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF]. Level 2 corresponds to ciphertexts with small noise (typically, ᾱ ≈ 2 -50 ). This level corresponds to the limit of what can be mapped over native 64-bit operations. Practical values and details are given in Section 8.

Our circuit bootstrapping consists in three parts:

Algorithm 11 Circuit Bootstrapping (calling algorithms 9 and 3)

Input: A level 0 TLWE sample c = (a, b) ∈ TLWE K,η (µ • 1
2 ), with µ ∈ B , a bootstrapping key BK K→ K, ᾱ = (BKi ∈ TRGSW K, ᾱ(K i )) i∈[ [1,n]] , k + 1 private keyswitch keys KS be done with additive noise overhead via the private functional keyswitch (Algorithm 3). Theorem 6.4 (Circuit Bootstrapping Theorem). Let n, α, N, k, B g , , H, denote TRLWE/TRGSW level 1 parameters, and the same variables names with underbars/upperbars for level 0 and 2 parameters. Let K ∈ B n , K ∈ B n and K ∈ B n, be a level 0, 1 and 2 TLWE secret keys, and K, K, K their respective TRLWE interpretation. Let BK K→ K, ᾱ be a bootstrapping key, composed by the n TRGSW [1,t]] be the corresponding private-keyswitching key. Given a level 0 TLWE sample c = (a, b) ∈ TLWE K (µ • 1 2 ), with µ ∈ B, the algorithm 11 outputs a level 1 TRGSW sample C ∈ TRGSW K (µ) such that

encryptions BK i ∈ TRGSW K, ᾱ(K i ) for i ∈ [[1, n]]. For each u ∈ [[1, k + 1]], let f u be the morphism from T to T N [X] defined by f u (x) = K u • x, and KS fu K→K,γ = (KS (u) i,j ∈ TRLWE K,γ (( Ki K u •2 -j ))) i∈[[1,n]],j∈[
-Err(C) ∞ ≤ n( k + 1) ¯ N βA BK + n(1 + k N )¯ + n2 -(t+1) + ntA KS (worst); -Var(Err(C)) ≤ n( k+1) ¯ N β2
θBK +n(1+ k N )¯ 2 + n2 -2(t+1) + ntϑ KS (average).

Here θBK = ᾱ2 and A BK is the variance and amplitude of Err(BK K→ K, ᾱ), and ϑ KS = γ 2 and A KS are the variance and amplitude of Err(KSK →K,γ ).

Proof. The output TRGSW ciphertext is correct, because by construction, the i-th TRLWE component c (u,w) has the correct message msg(µ w) is obtained by chaining one TLWE-to-TLWE bootstrapping (Algorithm 9) with one private key-switchings, as in Algorithm 3. The values of maximal amplitude and variance of Err(C) are directly obtained from the partial results of Theorem 6.2 and Theorem 4.2. In total, Algorithm 11 performs exactly bootstrappings (Algorithm 9), and (k + 1) private key switchings (Algorithm 3).

• h i ) = µK u /B w g . c (u,
Comparison with previous bootstrappings for TGSW. The circuit bootstrapping we just described evaluates a quasilinear number of level-2 external products, and a quasilinear number of level 1 products in the private keyswitchings. With the parameters proposed in the next section, it runs in 0.137 seconds for a 110-bit security parameter: level 2 operations take 70% of the running time, and the private keyswitch takes the remaining 30%.

Our circuit bootstrapping is not the first bootstrapping algorithm that outputs a TRGSW ciphertext. Many constructions have previously been proposed and achieve valid asymptotical complexities, but very few concrete parameters are proposed. Most of these constructions are recalled in the last section of [START_REF] Gama | Structural lattice reduction: Generalized worst-case to average-case reductions[END_REF]. In all of them, the bootstrapped ciphertext is obtained as an arithmetic expression on TRGSW ciphertexts involving linear combinations and internal products. First, all the schemes based on scalar variants of TRGSW suffer from a slowdown of a factor at least quadratic in the security parameter, because the products of small matrices with polynomial coefficients (via FFT) are replaced with large dense matrix products. Thus, bootstrapping on TGSW variants would require days of computations, instead of the 0.137 seconds we propose. Now, assuming that all the bootstrapping uses (Ring) instantiations of TRGSW, the design in [START_REF] Brakerski | Lattice-based FHE as secure as PKE[END_REF] based on the expansion of the decryption circuit via Barrington theorem, as well as the expression as a minimal deterministic automata of the same function in [START_REF] Gama | Structural lattice reduction: Generalized worst-case to average-case reductions[END_REF] require a quadratic number of internal level 2 TRGSW products, which is much slower than what we propose. Finally, the CRT variant in [START_REF] Alperin-Sheriff | Faster bootstrapping with polynomial error[END_REF] and [START_REF] Gama | Structural lattice reduction: Generalized worst-case to average-case reductions[END_REF] uses only a quasi-linear number of products, but since it uses composition between automata, these products need to run in level 3 instead of level 2, which induces a huge slowdown (a factor 240 in our benchs), because elements cannot be represented on 64-bits native numbers.

Sum-up of elementary Homomorphic Operations Table 1 summarizes the possible operations on plaintexts that we can perform with TFHE, and their correspondence over the ciphertexts. All these operations are expressed on the continuous message space T for TLWE and T N [X] for TRLWE. As previously mentioned, all samples contain noise: if an exact decryption is required, the message space must be chosen accordingly.

Observe that the operations involving keyswitching or bootstrapping can also be used to change the encryption key. If we assume the circular security, we can keep the same key after these operations. Otherwise, the keys are given as a chain, where every secret key is encrypted with the following one, and the each bootstrapping or keyswitching moves from the current key to the next one.

Security analysis

On the asymptotical side, TLWE samples can be equivalently rescaled and rounded to their closest binLWE representative, which in turn can be reduced to standard LWE with full secret using the modulus-dimension reduction [START_REF] Brakerski | Classical hardness of learning with errors[END_REF] or group-switching techniques [START_REF] Gama | Structural lattice reduction: Generalized worst-case to average-case reductions[END_REF]. Therefore, the semantic security of TFHE is asymptotically equivalent to worst case lattice problems. At the time of writing, there is still no reduction between the RingLWE and the binary-RingLWE instances. There is instead an asymptotic equivalence between ring [START_REF] Stehlé | Efficient public key encryption based on ideal lattices[END_REF][START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF] and module LWE [START_REF] Langlois | Worst-case to average-case reductions for module lattices[END_REF] problems for large modulus [START_REF] Albrecht | Large modulus ring-lwe >= module-lwe[END_REF].

In this section, we will rather focus on the practical hardness of TFHE, and express its effective security parameter λ directly as a function of the entropy of the secret n and the error standard deviation α.

Our analysis is based on the methodology of [START_REF] Albrecht | On the concrete hardness of learning with errors[END_REF] and [START_REF] Albrecht | On dual lattice attacks against small-secret LWE and parameter choices in helib and SEAL[END_REF]. In their work, they review many classes of attacks against LWE, ranging from a direct BDD approach with standard lattice reduction, sieving algorithms, a variant of BKW [START_REF] Blum | Noise-tolerant learning, the parity problem, and the statistical query model[END_REF], and resolution of LWE via man in the middle attacks. In general, they found out that there is no single-best attack against all possible parameters, however, according to their results table [START_REF] Albrecht | On the concrete hardness of learning with errors[END_REF]Section8,Tables 7,[START_REF] Alperin-Sheriff | Faster bootstrapping with polynomial error[END_REF]] for the range of dimensions and noise used for FHE, it appears that the SIS-distinguisher attack is often the most efficient attack. Since q is not a parameter in our definition of TLWE, we need to adapt their results. This section relies on the following heuristics concerning the experimental behaviour of lattice reduction algorithms. They have been extensively verified and used in practice.

1. The fastest lattice reduction algorithms in practice are blockwise lattice algorithms (like BKZ-2.0 [START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF], D-BKZ [START_REF] Micciancio | Practical, predictable lattice basis reduction[END_REF], or the slide reduction with large blocksize [START_REF] Gama | Predicting Lattice Reduction[END_REF][START_REF] Micciancio | Practical, predictable lattice basis reduction[END_REF]).

Practical blockwise lattice reduction algorithms have an intrinsic quality

δ > 1 (which depends on the blocksize and is usually called the root Hermite Factor ), and given a m-dimensional real basis B of volume V , they compute short vectors of norm δ m V 1/m .

3. Different approaches to evaluate the running time of BKZ-2.0 have been proposed in the literature [START_REF] Albrecht | Estimate all the {LWE, NTRU} schemes[END_REF][START_REF] Chen | BKZ 2.0: Better lattice security estimates[END_REF][START_REF] Albrecht | On the concrete hardness of learning with errors[END_REF][START_REF] Alkim | Post-quantum key exchange -A new hope[END_REF][START_REF] Albrecht | On the complexity of the BKW algorithm on LWE[END_REF]. In this section, we use the following estimation in seconds: log 2 (t BKZ )(δ) = 0.009 log 2 (δ) 2 -27 according to the extrapolation by Albrecht et al [START_REF] Albrecht | On the complexity of the BKW algorithm on LWE[END_REF] of Liu-Nguyen datasets [START_REF] Liu | Solving bdd by enumeration: An update[END_REF].

4. The coordinates of vectors produced by lattice reduction algorithms are balanced. Namely, if the algorithm produces vectors of norm v 2 , each coefficient has a marginal Gaussian distribution of standard deviation v 2 / √ n. Provided that the geometry of the lattice is not too skewed in particular directions, this fact can sometimes be proved, especially if the reduction algorithm samples vectors with Gaussian distribution over the input lattice.

5. For mid-range dimensions and polynomially small noise, the SISdistinguisher plus lattice reduction algorithms combined with the searchto-decision is the best attack against LWE; (but this point is less clear, to the analysis of [START_REF] Albrecht | On the complexity of the BKW algorithm on LWE[END_REF], at least, this attack model tends to overestimate the power of the attacker, so it should produce more conservative parameters).

6. Except for small polynomial speedups in the dimension, we do not know better algorithms to find short vectors in random anti-circulant lattices than generic algorithms. This folklore assumption seems still up to date at the time of writing. The most recent asymptotic attacks [START_REF] Cramer | Short stickelberger class relations and application to ideal-svp[END_REF] against ideal lattice do not reach polynomial noise rates, and they are not practical.

The SIS-based distinguisher attack against the LWE problem consists in finding a small integer combination that cancels the left hand side of homogeneous LWE samples. If applying the same combination to the right hand side does not make it small, we deduce that our inputs are not LWE samples, but rather uniformly random samples. Such SIS-distinguisher has in general a small advantage ε. To recover the full key, we use the well known search to decision reduction, which is particularly tight for TLWE: guess that the first key bit is zero, randomize the first coordinates of each sample, and use the distinguisher about 1/ε 2 times to amplify its advantage to Θ(1), and to confirm whether the result are still TLWE samples, i.e. if our guess of the first key bit is correct. Once a key bit is found, getting the other bits involves solving lower-dimensional TLWE problems, and are significantly easier, therefore we consider that the complexity of the attack is the time needed to find the first key bit. We also extend the analysis of [START_REF] Albrecht | On the concrete hardness of learning with errors[END_REF] to handle the continuous torus.

Let (a 1 , b 1 ), . . . , (a m , b m ) be either m TLWE samples of error standard deviation α or m uniformly random samples of T n+1 , we need to find a small combination v 1 , . . . , v m of samples such that v i a i is small. Most previous models, that work on a discrete group, would require that this term is exactly zero. By allowing approximations, we may find valid solutions in smaller dimension m than the usual bound n log n. In particular, even m < n would make sense. Now, consider the (m+n)-dimensional lattice, generated by the rows of the following basis B ∈ M n+m,n+m (R):

B =          1 0 . . . 0 0 1 a1,1 • • • a1,n 1 0 . . . . . . . . . . . . am,1 • • • am,n 0 1          .
Our goal is to find a short vector w = [x 1 , . . . , x n , v 1 , . . . , v m ] in the lattice of B, whose first n coordinates (x 1 , . . . , x n ) = m i=1 v i a i mod 1 are shorter than the second part (v 1 , . . . , v m ). To this skewness into account, we choose a real parameter q > 1 (that will be optimized later), and apply the unitary transformation f q to the lattice, which multiplies the first n coordinates by q and the last m coordinates by 1/q n/m . Although this new basis now looks like a classical LWE matrix, the variable q is a real parameter, rather than an integer. It then suffices to find a regular short vector with balanced coordinates in the transformed lattice, defined by this basis:

f q (B) =           q 0 . . . 0 0 q qa1,1 • • • qa1,n 1 q n/m 0 . . . . . . . . . . . . qam,1 • • • qam,n 0 1 q n/m           , with q ∈ R > 1.
To that end, we apply the fastest algorithm (BKZ-2.0 or slide reduction) directly to f q (B), which outputs a vector f q (w) of standard deviation δ n+m / √ n + m where δ ∈]1, 1.1] is the quality of the reduction. Once we obtain a such vector w, all we need is to analyse the term

m i=1 v i b i = m i=1 v i (a i s + e i ) = s • m i=1 (v i a i ) + m i=1 v i e i = s • x + v • e. It has Gaussian distribution of variance σ 2 = δ 2(m+n) q 2 • nS 2 m+n + q 2n/m δ 2(m+n) α 2 m m+n = δ 2(m+n) S 2 q 2 • n m+n + q 2n/m α 2 m m+n . Here S = s √ n ≈ 1 √ 2
. This distribution may be distinguished from the uniform distribution with advantage ε when σ 2 is equal to the smoothing variance 1 2π η 2 ε (Z). To summarize, the security parameter of LWE is (bounded by) the solution of the following system of equations

λ(n, α) = log 2 (t attack ) = min 0<ε<1 log 2 1 ε 2 t BKZ (n, α, ε) (3) log 2 (t BKZ )(n, α, ε) = 0.009 log 2 (δ) 2 -27 (4) ln(δ)(n, α, ε) = max m>1 q>1 1 2(m+n) ln 1 2π η 2 ε (Z) -ln S 2 q 2 n m+n + q 2n m α 2 m m+n (5) 1 2π η 2 ε (Z) ≈ 1 2π 2 ln 2 ε . (6)
Here, Equation ( 3) means that we need to run the distinguisher 1 ε 2 times (by Chernoff's bound), and we need to optimize the advantage ε accordingly. 16Equation ( 4) is the heuristic prediction of the running time of lattice reduction. In Equation ( 5) q and m need to be chosen in order to maximize the targeted approximation factor of the lattice reduction step.

Differentiating Equation ( 5) in q, we find that its maximal value is

q best = S 2 α 2 m 2(m+n)
.

Replacing this value and setting t = n m+n , Equation ( 5) becomes:

ln(δ)(n, α, ε) = max t>0 1 2n t 2 2 + t(1 -t) 1 where    1 = ln η 2 ε (Z) 2πα 2 2 = ln η 2 ε (Z) 2πS 2 .
Finally, by differentiating this new expression in t, the maximum of δ is reached for t best = 1 2( 1 -2) , because 1 > 2 , which gives the best choices of m and q and δ. Finally, we optimize ε numerically in Equation [START_REF] Albrecht | On the complexity of the BKW algorithm on LWE[END_REF].

All previous results are summarized in Figure 9, which displays the security parameter λ as a function of n, log 2 (α).

Remark 9. The analysis presented in this section corresponds to the original security analysis of papers [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF][START_REF] Chillotti | Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[END_REF]. In the meantime, many new cost models have been proposed in the literature and they were integrated in the new version of the LWE estimator [START_REF] Albrecht | On the concrete hardness of learning with errors[END_REF][START_REF] Albrecht | Estimate all the {LWE, NTRU} schemes[END_REF] and recommended in the Homomorphic Encryption Security Standard white paper [START_REF] Albrecht | Homomorphic encryption security standard[END_REF]. In Table 4 we provide new parameters for the gate bootstrapping, that achieve more than 128-bits of security in the classical model, and more than 80-bits of security in the quantum model. Gate bootstrapping Parameters. From a theoretical point of view, our scale invariant scheme is defined over the real torus T, where all the operations are modulo 1. In practice, since we can work with approximations, we chose to rescale the elements over T by a factor 2 32 , and to map them to 32-bit integers. Thus, we take advantage of the native and automatic mod 2 32 operations, including for the external multiplication with integers. Except for some FFT operations, this seems more stable and efficient than working with floating point numbers and reducing modulo 1 regularly. Polynomials mod X N + 1 are either represented as the classical list of the N coefficients, or using the Lagrange halfcomplex representation, which consists in the complex (2 • 64bits) evaluations of the polynomial over the roots of unity exp(i(2j + 1)π/N ) for j ∈ [[0, N 2 [[. Indeed, the N 2 other evaluations are the conjugates of the first ones, and do not need to be stored. The conversion between both representations is done using a dedicated assembly implementation of the Fast Fourier Transform (FFT) for the anticyclic ring (twice as using the generic library FFTW [START_REF] Frigo | The design and implementation of FFTW3[END_REF] used in by [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF]). Note that the direct FFT transform is √ 2N Lipschitz, so the lagrange half-complex representation tolerates approximations, and 53bits of precision is indeed more than enough, provided that the real representative remains small. However, the modulo 1 reduction, as well as the gadget decomposition in base h, are not compatible with the Lagrange representation: we therefore need to regularly transform the polynomials to and from their classical representation.

Applications, practical parameters and running time estimates

In the TFHE library [START_REF] Chillotti | TFHE: Fast fully homomorphic encryption library[END_REF], the gate bootstrapping uses the following parameters.

-TLWE samples use n = 500, and standard deviation α = 2 -7 , so their amplitude is < -Correctness: The final error variance after bootstrapping is 1.63 • 10 -5 , by Theorem 6.3. It corresponds to a standard deviation of σ = 4.05 • 10 -3 . In [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF], the final standard deviation is larger 1.08 • 10 -2 . In other words, the noise amplitude after our bootstrapping is < 1 16 with very high probability erf(1/16 √ 2σ) ≥ 1 -2 -150 (better than ≥ 1 -2 -32 in [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF]).

Note that the size of the key switching key can be reduced by a factor n + 1 = 501 if all the masks are the output of a pseudo random function; we may for instance just give the seed. The same technique can be applied to the bootstrapping key, on which the size is only reduced by a factor k + 1 = 2.

The source code of our implementation is available on github https:// github.com/tfhe/tfhe. We implemented the FHE scheme in C/C++, and run the bootstrapping algorithm on a 64-bit single core (i7-4910MQ) at 2.90GHz. This seems to correspond to the machine used in [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF]. We measured a running time of 13ms per bootstrapping, and of 34µs per external product, both using the Lagrange half-complex representation. Profiling the execution shows that the FFTs and complex multiplications are taking 66% of the total time. The remaining time is mostly taken by the keyswitch operation, and the decomposition in base h. As a consequence, all binary gates are executed in 13ms, and the native bootstrapped MUX (also described in Section 6.1) gate takes 26ms single core time (Table 2).

Table 3 shows that the strength of the lattice reduction is compatible with the values announced in [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF]. Our model predicts that the lattice reduction phase is harder (δ = 1.0052 in our analysis and δ = 1.0064 in [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF]), but the value of ε is bigger in our case. Overall, the security of their parameters-set is evaluated by our model to 149-bits of security, which is larger than the precises the parameters for the keyswitching key and the bootstrapping key for our implementation and for the one in [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF].

≥ 100-bits of security announced in [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF]. The main reason is that we take into account the number of times we need to run the SIS-distinguisher to obtain a non negligible advantage. Since our scheme has a smaller noise propagation overhead, we were able to raise the input noise levels in order to strengthen the system, so with the parameters we chose in our implementation, our model predicts 198-bits of security for the bootstrapping key and 163-bits for the keyswitching key (which becomes the bottleneck).

Remark 10. We generated several random Boolean circuits of depth larger than 10000, composed by a million of bootstrapped homomorphic gates. We executed them and measured the actual noise of the ciphertexts. The (light blue) histogram is the measured error distribution after every bootstrapped gate, the (purple) plain line represents the Gaussian distribution whose variance is predicted by Theorem 6.3 using the parameters of Section 8, and the (red) dashed line represents the critical Gaussian distribution for an amplitude of experimental results confirm that our average case theorem predicts the output variance accurately, and that the noise distribution after bootstrapping is Gaussian. This experimentally validates our independence heuristic assumption 3.11, even when ciphertexts are re-used in a very large depth homomorphic circuit (Figure 10).

Circuit Bootstrapping Starting from all these considerations, we implemented our circuit bootstrapping as a proof of concept. The code is available in the experimental repository of TFHE [START_REF] Chillotti | TFHE: Fast fully homomorphic encryption library[END_REF]. We perform a Circuit Bootstrapping in 0.137 seconds. One of the main constraints to obtain this performance is to ensure that all the computations are feasible and correct under 53 bits of floating point precision, in order to use the fast FFT. This requires to refine the parameters of the scheme. We verified the accuracy of the FFT with a slower but exact Karatsuba implementation of the polynomial product.

In our three levels, we used the following TRLWE and TRGSW parameter sets (Table 5), which have at least 152-bits of security, according to the security analysis from Section 7. Table 5. Parameters for levels 0, 1 and 2.

Since we assume circular security, we will use only one key per level, and the keyswitching parameters from Table 6 (in the leveled setting, the reader is free to increase the number of keys if he does not wish to assume circularity). TBSR Table 6. Parameters for all our keyswitchings.

Thus, we get these noise variances in input or in output (Table 7) Time Comparison With these parameters, we analyse the (single-core) execution timings for the evaluation of the LUT, MAX and Multiplication in LHE and FHE mode.

Output
In the LHE mode (left hand side of Fig. 11), all inputs are fresh ciphertexts (either TRLWE or TRGSW) and we compare the previous versions [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF] (without packing/batching or gate bootstapping) with the new optimizations i.e. horizontal/vertical packing; with weighted automata or with TBSR techniques. In the FHE mode (right hand side of Fig. 11), all inputs and outputs are TLWE samples on the {0, 1 2 } message space with noise amplitude 1 4 . Each operation starts by bootstrapping its inputs. We compare the gate-by-gate bootstapping strategy with the mixed version where we use leveled encryption with circuit bootsrapping. Our goal is to identify which method is better for each of the 6 cases. We observe that compared to the gate bootstrapping, we obtain a huge speed-up for the homomorphic evaluation of arbitrary function in both LHE and FHE mode, in particular, we can evaluate a 8 bits to 1 bit lookup table and bootstrap the output in just 137ms, or evaluate an arbitrary 8 bits to 8 bits function in 1.096s, and an arbitrary 16 bits to 8 bits function in 2.192s in FHE mode. For the multiplication in LHE mode, it is better to use the weighted automata technique when the number is less than 128 bits, and the TBSR counter after that. In the FHE mode, the weighted automata becomes faster than gate-bootstrapping after 4 bits of inputs, then the TBSR optimization becomes faster for > 64 bits inputs.

Conclusion and Open Problems

In this paper we presented a complete overview of the TFHE construction, from an abstract LWE and GSW point of view, to a concrete and efficient instantiation. We presented many improvements to the leveled and fully homomorphic modes: several ways to work over packed ciphertexts, new computation models that use TBSR counters and deterministic weighted automata techniques, as well as two efficient bootstrappings that operate in gate or circuit mode. We also provided a dedicated security analysis explaining how to chose the parameters depending on the desired security level, and we presented implementation details with practical timings for several applications using the techniques previously described.

We hope to enrich our framework by improving the efficiency of homomorphic evaluation for other arithmetic functions : we gave examples of the efficient homomorphic evaluation of the MAX and a counter mode operation involved in multiplication and division. It might be the case that our framework extends to other more complex arithmetic circuits with multiplicative operations which are targeted for concrete use-cases.

Optimized RNS (Residue Number System) implementation variants of BFV [START_REF] Bajard | A full rns variant of fv like somewhat homomorphic encryption schemes[END_REF][START_REF]of the BFV Homomorphic Encryption Scheme. Shai halevi and yuriy polyakov and victor shoup[END_REF] and HEEAN [START_REF] Cheon | A full RNS variant of approximate homomorphic encryption[END_REF] have recently been proposed and show a significant performance gain compared to their earlier respective implementation. RNS presents many benefits. In particular, it supports hardware implementations and is easily parallelizable. The TFHE scheme doesn't use an explicit q modulus and some of the operations we perform are not arithmetic operations. It is not clear how to use the double-CRT representation of cyclotomic polynomial ring elements. An interesting problem is to see how this translates in our setting.

On the implementation perspective, we plan on adding the additional features of the leveled mode of operations of TFHE on top of the library. We have implemented the circuit bootstrapping in the experimental branch. The next step is to implement the vertical and horizontal packing and to enhance the library with the homomorphic evaluation of TFHE ciphertexts using the automata model as explained in Section 5.2.

Our packing technique seems not to support efficient multiplicative SIMD operations for TRGSW ciphertexts. It would be useful to achieve such property

Fact 3 . 5 .e i 2 2•

 352 Given p valid and independent TLWE samples c 1 , . . . , c p under the same key s, and p integer polynomials e 1 , . . . , e p ∈ R, if the linear combination c = p i=1 e i • c i is a valid TLWE sample, it satisfies: msg(c) = p i=1 e i • msg(c i ), with variance Var(Err(c)) ≤ p i=1 Var(Err(c i )) and noise amplitude Err

Theorem 3 .

 3 13 (Worst-case External Product). Let A be a valid TGSW sample of message µ A and let b be a valid TLWE sample of message µ b . Then A b is a TLWE sample of message µ A • µ b and

  in the worst case, where β and are the parameters used in the decomposition Dec h,β, (b). If Err(A b) ∞ ≤ 1/4 we are guaranteed that A b is a valid TLWE sample. Proof. As A = TGSW(µ A ), then by definition it is equal to A = Z A + µ A • H, where Z A is a TGSW encryption of 0 and H is the gadget matrix. In the same way, as b = TLWE(µ b ), then by definition it is equal to b

Fig. 1 .

 1 Fig. 1. CMux gate -The CMux gate takes in input a TGSW sample C with message µC , a TLWE sample d0 with message µ d 0 and a TLWE sample d1 with message µ d 1 . It outputs a TLWE sample with message µ = µC • (µ d 1 -µ d 0 ) + µ d 0 . The η's and ϑ's represent respectively the noise in the worst and average case, for both the inputs and the output.

  and z d are respectively TGSW and TLWE samples of 0, and dec ∞ ≤ . Thus, CMux(C, d 1 , d 0 ) is the sum of four terms:

  Input: A TRLWE sample c of v ∈ TN [X] with key K. 1: p + 1 int. coefficients a1, . . . , ap, b ∈ Z/(2N Z) 2: p TRGSW samples C1, . . . , Cp of s1, . . . , sp ∈ B with key K

x 1 . . . x d- 1 Fig. 2 .

 112 Fig. 2. LUT with CMux tree -Intuitively, the horizontal rectangle encircles the bits packed in the horizontal packing, while the vertical rectangle encircles the bits packed in the vertical packing. The dashed square represents the packing in the case where the two techniques are mixed. The right part of the figure represents the evaluation of the sub-function fj on x = d-1 i=0 xi2 i via a CMux binary decision tree.

Lemma 5 . 2 (Fig. 3 .

 523 Fig. 3. Vertical packing for the evaluation of the fj LUT -As described in Algorithm 5, the image represents the idea of evaluation of the sub-function fj on x = d-1

i=0 xi2 i 1 : 3 :

 13 a list of d TRGSW samples Ci ∈ TRGSWK (xi), with xi ∈ B and i ∈ [[0, d -1]], Output: A TLWE sample c ∈ TLWE K (oj = fj(x)), with x = d-1 Evaluate the binary decision CMux tree of depth d -δ, with TRLWE inputs d0, . . . , d 2 d N -1 and TRGSW inputs C δ , . . . , C d-1 , and output a TRLWE sample d 2: d ← BlindRotate(d, (2 0 , . . . , 2 δ-1 , 0), (C0, . . . , C δ-1 )) Return c = SampleExtract(d)

Theorem 5 . 4 (

 54 Evaluation of det-WFA). Let A = (Q, i, B, T ) be a det-WFA with weights in (T N [X], +), and let |Q| denote the total number of states. Let C 0 , . . . , C d-1 be d valid TRGSW K samples of the bits of a word σ = σ 0 . . . σ d-1 . By evaluating at most d•|Q| CMux gates, Algorithm 6 outputs a TRLWE sample d that encrypts the weight w(σ), such that (using the same notations as inLemma 3.16)

Lemma 5 . 5 (

 55 Evaluation of Max det-WFA). Let A be the det-WFA of the Max, described in Figure 4. Let C x 0 , . . . , C x d-1 , C y 0 , . . . , C y d-1 be TRGSW K samples of the bits of x and y respectively. By evaluating 5d CMux gates (depth 2d), the Max det-WFA outputs a TRLWE sample d encrypting the maximal value between x and y and (with same notations as in Lemma 3.16) -Err(d) ∞ ≤ 2d • ((k + 1) N βA TRGSW + (kN + 1) ) (worst case), -Var(Err(d)) ≤ 2d • ((k + 1) N β 2 ϑ TRGSW + (kN + 1) 2 ) (average case).

Fig. 6 .

 6 Fig. 6. BSR -The figure represents the BSR(l). Here l = 0, N = 2 3 . The first column corresponding to k = 0 contains the bits of l in the little endian representation.

  p ].-TBSREncrypt(l): return a vector of non-trivial TRLWE ciphertexts encoding the torus representation of [B

  TBSRIncr(C), C); 11: end for 12: Out d-1+k ← TBSRBitExtract k (C) for each k ∈ [0, log 2 (m)]; 13: return Out and output all the bits

  -periodic or 128-antiperiodic. They can be packed on a single TRLWE ciphertext. The next two sequences B

Algorithm 8

 8 TBSR multiplication Input: The bitwise TRGSW-encryptions (Aj) j∈[0,d-1] ,(Bj) j∈[0,d-1] of two integers a, b of d-bits each Output: bitwise LWE encryptions of the product Out0, . . . , Out 2d-1 .

  corresponding to the functions fu(x) = -Ku • x when u ≤ k, andf k+1 (x) = 1 • x. Output: A level 1 TRGSW sample C ∈ TRGSWK,η(µ) 1: for w = 1 to 2: c(w) ← Bootstrapping BK, for u = 1 to k + 1 4: c (u,w) = PrivKS(KS (fu) , c(w) ) 5: Return C = (c (u,w) ) 1≤u≤k+1,1≤w≤

  TN [X] and ci the corresponding TRLWE ciphertext. The mi's are plaintexts in T and c their TLWE ciphertext. The bi's are bit messages and Ci their TRGSW ciphertext. The ϑi's are the noise variances of the respective ciphertexts. In the translation, w is in TN [X]. In the rotation, the ui's are integer coefficients. In the Z[X]-linear combination, the vi's are integer polynomials in Z[X].

Fig. 9 .

 9 Fig. 9. Security parameter λ as a function of n and α for LWE samples -This curve shows the security parameter levels λ (black levels) as a function of n = kN (along the x-axis) and log 2 (1/α) (along the y-axis) for TLWE (also holds for bin-LWE), considering both the attack of this section and the collision attack in time 2 n/2 .

  Gate bootstrapping mode Gate bootstrapping (1 bit)tGB = 13ms Time per any binary gate (HomAND, HomOR, HomXOR, ...) tGB = 13ms Time per HomMUX 2tGB = 26ms

3 Fig. 10 .

 310 Fig. 10. Accuracy of the average case theorems, and experimental validation of the independence assumption.

Level t KS noise stdev γ Usage 1 →

 1 0 t = 12 γ = 6.10 • 10 -5 Circuit Bootstap, Pre-KS 2 → 1 t = 30 γ = 3.29 • 10 -10 Circuit Bootstap, Step 4 in Alg. 11 1 → 1 t = 24 γ = 2.38 • 10 -8

  . The same reduction for the Ring variant of LWE is still an open problem.

	10 A submodule G is sufficiently dense if there exists an intermediate submodule H
	such that G ⊆ H ⊆ T n , the relative smoothing parameter ηH,ε(G) (a.k.a. smoothing
	parameter of H/G) is ≤ α, and H is the orthogonal in T n of at most n -1 vectors
	of Z n . This definition allows to convert any (Ring)-LWE with non-binary secret to a
	TLWE instance via binary decomposition.

  -4 . . . σ s-1,2 d -4 σ j,2 d -4

	x0 . . . x d-1	f0	. . . fs-1
	0 . . . 0	σ0,0	. . . σs-1,0	σj,0
	1 . . . 0	σ0,1	. . . σs-1,1	σj,1
	0 . . . 0	σ0,2	. . . σs-1,2	σj,2
	1 . . . 0	σ0,3	. . . σs-1,3	σj,3
	. . .	. . . . . .	. . .	. . .	. . .	. . .
	0 . . . 1	σ 0,2 d

Table 1 .

 1 TFHE elementary operations -In this table, all µi's denote plaintexts in

	Operation	Plaintext	Ciphertext	Variance
	Translation	µ + w	c + (0, w)	ϑ
	Rotation	X u i µ	X u i c	ϑ
	Z[X]-linear	viµi	vici	vi 2 2 ϑi
	SampleExtract	µiX i → µp	SampleExtract (Sect. 2.2)	ϑ
	Z-linear	f (m1, . . . , mp) PubKS KS (f, c1, . . . , cp)(Alg.2) R-lipschitzian PrivKS KS (f ) (c1, . . . , cp)(Alg.3) R 2 ϑ + np log 1 R 2 ϑ + n log 1 α CstKS α CstKS
	Ext. product	b1 • µ2	C1 c2 (Thm.3.13)	b1ϑ2 + Cst TRGSW ϑ1
	CMux	b1?µ2 : µ3	CMux(C1, c2, c3) (Lem.3.16) max(ϑ2, ϑ3) + Cst TRGSW ϑ1
	T-non-linear	X -ϕ(c 1 ) µ2	BlindRotate (Alg.4)	ϑ + nCst TRGSW
	Bootstrapping decrypt(c)?m : 0 Gate Bootstrapping (Alg.9)	Cst
			Circuit Bootstrapping (Alg.11)

  1 16 . A TLWE sample has 32 • (n + 1) bits ≈ 2 KBytes.-TRLWE samples use N = 1024, k = 1. This corresponds to (k + 1) • N • 32 bits ≈ 8 KBytes. -TRGSW samples use = 2,B g = 1024. This defines the gadget H and its decomposition Dec h,β, where β = 512 and = 2 -21 . A TRGSW sample has (k + 1) • TLWE samples ≈ 32 KBytes. -The Bootstrapping Key has n TGSW samples ≈ 15.6 MBytes. Its noise standard deviation is α = 3.73 • 10 -9 . Since we have a lower noise overhead, this is higher than the standard deviation ≈ 2.59 • 10 -10 of [29], (i.e. ours is more secure), but in counterpart, our TLWE key is binary. Section 7 predicts 198 bits of security for this key. -We chose t = 16 bits for the key switching: the decomposition has precision 2 -17 , and the KS has k • N • t LWE samples ≈ 32 MBytes. We set the noise stdev to γ = 2.16 • 10 -5 , which is estimated to λ = 159-bits of security by Section 7.

Table 2 .

 2 Timings for the Gate Bootstrapping mode -Since 2016 the speed of processors has increased and using the same algorithms and parameters the timing of gate bootstrapping (with the parameters in the Table 3) has decreased between 7ms and 10ms. n α λ ε best m best q best δ best Switch key 500 2.43 • 10 -5 159 2 -14 497 178.7 1.0052 Boot. key 1024 3.73 • 10 -9 198 2 -10 1037 14696. 1.0046 Boot.key, [29] 1024 2.59 • 10 -10 149 2 -7 1051 60351 1.0052

Table 3 .

 3 Parameters and security of the Gate bootstrapping -This table

Table 4 .

 4 New Parameters and security of the Gate bootstrapping -This table shows the parameters for the keyswitching key and the bootstrapping key based on the recent cost models recommended in the homomorphic encryption security standard[START_REF] Albrecht | Homomorphic encryption security standard[END_REF]. In the table λclassic is the security level secure against primal classical attack and λquantum is for the quantum attack.

	1 16 . The

Table 7 .

 7 TLWE Fresh TRGSW in LHE TRGSW Output of CB Bootst. key ϑ ≤ 2 -10 ϑ = 2 -60 ϑ ≤ 2 -48.2 ϑBK = 2 -92 Noise variances.And finally, Table8summarizes the timings (Core i7-4910MQ laptop), noises overhead, and maximal depth of all our primitives.

		CPU Time Var Noise add max depth
	Circuit bootstrap tCB = 137ms N.A.	N.A
	Fresh CMux	tXP = 34µs 2 -23.99	16384
	CB CMux	tXP = 34µs 2 -20.17	1017
	PubKST BSR	tKS = 180ms 2 -23.42	16384

Table 8 .

 8 Timings, noise overheads and maximal depth.

For the first two distributions, it is tight, but the uniform distribution over [-√ 3σ, √ 3σ] is even 0.78σ-subgaussian

Mathematically speaking, a more accurate notion would be distp(x, y) = xy p , which is a distance. However, the norm symbol is clearer for almost all practical purposes.

Probabilistic Polynomial Time.

Talking about maximum amplitude is an abuse of notation. A more correct approach would be to use a truncated distribution (as suggested in[START_REF] Micciancio | Trapdoors for lattices: Simpler, tighter, faster, smaller[END_REF]) in order to avoid all the negligible amounts appearing in the probability formulas.

N -1 j=0 K N (i-1)+j+1 X j . In this case, we say that K is the TRLWE interpretation of K, and K is the TLWE interpretation of K.

p i=1 s i a i , such that:

Circular security assumption could still be avoided in leveled mode if we accept to work with many keys.

The TRLWE samples can be trivial samples, in the case where the function f and its LUT are public.

If the sub-function fj and its LUT are public, the LUT values σj,0, . . . , σ j,2 d -1 can be given in clear. This means that the TRLWE samples dp, for p ∈ [[0, 2 d N -1]] are given as trivial TRLWE samples dp ← (0, N -1 i=0 σj,pN+iX i ) in input to algorithm 5.

For the p-th bit, one would return SampleExtract(cp) + (0,1 4 ), but it is always 0 if l ∈ [0, N -1].

Amplifying a distinguishing advantage from to Ω(1) requires at least O(1/ε) and at most (1/ε 2 ) trials, depending on the shape of the symmetric difference between the two distributions. Here, the difference between a modular Gaussian with large parameter and the uniform distribution is uniformly small, so we have to apply the upper-bound.

Acknowledgements

This work has been supported in part by the CRYPTOCOMP project. The authors would like to thank the anonymous reviewers of this paper and of the papers [22] and [24], as well as the Asiacrypt 2016 committee for rewarding [22] with the best paper award and for the invitation to submit at Journal of Cryptology. The authors would also like to thank Damien Stehlé, Fernando Virdia and Matthias Minihold for the discussions and for their helpful comments.

on N consecutive values, the rest is deduced by periodicity. To map the increment operation, all we need to do is shifting the sequences by 1 position

More generally, we can increment the BSR by any integer in [[0, N -1]], as in Figure 7. ]. As the BSR is the representation of integers in base 2, when we want to perform the division by 2, it corresponds to eliminate the first line and keep just the odd columns of the BSR (see Figure 7). Thus we can set

j+1,2k for j ∈ [[0, p -1]] and ∀k ∈ Z.

The only exception is the last line of the BSR, that has to be regenerated. Indeed, B (l) j+1,2k is the (j +1)-th bit of l+2k and it is the j-th bit of its half l/2 + k, which is our desired B ( l/2 ) j,k . This is unfortunately not enough to reconstruct the last sequence B ( l/2 ) p , since we have no information on the (p + 1)-th bits in BSR(l). However, in our case, we can reconstruct this last sequence directly. First, the numbers l 2 + k for k ∈ [0, N/2 -1] are all < N , so we can blindly set the corresponding B ( l 2 ) p,k = 0. Then, we just need to note that (B (l) p,0 , . . . , B (l) p,N -1 ) is N -l times 0 followed by l times 1, and our target (B

p,N/2 , . . . , B

p,N -1 ) must consist N/2 -l times 0 followed by l/2 times 1. Therefore, our target can be filled with the even positions (B

p,N -2 ). To summarize, the last line of the BSR in the division by 2 corresponds to the following blind transformation:

TBSR We now explain how we can encode these BSR sequences on TRLWE ciphertexts, considering that all the coefficients need to be in the torus rather than in B, and that we need to encode sequences that are either N -periodic or N -antiperiodic. We note the encoded BSR by TBSR. Therefore, this is our basic encoding of the BSR sequences: let

p ] be the BSR of some unknown number l ∈ [[0, N -1]]. For j ∈ After the blind rotation, the message in the accumulator is msg(ACC) = X -φ • v. After SampleExtract, the message is equal to the constant term of msg(ACC), i.e. -µ if φ ∈]] N 2 , 3 2), we obtain that the message is equal to 0.

We first provide a comparison between the bootstrapping of Algorithm 9, the Algorithm 1, 2 in [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF] and the Algorithm 3 in [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF].

-Like [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF] and [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF], we rescale the computation of the phase of the input TLWE sample so that it is modulo 2N (line 2) and we map all the corresponding operations in the multiplicative cyclic group {1, X, . . . , X 2N -1 }.

Since our TLWE samples are described over the real torus, the rescaling is done explicitly. This rescaling may induce a cumulated rounding error of amplitude at most δ ≈ √ n/4N in the average case and δ ≤ (n + 1)/4N in the worst case. In the best case, this amplitude can even be zero (δ = 0) if in the actual representation of TLWE samples, all the coefficients are restricted to multiple of 1 2N . -As in [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF] and [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF], messages are encoded as roots of unity in R. Our accumulator is a TRLWE sample (as in [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF]) instead of a TRGSW sample (as in [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF]). Also accumulator operations use the external product from Theorem 3.13 instead of the slower classical internal product. The test vector (1+X+ . . . +X N -1 ) is embedded in the accumulator from the very start, when the accumulator is still noiseless while in [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF], it is added at the very end. This removes a factor √ N to the final noise overhead. -Instead of the explicit loop proposed in [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF] and in [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF], we directly use the blind rotation Algorithm 4. As in [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF], all the TRGSW ciphertexts of X -ãiKi required to update the accumulator internal value are computed dynamically as a very small polynomial combination of BK i in the for loop of the Algorithm 4. This completely removes the need to decompose each ãi on an additional base B r , and to precompute all possibilities in the bootstrapping key. In other words, this makes our bootstrapping key 46 times smaller than in [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF], for the exact same noise overhead. Besides, due to this squashing technique, two accumulator operations were performed per iteration instead of one in our case. This gives us an additional 2× speed up. Also, a small difference in the way we associate CMux operations in Algorithm 4 removes a factor 2 in the noise compared to the previous gate bootstrapping procedure in [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF], and it is also faster. The speed ups have been obtained on a 64-bit (single core) Intel Core i7-4910MQ at 2.90GHz laptop, for 159-bits of security: more details are given in Section 7 and in Section 8.

The Algorithm 9 takes in input a TLWE ciphertext, and depending on its phase, it outputs either a ciphertext of 0 or of µ with a noise amplitude that is independent on the input. However, the input and output ciphertexts are not Algorithm 10 Gate Bootstrapping (calling Algorithms 9 and 2)

, with KS

i,j ∈ TRLWE K ,γ ( Ki 2 j ) be a key-switching key defined as in Theorem 4.2 (with the function f equal to the identity function id : T → T). Given one constant µ 1 ∈ T, and one sample c ∈ T n+1 whose coefficients are all multiples of 1 2 N , Algorithm 10 outputs a TLWE sample c ∈ TLWE K (µ) where µ = 0 iff |ϕ K (c)| < 1 4 , µ = µ 1 otherwise and such that:

where ĀBK and θBK = ᾱ2 are respectively the amplitude and the variance of the error of BK, and A KS and ϑ KS = γ 2 are respectively the amplitude and the variance of the error of KS.

Fully Homomorphic Boolean Gates. In [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF], the homomorphic evaluation of a NAND gate between LWE samples is achieved with 2 additions (one with a noiseless trivial sample) and a gate bootstrapping (Algorithm 10).

We chose the parameters such that Var(Err(c )) < 1 16 and we denote as c = Bootstrap (c) the output of the gate bootstrapping (Algorithm 9, with µ 1 = 1 4 ) plus key-switching (Algorithm 3) procedures applied to c.

Let us consider two TLWE samples c 1 and c 2 , with message space {0, 1/4} and Err(c 1 ) ∞ , Err(c 2 ) ∞ ≤ 1 16 . The result of the bootstrapped NAND gate is obtained by computing c = (0, 5 8 )-c 1 -c 2 , plus a bootstrapping (gate bootstrapping and key-switching). Indeed the possible values for the messages of c are 5 8 , 3 8 if either c 1 or c 2 encode 0, and 1 8 if both encode 1 4 . Since the noise amplitude Err(c) ∞ is < 1 8 , then |ϕ K (c)| > 1 4 iff NAND(msg(c 1 ), msg(c 2 )) = 1. This explains why it suffices to bootstrap c with parameters µ 1 = 1 4 to get the answer.

By using a similar approach, it is possible to directly evaluate with a single bootstrapping all the basic gates:

-

The HomXOR(c 1 , c 2 ) gate can be achieved also by performing Bootstrap (2 • (c 1 +c 2 )).

Remark 8. The term gate bootstrapping refers to the fact that this fast bootstrapping is performed after every gate evaluation, but it can be used even if we do not need to evaluate a specific gate and we just want to refresh noisy ciphertexts.

The ternary MUX gate (MUX(c,

is generally expressed as a combination of 3 binary gates. As already mentioned in [START_REF] Ducas | FHEW: Bootstrapping homomorphic encryption in less than a second[END_REF], we can improve the MUX evaluation by performing the middle ⊕ as a regular addition before the final KeySwitching. Indeed, this xor has at most one operand which is true, and at this location, it only affects a negligible amount of the final noise. Overall, the ternary MUX gate can be evaluated in FHE mode by evaluating only two gate bootstrappings and one public key-switching. We call this procedure native MUX, and we note it HomMUX as the other bootstrapped homomorphic gates, which computes:

c ∧ d 1 via a gate bootstrapping (Algorithm 9) of (0, -1 8 ) + c + d 1 ; -(1 -c) ∧ d 0 via a gate bootstrapping (Algorithm 9) of (0, 1 8 ) -c + d 0 ; a final public key-switching (Algorithm 2) on the sum, which dominates the noise.

This HomMUX is therefore bootstrappable with the same parameters for the other binary gates. In the rest of the paper, when we compare different homomorphic techniques, we refer to the gate bootstrapping mode as the technique consisting in evaluating small circuits expressed by using this bootstrapped gates.

Circuit bootstrapping (TLWE-to-TRGSW)

In the previous sections, we presented efficient leveled algorithms for some arithmetic operations, but the input and output have different types (e.g. TLWE/TRGSW) and we can not compose these operations, like in a usual algorithm. In fully homomorphic mode, connecting the two becomes possible if we

Eval Circuit Fig. 8. The figure represents the three levels of encryption on which our construction shifts. The arrows show the operations that can be performed inside each level or how to move from a level to another. In order to distinguish the objects with respect to their level, we adopted the intuitive notations "superior bar" for level 2, "no bar" for level 1 and "under bar" for level 0. We highlight in blue the different stages of the circuit bootstrapping (whose detailed description is given below).

1. TLWE-to-TLWE Pre-keyswitch: The input of the algorithm is a TLWE sample with a large noise amplitude over the message space {0, 1 2 }. Without loss of generality, it can be keyswitched to a level 0

2 ), of a message µ ∈ B with respect to the small secret key K ∈ B n and a large standard deviation η ∈ R (typically, η ≤ 2 -5 to guaranty correct decryption with overwhelming probability). This step is standard.

2. TLWE-to-TLWE Bootstrapping (Algorithm 9): Given a level 2 bootstrapping key BK K→ K, ᾱ = (BK i ) i∈[ [1,n]] where BK i ∈ TRGSW K, ᾱ(K i )), we use times the TLWE-to-TLWE Bootstrapping algorithm (algorithm 9) on c, to obtain TLWE ciphertexts c(1) , . . . , c( ) where c(w) ∈ TLWEK ,η (µ• 1 Bg w ), with respect to the same level 2 secret key K ∈ B n, and with a fixed noise parameter η ∈ R which does not depend on the input noise. If the bootstrapping key has a level 2 noise ᾱ, we expect the output noise η to remain smaller than level 1 value. especially if we want to efficiently evaluate homomorphic circuits involving both TRLWE and TRGSW ciphertexts.