Jakub Klemsa
email: jakub.klemsa@eurecom.fr

Hitchhiker's Guide to the TFHE Scheme

Keywords: Fully homomorphic encryption, TFHE scheme, Reliable homomorphic evaluation, Correctness

Also referred to as the holy grail of cryptography, Fully Homomorphic Encryption (FHE) allows for arbitrary calculations over encrypted data. First proposed as a challenge by Rivest et al. in 1978, the existence of an FHE scheme has only been shown by Gentry in 2009. However, until these days, existing general-purpose FHE schemes suffer from a substantial computational overhead, which has been vastly reduced since the original construction of Gentry, but it still poses an obstacle that prevents a massive practical deployment of FHE. The TFHE scheme by Chillotti et al. represents the state-of-the-art among general-purpose FHE schemes. This paper aims to serve as a thorough guide to the TFHE scheme, with a strong focus on the reliability of computations over encrypted data, and help researchers and developers understand the internal mechanisms of TFHE in detail. In particular, it may serve as a baseline for future improvements and/or modifications of TFHE or related schemes.

Introduction

Fully Homomorphic Encryption (FHE), first discovered by Gentry [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] in 2009, enables the evaluation of an arbitrary (computable) function over encrypted data. As a basic use-case of FHE, we outline a secure cloud-aided computation: we describe how a user (U) may delegate a computation over her sensitive data to a semi-trusted cloud (C):

• U generates secret keys sk, and (public) evaluation keys ek, which she sends to C; • U encrypts her sensitive data d with sk, and sends the encrypted data to C; • C employs ek to evaluate function f , homomorphically, over the encrypted data (i.e., without ever decrypting it), yielding an encryption of f (d), which it sends back to U; • U decrypts the message from C with sk, obtaining the desired result: f (d) in plain.

We illustrate the concept of homomorphic evaluation of a function over the plain vs. over the encrypted data in Figure 1. Among existing FHE schemes, two main means of homomorphic evaluation can be identified: (i) the leveled approach (e.g., [START_REF] Brakerski | Leveled) fully homomorphic encryption without bootstrapping[END_REF][START_REF] Cheon | Homomorphic encryption for arithmetic of approximate numbers[END_REF]), and (ii) the bootstrapped approach (e.g., [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF][START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF]), while a combination of both is also possible [START_REF] Cheon | Bootstrapping for approximate homomorphic encryption[END_REF]. The leveled approach (i) is particularly useful for functions that are represented by an evaluation circuit of limited depth which is known in advance. After evaluating it, no additional operation can be performed with the result, otherwise, the data might be corrupted. Based on the circuit's depth and other properties, parameters must be chosen accordingly. On the other hand, for the bootstrapped approach (ii), there is no limit on the circuit depth, which also means that the circuit does not need to be known in advance ← ----------Encrypted result Encr f (d)

Fig. 1 Illustration of an evaluation of function f over the plain and over the encrypted data in the User's and in the Cloud's domain, respectively. In both ways, the same result is obtained.

scheme by Chillotti et al. [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF] is currently considered as the state-of-the-art FHE scheme that follows the bootstrapped approach.

For a basic overview of the evolution of FHE schemes, we refer to a survey by Acar et al. [START_REF] Acar | A survey on homomorphic encryption schemes: Theory and implementation[END_REF] (from 2018; in particular for implementations, much progress has been made since then).

Basic Overview of TFHE

First, let us provide a high-level overview of TFHE and its abilities, and let us outline its structure.

