Flattening NTRU for Evaluation Key Free Homomorphic Encryption

1 Introduction

The notion of fully homomorphic encryption (FHE) scheme stayed as an open question for a few decades since its introduction by Rivest et al. [23]. In 2009 the first working FHE scheme was constructed by Gentry [11, 12]. However, the proposed scheme was lacking in performance and it was not possible to implement anything practical. For instance, its most crucial operation called bootstrapping, which is used to restore the noise in ciphertext to an acceptable level, was taking 30 seconds in this very first implementation. After the introduction of the first FHE scheme, we witnessed the introduction of many new FHE constructions aimed at bringing FHE closer to real-world applications and with fewer assumptions. Several integer-based constructions and learning with error (LWE)-based constructions may be found in [7, 8, 27] and in [5, 13, 14], respectively.

These recent constructions brought along an impressive array of optimization techniques that can compete with the expensive bootstrapping operation. Such one scheme, which is based on LWE, was constructed by Brakerski, Gentry and Vaikuntanathan (BGV) [4]. The scheme uses a method called modulus switching to mitigate noise growth in ciphertexts. Another leveled FHE scheme was presented by López-Alt, Tromer, Vaikuntanathan (LTV) in [20]. Their scheme is based on a variant of NTRU [16] constructed earlier by Stehlé and Steinfeld [25]. The authors introduced a new key switching technique called relinearization.

The NTRU variant in [25] was later modified and implemented by Bos et al. in [2]. They adopt the tensor product technique in [3] and achieved a scale-invariant scheme with limited noise growth on homomorphic operations. Also, with the use of the tensor product technique the authors managed to improve the security of the LTV scheme [20] by using much higher levels of noise and thereby remove the Decisional Small Polynomial Ratio (DSPR) assumption. Instead the scheme relies only on the standard lattice reductions as in [25]. However, as the authors also note, the YASHE scheme brings in large evaluation key and complicated key switching procedure. Specifically, the size of the evaluation keys are ℓw,q3 in which q is modulus, w is radix and ℓ = ⌊ log q⌋. In [2] the authors introduce a modification (YASHE’) to their scheme to eliminate the problems of expensive tensor product calculations and large evaluation keys. However, this modification re-introduces the DSPR assumption due to increase in noise.

Motivated by the complex noise management techniques, e.g. relinearization, modulus switching, bootstrapping, of the earlier FHE schemes Gentry, Sahai and Waters [15] proposed a new scheme based on the approximate eigenvector problem. The system uses matrix additions and multiplications which makes it asymptotically faster. At first, they define the GSW scheme as a somewhat homomorphic scheme since for a depth L circuit with B-bounded parameters the noise grows with a double exponential B^2L. To convert the scheme into a leveled FHE, they introduce a Flatten operation which decomposes the ciphertext entries into bits. The secret key is also kept in a special powers of two form. With these modifications, the noise performance is improved greatly. For a depth L circuit with B-bounded secret key entries and 1-bounded (flattened) ciphertexts, the error magnitude is at most (N + 1)^LB for N = log(q)(n + 1). However, ciphertexts still take a considerable space Θ(n²log(q)²) and as noted by GSW [15] the scheme may not be as efficient as existing leveled schemes in practice.

The Subfield Lattice Attack. To overcome the efficiency bottleneck of FHE numerous optimizations along with customized selections of parameters have been proposed in the literature, e.g. special form lattice dimensions and moduli permitting efficient number theoretical transforms and batching, assumptions regarding the distributions of noise and parameters, etc. On the downside many of these assumptions are still open to debate from a security point of view. A very recent work by Albrecht, Bai and Ducas [22] painfully demonstrated this fact. The authors exploit the presence of a subfield to solve the NTRU problem for large moduli q and show that when the NTRU parameters are chosen poorly then the DSPR problem is not as hard as believed thereby invalidating the underlying security assumption in LTV [9, 20] and YASHE’ [2]. Thus, the asymptotic security of both schemes is significantly reduced. Furthermore, very recently Kirchner and Fouque in [17] proposed a variant of the subfield attack of Albrecht et. al. [22]. What is striking is that the authors are able to recover functional versions of secret keys for a wide array of instances of NTRU-based FHE implementations that use short keys, e.g. YASHE [2] and LTV-based FHE [9] even for instances with Hermite factors of 1.0058. The authors conclude that the only proven way to secure the NTRU is to use the parameters in Stehlé and Steinfeld’s NTRU variant [25], i.e. σ = 𝓞(q).

Our Contribution. In this work, we present a new leveled FHE scheme F-NTRU that is based on the Stehlé and Steinfeld variant of NTRU [25] and adopts Flattening – the noise management technique introduced in (GSW) [15]. In a nutshell, we are able to achieve the best of both implementations in [2], i.e. elimination of expensive evaluation keys and reduction of security assumptions. Specifically,

1. We introduce the first NTRU based FHE implementation that uses the Flattening method of GSW. Our scheme uses the encryption methods of NTRU for ciphertext creation, converts them into a matrix structure and makes use of the Flattening noise management technique.

2. Our scheme uses a wide key distribution σ=2nlog⁡(8nq)⋅q1/2+ϵ and hence only relies on standard lattice reductions as in [25] (no DSPR assumption). Thus, our scheme is immune to the Subfield Lattice Attacks by Albrecht, Bai and Ducas [22] and Kirchner and Fouque [17].

3. By employing Flattening, we are able to multiply ciphertexts with only linear increase in the size of the noise level. Our scheme does not use any expensive noise reduction techniques such as relinearization and does not require prohibitively large evaluation keys.

4. Our construction does not require evaluation keys. In contrast, YASHE evaluation keys grow as 𝓞̃ (L⁴) where L represents the evaluation depth. This makes it impossible to use YASHE in deep evaluations.

5. Using the noise asymmetry property of our scheme, we are able to provide small parameters which results in fast homomorphic multiplications in range of milliseconds even for large multiplicative levels, e.g. 76 msec for L = 30.

6. Finally, via a simple polynomial to integer mapping our scheme becomes able to support homomorphic integer arithmetic. We present noise analysis in this case as well. Featuring a very large message space, the integer version of F-NTRU is capable to support a wide range of applications where such arithmetic is required.

2 Overview of NTRU Based FHE Schemes and GSW

We briefly summarize the NTRU based FHE Schemes and the GSW scheme that is relevant to our construction in Appendix A.

3 Our proposal: F-NTRU Scheme

Here we propose a new scheme called F-NTRU that shares the goals of the GSW construction [15], i.e. no evaluation keys, no expensive relinearization operations, no modulus switching and simple homomorphic additions and multiplications. To this end we adopt the flattening approach of [15] and apply it to the NTRU variant, i.e. NTRU′, by Stehlé and Steinfeld [25].

Preliminaries. We work in R_q = ℤ_q[x]/〈xⁿ + 1〉. We adapt two functions from [15] to work in the polynomial setting as follows:

1. Bit-Decomposition: The BitDecomp function takes a ciphertext polynomial c(x) and splits them into binary polynomials and forms a vector as:

   c→(x)=BitDecomp(c(x))=[cℓ−1(x)cℓ−2(x)…c0(x)].

   Here a polynomial c_i(x) with index i represents the binary polynomial that is formed using the i^th bit index of the coefficients of c(x). One may easily reconstruct the ciphertext c(x) by simply computing:

   c(x)=∑i=0ℓ−12i⋅ci(x)∈Rq.

   Note that when we are computing BitDecomp⁻¹, the elements in the vector do not necessarily have to be binary polynomials. It is possible that polynomials can contain coefficients that are not bits.

2. Flatten: When we are performing arithmetic operations, i.e. addition and multiplication, in our scheme, the elements of a flattened ciphertext vector lose their binary form. These extra bits in the coefficients of the polynomials cause additional noise in subsequent arithmetic operations. To prevent this, we use Flatten. Flatten restructures all the elements of the ciphertext vector into binary polynomials. We evaluate the Flatten operation as follows:

   Flattenc→(x)=BitDecompBitDecomp−1c→(x).

   Here in the equation BitDecomp⁻¹ converts the ciphertext vector into a full ciphertext polynomial in R_q. Later, using BitDecomp we convert the ciphertext into a binary polynomial vector again. Basically, this method carries over the extra bits of an element in the vector from least significant to most significant and performs a modular reduction using q to prevent overflow in the overall scheme.

The F-NTRU Scheme. The primitive operations of F-NTRU are defined as follows:

1. KeyGen: We use the key generation method of NTRU′ to select our parameters. For a security parameter λ, we choose our message modulus as 2, modulus q = q(λ), polynomial degree n = n(λ) where n is power of 2. Also we set Gaussian distributions χ_err = χ_err(λ) and χ_key = χ_key(λ). Sample g, f′ ∈ χ_key and set public key h = 2gf⁻¹ and secret key f = 2f′ + 1.

2. Encrypt: In order to encrypt a message μ, we create a vector with length ℓ = log q. Later, we fill the elements with encryptions of zeros using the NTRU′ scheme:

   c→  =  {Encℓ−1(0),Encℓ−2(0),…,Enc0(0)}={cℓ−1,cℓ−2,…,c0},

   where Enc_i(0) = hs_i + 2e_i + 0. We call this the ciphertext vector. We take the transpose of the vector to list the elements in row and apply BitDecomp to the ciphertexts to turn the vector into a ℓ × ℓ matrix:

   c=BitDecomp(c→⊤)

   Then, we use the matrix to encrypt a message μ by evaluating:

   C=Flatten(Iℓ⋅μ+c).

   Here, in the equation I_ℓ is identity matrix with size ℓ.

3. Decrypt: To decrypt the message we take the first row of the matrix and apply Inverse-Bit-Decomposition to form a NTRU’ ciphertext:

   BitDecomp−1{c(0,ℓ−1),c(0,ℓ−2),…,c(0,1),c(0,0)}=c0.

   Once the NTRU’ ciphertext is constructed, we are able to decrypt the message using the secret key f for the NTRU’ scheme as ⌊c₀f⌉ mod 2 = μ.

4. Eval. The homomorphic XOR and AND operations are simply computed as matrix addition and multiplication operations, respectively followed by a Flatten operation, i.e.

   C′=Flatten(C+C~)   ,   C′=Flatten(C⋅C~).

We show; how the correctness of homomorphic circuit evaluation are preserved in Appendix B, and the optimization techniques that are implemented in Appendix C.

4 Security Analysis

Our scheme uses the NTRU’ encryption scheme adopted from [25]. In F-NTRU, an attacker has access only to a ciphertext vector which holds NTRU’ ciphertexts built with fresh encryptions of zero. Therefore as long as NTRU’ ciphertexts are secure, our scheme is also secure. According to the Stehlé and Steinfeld [25], their scheme is IND-CPA secure under the hardness of R-LWE assumption as long as the error has a wide distribution 𝔻_ℤⁿ,σ, i.e. σ > q ⋅ poly(n). However, in the DHS and YASHE’ schemes such a high noise instantiations are not possible due to the noise growth in homomorphic multiplications. Therefore, both schemes use narrow error distributions and additionally assume hardness of the Decisional Small Polynomial Ratio (DSPR) Problem along with the R-LWE assumption.

Fortunately, our scheme has a better control on noise management. The (size of the) noise increases linearly with the multiplicative depth. Therefore, we are able to use a wide error distribution and achieve IND-CPA security as in the original scheme by Stehlé and Steinfeld in [25]. Thus the standard deviation σ_key of the discrete Gaussian distribution 𝔻_ℤⁿ,σkey needs to be set as:

for ϵ > 0. In this setting we are able to generate a public key h = g/f, i.e. g ∈ χ_key and f′ ∈ χ_key (f = 2f + 1) in which χ_key is truncated 𝔻_ℤⁿ,σkey, that is indistinguishable from a uniformly random distribution. The ϵ is evaluated by using the statistical distance Δ between the uniformly random distribution and the Gaussian distributed selected polynomials:

For R-LWE security we follow the settings in [20]. The noise parameters s and e are sampled from the distribution χ_err, a truncated Gaussian distribution 𝔻_ℤⁿ,σerr. The standard deviation σ_err of the error distribution has the following bound σ_err > nlog(n). With this bound, we are able to add noise to our public key and keep it computationally indistinguishable from random uniform distribution.

As above mentioned, the distributions χ_key and χ_err are truncated Gaussian distributions. They are also defined as B-bounded^[1] distributions which means the samples are selected from [−B, B]. The bound value B is selected as a function of the advantage ϵ in a distinguishing attack, e.g. ϵ = 2⁻¹²⁸. The function, e.g. see [10], gives for a sample x ∈ χ the probability of x being larger than k ⋅ σ for a factor k is:

Using the equation above, we select the factor k as k(ϵ) = min{k|erf(k/2) < ϵ}, and select the B-bound as B = k(ϵ) ⋅ σ.

Hermite Factor. The existing attacks rely on the lattice reduction algorithms and the best attack known in practice is BKZ 2.0 [6] by Chen and Nguyen. The quality of the security is measured by Hermite factor δ. A recent work by van de Pol and Smart [26] shows that a fixed Hermite factor for all the lattice dimensions is not true. They show that it is possible to reduce the lattice dimension by selecting a larger Hermite factor for the same security level by utilizing the work of Chen and Nguyen in [6]. Later, a similar approach is followed by Lepoint and Naehrig [19]. They used a quadratic function to interpolate the enumeration costs in [6] and compute the Hermite factors for a wide range of lattice dimensions. This results in Hermite factors that are more precise for the required security levels. Furthermore, they also derive the following condition on q

where α=−log⁡(ϵ)/π. Using this equation and the Hermite factor values in [19] we estimate the required n and q pairs for the security levels λ = {80, 128} in Section 7.

5 Noise Analysis

In this section we analyze the noise performance of our scheme with homomorphic evaluations. In case of a homomorphic addition, the noise increases only a small percent compared to homomorphic multiplication. In our analysis we want to determine the depth of the circuit we can evaluate and still decrypt correctly with growing noise. This analysis includes average case and worst case scenarios for homomorphic multiplication that estimates the number of possible multiplicative levels. Since additions contribute minimally to noise growth we focus only on homomorphic multiplications.

For an element a ∈ ℝ we define the Euclidean norm ||a||=∑ai2 and the infinity norm ∥a∥_∞ = max|a_i| for all possible values of i. In multiplication, we can bound the noise growth with the aid of the following Lemma.

Recursive Evaluation. We assume the evaluation circuit is arranged into a tree with levels of parallel multiplication gates that accept as input the output ciphertexts from the previous level. Lets denote a ciphertext matrix that is at a certain multiplicative level i as C⁽ⁱ⁾. Then, a ciphertext matrix at a multiplicative level C⁽ⁱ⁾ = C⁽ⁱ⁻¹⁾ ⋅ C̃⁽ⁱ⁻¹⁾. Lets recall that these ciphertext matrices are actually NTRU’ ciphertext vectors with BitDecomp applied. We also denote the ciphertexts in the vector for multiplicative level i and row index j as cj(i).

In the first multiplicative level, i.e. i = 0, ciphertext vectors are fresh encryptions with security parameters explained in Section 4. Basically, we have samples g, f′ ∈ χ_key and s, e ∈ χ_err and ciphertexts cj(0) = hs_j + 2e_j + 2^jμ where μ is the message, f = 2f′ + 1 and h = 2 gf⁻¹ is public key. The equation can be written with level index to show the result of a multiplicative level as:

By taking advantage of noise asymmetry and using single bit encryption, the noise is formulated as

for μ, μ̃ ∈ {0, 1}, the noise bounds B_i, B_keyB_err. The details of the noise analysis is in Appendix D

Circuit Evaluation. The single bit encryption gives an advantage for scalable computation. In order to maintain the message bit values as 0 or 1, the gates sohuld be implemented in such a way to preserve the structure. The implementation details are in Appendix E.

6 Complexity

In Table 1 we summarize the asymptotic complexities of F-NTRU and YASHE schemes. We use ℓ = (log q)/ω for radix size 2^ω. Note that our scheme does not require evaluation keys, but the ciphertexts consist of ℓ polynomials. After circuit evaluations the ℓ polynomials are reduced to a single polynomial ciphertext. On the other hand YASHE requires ℓ³ polynomials for evaluation keys. For homomorphic AND evaluation our scheme requires ℓ² polynomial multiplications or using the one sided AND evaluation it uses ℓ polynomial multiplications. In case of YASHE, the scheme uses ℓ² polynomial multiplications followed by a costly key switching operation computed via ℓ³ polynomial multiplications.

7 Parameter Selection

In our choice of parameters we aimed for 80-bit and 128-bit security levels. For comparison, we also tabulated parameter choices for selected depths for F-NTRU and YASHE as shown in Table 2. The parameters were extracted using the single bit encryption case and for an implementation that takes advantage of the noise asymmetry, i.e. Equation 5. In case of selection of the noise distribution we follow the Equation 1 and choose noise distance to be smaller than 2⁻¹²⁸ for Equation 2. The Hermite Factor is selected using the approach in Section 4. We also use the R-LWE estimator from [1] for selecting a bound for error noise, i.e. B_err = 2.

In Table 3 and Table 4, we summarize the maximum possible number of multiplications, i.e. 2^L, for 80-bit and 128-bit security levels, respectively. Note that it is advantageous to select large radix sizes ω for faster evaluation. This decreases the run-time significantly, however, the depth is reduced somewhat since the noise is increased. As for ciphertext sizes, we are able to decrease it by a factor of ω.

8 Implementation Results

We implemented the F-NTRU scheme using Shoup’s NTL library version 9.6.4 [24] compiled with the GMP 6.1 package. We ran our experiments on a 125 GBs of RAM and Intel Xeon E5-2637v2 64-bit CPU server clocked at 3.5 Ghz. The timing results for homomorphic multiplication are summarized in Table 5 for the parameters choices in Table 2. Although the algorithm is suitable for parallelization, NTL’s threading capabilities are limited. Therefore, when we use 4 threads, i.e. C = 4, we only achieve ∼ 2 times speedup. Furthermore, it is clear from the table that using 8 threads does not change the timings significantly.

The main advantage of the proposed F-NTRU scheme is that it eliminates costly evaluation keys and the slow relinearization operations. In addition the homomorphic evaluation is immensely simplified as we no longer care about keeping track of the evaluation levels per ciphertext. Finally, we summarize the evaluation key and ciphertext sizes in Table 6.

9 Conclusion

We presented a new leveled FHE scheme F-NTRU based on a variant of NTRU and by making use of a recently proposed noise management technique. Our scheme manages to eliminate costly evaluation keys, and any need for key switching and relinearization operations. We rigorously analyzed the security and noise performance of the proposed scheme, and determined parameters needed for correct evaluation of circuits of arbitrary depth. Our scheme makes use of wide key distributions and does not suffer from the Subfield Lattice Attack as LTV and YASHE’. Unlike these schemes, our proposed scheme does not rely on the DSPR assumption.

We analyzed and compared our scheme to the only other NTRU based FHE scheme immune to the attack, i.e. YASHE. Unlike YASHE, our scheme does not suffer from costly evaluation keys and relinearization operations. More significantly it supports deep homomorphic evaluation at reasonable ciphertext sizes, i.e. 2376 KB for 30 multiplicative levels. Our implementation achieves competitive speeds: multiplication in 24.4 msec to support 5 levels and 76 msec for 30 levels. With such speeds our scheme becomes relevant for use in restricted real-life applications. Finally, via a simple polynomial to integer mapping, our scheme supports homomorphic integer arithmetic with a very large message space as desired by many applications.