Ilaria Chillotti
email: ilaria.chillotti@zama.ai

Damien Ligier
email: damien.ligier@zama.ai

Jean-Baptiste Orfila
email: jb.orfila@zama.ai

Samuel Tap
email: samuel.tap@zama.ai

Improved Programmable Bootstrapping with Larger Precision and Efficient Arithmetic Circuits for TFHE

Fully Homomorphic Encryption (FHE) schemes enable to compute over encrypted data. Among them, TFHE [CGGI17] has the great advantage of offering an efficient method for bootstrapping noisy ciphertexts, i.e., reduce the noise. Indeed, homomorphic computation increases the noise in ciphertexts and might compromise the encrypted message. TFHE bootstrapping, in addition to reducing the noise, also evaluates (for free) univariate functions expressed as look-up tables. It however requires to have the most significant bit of the plaintext to be known a priori, resulting in the loss of one bit of space to store messages. Furthermore it represents a non negligible overhead in terms of computation in many use cases.

In this paper, we propose a solution to overcome this limitation, that we call Programmable Bootstrapping Without Padding (WoP-PBS). This approach relies on two building blocks. The first one is the multiplication à la BFV [FV12] that we incorporate into TFHE. This is possible thanks to a thorough noise analysis showing that correct multiplications can be computed using practical TFHE parameters. The second building block is the generalization of TFHE bootstrapping introduced in this paper. It offers the flexibility to select any chunk of bits in an encrypted plaintext during a bootstrap. It also enables to evaluate many LUTs at the same time when working with small enough precision. All these improvements are particularly helpful in some applications such as the evaluation of Boolean circuits (where a bootstrap is no longer required in each evaluated gate) and, more generally, in the efficient evaluation of arithmetic circuits even with large integers. Those results improve TFHE circuit bootstrapping as well. Moreover, we show that bootstrapping large precision integers is now possible using much smaller parameters than those obtained by scaling TFHE ones.

Introduction

Fully Homomorphic Encryption (FHE) is a family of encryption schemes allowing to perform computation over encrypted data. FHE schemes use noisy ciphertexts for security reasons, i.e., ciphertexts containing some randomness. This noise grows after every performed homomorphic operation, and, if not controlled, can compromise the message and prevent the user from decrypting correctly. A technique called bootstrapping and introduced by Gentry [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] allows to reduce the noise, by mean of a public key called bootstrapping key. By using bootstrapping frequently, thus reducing the noise when needed, one can perform as many homomorphic operations as she wants, but it remains an expensive technique, both in terms of execution time and memory usage.

Nowadays, the most practical FHE schemes are based on the hardness assumption called Learning With Errors (LWE), introduced by Regev in 2005 [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF], and on its ring variant (RLWE) [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]. Even if bootstrapping is possible for all these schemes, some of them (such as BGV [START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF], BFV [START_REF] Brakerski | Fully homomorphic encryption without modulus switching from classical gapsvp[END_REF][START_REF] Fan | Somewhat practical fully homomorphic encryption[END_REF] and CKKS [START_REF] Hee Cheon | Homomorphic encryption for arithmetic of approximate numbers[END_REF]) actually avoid it because the technique remains a bottleneck. These schemes make use of RLWE ciphertexts exclusively and adopt a leveled approach, which consists in choosing parameters that are large enough to tolerate all the noise produced during the computation. These schemes take advantage of SIMD encoding [START_REF] Smart | Fully homomorphic SIMD operations[END_REF] to pack many messages in a single ciphertext and perform the homomorphic evaluations in parallel on all of these messages at the same time, and they naturally perform homomorphic multiplications between RLWE ciphertexts by doing a (tensor) product followed by a relinearization/key switching.

TFHE [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][START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF] is also an (R)LWE-based FHE scheme which differentiates from the other (R)LWE-based cryptosystems because it supports a very efficient bootstrapping technique. TFHE was originally proposed as an improvement of FHEW [START_REF] Ducas | FHEW: bootstrapping homomorphic encryption in less than a second[END_REF], a GSW [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF] based scheme with a fast bootstrapping for the evaluation of homomorphic Boolean gates. Apart from improving FHEW bootstrapping, TFHE also introduces new techniques in order to support more functionalities than the ones proposed by FHEW and to improve homomorphic evaluation of complex circuits. TFHE efficiency comes in part from the choice of a small ciphertext modulus which allows to use CPU native types to represent a ciphertext both in the standard domain and in Fourier domain. This is what we call the TFHE context.

TFHE encrypts messages in the most significant bits, meaning a message m ∈ Z is rescaled by a factor ∆ ∈ Z before being reduced modulo q. The small noise e ∈ Z is added in the least significant bit, so a noisy plaintext looks like ∆ • m + e mod q. In this paper, when we refer to bits of precision, we mean the quantity p = log 2 ( q ∆ ). We illustrate this in Figure 1. Note that if m > 2 p some of the information in m will be lost because of the modulo q.

TFHE bootstrapping is very efficient, but also programmable, meaning that a univariate function can be evaluated at the same time as the noise is being reduced. It is often called programmable bootstrapping [CJL + In TFHE, messages are encoded in the most significant bits (MSB), and so it is rescaled by a scaling factor ∆, while the error appears in the least significant bits (LSB). The precision is log 2 ( q ∆ ), i.e 7 bits in the figure .   function to be evaluated is represented as a look-up table (LUT) and the bootstrapping rotates this table (stored in an encrypted polynomial) in order to output the correct element in the table. The LUT has to have redundancy (each coefficient is repeated a certain amount of time consecutively) in order to remove the input ciphertext noise during the PBS.

A multi-output version of the PBS is described in [START_REF] Carpov | New techniques for multi-value input homomorphic evaluation and applications[END_REF] allowing the evaluation of multiple (negacyclic) functions {f i } i over one encrypted input. Each function f i is encoded as a LUT in a polynomial P i . One can find a shared polynomial Q such that we can decompose each P i as Q • P i and compute CT out ← PBS(ct in , BSK, Q). Then, one needs to multiply CT out by each of P i and sample extract the resulting ciphertexts. One would have obtained the evaluation of each function. One drawback of this method is that the noise inside the i-th output ciphertexts depends on P i .

A recent paper revisits the TFHE bootstrapping [START_REF] Guimarães | Revisiting the functional bootstrap in TFHE[END_REF]. It gives two algorithms and a few optimizations to compute programmable bootstrapping on large precision ciphertexts encrypting one message decomposed in a certain base. Those algorithms could be used to homomorphically compute multivariate functions if we call them with the right lookup tables.

The BGV/BFV/CKKS leveled approach is very convenient when the circuit that has to be homomorphically evaluated is small in terms of multiplicative depth, but also known in advance. When multiple inputs have to be evaluated with the same circuit at once, this approach is also very good in terms of amortized computation time. However, when the circuit is deep and unknown a priori, the TFHE approach is more convenient.

A recent work by Boura et al., called Chimera [START_REF] Boura | CHIMERA: combining ring-lwe-based fully homomorphic encryption schemes[END_REF], tries to take advantage of both approaches, by building bridges between FHE schemes (TFHE, BFV and CKKS), in order to switch between them depending on which functionality is needed.

TFHE and its fast PBS are very powerful, but have some limitations:

A In general, to correctly bootstrap a ciphertext, its encrypted plaintext needs to have its first Most Significant Bit (MSB) set to zero (or at least known). The only exception is when the univariate function evaluated is negacyclic.

B One cannot bootstrap efficiently a message with a large precision (e.g., more than 6 bits). The number of bits of the message we bootstrap is strictly related to the dimension N of the ring chosen for the PBS. This means that the more we increase the precision, the more we have to increase the parameter N , and the slower the computation is.

C The PBS algorithm is not multi-thread friendly. Indeed, it is a loop working on an accumulator. D There exists no native multiplication between two LWE ciphertexts. There are two approaches to multiply LWE ciphertexts: (i) use two programmable bootstrappings to evaluate the function x → x 2 4 so we can build the multiplication x•y = (x+y) 2 4 -(x-y) 2 4 ; (ii) use 1 or more TFHE circuit bootstrappings [START_REF] Chillotti | Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[END_REF]Alg. 6] in order to convert one of the inputs into a GGSW (if not given as input) and then performing an external product. Since both techniques use PBS, they both suffer from limitations A and B. E Because of limitations A and B it is not possible, in an efficient manner, to homomorphically split a message contained in a single ciphertext into several ciphertexts containing smaller chunks of the original message.

F The PBS can evaluate only a single function per call. Using the [START_REF] Carpov | New techniques for multi-value input homomorphic evaluation and applications[END_REF] trick, we can evaluate multiple Look-Up Tables at the same time, but the output will have an additional amount of noise which depends on the function evaluated.

G TFHE gate bootstrapping represents a very easy solution for evaluating homomorphic Boolean circuits. However, this technique requires a PBS for each binary gate, which results in a costly execution. Furthermore, when we want to apply a similar approach to the arithmetic circuit with bigger integers (more than 1 bit), TFHE does not provide a solution.

H TFHE circuit bootstrapping requires PBS followed by many key switchings which is quite time consuming.

Contributions. In this paper we overcome the above-mentioned TFHE limitations. First, we generalize TFHE PBS so it can evaluate several functions at once without additional computation or noise. This approach is possible when the message to bootstrap is small enough. It overcomes limitation F and enables to compute a single generalized PBS when computing a circuit bootstrapping instead of PBS, overcoming limitation H. Circuit bootstrapping is particularly interesting in the leveled evaluation of Look-Up Tables, as shown in [START_REF] Chillotti | Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[END_REF]. Furthermore, we thoroughly study the noise growth when computing a tensor product followed by a relinearization (i.e., the BFV-like multiplication) and found parameters compatible with the TFHE context representing a new way of computing LWE multiplications in TFHE. This multiplication is efficient and does not require a PBS which overcomes limitation D. We also propose a packed use of this algorithm to compute several LWE products at once or a sum of several LWE products at once. Our noise analysis is also valid for BFV-like schemes and can help estimate the noise growth there.

From this multiplication, we define a new PBS procedure that does not require the MSB to be set to zero, overcoming limitation A. This new procedure is composed of few generalized PBS that can be computed in parallel which makes it more multithread compatible (limitation C). Observe that, differently from Chimera, which builds bridges to move between different schemes, we add the support for a BFVlike multiplication into TFHE, in order to remove some of the TFHE limitations. In this way, we don't need to switch between schemes, and we can remain all the time in the TFHE context.

From this new PBS we are able to homomorphically decompose a plaintext from a single ciphertext into several ciphertexts encrypting blocks of the input plaintext, overcoming limitation E, and also relax the need for PBS at every gate in the gate bootstrapping and its generalization, overcoming limitation G.

From this new decomposition algorithm and the Tree-PBS algorithm [START_REF] Guimarães | Revisiting the functional bootstrap in TFHE[END_REF], we are able to create a fast PBS for larger input messages, overcoming limitation B. We can also in an even faster manner refresh the noise (bootstrap, not PBS) in a ciphertext from this new decomposition algorithm.

Background and Notations

The parameter q is a positive integer and represents the modulo for the integers we are working with. We note Z q the ring Z/qZ. The parameter N is a power of 2 and represents the size of polynomials we are working with. We note R q the ring Z q [X]/(X N + 1). A Gaussian distribution with a mean set to zero and a standard deviation set to σ is written χ σ . We use the symbol || for concatenation. When ι is an integer, we note by [•] ι the reduction modulo ι and by • ι the rounding then the reduction modulo ι. We refer to the most (resp. least) significant bits of an integer as MSB (resp. LSB). We alse refer to look-up tables as LUT. The (computational) complexity of an algorithm Alg, potentially dependent on some parameters

p 1 , • • • , p n , is denoted C p 1 ,••• ,pn Alg .
Remark 1 Observe that in this paper we use different notations compared to TFHE [CGGI16, CGGI17, CGGI20]. In TFHE, the message and ciphertext spaces are expressed by using the real torus T = R/Z. On a computer, they implemented T by using native arithmetic modulo 2 32 or 2 64 , which means that they work on Z q (with q = 2 32 or q = 2 64 ). This is why we prefer to use Z q instead of T, as already adopted in [CJL + 20]. It is made possible because there is an isomorphism between Z q and 1 q Z/Z as explained in [BGGJ20, Section 1].

LWE, RLWE & GLWE Ciphertexts.

A GLWE ciphertext of a message M ∈ R q with the scaling factor ∆ ∈ Z q under the secret key S ∈ R k q is defined as follows:

CT = (A 1 , • • • , A k , B = k i=1 A i • S i + M • ∆ q + E) = GLWE S (M • ∆) ∈ R k+1 q such that S = (S 1 , • • • , S k ) ∈ R k q
is the secret key with coefficients either sampled from a uniform binary, uniform ternary or Gaussian distribution, {A i } k i=1 are polynomials in R q with coefficients sampled from the uniform distribution in Z q , E is an noise (error) polynomial in R q such that its coefficients are sampled from a Gaussian distributions χ σ . The parameter k is a positive integer and represents the number of polynomials in the GLWE secret key. To simplify notations, we sometimes define S k+1 as -1.

A GLWE ciphertext with N = 1 is an LWE ciphertext and in this case we consider the parameter n = k for the size of the LWE secret key and we note both the ciphertext and the secret with a lower case e.g. ct and s. A GLWE ciphertext with k = 1 and N > 1 is an RLWE ciphertext.

Lev, RLev & GLev Ciphertexts. A GLev ciphertext with the base B ∈ N * and ∈ N * levels, of a message M ∈ R q under the GLWE secret key S ∈ R k q is defined as the following vector of GLWE ciphertexts:

CT = (CT 1 , • • • , CT ) = GLev B, S (M ) ∈ R ×(k+1) q where CT i = GLWE S (M • q B i
) is a GLWE ciphertext. A GLev ciphertext with N = 1 is a Lev ciphertext and in this case we consider the parameter n = k for the size of the LWE secret key. A GLev ciphertext with k = 1 and N > 1 is a RLev ciphertext.

Decomposition Algorithms. The decomposition algorithm in the integer base B ∈ N * with ∈ N * levels is written dec (B, ) and takes as input an integer x ∈ Z q and output a decomposition vector of integers (x 1 , • • • , x ) ∈ Z q such that:

dec (B, ) (x), q B 1 , • • • , q B = x • B q • q B ∈ Z q
Note that this decomposition starts from the MSB. When we apply this decomposition on a vector of integers, we end up with a vector of decomposition vector of integers.

We can also decompose an integer polynomials X ∈ R q into a decomposition vector of polynomials (X 1 , • • • , X ) ∈ R q such that:

dec (B, ) (X), q B 1 , • • • , q B = X • B q • q B ∈ R q
When we apply this decomposition on a vector of polynomials, we end up with a vector of decomposition vectors of polynomials.

Key Switching.

A technique that is often used in FHE, called key switching, allows to change parameters and keys in the ciphertext. The key switching makes the noise grow and is performed using a so-called key-switching key which is a public key composed of encryptions of secret key elements. There are different types of key switchings: we will quickly list and describe the ones that are interesting for the understanding of the paper. The LWE-to-GLWE key-switching key is noted KSK and is equal to

KSK = CT i = GLev B, S (s i ) 1≤i≤n
, where s = (s 1 , . . . , s n ) ∈ Z n q is the input LWE secret key and S = (S 1 , . . . , S k ) ∈ R k q is the output GLWE secret key.

• CT out ← PrivateKS({ct i } i∈{1,...,p} , KSK) : allows to apply a private lin-

ear function f : (Z/qZ) p -→ Z/qZ[X] over p LWE ciphertexts {ct i = LWE s (m 1 )} i∈{1,...,p} and creates a GLWE ciphertext CT out = GLWE S (f (m 1 , • • • , m p )). For more details check [CGGI17, Algorithm 2].
• CT out ← PublicKS({ct i } i∈{1,...,p} , KSK, f ) : is a public version of the previous key switching, i.e., a key switching with a public linear function f . For more details check [CGGI17, Algorithm 1]. The key switching used in TFHE PBS is a public key switching, where the function f is the identity function and the output GLWE is instantiated with k = n and N = 1 (i.e., as an LWE instance).

• CT out ← PackingKS({ct j } p j=1 , {i j } p j=1 , KSK) : is a (public) key switching procedure enabling to pack several LWE ciphertexts into one GLWE. It takes as input a set of p LWE ciphertexts as well as a set of p indexes. Given the set of indexes {i j } p j=1 , the function f has the following shape:

