CHIMERA: Combining Ring-LWE-based Fully Homomorphic Encryption Schemes

1 Introduction

Homomorphic encryption enables computations on encrypted data without decrypting it. Shortly after the development of the first fully homomorphic encryption (FHE) scheme by Gentry [23], extensive research has been carried out on the design, implementation and cryptanalysis of various other FHE schemes.

Several constructions based on the Ring-LWE problem [26] are today among the most promising FHE candidates, each of them having particular advantages that depend on the type of the target homomorphic operations and arithmetic. More precisely, certain schemes are better for integer arithmetic whereas others have advantages for performing arithmetic with real numbers; some are more suitable for vector operations whereas others perform well in the case of sequential combinatorial operations on individual slots such as the evaluation of Boolean circuits, finite state machines or lookup tables. In addition, different constructions typically tolerate different amounts of noise and hence, homomorphic evaluation of circuits of different multiplicative depth.

It is thus of central importance to be able to use the optimal scheme for each type of operation in a particular computation. This motivates the need for building an efficient hybrid solution combining more than one scheme and switching between these schemes during the individual operations.

This paper proposes such a practical hybrid solution based on efficient switching algorithms for three different Ring-LWE schemes, where each scheme is best suited for certain types of operations: 1) TFHE [18, 19] particularly suitable for combinatorial operations on individual slots and tolerating large noise and thus, large multiplicative depth. 2) B/FV [6, 13, 21] allowing to perform large vectorial arithmetic operations as long as the multiplicative depth of the evaluated circuit remains small; 3) HEAAN [15, 16] - a mixed encryption scheme shown to be very efficient for floating-point computations.

We achieve such a hybrid solution by first mapping the different plaintext spaces of the different schemes to a common algebraic structure using certain natural algebraic homomorphisms. Once such a uniformization of the plaintext spaces has been achieved, we describe our scheme switching algorithms. The main idea here is to replace the expensive bootstrapping algorithms with more efficient key-switching operations. Recall that if 𝓢₁ and 𝓢₂ are two homomorphic encryption schemes then the concept of bootstrapping, originally introduced by Gentry [23], is a homomorphic evaluation (under the scheme 𝓢₂) of the decryption function for the scheme 𝓢₁. Since all Ring-LWE-based FHE decryption functions evaluate an inner product followed by a rounding function and since the rounding function is a step function, instead of first applying the expensive bootstrapping and then evaluating a function f, one can replace the last rounding step in the bootstrapping by a more general step function g that approximates f and use a homomorphic lookup table evaluation. This is essentially the idea of the key-switching algorithms described in Section 2.2 that are later used to achieve a switch between the schemes in Sections 3 and 4. Note that the concept of functional key-switch is not new (it appeared already in the context of TFHE [18] and implicitly in the work of Ducas and Micciancio [20]). Yet, its application to scheme switching presented in this work is novel.

To better explain the algebraic aspects of our approach, we let 𝓡_m denote the quotient ring (ℤ/mℤ)[X]/(X^N + 1) for some integers m and N and we let 𝕋 = ℝ/ℤ be the torus. To introduce the algebraic structure of the plaintext spaces in TFHE, we distinguish two different underlying encryption schemes (an encryption scheme on a ring and a homomorphic one on a module over that ring):

1. TRGSW : encryption scheme on the ring 𝓡 := ℤ[X]/(X^N + 1),

2. TRLWE : HE scheme on the 𝓡-module 𝕋_𝓡 := (ℝ[X]/(X^N+1))/𝓡.

The plaintext space for the scheme TRGSW is the ring 𝓡 whereas its ciphertext space is (𝕋^N)^2ℓ for some integer ℓ that depends on various precision and noise parameters (see Section 2 for details). Elseways, the plaintext space for the scheme TRLWE is the 𝓡-module 𝕋_𝓡 and the ciphertext space is (𝕋^N)² (see Section 2.2 for details as well as for the definition of the external product which is the homomorphic evaluation algorithm for the ring action on the module).

On the other hand, the plaintext space of B/FV is 𝓡_p for some integer p (a prime, a power of 2 or a small number 1 mod 2N, depending on the functionality that we want) and the ciphertext space is Rq2 for some larger integer q. Finally, HEAAN has for message space a ball of radius B in 𝓡_q with respect to a certain ℓ_∞-norm defined in Section 2.4 and its ciphertext space is Rq2.

It is not too hard to verify that in the three cases listed above, the ciphertext spaces share very similar algebraic structures. For B/FV and HEAAN this is trivial to do; for TFHE, it suffices to identify the ciphertext space Rq2 with a subgroup of the torus (𝕋^N)² as follows: using that Rq2 ≃ ((ℤ/qℤ)^N)², we simply identify q⁻¹ ℤ/ℤ ≃ ℤ/qℤ, the latter being the multiplication-by-q isomorphism of ℤ-modules.

Yet, the plaintext spaces are a priori rather different. In order to apply any key-switching technique, one thus needs to uniformize them (i.e., map them to the same algebraic structure). In addition, this algebraic structure should carry a specific metric allowing us to quantify and measure the noise in the decryption function. We achieve this by using the plaintext space of TFHE, namely ℝ[X]/(X^N + 1) modulo ℤ (a space we introduce in Section 2 and denote by 𝕋_𝓡 throughout the paper). We then show how to map both B/FV and HEAAN plaintexts to 𝕋_𝓡 in Sections 3 and 4.

Our hybrid solution has many practical applications. First and foremost, it becomes an integral tool for the recent standardization initiatives of homomorphic schemes and common APIs [8], especially since TFHE, B/FV (Seal) and HEAAN are part of this standardization process.

Then, imagine a scenario where operations on large datasets must be performed and a decision must be taken on the result. The first part would be easier via the B/FV scheme, whereas the decision function can be evaluated faster in TFHE. Therefore, one would like an efficient method to pass from B/FV to TFHE. Similarly, if more approximate computations have to be performed, one would benefit from a scheme switching between HEAAN and TFHE. Another example comes from the recent Idash’18 Track 2 [1] competition on designing homomorphic solutions for semi-parallel Genome Wide Association Studies (GWAS). One of the operations needed for the challenge required to compute homomorphically the product G⁻¹ ⋯ S, for a small 4 × 4 symmetric matrix G and a much larger 4 × 10000 matrix S. In this scenario, the bootstrapping of TFHE can be used to compute the 10 coefficients of G⁻¹ (via either Gaussian elimination or Cholesky factorization), so these algorithms that include loops, inversions and have very high multiplicative depth, benefit from fast bootstrapping on individual data. Then, the matrix multiplication G⁻¹ ⋯ S can be massively vectorized using the SIMD operations of HEAAN. Similarly, different machine learning algorithms use SIMD operations to produce an output vector and at the end, one needs to compute the maximum of its coordinates. Conversely, various financial systems need to perform small computations on an encrypted database with a potentially very large multiplicative depth over a long period of time and at the end of the period provide statistics on the current dataset. In this case, it is essential to operate in bootstrapped mode as in TFHE and then perform the low-depth statistical calculations in B/FV or HEAAN. In such a scenario, it is important to transform TFHE ciphertexts to B/FV or HEAAN ones.

As a byproduct of our analysis of the three above schemes from the perspective of TFHE, we propose the general definition of a FHE module structure, that is, an external product allowing to homomorphically evaluate the action of the ring R on the module M whenever M is equipped with an HE scheme and R is equipped with a FHE scheme. This concept already appears in a particular case in [18] (named as external product), but it can certainly be of independent interest in future research in FHE. For instance, it permits to express the relinearization in the internal products of HEAAN and B/FV in terms of the FHE module structure for TFHE and this without loss as it is the same algorithm.

Figure 1

Bridges between Ring-LWE homomorphic schemes. Plain arrows represent bridges between the different schemes. Dotted arrows represent inclusion. Finally, the spaces P = p and P = X − p are instantiations of P⁻¹𝓡/𝓡.

2 Preliminaries

Let 𝕋 = ℝ/ℤ be the real torus and let 𝓡 = ℤ[X]/(X^N + 1) be the ring of polynomials with integer coefficients modulo X^N + 1. For a ring A (e.g., A = ℤ, ℝ, ℂ), let 𝓡_A := 𝓡 ⊗_ℤA = A[X]/(X^N + 1) be the ring of polynomials modulo X^N + 1 with coefficients in A. In particular, 𝓡 = 𝓡_ℤ, so we interchangeably omit the index.

Let 𝕋_𝓡 = 𝓡_ℝ/𝓡_ℤ (a.k.a ℝ[X] mod X^N + 1 mod ℤ) which we view as an 𝓡-module (it has no ring structure). We often refer to the left action of 𝓡 on 𝕋_𝓡 as an external multiplication with coefficients in 𝓡. Moreover, let 𝓑 be the subset of all polynomials of 𝓡_ℤ with coefficients in {0, 1} (here, we identify 𝓡_ℤ ≃ ℤ^N as ℤ-modules in the natural way). Finally, if x ∈ 𝓡, let 𝓡_x = 𝓡/x 𝓡 and let π_x : 𝓡 → 𝓡_x be the natural surjection.

We use the ℓ_p-distance on the N-dimensional torus 𝕋^N and write ∥x − y∥_p for the distance between two elements x, y ∈ 𝕋. Note that it satisfies ∀ m ∈ ℤ, ∥m ⋯ x∥_p ≤ ∣m∣ ∥x∥_p. For an integer element a ∈ 𝕋_𝓡, consider any representative a(X) = a₀ + … + a_N−1X^N−1 ∈ ℝ[X]. We will (unambiguously) write ∥a∥_p for the norm of the image of (a₀, …, a_N−1) in 𝕋^N.

The notion of Lipschitz function always refers to the ℓ_∞-distance: a function f : 𝕋^m → 𝕋ⁿ is said to be κ-lipschitz if ∥f(x) − f(y)∥_∞ ≤ κ ∥x − y∥_∞ for all inputs x, y, where ∥ ⋯ ∥_∞ is the ℓ-infinity norm.

In this work, we revisit the three scale-invariant families of HE schemes (TFHE in Section 2, B/FV in Section 3 and HEAAN in Section 4), all of them based on the Ring-LWE problem introduced in [26].

More precisely, we present a slightly different interpretation of these schemes through the concept of FHE module structure that provides a more conceptual interpretation of the corresponding homomorphic evaluation of the action of a ring on a module over that ring. More importantly, in the subsequent sections, we realize each of the plaintext spaces of the schemes B/FV, TFHE and HEAAN as subsets of the 𝓡-module 𝕋_𝓡 which enables the scheme-switching algorithms.

2.5 𝕋_𝓡 as the common plaintext algebraic structure

As mentioned earlier, the three homomorphic schemes use nearly the same ciphertext space (up to rescaling by a factor q). In addition, all decryption methods make use of the phase function up to minor differences: b − sa versus b + sa in B/FV or ∑i=0msi⋅ai,s∈R,ai∈TR for various values of m in Seal [13]. Yet, the plaintext spaces are à priori different as they are based on different mathematical structures (groups, rings, intervals, random sets).

In order to exploit the advantages of each scheme, we need to be able to homomorphically switch between the different plaintext spaces, and most importantly, to give a meaningful semantic to these transformations.

The main idea that enables us to give a meaningful semantic to the scheme switching transformation is to interpret all the plaintext spaces as being embedded in the same module 𝕋_𝓡 as shown in Figure 2 and to use the distance function on the torus to quantify the transformation error. In this setting, all schemes use the same ciphertext space TR2, the same key space 𝓑 and the same phase function φ_s(a, b) = b− s ⋯ a. Thus, the probabilistic characterization of the message and error as the expectation and the standard deviation of the TFHE phase, respectively, are automatically extended to all schemes.

Figure 2

Representation of the plaintext space over the 𝕋_𝓡

2.6 Real and complex slots for B/FV, TFHE and HEAAN

In this section we recall the representation of the plaintext spaces of the three schemes via the user slots. This is indeed the representation used in the current implementations.

B/FV

In B/FV, homomorphic operations are performed either on N SIMD slots modulo a medium-size integer p [13, 21], or more recently, on a single big-number slot modulo p^N + 1 [14]. In both cases, the set of these slots has a ring structure and is isomorphic to a quotient of 𝓡_ℤ by a principal ideal (the native plaintext in [14]).

HEAAN

In HEAAN, homomorphic operations are performed on N/2 SIMD slots containing complex numbers in fixed-point representation with the same public exponent and the same precision. By interpolating the complex roots of X^N + 1, the native plaintext can be mapped to small polynomials of 𝕋_𝓡 (i.e., a zero-centered ball of small fixed radius) since the complex DFT matrix is Hermitian. We achieve this in Section 4.

TFHE

Finally, in TFHE, the message space is an arbitrary subset of 𝕋_𝓡, without any particular structure.

Preserving the user slots

In order to introduce the notion of slots (real or complex), we use the following two isomorphisms of ℝ-vector spaces:

RR≃RN,f=a0+⋯+aN−1XN−1↦(a0,…,aN),(1)

and

RR≃CN/2,f↦(f(ζ),f(ζ3),…,f(ζN−1)).(2)

Here ζ = e^πi/N is a primitive root of X^N + 1. Representation (1) corresponds to what is called the coefficient packing and representation (2) corresponds to what is called the slot packing.

The unified native plaintext spaces and the correspondence with the user-space slots are shown in Figure 3.

Figure 3

Unifying the plaintext space in RLWE-schemes. See the following sections for the definition of the notation.

3 A general abstraction of B/FV over the torus

The B/FV scheme is very efficient in evaluating arithmetic circuits (i.e. polynomials on the plaintext). Yet, huge slowdowns are observed when evaluating comparisons, the sign function or other non-linear decision diagrams that do not correspond to sparse low-degree polynomials.

Here, we propose an alternative approach that switches to a different scheme, and for instance, executes the non-arithmetic operation via TFHE’s gate bootstrapping. We explain how to represent the plaintext spaces in order to enable this conversion.

Originally, the construction of B/FV uses 𝓡_p as the plaintext space, where p ≥ 2 is a plaintext modulus. For more flexibility (see, e.g., the B/FV with big numbers below), one can use an arbitrary element P ∈ 𝓡 and take 𝓡_ℤ/P 𝓡_ℤ as the plaintext space.

Following the ideas of [14, 22], given an element P ∈ 𝓡_ℤ that is invertible in 𝓡_ℝ, let 𝓛(P) and 𝓛(P⁻¹) be the real lattices generated by the rows of the matrices associated to P and P⁻¹, respectively. Recall that these are the matrices (with respect to the standard basis {1, X, …, X^N−1}) corresponding to the linear transformation of the ℝ-vector space 𝓡_ℝ that is multiplication by P. The native plaintext space 𝓜 is precisely the subgroup P⁻¹ 𝓡_ℤ/𝓡_ℤ ⊂ 𝓡_ℝ/𝓡_ℤ = 𝕋_𝓡. We then have

where the isomorphism is induced by u ↦ P ⋯ u for u ∈ P⁻¹ 𝓡_ℤ/𝓡_ℤ. Thus, 𝓜 ≃ 𝓡_P. Geometrically, 𝓜 can be thought of as the vectors in the lattice 𝓛(P⁻¹) whose coordinates are taken modulo ℤ. Algebraically, 𝓜 is the P-torsion of the 𝕋_𝓡.

Via this isomorphism, the native plaintext space 𝓜 is equipped with the following internal Mongomery-type product:

Multiplication in B/FV

We will now deploy our definition of an FHE module structure to recover the internal homomorphic product of B/FV in terms of the external product. We view the plaintext space M := 𝓡_P as an R := 𝓡_ℤ-module and let s ∈ 𝓑 ⊂ 𝓡_ℤ be the key.

Given a TRLWE ciphertext c = (a, b) ∈ TR2, we denote by (a͠,b͠) ∈ RZ2 the optimal lift of c to RR2, that is the pair of the unique lifts of c for which all coefficients of a͠ and b͠ are in [−1/2, 1/2). Let (a₁, b₁), (a₂, b₂) ∈ TR2 be two ciphertexts of plaintexts μ₁, μ₂ ∈ 𝓜 ⊂ 𝕋_𝓡. We are searching for a ciphertext (a, b) that is a valid encryption of the product μ₁ ⊠_Pμ₂. Since μ_i = b_i − s ⋯ a_i for i = 1, 2, we can write

We would like to define the internal product (a₁, b₁) ⊠_P (a₂, b₂) as a pair (a, b) with the property that

The important point here is that we would like to find a, b ∈ 𝕋_𝓡 such that

This would have been trivial without the s² term. To deal with the latter, we use an encryption Enc_R(s) =: RK (the relinearization key) and the definition of an FHE module structure to deduce that

To summarize, we get

Alternatively, the term s²a͠₁a͠₂ can also be computed as RK′ ⊡ Enc_M(a͠₁a͠₂) where RK′ = Enc_R(s²).

Letting RK be a relinearization key as above, that is a TRGSW encryption of s with key s (denoted by TRGSW_s(s)), this analysis in the noiseless setting motivates the following definition of a B/FV internal homomorphic product in the presence of noise:

3.1 Bridging B/FV slots with TFHE

In the classical description of B/FV or Seal, P(X) is usually chosen as a constant integer p. In this case, the plaintext space 𝓜 consists in all the multiples of P⁻¹ = p⁻¹ mod (X^N + 1) mod ℤ, which is a rescaling of the classical plaintext space description 𝓡_p (as shown in Figure 4). In particular, if X^N + 1 has N roots modulo p, 𝓜 is isomorphic to N independent integer slots modulo p (else, there are less slots, in extension rings or fields). From a lattice perspective, 𝓜 is viewed as the orthogonal lattice generated by 1/pI_N (I_N is the N × N identity matrices). The packing radius of 𝓜 is 1/2p which is the maximal error tolerable by the phase. Rounding an element to 𝓜 consists of rounding each coordinate independently to the nearest multiple of 1/p.

Figure 4

The B/FV plaintext space over the 𝕋_𝓡

In the literature, the isomorphism used to obtain the slot representation is

p−1RZ/RZ≃Rp≃(Z/pZ)N,μ↦(μ(r0),…,μ(rN−1)).(5)

Here, one assumes that the polynomial X^N + 1 mod p factorizes into distinct linear factors X − r₀, …, X − r_N−1 (i.e., it has N distinct roots r₀, …, r_N−1 mod p). This isomorphism allows to manipulate N independent slots in parallel. Typical values are N = 2¹⁵ and p = 2¹⁶ + 1 (allowing a very small noise α ≈ 2⁻⁸⁸⁶ according to [8], so a multiplicative depth of ≈ 28 without key-switch according to the propagation of Lemma 1).

If we identify a polynomial in 𝓡_p with its coefficient vector in (ℤ/pℤ)^N, the bijection between the coefficients and the slot then corresponds to the Vandermonde matrix of (r₀, …, r_N−1) mod p

VDM=1r01⋯r0N−11r11⋯r1N−1⋮⋮⋯⋮1rN−11⋯rN−1N−1modp.(6)

3.1.1 B/FV → TFHE

In this section we show how B/FV ciphertexts, interpreted as TRLWE ciphertexts with plaintext (slots in) 𝓡_p, can be transformed into k independent TLWE ciphertexts.

Let z = (z₀, …, z_N−1) ∈ (ℤ/pℤ)^N be a B/FV plaintext and, as in the previous section, let p⁻¹ 𝓡_ℤ/𝓡_ℤ ≃ (ℤ/pℤ)^N be the identification (5) and let μ ∈ p⁻¹ 𝓡_ℤ/𝓡_ℤ ⊂ 𝕋_𝓡 be the preimage of z. More generally, suppose that we start with a ℤ-module homomorphism f : (ℤ/pℤ)^N → (ℤ/pℤ)^N with a matrix F ∈ 𝓜_N(ℤ), where 𝓜_N(ℤ) is the class of integer N × N matrices (this could arise in practice as either a projection, extraction or permutation of the slots) and get the output f(z) as a polynomial ∑i=0N−1μi′Xi ∈ p⁻¹ 𝓡_ℤ/𝓡_ℤ where^[2]μ′ := (μ0′,…,μN−1′)=1pf(z0,…,zN−1) mod ℤ.

Then, by definition, we have μ′ = (F⋯VDM)μ mod ℤ, where F ⋯ VDM can be any integer representative of F ⋯ VDMmod p. In particular, we can always take the representative with all coefficients in [−p/2, p/2). This is a (Np/2)-Lipschitz ℤ-module homomorphism, and can be evaluated via the functional key-switch of Theorem 2 (see Algorithm 1). Coefficients can then be homomorphically extracted as individual TLWE ciphertexts with the SampleExtract of TFHE.

Algorithm 1

Public Functional Switching B/FV to TFHE

Input:TRLWE ciphertext c(X) = (a(X), b(X)) encoding N slots (z0, …, zN−1)mod p with key K ∈ 𝓑, a public ℤ-module homomorphism f : (ℤ/pℤ)N → (ℤ/pℤ)N with matrix F ∈ 𝓜N(ℤ), and key switch key KSi,j ∈ TRLWES(Ki2j), where S ∈ 𝓑.

Output: a TRLWE ciphertext c′ ∈ TR2 encrypted with key S ∈ 𝓑 whose message is ∑i=0N−1μi′Xi where (μ0′,…,μN−1′)=1pf(z0,…,zN−1)

1: F′ = F ⋯ VDM mod p (all coefficients lifted in [−p/2, p/2))

2: Compute B = F′(b(X)) ∈ 𝕋N

3: fori ∈ 0 → N − 1 do do

4:     Compute Ai = F′(Xia(X)) = A ∈ 𝕋N

5:     Decompose Ai=∑j=0lAi,j⋅2−j with Ai,j ∈ 𝔹N

6: end for

7: return(0,B)−∑i=0N−1∑j=0lAi,j⋅KSi,j

Proposition 2

(B/FV slots → TFHE) Letc = (a, b) ∈ TR2be a TRLWE ciphertext encryptingNslots (z₀, …, z_N−1) mod pwith keyK ∈ 𝓑, letf : (ℤ/pℤ)^N → (ℤ/pℤ)^Nbe a public ℤ-module homomorphism with matrixF ∈ 𝓜_N(ℤ). LetKS_i,j ∈ TRLWE_S,α(K_i/2^j) be a key switching key (0 ≤ i < N, 1 ≤ j < log₂α) andK_iis thei-th coefficient ofK. By applying the functional key-switch ofTheorem 2using the integer transformationF ⋯ VDM mod pwhose coefficients are between [−p/2, p/2) and we obtain a TRLWE ciphertextc′ ∈ 𝕋_𝓡encrypted with keyS ∈ 𝓑 whose message is∑i=0N−1μi′Xiwhere(μ0′,…,μN−1′)=1pf(z0,…,zN−1). The noise variance satisfies

Var(Err(c′))≤Np22Var(Err(c))+α2ℓN2+N4.

3.1.2 TFHE → B/FV

Conversely, we would like to transform k independent TLWE ciphertexts (encryptions of messages (μ₀, …, μ_k−1) ∈ 𝕋^k) into a TRLWE ciphertext with slots in ℤ/pℤ. Again, we will need to define a Lipschitz ℤ-module homomorphism g : 𝕋^k → (ℤ/pℤ)^N. Unfortunately, since for all x ∈ 𝕋^k there exists y ∈ 𝕋 such that x = p ⋯ y, we have g(x) = p ⋯ g(y) = 0 in (ℤ/pℤ)^N and this implies that g is zero everywhere, which is of limited interest.

Therefore, we need to restrict the message space only to multiples of 1/p (this prevents division by p). Such a plaintext space restriction may imply that input TLWE ciphertexts must be bootstrapped before exporting them as B/FV slots using gate bootstrapping from Theorem 3. Note that B/FV manages with a noise that is smaller than in the TFHE. Therefore for this transformation, it is not enough to only switch between different ciphertexts types, but also to decrease the noise. Also the bootstrapping of the input permits to map the plaintext space to the space composed of exact multiples of 1/p.

Then, let g : (ℤ/pℤ)^k → (ℤ/pℤ)^N be a ℤ-linear map whose matrix G is in 𝓜_N,k(ℤ). To obtain a B/FV ciphertext whose slots are g(pμ₀ mod p, …, pμ_k−1 mod p), the actual transformation to apply is VDM⁻¹ ⋯ G mod p (see Algorithm 2). Again, we can choose the representative with coefficients in [−p/2,p/2) which is (Np/2)-Lipschitz.

Algorithm 2

Public Functional Switching TFHE to B/FV

Input:k < N TLWE ciphertexts (ai, bi) encoding μi ∈ 𝓜N,k(ℤ) with key S ∈ 𝔹n, a public (Np/2)-Lipschitz ℤ-module morphism g : (ℤ/pℤ)k → (ℤ/pℤ)N, whose matrix G ∈ 𝓜N,k(ℤ) and KSi = TRGSWK (Si) with K ∈ 𝓑 and 1 ≤ i ≤ n.

Output: a B/FV ciphertext (a(X),b(X)) encoding a plaintext with slots are g(pμ0 mod p, …, pμk−1 mod p), with key K ∈ 𝓑

1: G′ = VDM−1 × G mod p (all coefficients lifted in [−p/2, p/2))

2: Compute B = G′(b0,…, bk) ∈ 𝕋𝓡

3: fori ∈ 0 → N − 1 do do

4:     Compute A[i] = G′( a0[i], …, ak[i]) ∈ 𝕋𝓡

5: end for

6: return(0,B)−∑i=0N−1KSi⊡(0,A[i])

Bootstrapping in B/FV

If we want to decrease the noise of the output, different possibilities for the algorithm of bootstrapping exist in the literature [12, 21]. The first one is the naive bootstrapping, where we evaluate the rounding function. In this case for p > 2N + 1 prime (p = 1 mod N), we need O(p) internal products for the evaluation and we preserve the N slots. The second one is the bootstrapping proposed in [12], where p = r^e is a power of a prime number, and we need only (e − 1)(r − 1) multiplications, but the number of slots is reduced.

Non-linear functions in B/FV

In B/FV, an arbitrary function f : ℤ/pℤ → ℤ/pℤ, for a prime p, can be interpolated by a polynomial of degree ≤ p − 1 (by Lagrange interpolation) and can thus be evaluated as an arithmetic circuit of multiplicative depth 2log₂p. The evaluation of the polynomial is performed simultaneously on the N slots. If the function f is viewed as a function f : 𝕋 → 𝕋, both the domain and the range are in this case rounded to exact multiples of 1/p. Compared to TFHE, the output is constrained in the subset p⁻¹ ℤ/ℤ (e.g., only to multiples of 1/p), but on the other hand, there is no negacyclic constraint on the input, so the graph of the non-linear function can be arbitrary everywhere. However, except in very special circumstances, the polynomial to evaluate is dense, so the number of homomorphic operations is Θ(p) which is impractical for large p’s and thus, the method does not apply to big-number slots. One notable exception to this rule is the bootstrapping in [12] modulo p^k, which proves that the rounding function is the composition of sparse polynomials.

4 A general abstraction of HEAAN over the torus

For HEAAN, the homomorpic encryption scheme of approximate numbers, the idea is that instead of correcting the error during the decryption for the sake of increased noise, one keeps the approximation error and thus, reduces the noise. In this scheme only the significant digits are used and the phase is taken as a good approximation of the plaintext. HEAAN is a mixed encryption scheme dedicated to fixed-point arithmetic with public exponent. Similarly to scale invariant schemes, the noise is appended to the least significant bits of the phase, but unlike B/FV, the space of valid messages is a small bounded interval rather than evenly-distributed in the whole space. Also, the maximal amount of noise is interpreted in terms of the ratio between the diameter of the message space and the scale modulus q rather than the usual noise amplitude versus packing radius. As we keep performing homomorphic operations, the message space diameter increases until the majority of the space is covered at this point, the scale invariance property enables to extract the message as a classical LWE sample that can be processed, for instance, by TFHE. To fully enable this switch between schemes, it is necessary to relate the message spaces of HEAAN and TFHE.

Tags of ciphertexts

To do this, we revisit the representation of HEAAN ciphertexts by adding the following three tags/parameters that we define and clarify below:

1. L ∈ ℕ: level exponent of the ciphertext - overall, it quantifies the maximum amount of homomorphic operations before performing a bootstrapping (the native plaintext ∥μ∥_∞ ≤ 2^−L),

2. ρ ∈ ℕ: bits of precision of the plaintext, that is, the number of bits in the mantissa. Since it is a global constant, we omit it in general.

3. τ ∈ ℤ: slot exponent (order of magnitude of the complex values in each slot). Here, we use floating-point representation for which the exponent is public and fixed across all the coordinates of the vector and only the mantissas are secret. More precisely, a complex number z is represented as z = m ⋯ 2^τ where τ is public and m ∈ 2^−ρ ⋯ (ℤ + i ℤ) with 0 ≤ ∣m∣ < 1.

In Figure 5, we show the plaintext space (with the rounding error) using the tags defined before.

Figure 5

The HEAAN plaintext space over the 𝕋_𝓡, where the error ε is an approximation error of the same order as α = 2^−(L+ρ).

More precisely, L is needed since HEAAN can be viewed as an instantiation of TRLWE whose native plaintext space is the subset of all polynomials μ ∈ 𝕋_𝓡 of small norm ∥μ∥_∞ ≤ 2^−L. The integer L > 0 is the level exponent of the ciphertext, it is public and decreases with each multiplication. When the level is too low, the ciphertext must be bootstrapped to allow further processing.

The plaintext space is always described with a global and fixed number ρ of significant bits. One can define the noise amplitudeα := 2^−(L+ρ). Finally, since the goal is to represent ρ-bit fixed-point values of any order of magnitude, each ciphertext carries a public integer exponent τ ∈ ℤ which represents the order of magnitude of its slots.

We choose these three tags because they are helpful for the parameter selection of the cryptosystem (N and α) from the user point of view. For that, the first step is to fix ρ, the precision needed at the end of the algorithm, the second step is to determine the range of each variable (so the slot exponents τ): this can be done either from the domain of the evaluated function or experimentally by running the algorithm on a fake data. Then, using the noise propagation formula for elementary operations given in this section, we compute the smallest level exponent L > 1 for each variable by traversing the arithmetic graph of the algorithm. Finally, we use the security API document [8] (or the LWE estimator) to find the smallest key size N that supports a noise rate α = 2^−(L+ρ) to the desired security parameter.^[3] The original HEAAN choice of tags is inherent and to determine the final system parameters, we have to solve a complex system of equations.

Complex-valued slots for plaintexts

Recall that N is always a power of 2. Given a message μ ∈ 𝓡_ℝ where ∥μ∥_∞ ≤ 2^−L, its complex slots (z₁, …, z_N/2) are defined as the (rescaled) evaluation on the complex roots of X^N + 1, so z_k = 2^L+τμ(ζ_k) ∈ ℂ. We omit the values on the last N/2 roots as they are complex conjugates of the first ones since μ is real. If ∥μ∥_∞ ≈ 2^−L, this indeed implies that slot values |zk|≈N2τ and that the slot precision is up to 2^τ−ρ.

In order to unify the message spaces, we redefine tagged HEAAN ciphertexts as a quadruple (a, b, τ, L) ∈ TR2 × ℤ × ℕ where (a, b) is a TRLWE ciphertext. As usual, the phase of a ciphertext is (b − s ⋯ a) ∈ 𝕋_𝓡 and the message is the expectation of the phase. The slots of a ciphertext are the slots of its message μ ∈ 𝕋_𝓡 represented by a lift in 𝓡_ℝ of small real norm ≤ 2^−L. From a matrix point of view, the transformation between the coefficients and the slots is the multiplication with 2^τ+L times the complex DFT matrix of ζ_k. We have (z₁, …, z_N/2) = DFT ⋯ (μ₀, …, μ_N−1) and (μ₀, …, μ_N−1) = 2Re(IDFT ⋯ (z₁, …, z_N/2)).

4.2 Non-linear functions in HEAAN

In HEAAN, non-linear functions can be evaluated via approximations by either complex-valued polynomials (via traditional products) or trigonometric polynomials (Fourier approach within the bootstrapping).

As explained in [4], Fourier series of smooth and regular functions converge rapidly: for instance, the Fourier series of a C^∞-function converges super-algebraically and if one smooths any periodic function by convolution with a small Gaussian, its Fourier series converges exponentially fast. However, the convergence is slower if the function has discontinuities (pointwise convergence in Ω(1/k)), or discontinuities in its derivative (uniform convergence in Ω(1/k²)) where k is the number of harmonics used in the series.

Compared to classical approximations of functions by polynomials in [10, 24] (i.e. Taylor series or Weierstrass approximation theorem), Fourier series have three main advantages: they do not diverge to ∞ outside of the interval (better numerical stability), the Fourier coefficients are small (square integrable), and the series converge uniformly to the function on any interval that does not contain any discontinuity in the derivative.

With this bootstrapping trick, HEAAN can at the same time evaluate a non-linear function and bootstrap its output to a level L even higher than its input. Taking this fact into account, instead of writing ReLU(x) = max(0, x) as 12(∣x∣ + x) like in TFHE, where the term +x/2 is not bootstrapped, it is actually better to extend the graph of ReLU from a half period (−1/4, 1/4) directly to a 1-periodic continuous function and to decompose the whole graph as a Fourier series. In the latter case, the output level L can be freely set to an arbitrary large value. Figure 6 shows a degree-7 approximation of the odd-even periodic extension of the graph of ReLU(x).

Figure 6

ReLU for HEAAN

5 Implementation of some major components of Chimera

Some of the algorithms presented in this paper have been implemented and tested in the context of an IDash 2018 [1] submission described in [9]. This submission was selected in October 2018 to be among the finalists of the competition.

Since the challenge was mostly about real-valued algorithms, we implemented the TFHE/HEAAN bridges, and we left the implementation of the TFHE-B/FV bridges as a future work. In the implementation, torus arithmetic is represented either by double-precision floats (for α ≥ 2⁻⁵²), or by a fixed-size array of 64-bit gmp limbs, and polynomial multiplications are implemented via the complex FFT. Since the total precision required was always lower than 128 bits for external products and 192 bits for internal products (so at most two or three gmp limbs), there was no advantage in switching to an alternative RNS/NTT representation. All bit-decompositions for the TRGSW external products (also used in the internal product) have been carried-on in base 2¹⁶ and 2³² rather than in base 2. The implemented algorithms are:

1. Evaluation of a sigmoid on a TLWE ciphertext via gate bootstrapping followed by a functional key-switch to HEAAN (noise reduction from (α = 2⁻⁷, N = 650) to (α = 2⁻⁸⁰, N = 4096)). The time for the evaluation of the bootstrapped sigmoid is: 32s for the bootstrapping to TLWE and 7s for the public key-switch TLWE to TRLWE.

2. External product to multiply a HEAAN ciphertext by a fresh TRGSW ciphertext, using both the slot packed ciphertexts (N/2 slots) and coefficient-packed ciphertexts (N slots). The time is 80ms with parameters α = 2⁻⁸⁰, N = 4096.

3. TRLWE internal product for HEAAN slotwise multiplication, using the tagging system proposed here, and relinearization via the external product formula. The time is 160$ms for parameters α = 2⁻⁸⁰, N = 4096.

4. Evaluation of the non-linear function log ∣x∣ on 1024 slots in parallel during the bootstrapping for HEAAN (Algorithm 4), versus the traditional bootstrapping followed by a Taylor approximation.

The implementation of the algorithms described in this section is now public and available at: https://github.com/DPPH/chimera-iDash2018. Other directions that we leave as a future work is the elaboration of a bridge towards the BGV scheme as well as the introduction of RNS in this framework. The presented framework has already been applied to some concrete use-cases in the domain of machine-learning [5, 9] but we are wishing to provide more applications in this or other directions. The remaining bridges will be implemented when specific use cases are identified for them.

Conclusion

Some recent works introduce alternatives to the methods presented in this article. In [17], the authors propose a new method for the evaluation of the sign function by staying in the HEAAN encoding by multiple compositions of polynomials. This extends to the evaluation of the RELU function and can be very efficient in amortized running time. This SIMD sign evaluation, can be viewed as a bootstrapping for BFV via HEAAN, which is not covered in this work.

Furthermore, in [11], an alternative method for switching between RLWE ciphertexts is presented. This is an orthogonal direction to ours and uses composition with Galois polynomials. In this work, the authors obtain speed-up by one order of magnitude in particular on the LWE-RLWE conversion. As a counterpart the noise overhead is no longer additive since the phase is multiplied by a power of 2. This method can speed-up the Chimera framework by replacing some of the underlying KS methods.