Similar to many other FHE schemes, the TFHE scheme builds upon the Learning With Errors (LWE) encryption scheme, first introduced by Regev [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. There are two important properties of LWE: additive homomorphism, and the presence of noise; let us comment on either:

Additive homomorphism: LWE ciphertexts, also referred to as samples, are represented by vectors of (additive) group elements. By the nature of LWE encryption, LWE samples are additively homomorphic, which means that-roughly speaking-for two samples c 1 and c 2 , which encrypt respectively µ 1 and µ 2 , it holds that c 1 + c 2 encrypts µ 1 + µ 2 . Noise: To achieve security, LWE samples need to contain a certain amount of noise. However, with each homomorphic addition, noises also add up, which may ultimately destroy the accuracy/correctness of the plaintext.

Like many other FHE schemes, TFHE deals with the noise growth by defining a procedure referred to as bootstrapping. Bootstrapping aims at resetting the noise to an-on average-fixed level. Otherwise, if the noise exceeded a certain bound, the probability of correct decryption would drop rapidly.

To sum up, TFHE offers two operations: (i) homomorphic addition, and (ii) bootstrapping.

Homomorphic addition (i) is a very cheap operation, however, the noise accumulates. On the other hand, bootstrapping (ii) is a costly operation, but it refreshes the noise and-in case of TFHE-it is inherently capable of evaluating homomorphically a custom Look-Up Table (LUT), which can be moreover encrypted. These two operations are sufficient for the full homomorphism, i.e., the possibility to evaluate any computable function over encrypted data. In Figure 2, we introduce the TFHE gate, which comprises (i) homomorphic addition(s), grouped into a homomorphic dot-product with integer weights, followed by (ii) TFHE bootstrapping. For bootstrapping, we outline its internal structure that consists of four sub-operations: KeySwitch, ModSwitch, Blind-Rotate and SampleExtr.

Aim of this Work

The aim of this work is to provide FHE researchers and developers with a comprehensive and intelligible guide to the TFHE scheme. In particular, in this paper, we thoroughly analyze the noise growth of TFHE's operations, which is decisive for the correctness and reliability of homomorphic evaluations in the wild. Besides that, we comment on the purpose of selected tricks that are intended to decrease the noise growth. Therefore, our TFHE guide is supposed to provide useful insights for any prospective improvements and/or design modifications to TFHE(-related schemes).

Related Work. The original full paper on TFHE [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF] is followed by other papers that recall or redefine TFHE in numerous ways [START_REF] Guimarães | Revisiting the functional bootstrap in TFHE[END_REF][START_REF] Chillotti | Improved Programmable Bootstrapping with Larger Precision and Efficient Arithmetic Circuits for TFHE[END_REF][START_REF] Chen | Multikey homomorphic encryption from tfhe[END_REF][START_REF] Kwak | Towards Practical Multi-key TFHE: Parallelizable, Key-Compatible, Quasi-linear Complexity[END_REF], while changing the notation as well as the approach to describe the bootstrapping procedure.

Joye [START_REF] Joye | Sok: Fully homomorphic encryption over the [discretized] torus[END_REF] provides a SoK paper on TFHE, supported by many examples with concrete values. Our TFHE guide complements their SoK in particular by providing a thorough noise growth analysis, which is one of its pillars.

Paper Outline

We introduce building blocks of the TFHE scheme in Section 2. Next, in Section 3, we describe the construction of TFHE in detail with a particular focus on noise propagation. We further focus on the correctness of homomorphic evaluation in Section 4. In Section 5, we briefly comment on implementation aspects of TFHE. We conclude our paper in Section 6.

Building Blocks of TFHE

In this section, we first briefly outline flavors of LWE, we outline a technical notion, referred to as the concentrated distribution, and we provide a list of symbols and notation. Then, we introduce in detail a generalized variant of LWE, denoted GLWE, and we comment on its additive homomorphism, security and other properties. Finally, we define the decomposition operation that we use to build up a compound scheme called GGSW, which enables multiplicative homomorphism. The torus is the underlying additive group of LWE that is used in TFHE, denoted T and defined as T := R/Z with the addition operation. The torus can be represented by the interval [0, 1), with each addition followed by reduction mod 1, e.g., 0.3+0.8 = 0.1. Since T is an abelian group, we may perceive T as an algebraic Z-module, i.e., we further have scalar multiplication Z×T → T, defined as repeated addition.

The ring variant of LWE, introduced by Lyubashevsky et al. [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF], extends the module's ring to a ring of polynomials with a bounded degree. In TFHE, we will work with the ring Z[X]/(X N + 1), denoted Z (N ) [X], with N a power of two. Then, the underlying Z (N ) [X]-module comprises torus polynomials modulo

X N + 1, denoted T (N ) [X].

Concentrated Distribution

Unlike (scalar) multiplication, the division of a torus element by an integer cannot be defined without ambiguity, the same holds for the expectation of a distribution over the torus. However, this can be fixed for a concentrated distribution [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF], which is a distribution with support limited to a ball of radius 1 /4, up to a negligible subset. For further details, we refer to [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF].

Symbols & Notation

Throughout the paper, we use the following symbols & notation; we denote:

• B := {0, 1} ⊂ Z the set of binary coefficients, • T the additive group R/Z, referred to as the torus (i.e., real numbers modulo 1), • Z n the quotient ring Z/nZ (or its additive group), • ⌊•⌉ : R → Z the standard rounding function,

• for vector v, v i stands for its i-th coordinate, • ⟨u, v⟩ the dot product of two vectors u and v, • M (N ) [X] the additive group (or ring) of polynomials modulo X N + 1 with coefficients from M , where N ∈ N is a power of two, • for polynomial p(X), p (i) stands for the coefficient of p at X i , • for vector of polynomials w, w (j) i stands for the coefficient at X j of the i-th coordinate of w, • ∥p(X)∥ 2 2 the square of the l 2 -norm of polynomial p(X) (i.e., the sum of squared coefficients), • a $ ← M the uniform draw of random variable a from M , • a α ← M the draw of random variable a from M with distribution α (for α ∈ R, we consider the zero-centered /discrete/ Gaussian draw with standard deviation α),

• E[X], Var[X] the expectation and the variance of random variable X, respectively.

Generalized LWE

First, we define a generalized variant of the LWE scheme, referred to as GLWE, which combines plain LWE with its ring variant. We define GLWE solely over the torus, although another underlying structure might be used, e.g., Z q with prime q that is taken in some other schemes. Definition 1 (GLWE Sample). Let k ∈ N be the dimension, N ∈ N, N a power of two, be the degree, α ∈ R + 0 be the standard deviation of the noise, and let the plaintext space P = T (N ) [X], the ciphertext (sample) space C = T (N ) [X] 1+k and the key space K = Z (N ) [X] k . For µ ∈ P and z χ ← K, where χ is a key distribution, we call c = (b, a) =: GLWE z (µ) the GLWE sample of message µ under key z,

if b = µ -⟨z, a⟩ + e, (1)
where a

$ ← T (N ) [X] k and e α ← T (N ) [X]
. If a = 0, we call the sample trivial, and if µ = 0, we call the sample homogeneous. We denote z := (1, z) ∈ Z (N ) [X] 1+k , referred to as the extended key. For N = 1, we have the (plain) LWE sample and we usually denote its dimension by n. We also generalize GLWE sampling to vector messages, yielding a matrix of 1+k columns, with one GLWE sample per row.

GLWE sampling is actually encryption: in TFHE, plaintext data is encrypted using the plain LWE, while GLWE is used internally. To decrypt, we apply the GLWE phase function (followed by rounding if applicable). Definition 2 (GLWE phase). Let k, N and α be GLWE parameters as per Definition 1, and let c = (b, a) be a GLWE sample of µ under GLWE key z. We call the function φ z : T

(N ) [X] × T (N ) [X] k → T (N ) [X], φ z (b, a) = b + ⟨z, a⟩ = ⟨z, c⟩, ( = µ + e), (2)
the GLWE phase. We call the sample c valid iff the distribution of φ z (c) is concentrated. Finally, for valid sample c, we call msg z (c) := E φ z (c) the message of c, which equals µ, since the noise is zero-centered and concentrated. Remark 1. GLWE phase returns µ + e, i.e., the original message with a small amount of noise. We may define GLWE decryption as either:

1. an erroneous decryption via GLWE phasewe accept some errors in the decrypted result, which might be considered harmless or even useful, e.g., in the context of differential privacy [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF]; or 2. a correctable decryption -for this purpose, we need to control the amount of noise and follow GLWE phase by an appropriate rounding step (relevant for this paper); or 3. an expectation of GLWE phase, i.e., msg z (c)this is useful for formal definitions and proofs.

In the following theorem, we state the additively homomorphic property of GLWE.

Theorem 1 (Additive Homomorphism). Let c1 , . . . , cn be valid and independent GLWE samples under GLWE key z and let w 1 , . . . , w n ∈ Z (N ) [X] be integer polynomials (weights). In case

c = n i=1 w i • ci is a valid GLWE sample, it holds msg z n i=1 w i • ci = n i=1 w i • msg z (c i ) (3)
and for the noise variance

Var[c] = n i=1 ∥w i ∥ 2 2 • Var[c i ]. ( 4
)
If all samples ci have the same variance V 0 , we have

Var[c] = V 0 • n i=1 ∥w i ∥ 2 2
and we define

ν 2 := n i=1 ∥w i ∥ 2 2 , (5)
referred to as the quadratic weights. We refer to the operation (3) as the (homomorphic) dot product (DP).

Discrete-Valued Plaintext Space

As outlined in Remark 1, item 2, in this paper, we focus on a variant of GLWE that restricts its messages to a discrete subspace of the entire torus plaintext space. Denoted by M, we refer to the plaintext subspace as the cleartext space, leaving the term plaintext space for torus polynomials.

In this paper, we only focus on the cleartext space of the form M = 1 2 π Z/Z ⊂ T (a subgroup of T isomorphic to Z 2 π ), where we refer to the parameter π as the cleartext precision. In terms of Definition 2, if it holds for the noise e that |e| < 1 /2 π+1 , then rounding of the value φ z (b, a) ∈ T to the closest element of M leads to the correct decryption/recovery of µ.

Discretized Torus

For the sake of simplicity of the noise growth analysis, TFHE is defined over the continuous torus, whereas in implementation, a discretized finite representation must be used instead. To cover the unit interval uniformly, TFHE implementations use an integral type-usually 32-or 64-bit (u)int-to represent a torus element, where we denote the bit-precision by τ . E.g., for τ = 32-bit uint32 type, t ∈ uint32 represents t /2 32 ∈ T ∼ [0, 1), where the denominator is usually denoted by q = 2 τ (in this case q = 2 32 ). Using such a representation, we effectively restrict the torus T to its submodule T q := q -1 Z/Z ⊂ T.

Distribution of GLWE Keys

For the coefficients of GLWE keys, a ternary distribution χ p : (-1, 0, 1) → (p, 1 -2p, p), parameterized by p ∈ (0, 1 /2), can be used. In particular, uniform ternary distribution is suggested by a draft of the homomorphic encryption standard [START_REF] Albrecht | Homomorphic encryption standard[END_REF], and it also is widely adopted by main FHE libraries like HElib [START_REF]HElib[END_REF], Lattigo [START_REF] Mouchet | Lattigo: A multiparty homomorphic encryption library in go[END_REF], SEAL [START_REF][END_REF], or HEAAN [19], although they implement other schemes than TFHE. With a fixed GLWE dimension and carefully chosen p, the distribution χ p may achieve better security as well as lower noise growth than uniform binary U 2 : (0, 1) → ( 1 /2, 1 /2). On the other hand, it is worth noting that for "small" values of p, such keys are also referred to as sparse keys (in particular with a fixed/limited Hamming weight), and there exist specially tailored attacks [START_REF] Cheon | A hybrid of dual and meet-in-the-middle attack on sparse and ternary secret lwe[END_REF][START_REF] Son | Revisiting the hybrid attack on sparse secret lwe and application to he parameters[END_REF]; we discuss security in the following paragraphs. Note 1. In TFHE, one instance of LWE and one of GLWE is employed. For LWE keys, usually, uniform binary distribution is used for technical reasons, although attempts to extend the key space can be found in the literature [START_REF] Joye | Blind rotation in fully homomorphic encryption with extended keys[END_REF]. For GLWE keys, a ternary distribution can be used immediately.

Security of (G)LWE

Estimation of the security of (G)LWE encryption is a complex task: it depends on (i) the size of the secret key (i.e., the dimension and/or the polynomial degree), (ii) the distribution of its coefficients, (iii) the distribution of the noise, which is usually given by its standard deviation, denoted by α, and (iv) the underlying structure (usually integers modulo q). As a rule of thumb, it holds that the longer key, the better security, as well as the greater noise, the better security.

A state-of-the-art tool that implements an LWE security assessment is known as lattice--estimator -a tool by Albrecht et al. [START_REF] Albrecht | contributors: Security Estimates for Lattice Problems[END_REF][START_REF] Albrecht | On the concrete hardness of learning with errors[END_REF]. Authors aim at considering all known relevant attacks on LWE, including those targeting sparse keys, as outlined previously. A plot that shows selected results of lattice-estimator can be found in Figure 3. A code example of the usage of lattice-estimator as well as raw data that were used to generate the figure can be found in our repository 1 .

Balancing Parameters

The downside of increasing the key size (improves security) is longer evaluation time (reduces performance), similarly increasing the amount of noise (improves security) leads to an error-prone evaluation (reduces correctness). Therefore, the goal is to find the best balance within the triangle of somehow orthogonal goals:

security performance correctness
The problem of finding such a balance is thoroughly studied by Bergerat et al. [START_REF] Bergerat | Parameter optimization & larger precision for (t)fhe[END_REF], who provide concrete results that aim at achieving the best performance, without sacrificing security, nor correctness.

Decomposition

To enable homomorphic multiplication and at the same time to reduce its noise growth, torus elements get decomposed into a series of integers. The operation is parameterized by (i) the decomposition base (denoted B; we only consider B = 2 γ a power of two), and (ii) by the decomposition depth (denoted d). We further denote

g := ( 1 /B, 1 /B 2 , . . . , 1 /B d ), (6)
referred to as the gadget vector. We define gad-

get decomposition of µ ∈ T ∼ [-1 /2, 1 /2) ⊂ R, denoted g -1 (µ), as the base-B representation of μ = ⌊B d • µ⌉ ∈ Z (multiplied in R) in the alphabet [-B /2, B /2) ∩ Z.
Note that such decomposition is unique. For the decomposition error, it holds that

µ -⟨g, g -1 (µ)⟩ ≤ 1 /2B d . (7)
We denote

ε 2 := 1 12B 2d and (8)
1 https://github.com/fakub/LWE-Estimates

V B := B 2 + 2 12 (9)
the variance of the decomposition error and the mean of squares of the alphabet [-B /2, B /2) ∩ Z (n.b., we assume B is even), respectively; for both we consider a uniform distribution. Note that with the alphabet [0, B) ∩ Z, the respective value of V B would have been higher, i.e., this is one of the little tricks to reduce later the noise growth. For k ∈ N, k ≥ 2, we further denote

G k := I k ⊗ g, (10)
where I k is identity matrix of size k and ⊗ stands for the tensor product, i.e., we have G k ∈ T kd×k , referred to as the gadget matrix.

We generalize g -1 to torus vectors and torus polynomials (and their combination) in a natural way: for vector t ∈ T n , g -1 (t) is the concatenation of respective component-wise decompositions g -1 (t i ), for polynomial t ∈ T (N ) [X], g -1 (t) proceeds coefficient-wise, i.e., the output is a vector of integer polynomials. Finally, for a vector of torus polynomials, g -1 outputs a concatenation of respective vectors of integer polynomials.

GGSW & Homomorphic Multiplication

Unlike GLWE, which encrypts torus polynomials, GGSW encrypts integer polynomials. The main aim of GGSW is to allow homomorphic multiplication of a (GLWE-encrypted) torus polynomial by a (GGSW-encrypted) integer polynomial. The multiplicative homomorphic operation is referred to as the External Product, denoted by : GGSW × GLWE → GLWE. Definition 3 (GGSW Sample). Let k, N and α be the parameters of a GLWE instance with key z. ) [X] if rows of Z are mutually independent, homogeneous GLWE samples under the key z. We call the sample valid iff there exists m ∈ Z ) [X] 1+k and GGSW sample Ā of corresponding dimensions, we define the External Product, : GGSW × GLWE → GLWE, as

We call C = Z+m•G 1+k , C ∈ T (N ) [X] (1+k)d,1+k , the GGSW sample of m ∈ Z (N
(N ) [X] such that each row of C-m•G 1+k is a valid homogeneous GLWE sample. Definition 4 (External Product). For GLWE sample c = (b, a) ∈ T (N
g -1 (c) T • Ā =: Ā c. ( 11
)
Est In the following theorem, we state the multiplicative homomorphic property of the external product and we evaluate its excess noise. Theorem 2 (Correctness & Noise Growth of ). Given GLWE sample c of µ c ∈ T (N ) [X] under GLWE key z and noise parameter α, and GGSW sample Ā of m A ∈ Z (N ) [X] under the same key and noise parameters, external product returns GLWE sample c′ = Ā c, which holds excess noise e , given by z, c′ = m A • z, c + e , for which it holds

Var[e ] ≈ dN V B α 2 (1 + k) amplified GGSW noise + + ∥m A ∥ 2 2 • ε 2 (1 + kN V z ) decomp. errors , ( 12
)
where V z is the variance of individual coefficients of the GLWE key z and other parameters are as per previous definitions. If e and the noise of c are "sufficiently small", c′ encrypts msg z (c ′ ) = m A • µ c , i.e., external product is indeed multiplicatively homomorphic.

Proof. Find the proof in Appendix A.1.

Constructing the TFHE Scheme

By far, there are two issues with (G)LWE:

1. As shown in Theorem 1, each additive homomorphic operation over (G)LWE samples leads to noise growth in the resulting aggregate sample, which limits the number of additions and which may also lead to incorrect results if the noise grows "too much". 2. Besides that, no homomorphic operation other than addition has been defined yet, which is not sufficient to achieve the full homomorphism.

The procedure referred to as bootstrapping aims at resolving them both at the same time: while refreshing the noise to a certain, constant-onaverage level, bootstrapping also inherently evaluates a function, referred to as the bootstrapping function, represented by a Look-Up Table (LUT). This makes TFHE fully homomorphic. Note 2. An approach that clearly achieves the full homomorphism is presented in the original paper by Chillotti et al. [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF], where authors define several logical gates, including ¬, ∨, and ∧. We refer to this variant as the binary TFHE, however, in this paper we rather focus on the variant of TFHE with a discrete multi-value cleartext space Z 2 π , as out- lined in Section 2.1.1. Binary TFHE might then be perceived as a special case.

As already outlined in Figure 2, TFHE gate is a combination of a homomorphic dot-product (cf. Theorem 1) and the bootstrapping procedure, which consists of four algorithms: KeySwitch, Mod-Switch, BlindRotate and SampleExtr; find a more detailed illustration of bootstrapping in Figure 4. In the rest of this section, we discuss each algorithm in detail (except ModSwitch, which we cover together with BlindRotate) and we combine them into the Bootstrap algorithm.

According to the results of Bergerat et al. [START_REF] Bergerat | Parameter optimization & larger precision for (t)fhe[END_REF], it shows that in most cases, more efficient TFHE parameters can be found if dot-product is Fig. 4 Outline of the internal structure of TFHE's bootstrapping. The aim of KeySwitch is to improve performance, whereas BlindRotate (inside the gray box) evaluates the LUT and refreshes the noise.

moved before key-switching (originally proposed by Bourse et al. [START_REF] Bourse | Fast homomorphic evaluation of deep discretized neural networks[END_REF]), as opposed to the original variant of TFHE [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF]. I.e., in the new variant, key-switching appears at the beginning of bootstrapping, whereas in the original variant, keyswitching is the last step. Authors of [START_REF] Bergerat | Parameter optimization & larger precision for (t)fhe[END_REF] also consider a variant that omits key-switching, but they do not find it more efficient either. Hence, we describe solely the new, re-ordered variant with key-switching in this paper.

Key-Switching

The first step towards refreshing the noise, which happens in blind-rotate, is key-switching. Since blind-rotate is a demanding operation, the aim of key-switching is to reduce the dimension of the input sample. Attempts to omit key-switching were also tested by Bergerat et al. [START_REF] Bergerat | Parameter optimization & larger precision for (t)fhe[END_REF], however, achieving a poorer performance than the variant with key-switching.

The key-switching operation, denoted Key-Switch, effectively changes the encryption key of LWE sample (b ′ , a ′ ) from LWE key s ′ ∈ B n ′ to LWE key s ∈ B n . Besides the input LWE sample, KeySwitch requires a series of key-switching keys, while the j-th key is defined as

KS j := LWE s (s ′ j g ′ ), j ∈ [1, n ′ ], (13)
where g ′ is a gadget vector given by decomposition base B ′ and depth d ′ , and where each component of s ′ j g ′ produces one LWE sample, independent from others. I.e., KS j ∈ T d ′ ,1+n is interpreted as a matrix, where rows are actual LWE samples. We denote the set of key-switching keys from s ′ to s as KS s ′ →s := (KS j ) n ′ j=1 . Note that key-switching keys consist of LWE samples and they can therefore be published as a part of evaluation keys.

Given LWE sample (b ′ , a ′ ) ∈ T 1+n ′ of µ under s ′ , key-switching keys KS s ′ →s , generated with gadget vector g ′ , we define key-switching as

KeySwitch s ′ →s (b ′ , a ′ ) = (b ′ , 0)- n ′ j=1 g ′-1 (a ′ j ) T •KS j , (14)
which returns an LWE sample of µ under s. Note that in fact, KeySwitch homomorphically evaluates the phase function. In the following theorem, we evaluate the excess noise induced by KeySwitch. Theorem 3 (Correctness & Noise Growth of Key-Switching). Given LWE sample c′ of µ ∈ T under LWE key s ′ and key-switching keys KS s ′ →s , encrypted with noise parameter α ′ , KeySwitch s ′ →s returns LWE sample c, which holds excess noise e KS , given by s, c = s′ , c′ + e KS , for which it holds

Var[e KS ] ≈ n ′ V s ′ ε ′2 decomp. errors + n ′ d ′ V B ′ α ′2 amplif. KS noise , (15)
where ε ′2 and V B ′ are as per (8) and (9), respectively, with B ′ and d ′ , V s ′ is the variance of individual coefficients of the LWE key s ′ , and other parameters are as per previous definitions. If e KS and the noise of c′ are "sufficiently small", it holds µ = msg s (c) = msg s ′ (c ′ ), i.e., KeySwitch indeed changes the key, without modifying the message.

Proof. Find the proof in Appendix A.2.

Blind-Rotate

The blind-rotate operation, denoted BlindRotate, is the cornerstone of bootstrapping since this is where the noise gets refreshed. It combines two ingredients: the decryption (phase) function φ s (b, a) = µ + e (cf. ( 2)), and the multiplicative homomorphism of GGSW×GLWE samples (cf. Theorem 2).

Internally, blind-rotate evaluates a relation reminiscent of the phase function φ s (b, a). However, as such, the phase function does not get rid of the noise -indeed, the error term remains present in the original amount; cf. [START_REF] Brakerski | Leveled) fully homomorphic encryption without bootstrapping[END_REF]. Therefore, a rounding step-as outlined in Section 2.1.1-must be included, too. Blind-rotate achieves rounding using a staircase LUT, i.e., a LUT that encodes a staircase function, where the "stairs" are responsible for rounding. Such a LUT is provided in a form of a (possibly encrypted) polynomial, which is referred to as the test vector, denoted by tv(X), whose coefficients represent the LUT values.

Roughly speaking, we aim at multiplying tv(X) by X -M , where M holds somehow the erroneous phase µ + e. This "shifts" the coefficients of tv(X) by M positions towards lower powers of X (we can think of discarding the coefficients that underflow for now). Then, evaluating tv(X)•X -M at X = 0 (i.e., taking the constant term of the product) yields the originally M -th coefficient of tv(X).

In the following paragraphs, we outline more concretely how a LUT can be encoded into a torus polynomial, which we further reduce modulo X N + 1, so that it can be taken as a plaintext for a (possibly trivial) GLWE sample.

Encoding a LUT into a Polynomial Modulo X N + 1

The product of degree-N polynomial tv(X) and monomial X m (with 0 ≤ m < N ) holds the coefficients of tv shifted by m positions towards higher degrees. Reducing the product tv(X) • X m modulo X N + 1 brings the coefficients of powers higher than or equal to N back to lower powers (namely by N positions) while flipping their sign (e.g., aX N +k is reduced to -aX k ). Hence, multiplication of a polynomial by a monomial modulo X N + 1 yields a negacyclic rotation. These are the consequences for LUT evaluation in blind-rotate:

• multiplying tv(X) by X -m mod X N + 1 with 0 ≤ m < N results in moving the m-th coefficient of tv(X) to the constant position, which is then taken as a result of the LUT; • for N ≤ m < 2N , the result equals to the (m -N )-th coefficient of tv(X) with a flipped sign, due to the negacyclic rotation; and • for greater m, it is worth noting that the period is 2N .

Since we assume that tv is a torus polynomial, we have LUT : Z 2N → T and it holds

LUT(N + m) = -LUT(m), m ∈ [0, N ), (16)
i.e., only the first N values of a LUT need to be provided explicitly, while the other N values are given implicitly by the negacyclic extension, and the rest is periodic with a period of 2N . Encoded in a test vector tv ∈ T (N ) [X] as

tv (m) = LUT(m), m ∈ [0, N ), ( 17
)
the LUT is evaluated at m ∈ Z as

X -m • tv(X) mod X N + 1 (0) = = (-1) ⌊ m /N⌋ • tv(X) (m mod N ) = = LUT(m mod 2N ). ( 18
)
We illustrate encoding of a LUT into a polynomial (test vector) tv(X) in Figure 5. Next, we outline the overall idea of blind-rotate.

Encoding the Stairs

Let us put forward explicitly the process of encoding the desired (negacyclic) bootstrapping function f : Z 2 π → Z 2 π (which acts on cleartexts) into the respective LUT : Z 2N → T, represented by the test vector tv(X), including the "stairs":

LUT(k) = f k • 2 π 2N , k ∈ [0, 2N ). ( 19
)
We provide an illustration of such an encoding in Figure 6. We recall that only the LUT values for k ∈ [0, N ) are actually encoded into the test vector; cf. ( 17), [START_REF][END_REF] and Figure 5. Recall that the "stairs" are supposed to be responsible for rounding, which in turn refreshes the noise. From 19, it follows that the width of such a stair is 1 /2 π . By E max , defined as

E max := 1 2 π+1 , (20)
we denote the maximum of error magnitude that leads to the correct LUT evaluation; cf. Figure 6. Note 3. Bootstrapping cannot be applied to only refreshing the noise, i.e., setting identity as the

tv(X) = 0 +1X -1X 2 +2X 3 (mod X 4 + 1) . . . provided LUT values . . .

negacyclic extension

Rotation by X -m with m = 3

X -3 • tv(X) = 2 +0X -1X 2 +1X 3 (mod X 4 + 1)
Fig. 5 Illustration of encoding of a LUT into a polynomial mod X N + 1 that is used in blind-rotate. We set N = 4 and we evaluate at m = 3, which means "rotation" by X -3 . The desired output value LUT(3) is emphasized in red. N.b., in this illustration, we omit the "stairs" for simplicity.

bootstrapping function, since identity is not negacyclic. A workaround must be made, with respect to a particular use case. Specifically, many existing implementations prepend an extra bit of padding, which they set to zero and do not use it. Note that such implementations need to somehow prevent possible overflows of homomorphic additions.

Idea of Blind-Rotate

First, let us get back to the phase function, which is responsible for decryption. Originally, with a LWE sample (b, a) to be bootstrapped, φ s (b, a) is (i) evaluated over the torus, and (ii) it is using known bits of the key s. For (i): based on previous observations, we first rescale & round the sample (b, a) ∈ T 1+n to the Z 2N domain, which preserves periodicity. Therefore, we calculate the scaled and rounded value of the phase function as

m = b + ⟨s, ã⟩, (21)
where b = ⌊2N b⌉ and ãi = ⌊2N a i ⌉, which is also referred to as modulus switching. As outlined previously, we aim at performing the evaluation of m as per [START_REF] Son | Revisiting the hybrid attack on sparse secret lwe and application to he parameters[END_REF] in powers of X; cf. [START_REF][END_REF].

For (ii): the secret key s is clearly not known to the evaluator (the cloud). Instead, bits s i of the key are provided in a form of GGSW samples BK i , encrypted with GLWE key z, and referred to as the bootstrapping keys, denoted by BK s→z = (BK i ) n i=1 . From (i) and (ii), it follows that given the sample (b, a) and the encrypted bits of the key s (bootstrapping keys), we can apply homomorphic operations to obtain the (encrypted) monomial X m modulo X N + 1, which we employ for LUT evaluation as per [START_REF][END_REF]. I.e., the test vector gets blindly rotated. s t a i r c . L U T p r e c . c l e a r t e x t p r e c . 6 Relation between a negacyclic bootstrapping function f and respective staircase LUT (illustrative). If the evaluated value does not leave its "stair", i.e., the input's error magnitude is lower than Emax, LUT gets evaluated correctly.

1 2 π . . . f : Z 2 π → Z 2 π . . . LUT : Z 2N → T Fig.
In the following paragraphs, we provide a full technical overview of modulus-switching and blind-rotate, respectively.

Modulus-Switching

As outlined, blind-rotate is preceded by a technical step, referred to as modulus-switching and denoted by ModSwitch, which is parameterized by N ∈ N. ModSwitch N , which inputs LWE sample (b, a) ∈ T 1+n under LWE key s and outputs LWE sample ( b, ã) ∈ Z 1+n 2N under the same key, is defined as

ModSwitch N (b, a) = ⌊2N b⌉, ⌊2N a i ⌉ n i=1 =: ( b, ã), (22)
where multiplications of type 2N •a i are performed in R (using any unit interval for T), then rounding brings result back to Z, from where we easily obtain Z 2N .

Due to rounding, additional noise is induced by ModSwitch; we evaluate it in the following lemma. Lemma 1 (Noise Growth of Modulus-Switching). ModSwitch N induces an excess noise, given by 1 /2N •⟨s, ( b, ã)⟩ = ⟨s, (b, a)⟩+e MS , for which it holds

Var[e MS ] = 1 + n /2 48N 2 , ( 23
)
where n is the LWE dimension.

Proof. We write

e MS = ⟨(1, s), ( b/2N -b, ã/2N -a)⟩ = = b/2N -b ∈(-1 /4N, 1 /4N] + s i • ( ãi /2N -a i ) ∈(-1 /4N, 1 /4N] , (24)
where each underbraced term is assumed to have a uniform distribution on (-1 /4N, 1 /4N], i.e., the variance of 1 /48N 2 . For s i , we have E[

s 2 i ] = 1 /2. For independent variables with E[Y ] = 0, it holds Var[X • Y ] = E[X 2 ] • Var[Y ],
which is this case for X = s i and Y = ãi /2N -a i . The result follows.

Description of Blind-Rotate

A description of blind-rotate is given in Algorithm 1. In line 3, if BK i encrypts s i = 0, the line evaluates to (encrypted) ACC = X 0•ãi • ACC, if BK i encrypts s i = 1, we obtain (encrypted) X 1•ãi • ACC. I.e., after blind-rotation, we obtain an encryption of X m • tv, where m = ⟨s, ( b, ã)⟩. Line 3 also mandates s i ∈ B, as outlined in Note 1, although generalization attempts exist [START_REF] Joye | Blind rotation in fully homomorphic encryption with extended keys[END_REF]. Remark 2. During blind-rotate, the "old" noise is refreshed with a fresh noise, which comes from the bootstrapping keys and from the (possibly encrypted) test vector -the fresh noise does not depend on the noise of the input sample. Nevertheless, the "old" noise affects what value from the test vector is selected (gets rotated to), i.e., at which point the (staircase) LUT is evaluated; cf. Figure 6. We discuss two types of decryption errors later in Section 4.1.1. In the following theorem, we evaluate the noise of the output of BlindRotate -i.e., the refreshed noise, which we denote V 0 .

Algorithm 1 BlindRotate

Input: LWE sample (b, a) of µ ∈ T under LWE key s ∈ B n , modulus-switched to ( b, ã) ∈ Z 1+n 2N , Input: (usually trivial) GLWE sample t ∈ T (N ) [X] 1+k of tv ∈ T (N ) [X] (aka. test vector) under GLWE key z ∈ Z (N ) [X] k , Input: for i ∈ [1,
n], GGSW samples of s i under z, referred to as bootstrapping keys, denoted BK s→z := (BK i ) n i=1 . Output: GLWE sample of X m • tv under z, where m = ⟨s, ( b, ã)⟩ ≈ 2N µ.

1: ACC ← X b • t ▷ aka. accumulator 2: for i ∈ [1, n] do 3: ACC ← ACC + BK i (X
Var[⟨z, ACC⟩] ≈ α 2 t + ndN V B α 2 (1 + k) + + nε 2 (1 + kN V z ) =: V 0 , (25)
which we denote by V 0 , other parameters are as per previous theorems and definitions. If the noise of ⟨z, ACC⟩ is "sufficiently small", it holds msg z (ACC) = X m • tv, where m = ⟨s, ( b, ã)⟩ ≈ 2N µ, i.e., BlindRotate indeed "rotates" the test vector by the approximate phase of (b, a), scaled to Z 2N .

Proof. Find the proof in Appendix A.3.

Sample-Extract

By far, BlindRotate outputs a GLWE sample of a polynomial (blindly-rotated test vector), which holds the desired value at its constant term and which is encrypted with a GLWE key. The goal of SampleExtr is to literally extract a partial LWE sample, which encrypts the constant term, out of the GLWE sample, which we denote by (b, a) ∈ T (N ) [X] 1+k (the last-step ACC in Algorithm 1). Note that a similar thing happens with the key:

the new LWE key is also an "extract" of the original polynomial GLWE key z ∈ Z (N ) [X] k . Writing down the constant term of ⟨z, (b, a)⟩, which is a torus polynomial, we obtain z, (b, a)

(0) = b (0) + k i=1 z i (X) • a i (X) (0) = = b (0) + k i=1 z (0) i , -z (N -1) i , . . . , -z (1) i i-th partial extr. LWE key z * i , a (0)
i , a

i , . . . , a

(N -1) i i-th partial extr. LWE sample a * i , ( 26
)
where we denote the i-th partial extracted LWE key and sample by z * i ∈ Z N and a * i ∈ T N , respectively. We obtain the full extracted LWE key and sample as their concatenations, denoted respectively as z * ∈ Z kN and (b (0) , a * ) ∈ T 1+kN , where b (0) is prepended. Note that a * is a simple serialization of polynomial coefficients of a, whereas for z, a rearranging is needed, together with negative signs. Finally, we have z, (b, a)

(0) = z * , (b (0) , a * ) , (27)
while noise preserves. Note that the extracted key z * plays the role of the LWE key s ′ that is supposed to be encrypted in key-switching keys -we compose the four algorithms and we provide further details in the next section.

TFHE Bootstrapping

Putting the four algorithms together, we obtain the TFHE (Programmable) Bootstrapping algorithm; find it as Algorithm 2, previously outlined in Figure 4. It is worth noting that BlindRotate (on line 3 of that algorithm) inputs a negative sample: this is due to the LUT encoding that we use; cf. ( 17) and ( 18), where a negative sign at m is expected, although by Theorem 4, a positive sign appears in the power of X.

We provide a summary of parameters in Table 1. For an exhaustive technical overview of blind-rotate, preceded by modulus-switching and followed by sample-extract, we refer to Appendix B, Figure B1.

Recall that the noise gets refreshed in Blind-Rotate (cf. Remark 2) and it does not change in ) [X] under the key z, where tv encodes negacyclic bootstrapping function f : Z 2 π → Z 2 π as per (17) and ( 19), Input: key-switching keys KS z * →s and bootstrapping keys BK s→z . Output: LWE sample of f (m) /2 π under key z * . SampleExtr, i.e., the variance of a freshly bootstrapped sample is given by V 0 as per [START_REF] Bergerat | Parameter optimization & larger precision for (t)fhe[END_REF]. N.b., at this point, we do not guarantee the correctness of the output -details will be given in Section 4, where we identify bounds that need to be satisfied so that the bootstrapping function is evaluated at the correct point.

Algorithm 2 Bootstrap Input: LWE sample (b * , a * ) ∈ T 1+kN of µ = m /2 π , m ∈ Z 2 π , under LWE key z * ∈ Z kN , extracted from GLWE key z ∈ Z (N ) [X] k , Input: (possibly trivial) GLWE sample t ∈ T (N ) [X] 1+k of test vector tv ∈ T (N
1: (b, a) ← KeySwitch (b * , a * ), KS z * →s 2: ( b, ã) ← ModSwitch N (b, a) 3: (s, r) ← BlindRotate (-b, -ã), t, BK s→z 4: return (b ′ , a ′ ) ← SampleExtr (s, r)

Correctness of LUT Evaluation

In this section, we combine the noise growth estimates from the previous section and we derive a condition for the correct evaluation of the bootstrapping function. As outlined, the noise propagates throughout various operations, let us provide an overview first.

Overview of Noise Propagation

The noise, which is present in every encrypted sample, evolves during the evaluation of a TFHE gate, which comprises (i) homomorphic dotproduct and (ii) bootstrapping (with its four suboperations). Let us comment on either operation: Dot-product: Provided that the noise of involved samples is independent, the error variance of a weighted sum is additive with weights squared (cf. (4) in Theorem 1).

Bootstrapping: If the noise of the sample-to-bebootstrapped is smaller than a certain bound, the blind-rotate step of bootstrapping evaluates the bootstrapping function correctly: i.e., the error of m (as per Theorem 4 and Algorithm 1) is smaller than the bound E max ; cf. Figure 6. The resulting sample then carries-on average-a fixed amount of noise (independent of the original sample), which solely depends on the TFHE parameters (cf. [START_REF] Bergerat | Parameter optimization & larger precision for (t)fhe[END_REF] in Theorem 4).

In Figure 7, we illustrate the error propagation throughout a TFHE gate, where e

(i)
0 denotes actual noise of the i-th, freshly bootstrapped sample. Note that the overall maximum of relative average noise is achieved within bootstrapping when the modulus-switched sample ( b, ã) enters blindrotate, which refreshes the noise; cf. Remark 2.

We denote the maximum error and its variance by e max and V max , respectively, and we have

V max ≈ ν 2 max • V 0 + V KS + V MS , (28)
where ν 2 max is the maximum of sums of squares of integer weights of dot-products (cf. ( 5)) across the entire computation, V 0 , V KS and V MS are respectively the variance of a freshly bootstrapped sample (cf. [START_REF] Bergerat | Parameter optimization & larger precision for (t)fhe[END_REF], combined using (4)), the variance of the excess noise of key-switching (cf. [START_REF] Albrecht | Homomorphic encryption standard[END_REF]) and that of modulus-switching (cf. ( 23)). Note that e max is the relative, torus-scaled error of m ∈ Z 2N that enters blind-rotate; cf. Algorithm 2. The magnitude of this error is decisive for the correctness of the bootstrapping function evaluation as per Figure 6. Note 4. Let us outline an intuition that justifies the design where key-switching is moved to the beginning of bootstrapping (proposed in [START_REF] Bourse | Fast homomorphic evaluation of deep discretized neural networks[END_REF], experimentally shown to be more efficient in [START_REF] Bergerat | Parameter optimization & larger precision for (t)fhe[END_REF], presented in this paper), as opposed to the original TFHE design [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF], where key-switching is the last step of bootstrapping. The variance of the maximum error of the original variant writes

V max ≈ (V BR + V KS V (or.) 0 ) • ν 2 + V MS , (29)
whereas in the re-ordered variant, we have

V max ≈ V BR V (re.) 0 •ν 2 + V KS + V MS , (30)
where V BR is the variance of the output of Blind-Rotate. We may notice that the re-ordered variant is expected to achieve a lower noise growth, in particular for applications with greater ν 2 . Also, note that the re-ordered variant in fact only swaps key-switching and dot-product; let us outline both, starting after sample-extract: ---→ KS → MS → . . .

Correct Evaluation of the Bootstrapping Function

Let us define the quantity κ, which aims at quantifying the probability of correct evaluation of the bootstrapping function (i.e., |e max | < E max ), as

κ := E max √ V max . ( 31
)
The aim of κ is to tell how many times the standard deviation of the maximum error, denoted σ max = √ V max , fits into the target interval of the size of 2E max around the expected value. The probability that a normally distributed random variable falls within the interval of κ times its standard deviation can be looked-up from standard normal tables (aka. the Z-tables). Note that by the Central Limit Theorem, we assume a normal distribution for the value of m. E.g., for κ = 3, we have Pr[•] ≈ 99.73% ≈ 1 /370 (aka. rule of 3σ), however, we recommend higher values of κ (e.g., Bergerat et al. [START_REF] Bergerat | Parameter optimization & larger precision for (t)fhe[END_REF] provide their parameters with κ = 4, which gives error rate ≈ 1 /15 787). N.b., also the size of the evaluated circuit as well as possible real-world consequences of an incorrect evaluation shall be taken into account.

From [START_REF]Concrete: State-of-the-art TFHE library for boolean and integer arithmetics[END_REF] and [START_REF] Cheon | A hybrid of dual and meet-in-the-middle attack on sparse and ternary secret lwe[END_REF], we obtain the fundamental condition on the variance of the maximum error as

V max ≤ 1 κ 2 • 2 2π+2 , (32)
where V max can be further broken down by [START_REF]NuCypher[END_REF] and other previous equalities. If the fundamental condition is satisfied, the (erroneous) value of m does not leave its "stair" with high probability (related to κ), and the bootstrapping function f is evaluated correctly; cf. Figure 6.

Types of Decryption Errors

Correct blind-rotate does not itself guarantee the correctness of the result after decryption -indeed, there is a non-zero probability that the freshly bootstrapped sample (or a dot-product of them) decrypts incorrectly due to the intrinsic LWE noise. Therefore, we define two types of decryption errors that may occur after a dot-product followed by bootstrapping: one due to LWE noise (as just outlined), and one due to incorrect blind-rotate.

Fresh Bootstrap Error (Err 1 ) First, let us assume that blind-rotate rotates the test vector correctly (i.e., |e max | < E max ) and we denote the output LWE sample of bootstrapping as c′ . Then, if the distance of ⟨s, c′ ⟩ from the expected value is greater than E max , we refer to this kind of error as the type-1 error, denoted Err 1 . The probability of Err 1 relates to the noise of a correctly blind-rotated, freshly bootstrapped sample, which can be estimated from V 0 ; see [START_REF] Bergerat | Parameter optimization & larger precision for (t)fhe[END_REF].

Blind-Rotate Error (Err 2 ) Second, we consider the result of a TFHE gate, i.e., we take a dot-product of a bunch of independent, freshly bootstrapped samples, with ν2 ≤ ν 2 max , and we bootstrap it. Then, if blind-rotate rotates the test vector incorrectly (i.e., |e max | > E max ), we refer to this kind of error as the type-2 error, denoted Err 2 . Note that a combination of both error types may occur 2 .

The probability of Err 2 relates to the error of modulus-switched sample ( b, ã) that appears inside bootstrapping, and it can be estimated from V max ; see [START_REF]NuCypher[END_REF]. We outline both error types in Figure 8. Corollary 1. For the probabilities of type-1 and type-2 errors, by [START_REF]NuCypher[END_REF] we have

Pr[Err 1 ] < Pr[Err 2 ]. ( 33
)
For common choices of parameters, Pr[Err 1 ] can be neglected. I.e., we may use the fundamental condition [START_REF] Van Beirendonck | FPT: a Fixed-Point Accelerator for Torus Fully Homomorphic Encryption[END_REF] to estimate the probability of incorrect evaluation of a single TFHE gate.

Parameter Constraints

Previously, we justified the use of the fundamental condition [START_REF] Van Beirendonck | FPT: a Fixed-Point Accelerator for Torus Fully Homomorphic Encryption[END_REF] to make error probability estimates. Next, we identify four high-level parameters that aim at characterizing the properties of an instance of TFHE. Finally, we combine the fundamental condition to obtain a relation between the four high-level parameters and actual TFHE parameters (like LWE dimension or noise amplitude).

Characteristic Parameters

Given a usage scenario, an instance of TFHE can be characterized by the following four (input) parameters:

1. cleartext space bit-precision, denoted by π (cf. Section 2.1.1); 2. quadratic weights, denoted by ν 2 (cf.

Theorem 1, we take maximum of computation); 3. bit-security level, denoted by λ; and 4. bootstrapping correctness, denoted by η := Pr[Err 2 ] (cf. Corollary 1).

Let us provide more (practical) comments on each of the input parameters.

Cleartext Bit-Precision: π Regarding the choice of an appropriate cleartext bit-precision, we point out two things: First, it shows that the complexity of the TFHE bootstrapping grows roughly exponentially with the cleartext bit-precision -reasonable bootstrapping times can be achieved for up to about π = 8 bits, then, splitting the cleartext into multiple chunks comes into play. Second, bootstrapping is capable of evaluating a custom bootstrapping function f : Z 2 π → Z 2 π , however, such function must be negacyclic; cf. ( 16) and (19), unless a workaround is adopted as per Note 3. Both limitations must be carefully considered before choosing the right cleartext space bit-precision π: it might make sense to decrease the cleartext space size at the expense of additional, but cheaper bootstrapping.

Quadratic Weights: ν 2 As outlined in (28), ν 2 max := max g {ν 2 g } is defined as the maximum of sums of squares of integer weights of dot-products across the whole circuit that comprises TFHE gates g ∈ G (with ν 2 defined in ( 5)). Note that log(ν g ) expresses the number of bits of the standard deviation of the excess noise introduced by the dot-product in gate g.

Security Level: λ

We discuss LWE/GLWE security in Section 2.1.4. Recall that the higher λ is requested, the higher LWE dimension and/or the lower noise must be present, and security also depends on the distribution of keys.

Bootstrapping Correctness: η Introduced in Section 4.1, the parameter κ characterizes the probability of erroneous blind-rotate. In Corollary 1, we use this probability to estimate the overall probability of correct evaluation of a TFHE gate. Hence, to quantify the probability of correct evaluation of a single TFHE gate, we take η, and by standard normal tables, we deduce the value of κ, which we use for the rest of the analysis. Recall that κ relates to the correctness of a single TFHE gate, i.e., for a circuit that consists of multiple TFHE gates, the value of η needs to be modified accordingly.

Parameter Relations

To make the fundamental condition (32) hold, we may combine ( 28) with ( 25), ( 15) and ( 23), and mandate

V max ≈ ν 2 • V 0 + V KS + V MS ≈ ≈ ν 2 • α 2 t + ndN V B α 2 (1 + k) + + nε 2 (1 + kN V z ) + kN V z ε ′2 + + kN d ′ V B ′ α ′2 + 1 + n /2 48N 2 ! ≤ ! ≤ 1 κ 2 • 2 2π+2 , (34)
where the baseline parameters are summarized in Table 1, ε 2 and V B are defined in ( 8) and ( 9), respectively, and V z stands for the variance of coefficients of the internal GLWE secret key z.

In terms of the security ↔ correctness ↔ performance triangle given in Section 2.1.5, this inequality only provides a guarantee of correctness, which is given by η (translated into κ), for prescribed plaintext precision π and quadratic weights ν 2 . In particular, security is not addressed and it must be resolved separately, e.g., using lattice-estimator [START_REF] Albrecht | contributors: Security Estimates for Lattice Problems[END_REF]. The combination of constraints on TFHE parameters makes it a complex task to generate a set of parameters, which is further supposed to achieve a good performance. Authors of [START_REF] Bergerat | Parameter optimization & larger precision for (t)fhe[END_REF] claim to have implemented a generator of efficient TFHE parameters and they provide a comprehensive list of TFHE parameters for many input setups. However, at the time of writing, the tool is not publicly available yet.

Implementation Remarks

In this section, we briefly comment on various implementation aspects of TFHE, namely • (negacyclic) polynomial multiplication;

• additional errors (noise) that stem from particular implementation choices; • estimated complexity & key sizes; and • existing implementations of TFHE, including recent trends and advances.

Negacyclic Polynomial Multiplication

For performance reasons, modular polynomial multiplication in TFHE-which appears, e.g., in GLWE encryption (1) or in external product (11)-is implemented using Fast Fourier Transform (FFT). Recall that polynomials mod X N + 1 rotate negacyclically when multiplied by X k , unlike polynomials mod X N -1, which rotate cyclically. Note that in such a case, polynomial multiplication is equivalent to the standard cyclic convolution, which can be calculated using Fast Fourier Transform (FFT). However, for polynomials mod X N + 1, other tricks need to be put into place; find a description of negacyclic polynomial multiplication, e.g., in [START_REF] Klemsa | Fast and error-free negacyclic integer convolution using extended fourier transform[END_REF].

Implementation Noise

Notably, FFT is the major source of additional errors (noise) that are not captured by the theoretical noise analysis given in Section 4. The magnitude of FFT errors depends particularly on the number representation that is used by selected FFT implementation; find a study on FFT errors in [START_REF] Klemsa | Fast and error-free negacyclic integer convolution using extended fourier transform[END_REF]. Although for commonly used parameters and FFT implementations, FFT errors are negligible compared to (G)LWE noises, they shall be kept in mind, in particular in non-standard constructions or new designs.

In addition, compared to the theoretical results of Section 4, torus elements are represented using a finite representation (as outlined in Section 2.1.2; e.g., with 64-bit integers), which also changes the errors slightly. However, as long as the torus precision (e.g., 2 -64 ) is much smaller than the standard deviation of the (G)LWE noisewhich is usually the case for common parameter choices-this contribution can be neglected.

Key Sizes & Bootstrapping Complexity

Below, we provide the sizes of key-switching and bootstrapping keys, as represented in a TFHE implementation with a τ -bit representation of torus elements. The complexity of TFHE bootstrapping, which is the dominant operation of TFHE, is roughly proportional to the key sizes.

Size of Key-Switching Keys

Using notation of Table 1, key-switching keys consist of N sub-keys KS j ∈ T d ′ ,1+n ; altogether we have

(KS j ) N j=1 = N d ′ (1 + n)τ [bits]. ( 35
)
Note that a common method to store/transmit key-switching keys, which can also be applied to bootstrapping keys, is to keep just a seed for a pseudo-random number generator (PRNG), instead of all of the randomness. I.e., for each LWE sample, just the value of b is kept and the values of a can be re-generated from the seed.

Size of Bootstrapping Keys

Bootstrapping keys consist of n GGSW samples BK i ∈ T (N ) [X] (1+k)d,1+k ; altogether we have

(BK i ) n i=1 = n(1 + k) 2 dN τ [bits]. ( 36
)
Rough Estimate of Bootstrapping Complexity Key-switching is dominated by N d ′ (1 + n) torus multiplications, followed by 1 + n summations of N d ′ elements, which makes keyswitching O N d ′ (1 + n)τ . Blind-rotate is dominated by n(1 + k) 2 d degree-N polynomial multiplications, followed by a similar number of additions/subtractions, which makes blind-rotate O n(1+k) 2 dN τ . Note that the entire calculation of BlindRotate (cf. Algorithm 1) can be performed in the Fourier domain -thanks to its linearity and pre-computed bootstrapping keys, i.e., the O(τ N log N ) term of FFT can be neglected. In this rough estimate, we neglect modulus-switching and sample-extract. Also, we do not distinguish the bit-length of τ for LWE and GLWE, as some implementations do [START_REF]NuCypher[END_REF].

Existing TFHE Implementations

The original (experimental) TFHE library [START_REF] Tfhe | Fast Fully Homomorphic Encryption Library over the Torus[END_REF] is not developed anymore, instead, there are other, more or less active implementations. Here we list selected implementations of TFHE: TFHE-rs [START_REF] Tfhe-Rs | Pure Rust implementation of the TFHE scheme for boolean and integers FHE arithmetics[END_REF]: written in Rust, TFHE-rs implements latest findings by Bergerat et al. [START_REF] Bergerat | Parameter optimization & larger precision for (t)fhe[END_REF] (recently separated from the Concrete Library [START_REF]Concrete: State-of-the-art TFHE library for boolean and integer arithmetics[END_REF] that implements higher-level operations and interfaces); FPT [START_REF] Van Beirendonck | FPT: a Fixed-Point Accelerator for Torus Fully Homomorphic Encryption[END_REF]: an experimental FPGA accelerator for TFHE bootstrapping (a benchmark of state-of-the-art implementations in software/GPU/FPGA/ASIC can also be found in [START_REF] Van Beirendonck | FPT: a Fixed-Point Accelerator for Torus Fully Homomorphic Encryption[END_REF]); nuFHE [START_REF] Nucypher | A GPU implementation of fully homomorphic encryption on torus[END_REF]: a GPU implementation of TFHE.

TFHE is also implemented as a part of more generic libraries like OpenFHE [START_REF] Badawi | OpenFHE: Open-source fully homomorphic encryption library[END_REF], which is a successor of PALISADE [START_REF] Palisade | PALISADE Lattice Cryptography Library[END_REF] and which also attempts to incorporate the capabilities of HElib [START_REF]HElib[END_REF] and HEAAN [19]. There exist many other implementations that are not listed here.

Conclusion

We believe that our TFHE guide helps many researchers and developers understand the inner structure of TFHE, in particular probably the most mysterious operation -the negacyclic blindrotate -thanks to a step-by-step explanation, which we support with an illustration. Not only do we provide an intelligible description of each sub-operation of bootstrapping, but we also highlight what tweaks can be put in place to limit the noise growth at little to no additional cost (e.g., the order of key-switch ↔ dot-product or the signed decomposition alphabet). Last but not least, we provide a comprehensive noise analysis, supported by proofs, where we employ an easyto-follow notation of the decomposition operation using g and g -1 . Finally, we list selected implementation remarks that shall be kept in mind when attempting to implement TFHE and its variants or modifications.

eFig. 7

 7 Fig. 7 Noise propagation from a bunch of freshly bootstrapped samples throughout a TFHE gate towards a new, freshly bootstrapped sample. If |emax| < Emax, the bootstrapping function is evaluated correctly.

2 Fig. 8

 28 Fig.8Illustration of type-1 and type-2 errors: LUT evaluates correctly and incorrectly to 0 and 3, respectively.

  Bit-security of LWE as estimated by lattice-estimator by Albrecht et al.[START_REF] Albrecht | contributors: Security Estimates for Lattice Problems[END_REF][START_REF] Albrecht | On the concrete hardness of learning with errors[END_REF] (commit ID f9dc7c), using underlying group size q = 2 64 . Interpolated between grid points. Raw data can be found at https://github.com/fakub/ LWE-Estimates.

		40								576
			. bit-security of LWE					512
		32								448
	-log(α)	24								256 320 384
		16								192
										128
		8								64
		0	256	512	768	1024	1280	1536	1792	2048
					LWE dimension n
	Fig. 3

  ãi • ACC -ACC) 4: end for 5: return ACC Theorem 4 (Correctness & Noise Growth of Blind-Rotate). Given inputs of Algorithm 1, where bootstrapping keys are encrypted with noise parameter α and test vector is (possibly) encrypted with noise parameter α t (i.e., α t = 0 or α), BlindRotate returns the last-step ACC with noise variance given by

Table 1

 1 Summary of parameters' notation. Parameters ε 2 , ε ′2 and V B , V B ′ are derived from respective decomposition parameters; cf. (8) and (9).

	LWE secret key	s	GLWE secret key	z
	LWE dimension	n	GLWE dimension	k

GLWE polyn. degree N LWE noise std-dev α ′ GLWE noise std-dev α KS decomp. base B ′ BK decomp. base B KS decomp. depth d ′ BK decomp. depth d

The result may combine both kinds of errors and decrypt correctly at the same time -in such a case, we consider that both error types occur simultaneously.

Acknowledgments

We would like to thank Melek Önen for her useful comments as well as the anonymous referees for their helpful suggestions.

Funding

This work was supported by the MESRI-BMBF French-German joint project UPCARE (ANR-20-CYAL-0003-01), and by the Grant Agency of CTU in Prague, grant No. SGS21/160/OHK3/3T/13.

Availability of Data and Material

The datasets generated during and/or analyzed during the current study are available in the following repository: https://github.com/fakub/ LWE-Estimates.

Declarations

Conflicts of interest

The authors have no relevant financial or nonfinancial interests to disclose.

Ethical approval

This article does not contain any studies with human participants or animals performed by any of the authors. Given GLWE sample c of µ c ∈ T (N ) [X] under GLWE key z and noise parameter α, and GGSW sample Ā of m A ∈ Z (N ) [X] under the same key and noise parameters, external product returns GLWE sample c′ = Ā c, which holds excess noise e , given by z, c′ = m A • z, c + e , for which it holds

where V z is the variance of individual coefficients of the GLWE key z and other parameters are as per previous definitions. If e and the noise of c are "sufficiently small", c′ encrypts msg z (c ′ ) = m A • µ c , i.e., external product is indeed multiplicatively homomorphic.

Proof. Let us denote c = (b, a) ∈ T (N ) [X] 1+k and let us unfold the construction of Ā as

where

i . Unfolding the construction of Ā and that of external product, we obtain

while in (A3), terms denoted ♦ and ♥ cancel out. Next, in (A4), we assume that each decomposition error term (cf. ( 7)) has a uniform distribution on [-1 /2B d , 1 /2B d ), hence variance of ε 2 ; cf. [START_REF] Guimarães | Revisiting the functional bootstrap in TFHE[END_REF]. Finally, in (A5), we assume that the decomposition digits have a uniform distribution on [-B /2, B /2) ∩ Z, hence their mean of squares equals V B ; cf. [START_REF] Chillotti | Improved Programmable Bootstrapping with Larger Precision and Efficient Arithmetic Circuits for TFHE[END_REF]. Evaluating the variance of each term, the result follows, while ≈ is due to the possible statistical dependency of variables across terms. Note that we indicate the length of inner products in lower indices.

A.2 Proof of Theorem 3

where ε ′2 and V B ′ are as per (8) and (9), respectively, with B ′ and d ′ , V s ′ is the variance of individual coefficients of the LWE key s ′ , and other parameters are as per previous definitions. If e KS and the noise of c′ are "sufficiently small", it holds µ = msg s (c) = msg s ′ (c ′ ), i.e., KeySwitch indeed changes the key, without modifying the message.

Proof. Similar to the proof of Theorem 2, we write

and the result follows.

A.3 Proof of Theorem 4

Theorem 4 (Correctness & Noise Growth of Blind-Rotate). Given inputs of Algorithm 1, where bootstrapping keys are encrypted with noise parameter α and test vector is (possibly) encrypted with noise parameter α t (i.e., α t = 0 or α), BlindRotate returns the last-step ACC with noise variance given by

which we denote by V 0 , other parameters are as per previous theorems and definitions. If the noise of ⟨z, ACC⟩ is "sufficiently small", it holds msg z (ACC) = X m • tv, where m = ⟨s, ( b, ã)⟩ ≈ 2N µ, i.e., BlindRotate indeed "rotates" the test vector by the approximate phase of (b, a), scaled to Z 2N .

Proof. The core of BlindRotate consists of the sample t being gradually externally-multiplied by BK i 's (plus some other additions/multiplications). For i-th step with a := ãi ∈ Z 2N and BK := BK i that encrypts s := s i ∈ {0, 1}, we write:

where (A9) is by Theorem 2 and the step towards (A10) holds for s ∈ {0, 1}. Hence, with each such

Appendix B Tech. Overview

In Figure B1, we provide an exhaustive technical overview of blind-rotate, preceded by modulusswitching and followed by sample-extract.

Blind-Rotate of TFHE

Encrypted bootstrapping function (aka. test vector; assuming k = 1)

blind-rotate 0.s (0) + 0.s (1) X + . . . + 0.s (N -1) X N -1 sample-extract 0.s (0) 0.r (N -1) . . . 0.r (1) 0.r (0)

GLWE sample τ bits 0.v (0) + 0.v (1) X + . . . + 0.v (N -1) X N -1 0.u ( b) + . . . (ACC) 0.r (0) + . . .