f ({m j } p j=1 ) -→ p j=1 m j • X i j .
GSW, RGSW & GGSW Ciphertexts. A GGSW ciphertext with the base B ∈ N * and ∈ N * levels, of a message M ∈ R q under the GLWE secret key

S = (S 1 , • • • , S k ) ∈ R k
q is defined as the following vector of GLev ciphertexts:

CT = CT 1 , • • • , CT k+1 = GGSW (B, ) S (M ) ∈ R (k+1)× ×(k+1) q where CT i = GLev (B, ) S (-S i • M ) is a GLev ciphertext.
Remember that we note S k+1 = -1.

A GGSW ciphertext with N = 1 is a GSW ciphertext, and a GGSW ciphertext with k = 1 and N > 1 is a RGSW ciphertext. TFHE PBS. The bootstrapping of TFHE has a double functionality: it reduces the noise in the ciphertexts and at the same time evaluates a univariate function. We call it PBS for programmable bootstrapping. In order to be performed, the PBS uses a so called bootstrapping key, i.e., a list of GGSW encryptions of the elements of the secret key used to encrypt the input LWE (noisy) ciphertext of the PBS. The procedure is composed of three major steps:

• Modulus Switching: the input LWE ciphertext in Z n+1 q is converted into a ciphertext in Z n+1
2N ; • Blind Rotation: a GLWE encryption of a redundant LUT 1 is rotated (by using a loop of CMux operations [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF]) according to the LWE ciphertext produced in the previous step and the public bootstrapping key;

• Sample Extraction: the constant coefficient of the GLWE output of the previous step is extracted as a LWE ciphertext.

Building Blocks

In this section we describe two building blocks: the LWE multiplication, that uses an existing GLWE multiplication together with some key switchings and sample extraction, and a generalized version of TFHE PBS. Both techniques are necessaries in order to build our constructions in the rest of the paper.

LWE Multiplication

We first recall the multiplication algorithm for GLWE ciphertexts in Algorithm 1.

It is composed of a tensor product followed by a relinearization and is widely used in the literature [START_REF] Fan | Somewhat practical fully homomorphic encryption[END_REF] (we recall the GLWE [START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF] algorithm, instead of the more limited RLWE version). Since this algorithm is largely used in the rest of the paper, we thoroughly study its noise growth and provide a formal noise analysis where Var(S) is the variance of a GLWE secret key polynomial S ∈ R q , Var(S even ) (resp. Var(S odd )) is the variance of even (resp. odd) coefficients in S 2 and Var(S ) is the variance of coefficients in S i • S j which is the product between two independent secret key polynomials S i , S j ∈ R q . We provide concrete cryptographic parameters depending on the precision and the multiplicative depth in the Table 3.1.

1 A redundant LUT is a LUT corresponding to a function f , whose entries are redundantly represented inside the coefficients of a polynomial in R q . In practice, the redundancy consists in a r times (with r a system parameter) repetition of the entries f (i) of the LUT with a certain shift:

P f = X -r/2 • N/r-1 i=0 X i•r • r-1 j=0 f (i) • X j .
Theorem 1 (GLWE multiplication) Let CT 1 = GLWE S (PT 1 ) ∈ R k+1 q and CT 2 = GLWE S (PT 2 ) ∈ R k+1 q be two GLWE ciphertexts, encrypting respectively PT 1 = M 1 ∆ 1 ∈ R q and PT 2 = M 2 ∆ 2 ∈ R q , under
the same secret key S = (S 1 , . . . , S k ) ∈ R k q , with noise sampled respectively from χ σ 1 and χ σ 2 . Let

RLK= CT i,j =GLev (B, ) S (S i •S j )∈R ×(k+1) q 1≤j≤i
1≤i≤k be a relinearization key for the GLWE secret key S, with noise sampled from χ σ RLK .

Algorithm 1 computes a new GLWE ciphertext CT encrypting the product PT 1 • PT 2 /∆ ∈ R q where ∆ = min (∆ 1 , ∆ 2 ) (a scaling factor), under the secret key S, with a noise variance Var GLWEMult estimated by the following formula:

Var GLWEMult = N ∆ 2 ∆ 2 1 ||M 1 || 2 ∞ σ 2 2 + ∆ 2 2 ||M 2 || 2 ∞ σ 2 1 + σ 2 1 σ 2 2 + + N ∆ 2 q 2 -1 12 1 + kN Var(S) + kN E 2 (S) + kN 4 Var(S) + 1 4 (1 + kN E(S)) 2 (σ 2 1 + σ 2 2 )+ + 1 12 + kN 12∆ 2 • (∆ 2 -1) • Var(S) + E 2 (S) + 3 • Var(S) + k(k -1)N 24∆ 2 • (∆ 2 -1) • Var(S ) + E 2 (S ) + 3 • Var(S ) + + kN 24∆ 2 • (∆ 2 -1) • Var(S odd ) + Var(S even ) + 2 • E 2 (S mean ) + 3 • Var(S odd ) + Var(S even ) + k N σ 2 RLK • (k + 1) 2 • B 2 + 2 12 + + kN 2 q 2 12B 2 - 1 12 (k -1) • (Var(S ) + E 2 (S mean )) + Var(S odd ) + Var(S even ) + 2E 2 (S mean ) + + kN 8 • (k -1)
• Var(S ) + Var(S odd ) + Var(S even ) .

(1)

Let k * = k(k + 1) 2 and k + = (k + 1)(k + 2) 2
. The complexity of the algorithm is:

C (k, ,n,N ) GLWEMult = C (k,N ) TensorProduct + C (k, ,N ) Relin , with C (k,N ) TensorProduct = 2(k + 1)C FFT + k + C iFFT + (k + 1) 2 N C multFFT + k * N C addFFT , and
C (k, ,N ) Relin = N k * C dec + k * C FFT + k * (k + 1)N C multFFT + (k * -1)(k + 1)N C addFFT + (k + 1)C iFFT (2)
Proof 1 (sketch) In the proof, we compute the decryption of the resulting ciphertext, obtaining the message plus the noise so we can estimate its variance. The detailed computation leading us to the aforementioned noise formula is provided in Supplementary Material C.

Algorithm 1: CT ← GLWEMult (CT 1 , CT 2 , RLK) Context:          S = (S 1 , . . . , S k ) ∈ R k q : a GLWE secret key ∆ = min (∆ 1 , ∆ 2 ) ∈ Zq PT 1 = M 1 ∆ 1 ∈ Rq PT 2 = M 2 ∆ 2 ∈ Rq Input:        CT 1 = GLWE S (PT 1 ) = A 1,1 , • • • , A 1,k , B 1 ∈ R k+1 q CT 2 = GLWE S (PT 2 ) = A 2,1 , • • • , A 2,k , B 2 ∈ R k+1 q RLK = CT i,j = GLev (B, ) S (S i • S j ) 1≤j≤i 1≤i≤k : a relinearization key for S Output: CT = GLWE S PT 1 •PT 2 ∆ ∈ R k+1 q 1 begin /* Tensor product */ 2 for 1 ≤ i ≤ k do 3 T i ← [A1,i•A2,i] Q ∆ q 4 end 5 for 1 ≤ i ≤ k, 1 ≤ j < i do 6 R i,j ← [A1,i•A2,j+A1,j•A2,i] Q ∆ q 7 end 8 for 1 ≤ i ≤ k do 9 A i ← [A1,i•B2+B1•A2,i] Q ∆ q 10 end 11 B ← [B 1 •B 2 ] Q ∆ q /* Relinearization */ 12 CT ← A 1 , • • • , A k , B + k i=1 CT i,i , dec (B, ) T i + 1≤j<i 1≤i≤k CT i,j • dec (B, ) R i,j 13 end
The same Algorithm 1 can be adapted in order to perform a GLWE square: the square is more efficient since R i,j and A i are computed with a single multiplication instead of two. For more details, we refer to Algorithm 9 in the Supplementary Material A.1.

Single LWE Multiplication

We now define Algorithm 2 for homomorphically multiply two LWE ciphertexts. It requires the sample extraction procedure, which is an algorithm adding no noise to the ciphertext and consisting in simply rearranging some of the coefficients of the GLWE input ciphertext to build the output LWE ciphertext encrypting one of the coefficients of the input polynomial plaintext. The sample extraction is described in [CGGI20, Section 4.2] for RLWE inputs, and can be easily extended to GLWE ones. Due to page constraint, this algorithm is described in the Supplementary Material A, Algorithm 14.

Theorem 2 (LWE-to-GLWE Packing Key Switch) We start with the simplest case were we pack a single LWE ciphertext. Let ct in = LWE s (m • ∆) ∈ Z n+1 q be an LWE ciphertext encrypting m • ∆ ∈ Z q , under the LWE secret key s = (s 1 , . . . , s n ) ∈ Z n q , with noise sampled respectively from χ σ . Let S be a GLWE secret key such that

S = (S 1 , . . . , S k ) ∈ R k+1 q . Let KSK = CT i = GLev B, S (s i ) ∈ R ×(k+1)
q 1≤i≤n be a key switching key from s to S with noise sampled from χ σ KSK . There are two different variances after a packing key switch: one for the coefficient we just filled written Var fill and another for the empty coefficients Var emp . Those variances are estimated by:

Var (1) fill = σ 2 + n q 2 12B 2 - 1 12 Var(s i ) + E 2 (s i ) + n 4 Var(s i ) + n σ 2 KSK B 2 + 2 12
Var (1) emp = n σ 2 KSK B 2 + 2 12
(3)

When we pack 1 ≤ α ≤ N LWE ciphertexts, we have Var

(α) fill = Var (1) fill + (α -1) • Var (1)
emp and

Var (α) emp = α • Var (1)
emp The complexity of the algorithm is:

C (α, ,n,k,N ) PackingKS = α nC dec + α n(k + 1)N C mul + ((α n -1)(k + 1)N + α)C add
Proof 2 (sketch) In the proof, we compute the decryption of the resulting ciphertext, obtaining the message plus the noise so we can estimate the two variances. The detailed computation leading us to the aforementioned noise formulas are provided in Supplementary Material D.

Algorithm 2: ct out ← LWEMult (ct 1 , ct 2 , RLK, KSK) Context:                s = (s 1 , • • • , sn) ∈ Z n q : the LWE input secret key s = (s 1 , • • • , s kN ) ∈ Z kN q : the LWE output secret key S = S 1 , . . . , S k ∈ R k q : a GLWE secret key ∀1 ≤ i ≤ k, S i = N -1 j=0 s (i-1)•N +j+1 X j ∈ Rq ∆out = max(∆ 1 , ∆ 2 ) ∈ Zq Input:            ct 1 = LWEs(m 1 • ∆ 1 ) ∈ Z n+1 q ct 2 = LWEs(m 2 • ∆ 2 ) ∈ Z n+1
q RLK : a relinearization key for S as defined in algorithm 1

KSK = CT i = GLev B, S (s i ) 1≤i≤n
: a key switching key from s to S

Output: ctout = LWE s (m 1 • m 2 • ∆out) ∈ Z kN +1 q 1 begin /* KS from LWE to GLWE */ 2 CT 1 = GLWE S (m 1 • ∆ 1 ) ← PackingKS({ct 1 }, {0}, KSK) ; 3 CT 2 = GLWE S (m 2 • ∆ 2 ) ← PackingKS({ct 2 }, {0}, KSK) ; /* GLWE multiplication: Tensor product + Relinearization */ 4 CT = GLWE S (m 1 • m 2 • ∆out) ← GLWEMult(CT 1 , CT 2 , RLK) /* Sample extract the constant term */ 5 ctout = LWE s (m 1 • m 2 • ∆out) ← SampleExtract (CT, 0) 6 end Theorem 3 (LWE Multiplication) Let ct (1) = LWE s (m 1 • ∆ 1 ) and ct (2) = LWE s (m 2 • ∆ 2 ) be two LWE ciphertexts, encrypting respectively m 1 • ∆ 1 and m 2 • ∆ 2 ,
both encrypted under the LWE secret key s = (s 1 , . . . , s n ), with noise sampled respectively from χ σ 1 and χ σ 2 . Let KSK={CT i =GLev B, S (s i )} 1≤i≤n a key switching key from s to S where S = (S 1 , . . . , S k ), with noise sampled from χ σ KSK . Let RLK be a relinearization key for S , defined as in Theorem 1.

Algorithm 2 computes a new LWE ciphertext ct out , encrypting the product m 1 • m 2 • ∆ out , where ∆ out = max(∆ 1 , ∆ 2 ), under the secret key s . The variance of the noise in ct out can be estimated by replacing the variances σ 1 and σ 2 in the RLWE multiplication (Formula 1, Theorem 1) with the variance estimated after a packing key switch (Formula 3, Theorem 2). The complexity is:

C ( KS , RL ,n,k,N ) LWEMult = 2 • C (1, KS ,n,k,N ) PackingKS + C (k, RL ,n,N ) GLWEMult + C (N ) SampleExtract

Packed Products & Packed Sum of Products

It is possible to use algorithm 2 to compute with a single multiplication several products, or several squares, or a sum of several products, or even a sum of several squares.

These four functionalities can be easily achieved by slightly modifying Algorithm 2. In the case of PackedMult and PackedSumProducts, the algorithm take in input two sets of LWE ciphertexts ct (1)

i = LWEs(m (1) i •∆ 1 ) 0≤i<α and ct (2) i = LWEs(m (2) i •∆ 2 ) 0≤i<α : 1. PackedMult: the goal is to compute LWE encryptions of the products m (1) i • m (2) i • ∆ out , where ∆ out = max(∆ 1 , ∆ 2 ).
The two input sets are packed with a packing key switch into two GLWE ciphertexts with indexes

ℒ 1 = {0, 1, 2, • • • , α -1} and ℒ 2 = {0, α, 2α, • • • , (α -1)
α} respectively. The resulting GLWE ciphertexts are multiplied with the GLWE multiplication (Algorithm 1) and finally all the coefficients at indexes i • (α + 1) (for 0 ≤ i < α) are extracted.

2. PackedSumProducts: the goal is to compute a LWE encryption of the sum of products α-1 i=0 m

(1)

i •m (2) i •∆out, where ∆ out = max(∆ 1 , ∆ 2 ).
The two input sets are packed with a packing key switch into two GLWE ciphertexts with indexes

ℒ 1 = {0, 1, 2, • • • , α -1} and ℒ 2 = {α -1, α -2, α -3, • • • , 0} respectively.
The resulting GLWE ciphertexts are multiplied with the GLWE multiplication (Algorithm 1) and finally the coefficient at index α -1 is extracted.

Note that it is possible to compute packed squares and a packed sum of squares if the two LWE input sets are equal. It is also possible to compute squares and a sum of squares by computing a RLWE multiplication between an RLWE ciphertext and itself. In that case, a single set of LWE input in provided

{ct i } = {LWE s (m i • ∆)} 0≤i<α :
1. PackedSquares: the goal is to compute LWE encryptions of the squares m 2 i • ∆. The input set is packed with a packing key switch into a GLWE ciphertext with indexes

ℒ = {2 0 -1, 2 1 -1, 2 2 -1, • • • , 2 α-1 -1}.
The resulting GLWE ciphertext is squared by using the GLWE square algorithm and finally all the coefficients at indexes 2 i+1 -2 (for 0 ≤ i < α) are extracted.

PackedSumSquares: the goal is to compute a LWE encryption of the sum of squares

α-1 i=0 m 2 i •2∆.
To achieve this goal, the input set is packed with a packing key switch into a GLWE ciphertext with redundancy, using two indexes sets

ℒ 1 = {0, 1, 2, • • • , α -1} and ℒ 2 = {2α -1, 2α -2, 2α -3, • • • , α}.
The resulting GLWE ciphertext is squared by using the GLWE square algorithm and finally the coefficient at index 2α -1 is extracted.

Note that we could also compute packed products and a packed sum of products with a GLWE square algorithm by changing ℒ, ℒ 1 and ℒ 2 and also extracting different coefficients. Also note that for these four algorithms, there are restrictions regarding the maximum value that α can take each time. We provide more details in the Supplementary Material A.2.

Generalized PBS

