# Bootstrapping of FHE over the Integers with Large Message Space

Authors: Zhizhu Lian; Yupu Hu; Hu Chen; Baocang Wang
Journal: Security and Communication Networks
 (2018)

---

## Abstract

For the decryption of the fully homomorphic encryption (FHE) over the integers with the message spaceZQ, Nuida and Kurosawa proposed a Q4λ-multiplicative-degree circuit to compute it at Eurocrypt 2015, where λ is the security parameter and the message size Q is a constant. Since the degree of the decryption circuit is polynomial in Q, the range of the message size Q is limited. In this work, we solve this open problem as long as Q is large enough (larger than λ). We represent the decryption circuit as a arithmetic polynomial of multiplicative degree 108·λlog3λ, which is independent of the message size Q except a constraint Q>λ. Moreover, the bootstrapping process requires only O(λ·log⁡λ) number of multiplications to implement the decryption circuit, which is significantly lower than O(λ4) of Nuida and Kurosawa’s work. We also show the efficiency of the FHE scheme with message space ZQ compared to the FHE scheme with binary message space. As a result, we have that the former is preferable.


---

## Body

## 1. Introduction

In 1978, Rivest, Adleman, and Dertouzos introduced the notion of fully homomorphic encryption (FHE) which can compute any circuit on encrypted data without decryption [1]. It solves the ciphertext data calculation and the privacy protection of private cloud user in cloud computing environment. Until 2009, Gentry proposed firstly a fully homomorphic encryption scheme based on ideal lattices [2].Gentry’s Blueprint. First, Gentry constructed a somewhat homomorphic encryption (SHE) scheme, whose ciphertexts contain some noises for the security of the scheme. Noises, however, also limit the number of the homomorphic operations, e.g., ciphertexts multiplications. The second step is squashing the decryption circuit associated with an arbitrary ciphertext to obtain a low enough degree polynomial in the ciphertext bits and the secret key bits, which can be homomorphically evaluated by SHE scheme (called bootstrappable scheme). The last step is Gentry’s breakthrough, called bootstrapping, which refreshed ciphertexts by homomorphically evaluating this low multiplicative degree decryption circuit on the encryption of those bits, thus resulting in a new encryption of the same plaintext, but with possibly reduced noise. The refreshed ciphertexts can then support subsequent homomorphic operations. By repeatedly refreshing ciphertexts, the number of permissible homomorphic operations becomes unlimited. So a pure FHE scheme is transformed from the bootstrappable SHE scheme.


### 1.1. FHE over the Integers

At Eurocrypt 2010, van Dijk et al. [3] proposed the first FHE scheme over the integers (called DGHV scheme) following Gentry’s blueprint. The security of DGHV relies on the hardness of the Approximate Greatest Common Divisor problem (AGCD) and the Sparse Subset Sum problem (SSSP). Several works have dramatically improved the efficiency and the hardness assumption needed to implement it, including [4–12]. Some of the schemes above are leveled FHE scheme, but they essentially follow Gentry’s blueprint.In DGHV scheme, for the ciphertextc encryption of message m under secret key p (where p is a prime number), the decryption m←cmodpmod2 can be turned into the following circuit: (1)cmodpmod2=cmod2⊕∑i=1Θsizimod2, where the Θ length vector s=(s1,…,sΘ)∈0,1Θ is the secret key with Hamming weight θ, and each zi=(zi,0.zi,-1,…,zi,-n)2 is a real number with n=⌈log⁡θ⌉+3 bits of precision after the binary point, satisfying ∑i=1Θsizi≈c/p. This decryption circuit is implemented with a binary circuit of degree 64·λlog2λ on the secret key bits (s1,…,sΘ).Message Space. Practically, the computation over bitwise encryptions is not efficient. It is important to construct the FHE over lager integers for secure integer arithmetic (see [6, 13]). Fortunately, it is quite straightforward to extend the message space from Z2 to ZQ for SHE scheme [6, 14]. But they cannot convert this extended SHE scheme to an FHE scheme via the bootstrapping procedure. Because computing Q-ary addition seems to need more complex carry computations than binary addition, it seemed technically difficult to obtain a mod-Q arithmetic circuit that performs the decryption circuit (2)m⟵cmodpmodQ.At Eurocrypt 2015, Nuida and Kurosawa [8] proposed a Q-ary half adder, yielding the carry a in the procedure x+y=aQ+b for any x,y∈ZQ. They determined a carry function (3)a=fcarry,Qx,y=∑i=1Q-1xiQyQ-iQ,where xiQ=xx-1…x-i+1/(ii-1…1)modQ. It has the multiplicative degree Q. The squashed decryption in [8] works as (4)cmodpmodQ=(c-p∑i=1ΘsizimodQ, where Q is a constant prime, the secret key s=(s1,…,sΘ)∈{0,1}Θ is Θ length vector with Hamming weight θ=λ, and zi=(zi,0.zi,-1,…,zi,-L)Q<Q is a real number with L=⌈logQλ⌉+2 bits of precision after the Q-ary point, satisfying ∑i=1Θsizi≈c/p. The decryption circuit is computed by a mod-Q arithmetic circuit of multiplicative degree Q4λ=O(λ), where Q is a constant.In 2017, Cheon et al. [15] presented a faster bootstrapping of FHE over the integers than the previous work in [8]. The degree of the decryption is O(λ1+ε), and the number of homomorphic multiplications is O(log2λ), where ε is some small constant (being affected by the modulus Q).However, the modulusQ still needs to be a constant.ForQ>8Θ2, Cheon and Kim [16] expressed the decryption circuit as an L-restricted depth-3 (∑∏∑​) circuit by the technique in [17]. The L-degree is at most 8Θ2 and the number of product gates is at most 8Θ2+Θ+1. As we know, Θ is ω(λ6log⁡λ) in [3] and is reduced to O~(λ3) in [4]. The decryption is too complexity to bootstrap. So, in the FHE scheme, the ciphertext associated with the large prime message space needs a low-degree decryption circuit.Efficiency. To evaluate homomorphically a mod-Q arithmetic circuit, one can use the FHE scheme with message space ZQ directly, or one can firstly convert the arithmetic circuit to a Boolean one and carry out all the computation using an FHE scheme with binary message space. At ACNS 2016, Kim and Tibouchi [18] compared the two approaches for the Nuida-Kurosawa scheme, denoted by NK, and showed that the scheme NK with nonbinary message space is less efficient than its variant with binary message space. Fortunately, the bootstrapping method proposed by Cheon et al. [15] is worthwhile for Q of constant size by comparing both above approaches for CLT scheme. However, the modulus Q still needs to be a constant.Therefore, it is open for large value ofQ to express the decryption circuit of FHE schemes with the form (5) as a low-degree polynomial.(5)m⟵cmodpmodQ


### 1.2. Contributions

In this paper, we solve this open problem as long asQ is large enough (larger than θ).The usual technique for squashing the decryption circuit amounts to homomorphically evaluating a large integer sum of the form∑i=1Θsizi, where the si are secret bits and the zi are public constants computed from the original ciphertexts and public parameters. In [8], Nuida and Kurosawa represented the zi’s as their Q-ary expansion and applied the mod-Q circuit for iterated addition. And they have also proved that the degree Q of the polynomial fcarry,Q(x,y) computing the carry of Q-ary half adder is the lowest degree. In order to obtain a low enough degree (be independent of Q) of decryption circuit, we cannot deal with the carry bit any more. Instead, in this paper we use zi=(zi,0.zi,-1,…,zi,-n)2 the binary representation of the real number zi. This means that we have to use mod-Q arithmetic circuit gates to emulate bit operations. Specifically for bits a and b, the XOR operation is computed by a⊕b=a+b-2abmodQ, and the AND operation is computed by a⊙b=abmodQ. So we can use the mod-Q arithmetic circuit to implement the decryption circuit. Usually, emulating binary operations are not that efficient since emulating binary addition needs multiplication. The challenge is how to compute it efficiently.Note that if using only a three-for-two trick, as mentioned in Section2.2, the decryption can be implemented with a multiplicative degree O(λ3) of mod-Q arithmetic circuit, which is better than the result of [16]. Our main contribution is reducing the multiplicative degree to O(λlog3λ) for any large prime Q with a constraint Q>λ.Now let us recall the circuit procedure computing⌊∑i=1Θsizi⌉mod2 in DGHV scheme [3].(1)
The first circuit computes the Hamming weight of the vectorσ(-j)=(s1z1,-j,…,sΘzΘ,-j), i.e., W-j=∑i=1Θsizi,-j for j=0,1,…,n, and denotes the binary representation of W-j as (w-j,t,…,w-j,0)2. Hence, ∑i=1Θsizi=W0+2-1W-1+…+2-nW-n. Specifically, for 0≤i≤t, 0≤j≤n, the i-th bit w-j,i of W-j can be obtained by using the elementary symmetric polynomial e(σ(-j)).(2)
The second circuit computesa and b, satisfying W0+2-1W-1+…+2-nW-n=a+b by applying the three-for-two trick over Z2 repeatedly.(3)
The third circuit computes⌊a+b⌉mod2 by a polynomial of degree 4.In this work, we use mod-Q arithmetic circuit to simulate those bit operations in the above binary circuit. It is easy to simulate the second circuit by applying the three-for-two trick over ZQ. It will cost some additional multiplicative degree, since we need an arithmetic polynomial of degree 2 to compute the XOR operation. The third circuit is also easy to be simulated with a polynomial of degree 4.However, to emulate the elementary symmetric polynomiale(σ(-j)) in step (1), it will take a polynomial of a high degree (greater than Θ, where Θ is ω(λ6log⁡λ) in [3] and is reduced to O~(λ3) in [4]). This cost is unacceptable. So we need to find a new arithmetic function to compute w-j,i, the bits in the binary representation of W-j.Our main idea is as follows.If we know the value of an integerb, it is easy to obtain each bit in the binary representation of b, but if we only get the range of value of b, namely, b<θ for some integer θ, it can be a little tricky to get each bit of b. We observe that we can overcome it by applying Lagrange interpolating polynomial, as shown in Section 2.3. Since the Hamming weight of the secret key vector s=(s1,…,sΘ) is θ, the Hamming weight of the vector σ(-j)=(s1z1,-j,…,sΘzΘ,-j) is not bigger than θ, namely, W-j≤θ. So we can get W-j just by using the mod-Q addition gate to directly add up at the cost of an additional condition that Q>θ. Then, for 0≤i≤⌈log⁡θ⌉-1, we can obtain all bits w-j,i by applyingLagrange interpolating polynomial on W-j.Conclusion: now we can express the decryption as mod-Q arithmetic polynomial with a constraint Q>θ. The simulation circuit computing step (1) is θ degree of the Lagrange interpolating polynomial. The simulation circuit computing step (2) has the multiplicative degree at most 3⌈log3/2n⌉+2. Hence, the multiplicative degree of our decryption circuit is (6)θ·3log3/2n+2·4≤108·λlog3λwhere we set n=⌈log⁡θ⌉+3, θ=λ. Moreover, the number of the multiplications required in our decryption is only O(θlog⁡θ), comparable with O(λ4) in [8].Efficiency. The arithmetic decryption circuit in NK scheme is not competitive as pointed out by [18], due to the fact that the squashed decryption circuit for NKQ has a depth polynomial in Q. Fortunately, the degree 108·λlog3λ of our squashed decryption circuit is independent of Q with a constraint Q>λ.We use the leveled FHE scheme over the integer proposed by Coron, Lepoint, and Tibouchi, denoted byCLT2, and extend its message space to ZQ, denoted by CLTQ. To state the efficiency of CLTQ with our bootstrapping procedure, we compare it with the scheme Convert-CLT2 converting the mod-Q arithmetic circuit to binary and evaluating all the operation using the scheme CLT2 with binary message space. Here we compare in terms of the ciphertext size and the time complexity of basic operation implemented during homomorphic evaluation.Then ciphertext sizeγQ of CLTQ is a little shorter than that of Convert-CLT2, specifically (7)log⁡Q·γ2γQ~log⁡Q·2λ+2log⁡λ+log⁡λ+22log⁡λ+922λ+2log⁡λ+log⁡λ·log4λ+92log⁡λ+log⁡Q+82.And for some Q∈[256,281], we have 1<log⁡Q·γ2/γQ<1.4 when λ=64. The ciphertexts for CLTQ and Convert-CLT2 are of the same size.Moreover, we denote byTQ the time complexity of a single ciphertext refresh operation in CLTQ and by T2′ the time complexity of carrying out a multiplication mod-Q in Convert-CLT2 (by homomorphically evaluating the Boolean circuit for modular multiplication, with a refresh operation after each AND gate). Then we show that (8)T2′TQ=17log⁡Q·λlog⁡λ·log⁡Q·γ2γQ~17log⁡Q·λlog⁡λ.For instance, TQ is faster than T2′ by a factor of more than 930, when Q≥λ.Then, we say that a pure FHE scheme with large message space with our bootstrapping procedure is preferable.


### 1.3. The Organization

We summarize some notations and tricks in Section2. In Section 3, we express the decryption circuit as a mod-Q arithmetic circuit of a low enough multiplicative degree. In Section 4, we present an FHE scheme over the integers with bootstrapping for the large prime message space and show its efficiency compared to the FHE scheme with binary message space. Finally, conclusion is given in Section 5.


## 1.1. FHE over the Integers

At Eurocrypt 2010, van Dijk et al. [3] proposed the first FHE scheme over the integers (called DGHV scheme) following Gentry’s blueprint. The security of DGHV relies on the hardness of the Approximate Greatest Common Divisor problem (AGCD) and the Sparse Subset Sum problem (SSSP). Several works have dramatically improved the efficiency and the hardness assumption needed to implement it, including [4–12]. Some of the schemes above are leveled FHE scheme, but they essentially follow Gentry’s blueprint.In DGHV scheme, for the ciphertextc encryption of message m under secret key p (where p is a prime number), the decryption m←cmodpmod2 can be turned into the following circuit: (1)cmodpmod2=cmod2⊕∑i=1Θsizimod2, where the Θ length vector s=(s1,…,sΘ)∈0,1Θ is the secret key with Hamming weight θ, and each zi=(zi,0.zi,-1,…,zi,-n)2 is a real number with n=⌈log⁡θ⌉+3 bits of precision after the binary point, satisfying ∑i=1Θsizi≈c/p. This decryption circuit is implemented with a binary circuit of degree 64·λlog2λ on the secret key bits (s1,…,sΘ).Message Space. Practically, the computation over bitwise encryptions is not efficient. It is important to construct the FHE over lager integers for secure integer arithmetic (see [6, 13]). Fortunately, it is quite straightforward to extend the message space from Z2 to ZQ for SHE scheme [6, 14]. But they cannot convert this extended SHE scheme to an FHE scheme via the bootstrapping procedure. Because computing Q-ary addition seems to need more complex carry computations than binary addition, it seemed technically difficult to obtain a mod-Q arithmetic circuit that performs the decryption circuit (2)m⟵cmodpmodQ.At Eurocrypt 2015, Nuida and Kurosawa [8] proposed a Q-ary half adder, yielding the carry a in the procedure x+y=aQ+b for any x,y∈ZQ. They determined a carry function (3)a=fcarry,Qx,y=∑i=1Q-1xiQyQ-iQ,where xiQ=xx-1…x-i+1/(ii-1…1)modQ. It has the multiplicative degree Q. The squashed decryption in [8] works as (4)cmodpmodQ=(c-p∑i=1ΘsizimodQ, where Q is a constant prime, the secret key s=(s1,…,sΘ)∈{0,1}Θ is Θ length vector with Hamming weight θ=λ, and zi=(zi,0.zi,-1,…,zi,-L)Q<Q is a real number with L=⌈logQλ⌉+2 bits of precision after the Q-ary point, satisfying ∑i=1Θsizi≈c/p. The decryption circuit is computed by a mod-Q arithmetic circuit of multiplicative degree Q4λ=O(λ), where Q is a constant.In 2017, Cheon et al. [15] presented a faster bootstrapping of FHE over the integers than the previous work in [8]. The degree of the decryption is O(λ1+ε), and the number of homomorphic multiplications is O(log2λ), where ε is some small constant (being affected by the modulus Q).However, the modulusQ still needs to be a constant.ForQ>8Θ2, Cheon and Kim [16] expressed the decryption circuit as an L-restricted depth-3 (∑∏∑​) circuit by the technique in [17]. The L-degree is at most 8Θ2 and the number of product gates is at most 8Θ2+Θ+1. As we know, Θ is ω(λ6log⁡λ) in [3] and is reduced to O~(λ3) in [4]. The decryption is too complexity to bootstrap. So, in the FHE scheme, the ciphertext associated with the large prime message space needs a low-degree decryption circuit.Efficiency. To evaluate homomorphically a mod-Q arithmetic circuit, one can use the FHE scheme with message space ZQ directly, or one can firstly convert the arithmetic circuit to a Boolean one and carry out all the computation using an FHE scheme with binary message space. At ACNS 2016, Kim and Tibouchi [18] compared the two approaches for the Nuida-Kurosawa scheme, denoted by NK, and showed that the scheme NK with nonbinary message space is less efficient than its variant with binary message space. Fortunately, the bootstrapping method proposed by Cheon et al. [15] is worthwhile for Q of constant size by comparing both above approaches for CLT scheme. However, the modulus Q still needs to be a constant.Therefore, it is open for large value ofQ to express the decryption circuit of FHE schemes with the form (5) as a low-degree polynomial.(5)m⟵cmodpmodQ


## 1.2. Contributions

In this paper, we solve this open problem as long asQ is large enough (larger than θ).The usual technique for squashing the decryption circuit amounts to homomorphically evaluating a large integer sum of the form∑i=1Θsizi, where the si are secret bits and the zi are public constants computed from the original ciphertexts and public parameters. In [8], Nuida and Kurosawa represented the zi’s as their Q-ary expansion and applied the mod-Q circuit for iterated addition. And they have also proved that the degree Q of the polynomial fcarry,Q(x,y) computing the carry of Q-ary half adder is the lowest degree. In order to obtain a low enough degree (be independent of Q) of decryption circuit, we cannot deal with the carry bit any more. Instead, in this paper we use zi=(zi,0.zi,-1,…,zi,-n)2 the binary representation of the real number zi. This means that we have to use mod-Q arithmetic circuit gates to emulate bit operations. Specifically for bits a and b, the XOR operation is computed by a⊕b=a+b-2abmodQ, and the AND operation is computed by a⊙b=abmodQ. So we can use the mod-Q arithmetic circuit to implement the decryption circuit. Usually, emulating binary operations are not that efficient since emulating binary addition needs multiplication. The challenge is how to compute it efficiently.Note that if using only a three-for-two trick, as mentioned in Section2.2, the decryption can be implemented with a multiplicative degree O(λ3) of mod-Q arithmetic circuit, which is better than the result of [16]. Our main contribution is reducing the multiplicative degree to O(λlog3λ) for any large prime Q with a constraint Q>λ.Now let us recall the circuit procedure computing⌊∑i=1Θsizi⌉mod2 in DGHV scheme [3].(1)
The first circuit computes the Hamming weight of the vectorσ(-j)=(s1z1,-j,…,sΘzΘ,-j), i.e., W-j=∑i=1Θsizi,-j for j=0,1,…,n, and denotes the binary representation of W-j as (w-j,t,…,w-j,0)2. Hence, ∑i=1Θsizi=W0+2-1W-1+…+2-nW-n. Specifically, for 0≤i≤t, 0≤j≤n, the i-th bit w-j,i of W-j can be obtained by using the elementary symmetric polynomial e(σ(-j)).(2)
The second circuit computesa and b, satisfying W0+2-1W-1+…+2-nW-n=a+b by applying the three-for-two trick over Z2 repeatedly.(3)
The third circuit computes⌊a+b⌉mod2 by a polynomial of degree 4.In this work, we use mod-Q arithmetic circuit to simulate those bit operations in the above binary circuit. It is easy to simulate the second circuit by applying the three-for-two trick over ZQ. It will cost some additional multiplicative degree, since we need an arithmetic polynomial of degree 2 to compute the XOR operation. The third circuit is also easy to be simulated with a polynomial of degree 4.However, to emulate the elementary symmetric polynomiale(σ(-j)) in step (1), it will take a polynomial of a high degree (greater than Θ, where Θ is ω(λ6log⁡λ) in [3] and is reduced to O~(λ3) in [4]). This cost is unacceptable. So we need to find a new arithmetic function to compute w-j,i, the bits in the binary representation of W-j.Our main idea is as follows.If we know the value of an integerb, it is easy to obtain each bit in the binary representation of b, but if we only get the range of value of b, namely, b<θ for some integer θ, it can be a little tricky to get each bit of b. We observe that we can overcome it by applying Lagrange interpolating polynomial, as shown in Section 2.3. Since the Hamming weight of the secret key vector s=(s1,…,sΘ) is θ, the Hamming weight of the vector σ(-j)=(s1z1,-j,…,sΘzΘ,-j) is not bigger than θ, namely, W-j≤θ. So we can get W-j just by using the mod-Q addition gate to directly add up at the cost of an additional condition that Q>θ. Then, for 0≤i≤⌈log⁡θ⌉-1, we can obtain all bits w-j,i by applyingLagrange interpolating polynomial on W-j.Conclusion: now we can express the decryption as mod-Q arithmetic polynomial with a constraint Q>θ. The simulation circuit computing step (1) is θ degree of the Lagrange interpolating polynomial. The simulation circuit computing step (2) has the multiplicative degree at most 3⌈log3/2n⌉+2. Hence, the multiplicative degree of our decryption circuit is (6)θ·3log3/2n+2·4≤108·λlog3λwhere we set n=⌈log⁡θ⌉+3, θ=λ. Moreover, the number of the multiplications required in our decryption is only O(θlog⁡θ), comparable with O(λ4) in [8].Efficiency. The arithmetic decryption circuit in NK scheme is not competitive as pointed out by [18], due to the fact that the squashed decryption circuit for NKQ has a depth polynomial in Q. Fortunately, the degree 108·λlog3λ of our squashed decryption circuit is independent of Q with a constraint Q>λ.We use the leveled FHE scheme over the integer proposed by Coron, Lepoint, and Tibouchi, denoted byCLT2, and extend its message space to ZQ, denoted by CLTQ. To state the efficiency of CLTQ with our bootstrapping procedure, we compare it with the scheme Convert-CLT2 converting the mod-Q arithmetic circuit to binary and evaluating all the operation using the scheme CLT2 with binary message space. Here we compare in terms of the ciphertext size and the time complexity of basic operation implemented during homomorphic evaluation.Then ciphertext sizeγQ of CLTQ is a little shorter than that of Convert-CLT2, specifically (7)log⁡Q·γ2γQ~log⁡Q·2λ+2log⁡λ+log⁡λ+22log⁡λ+922λ+2log⁡λ+log⁡λ·log4λ+92log⁡λ+log⁡Q+82.And for some Q∈[256,281], we have 1<log⁡Q·γ2/γQ<1.4 when λ=64. The ciphertexts for CLTQ and Convert-CLT2 are of the same size.Moreover, we denote byTQ the time complexity of a single ciphertext refresh operation in CLTQ and by T2′ the time complexity of carrying out a multiplication mod-Q in Convert-CLT2 (by homomorphically evaluating the Boolean circuit for modular multiplication, with a refresh operation after each AND gate). Then we show that (8)T2′TQ=17log⁡Q·λlog⁡λ·log⁡Q·γ2γQ~17log⁡Q·λlog⁡λ.For instance, TQ is faster than T2′ by a factor of more than 930, when Q≥λ.Then, we say that a pure FHE scheme with large message space with our bootstrapping procedure is preferable.


## 1.3. The Organization

We summarize some notations and tricks in Section2. In Section 3, we express the decryption circuit as a mod-Q arithmetic circuit of a low enough multiplicative degree. In Section 4, we present an FHE scheme over the integers with bootstrapping for the large prime message space and show its efficiency compared to the FHE scheme with binary message space. Finally, conclusion is given in Section 5.


## 2. Preliminaries

### 2.1. Notations

For a real numberz, we denote by ⌈z⌉, ⌊z⌋, ⌊z⌉ the rounding of a up, down, or the nearest integer. For integers m, n, we denote the integer sets {m,m+1,…,n-1,n} and {m,m+1,…,n-1} by [m,n], and [m,n), respectively. For a real number r, we use r=(…,r1,r0.r-1,r-2,…,r-n)Q to denote the Q-ary representation of r with n bits of precision after the Q-ary point. When Q=2, it denotes the binary representation of r. Given x,p∈R, we let [x]p denote the unique number in (-p/2,p/2] that is congruent to xmodp. All logarithms in the text are base-2 unless stated otherwise.For a positive integern, x∈Z∩[0,2n) and y∈R, define BitDecompn(x)=(x0,x1,…,xn-1)2∈{0,1}n with x=∑i=0n-1xi2i, and PowersofTwon(y)=(y,2y,…,2n-1y)∈Rn; then we have (9)BitDecompnx,PowersofTwony=∑i=0n-1xi2iy=xy.


### 2.2. Three-for-Two Trick overZQ

Three-for-two trick is used to transform three numbers of arbitrary bit length into two numbers that are at most 1 bit longer, such that the sum of the two output numbers is the same as the sum of the three input numbers. And three-for-two trick overZQ has been mentioned in [17]. For a,b,c∈{0,1}∗, let a=(…,a1,a0)2, b=(…,b1,b0)2, and c=(…,c1,c0)2; then(10)a+b+c=XORa,b,c+2CARRYa,b,cmodQ=…,XORa0,b0,c0+…,CARRYa0,b0,c0,0modQ,where (11)XORai,bi,ci=4aibici-2aibi+aici+bici+ai+bi+cimodQ,CARRYai,bi,ci=aibi+aici+bici-2aibicimodQ.while for Q=2, the bit operation XOR(ai,bi,ci)=ai⊕bi⊕ci, and CARRY(ai,bi,ci)=aibi⊕aici⊕bici.


### 2.3. Lagrange Interpolating Polynomial

The Lagrange interpolating polynomial is the polynomialf(x) of degree n-1 that passes through the n points {(x0,y0=f(x0)),…,(xn-1,yn-1=f(xn-1))}, and given by f(x)=∑j=0n-1fj(x), where (12)fjx=yj∏0≤k≤n-1,k≠jx-xkxj-xk.Our goal of introducing the Lagrange interpolation polynomial is to obtain the mod-Q arithmetic polynomial expression of computing any bit in the binary representation of the integer x∈[0,θ]. For every integer b∈[0,θ], let b=(bn-1,…,b0)2, where n=⌈log⁡θ⌉. For each index t∈[0,n-1], we construct a set consisting of integer b and its t-th bit bt, where b=0,1,…,θ, namely, denote the set as {(b,bt)}b∈[0,θ] for each t. So for each index t∈[0,n-1], the θ+1 points set is (13)xb=b,yb=btb∈0,θ=x0=0,y0=0t,x1=1,y1=1t,…,xθ=θ,yθ=θt.If the variable x equates to an integer b∈[0,θ], for the index t∈[0,…,n-1], the output of the Lagrange interpolating polynomial (14)Ftx=∑j=0θyj∏0≤k≤θ,k≠jx-xkxj-xkmodQis yb, which equates to the t-th bit in the binary representation of x. The multiplicative degree of the mod-Q arithmetic circuit is θ.


## 2.1. Notations

For a real numberz, we denote by ⌈z⌉, ⌊z⌋, ⌊z⌉ the rounding of a up, down, or the nearest integer. For integers m, n, we denote the integer sets {m,m+1,…,n-1,n} and {m,m+1,…,n-1} by [m,n], and [m,n), respectively. For a real number r, we use r=(…,r1,r0.r-1,r-2,…,r-n)Q to denote the Q-ary representation of r with n bits of precision after the Q-ary point. When Q=2, it denotes the binary representation of r. Given x,p∈R, we let [x]p denote the unique number in (-p/2,p/2] that is congruent to xmodp. All logarithms in the text are base-2 unless stated otherwise.For a positive integern, x∈Z∩[0,2n) and y∈R, define BitDecompn(x)=(x0,x1,…,xn-1)2∈{0,1}n with x=∑i=0n-1xi2i, and PowersofTwon(y)=(y,2y,…,2n-1y)∈Rn; then we have (9)BitDecompnx,PowersofTwony=∑i=0n-1xi2iy=xy.


## 2.2. Three-for-Two Trick overZQ

Three-for-two trick is used to transform three numbers of arbitrary bit length into two numbers that are at most 1 bit longer, such that the sum of the two output numbers is the same as the sum of the three input numbers. And three-for-two trick overZQ has been mentioned in [17]. For a,b,c∈{0,1}∗, let a=(…,a1,a0)2, b=(…,b1,b0)2, and c=(…,c1,c0)2; then(10)a+b+c=XORa,b,c+2CARRYa,b,cmodQ=…,XORa0,b0,c0+…,CARRYa0,b0,c0,0modQ,where (11)XORai,bi,ci=4aibici-2aibi+aici+bici+ai+bi+cimodQ,CARRYai,bi,ci=aibi+aici+bici-2aibicimodQ.while for Q=2, the bit operation XOR(ai,bi,ci)=ai⊕bi⊕ci, and CARRY(ai,bi,ci)=aibi⊕aici⊕bici.


## 2.3. Lagrange Interpolating Polynomial

The Lagrange interpolating polynomial is the polynomialf(x) of degree n-1 that passes through the n points {(x0,y0=f(x0)),…,(xn-1,yn-1=f(xn-1))}, and given by f(x)=∑j=0n-1fj(x), where (12)fjx=yj∏0≤k≤n-1,k≠jx-xkxj-xk.Our goal of introducing the Lagrange interpolation polynomial is to obtain the mod-Q arithmetic polynomial expression of computing any bit in the binary representation of the integer x∈[0,θ]. For every integer b∈[0,θ], let b=(bn-1,…,b0)2, where n=⌈log⁡θ⌉. For each index t∈[0,n-1], we construct a set consisting of integer b and its t-th bit bt, where b=0,1,…,θ, namely, denote the set as {(b,bt)}b∈[0,θ] for each t. So for each index t∈[0,n-1], the θ+1 points set is (13)xb=b,yb=btb∈0,θ=x0=0,y0=0t,x1=1,y1=1t,…,xθ=θ,yθ=θt.If the variable x equates to an integer b∈[0,θ], for the index t∈[0,…,n-1], the output of the Lagrange interpolating polynomial (14)Ftx=∑j=0θyj∏0≤k≤θ,k≠jx-xkxj-xkmodQis yb, which equates to the t-th bit in the binary representation of x. The multiplicative degree of the mod-Q arithmetic circuit is θ.


## 3. Bootstrapping the Decryption

This section deals mainly with how to implement the decryptionm←cmodpmodQ with a mod-Q arithmetic circuit of a low degree.


### 3.1. Squashing the Decryption with SSSP Assumption

The decryption circuit is(15)m⟵cmodpmodQ=c-cpmodQ. Let y be a vector of Θ rational number in [0,Q) with κ bits of precision after the binary point, and let sk=(s1,s2,…,sΘ)2 be the secret key vector of Θ bits with Hamming weight θ such that 1/p=〈sk,y〉+εmodQ, where |ε|<2-κ. We firstly compute zi=[c·yi], keeping only n=⌈log⁡θ⌉+3 bits of precision after the binary point for i=1,2,…,Θ. So [c·yi]=zi-Δi for some Δi with |Δi|<1/16θ. We have (16)cp-∑i=1Θsizi=cp-∑i=1Θsic·yi+∑i=1ΘsiΔimodQ=cp-c·1p-ε+∑i=1ΘsiΔimodQ=c·ε+∑i=1ΘsiΔimodQ.We set the bit length of ciphertextc is γ<κ-4; thus, |c·ε|<1/16. And we observe that |∑i=1ΘsiΔi|≤θ/16θ. Since c is a valid ciphertext, satisfying that the value of c/p is within 1/8 of an integer as the definition in [3]; thus, ∑i=1Θsizi is within 1/4 of an integer. Therefore, we have (17)m⟵cmodpmodQ=c-∑i=1ΘsizimodQ. For i∈[1,Θ], let zi=(zi′.zi′′)2, where zi′=(zi,γlog⁡Q-1′,…,zi,0′)2 is the integer part of zi and zi′′=(zi,-1′′,…,zi,-n′′)2 is the fractional part. Then we have (18)m=c-∑i=1Θsizi′modQ-2-n∑i=1Θsizi′′modQ.where 2-n∑i=1Θsizi′′ is within 1/4 of an integer. (Note that most of the context above in this subsection has been described by van Dijk et al. in [3], which is the procedure of squashing the decryption circuit for the case of Q=2.)


### 3.2. Bootstrapping

For the integer part, we need to computesizi′modQ. We can firstly reduce zi′ with the modulo Q and sum up for all i, namely, (19)∑i=1Θsizi′modQ=∑i=1Θsizi′modQmodQ.It only takes Θ multiplication-by-constant gates and Θ mod-Q addition gates.For the factional part, in order to compute⌊2-n∑i=1Θsizi′′⌉, here we firstly construct a mod-Q circuit that outputs each bit in the binary representation of the sum ∑i=1Θsizi′′=∑i=1Θ(sizi,-1′′,…,sizi,-n′′)2 in the following step (1).(1)
Generaten integer numbers {W-j}j∈[1,n] such that W-j=∑i=1Θsizi,-j′′, namely, W-j is the Hamming weight of the vector σ(-j)=(s1z1,-j′′,…,sΘzΘ,-j′′). Since the Hamming weight of the vector sk is θ, then W-j is not bigger than θ, i.e., W-j≤θ. Firstly, compute the sums W-j by directly using mod-Q addition gates, this works since Q>θ. Let W-j=(w-j,n-1,…,w-j,0)2. Then convert the small integer W-j into their bit representation by applying theLagrange interpolating polynomial introduced in Section 2.3; namely, for 0≤t≤n-1, 1≤j≤n, we have w-j,t=Ft(W-j), where the multiplicative degree is θ.(2)
Now∑i=1Θsizi′′=∑j=1n2n-jW-j, which is the sum of n  2n-bit length of numbers. We can compute it by applying the three-for-two trick over ZQ mentioned in Section 2.2 repeatedly, resulting in two numbers t1 and t2 satisfying t1+t2=∑j=1n2n-jW-j. Since we need to apply this trick ⌈log3/2n⌉+2 times, the bit length of t1 and t2 becomes 2n+⌈log3/2n⌉+2.(3)
Lett1=2nt1′+t1′′, t2=2nt2′+t2′′, then(20)2-n∑i=1Θsizi′′=2-nt1+t2=t1′+t2′+2-nt1′′+t2′′.To evaluate⌊2-n(t1′′+t2′′)⌉, let (21)2-nt1′′=0.a-1,…,a-n2,2-nt2′′=0.b-1,…,b-n2.Letc0,c-1,…,c-n+1,c-n=0 be all the carry bits generated in the addition procedure, where c-i+1=MAJ(a-i,b-i,c-i)=(a-i⊕b-i)(a-i⊕c-i)⊕a-i. Thus, we have (22)2-nt1′′+t2′′=c0.a-1⊕b-1⊕c-1,…,a-n⊕b-n⊕02.Since2-n∑i=1Θsizi′′ is within 1/4 of some integer mentioned in Section 3.1, we have a-1⊕b-1⊕c-1=0, a-2⊕b-2⊕c-2=0; thus(23)c0=a-1a-2b-2⊕a-2b-1b-2⊕a-1a-2⊕a-1b-1⊕a-1b-2⊕a-2b-1⊕b-1b-2.Using mod-Q gates to compute those bit operations,(24)c0=a-1×a-2+a-1×b-1+a-2×b-1+b-1×b-2-2×a-1×a-2×b-1-a-1×a-2×b-2-a-2×b-1×b-2-2×a-1×b-1×b-2+2×a-1×a-2×b-1×b-2modQ,which is a polynomial of degree 4. For integer part, to implementt1′+t2′, we can compute t1′modQ and t2′modQ with the stored numbers aj←2jmodQ for j=1,2,…,n+⌈log3/2n⌉+2. Since for an integer b=(bk,…,b1,b0)2,(25)bmodQ=b0+2b1+…+2kbkmodQ=a0b0+a1b1+…+akmodQbkmodQ.The modified decryption works as(26)m=c-∑i=1Θsizi′modQ-t1′modQ+t2′modQ+c0modQ.We conclude that the degree of the polynomial in the first step isθ, the degree of the polynomial in the second step is at most 3⌈log3/2n⌉+2<27·log2.71θ, and the degree of the polynomial in the third step is 4. Therefore, the total degree of the decryption circuit over ZQ is bounded by θ·(27·log2.71θ)·4<108·θlog3θ. Since we set θ=λ for security, the degree is at most 108·λlog3λ. So the multiplicative degree of the decryption circuit is O(λlog3λ) for any prime Q with the constraint Q>λ.Remark 1.
In [4], the authors set θ=λ/log⁡λ (θ=15 when λ=72). It means that we can express the decryption circuit of FHE scheme over the integers as a low-degree polynomial over ZQ for any Q≥16. The multiplicative degree of decryption circuit in [8] is O(λ) for the case that Q is a constant prime, and 8Θ2 in [16] for the case Q>8Θ2. If Q is bigger than 15, our degree of decryption circuit is smaller than that of [8]. See Table 1.Table 1
Multiplicative degree of decryption circuit.
Q = 2 Q is a constant prime Q > λ [3] 64 λ  l o g 2 λ - - [4] 2 λ - - [8] 16 λ Q 4 λ - [15] - O ( λ 1 + ϵ ) - [16] - - 8 Θ 2 our result - - 108 λ  l o g 3 λMoreover, we reduce the number of multiplications in the decryption circuit which is better than almost previous works as shown in Table2. Here we have to emphasize that we do not count the number of multiplication-by-constant gates in the decryption circuit to the number of multiplications.Table 2
The number of multiplications in the decryption circuit.
the number of multiplications [3] O ( θ Θ ) [4] O ( θ 2 ) [8] O(Θlog2θ) [15] O(log2θ) [16] Θ2+Θ+1 our result O ( θ  l o g  θ )Proposition 2.
The number of multiplications in our squashed decryption circuit is at mostO(θ·log⁡θ).Proof.
For the integer part, we useΘ multiplication-by-constant gates and Θ mod-Q addition gates.
For the factional part, in step(1), we apply theLagrange interpolating polynomial in n variate, which is a polynomial of degree θ. For a variate x, first we compute y1=x,y2=x2,…,yθ=xθ which requires θ-1 multiplications. So aLagrange interpolating polynomial consists of θ-1 multiplications, θ-1 multiplication-by-constant gates, and θ additions gates. Then we need the nθ multiplications in step (1).
The 3-for-2 trick overZQ for the bits a,b,c needs 4 multiplications gates. Step (2) needs to sum up the n  2n-bit length of numbers, and for the first time applying this trick, it takes 4·2n·(n/3) multiplications gates, the second time needs to sum up about 2n/3  2n+1-bit of numbers, and it takes 4·(2n+1)·((2n/3)/3) multiplications gates, and so on. Then it takes about (27)8n2/3·1-2/3log3/2n+31-2/3+4n/3·1-2/3log3/2n+21-2/3<8n2+4nmultiplication gates in step (2).
In step(3), we need 9 multiplications to compute c0.
So the number of multiplications in our squashed circuit is(28)θ·n+8n2+4n+9=Oθ·log⁡θ.


### 3.3. Removing the ConstraintQ>λ

The constraintQ>λ is required because we want to compute the bits of the Hamming weight by directly summing up without regard to the carry bits generated from the addition. We observe that the optimization of the binary decryption circuit proposed in [4] does not counter the Hamming weight, so we can remove the constraint. With the three-for-two trick over ZQ, we can transform the binary decryption circuit to mod-Q arithmetic circuit, resulting in more complexity of the decryption circuit.More precisely, we can divide the secret keysk into θ boxes Boxi of B=Θ/θ bits each, such that each box has single 1-bit in it. Then (29)m=c-∑i=1ΘsizimodQ=c-∑i=1θ∑sj∈BoxizjmodQ.Let qi=∑sj∈Boxizj be obtained by adding B numbers, with only one being nonzero. So (30)qi=∑sj∈BoxizjmodQ=∑sj∈Boxizj. It only requires the mod-Q addition gates. Then applying three-for-two trick over ZQ to add up the θ numbers and using the rounding computations in step (3) in last subsection, the decryption circuit is implemented by a polynomial of multiplicative degree 3⌈log3/2θ⌉+2·4<108θ3, i.e., O(λ3).The goal we describe in this subsection is to emphasize that our work in the last subsection reduces the multiplicative degree of decryption circuit fromO(λ3) to O(λlog3λ).


## 3.1. Squashing the Decryption with SSSP Assumption

The decryption circuit is(15)m⟵cmodpmodQ=c-cpmodQ. Let y be a vector of Θ rational number in [0,Q) with κ bits of precision after the binary point, and let sk=(s1,s2,…,sΘ)2 be the secret key vector of Θ bits with Hamming weight θ such that 1/p=〈sk,y〉+εmodQ, where |ε|<2-κ. We firstly compute zi=[c·yi], keeping only n=⌈log⁡θ⌉+3 bits of precision after the binary point for i=1,2,…,Θ. So [c·yi]=zi-Δi for some Δi with |Δi|<1/16θ. We have (16)cp-∑i=1Θsizi=cp-∑i=1Θsic·yi+∑i=1ΘsiΔimodQ=cp-c·1p-ε+∑i=1ΘsiΔimodQ=c·ε+∑i=1ΘsiΔimodQ.We set the bit length of ciphertextc is γ<κ-4; thus, |c·ε|<1/16. And we observe that |∑i=1ΘsiΔi|≤θ/16θ. Since c is a valid ciphertext, satisfying that the value of c/p is within 1/8 of an integer as the definition in [3]; thus, ∑i=1Θsizi is within 1/4 of an integer. Therefore, we have (17)m⟵cmodpmodQ=c-∑i=1ΘsizimodQ. For i∈[1,Θ], let zi=(zi′.zi′′)2, where zi′=(zi,γlog⁡Q-1′,…,zi,0′)2 is the integer part of zi and zi′′=(zi,-1′′,…,zi,-n′′)2 is the fractional part. Then we have (18)m=c-∑i=1Θsizi′modQ-2-n∑i=1Θsizi′′modQ.where 2-n∑i=1Θsizi′′ is within 1/4 of an integer. (Note that most of the context above in this subsection has been described by van Dijk et al. in [3], which is the procedure of squashing the decryption circuit for the case of Q=2.)


## 3.2. Bootstrapping

For the integer part, we need to computesizi′modQ. We can firstly reduce zi′ with the modulo Q and sum up for all i, namely, (19)∑i=1Θsizi′modQ=∑i=1Θsizi′modQmodQ.It only takes Θ multiplication-by-constant gates and Θ mod-Q addition gates.For the factional part, in order to compute⌊2-n∑i=1Θsizi′′⌉, here we firstly construct a mod-Q circuit that outputs each bit in the binary representation of the sum ∑i=1Θsizi′′=∑i=1Θ(sizi,-1′′,…,sizi,-n′′)2 in the following step (1).(1)
Generaten integer numbers {W-j}j∈[1,n] such that W-j=∑i=1Θsizi,-j′′, namely, W-j is the Hamming weight of the vector σ(-j)=(s1z1,-j′′,…,sΘzΘ,-j′′). Since the Hamming weight of the vector sk is θ, then W-j is not bigger than θ, i.e., W-j≤θ. Firstly, compute the sums W-j by directly using mod-Q addition gates, this works since Q>θ. Let W-j=(w-j,n-1,…,w-j,0)2. Then convert the small integer W-j into their bit representation by applying theLagrange interpolating polynomial introduced in Section 2.3; namely, for 0≤t≤n-1, 1≤j≤n, we have w-j,t=Ft(W-j), where the multiplicative degree is θ.(2)
Now∑i=1Θsizi′′=∑j=1n2n-jW-j, which is the sum of n  2n-bit length of numbers. We can compute it by applying the three-for-two trick over ZQ mentioned in Section 2.2 repeatedly, resulting in two numbers t1 and t2 satisfying t1+t2=∑j=1n2n-jW-j. Since we need to apply this trick ⌈log3/2n⌉+2 times, the bit length of t1 and t2 becomes 2n+⌈log3/2n⌉+2.(3)
Lett1=2nt1′+t1′′, t2=2nt2′+t2′′, then(20)2-n∑i=1Θsizi′′=2-nt1+t2=t1′+t2′+2-nt1′′+t2′′.To evaluate⌊2-n(t1′′+t2′′)⌉, let (21)2-nt1′′=0.a-1,…,a-n2,2-nt2′′=0.b-1,…,b-n2.Letc0,c-1,…,c-n+1,c-n=0 be all the carry bits generated in the addition procedure, where c-i+1=MAJ(a-i,b-i,c-i)=(a-i⊕b-i)(a-i⊕c-i)⊕a-i. Thus, we have (22)2-nt1′′+t2′′=c0.a-1⊕b-1⊕c-1,…,a-n⊕b-n⊕02.Since2-n∑i=1Θsizi′′ is within 1/4 of some integer mentioned in Section 3.1, we have a-1⊕b-1⊕c-1=0, a-2⊕b-2⊕c-2=0; thus(23)c0=a-1a-2b-2⊕a-2b-1b-2⊕a-1a-2⊕a-1b-1⊕a-1b-2⊕a-2b-1⊕b-1b-2.Using mod-Q gates to compute those bit operations,(24)c0=a-1×a-2+a-1×b-1+a-2×b-1+b-1×b-2-2×a-1×a-2×b-1-a-1×a-2×b-2-a-2×b-1×b-2-2×a-1×b-1×b-2+2×a-1×a-2×b-1×b-2modQ,which is a polynomial of degree 4. For integer part, to implementt1′+t2′, we can compute t1′modQ and t2′modQ with the stored numbers aj←2jmodQ for j=1,2,…,n+⌈log3/2n⌉+2. Since for an integer b=(bk,…,b1,b0)2,(25)bmodQ=b0+2b1+…+2kbkmodQ=a0b0+a1b1+…+akmodQbkmodQ.The modified decryption works as(26)m=c-∑i=1Θsizi′modQ-t1′modQ+t2′modQ+c0modQ.We conclude that the degree of the polynomial in the first step isθ, the degree of the polynomial in the second step is at most 3⌈log3/2n⌉+2<27·log2.71θ, and the degree of the polynomial in the third step is 4. Therefore, the total degree of the decryption circuit over ZQ is bounded by θ·(27·log2.71θ)·4<108·θlog3θ. Since we set θ=λ for security, the degree is at most 108·λlog3λ. So the multiplicative degree of the decryption circuit is O(λlog3λ) for any prime Q with the constraint Q>λ.Remark 1.
In [4], the authors set θ=λ/log⁡λ (θ=15 when λ=72). It means that we can express the decryption circuit of FHE scheme over the integers as a low-degree polynomial over ZQ for any Q≥16. The multiplicative degree of decryption circuit in [8] is O(λ) for the case that Q is a constant prime, and 8Θ2 in [16] for the case Q>8Θ2. If Q is bigger than 15, our degree of decryption circuit is smaller than that of [8]. See Table 1.Table 1
Multiplicative degree of decryption circuit.
Q = 2 Q is a constant prime Q > λ [3] 64 λ  l o g 2 λ - - [4] 2 λ - - [8] 16 λ Q 4 λ - [15] - O ( λ 1 + ϵ ) - [16] - - 8 Θ 2 our result - - 108 λ  l o g 3 λMoreover, we reduce the number of multiplications in the decryption circuit which is better than almost previous works as shown in Table2. Here we have to emphasize that we do not count the number of multiplication-by-constant gates in the decryption circuit to the number of multiplications.Table 2
The number of multiplications in the decryption circuit.
the number of multiplications [3] O ( θ Θ ) [4] O ( θ 2 ) [8] O(Θlog2θ) [15] O(log2θ) [16] Θ2+Θ+1 our result O ( θ  l o g  θ )Proposition 2.
The number of multiplications in our squashed decryption circuit is at mostO(θ·log⁡θ).Proof.
For the integer part, we useΘ multiplication-by-constant gates and Θ mod-Q addition gates.
For the factional part, in step(1), we apply theLagrange interpolating polynomial in n variate, which is a polynomial of degree θ. For a variate x, first we compute y1=x,y2=x2,…,yθ=xθ which requires θ-1 multiplications. So aLagrange interpolating polynomial consists of θ-1 multiplications, θ-1 multiplication-by-constant gates, and θ additions gates. Then we need the nθ multiplications in step (1).
The 3-for-2 trick overZQ for the bits a,b,c needs 4 multiplications gates. Step (2) needs to sum up the n  2n-bit length of numbers, and for the first time applying this trick, it takes 4·2n·(n/3) multiplications gates, the second time needs to sum up about 2n/3  2n+1-bit of numbers, and it takes 4·(2n+1)·((2n/3)/3) multiplications gates, and so on. Then it takes about (27)8n2/3·1-2/3log3/2n+31-2/3+4n/3·1-2/3log3/2n+21-2/3<8n2+4nmultiplication gates in step (2).
In step(3), we need 9 multiplications to compute c0.
So the number of multiplications in our squashed circuit is(28)θ·n+8n2+4n+9=Oθ·log⁡θ.


## 3.3. Removing the ConstraintQ>λ

The constraintQ>λ is required because we want to compute the bits of the Hamming weight by directly summing up without regard to the carry bits generated from the addition. We observe that the optimization of the binary decryption circuit proposed in [4] does not counter the Hamming weight, so we can remove the constraint. With the three-for-two trick over ZQ, we can transform the binary decryption circuit to mod-Q arithmetic circuit, resulting in more complexity of the decryption circuit.More precisely, we can divide the secret keysk into θ boxes Boxi of B=Θ/θ bits each, such that each box has single 1-bit in it. Then (29)m=c-∑i=1ΘsizimodQ=c-∑i=1θ∑sj∈BoxizjmodQ.Let qi=∑sj∈Boxizj be obtained by adding B numbers, with only one being nonzero. So (30)qi=∑sj∈BoxizjmodQ=∑sj∈Boxizj. It only requires the mod-Q addition gates. Then applying three-for-two trick over ZQ to add up the θ numbers and using the rounding computations in step (3) in last subsection, the decryption circuit is implemented by a polynomial of multiplicative degree 3⌈log3/2θ⌉+2·4<108θ3, i.e., O(λ3).The goal we describe in this subsection is to emphasize that our work in the last subsection reduces the multiplicative degree of decryption circuit fromO(λ3) to O(λlog3λ).


## 4. FHE SchemeCLTQ with Our Bootstrapping Procedure

To show the usefulness of our squashed decryption circuit, we present a variant of FHE scheme over the integers with our bootstrapping procedure and then compare it with the original scheme in binary setting. By Gentry’s bootstrapping theory, we can get the “pure” FHE scheme transformed from the somewhat FHE scheme or the leveled FHE scheme. Here we only describe the latter scheme, since in the former situation the FHE scheme in mod-Q setting is not perforable to the binary setting.Here we describe an FHE scheme over the integers with bootstrapping for large prime message space just like Cheon, Han, and Kim did in [15], which is a variant of the FHE scheme presented by Coron, Lepoint, and Tibouchi in [7].Letρ be a bound on the bit length of the noise, η the bit length of the original secret key, and γ the bit length of the ciphertext. The parameter τ refers to the number of encryptions of zero contained in the public key for encryption, Θ the size of the secret vector, θ the Hamming weight of the vector, and κ the bit length of the rational numbers in the public key.These parameters must satisfy the following constraints.(i)
ρ≥λ, to protect against the brute force attacks on the noise.(ii)
η≥ρ+O(L(log⁡λ+log⁡Q)), where L is the depth of multiplication of the circuits to be evaluated.(iii)
γ>ω(η2·log⁡λ), to avoid lattice-based attacks [3, 4].(iv)
τ=γ+2λ+2, in order to use the leftover hash lemma in the security proof.(v)
Θ2≥γω(log⁡λ), to avoid known attacks on the sparse subset sum problem [4, 5].(vi)
Θθ/2≥2λ to avoid an attack on the sparse subset sum problem [19].(vii)
γ<κ-log⁡Q-4 is required in Section 3.1.


### 4.1. FHE Scheme with Message SpaceZQ

In this subsection, we describe an FHE scheme over the integers for message spaceZQ for a prime modulus Q, where Q can be any prime bigger than the security parameter λ, denoted by CLTQ.For anη-bit odd integer p, and an integer q0 in [0,2γ/p2), we define the set (31)Dp,q0ρ=p2·q+r:Chooseq⟵0,q0,r⟵-2ρ,2ρ.C L T Q . K e y G e n ( 1 λ ). Generate a η-bit prime p and a γ-bit integer x0=p2·q0+r0 with r0←(-2ρ,2ρ) and q0←[0,2γ/p2).( 1 ) Generate the public key for encryption. For 1≤i≤τ, sample xi←Dp,q0ρ, y′←Dp,q0ρ and y=y′+⌊p/Q⌋.( 2 ) Generate the public key for multiplication. Let v′ be a vector of Θ numbers with κ bit of precision following the binary point, denoted by v′=(v1′,…,vΘ′). Choose uniformly a Θ-bit vector s′=(s1′,s2′,…,sΘ′)∈{0,1}Θ at random such that (32)Q·2ηp2=s′,v′+ϵmodQ2ηwith |ϵ|<2-κ. Then, define (33)α=q·p2+r+PowersofTwos′·p2η+1,where the components of q are randomly chosen from [0,q0)∩Z and those of r from (-2ρ,2ρ)∩Z.(3) Generate the public key for bootstrapping. Choose uniformly aΘ-bit vector s=(s1,s2,…,sΘ)∈{0,1}Θ at random, with Hamming weight θ.Choose a random integervi∈[0,Qκ+1) such that ∑i=1Θsi·vi=⌊Qκ+1/p⌉ and set Z=⌊2κ(pmodQ)/p⌉=⌊2κ/p⌉.For0≤i≤Θ, choose ui←[0,2log⁡Q+κ+1)∩Z in such a way that ∑i=1Θsiui=Zmod2κ+1. Set yi=ui/2κ, and denote it by the vector y=(y1,y2,…,yΘ). Then ∑i=1Θsiyi=1/p-εp for some |εp|<2-κ.Forn=⌈log⁡θ⌉+3, generate the vector β=(β1,…,βΘ): (34)βi=qi·p2+pQ·si+ri,where qi∈[0,q0) and ri∈(-2ρ,2ρ) for 1≤i≤Θ.Output the secret keysk=(p,s1,s2,…,sΘ), and the public key pk={x0,y,x1,…,xτ,v′,α,y,β}.C L T Q . E n c ( p k , m ). Given a message m∈ZQ, uniformly sample a subset S⊆{1,2,…,τ}, and output (35)c=∑i∈Sxi+y·mx0C L T Q . D e c ( s k , c ). Given a ciphertext c, output m=[⌊Qc/p⌉]Q.C L T Q . A d d ( p k , c 1 , c 2 ). Given two ciphertexts c1,c2, output cadd=[c1+c2]x0.C o n v e r t ( p k , c ). Given a ciphertext c, output c′=2〈α,BitDecompη(c)〉, where c=(⌊c·vi′⌉mod2η)1≤i≤Θ.C L T Q . M u l t ( p k , c 1 , c 2 ). Given two ciphertexts c1,c2, output cmult=[Convert(pk,c1·c2)]x0.C L T Q . M u l t C o n s ( p k , c , a ). Given a ciphertext c and a constant a∈ZQ, output cmultcons=[a·c]x0.C L T Q . R e c r y p t ( p k , c , D ε ). Given a ciphertext c for a message m, for i=1,2,…,Θ, compute zi=[Qc·yi], keeping only n=⌈log⁡θ⌉+3 bits of precision after binary point. Denote the binary representation of zi as zi=(…,zi,1,zi,0.zi,-1,…,zi,-n)2. And given the decryption Dε, which is (36)m=QcpQ=∑i=1ΘsiziQ,output a refreshed ciphertextc′=[⌊∑i=1Θβizi⌉]x0. The algorithm homomorphically evaluates the decryption circuit on the encryptions of the secret key bits (s1,s2,…,sΘ), referring to the bootstrapping process in Section 3 for more details.


### 4.2. Correctness

In this subjection, we prove the correctness of the homomorphic procedure.For the schemeCLTQ, the ciphertext has the form that c=q·2+(Qr∗+m)⌊p/Q⌋+r with two kinds of noise r and r∗. In [7], it is called a ciphertext with noise (ρ,ρ∗) if |r|<2ρ and |r∗|<2ρ∗. The authors of [15] proposed a noise growth analysis during the homomorphic addition and multiplication as shown in Lemma 3.Lemma 3 (Lemma 3 in [15]).
Letc1 and c2 be ciphertext with (ρ1,ρ1∗) and (ρ2,ρ2∗), respectively. Let ρ=max(ρ1,ρ2) and ρ∗=max(ρ1∗,ρ2∗).(i)
CLTQ.Add(pk,c1,c2) is a ciphertext with noise (ρ+2,ρ∗+1)(ii)
CLTQ.Mult(pk,c1,c2) is a ciphertext with noise (ρ+ρ∗+log⁡Q+8,log⁡Θ).Supposeρ∗≤log⁡Θ during the homomorphic evaluation. By Lemma 3, for the CLT scheme, the noise length in bits has only grown by an additive factor (log⁡Θ+log⁡Q+8). The noise growth during homomorphic evaluation is linear; then we have the following.Lemma 4 (recryption noise).
Letc be a ciphertext for a message m∈ZQ; CLTQ.Recrypt(pk,c,Dε) is a ciphertext with noise (37)ρ+log⁡Θ+L′log⁡λ+log⁡Q,log⁡Θ,where the depth of decryption L′ is (2·⌈log3/2n⌉+6+log⁡θ), less than (log(θlog4θ)+8).Proof.
The decryption circuitDε has been described in Section 3. We get the refreshed ciphertext c′=[⌊∑i=1Θβizi⌉]x0, where the noise of encryption of the secret key bit βi is (ρ,0). We describe the noise increasing with homomorphic evaluations in the bootstrapping procedure. Here we only consider the evaluations for the fraction part in bootstrapping to approximately compute the noise.
In step(1) of Section 3.2, we get the encryption of the Hamming weight of the vector σ(-j) with noise (ρ+log⁡Θ,0). The degree of theLagrange interpolating polynomial is θ, which can be implemented by a circuit of depth log⁡θ. So we obtain the ciphertexts encrypted the bit of the Hamming weight w-j,i with the noise (ρ+log⁡Θ+log⁡θ(log⁡Θ+log⁡Q+8),log⁡Θ).
In step(2), it needs to apply three-for-two trick ⌈log3/2n⌉+2 times. After implementing three-for-two trick one time, we get the ciphertexts with noise (ρ+log⁡Θ+(2+log⁡θ)(log⁡Θ+log⁡Q+8),log⁡Θ). Then we get the ciphertexts with noise (ρ+log⁡Θ+(2·(⌈log3/2n⌉+2)+log⁡θ)(log⁡Θ+log⁡Q+8),log⁡Θ) after implementing step (2).
The circuit which computes step(3) has multiplicative degree 4; we get the ciphertexts with noise(38)ρ+log⁡Θ+2·log3/2n+2+2+log⁡θlog⁡Θ+log⁡Q+8,log⁡Θ=ρ+log⁡Θ+2log3/2n+6+log⁡θlog⁡Θ+log⁡Q+8,log⁡ΘSet the depthL≥L′+1, namely, L=log⁡(θ·log4θ)+9, and η≥ρ+log⁡Θ+L(log⁡Θ+log⁡Q+8); the scheme CLTQ is correct and bootstrappable.According to the conditions for the parameters, one can takeρ=2λ, η=O~(2λ+log⁡Θ+L(log⁡Θ+log⁡Q+8))=O~(λ+LlogQ), γ=O~((2λ+log⁡Θ+Llog⁡Θ+log⁡Q+8)2log⁡λ)=O~(λ2+(LlogQ)2), κ=γη/ρ, τ=γ+2λ+2, and L=log⁡(λ·log4λ)+9.Note thatΘ is chosen so that the sparse subset sum problem is hard. We consider that Θ is unaffected by change of Q. We set θ=λ, then Θ=O(λ2) for any Q satisfying all the above conditions.The following theorem holds by the bootstrapping theorem proposed by Gentry in [2].Theorem 5.
Our schemeCLTQ with the above parameters setting is a pure fully homomorphic encryption.


### 4.3. Security

The FHE scheme over the integers isIND-CPA secure under the AGCD assumption. Our scheme just extends its message space from Z2 to ZQ and combines a squashing procedure before the bootstrapping. Thus, it is easy to see that the following theorem holds.Theorem 6.
Under the assumption that both of AGCD and SSSP are hard, our schemeCLTQ isIND-CPA secure.


### 4.4. Efficiency

As mentioned in [18], to evaluate a mod-Q arithmetic circuit with FHE scheme over the integers, one could either use the FHE scheme with large message space directly or first convert the arithmetic circuit to a Boolean one and then evaluate that converted circuit using an FHE scheme with binary message space.We denoteBAddQ and BMultQ as the Boolean circuits to perform addition and multiplication on two n-bit integers modulus Q as in [18], and we have the following numbers of AND gates for BAddQ and BMultQ.Proposition 7 (see [18]).
For ann-bit prime Q, BAddQ uses 9n AND gates, and BMultQ uses 17n2 AND gates.We denoteConvert-CLT2 the FHE scheme obtained from CLT2 with binary message space using the converting circuit with the BAddQ and BMultQ. Note that, for the scheme CLT2, the decryption is implemented by a circuit of degree of 2θ=2λ as presented in [4], in which the number of multiplication equals θ2=λ2. Just like [18], we compare Convert-CLT2 and CLTQ in terms of the size of the ciphertexts and the time complexity of basic operations carried out during homomorphic evaluation.


#### 4.4.1. Comparing the Size of the Ciphertexts

The ciphertext sizeγQ of CLTQ equals O~((λ+Llog⁡λ+log⁡Q)2log⁡λ) and grows in the log⁡Q when Q grows. Proposition 8 tells us that the ciphertext size of CLTQ is almost the same as that of Convert-CLT2 when log⁡Q∈[6,200].Proposition 8.
For a given security parameterλ, and any prime Q, let γ2′=γ2·log⁡Q. Then we have (39)γ2′γQ~log⁡Q·2λ+2log⁡λ+log⁡λ+22log⁡λ+922λ+2log⁡λ+log⁡λ·log4λ+92log⁡λ+log⁡Q+82.Proof.
We haveγQ=O~((2λ+log⁡Θ+Llog⁡Θ+log⁡Q+8)2log⁡λ), where the implied constant does not depend on Q. Since LQ=log(λ·log4λ)+9 for odd prime Q>2, and L2=log⁡λ+2 for Q=2; thus, (40)γ2′γQ~log⁡Q·γ2γQ~log⁡Q·2λ+log⁡Θ+L2log⁡Θ+922λ+log⁡Θ+LQlog⁡λ+log⁡Q+82~log⁡Q·2λ+2log⁡λ+log⁡λ+22log⁡λ+922λ+2log⁡λ+logλ·log4λ+92logλ+logQ+82.In Figure1, we show that the value of γ2′/γQ as a function of log⁡Q for the case λ=64. It tells us that the ciphertext size of CLTQ is a little shorter than Convert-CLT2. When 8≤log⁡Q≤81, namely, 256≤Q<281, we have 1<γ2′/γQ<1.4. Roughly speaking, we say that the ciphertexts for the scheme CLTQ and Convert-CLT2 have almost the same size.Figure 1
The rate of the ciphertext sizes forλ=64.


#### 4.4.2. Comparing the Speed of Homomorphic Operations

Now, we would like to compare the speed of homomorphic operations inConvert-CLT2 and CLTQ. That speed is essentially determined by the cost of homomorphic multiplication modulo Q.Proposition 9.
For a given security parameterλ, and any prime Q, let T2′ be the time complexity of carrying out a multiplication modQ in Convert-CLT2, and TQ be the time complexity of a single ciphertext refresh operation in CLTQ. Then we have (41)T2′TQ≤17log⁡Q·λlog⁡λ·log⁡Q·γ2γQ.Proof.
For any primeQ, let tQ be the time complexity of ciphertexts multiplication. Then TQ is tQ multiplied by the number of multiplications in decryption circuit, and T2′ is T2 multiplied by the number of AND gates in BMultQ circuit.
As far as we know, the best time complexity fork-bit multiplication is klogk2O(log∗k), where log∗k represents the iterated logarithm [20]. In our case, k is γQ and(42)log⁡γQ=log⁡O~2λ+log⁡Θ+Llog⁡Θ+log⁡Q+82log⁡λ=log⁡log⁡λ+2log⁡2λ+log⁡Θ+Llog⁡Θ+log⁡Q+8+constant<2log⁡λ+log⁡Qlog⁡λ+constant, while log⁡γ2>2log⁡(λ+log2λ)+constant.
Then forQ=poly(λ), even for Q=exp⁡(λ), the effect of log⁡Q is dominated by that of λ, so we can estimate t2/tQ by γ2/γQ, since we can ignore effect of Q in the part logγQ2O(log∗γQ).
By Proposition2, we have that the number of multiplications of the decryption for CLTQ scheme is about θlog⁡θ, while for CLT2, it is about θ2. On the other hand, we need 17log2Q AND gates for the Boolean circuit BMultQ as in Proposition 7. Then we have (43)T2′TQ≤17log2Q·θ2θlog⁡θ·t2tQ~17log2Q·θlog⁡θ·γ2γQ~17log⁡Q·θlog⁡θ·log⁡Q·γ2γQIn Figure2, we show the value of T2′/TQ as a function of log⁡Q for the case λ=64, which tells us that homomorphic multiplication for CLTQ increase performance as Q grows.Figure 2
The rate of the time complexity forλ=64.Remark 10.
Forλ=64, the value of γ2′/γQ climbs up and then declines as log⁡Q grows as shown in Figure 1. If Q=64,Q=256, it is 0.8548 and 1.0007, respectively. The value of T2′/TQ becomes much large as log⁡Q grows and has an upper bound close to 25447 for λ=64 as shown in Figure 2. Table 3 shows the efficiency of CLT2 measured against CLTQ for some primes Q.Table 3
The value ofγ2′/γQ and T2′/TQ.
λ log ⁡ Q γ2′/γQ T 2 ′ / T Q 64 log ⁡ Q = 6 0.8548 930.0392 64 log ⁡ Q = 7 0.9366 1186.9155 64 log ⁡ Q = 8 1.0073 1461.2334 64 log ⁡ Q = 32 1.3637 7983.0041 64 log ⁡ Q = 81 1.004 14751.7915 64 log ⁡ Q = 82 0.9963 14838.0201


## 4.1. FHE Scheme with Message SpaceZQ

In this subsection, we describe an FHE scheme over the integers for message spaceZQ for a prime modulus Q, where Q can be any prime bigger than the security parameter λ, denoted by CLTQ.For anη-bit odd integer p, and an integer q0 in [0,2γ/p2), we define the set (31)Dp,q0ρ=p2·q+r:Chooseq⟵0,q0,r⟵-2ρ,2ρ.C L T Q . K e y G e n ( 1 λ ). Generate a η-bit prime p and a γ-bit integer x0=p2·q0+r0 with r0←(-2ρ,2ρ) and q0←[0,2γ/p2).( 1 ) Generate the public key for encryption. For 1≤i≤τ, sample xi←Dp,q0ρ, y′←Dp,q0ρ and y=y′+⌊p/Q⌋.( 2 ) Generate the public key for multiplication. Let v′ be a vector of Θ numbers with κ bit of precision following the binary point, denoted by v′=(v1′,…,vΘ′). Choose uniformly a Θ-bit vector s′=(s1′,s2′,…,sΘ′)∈{0,1}Θ at random such that (32)Q·2ηp2=s′,v′+ϵmodQ2ηwith |ϵ|<2-κ. Then, define (33)α=q·p2+r+PowersofTwos′·p2η+1,where the components of q are randomly chosen from [0,q0)∩Z and those of r from (-2ρ,2ρ)∩Z.(3) Generate the public key for bootstrapping. Choose uniformly aΘ-bit vector s=(s1,s2,…,sΘ)∈{0,1}Θ at random, with Hamming weight θ.Choose a random integervi∈[0,Qκ+1) such that ∑i=1Θsi·vi=⌊Qκ+1/p⌉ and set Z=⌊2κ(pmodQ)/p⌉=⌊2κ/p⌉.For0≤i≤Θ, choose ui←[0,2log⁡Q+κ+1)∩Z in such a way that ∑i=1Θsiui=Zmod2κ+1. Set yi=ui/2κ, and denote it by the vector y=(y1,y2,…,yΘ). Then ∑i=1Θsiyi=1/p-εp for some |εp|<2-κ.Forn=⌈log⁡θ⌉+3, generate the vector β=(β1,…,βΘ): (34)βi=qi·p2+pQ·si+ri,where qi∈[0,q0) and ri∈(-2ρ,2ρ) for 1≤i≤Θ.Output the secret keysk=(p,s1,s2,…,sΘ), and the public key pk={x0,y,x1,…,xτ,v′,α,y,β}.C L T Q . E n c ( p k , m ). Given a message m∈ZQ, uniformly sample a subset S⊆{1,2,…,τ}, and output (35)c=∑i∈Sxi+y·mx0C L T Q . D e c ( s k , c ). Given a ciphertext c, output m=[⌊Qc/p⌉]Q.C L T Q . A d d ( p k , c 1 , c 2 ). Given two ciphertexts c1,c2, output cadd=[c1+c2]x0.C o n v e r t ( p k , c ). Given a ciphertext c, output c′=2〈α,BitDecompη(c)〉, where c=(⌊c·vi′⌉mod2η)1≤i≤Θ.C L T Q . M u l t ( p k , c 1 , c 2 ). Given two ciphertexts c1,c2, output cmult=[Convert(pk,c1·c2)]x0.C L T Q . M u l t C o n s ( p k , c , a ). Given a ciphertext c and a constant a∈ZQ, output cmultcons=[a·c]x0.C L T Q . R e c r y p t ( p k , c , D ε ). Given a ciphertext c for a message m, for i=1,2,…,Θ, compute zi=[Qc·yi], keeping only n=⌈log⁡θ⌉+3 bits of precision after binary point. Denote the binary representation of zi as zi=(…,zi,1,zi,0.zi,-1,…,zi,-n)2. And given the decryption Dε, which is (36)m=QcpQ=∑i=1ΘsiziQ,output a refreshed ciphertextc′=[⌊∑i=1Θβizi⌉]x0. The algorithm homomorphically evaluates the decryption circuit on the encryptions of the secret key bits (s1,s2,…,sΘ), referring to the bootstrapping process in Section 3 for more details.


## 4.2. Correctness

In this subjection, we prove the correctness of the homomorphic procedure.For the schemeCLTQ, the ciphertext has the form that c=q·2+(Qr∗+m)⌊p/Q⌋+r with two kinds of noise r and r∗. In [7], it is called a ciphertext with noise (ρ,ρ∗) if |r|<2ρ and |r∗|<2ρ∗. The authors of [15] proposed a noise growth analysis during the homomorphic addition and multiplication as shown in Lemma 3.Lemma 3 (Lemma 3 in [15]).
Letc1 and c2 be ciphertext with (ρ1,ρ1∗) and (ρ2,ρ2∗), respectively. Let ρ=max(ρ1,ρ2) and ρ∗=max(ρ1∗,ρ2∗).(i)
CLTQ.Add(pk,c1,c2) is a ciphertext with noise (ρ+2,ρ∗+1)(ii)
CLTQ.Mult(pk,c1,c2) is a ciphertext with noise (ρ+ρ∗+log⁡Q+8,log⁡Θ).Supposeρ∗≤log⁡Θ during the homomorphic evaluation. By Lemma 3, for the CLT scheme, the noise length in bits has only grown by an additive factor (log⁡Θ+log⁡Q+8). The noise growth during homomorphic evaluation is linear; then we have the following.Lemma 4 (recryption noise).
Letc be a ciphertext for a message m∈ZQ; CLTQ.Recrypt(pk,c,Dε) is a ciphertext with noise (37)ρ+log⁡Θ+L′log⁡λ+log⁡Q,log⁡Θ,where the depth of decryption L′ is (2·⌈log3/2n⌉+6+log⁡θ), less than (log(θlog4θ)+8).Proof.
The decryption circuitDε has been described in Section 3. We get the refreshed ciphertext c′=[⌊∑i=1Θβizi⌉]x0, where the noise of encryption of the secret key bit βi is (ρ,0). We describe the noise increasing with homomorphic evaluations in the bootstrapping procedure. Here we only consider the evaluations for the fraction part in bootstrapping to approximately compute the noise.
In step(1) of Section 3.2, we get the encryption of the Hamming weight of the vector σ(-j) with noise (ρ+log⁡Θ,0). The degree of theLagrange interpolating polynomial is θ, which can be implemented by a circuit of depth log⁡θ. So we obtain the ciphertexts encrypted the bit of the Hamming weight w-j,i with the noise (ρ+log⁡Θ+log⁡θ(log⁡Θ+log⁡Q+8),log⁡Θ).
In step(2), it needs to apply three-for-two trick ⌈log3/2n⌉+2 times. After implementing three-for-two trick one time, we get the ciphertexts with noise (ρ+log⁡Θ+(2+log⁡θ)(log⁡Θ+log⁡Q+8),log⁡Θ). Then we get the ciphertexts with noise (ρ+log⁡Θ+(2·(⌈log3/2n⌉+2)+log⁡θ)(log⁡Θ+log⁡Q+8),log⁡Θ) after implementing step (2).
The circuit which computes step(3) has multiplicative degree 4; we get the ciphertexts with noise(38)ρ+log⁡Θ+2·log3/2n+2+2+log⁡θlog⁡Θ+log⁡Q+8,log⁡Θ=ρ+log⁡Θ+2log3/2n+6+log⁡θlog⁡Θ+log⁡Q+8,log⁡ΘSet the depthL≥L′+1, namely, L=log⁡(θ·log4θ)+9, and η≥ρ+log⁡Θ+L(log⁡Θ+log⁡Q+8); the scheme CLTQ is correct and bootstrappable.According to the conditions for the parameters, one can takeρ=2λ, η=O~(2λ+log⁡Θ+L(log⁡Θ+log⁡Q+8))=O~(λ+LlogQ), γ=O~((2λ+log⁡Θ+Llog⁡Θ+log⁡Q+8)2log⁡λ)=O~(λ2+(LlogQ)2), κ=γη/ρ, τ=γ+2λ+2, and L=log⁡(λ·log4λ)+9.Note thatΘ is chosen so that the sparse subset sum problem is hard. We consider that Θ is unaffected by change of Q. We set θ=λ, then Θ=O(λ2) for any Q satisfying all the above conditions.The following theorem holds by the bootstrapping theorem proposed by Gentry in [2].Theorem 5.
Our schemeCLTQ with the above parameters setting is a pure fully homomorphic encryption.


## 4.3. Security

The FHE scheme over the integers isIND-CPA secure under the AGCD assumption. Our scheme just extends its message space from Z2 to ZQ and combines a squashing procedure before the bootstrapping. Thus, it is easy to see that the following theorem holds.Theorem 6.
Under the assumption that both of AGCD and SSSP are hard, our schemeCLTQ isIND-CPA secure.


## 4.4. Efficiency

As mentioned in [18], to evaluate a mod-Q arithmetic circuit with FHE scheme over the integers, one could either use the FHE scheme with large message space directly or first convert the arithmetic circuit to a Boolean one and then evaluate that converted circuit using an FHE scheme with binary message space.We denoteBAddQ and BMultQ as the Boolean circuits to perform addition and multiplication on two n-bit integers modulus Q as in [18], and we have the following numbers of AND gates for BAddQ and BMultQ.Proposition 7 (see [18]).
For ann-bit prime Q, BAddQ uses 9n AND gates, and BMultQ uses 17n2 AND gates.We denoteConvert-CLT2 the FHE scheme obtained from CLT2 with binary message space using the converting circuit with the BAddQ and BMultQ. Note that, for the scheme CLT2, the decryption is implemented by a circuit of degree of 2θ=2λ as presented in [4], in which the number of multiplication equals θ2=λ2. Just like [18], we compare Convert-CLT2 and CLTQ in terms of the size of the ciphertexts and the time complexity of basic operations carried out during homomorphic evaluation.


### 4.4.1. Comparing the Size of the Ciphertexts

The ciphertext sizeγQ of CLTQ equals O~((λ+Llog⁡λ+log⁡Q)2log⁡λ) and grows in the log⁡Q when Q grows. Proposition 8 tells us that the ciphertext size of CLTQ is almost the same as that of Convert-CLT2 when log⁡Q∈[6,200].Proposition 8.
For a given security parameterλ, and any prime Q, let γ2′=γ2·log⁡Q. Then we have (39)γ2′γQ~log⁡Q·2λ+2log⁡λ+log⁡λ+22log⁡λ+922λ+2log⁡λ+log⁡λ·log4λ+92log⁡λ+log⁡Q+82.Proof.
We haveγQ=O~((2λ+log⁡Θ+Llog⁡Θ+log⁡Q+8)2log⁡λ), where the implied constant does not depend on Q. Since LQ=log(λ·log4λ)+9 for odd prime Q>2, and L2=log⁡λ+2 for Q=2; thus, (40)γ2′γQ~log⁡Q·γ2γQ~log⁡Q·2λ+log⁡Θ+L2log⁡Θ+922λ+log⁡Θ+LQlog⁡λ+log⁡Q+82~log⁡Q·2λ+2log⁡λ+log⁡λ+22log⁡λ+922λ+2log⁡λ+logλ·log4λ+92logλ+logQ+82.In Figure1, we show that the value of γ2′/γQ as a function of log⁡Q for the case λ=64. It tells us that the ciphertext size of CLTQ is a little shorter than Convert-CLT2. When 8≤log⁡Q≤81, namely, 256≤Q<281, we have 1<γ2′/γQ<1.4. Roughly speaking, we say that the ciphertexts for the scheme CLTQ and Convert-CLT2 have almost the same size.Figure 1
The rate of the ciphertext sizes forλ=64.


### 4.4.2. Comparing the Speed of Homomorphic Operations

Now, we would like to compare the speed of homomorphic operations inConvert-CLT2 and CLTQ. That speed is essentially determined by the cost of homomorphic multiplication modulo Q.Proposition 9.
For a given security parameterλ, and any prime Q, let T2′ be the time complexity of carrying out a multiplication modQ in Convert-CLT2, and TQ be the time complexity of a single ciphertext refresh operation in CLTQ. Then we have (41)T2′TQ≤17log⁡Q·λlog⁡λ·log⁡Q·γ2γQ.Proof.
For any primeQ, let tQ be the time complexity of ciphertexts multiplication. Then TQ is tQ multiplied by the number of multiplications in decryption circuit, and T2′ is T2 multiplied by the number of AND gates in BMultQ circuit.
As far as we know, the best time complexity fork-bit multiplication is klogk2O(log∗k), where log∗k represents the iterated logarithm [20]. In our case, k is γQ and(42)log⁡γQ=log⁡O~2λ+log⁡Θ+Llog⁡Θ+log⁡Q+82log⁡λ=log⁡log⁡λ+2log⁡2λ+log⁡Θ+Llog⁡Θ+log⁡Q+8+constant<2log⁡λ+log⁡Qlog⁡λ+constant, while log⁡γ2>2log⁡(λ+log2λ)+constant.
Then forQ=poly(λ), even for Q=exp⁡(λ), the effect of log⁡Q is dominated by that of λ, so we can estimate t2/tQ by γ2/γQ, since we can ignore effect of Q in the part logγQ2O(log∗γQ).
By Proposition2, we have that the number of multiplications of the decryption for CLTQ scheme is about θlog⁡θ, while for CLT2, it is about θ2. On the other hand, we need 17log2Q AND gates for the Boolean circuit BMultQ as in Proposition 7. Then we have (43)T2′TQ≤17log2Q·θ2θlog⁡θ·t2tQ~17log2Q·θlog⁡θ·γ2γQ~17log⁡Q·θlog⁡θ·log⁡Q·γ2γQIn Figure2, we show the value of T2′/TQ as a function of log⁡Q for the case λ=64, which tells us that homomorphic multiplication for CLTQ increase performance as Q grows.Figure 2
The rate of the time complexity forλ=64.Remark 10.
Forλ=64, the value of γ2′/γQ climbs up and then declines as log⁡Q grows as shown in Figure 1. If Q=64,Q=256, it is 0.8548 and 1.0007, respectively. The value of T2′/TQ becomes much large as log⁡Q grows and has an upper bound close to 25447 for λ=64 as shown in Figure 2. Table 3 shows the efficiency of CLT2 measured against CLTQ for some primes Q.Table 3
The value ofγ2′/γQ and T2′/TQ.
λ log ⁡ Q γ2′/γQ T 2 ′ / T Q 64 log ⁡ Q = 6 0.8548 930.0392 64 log ⁡ Q = 7 0.9366 1186.9155 64 log ⁡ Q = 8 1.0073 1461.2334 64 log ⁡ Q = 32 1.3637 7983.0041 64 log ⁡ Q = 81 1.004 14751.7915 64 log ⁡ Q = 82 0.9963 14838.0201


## 4.4.1. Comparing the Size of the Ciphertexts

The ciphertext sizeγQ of CLTQ equals O~((λ+Llog⁡λ+log⁡Q)2log⁡λ) and grows in the log⁡Q when Q grows. Proposition 8 tells us that the ciphertext size of CLTQ is almost the same as that of Convert-CLT2 when log⁡Q∈[6,200].Proposition 8.
For a given security parameterλ, and any prime Q, let γ2′=γ2·log⁡Q. Then we have (39)γ2′γQ~log⁡Q·2λ+2log⁡λ+log⁡λ+22log⁡λ+922λ+2log⁡λ+log⁡λ·log4λ+92log⁡λ+log⁡Q+82.Proof.
We haveγQ=O~((2λ+log⁡Θ+Llog⁡Θ+log⁡Q+8)2log⁡λ), where the implied constant does not depend on Q. Since LQ=log(λ·log4λ)+9 for odd prime Q>2, and L2=log⁡λ+2 for Q=2; thus, (40)γ2′γQ~log⁡Q·γ2γQ~log⁡Q·2λ+log⁡Θ+L2log⁡Θ+922λ+log⁡Θ+LQlog⁡λ+log⁡Q+82~log⁡Q·2λ+2log⁡λ+log⁡λ+22log⁡λ+922λ+2log⁡λ+logλ·log4λ+92logλ+logQ+82.In Figure1, we show that the value of γ2′/γQ as a function of log⁡Q for the case λ=64. It tells us that the ciphertext size of CLTQ is a little shorter than Convert-CLT2. When 8≤log⁡Q≤81, namely, 256≤Q<281, we have 1<γ2′/γQ<1.4. Roughly speaking, we say that the ciphertexts for the scheme CLTQ and Convert-CLT2 have almost the same size.Figure 1
The rate of the ciphertext sizes forλ=64.


## 4.4.2. Comparing the Speed of Homomorphic Operations

Now, we would like to compare the speed of homomorphic operations inConvert-CLT2 and CLTQ. That speed is essentially determined by the cost of homomorphic multiplication modulo Q.Proposition 9.
For a given security parameterλ, and any prime Q, let T2′ be the time complexity of carrying out a multiplication modQ in Convert-CLT2, and TQ be the time complexity of a single ciphertext refresh operation in CLTQ. Then we have (41)T2′TQ≤17log⁡Q·λlog⁡λ·log⁡Q·γ2γQ.Proof.
For any primeQ, let tQ be the time complexity of ciphertexts multiplication. Then TQ is tQ multiplied by the number of multiplications in decryption circuit, and T2′ is T2 multiplied by the number of AND gates in BMultQ circuit.
As far as we know, the best time complexity fork-bit multiplication is klogk2O(log∗k), where log∗k represents the iterated logarithm [20]. In our case, k is γQ and(42)log⁡γQ=log⁡O~2λ+log⁡Θ+Llog⁡Θ+log⁡Q+82log⁡λ=log⁡log⁡λ+2log⁡2λ+log⁡Θ+Llog⁡Θ+log⁡Q+8+constant<2log⁡λ+log⁡Qlog⁡λ+constant, while log⁡γ2>2log⁡(λ+log2λ)+constant.
Then forQ=poly(λ), even for Q=exp⁡(λ), the effect of log⁡Q is dominated by that of λ, so we can estimate t2/tQ by γ2/γQ, since we can ignore effect of Q in the part logγQ2O(log∗γQ).
By Proposition2, we have that the number of multiplications of the decryption for CLTQ scheme is about θlog⁡θ, while for CLT2, it is about θ2. On the other hand, we need 17log2Q AND gates for the Boolean circuit BMultQ as in Proposition 7. Then we have (43)T2′TQ≤17log2Q·θ2θlog⁡θ·t2tQ~17log2Q·θlog⁡θ·γ2γQ~17log⁡Q·θlog⁡θ·log⁡Q·γ2γQIn Figure2, we show the value of T2′/TQ as a function of log⁡Q for the case λ=64, which tells us that homomorphic multiplication for CLTQ increase performance as Q grows.Figure 2
The rate of the time complexity forλ=64.Remark 10.
Forλ=64, the value of γ2′/γQ climbs up and then declines as log⁡Q grows as shown in Figure 1. If Q=64,Q=256, it is 0.8548 and 1.0007, respectively. The value of T2′/TQ becomes much large as log⁡Q grows and has an upper bound close to 25447 for λ=64 as shown in Figure 2. Table 3 shows the efficiency of CLT2 measured against CLTQ for some primes Q.Table 3
The value ofγ2′/γQ and T2′/TQ.
λ log ⁡ Q γ2′/γQ T 2 ′ / T Q 64 log ⁡ Q = 6 0.8548 930.0392 64 log ⁡ Q = 7 0.9366 1186.9155 64 log ⁡ Q = 8 1.0073 1461.2334 64 log ⁡ Q = 32 1.3637 7983.0041 64 log ⁡ Q = 81 1.004 14751.7915 64 log ⁡ Q = 82 0.9963 14838.0201


## 5. Conclusion

We propose an FHE scheme over the integers with message spaceZQ for any prime Q>θ. If we set θ=λ, the decryption circuit of this scheme is expressed as a polynomial of multiplicative degree 108·θlog3θ=O(λlog3λ), which is independent of the modulus Q except the constraint Q>λ. And we also reduce the number of multiplications in the decryption circuit which is better than most of previous work.To explore our squashed decryption circuit is worthwhile for large values ofQ, we present a variant of leveled FHE scheme CLT that supports arbitrarily homomorphic operations in the message space ZQ for Q>λ. By comparing the two schemes CLTQ and Convert-CLT2, we have seen that the two schemes have almost the same ciphertext size, but the former is significantly preferable.



---

*Source: 6520258-2018-07-29.xml*