We propose a more versatile algorithm for the PBS where we are able to bootstrap a precise chunk of bits, instead of only the MSB as described in TFHE, and to also apply several function evaluations at once. We describe this generalization in Algorithm 3. We introduce two new parameters, κ and ϑ, which redefine the modulus switching step of TFHE PBS. In particular, κ defines the number of MSB that are not considered in the PBS, while 2 ϑ defines the number of functions that can be evaluated at the same time in a single generalized PBS.

The two parameters κ and ϑ are illustrated in Figure 2, where "input" represents the plaintext (with noise) that is encrypted the input ciphertext of the modulus switching, and "output" illustrates the plaintext (with noise) that is encrypted inside the output ciphertext (after modulus switching). The first κ MSB will not impact the following steps of the generalized PBS and ϑ bits will be set to 0 in order to encode 2 ϑ functions in the LUT stored in P f (see Section 4.3 for more details). Observe that the case (κ, ϑ) = (0, 0) corresponds to the original TFHE PBS. We also define the "plaintext modulus switching" function written PTModSwitch to recover the plaintext of the encrypted output of a mod-ulus switching algorithm. Let m ∈ Z q be a message, ∆ ∈ Z q its scaling factor, κ ∈ Z and ϑ ∈ N the parameters of a modulus switching. We define q = q ∆2 κ . The case where κ ≥ 0 is illustrated in Figure 3. We defined (β, m ) ← PTModSwitch q (m, ∆, κ, ϑ) ∈ {0, 1} × N as follow: Note that for simplicity purpose, we provide the generalized PBS noise formula only for binary secret keys. However, in Supplementary Material B we provide formulas as well as proofs for more key distributions (binary, ternary and Gaussian).

If κ ≥ 0 : m = m mod q 2 if m mod q < q 2 , β = 0, else β = 1 Else : m = m β is a random bit Output: m β m 2N ϑ
Theorem 4 (Generalized PBS) Let s = (s 1 , • • • , s n ) ∈ Z n
q be a binary LWE secret key. Let S = (S 1 , . . . , S k ) ∈ R k q be a GLWE binary secret key such that

S i = N -1 j=0 s (i-1)•N +j+1 •X j
, and s = (s 1 , • • • , s kN ) be the corresponding binary LWE secret key. Let P f be a r-redundant LUT for a function f : Z → Z and ∆ out be the output scaling factor. Let (κ, ϑ) be the two integer variables defining (along with N ) the window size to be modulus switched, such that q2 ϑ ∆ in 2 κ < 2N , and let

(β, m ) = PTModSwitch q (m, ∆ in , κ, ϑ) ∈ {0, 1} × N. Then Algorithm 3 takes as input a LWE ciphertext ct in = LWE s (m • ∆ in ) ∈ Z n+1 q with noise distribution from χ σ in , a bootstrapping key BSK= CT i =GGSW B, S (s i ) n i=1
from s to S and a (possibly trivial) GLWE encryption of P f • ∆ out , and returns an LWE ciphertext ct out under the secret key s , encrypting the message

(-1) β • f (m ) • ∆ out if and only if the input noise has variance σ 2 in < ∆ 2 in 4Γ 2 -q 2 12w 2 + 1 12 -nq 2 24w 2 -n 48
, where Γ is a variable depending on the probability of correctness defined as

P =erf Γ √ 2 , w = 2N •2 -ϑ and q = q • 2 -κ .
The output noise after the generalized PBS is estimated by the formula:

Var(PBS) = n (k+1)N B 2 + 2 12 Var(BSK)+n q 2 -B 2 24B 2 1 + kN 2 + nkN 32 + n 16 1 - kN 2 2 .
The complexity of Algorithm 3 is the same as the complexity of TFHE bootstrapping [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF], i.e.,

C (n, ,k,N ) GenPBS = C (n) ModulusSwitching + nC (n, ,k,N ) CMUX C (N ) SampleExtract with          C (n) ModulusSwitching = (n + 1)C Scale&Round C (n, ,k,N ) CMUX = (k + 1)(n + 1)C (N ) Rotation + 2n(k + 1)N C Add + C (n, ,k,N ) ExternalProduct C (n, ,k,N ) ExternalProduct = n (k + 1)N C dec + n (k + 1)C FFT + n(k + 1) (k + 1)N C multFFT + +n(k + 1)( (k + 1) -1)N C addFFT + n(k + 1)C iFFT Proof 3 (sketch)
In the proof, we compute the decryption of the resulting ciphertext, obtaining the message plus the noise so we can estimate its variance. The detailed proof of this theorem is provided in Supplementary Material B.

Algorithm 3: ct out ← GenPBS (ct in , BSK, CT f , κ, ϑ) Context:                              s = (s 1 , • • • , sn) ∈ Z n q : the LWE input secret key s = (s 1 , • • • , s kN ) ∈ Z kN q : the LWE output secret key S = S 1 , . . . , S k ∈ R k q : a GLWE secret key ∀1 ≤ i ≤ k, S i = N -1 j=0 s (i-1)•N +j+1 X j ∈ Rq P f ∈ Rq : a r -redundant LUT for x → f (x) ∆out ∈ Zq : the output scaling factor f : Z → Z : a function (β, m ) = PTModSwitchq(m, ∆ in , κ, ϑ) ∈ {0, 1} × N Input:            ct in = LWEs(m • ∆ in ) = (a 1 , • • • , an, a n+1 = b) ∈ Z n+1 q BSK = CT i = GGSW B, S (s i ) n i=1
: a bootstrapping key from s to S

CT f = GLWE S P f • ∆out ∈ R k+1 q (κ, ϑ) ∈ Z × N : define along with N the chunk of the plaintext to bootstrap Output: ctout = LWE s (-1) β • f (m ) • ∆out if we respect requirements in Theorem 4 1 begin /* modulus switching */ 2 for 1 ≤ i ≤ n + 1 do 3 a i ← a i •2N •2 κ-ϑ q • 2 ϑ 2N 4 end /* blind rotate of the LUT */ 5 CT ← BlindRotate CT f , {a i } n+1 i=1 , BSK ; /* sample extract the constant term */ 6 ctout ← SampleExtract (CT, 0) 7 end

Upgraded Bootstrapping

This section describes our main contributions, i.e., the WoP-PBS (PBS without a bit of padding) and the PBS evaluating multiple look-up tables at the same time (we call this algorithm PBSmanyLUT).

WoP-PBS first version

A big constraint with TFHE PBS is the negacyclicity of the rotation of the LUT. It implies a need of a padding bit (as mentioned in Limitation A). We propose a solution to remove that requirement, by using the aforementioned LWE multiplication (Algorithm 1) and the generalized PBS (Algorithm 3). This new bootstrapping is called the programmable bootstrapping without padding (WoP-PBS) and a first version is described in Algorithm 4.

Algorithm 4: ct out ← WoP-PBS 1 (ct in , BSK, RLK, KSK, P f , ∆ out , κ, ϑ) Context:                                  s = (s 1 , • • • , sn) ∈ Z n q s = (s 1 , • • • , s kN ) ∈ Z kN q S = S (1) , . . . , S (k) ∈ R k q ∀1 ≤ i ≤ k, S (i) = N -1 j=0 s (i-1)•N +j+1 X j ∈ Rq f : Z → Z : a function P 1 ∈ Rq : a redundant LUT for x → 1 (β, m ) = PTModSwitchq(m, ∆, κ, ϑ) ∈ {0, 1} × N CT f = GLWE S P f • ∆out ∈ R k+1 q (might be a trivial encryption) CT 1 ∈ R k+1 q : a trivial encryption of P 1 • ∆out Input:                              ct in = LWEs(m • ∆ in ) = (a 1 , • • • , an, a n+1 = b) ∈ Z n+1 q BSK = BSK i = GGSW (B, ) S (s i ) 1≤i≤n : a bootstrapping key from s to S RLK = CT i,j = GLev (B, ) S S i • S j 1≤j≤i 1≤i≤k : a relinearization key for S KSK = CT i = GLev (B, ) S s i 1≤i≤kN
: a key switching key from s to S

P f ∈ R : a redundant LUT for x → f (x) ∆out ∈ Zq : the output scaling factor (κ, ϑ) ∈ Z × N : define along with N the window size Output: ctout = LWE s (f (m ) • ∆out) if we respect requirements in Theorem 5 1 begin /* Compute two PBS in parallel: */ 2 ct f = LWE s ((-1) β • f (m ) • ∆out) ← GenPBS ct in , BSK, CT f , κ -1, ϑ ; 3 ct Sign = LWE s ((-1) β • ∆out) ← GenPBS (ct in , BSK, CT 1 , κ -1, ϑ) ; /* Compute the multiplication */ 4 ctout ← LWEMult(ct f , ct Sign , RLK, KSK); 5 end Theorem 5 (PBS Without Padding (V1)) Let s = (s 1 , • • • , s n ) ∈ Z n
q be a binary LWE secret key. Let S = (S 1 , . . . , S k ) ∈ R k q be a GLWE secret key such that

S i = N -1 j=0 s (i-1)•N +j+1 X j ∈Rq, and s = (s 1 , • • • , s kN ) ∈ Z kN q
be the corresponding binary LWE key. Let P f ∈ R q (resp. P 1 ∈ R q ) be a r-redundant LUT for the function f : Z → Z, (resp. the constant function x → 1) and ∆ out ∈ Z q be the output scaling factor. Let CT f be a (possibly trivial) GLWE encryption of P f • ∆ out and CT 1 be a trivial GLWE encryption of P 1 • ∆ out . Let (κ, ϑ) ∈ Z × N be the two integer variables defining (along with N ) the chunk of the plaintext that is going to be bootstrapped, such that q2 ϑ ∆ in 2 κ <2N , and let

(β, m ) = PTModSwitch q (m, ∆ in , κ, ϑ) ∈ {0, 1} × N. Let KSK= CT i =GLev (B, ) S (s i )
1≤i≤n be a key switching key from s to S , with noise sampled respectively from χ σ (1) and χ σ (2) . Let RLK= CT i,j =GLev (B, ) S (S i •S j ) 1≤j≤i 1≤i≤k be a relinearization key for S , defined as in Theorem 1. Let BSK= CT i =GGSW B, S (s i ) n i=1 be a bootstrapping key from s to S .

Then the Algorithm 4 takes in input a LWE ciphertext

ct in = LWE s (m • ∆ in ) ∈ Z n+1 q
where ct in = (a 1 , • • • , a n , a n+1 = b), with noise sampled from χ σ in , and returns an LWE ciphertext ct out ∈ Z kN +1 q under the secret key s encrypting the messages f (m ) • ∆ out if and only if the input noise has variance verifying Theorem 3.

The output ciphertext noise variance verifies Var(WoP-PBS 1 ) = Var(LWEMult) with input variances for the LWE multiplication (Algorithm 2) defined as σ i = Var(GenPBS), for i ∈ {1, 2}.

The complexity of Algorithm 4 is:

C (n, PBS ,k 1 ,N 1 , KS , RL ,k 2 ,N 2 ) WoP-PBS 1 = 2C (n, PBS ,k 1 ,N 1 ) GenPBS + C ( KS , RL ,N 1 ,k 2 ,N 2 ) LWEMult
Proof 4 (Sketch) We only provide a proof of correctness of the algorithm, considering that the noise and the complexity are directly deduced from the GenPBS and LWEMult algorithms. Both of the GenPBS are applied with the same parameters except for the evaluated function (P f or P 1 ). Thus, in both ciphertexts ct f and ct Sign the value of β is the same. Then,

ct out = LWE s ((-1) 2β • f (m ) • ∆ out ) = LWE s (f (m ) • ∆ out ).
Remark 2 Observe that, in Algorithm 4 we set KSK as a key switching key for s to S where s is the LWE secret key composed of the coefficients in S . In practice, the key switching can be done to a key S , that has nothing to do with s . In this case, the RLK should be adapted as well to the key S .

It shall be noticed that in Algorithm 4:

• The two GenPBS have the same input ciphertext. To make the evaluation more efficient (evaluating a single bootstrapping instead of two), it is possible to use either the multi-value bootstrap described in [START_REF] Carpov | New techniques for multi-value input homomorphic evaluation and applications[END_REF], which will be faster but at the cost of a higher output noise. Another option would be to take advantage of the PBSmanyLUT, that we describe in detail in Algorithm 6 if the input message is small enough (cf. Remark 3).

• There could be only one key switching done in LWEMult (instead of two) if one of the two inputs is provided as a GLWE ciphertext (one GenPBS does not perform the final sample extraction).

• The LWEMult on line 4 can be replaced by a LWESquare (which corresponds to a PackedSquares with α = 2, Algorithm 12) which is faster.

These improvements could increase the noise but improve the complexity of the algorithm.

WoP-PBS second version

Another big constraint with TFHE PBS is that the polynomial size is directly linked to the size of the message we want to bootstrap (as mentioned in Limitation B). The smallest growth of the polynomial size slows down the computation by more than a factor 2 as TFHE PBS complexity is proportional to the FFT complexity: N log 2 (N ) with N the polynomial size. Keeping that in mind, we offer a different way to perform a bootstrap without padding in Algorithm 5 which can be more efficient in a multi-threaded machine. The main idea behind this Algorithm is to write a message m as β||m with β the most significant bit and m the rest of the message. The function f to be computed is broken into two functions: f 0 and f 1 . We want f 0 if β is equal to 0 and f 1 if β = 1. We use β as an encrypted decision bit, so we can choose between f 0 (m ) or f 1 (m ) thanks to the LWEMult algorithm. We give the complete set of cryptographic parameters for different precisions in Table 2. In a nutshell, for precisions from 1 to 5 bits, we use log 2 (N ) = 11 and for 6 and 7 bits of precisions, we use log 2 (N ) = 12.

Theorem 6 (PBS Without Padding (V2)) Let f 0 and f 1 be the two functions representing f such that f 0 (x) = f (x) = f 1 (x -p) for a certain p ∈ N. Then, under the same hypothesis of Theorem 5, the Algorithm 5 takes in input a LWE ciphertext

ct in = LWE s (m • ∆ in ) = (a 1 , • • • , a n , a n+1 = b)
, with noise from χ σ in , and returns in output a LWE ciphertext ct out under the secret key s encrypting the messages f (m ) • ∆ out if and only if the input noise has variance verifying the Theorem 3.

The output ciphertext noise variance verifies Var(WoP-PBS 2 ) = 2 • Var(LWEMult) with input variances for the LWEMult defined as σ i = Var(GenPBS), for i ∈ {1, 2}.

The complexity of Algorithm 4 is:

C (n, PBS ,k 1 ,N 1 , KS , RL ,k 2 ,N 2 ) WoP-PBS 2 = 3C (n, PBS ,k 1 ,N 1 ) GenPBS + 2C ( KS , RL ,N 1 ,k 2 ,N 2 ) LWEMult + (N 2 + 3)C add Proof 5 (Sketch) We have ct β 0 = LWE s ( ∆ out 2 ((-1) β + 1)). If β = 0, then ct β 0 = LWE s (∆ out ) else ct β 0 = LWE s (0). Then, ct β 0 = LWE s ((1 -β)∆ out ). Similarly, we obtain ct β 1 = LWE s ((-β)∆ out ). The output ciphertext ct out is then equal to LWE s (((-1) β (1 -β)∆ out f 0 (m ) + (-1) β (-β)∆ out f 1 (m ). Thus, if β = 0, ct out = f 0 (m ) else ct out = f 1 (m ), as expected.
It shall be noticed that in Algorithm 5:

Algorithm 5: ct out ← WoP-PBS 2 (ct in , BSK, RLK, KSK, P f , ∆ out , κ, ϑ) Context:                                      s = (s 1 , • • • , sn) ∈ Z n q s = (s 1 , • • • , s kN ) ∈ Z kN q S = S (1) , . . . , S (k) ∈ R k q ∀1 ≤ i ≤ k, S (i) = N -1 j=0 s (i-1)•N +j+1 X j ∈ Rq f 0 (x) = f (x) = f 1 (x -p) for a certain p (β, m ) = PTModSwitchq(m, ∆, κ, ϑ) ∈ {0, 1} × N P 1 ∈ Rq : as defined in Algorithm 4 CT f i = GLWE S P f i • ∆out ∈ R k+1 q (might be a trivial encryption) CT 1 ∈ R k+1 q : a trivial encryption of P 1 • ∆out 2 P f 0 , P f 1 ∈ Rq : redundant LUTs of the two halves of P f Input:              ct in = LWEs(m • ∆ in ) = (a 1 , • • • , an, a n+1 = b) ∈ Z n+1 q
BSK, KSK, RLK : as defined in Algorithm 4 P f ∈ Rq : a redundant LUT for x → f (x) ∆out ∈ Zq : the output scaling factor (κ, ϑ) ∈ Z × N : define along with N the window size

Output: ctout = LWE s (f (m ) • ∆out) if we respect requirements in Theorem 6 1 begin /* Compute in parallel 3 PBS: */ 2 ct f 0 = LWE s ((-1) β • ∆out • f 0 (m )) ← GenPBS(ct in , BSK, CT f 0 , κ, ϑ) ; 3 ct f 1 = LWE s ((-1) β • ∆out • f 1 (m )) ← GenPBS(ct in , BSK, CT f 1 , κ, ϑ) ; 4 ct Sign = LWE s ((-1) β • ∆out 2 ) ← GenPBS(ct in , BSK, CT 1 , κ, ϑ) ; /* Compute two sums in parallel: */ 5 ct β 0 = LWE s ((1 -β) • ∆out) ← ct Sign + (0, ∆out 2 ) ; 6 ct β 1 = LWE s (-β • ∆out) ← ct Sign -(0, ∆out 2 ) ; /* Compute two multiplications in parallel: */ 7 ct β•f 0 ← LWEMult(ct f 0 , ct β 0 , RLK, KSK) ; 8 ct β•f 1 ← LWEMult(ct f 1 , ct β 1 , RLK, KSK) ;
/* Add the previous results: */

9 ctout ← ct β•f 0 + ct β•f 1 ; 10 end
• The three GenPBS have the same input ciphertext. As we observed for Algorithm 4, to make the evaluation more efficient by evaluating a single bootstrapping instead of three, it is possible to use either the multi-value bootstrap described in [START_REF] Carpov | New techniques for multi-value input homomorphic evaluation and applications[END_REF] or to take advantage of the PBSmanyLUT (Algorithm 6 and cf. Remark 3).

• We could remove two key switches (among four) as explained for the WoP-PBS 1 .

• To improve both performance and noise, in practice, we can do a lazy relinearization as described in [LLK + 20], i.e., the step of relinearization of the two LWEMult will be done after the final addition.

• The two LWEMult followed by the final addition can be replaced by a PackedSumProducts (Algorithm 11 described in detail in Supplementary Material A.2).

These improvements could increase the noise but also improve the complexity of the algorithm.

A multi-output PBS

We are able to extract any chunk of the encrypted plaintext with ϑ, κ and N . When possible, one can define a smaller chunk for the plaintext by trimming the bound in the LSB using a ϑ > 0. It means that after the modulus switching there are ϑ LSB set to 0. More formally, after the modulus switching, a plaintext m * will be of the form

m * = m • ∆ + e • 2 ϑ ∈ Z q .
Thank to the ϑ LSB set to 0 in the plaintext, one can evaluate 2 ϑ functions at the cost of only one GenPBS without increasing the noise compared to a regular TFHE PBS. The procedure is described in Algorithm 6.

Algorithm 6: ct 1 , . . . , ct 2 ϑ ← PBSmanyLUT(ct in , BSK, P (f1,...f 2 ϑ ) , ∆ out , κ, ϑ) Context:                          s = (s 1 , . . . , sn) ∈ Z n q s = (s 1 , . . . , s kN ) ∈ Z kN q S = S (1) , . . . , S (k) ∈ R k q ∀1 ≤ i ≤ k, S (i) = N -1 j=0 s (i-1)•N +j+1 X j ∈ Rq f 1 , . . . , f 2 ϑ : Z → Z (β, m ) = PTModSwitchq(m, ∆, κ, ϑ) ∈ {0, 1} × N CT (f 1 ,...,f 2 ϑ ) = GLWE S P (f 1 ,...,f 2 ϑ ) • ∆out (might be a trivial encryption) Input:            ct in = LWEs(m • ∆ in ) = (a 1 , • • • , an, a n+1 = b) ∈ Z n+1 q BSK = BSK i = GGSW (B, ) S (s i ) 1≤i≤n P (f 1 ,...,f 2 ϑ ) : a redundant LUT for : x → f 1 (x)|| . . . ||f 2 ϑ (x) (κ, ϑ) ∈ Z × N : define along with N the window size Output: ct 1 , . . . , ct 2 ϑ such that ct j = LWE s (-1) β • f j (m ) • ∆out 1 begin /* modulus switching */ 2 for 1 ≤ i ≤ n + 1 do 3 a i ← a i •2N •2 κ-ϑ q • 2 ϑ 2N 4 end /* blind rotate of the LUT */ 5 CT ← BlindRotate CT (f 1 ,••• ,f 2 ϑ ) , {a i } 1≤i≤n+1 , BSK ;
/* sample extract the first 2 ϑ terms (coeffs. from 0 to 2 ϑ -1)

*/ 6 for 1 ≤ j ≤ 2 ϑ do 7 ct j ← SampleExtract j-1 (CT) 8 end 9 end
The form of the LUT polynomial is set accordingly to the ϑ parameter so that it contains up to 2 ϑ functions. As for TFHE bootstrapping, one needs to have redundancy in the LUT to remove the input noise. Each block of functions (i.e., the sequence of f i , i ∈ [1, 2 ϑ ] coefficients) is repeated all along the polynomial. The LUT can be build as follow:

P (f 1 ,...,f 2 ϑ ) = X N 2p p-1 j=0 X j N p N p2 ϑ -1 k=0 X k•2 ϑ 2 ϑ -1 i=0 f i+1 (j)X i , with p = q ∆ in • 2 κ+1
By doing so, one can sample extract at the end 2 ϑ coefficients which leads to 2 ϑ output ciphertexts, one for each evaluated functions. By neglecting the computational cost of the ϑ sample extractions, the complexity is the same than for a PBS evaluating only one function. The noise is also not impacted.

This method is particularly efficient when the polynomial size is constrained by the desired output noise. If the polynomial size is chosen large enough, there will be bits set to zero between the modulus switching noise and the message. This new method allows to exploit these bits to compute different functions on the same input ciphertext.

Theorem 7 (Multi-output PBS) Let s = (s 1 , • • • , s n ) ∈ Z n
q be a binary LWE secret key. Let S = (S 1 , . . . , S k ) ∈ R k q be a GLWE secret key such that

S i = N -1 j=0 s (i-1)•N +j+1 X j ∈Rq, and s = (s 1 , • • • , s kN ) ∈ Z kN q
be the corresponding LWE key. Let P (f 1 ,...f 2 ϑ ) ∈ R q be a r-redundant LUT for the functions x → f 1 (x)|| . . . ||f 2 ϑ (x) and ∆ out ∈ Z q be the output scaling factor. Let (κ, ϑ) ∈ Z × N be the two integer variables defining (along with N ) the window size to be modulus switched, such that q2 ϑ ∆ in 2 κ <2N , and let (β, m ) = PTModSwitch q (m, ∆ in , κ, ϑ).

Then, the Algorithm 6 takes in input a LWE ciphertext

ct in = LWE s (m • ∆ in ) = (a 1 , • • • , a n , a n+1 = b), with noise distribution from χ σ in , a bootstrapping key BSK= CT i =GGSW B, S (s i ) n i=1
from s to S and a (trivial) GLWE encryption of P f • ∆ out , and returns in output 2 ϑ LWE ciphertexts {ct j } j∈[0,2 ϑ ] under the secret key s encrypting the messages (-1) β •f j (m )•∆ out if and only if the input noise has variance verifying the Theorem 3.

The complexity of the algorithm is:

C (n, ,k,N,ϑ) PBSmanyLUT = C (n, ,k,N ) GenPBS + 2 ϑ C (N ) SampleExtract
Proof 6 The proof is the mainly the same as the one from the GenPBS (provided in Supplementary Material B). Let p = q ∆ in •2 κ+1 be the number of possible values for each

f i , i ∈ [0, 2 ϑ ]. Let m ∈ [0, p -1] be a plaintext value. The polynomial P (f 0 ,••• ,f 2 ϑ ) encodes the following LUT:   ..., f 1 (m), ..., f 2 ϑ (m), ..., f 1 (m), ..., f 2 ϑ (m) N/p elements , f 1 (m + 1), ..., f 2 ϑ (m + 1), ..., f 1 (m + 1), ..., f 2 ϑ (m + 1) N/p elements , ...    p blocks
From the GenPBS, ϑ bits are set to 0. Then, by construction of the LUT,

LUT (f 0 ,••• ,f 2 ϑ ) [m * + i] = f i+1 (m ) for i ∈ [0, 2 ϑ -1]
, so that sample extracting gives the expected result.

Remark 3 Observe that PBSmanyLUT and WoP-PBS algorithms can be combined in two different ways:

1. Using PBSmanyLUT to improve WoP-PBS: In WoP-PBS 1 , the ct Sign and each ct f i resulting from distinct GenPBS can be evaluated at once by using a single PBSmanyLUT. Similarly, in WoP-PBS 2 , ct Sign and each ct f 0,i and ct f 1,i could be evaluated at once. In both cases, this variant can be applied only if the polynomial size chosen for the WoP-PBS is large enough to allow multiple LUT evaluations (i.e, if precision is not yet a bottleneck condition): this variant of the WoP-PBS will improve the complexity of the algorithm, without impacting the noise growth.

2. Using WoP-PBS to improve PBSmanyLUT: The PBSmanyLUT algorithm implicitly performs a GenPBS with a special modulus switching. This GenPBS can actually be replaced by a WoP-PBS (with the same special modulus switching) as a WoP-PBS performs the same operation as GenPBS, without the bit of padding constraint. This technique is what we call WoPBSmanyLUT.

Remark 4 A technique to evaluate many LUTs at the same time by performing a single TFHE bootstrapping (plus a bunch of polynomial multiplications per LUT) has been already proposed in [START_REF] Carpov | New techniques for multi-value input homomorphic evaluation and applications[END_REF] and used in [START_REF] Guimarães | Revisiting the functional bootstrap in TFHE[END_REF]. Their technique does not impose a strong constraint on the polynomial size used for the bootstrapping, however it results in a larger output noise, that strictly depends on the function that is evaluated. If the noise constraints at the output of the bootstrapping are a problem, the technique of [START_REF] Carpov | New techniques for multi-value input homomorphic evaluation and applications[END_REF] will require to increase the polynomial size.

Our new PBSmanyLUT is a better alternative to this technique in some situations as the output noise will be independent of the function evaluated. But this comes at the cost of having enough space for the evaluation of the different LUTs (i.e., ϑ bits on the modulus switching to evaluate 2 ϑ functions so a large enough polynomial size N must be chosen). If we already are working with large enough polynomials, there is no computation overhead nor noise growth when replacing a GenPBS by a PBSmanyLUT.

Applications

In this section we present some of the applications that take advantage from our new techniques. In particular, we show that:

• Using a combination of LWEMult and GenPBS improves the gate bootstrapping technique of TFHE [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF], because it allows to perform leveled binary operations between bootstrappings (instead of bootstrapping every single gate).

• The improved gate bootstrapping technique can be extended in order to evaluate arithmetic circuits with larger precision, by using a combination of LWEMult and WoP-PBS (or its variants).

• Using the PBSmanyLUT technique allows to improve the Circuit Bootstrapping of TFHE by a factor , without affecting the noise growth.

• The WoP-PBS technique (and its variants) can be used to bootstrap on larger precision inputs.

Fast Arithmetic

We start by describing an improvement of FHE Boolean circuit evaluation. Then, we extend it to arithmetic circuits dealing with integers encoded in more than a single bit. Finally, we describe how to use the later to build exact computation on bigger encrypted integers.

Fast Boolean Arithmetic

In TFHE [START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF], authors improve techniques proposed in FHEW [START_REF] Ducas | FHEW: bootstrapping homomorphic encryption in less than a second[END_REF] to perform fast homomorphic evaluation of Boolean circuits and called this feature gate bootstrapping. It is very easy to use, because it performs one bootstrapping for each bivariate Boolean gate evaluated: there is no need to be careful with the noise management anymore because each gate reset the noise systematically. This also makes the conversion between the cleartext Boolean circuits and the encrypted circuits quite straightforward in practice. However, performing a bootstrapping at each bivariate Boolean gate is very expensive when we want to evaluate large circuits and seem unnecessary. One idea to make the evaluation more efficient would be to mix the bootstrapping with some leveled operations, at the cost of loosing the ease of not caring about noise growth. But this idea cannot be immediately applied when it comes to gate bootstrapping: in fact, the bootstrapping also takes care of ensuring a fixed encoding in the ciphertexts, that may not be ensured if we introduce leveled operations. Furthermore, TFHE can only evaluate linear combinations between LWE ciphertexts; non linear operations would require the use of bootstrapping or of a non native product between LWE ciphertexts (e.g., an external product which is not composable because it makes use of different input ciphertext types). This is especially problematic when we want to evaluate an AND gate, for instance.

To be more clear, in gate bootstrapping, messages are encoded with what we call one "bit of padding": meaning that we know that the MSB of the plaintext (without noise) is set to zero. This bit is used to perform a linear combination while preserving the (plaintext) MSB of this combination so we can bootstrap it (the function is negacyclic, so do not need an additional bit of padding) and get a correct result. Roughly speaking, the initial linear combination evaluates the linear part of the gate and consumes the bit of padding, while the bootstrapping takes care of the evaluation of the non-linear part of the gate, reduces the noise and brings the bit of padding back to be able to perform a future operation.

We propose a novel approach based on the GenPBS and LWEMult which removes both the constraint of padding bits and the difficulties with the non-linear leveled evaluations. Thus, this offers the possibility of computing series of Boolean gates without the need of computing a bootstrap for every gate. A GenPBS should only be computed to reduce the noise when needed. In Lemma 1, we only describe some of the most common Boolean gates (i.e., XOR, NOT and AND), whose combination offers functional completeness. The other gates can be obtained by combining these operations.

Lemma 1 Let b i ∈ {0, 1} such that ct i = LWE s (b i • q 2 ) ∈ Z n+1 q
, for i ∈ {1, 2}. Let 0, q 2 ∈ Z n+1 q be a trivial LWE ciphertext. Then, the following equalities between Boolean gates and homormorphic operators hold:

ct 1 XOR ct 2 = ct 1 + ct 2 ct 1 AND ct 2 = LWEMult(ct 1 , ct 2 , RLK, KSK) NOT ct 1 = ct 1 + 0, q 2
Proof 7 (Sketch) A bit is naturally encoded as a 0 (resp. q 2 ) if its value is 0 (resp. 1). Then the Boolean gates XOR and NOT stem from that encoding. The AND is a direct application of the LWEMult.

The noise increases after each computed gate since no bootstrap is performed. Then, after chaining many of them, a noise reduction might be required. We propose two simple processes exploiting the GenPBS with the (negacyclic) sign function.

Lemma 2 Let ct in be a LWE ciphertext resulting from a Boolean circuit with gates defined as in Lemma 1. Then, each of the following operators allows to bootstrap the ciphertext during the Boolean circuit evaluation:

ct out ← GenPBS(ct in , BSK, P 1 • X N/2 , ∆ out = q 4 , κ = 0, ϑ = 0) + 0, q 4 (4) ct out ← GenPBS(ct in , BSK, P f = 3N 4 -1 i= N 4 X i , ∆ out = q 2 , κ = -1, ϑ = 0) (5)
Proof 8 The first method 4 uses GenPBS with the parameters ∆ out = q 4 , κ = 0, ϑ = 0 and P f = P 1 * X N/2 . The output of the GenPBS gives ct tmp = LWE s (± q 4 ).

Then, depending on the sign, the term ct tmp + (0,

q 4 ) is equal to LWE s (0) or ct tmp = LWE s ( q 2
). The second approach 5 uses other parameters for the modulus switching which can be seen as shifted of one bit, i.e., κ = -1, ϑ = 0 and ∆ out = q 2 . In this case, the sign does not impact the value of the encoded bit, since ±0 = 0 and ± q 2 = q 2 .

Then, evaluating GenPBS with the function

P f = 3N 4 -1 i= N 4 X i and ∆ out = q 2
, we obtain

ct out = LWE s (±0) or LWE s (± q 2 ).

Modular Power of 2 Arithmetic

We generalize the faster Boolean circuit method (described in Lemma 1) to any power of two modular integer circuits. This enables a more efficient exact arithmetic modulo 2 p for some integer p. For i ∈ {1, 2}, let ct i = LWE s (m i • q 2 p ) be a LWE ciphertext encrypting the message m i ∈ 0, 2 p (i.e., m i has a precision of p bits). As in the case of faster Boolean arithmetic, we define three natural homomorphic operators to mimic modular 2 p arithmetic: the addition (Add 2 p ) that is evaluated as an homomorphic LWE addition, the multiplication (Mul 2 p ) that is evaluated as a LWEMult, and the unary opposite (Opp 2 p ) that is obtained by simply negating the LWE input.

When we deal with integers encoded with more than one bit, functions we have to apply during a PBS are no longer negacyclic. It means that without a WoP-PBS we would have to have at least 2 bits of padding (one for a linear combination and another one for the PBS with non-negacyclic function evaluation). This results in a big N when we want to work with larger powers of two. With a WoP-PBS, we do not need to have bits of padding. Then, we can simply compute leveled additions and multiplications, and only use a WoP-PBS when we have to reset the noise to a lower level.

From Power of 2 Modular Arithmetic to Exact Integer Arithmetic

We now present some operators allowing to extend homomorphic computation modulo a power of two modular to bigger integer arithmetic. To do so, we will use a few LWE ciphertexts to represent a single big integer. These required operations offer the possibility to compute an exact integer multiplication between two LWE ciphertexts as in 5.1.2 and keeping the LSB of the computation. However, we also need to be able to recover the MSB of additions and multiplications for carry propgation when we deal with big integers encrypted with several ciphertexts. The operators keeping the MSB of the computation between two messages m 1 , m 2 ∈ 0, 2 p are defined as:

Add MSB 2 p : (m 1 , m 2 ) → m 1 + m 2 2 p mod 2 p and Mul MSB 2 p : (m 1 , m 2 ) → m 1 • m 2 2 p mod 2 p
and their implementation is described in Algorithm 7. Their homomorphic implementations are defined into the Algorithm 7.

In Algorithm 7, to improve efficiency, we can remove both PublicKS and include them in the relinearization steps of the previous WoP-PBS. If parameters allow it, one might also replace Lines 6 and 7 of Algorithm 7 by a single WoP-PBS to extract the MSB directly.

Lemma 3 (MSB operations) For i ∈ {1, 2}, let ct i = LWE s (m i • ∆) be two LWE ciphertexts, encrypting m i • ∆ with 0 ≤ m i < 2 p and ∆ = q 2 p , both encrypted under the same secret key s = (s 1 , . . . , s n ) ∈ Z n q , with noise sampled in χ σ i . Let BSK, KSK, RLK be defined as in Theorem 5.

Then Context:

                       s = (s 1 , • • • , sn) ∈ Z n q s = (s 1 , • • • , s kN ) ∈ Z kN q S = S (1) , . . . , S (k) ∈ R k q ∀1 ≤ i ≤ k, S (i) = N -1 j=0 s (i-1)•N +j+1 X j ∈ Rq ∆ = q 2 p ∈ Zq 0 ≤ m 1 , m 2 < 2 p P Id : a redundant LUT for x → x (identity function) Input:                            ct 1 = LWEs(m 1 • ∆) ∈ Z n+1 q ct 2 = LWEs(m 2 • ∆) ∈ Z n+1 q BSK = BSK i = GGSW (B, ) S (s i ) 1≤i≤n : a bootstrapping key from s to S KSK 1 = CT i = GLev (B, ) S s i 1≤i≤kN
: a key switching key from s to S

KSK 2 = ct i = Lev (B, ) s s i 1≤i≤kN
: a key switching key from s to s

RLK = CT i,j = GLev (B, ) S S i • S j 1≤j≤i 1≤i≤k
: a relinearization key for S Output: ctout = LWEs • ∆), under the secret key s .

m 1 +m 2 2 p 2 p • ∆ ctout = LWEs m 1 •m 2 2 p 2 p • ∆ 1 begin /*
The variance of the noise of ct out can be estimated by composing the noise formulas of the different operations composing the algorithm. The complexity of Algorithm 7 is:

C (n, PBS ,k 1 ,N 1 , KS , RL ,k 2 ,N 2 ) Add MSB 2 p = 3C (n, PBS ,k 1 ,N 1 , KS , RL ,k 2 ,N 2 ) WoP-PBS + 2C (1, KS ,k 2 N 2 ,1,n) PublicKS + 2(N 2 + 1)C add C (n, PBS ,k 1 ,N 1 , KS , RL ,k 2 ,N 2 ) Mul MSB 2 p = 3C (n, PBS ,k 1 ,N 1 , KS , RL ,k 2 ,N 2 ) WoP-PBS + 2C (1, KS ,k 2 N 2 ,1,n) PublicKS + (N 2 + 1)C add + C ( KS , RL ,k 2 N 2 ,1,k 2 N 2 ) LWEMult (6)
Proof 9 (sketch) The first two WoP-PBS of the algorithm send the two messages m 1 and m 2 to a lower scaling factor q 2 2p . This way, when the leveled addition (resp. the LWEMult) operation is performed, the new precision 2p will be able to store the entire (both MSB and LSB) exact result. The third WoP-PBS is used to extract only the LSB of the result, that will be subtracted from the result of the previous computation to obtain an encryption of the MSB at scaling factor q 2 p , i.e, ready to be used in the following computation. Observe that the PublicKS are used in order to switch the secret key in order to be compatible with the following operation.

Faster Circuit Bootstrapping

In TFHE [START_REF] Chillotti | Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[END_REF], authors present a technique called circuit bootstrapping, that allows to convert an LWE ciphertext into an GGSW ciphertext. The circuit bootstrapping is necessary for leveled evaluations using the external product: the latter's inputs are both GLWE and GGSW ciphertexts, while its output is a GLWE ciphertext. To sum up, circuit bootstrapping allows to build a new GGSW ciphertext from an LWE ciphertext so one can use it as input to an external product for instance. The authors of [START_REF] Chillotti | Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[END_REF] observe that a GGSW ciphertext, encrypting a message µ ∈ Z (µ is binary in their application) under the secret key S = (S 1 , . . . , S k , S k+1 = -1), is composed by (k+1) GLWE ciphertexts encrypting µ•S i • q B j , for 1 ≤ i ≤ k+1 and 1 ≤ j ≤ . As already mentioned in Section 2, the goal of circuit bootstrapping is to build one by one all the GLWE ciphertexts composing the output GGSW. In order to do that, it performs the following two steps:

• The first step performs independent TFHE PBS to transform the input LWE encryption of µ into independent LWE encryptions of µ • q B j . • The second step performs a list of (k + 1) private key switchings from LWE to GLWE to multiply the messages µ • q B j obtained in the first step by the elements of the secret key S i , and so to obtain the different lines of the output GGSW.

Here, we propose a faster method based on the PBSmanyLUT algorithm (Algorithm 6). In a nutshell, the idea is to replace the PBS of the first step by only one PBSmanyLUT (that costs exactly the same as a one of the original PBS and do not increase the noise). Since the most costly part of the circuit boostrapping is due to the PBS part, the overall complexity is then roughly reduced by a factor

. In [CGGI17], = 2, so we have an improvement of a factor 2 on the PBS part, without any impact on the noise.

Lemma 4 Let consider the circuit boostrapping algorithm as described in [START_REF] Chillotti | Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[END_REF]Alg. 11]. The independent bootstrappings (line 2) could be replaced by:

{ct i } i∈[1, ] ← PBSmanyLUT(ct in , BSK, P • X N/2 ρ+1 , 1, κ = 0, ρ = log 2 ( ) ) ∀i ∈ [1, ], ct i + 0, q 2B i with P (X) = N 2 ρ -1 i=0 2 ρ -1 j=0 q 2B j X 2 ρ •i+j .
Proof 10 By calling PBSmanyLUT with ρ = log 2 ( ) , we are able to compute PBS in parallel. The polynomial P represents the LUT:

    q 2B 1 , . . . , q 2B
, 0, . . . , 0

2 ρ elements , q 2B 1 , . . . , q 2B
, 0, . . . , 0 2 ρ elements , . . . , q 2B 1 , . . . , q 2B , 0, . . . , 0

2 ρ elements     N =N/2 ρ elements
In the end, for i ∈ [1, ], ct i = LWE S (± q 2B i ), with the sign depending on the plaintext value. By adding the trivial ciphertext 0, q 2B i to the ct i , we either get ct i = LWE S ( q B i ) or LWE S (0), as expected.

Large Precision Without Padding (Programmable) Bootstrapping

We first describe a way to efficiently bootstrap an LWE ciphertext with larger precision and then show how to also compute a PBS on such ciphertexts. These algorithms do not require the input LWE ciphertext to have a bit of padding.

Larger Precision Without Padding Bootstrapping

We introduce a new procedure in Algorithm 8 to homomorphically decompose a message encrypted inside a ciphertext in α ciphertexts each encrypting a small chunk of the original message. The key of the efficiency of this algorithm is to begin by extracting the least significant bits instead of the most significant bits. To do so, we use the previously introduced parameter κ to remove some of the most significant bits of the input message m and apply the bootstrapping algorithm on the remaining bits as described in subsection 3.2. The bootstrapping algorithm must be a WoP-PBS (Algorithm 4 or 5) as the value of most significant bit is not guaranteed to be set to zero. This procedure allows us to obtain an encryption of the least significant bits of the message. Next, by subtracting this result to the input ciphertext, we remove the least significant bits of the input message. This gives a new ciphertext encrypting only the most significant bits of the input message. From now on, this procedure is then repeated on the resulting ciphertext until we obtain

α ciphertexts, each encrypting m i ∆ i such that m in ∆ in = α-1 i=0 m i ∆ i .
This process is somehow similar to the approach called Digit Extraction applied on the BGV/BFV schemes, presented in [START_REF] Halevi | Bootstrapping for helib[END_REF][START_REF] Chen | Homomorphic lower digits removal and improved fhe bootstrapping[END_REF]. This entails a significantly better complexity than the solution explained in the Limitation E as each bootstrap only needs a ring dimension big enough to bootstrap correctly the number of bits of each chunk instead of having to be big enough to bootstrap correctly the total number of bits of the input ciphertext.

Efficiency might be improved within the multiplication inside each WoP-PBS by adding a keyswitching during the relinearization step to reduce the size of the LWE dimension. As the complexity of the WoP-PBS depends on this LWE dimension, this will result in a faster version of Algorithm 8.

Algorithm 8: ct out ← Decomp(ct in , BSK, RLK, KSK, ℒ)

Context:                          s = (s 1 , • • • , sn) ∈ Z n q s = (s 1 , • • • , s N ) ∈ Z kN q S = S (1) , . . . , S (k) ∈ R k q ∀1 ≤ i ≤ k, S (i) = N -1 j=0 s (i-1)•N +j+1 X j ∈ Rq {P f i } i∈[0,α-1] : LUTs for the functions f i ∀i ∈ [1, α -1], ∆ i = ∆ in • 2 i-1 j=1 d j ≤ q ∆ 0 = ∆ in , m in ∆ in = α-1 i=0 m i ∆ i Input:      ct in = LWEs(m in • ∆ in ) ∈ Z n+1 q BSK, KSK, RLK : as defined in Algorithm 4 ℒ = {d i } i∈[0,α-1] with d i ∈ N * Output: {ct out,i = LWE s (m i • ∆ i )} i∈[0,α-1] 1 begin 2 ct ← ct in 3 for i ∈ [0, α -1] do 4 κ i ← α-1 j=i+1 d j 5 ct out,i ← WoP-PBS(ct, BSK, RLK, KSK, P f i , ∆ i , κ i , 0) 6 ct ← ct -ct out,i 7 end 8 end Lemma 5 Let ct in = LWE s (m in • ∆ in ) ∈ Z n+1 q be a LWE ciphertext, encrypting m in • ∆ in ∈ Z q .
under the LWE secret key s = (s 1 , . . . , s n ) ∈ Z n q , with noise sampled from χ σ . Let BSK, KSK and RLK as defined in Theorem 5.

Let ℒ = {d i } i∈[0,α-1] with d i ∈ N * s.t. ∆ in 2 α-1 i=0 d i ≤ q be the list defining the bit size of each output chunk. Algorithm 8 computes α ∈ N * new LWE ciphertexts {ct out,i } i∈[0,α-1] ,
where each one of them encrypts m i • ∆ i , where ∆ i = ∆ in • 2 i-1 j=1 d j , under the secret key s . The variances of the noise is Var(ct out,i ) = Var(WoP-PBS). The complexity is:

C (n, PBS ,k 1 ,N 1 , KS , RL ,α) Decomp = αC (n, PBS ,k 1 ,N 1 , KS , RL ,1,n) WoP-PBS 1 +α(n+1)C add + α(α + 1) 2 C add .
An immediate application of Algorithm 8 is a high precision bootstrap algorithm. By using the decomposition and then adding each ct out,i , one can get -with the right parameters-a noise smaller than the one of the input ciphertext.

Larger Precision WoP-PBS

The Tree-PBS and the ChainPBS algorithms introduced in [GBA21] allow to compute large precision programmable bootstrappings assuming that the input ciphertexts are already decomposed in chunks. In a nutshell, the idea behind the Tree-PBS is to encode a high-precision function in several LUTs. The first input ciphertext is used to select a subset among all the LUTs. This subset is then rearranged thanks to a key switching to build new encrypted LUTs. The previous steps can be repeated on the second input ciphertext, and so on. The Tree-PBS relies on the multi-output bootstrap from [START_REF] Carpov | New techniques for multi-value input homomorphic evaluation and applications[END_REF].

Thanks to the Algorithm 8, we are able to efficiently decompose a ciphertext. This allows to quickly switch from one representation (one ciphertext for one message) to another (e.g., several ciphertexts for one message) before calling the Tree-PBS or the ChainPBS algorithms. Moreover, we can replace the calls to PBS in both of the algorithms by a WoP-PBS. one of the alternative Algorithms 4 (or 5 can perform the same operation as the PBS, one can replaced the PBS in [START_REF] Guimarães | Revisiting the functional bootstrap in TFHE[END_REF] algorithms by a WoP-PBS. This relaxes the need to call Tree-PBS or ChainPBS with ciphertexts having a bit of padding. We call these two algorithms respectively the Tree-WoP-PBS and the Chained-WoP-PBS. Note that these algorithms can also be used to implement the Add MSB 2 p and Mul MSB 2 p operators.

Conclusion

This paper extends TFHE by exceeding some of its limitations. In particular, we present a new technique that allows to bootstrap messages without requiring a bit of padding, taking advantage of the GLWE multiplication (tensor product plus relinearization) and of our generalized version of TFHE's PBS. The latter additionally allows to evaluate multiple LUTs in a single PBS for free when possible. These two techniques are particularly interesting when used to improve both the gate bootstrapping and the circuit bootstrapping techniques of TFHE. Thank to this new programmable bootstrapping, there is no need to compute a systematic PBS in every homomorphic Boolean gates as leveled additions and multiplications can be evaluated between when noise allows it. Additionally, the evaluation of Boolean circuits can be extended in order to support the evaluation of larger powers of 2 modular arithmetic and exact integer arithmetic. The circuit bootstrapping can be drastically improved, by replacing the evaluation of multiple PBS in the algorithm by a single PBSmanyLUT (that costs exactly as a PBS), without affecting the noise growth. Finally, we introduce two new efficient methods to bootstrap ciphertexts with large precision: a bootstrapping method to bring the noise down as well as a programmable bootstrapping evaluating univariate functions.

Open problems. All the new techniques proposed improve the state of the art by adding new features to TFHE and getting rid of some of its constraints. However, many enhancements could be added. In particular, one of the major bottleneck concerns the computation of the negacyclic convolutions of polynomials. The most efficient method based on the FFT inherently adds noise to ciphertext due to the use of floating points over 64 bits. When applied with larger floating point representation, the performances collapse. Thus, the study of alternative methods compatible with the TFHE parameters might improve the practical performances.

Supplementary material A More Algorithms

A.1 GLWE Square Algorithm 9 describes the homomorphic square of a GLWE ciphertext.

Algorithm 9: CT ← GLWESquare(CT in , RLK) Context:      S = (S 1 , . . . , S k ) : a GLWE secret key ∆ = min ({∆ i }}) PT = N -1 i=0 m i ∆ i X i Input:    CT in = GLWE S (PT) = (A 1 , • • • , A k , B) RLK = CT i,j = GLev (B, ) S S (i) • S (j) 1≤j≤i 1≤i≤k : a relinearization key for S Output: CT = GLWE S PT 2 ∆ 1 begin /* Tensor product */ 2 for 1 ≤ i ≤ k do 3 T i ← [A 2 i ] Q ∆ q 4 end 5 for 1 ≤ i ≤ k, 1 ≤ j < i do 6 R i,j ← [2•Ai•Aj] Q ∆ q 7 end 8 for 1 ≤ i ≤ k do 9 A i ← [2•A i •B] Q ∆ q 10 end 11 B ← [B 2 ] Q ∆ q /* Relinearization */ 12 CT ← A 1 , • • • , A k , B + k i=1 CT i,i , dec (B, ) T i + 1≤j<i 1≤i≤k CT i,j • dec (B, ) R i,j 13 end
The noise analysis is similar to the noise analysis in Theorem 1.

A.2 Packed Products & Packed Sum of Products

In this section we report details for the algorithms described in Section 3.1.2: Algorithm 10 details the PackedMult operation, Algorithm 11 details the PackedSumProducts operation, Algorithm 12 details the PackedSquares operation and Algorithm 13 PackedSumSquares. Their noise analysis can be deduced from the results of Theorem 3.

Algorithm 10: ct (out) i α-1 i=0 ← PackedMult ct (1) i α-1 i=0 , ct (2) i α-1 i=0
, RLK, KSK

Context:                    s = (s 1 , • • • , sn) : the LWE input secret key s = (s 1 , • • • , s kN ) : the LWE output secret key S = S 1 , . . . , S k : a GLWE secret key ∀1 ≤ i ≤ k, S i = N -1 j=0 s (i-1)•N +j+1 X j α : such that α 2 ≤ N ∆out = max(∆ 1 , ∆ 2 ) Input:          ∀0 ≤ i < α, ct (1) i = LWEs(m (1) i • ∆ 1 ) ∀0 ≤ i < α, ct (2) i = LWEs(m (2) i • ∆ 2 )
RLK : a relinearization key for S as defined in algorithm 1 KSK : a key switching key from s to S as defined in algorithm 2

Output: ct

(out) i = LWE s m (1) i • m (2) i • ∆out α-1 i=0 1 begin /* KS from LWE to GLWE */ 2 ℒ 1 = {0, 1, 2, • • • , α -1}; 3 ℒ 2 = {0, α, 2α, • • • , (α -1)α}; 4 CT 1 ← PackingKS({ct (1)
i } α-1 i=0 , ℒ 1 , KSK) ; 5 CT 2 ← PackingKS({ct (2) i } α-1 i=0 , ℒ 2 , KSK) ; /* GLWE multiplication: Tensor product + Relinearization */ 6 CT ← GLWEMult(CT 1 , CT 2 , RLK) /* Sample extractions */ 7 for 0 ≤ i < α do 8 ct (out) i = LWE s m (1) i • m
(2) i

• ∆out ← SampleExtract (CT, i • (α + 1)) 9 end 10 end Algorithm 11: ct out ← PackedSumProducts({ct (1) i } α-1 i=0 , {ct (2)
i } α-1 i=0 , RLK, KSK)

Context:                    s = (s 1 , • • • , sn) : the LWE input secret key s = (s 1 , • • • , s kN ) : the LWE output secret key S = S 1 , . . . , S k : a GLWE secret key ∀1 ≤ i ≤ k, S i = N -1 j=0 s (i-1)•N +j+1 X j α : such that α ≤ N ∆out = max(∆ 1 , ∆ 2 ) Input:          ∀0 ≤ i < α, ct (1) i = LWEs(m (1) i • ∆ 1 ) ∀0 ≤ i < α, ct (2) i = LWEs(m (2) i • ∆ 2 )
RLK : a relinearization key for S as defined in algorithm 1 KSK : a key switching key from s to S as defined in algorithm 2

Output: ctout = LWE s α-1 i=0 m (1) i • m (2) i • ∆out 1 begin /* KS from LWE to GLWE */ 2 ℒ 1 = {0, 1, 2, • • • , α -1}; 3 ℒ 2 = {α -1, α -2, α -3, • • • , 0}; 4 CT 1 ← PackingKS({ct (1) i } α-1 i=0 , ℒ 1 , KSK) ; 5 CT 2 ← PackingKS({ct (2) i } α-1 i=0 , ℒ 2 , KSK) ; /* GLWE multiplication: Tensor product + Relinearization */ 6 CT ← GLWEMult(CT 1 , CT 2 , RLK) /* Sample extraction */ 7 ctout = LWE s α-1 i=0 m (1) i • m
(2) i

• ∆out ← SampleExtract (CT, α -1)

8 end Algorithm 12: ct (out) i α-1 i=0 ← PackedSquares {ct i } α-1 i=0 , RLK, KSK Context:                s = (s 1 , • • • ,
∀1 ≤ i ≤ k, S i = N -1 j=0 s (i-1)•N +j+1 X j α : such that 2 α ≤ N Input:      ∀0 ≤ i < α, ct i = LWEs(m i • ∆)
RLK : a relinearization key for S as defined in algorithm 1 KSK : a key switching key from s to S as defined in algorithm 2

Output: {ct

(out) i = LWE s (m 2 i • ∆)} α-1 i=0 1 begin /* KS from LWE to GLWE */ 2 ℒ = {2 0 -1, 2 1 -1, 2 2 -1, • • • , 2 α-1 -1}; 3 CT ← PackingKS({ct i } α-1 i=0 , ℒ,
= LWE s m 2 i • ∆ ← SampleExtract CT, 2 i+1 -2 7 end 8 end Algorithm 13: ct out ← PackedSumSquares {ct i } α-1 i=0 , RLK, KSK Context:                s = (s 1 , • • • , sn) : the LWE input secret key s = (s 1 , • • • , s kN ) : the LWE output secret key S = S 1 , . . . , S k : a GLWE secret key ∀1 ≤ i ≤ k, S i = N -1 j=0 s (i-1)•N +j+1 X j α : such that 2 α ≤ N Input:      ∀0 ≤ i < α, ct i = LWEs(m i • ∆)
RLK : a relinearization key for S as defined in algorithm 1 KSK : a key switching key from s to S as defined in algorithm 2

Output: ctout = LWE s α-1 i=0 m 2 i • 2∆ 1 begin /* KS from LWE to GLWE */ 2 ℒ 1 = {0, 1, 2, • • • , α -1}; 3 ℒ 2 = {2α -1, 2α -2, 2α -3, • • • , α}; 4 CT ← PackingKS({ct i } α-1 i=0 ||{ct i } α-1 i=0 , ℒ 1 ||ℒ 2 ,

B TFHE Generalized PBS

In this section, we provide a detailed proof of Theorem 4.

Proof 11 We consider the following LWE input ciphertext: (a i , • • • , a n , b) encrypted with the secret key s = (s 1 , • • • , s n ) so we have b = n i=1 a i •s i +m+e with a message m and an error e ∈ χ σ . We want to modulus switch this ciphertext and compute

a i ← a i •2N •2 κ-ϑ q • 2 ϑ 2N , for 1 ≤ i ≤ n + 1.
Let w = 2N • 2 -ϑ and q = q • 2 -κ . We note a i = w q a i = w q a i + a i , then we have a i ∈ ( -w 2 , w 2 ) and a i ∈ w q ( -q 2w , q 2w ). It means that Var(a i ) = w 2 -1

12 and E(a i ) = -1 2 , and that Var(a i ) = 1 12 -w 2 12q 2 and E(a i ) = -w 2q .

We decrypt:

Decrypt (a 1 , • • • , a n , b = a n+1 ), SK = = b - n i=1 a i • s i = w q b + b - n i=1 ( w q a i + a i ) • s i = w q b - n i=1 a i • s i + b - n i=1 a i • s i = w q m + w q e + b - n i=1 a i • s i
We can now study the error:

Var(E res ) = = Var w q e + b - n i=1 a i • s i = w 2 σ 2 in q 2 + Var(b) + n • Var(a i ) • (Var(s i ) + E 2 (s i )) + n • E 2 (a i ) • Var(s i ) = w 2 σ 2 in q 2 + 1 12 - w 2 12q 2 + n • 1 12 - w 2 12q 2 • 1 2 + n • w 2 4q 2 • 1 4 = w 2 σ 2 in q 2 + 1 12 - w 2 12q 2 + n 24 + nw 2 48q 2 E(E res ) = E w q e + b - n i=1 a i • s i = & & & & E w q e + E(b) - n i=1 E(a i • s i ) = -w 2q - n i=1 -w 2q • E(s i ) = w 2q • n 2 -1
In order to have correctness of the modulus switching with probability P = erf Γ √ 2 , the following condition must be satisfied:

Γ • Var(E res ) = Γ • w 2 σ 2 in q 2 + 1 12 - w 2 12q 2 + n 24 + nw 2 48q 2 < w∆ in 2q
which implies that:

σ 2 in < ∆ 2 in 4Γ 2 - q 2 12w 2 + 1 12 - nq 2 24w 2 - n 48 .
The steps of blind rotation and sample extraction are the same as in TFHE [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF]. We report the proof that estimates the noise after blind rotation (our analysis is slightly different from the analysis done in TFHE [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF]): the sample extraction step does not add any noise. In order to do the noise analysis for blind rotation, we need to analyze the noise of the external product.

Let the GLWE secret key be S = (S 1 , . . . , S k ) ∈ R k (in the algorithm it is notes S but we use the S notation to make the proof more readable), such that each polynomial key S i has coefficients sampled from a uniform binary, uniform ternary or Gaussian distribution with σ = 3.2. The external product : GLWE × GGSW → GLWE takes in input:

• A GLWE ciphertext c = GLWE S (µ) = (A 1 , . . . , A k , B = A k+1 ) ∈ R (k+1)
q such that the coefficients of the polynomials A α are sampled from ( -q 2 , q 2 ) and B = k α=1 A α • S α + M 1 + E 1 , where E 1 ∈ R q is such that each coefficient is sampled from (0, σ 2 1 ).

• A GGSW ciphertext C = GGSW S (m) = Z + M 2 • G ∈ R (k+1) ×(k+1)
q where G = Id ⊗ g is the gadget matrix, with g = ( q B , . . . , q B ). Each line of the GGSW ciphertext is of the form

C (i,j) = (A (i,j) 1 , . . . , A (i,j) k , B (i,j) ) = (A (i,j) , B (i,j) ) ∈ R (k+1)
q with i ∈ {1, . . . , k + 1} and j ∈ {1, . . . , }, such that the coefficients of the polynomials A (i,j) α are sampled from ( -q 2 , q 2 ) and

B (i,j) = k α=1 A (i,j) α • S α + M (i,j) 2 + E (i,j) 2
, where

E (i,j) 2 ∈ Z q [X]/(X N + 1) is such that each coefficient is sampled from (0, σ 2
2 ) and M (i,j) 2

= M 2 q B j (-S i ) (with S k+1 = -1). The output of the external product is:

• A GLWE ciphertext c out = GLWE S (M 1 • M 2 ) = (A out 1 , . . . , A out k , B out ) ∈ R (k+1) q
with error E ∈ R q such that each coefficient is sampled from (0, σ 2 ). We want to estimate σ.

Observe that the output is computed by computing:

c out = G -1 (c) R (k+1) •C = u • C
where the operation G -1 is the decomposition with respect to the gadget matrix. The product consists in the following steps:

1. Start by rounding each A α (α = 1, . . . , k + 1) at the log 2 (B) bit by A α , such that the coefficients of A α = A α -A α come from ( -q 2B , q 2B ).

Decompose each

A α = j=1 A α,j • q B -l with A α,j ∈ R with coefficients from ( -B 2 , B 2 ). 3. Return u = (A 1,1 , . . . , A 1, , . . . , A k,1 , . . . , A k, , B 1 = A k+1,1 , . . . , B = A k+1, ).
Observe that:

c out = G -1 (c) • C = u • C = k i=1 j=1 A i,j • C (i,j) + j=1 B j • C (k+1,j)
Let's compute the phase:

• E(A i,j ) = -1 2 , • Var(A i,j ) = B 2 -1 12 . E (i,j) 2
∈ R q is such that each coefficient is sampled from (0, σ 2 2 ). Then:

Var   j=1 k+1 i=1 (A i,j • E (i,j) 2 )   = • (k + 1) • Var A i,j • E (i,j) 2 = • (k + 1) • N • Var a i,j • e (i,j) 2 = • (k + 1) • N • Var a i,j • Var e (i,j) 2 + E 2 a i,j • Var e (i,j) 2 + Var a i,j • E 2 e (i,j) 2 = • (k + 1) • N • B 2 -1 12 • σ 2 2 + 1 4 • σ 2 2 = • (k + 1) • N • B 2 + 2 12 • σ 2 2
Step (2). Observe that M 2 ∈ R and we have no information about the distribution.

Observe that E 1 ∈ R q is such that each coefficient is sampled from (0, σ 2 1 ). Observe that B, A i come from ( -q 2B , q 2B ). So:

• E(A i ) = E(B) = -1 2 ,
• Var(A i ) = Var(B) = q 2 12B 2 -1 12 = q 2 -B 2 12B 2 . Then:

Var M 2 • E 1 -B + k i=1 A i • S i = ||M 2 || 2 2 • Var E 1 -B + k i=1 A i • S i
Where:

Var E 1 -B + k i=1 A i • S i = Var (E 1 ) + Var B + Var k i=1 A i • S i = Var (E 1 ) + Var B + kN • Var (a i • s i ) = σ 2 1 + q 2 -B 2 12B 2 + kN • Var (a i ) • Var (s i ) + E 2 (a i ) • Var (s i ) + Var (a i ) • E 2 (s i ) = σ 2 1 + q 2 -B 2 12B 2 + kN • q 2 -B 2 12B 2 • Var (s i ) + E 2 (s i ) + 1 4 • Var (s i ) = σ 2 1 + q 2 -B 2 12B 2 • 1 + kN • Var(s i ) + E 2 (s i ) + kN 4 • Var(s i )
If M 2 ∈ {0, 1} is a bit of the binary key as in the TFHE bootstrapping (E(M 2 ) = 1 2 and Var(M 2 ) = 1 4 and M 2 is a constant polynomial which we note m 2 ), then we have:

Var m 2 • E 1 -B + k i=1 A i • S i = Var (m 2 ) + E 2 (m 2 ) • Var E 1 -B + k i=1 A i • S i + Var (m 2 ) • E 2 E 1 -B + k i=1 A i • S i = 1 2 • Var E 1 -B + k i=1 A i • S i + 1 4 • E 2 E 1 -B + k i=1 A i • S i
Observe that:

E E 1 -B + k i=1 A i • S i = E (E 1 ) -E B + E k i=1 A i • S i = 0 + 1 2 + kN • E (a i ) • E (s i ) = 1 2 - kN 2 • E (s i ) = 1 2 • (1 -kN • E(s i ))
and:

E 2 E 1 -B + k i=1 A i • S i = 1 4 • (1 -kN • E(s i )) 2
Then:

Var m 2 • E 1 -B + k i=1 A i • S i = 1 2 • Var E 1 -B + k i=1 A i • S i + 1 4 • E 2 E 1 -B + k i=1 A i • S i = σ 2 1 2 + q 2 -B 2 24B 2 + kN 2 • q 2 -B 2 12B 2 • Var (s i ) + E 2 (s i ) + kN 8 • Var(s i ) + 1 16 • (1 -kN • E(s i )) 2 = σ 2 1 2 + q 2 -B 2 24B 2 • 1 + kN • Var (s i ) + E 2 (s i ) + kN 8 • Var(s i ) + 1 16 • (1 -kN • E(s i )) 2
Finally, if M 2 ∈ {0, 1} is a bit of the binary key as in the TFHE bootstrapping (E = 1 2 and Var = 1 4 ), then we have:

Var(E) = Var   j=1 k+1 i=1 (A i,j • E (i,j) 2 )   (1) + Var M 2 • E 1 -B + k i=1 A i • S i (2) = • (k + 1) • N • B 2 + 2 12 • σ 2 2 (1) + + σ 2 1 2 + q 2 -B 2 24B 2 • 1 + kN • Var (s i ) + E 2 (s i ) + kN 8 • Var(s i ) + 1 16 • (1 -kN • E(s i )) 2 (2)
The external product is used to compute the CMux, which is used in the programmable bootstrapping (PBS). In the PBS we have that:

C.0.3 Secret keys probability distributions.

We analyze the probability distributions of the secret keys and their combinations that appear in the multiplication. We start by observing some basic probability distributions for uniform binary, uniform ternary and Gaussian keys in Table 4.

Binary Ternary Gaussian

Var(s i ) 1/4 2/3 σ 2 E(s i ) 1/2 0 0 Var(s 2 i ) 1/4 2/9 2σ 4 E(s 2 i ) 1/2 2/3 σ 2 Var(s i s j ) 3/16 4/9 σ 4 E(s i s j ) 1/4 0 0
Table 4: Variances and expectations for s i , s 2 i and s i s j with s i and s j independently taken from the distribution and is either uniform binary, uniform ternary or Gaussian.

Distribution of S

i S j : i = j case. We consider a polynomial S(X) = N -1 i=0 s i • X i ∈ R q and S (X) = S 2 (X) = N -1 i=0 s i • X i = (N -2)/2 k=0 s 2k • X 2k + (N -2)/2 k=0 s 2k+1 • X 2k+1 ∈ R q .
We have each s i independently sampled from the same distribution of variance σ 2 and expectation µ .

     E(s α ) = E (s i • s j ) • (2α -N + 2) Var(s 2k ) = 2 • Var s 2 k + 2 • (N -2) • Var (s i • s j ) Var(s 2k+1 ) = 2 • N • Var (s i • s j )
Proof 12 Let's start by focusing on the even terms:

s α := s 2k = i+j=2k s i • s j = s 2 k -s 2 N 2 +k + i =j i+j=2k s i • s j = s 2 k -s 2 N 2 +k + i =j i+j=2k<N s i • s j - i =j i+j=2k≥N s i • s j = s 2 k -s 2 N 2 +k + i =j,i<j i+j=2k<N 2 • s i • s j - i =j,i<j i+j=2k≥N 2 • s i • s j
Observe that all the terms are independent since the couples (i, j) are exclusive in each sum. The variance is:

Var(s α ) := Var(s 2k ) = Var   s 2 k -s 2 N 2 +k + i =j,i<j i+j=2k<N 2 • s i • s j - i =j,i<j i+j=2k≥N 2 • s i • s j   = Var s 2 k + Var s 2 N 2 +k + Var   i =j,i<j i+j=2k<N 2 • s i • s j   + Var   i =j,i<j i+j=2k≥N 2 • s i • s j   = 2 • Var s 2 k + i =j,i<j i+j=2k<N 4 • Var (s i • s j ) k terms + i =j,i<j i+j=2k≥N 4 • Var (s i • s j ) N -2 2 -k terms = 2 • Var s 2 k + i =j,i<j i+j=2k 4 • Var (s i • s j ) N -2 2 terms = 2 • Var s 2 k + N -2 2 • 4 • Var (s i • s j ) = 2 • Var s 2 k + 2 • (N -2) • Var (s i • s j )
The expectation is:

E(s α ) := E(s 2k ) = E   s 2 k -s 2 N 2 +k + i =j,i<j i+j=2k<N 2 • s i • s j - i =j,i<j i+j=2k≥N 2 • s i • s j   = ¨¨Ë s 2 k - ¨¨¨Ë s 2 N 2 +k + E   i =j,i<j i+j=2k<N 2 • s i • s j   -E   i =j,i<j i+j=2k≥N 2 • s i • s j   = i =j,i<j i+j=2k<N 2 • E (s i • s j ) k terms - i =j,i<j i+j=2k≥N 2 • E (s i • s j ) N -2 2 -k terms = 2 • k • E (s i • s j ) -2 • N -2 2 -k • E (s i • s j ) = 2 • E (s i • s j ) • (k - N -2 2 + k) = E (s i • s j ) • (4k -N -2) = E (s i • s j ) • (2α -N + 2)
Now, let's focus on the odd coefficients.

s α := s 2k+1 = i+j=2k+1<N s i • s j - i+j=2k+1≥N s i • s j = i<j i+j=2k+1<N 2s i • s j - i<j i+j=2k+1≥N 2s i • s j
Observe again that all the terms are independent since the couples (i, j) are exclusive in each sum. The variance is:

Var(s α ) := Var(s 2k+1 ) = Var   i<j i+j=2k+1<N 2s i • s j - i<j i+j=2k+1≥N 2s i • s j   = Var   i<j i+j=2k+1<N 2s i • s j   + Var   i<j i+j=2k+1≥N 2s i • s j   = 4 • i<j i+j=2k+1<N Var (s i • s j ) k+1 terms +4 • i<j i+j=2k+1≥N Var (s i • s j ) N 2 -(k+1) terms = 4 • (k + 1) • Var (s i • s j ) + 4 • ( N 2 -k -1) • Var (s i • s j ) = 4 • Var (s i • s j ) • (k + 1 + N 2 -k -1) = 4 • Var (s i • s j ) • N 2 = 2 • N • Var (s i • s j )
The expectation is:

E(s α ) := E(s 2k+1 ) = E   i<j i+j=2k+1<N 2s i • s j - i<j i+j=2k+1≥N 2s i • s j   = E   i<j i+j=2k+1<N 2s i • s j   -E   i<j i+j=2k+1≥N 2s i • s j   = 2 • i<j i+j=2k+1<N E (s i • s j ) k+1 terms -2 • i<j i+j=2k+1≥N E (s i • s j ) N 2 -(k+1) terms = 2 • (k + 1) • E (s i • s j ) -2 • ( N 2 -k -1) • E (s i • s j ) = 2 • E (s i • s j ) k + 1 - N 2 + k + 1 = E (s i • s j ) (4k + 4 -N ) = E (s i • s j ) (2α + 2 -N )
In particular, in case of uniform binary, uniform ternary and Gaussian distributions, the squared secret keys have coefficients distributed as in Table 5.

Binary

Ternary Gaussian E(s α )

1 4 • (2α -N + 2) 0 0 E 2 (s mean ) = mean({E 2 (s α )} N -1 α=0 ) (N 2 +2) 48 0 0 Var(s 2k ) 3 8 • N -1 4 (2N -3) • 4 9 2N • σ 4 Var(s 2k+1 ) 3 8 • N N • 8 9 2N • σ 4
Table 5: General formula applied to polynomials with binary, ternary and Gaussian distributions. These formulas are true for N power of 2, N = 1.

For the Binary case, we can observe that:

N -1 α=0 E 2 (s α ) =   N/2-1 i=0 E 2 (s 2i+1 ) + N/2-1 i=0 E 2 (s 2i )   = N • (N 2 + 2) 48
This means that in average, the expectation of a coefficient of the squared binary key is (N 2 + 2)/48.

Proof 13   N/2-1 i=0 E 2 (s 2i+1 ) + N/2-1 i=0 E 2 (s 2i )   = N -1 k=0 E 2 (s k ) = N -1 k=0 k + 1 2 - N 4 2 = N -1 k=0 (k + 1) 2 4 -2 • k + 1 2 • N 4 + N 2 16 = N -1 k=0 k 2 4 + 1 4 + 2k 4 - kN 4 - N 4 + N 2 16 = N • 1 4 - N 4 + N 2 16 + N -1 k=0 k 2 4 + k 2 - kN 4 = N 4 - N 2 4 + N 3 16 + 1 4 • N -1 k=0 k 2 + 1 2 - N 4 • N -1 k=0 k = N 4 - N 2 4 + N 3 16 + + 1 4 • (N -1)N (2(N -1) + 1) 6 + 1 2 - N 4 • (N -1)N 2 = N (N 2 + 2) 48
Distribution of S i S j : i = j case. We consider two polynomials S 1 (X) =

N -1 i=0 S 1,i • X i ∈ R q and S 2 (X) = N -1 i=0 S 2,i • X i ∈ R q . We note as S (X) = S i (X) • S j (X).
We have:

S (X) = S i (X) • S j (X) = N α=1 S α • X α = N α=1   h+k=α<N S i,h • S j,k - h+k=α≥N S i,h • S j,k   • X α ∈ R q .
We have each coefficient of the two secret keys independently sampled from the same distribution of variance σ 2 and expectation µ .

E(S α ) = E (S i,h • S j,k ) • (2α + 2 -N ) Var(S α ) = N • Var (S i,h • S j,k )
Proof 14 Let S i , S j ∈ R be two independent keys following the same distribution (binary, ternary or Gaussian). Then:

S i • S j = N α=1 S α • X α = N α=1   h+k=α<N S i,h • S j,k - h+k=α≥N S i,h • S j,k   • X α
Observe that all the terms in the sum are independent. The variance is:

Var(S α ) = Var   h+k=α<N S i,h • S j,k - h+k=α≥N S i,h • S j,k   = Var h+k=α<N S i,h • S j,k + Var   h+k=α≥N S i,h • S j,k   = h+k=α<N Var (S i,h • S j,k ) + h+k=α≥N Var (S i,h • S j,k ) = h+k=α[N ] Var (S i,h • S j,k ) = N • Var (S i,h • S j,k )
The expectation is:

E(S α ) = E   h+k=α<N S i,h • S j,k - h+k=α≥N S i,h • S j,k   = E h+k=α<N S i,h • S j,k -E   h+k=α≥N S i,h • S j,k   = h+k=α<N E (S i,h • S j,k ) α+1 terms - h+k=α≥N E (S i,h • S j,k ) N -(α+1) terms = (α + 1) • E (S i,h • S j,k ) -(N -(α + 1)) • E (S i,h • S j,k ) = E (S i,h • S j,k ) • (α + 1 -N + α + 1) = E (S i,h • S j,k ) • (2α + 2 -N )
In particular, in case of uniform binary, uniform ternary and Gaussian distributions, the product secret keys have coefficients distributed as in Table 6.

Binary

Ternary Gaussian E(S α )

1 4 (2α + 2 -N ) 0 0 E 2 (S mean ) = mean({E 2 (S α )} N -1 α=0 ) N 2 +2 48 0 0 Var(S α ) 3 16 • N 4 9 • N σ 4 • N
Table 6: General formula applied to polynomials with binary, ternary and Gaussian distributions.

For the Binary case, we can observe that:

N -1 α=0 E 2 (S α ) = N • (N 2 + 2) 48
This means that in average, the expectation of a coefficient of the squared binary key is (N 2 + 2)/48.

Proof 15 N -1 α=0 E 2 (S α ) = N -1 α=0 1 4 (2α + 2 -N ) 2 = 1 16 • N -1 α=0 (2α + 2 -N ) 2 = 1 16 • N -1 α=0 4α 2 + 4 + 8α + N 2 -4N α -4N = 1 16 • 4N + N 3 -4N 2 + 4 N -1 α=0 α 2 + (8 -4N ) N -1 α=0 α = 1 16 • 4N + N 3 -4N 2 + 4 (N -1)N (2(N -1) + 1) 6 + (8 -4N ) (N -1)N 2 = N (N 2 + 2) 48

C.1 Tensor product

We perform a GLWE multiplication with dense messages having different scaling factors. The inputs are two GLWE ciphertexts modulo q:

CT (1) = (A (1) 1 , • • • , A (1)
k , B (1) = k i=1 A (1) i • S i + E 1 + P 1 ) ∈ R k+1 q CT (2) = (A (2) 1 , • • • , A (2)
k , B (2) = k i=1 A (2) i • S i + E 2 + P 2 ) ∈ R k+1 q such that • (S 1 , • • • , S k ) ∈ R k
is the secret key polynomial which have coefficients either sampled from a uniform binary, uniform ternary or gaussian distribution,

• {A

(1) i } k i=1 and {A

(2) i } k i=1 are polynomials in R q with coefficients sampled from ( -q/2, q/2 ),

• E 1 , E 2 are error polynomials in R q such that their coefficients are sampled from Gaussian distributions χ σ 1 , χ σ 2 respectively,

• P 1 = ∆ 1 • M 1 q and P 2 = ∆ 2 • M 2 q , with M 1 , M 2 ∈ T N [X] and ∆ 1 and ∆ 2 the scaling factors.

The first step (modulus switching, tensor product, rescale, round and modulo) is to compute:

T i =         A (1) i • A (2) i Q ∆         q depending on S 2 i k terms R i,j =         A (1) i • A
(2) j + A

(1)

j • A (2) i Q ∆        
q depending on S i • S j k(k -1) 2 terms

A i =         A (1) i • B (2) + B (1) • A (2) i Q ∆         q depending on S i k terms B = [B 1 • B 2 ] Q ∆ q constant term 1 term
where ∆ = min(∆ 1 , ∆ 2 ). The intermediate result of this step are the polynomials:

[T i ] Q = A (1) i • A (2) i = A (1) i • A (2) i q + q • U Ti ∈ R Q [R i,j ] Q = A (1) i • A
(2) j + A

(1)

j • A (2) i = A (1) i • A
(2) j + A

(1)

j • A (2) i q + q • U Ri,j ∈ R Q [A i ] Q = A (1) i • B (2) + B (1) • A (2) i = A (1) i • B (2) + B (1) • A (2) i q + q • U Ai ∈ R Q [B] Q = B (1) • B (2) = B (1) • B (2) q + q • U B ∈ R Q
These operations are performed in large precision Q = q 2 . The terms U T i , U R i,j , U A i , U B are in R. Then the polynomials are rescaled by ∆ and rounded modulo q:

[T i ] q = [T i ] Q ∆ q = [T i ] Q ∆ + T i q R i,j q = [R i,j ] Q ∆ q = [R i,j ] Q ∆ + R i,j q [A i ] q = [A i ] Q ∆ q = [A i ] Q ∆ + A i q [B ] q = [B] Q ∆ q = [B] Q ∆ + B
q such that T i , R i,j , A i , B are the rounding errors in ( -∆/2,∆/2 ) ∆ . Let's compute the noise growth generated by these operations. In order to estimate it, we have to • S is composed by k elements of the form S i = S, which distribution are given in Table 4.

• S T is composed by k elements of the form S 2 i = S , which distribution is studied in Section C.0.3. In particular, S = N -1 α=0 S α X α = S even + S odd with S even = N/2-1 i=0 S 2i X 2i and S odd = N/2-1 i=0 S 2i+1 X 2i+1 .

• S R is composed by k(k-1) 2 elements of the form S i • S j = S , which distribution is studied in Section C.0.3. Then: The formula is correct if N = 1. In fact, observe that the study for key S adapts for N = 1 but the key S does not. The square keys are not polynomials so there is just 1 term (not odd or even anymore). In case of S with N = 1, we fix the formula as follows:

Var(III) = Var B -A • S + R • S R + T • S T = Var B + Var A • S + Var R • S R + Var T • S T = ∆ 2 -1 12∆ 2 + k • N • Var(a)
If N = 1      Var(S odd ) = 0 Var(S even ) = 2 • Var(s 2 i ) E(S mean ) = E(s 2 i )
The factor 2 in Var(S even ) is given by the N/2 that took care of odd and even coefficients.

In the error of the tensor product:

Error(T , R , A , B ) = ∆ 1 ∆ M 1 E 2 + ∆ 2 ∆ M 2 E 1 + ∆ -1 E 1 E 2 (I) + + q ∆ (E 1 U 2 + E 2 U 1 ) (II) + B -A • S + R • S R + T • S T (III)
∈ R q the only difference happens in terms (I) and (II). Let's analyze them separately.

(I fill ) The variance is: (II fill ) By now, we note the coefficients S i,h of S i , simply by S. Then:

Var(I fill ) = Var ∆ 1 ∆ M 1 E 2 + ∆ 2 ∆ M 2 E 1 + ∆ -1 E 1 E 2 = Var ∆ 1 ∆ M 1 E 2 + Var ∆ 2 ∆ M 2 E 1 + Var(∆ -1 E 1 E 2 ) = ∆ 2 1 ∆ 2 ||M 1 || 2 ∞ (α 1 -1) • σ 2 2,
Var(II fill ) = = Var q ∆ (E 1 U 2 + E 2 U 1 ) = q 2 ∆ 2 • Var (E 1 U 2 + E 2 U 1 ) = q 2 ∆ 2 • (Var(E 1 U 2 ) + Var(E 2 U 1 )) = q 2 ∆ 2 • α 1
Var(e 1,fill u 2 ) + (N -α 1 )Var(e 1,emp u 2 ) + q 2 ∆ 2 • α 2 Var(e 2,fill u 1 ) + (N -α 2 )Var(e 2,emp u 1 ) = q 2 ∆ 2 • α 1 Var(e 1,fill u) + (N -α 1 )Var(e 1,emp u) + q 2 ∆ 2 • α 2 Var(e 2,fill u) + (N -α 2 )Var(e 2,emp u) Observe that e i and u j indicate the coefficients of E i and U j respectively. The factor N comes from the fact that they are polynomials.

= q 2 ∆ 2 • Var(u) + E 2 (u)

C.3 Relinearization

The last step (relinearization) is to compute:

Relin(T , R , A , B ) = (A 1 , • • • , A k , B )+ k i=1 CT i,i , dec (B, ) (T i ) + 1≤j<i 1≤i≤k CT i,j • dec (B, ) R i,j
The computation of the phase gives:

CT • (-S, 1) = Bres -Ares • S = B+ k i=1 h=1 B RLK (i,i) h •T i,h + i-1 j=1 B RLK (i,j) h •R i,j,h -A•S-k i=1 h=1 A RLK (i,i) h •T i,h + i-1 j=1 A RLK (i,j) h •R i,j,h •S = B-A•S+ k i=1 h=1 A RLK (i,i) h •S+E RLK (i,i) h +S 2 i • q B h •T i,h + + k i=1 h=1 i-1 j=1 A RLK (i,j) h •S+E RLK (i,j) h +S i •S j • q B h •R i,j,h -k i=1 h=1 A RLK (i,i) h •T i,h + i-1 j=1 A RLK (i,j) h •R i,j,h •S = B-A•S+ k i=1 h=1 E RLK (i,i) h +S 2 i • q B h •T i,h + k i=1 h=1 i-1 j=1 E RLK (i,j) h +S i •S j • q B h •R i,j,h = B-A•S+ k i=1 h=1 E RLK (i,i) h •T i,h + k i=1 h=1 S 2 i • q B h •T i,h + + k i=1 h=1 i-1 j=1 E RLK (i,j) h •R i,j,h + k i=1 h=1 i-1 j=1 S i •S j • q B h •R i,j,h = B-A•S+ k i=1 h=1 E RLK (i,i) h •T i,h + k i=1 S 2 i •T i + k i=1 h=1 i-1 j=1 E RLK (i,j) h •R i,j,h + k i=1 i-1 j=1 S i •S j •R i,j = B-A•S+ k i=1 h=1 E RLK (i,i) h •T i,h + i-1 j=1 E RLK (i,j) h •R i,j,h + k i=1 S 2 i •(T i -T i )+ i-1 j=1 S i •S j •(R i,j -R i,j ) = B-A•S+R•S R +T•S T + k i=1 h=1 E RLK (i,i) h •T i,h + i-1 j=1 E RLK (i,j) h •R i,j,h -R•S R -T•S T = Pres + E + k i=1 h=1   E RLK (i,i) h • T i,h + i-1 j=1 E RLK (i,j) h • R i,j,h   -R • S R -T • S T Error
The error term is then:

Error = E (I) + k i=1 h=1   E RLK (i,i) h • T i,h + i-1 j=1 E RLK (i,j) h • R i,j,h   (II) -R • S R -T • S T (III)
For each term, we compute their variance:

(I) This is the error obtained from the tensor product computation (II) The variance of the second term is:

Var(II) = Var   k i=1 h=1   E RLK (i,i) h • T i,h + i-1 j=1 E RLK (i,j) h • R i,j,h     = Var k i=1 h=1 E RLK (i,i) h •T i,h +Var k i=1 h=1 i-1 j=1 E RLK (i,j) h •R i,j,h = k Var E RLK (i,i) h •T i,h + k(k-
= k N σ 2 RLK • B 2 -1 12 + 1 4 + k(k-1) N 2 σ 2 RLK • B 2 -1 12 + 1 4 = k N σ 2 RLK • (k + 1) 2 • B 2 + 2 12

  Figure1:In TFHE, messages are encoded in the most significant bits (MSB), and so it is rescaled by a scaling factor ∆, while the error appears in the least significant bits (LSB). The precision is log 2 ( q ∆ ), i.e 7 bits in the figure.

Figure 2 :

 2 Figure 2: Modulus switching operation in the generalized PBS (Algorithm 3): on top of the figures we illustrate the data ( m, m, e), on the bottom the dimensions (κ, 2N , ϑ).

Figure 3 :

 3 Figure 3: Plaintext after the modulus switching from the generalized PBS (Algorithm 3) where κ ≥ 0: on top of the figure we illustrate the data(m, β, m ), on the bottom the dimensions (2N , ϑ).

  decrypt. Let S R = (S 1 •S 2 , S 1 •S 3 , • • • , S k-1 •S k ) ∈ R (k-1)k 2 q and S T = (S 2 1 , S 2 2 , • • • , S 2 k ) such that (S R ||S T ) = S ⊗ S.

Table 1 :

 1 The redundancy is used to perform the rounding operation during bootstrapping. Parameters depending on the GLWE multiplicative depth and the precision.

	Precision	1	2	3	4	5	6	7	8	9 10 11 12
	Max. depth 32 16 16 8	8	8	8	4	4	4	4	4
	log 2 (N )	12 11 12 11 11 12 12 11 11 11 12 12
	log 2 (B)	8	5	8 12 10 8	8 20 17 15 17 17
		8 10 8	4	5	8	8	2	3	3	3	3
	Precision	13 14 15 16 17 18 19 20 21 22 23 24
	Max. depth 4	2	2	2	2	2	2	2	2	2	2	2
	log 2 (N )	12 11 11 11 11 11 11 11 12 12 12 12
	log 2 (B)	8 30 30 20 20 20 20 20 20 20 20 20
		8	1	1	2	2	2	2	2	2	2	2	2

Table 2 :

 2 Parameter set for 128 bits of security for a WoP-PBS 2 followed by a GLWE multiplication for different precisions. In the table, "KS" means Key Switching, "BR" means Blind Rotation and "Relin" means Relinearization.

	Precision n	PBS/KS log 2 (N ) log 2 (B) BR	BR	KS log 2 (B)	KS	Relin log 2 (B)	Relin
	1	550	11	17	2	21	2	30	1
	2	550	11	13	3	17	2	30	1
	3	550	11	10	4	17	2	20	2
	4	550	11	9	5	13	3	20	2
	5	550	11	5	9	10	4	24	2
	6	550	12	10	5	12	4	24	2
	7	550	12	4	13	10	5	24	2

Table 3 :

 3 Generalization of TFHE gate bootstrapping.

  sn) : the LWE input secret key s = (s 1 , • • • , s kN ) : the LWE output secret key S = S 1 , . . . , S k : a GLWE secret key

  Var(S odd ) + Var(S even ) + 2 • E 2 (S mean ) + N 2 • E 2 (t) • Var(S odd ) + Var(S even ) Var(S odd ) + Var(S even ) + 2 • E 2 (S mean ) + 1 4∆ 2 • Var(S odd ) + Var(S even )

	=	∆ 2 -1 12∆ 2 + kN •		∆ 2 -1 12∆ 2 • Var(S) + E 2 (S) +	1 4∆ 2 • Var(S) +
		+	k(k -1)N 2	•	∆ 2 -1 12∆ 2 • Var(S ) + E 2 (S ) +	1 4∆ 2 • Var(S ) +
	+ 12∆ 2 • = kN 2 • ∆ 2 -1 ∆ 2 -1 kN 12∆ 2 + 12∆

• Var(S) + E 2 (S) + E 2 (a) • Var(S) + + k(k -1) 2 • N • Var(r) • Var(S ) + E 2 (S ) + E 2 (r) • Var(S ) + + k • N 2 • Var(t) • 2 • (∆ 2 -1) • Var(S) + E 2 (S) + 3 • Var(S) + + k(k -1)N 24∆ 2 • (∆ 2 -1) • Var(S ) + E 2 (S ) + 3 • Var(S ) + + kN 24∆ 2 • (∆ 2 -1)

• Var(S odd ) + Var(S even ) + 2 • E 2 (S mean ) + 3 • Var(S odd ) + Var(S even )

  • α 1 Var(e 1,fill ) + (N -α 1 )Var(e 1,emp ) + α 2 Var(e 2,fill ) + (N -α 2 )Var(e 2,emp ) kN E(S)) 2 • • α 1 σ 1,fill + (N -α 1 )σ 1,emp + α 2 σ 2,fill + (N -α 2 )σ 2,emp

	=	N ∆ 2 •	q 2 -1 12	1 + kN Var(S) + kN E 2 (S) +	kN 4	Var(S) +	1 4	(1 +

  RLK •Var(r i,j,h )+σ 2 RLK •E 2 (r i,j,h ))

									2	1)	Var E RLK	h (i,j)	•R i,j,h
	= k N Var e	RLK (i,i) h	•t i,h +	k(k-1) N 2	Var e	h RLK (i,j)	•r i,j,h
	= k N Var(e	RLK (i,i) h	)•Var(t i,h )+Var(e	RLK (i,i) h	)•E 2 (t i,h )+E 2 (e	h RLK (i,i)	)•Var(t i,h ) +
	+	k(k-1) N 2	Var(e	RLK (i,j) h	)•Var(r i,j,h )+Var(e	RLK (i,j) h	)•E 2 (r i,j,h )+E 2 (e	h RLK (i,j)	)•Var(r i,j,h )
	= k N (σ 2 RLK •Var(t i,h )+σ 2 RLK •E 2 (t i,h ))+	k(k-1) N 2	(σ 2

I. Chillotti, D. Ligier, J.B. Orfila & S. Tap

I. Chillotti, D. Ligier, J.B. Orfila & S. Tap

A i,j • (A (i,j) , B (i,j) ) + j=1 B j • (A (k+1,j) , B (k+1,j) )

So:

Let's compute the variance of E:

We give more details on steps (1) and (2).

Step (1). Observe that A i,j ∈ R with coefficients from ( -B 2 , B 2 ), so:

• The message m 2 in the RGSW is one of the bits of the LWE secret key, so it comes from a ({0, 1});

• The CMux input is computed by the formula

And the noise goes down to a simple external product;

• The CMux in the PBS is repeated n times;

• The initial σ RLWE in the PBS is equal to 0.

Then, the noise in the PBS can be estimated by:

If the RLWE secret key is binary:

Algorithm 14: ct ← SampleExtract (CT, p)

C Multiplication noise analysis

In this section we provide the details for the noise analysis of the multiplication described in Algorithm 1. We start by providing some basic notations and analysis for the distributions composing the different elements that are called in the multiplication. We then provide noise analysis for the two parts of the multiplication, i.e. the tensor product in Section C.1 and the relinearization in Section C.3.

C.0.1 Notations.

We use the notation [•] q to indicate a centered modular reduction, i.e., mod q with representants chosen in -q/2, q/2 ⊂ Z. When we do operations by moving and integer value x ∈ Z between different moduli q < Q ∈ N, the following conversions are used:

Then, we have the following properties for polynomials P (X) ∈ R:

When doing operations between polynomials:

Note that U + and U * are integer polynomials. Their distribution depends on the distribution of the polynomials. C.0.2 Uniform distributions in a fixed interval.

We observe what are the variance and expectations of random variables from uniform intervals:

• Let a i be a uniform variable in -∆/2, ∆/2 ⊂ Z. Then:

• Let a i be a uniform variable in -q/2, q/2 ⊂ Z. Then:

So now, let's analyze the term:

Now, let's observe the following relations:

and

Observe that the coefficients of S 2 i and S i S j are all ≤ N , if the key is binary or ternary. Since N < q, we assume that they do not overlap modulo q. If the key is Gaussian, the coefficients will be a small factor of N in the worse case, and we still assume they do not overlap modulo q.

By putting together Equations 7, 8 and 9, we obtain the following equality:

Then we can observe:

The value q ∆ is an integer smaller than q according to our parameter choices. So q ∆ will not overlap modulo q.

We extract the error:

Let's analyze each term separately.

(I) The variance of the first term is:

(II) Let's estimate the expectation and variance of U 1 and U 2 . They come from the modulus switching adding two terms of error U 1 and U 2 . They represent the part overlapping the modulo q.

Remember that, according to the RLWE assumptions, the A, B are insistinguishable from uniform in ( -q/2, q/2 ) with CT = (A(X), B(X)) an RLWE ciphertext.

Observe that:

We are looking for U . Then:

We assume that qU ≈ ∆M + E + qU since ∆M + E appears in the LSB. In practice it's like we did not cut the Gaussian's tails so we overestimate from here.

In reality we study U as if we we were doing

in Z, it supposes in general that U is not bigger than Q/q so we can keep the modulo Q.

So we study the variance as follows:

And the expectation:

By now, we note the coefficients S i,h of S i , simply by S. Then:

Observe that e i and u j indicate the coefficients of E i and U j respectively. The factor N comes from the fact that they are polynomials.

(III) In this third part, we compute the variance of the error caused by the rounding. We consider that B, A, R, T are all sampled from ( -∆/2,∆/2 ) ∆ . We also consider that: Finally:

C.2 Bi-Distributed Error Polynomials

In this section, we analyse the case where the message is not a dense polynomial and the error polynomial has coefficients following two different distributions. In particular, we suppose that the message polynomial M contains 0 ≤ α ≤ N filled coefficients, and their corresponding error terms following a Gaussian distribution (0, σ 2 fill ), and there are N -α empty coefficients with containing error from the distribution (0, σ 2 emp ). We consider two message polynomials M 1 and M 2 . The first one contains the α 1 message coefficients m 1,1 , • • • , m 1,α 1 and the second polynomial contains the α 2 message coefficients m 2,1 , • • • , m 2,α 2 .

We will make the noise analysis only for the coefficients in the resulting plaintext polynomial filled with single product of the form m 1,i • m 2,j for 1 ≤ i ≤ α 1 and 1 ≤ j ≤ α 2 .

As instance, in a product like:

we are not going to analyse the noise in the c 1 coefficient as instance.

An example is the result of a LWE to GLWE key switching, where the constant term is the only one containing a message, and its error is larger than the error in the other coefficients. where:

is the realinearization key, so that each component RLK

To ease the notations in this section, we will note T , R , A , B as T, R, A, B respectively.

Decomposition We start by decomposing T and R w.r.t the basis B and the number of level starting from the MSB. By using the previous notation, we have:

p=0 T i,p X p , and each T i,p is the closest multiple of q B in Z q . Then, we write each T i,p as h=1 T i,p,h q

p=0 R i,j,p X p , and each R i,j,p is the closest multiple of q B in Z q . Then, we write each R i,j,p as h=1 R i,j,p,h q B h , where each R i,j,p,h ∈ -B 2 , B 2 . The R i,j = N -1 p=0 R i,j,p • X p term represents the rounding error, so that each coefficient of R i,j,p ∼ ( -q 2B , q 2B ). We note as T i,h the polynomial N -1 p=0 T i,p,h X p and as R i,j,h the polynomial

The variance of the third term is:

•(Var(ri,j )•Var(S )+E 2 (ri,j )•Var(S )+Var(ri,j )•E 2 (S mean ))+

12 ((k-1)•(Var(S )+E 2 (S mean ))+Var(S odd )+Var(S even )+2E 2 (S mean ))+ + kN 8 •((k-1)•Var(S )+Var(S odd )+Var(S even ))

Finally:

D Packing KS LWE to GLWE noise analysis

We consider the LWE secret key s

q such that b= n i=1 a i s i +m+e with e from χ σ . We consider the GLWE secret key S=(S 1 ,••• ,S k )∈R k q and a key switching key composed of the following GLWE ciphertexts

During the algorithm we will round the {a i } to the closest multiple of q B and then decompose them such that for 1 ≤ i ≤ n we have a i = a i + āi and for 1 ≤ j ≤ we have a i = j=1 a i,j q B j with āi uniform in -q 2B , q

2B

and a i,j uniform in -B 2 , B 2 . We have Var a i,j • A (i,j) 1

a i,j • E (i,j)

Let's now study the error term in the filled coefficient: Let's finally study the error term in the other coefficients: