# Efficient GSW-Style Fully Homomorphic Encryption over the Integers

Authors: Jianan Zhao; Ruwei Huang; Bo Yang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

We propose a GSW-style fully homomorphic encryption scheme over the integers (FHE-OI) that is more efficient than the prior work by Benarroch et al. (PKC 2017). To reduce the expansion of ciphertexts, our scheme consists of two types of ciphertexts: integers and vectors. Moreover, the computational efficiency in the homomorphic evaluation can be improved by hybrid homomorphic operations between integers and vectors. In particular, when performing vector-integer multiplications, the evaluation has the computational complexity ofΟγlogγ and thus outperforms all prior FHE-OI schemes. To slow down the noise growth in homomorphic multiplications, we introduce a new noise management method called sequentialization; therefore, the noise in the resulting ciphertext increases by a factor of l⋅polyλ rather than polyλl in general multiplications, where l is the number of multiplications. As a result, the circuit with larger multiplicative depth can be evaluated under the same parameter settings. Finally, to further reduce the size of ciphertexts, we apply ciphertext truncation and obtain the integer ciphertext of size Ολlogλ, thus additionally reducing the size of the vector ciphertext in Benarroch’s scheme from Ο˜λ4 to Ολ2log2λ.


---

## Body

## 1. Introduction

Fully homomorphic encryption (FHE) allows us to evaluate any computable function on plaintextm but only manipulate the ciphertexts; moreover, this procedure will not reveal any private information. With this property, FHE can be applied to outsourcing computation, particularly in the scenario that the remote server is an untrusted third party.FHE has received major attention in cryptography since the first breakthrough by Gentry [1]. In Gentry’s blueprint, the first step is to construct a somewhat homomorphic encryption (SWHE) scheme based on ideal lattices, which can only evaluate a circuit of low depth since the ciphertext contains a noise component that grows exponentially after homomorphic multiplications. If the noise magnitude passes a predeﬁned threshold, the correctness of decryption will no longer remain. Then, by a key procedure called bootstrapping, the noise magnitude in the ciphertext can be reduced to the same level as that in the original ciphertext, and therefore, the SWHE scheme can be converted into an FHE scheme to evaluate a circuit of arbitrary depth. However, the costly bootstrapping procedure becomes a bottleneck in making this FHE scheme practical, and the complicated operations on ideal lattices become incomprehensible. Very shortly afterward, van Dijk, Gentry, Halevi, and Vaikuntanathan (DGHV) [2] proposed an alternative FHE scheme over the integers (FHE-OI) that is conceptually simpler than [1] since the homomorphic operations only consist of arithmetic operations on integers instead of ideal lattices. In addition, the scheme is based on a different hardness assumption, namely, the approximate greatest common divisor (AGCD) assumption [3]. Unfortunately, this scheme is still inefficient since it follows Gentry’s blueprint, which has a costly bootstrapping procedure. Moreover, the large size of public keys results in an increased storage requirement.In order to improve the efficiency and avoid bootstrapping, a new noise management technique called modulus switching was proposed by Brakerski et al. [4]. The authors first constructed an SWHE scheme based on the learning with errors (LWE) assumption. Then, by applying modulus switching, the noise component in the ciphertext grows only linearly after homomorphic multiplications. As a result, they obtained a leveled FHE scheme that can evaluate any circuit with polynomial depth L by carefully calibrating L ladders of moduli. Later, this technique was adapted to the FHE-OI scheme [5]; however, it leads to a greater storage requirement since the circuit with multiplicative depth L needs to be evaluated via a procedure of key switching, and this requires storing L public keys. The larger size of public keys is an inherent property in AGCD-based FHE schemes compared to LWE-based ones; hence, the public keys of L times larger size yield a huge storage requirement. Afterward, a scale-invariant LWE-based FHE scheme was proposed by Brakerski [6]. In this scheme, the message m is encrypted to a higher bit and the same modulus is used throughout the homomorphic evaluation process. By applying the bit decomposition technique on ciphertexts and the encryptions of secret keys, the author obtained a leveled LWE-based FHE scheme whose noise growth was still linear after homomorphic multiplications. The scale-invariant technique was subsequently applied to the FHE-OI scheme and shown to be more efficient than [5]. At PKC 2014, Coron et al. [7] proposed a scale-invariant FHE-OI scheme (CLT14) where only an extra multiplication key needed to be stored in the original public keys, which significantly reduced the storage requirement compared with [5]. To ensure the security of the secret key, they encrypted it into a subset sum as the multiplication key and made a circular-secure assumption. At Eurocrypt 2015, Cheon et al. [8] proposed another scale-invariant FHE-OI scheme (CS15), which introduced a dimension-reduction technique to homomorphic multiplications; they also used invalid encryptions of the bits of the secret key as the multiplication key instead of using subset sum, but they still needed a circular-secure assumption.At Crypto 2013, Gentry, Sahai, and Waters (GSW) [9] proposed a conceptually simpler LWE-based leveled FHE scheme without using modulus switching and evaluation keys; however, the noise growth was still linear with the multiplicative depth. In this scheme, the plaintext bit m is extended into a plaintext vector by multiplying a gadget vector, and then each entry in the plaintext vector is encrypted to a vector ciphertext. Finally, the outputted ciphertext has the form of a matrix instead of a vector as in prior LWE-based FHE schemes. The homomorphic multiplication procedure is the general multiplicative operation between a ciphertext matrix and a decomposed binary ciphertext matrix. The main contribution of this scheme is the simple and natural homomorphic multiplication procedure rather than complicated modulus switching; however, it must generate a matrix ciphertext, which requires larger storage. This new FHE scheme was studied by Benarroch et al. [10], and they proposed a complete GSW-style FHE-OI scheme (BBL17). In this scheme, there is no need to encrypt the secret key as the multiplication key and make the circular-secure assumption; however, like [9], it must expand the ciphertext from integer to vector, and therefore the size of the vector ciphertext becomes a bottleneck to this scheme’s efficiency.Note that the above FHE schemes are the encryptions of the plaintextm of a single bit, and the message space in these schemes is m∈0,1. There have been some SIMD approaches to make the FHE-OI scheme more efficient in parallel. In [11], the authors proposed a new technique to encrypt a vector of messages in a single ciphertext based on the Chinese Reminder theorem (CRT), thereby extending the message space from m∈0,1 to m∈0,1l. This technique has been improved by subsequent studies [7, 10]. In [12], the authors proposed an optimized bootstrapping procedure for larger message spaces of a single bit from m∈0,1 to m∈ZQ, where Q is the arbitrary prime larger than two. Subsequently, some improvements have been proposed to accelerate this technique and apply it to the homomorphic evaluation procedure [13–19].From what has been discussed above, we can conclude that current FHE-OI schemes have significantly improved efficiency by adapting new noise management techniques from LWE-based schemes. While CLT14 [7] and CS15 [8] adapt the scale-invariant technique to obtain a leveled FHE-OI scheme and avoid costly bootstrapping procedures, the homomorphic evaluation procedure is still not efficient enough to be practical. Moreover, these schemes need to encrypt the secret key as the multiplication key and make a circular-secure assumption. Meanwhile, BBL17 [10] constructs a GSW-style FHE-OI scheme whose homomorphic multiplication procedure is a general multiplicative operation between vector and matrix, and the multiplication key is not needed. Unfortunately, it must expand the ciphertext from integer to vector, and this expansion renders difficult attempts to make this scheme more efficient. Therefore, how to improve the computational efficiency in homomorphic evaluation and reduce the ciphertext expansion have remained a challenging and open problem.Our Contribution. In this paper, we propose a GSW-style FHE-OI scheme that is similar to BBL17 [10] but has a better spatial and computational efficiency. The main contribution of our scheme is three-fold.Firstly, our scheme reduces the expansion of ciphertexts by generating two types of ciphertexts (vector and integer ciphertexts), and not only the vector ciphertexts as in BBL17 [10]. Besides, our scheme supports some hybrid homomorphic operations between integer and vector ciphertexts in the homomorphic evaluation procedure, such as vector-vector, vector-integer, and integer-integer operations. Since the vector ciphertext has a size of Ογ2, which is γ times larger than the integer ciphertext, it is easy to see that the vector-vector operations are more costly than the integer-integer and integer-vector operations. As a result, when performing integer-integer and integer-vector homomorphic operations, the computational efficiency in our scheme is better than that in BBL17 [10]. In particular, when performing vector-vector multiplications, the asymptotic computational complexity in our scheme is identical to the homomorphic multiplications in prior leveled FHE-OI schemes [7, 8, 10], i.e., there is a complexity of Ογ2logγ. However, when performing vector-integer multiplications, the asymptotic computational complexity in our scheme is Ογlogγ, which is better than that of all prior leveled FHE-OI schemes.Secondly, our scheme displays better noise management since it performs the homomorphic multiplications in sequence. The method of sequentialization in homomorphic multiplications was first proposed in [20, 21] and derived from the observation that the noise growth is asymmetric after the homomorphic multiplications in GSW-style FHE schemes based on LWE. We find that the noise terms in our scheme also have an asymmetric form such as r1+γ⋅r2 after homomorphic multiplications. Hence, if we perform homomorphic multiplications between L ciphertexts with the same noise magnitude r in the sequence, the resulting ciphertext will have a noise magnitude of ΟL⋅γ⋅r rather than ΟγL⋅r after general multiplications. Therefore, the circuit with a multiplicative depth larger than L can be evaluated under the same parameter settings as general multiplications.Finally, the size of ciphertexts in our scheme can be further reduced by applying a technique of ciphertext compression called truncation. This technique was first proposed in CS15 [8], and the authors obtained an integer ciphertext of size Ογ−ρ. However, they only made a simple and abstract description of their technique and had not constructed a complete scheme. Moreover, they set γ−ρ to be small to obtain better efficiency, but this has been proved to be insecure in subsequent works [22]. We adapt this technique to our scheme and generalize it to the vector ciphertext. In addition, we construct a complete scheme and make the tight analysis of noise growth. In order to thwart the optimized OL attack proposed in [22], we set γ−ρ=λlogλ+ΩLlogλ, which significantly reduces the size of ciphertexts. Finally, we obtain an integer ciphertext of size Ο˜λ+L and vector ciphertext of size Ο˜λ2+L2.


## 2. Preliminaries

### 2.1. Notation

We denote the parameters in our scheme by Greek letters (such asρ,η,γ,τ,λ). Scalars are denoted by lowercase Latin characters (such as p, q, x, y, and r). Vectors are denoted by lowercase bold English letters (such as p, q, x, y, and r). Matrices are denoted by uppercase English letters (such as P, Q, X, Y, and R). For two integers z and p, we denote by zp the result in −p/2,p/2 after computing zmodp. For an n-dimensional vector z and an integer p, we denote by zp the result in −p/2,p/2n after computing zimodp0≤i≤n−1n, where zi is the i-th coordinate in z. For a vector z, we denote the norm z to be the inﬁnity norm of z, i.e., z=z∞=maxziinzzi. For some real number r, we denote by r the nearest integer rounded to r, and we have r=r+δ, where δ∈−1/2,1/2∩ℝ. We denote a uniform distribution on a finite set A by U(A). All logarithms in this paper are base two.


### 2.2. Gadget Vector and Bit Decomposition Function

For some integern, define an n-dimensional gadget vector g=20,21,…,2n−1. Define a decomposition function g−1:0,2n⟶0,1n that can decompose an n-bit-length integer to its binary representation and output an n-dimensional binary vector. For some integer z, we have g−1z=b0,b1,…,bn−1T, where bi is the i-th least significant bit of z, and z=g,g−1z. Define an augmented decomposition function G−1:0,2nl⟶0,1n×l which can decompose an l-dimensional vector z=z0,z1,…,zl−1 to its binary representation and output an n×l-dimensional binary matrix such that G−1z=g−1z0,g−1z1,…,g−1zl−1 and z=g⋅G−1z.Lemma 1 (leftover hash lemma [2]).
Setx1,…,xm⟵ℤM uniformly and independently, set s1,…,sm⟵0,1, and set y=∑i=1msiximodM. Then x1,…,xm,y is 1/2M/2m-uniform over ZMm+1.We can write the above leftover hash lemma as the following version, and we can see the obvious equivalence between the two lemmas.Lemma 2.
Setx=x1,…,xm⟵ZM uniformly and independently, set s⟵0,1m, and let y=x,smodM. Then x,y is 1/2M/2m-uniform over ZMm+1.Lemma 3 (see [10]).
Setx=x1,…,xm⟵ZM uniformly and independently, and set S⟵0,1m×n for some n; and let y=x⋅SmodM. Then x,y is 1/2M/2m-uniform over ZMm+n.


### 2.3. Approximate GCD

Since the first FHE scheme based on the approximate greatest common divisor (AGCD) problem was proposed in DGHV [2], there have been some AGCD variants proposed. The first noise-free AGCD variant was proposed in [23]. It generates a special public key element x0=pq0 without noise component r0 and sets q0 to be a random square free 2λ-rough integer to thwart some attacks based on factorization. Afterward, the first decisional and noise-free AGCD variant was proposed in [11]. In homomorphic evaluation, a noise-free x0 will not introduce an extra noise component and will simplify the noise analysis; however, this could make the scheme vulnerable to thwart quantum attacks. Therefore, to improve the security, some decisional-AGCD variants with a noise component in x0 were proposed in [7, 8, 10]. In the present work, we consider the decisional noisy variant proposed in BBL17 [10], and formally define it as follows.Definition 1.
Letρ,η,γ,p be some integers satisfying γ>η>ρ>0, and p is an η-bit odd integer. Define the distribution Dγ,ρp supported over 0,2γ as follows:(1)Dγ,ρp=Sampleq⟵ℤ∩0,2γ/p,r⟵ℤ∩−2ρ,2ρ:Outputx=p⋅q+r.Definition 2.
((ρ,η,γ)-AGCD). The ρ,η,γ-AGCD problem is to find p when given polynomially many samples from Dγ,ρp. The ρ,η,γ-decisional-AGCD problem is to distinguish between Dγ,ρp and the uniform distribution U0,2γ∩ℤ when given polynomially many samples from Dγ,ρp and U0,2γ∩ℤ.
In the following, we define the truncated distribution and sample from this distribution via rejection sampling.Definition 3.
(see [10]). Let X be a distribution supported over Z, and let k∈Z. The distribution X≤k is the distribution X conditioned on X≤k. If PrX≤k=0, then X≤k is undefined. Analogously, we can define X≥k.Lemma 4.
Letx0>2γ−1. Then, the distribution Dγ,ρp<x0 and U0,2γ∩ℤ are computationally indistinguishable under the ρ,η,γ-decisional-AGCD assumption.Proof.
First, we samplexi⟵Dγ,ρp<x0 via rejection sampling. It is easy to see that the rejection probability when sampling each xi is at most 1/2 since x0>2γ−1. Therefore, the distribution Dγ,ρp<x0 is efficiently sampleable up to a negligible statistical distance with Dγ,ρp since PrDγ,ρp<x0<x0 is noticeable. Second, we replace the samplings of the xi’s by xi⟵U0,x0∩Z. Similar to the above procedure, we can deduce that the statistical distance between U0,x0∩Z and U0,2γ∩ℤ is negligible. Since the distribution Dγ,ρp and U0,2γ∩ℤ are computationally indistinguishable under the ρ,η,γ-decisional-AGCD assumption, we finally conclude that the distribution Dγ,ρp<x0 and U0,x0∩Z are computationally indistinguishable.


### 2.4. The GSW-Style FHE Scheme over the Integers

We recall the first complete GSW-style FHE-OI scheme proposed in BBL17 [10].(i)
BBL.Keygen1λ: Generate the public parameters params=γ,ρ,η,τ according to the security parameter λ. Sample uniformly an η-bit integer p. First sample an integer x0⟵Dγ,ρp>2γ−1 and then τ integers xi1≤i≤τ⟵Dγ,ρp<x0. Write x=x1,…xτ, let pk=params,x,x0 and sk=p.(ii)
BBL.Encpk,m: Randomly sample a matrix S⟵0,1τ×γ and compute(2)c=m⋅g+xSx0,which is a vector of dimensionγ=logx0.(iii)
BBL.Addx0,c1,c2: Given the public key element x0 and two ciphertexts c1 and c2, compute(3)cadd=c1+c2x0.Note that this addition procedure is done when it is known that at most one of the plaintext messages is 1.(iv)
BBL.Multx0,c1,c2: Given the public key element x0 and two ciphertexts c1 and c2, compute(4)cmult=c1⋅G−1c2x0.(v)
BBL.Decsk,c: Compute f=c⋅g−1p/2modp, and output the following:(5)m⟵1,Iff≥p/4,0,Iff<p/4.


## 2.1. Notation

We denote the parameters in our scheme by Greek letters (such asρ,η,γ,τ,λ). Scalars are denoted by lowercase Latin characters (such as p, q, x, y, and r). Vectors are denoted by lowercase bold English letters (such as p, q, x, y, and r). Matrices are denoted by uppercase English letters (such as P, Q, X, Y, and R). For two integers z and p, we denote by zp the result in −p/2,p/2 after computing zmodp. For an n-dimensional vector z and an integer p, we denote by zp the result in −p/2,p/2n after computing zimodp0≤i≤n−1n, where zi is the i-th coordinate in z. For a vector z, we denote the norm z to be the inﬁnity norm of z, i.e., z=z∞=maxziinzzi. For some real number r, we denote by r the nearest integer rounded to r, and we have r=r+δ, where δ∈−1/2,1/2∩ℝ. We denote a uniform distribution on a finite set A by U(A). All logarithms in this paper are base two.


## 2.2. Gadget Vector and Bit Decomposition Function

For some integern, define an n-dimensional gadget vector g=20,21,…,2n−1. Define a decomposition function g−1:0,2n⟶0,1n that can decompose an n-bit-length integer to its binary representation and output an n-dimensional binary vector. For some integer z, we have g−1z=b0,b1,…,bn−1T, where bi is the i-th least significant bit of z, and z=g,g−1z. Define an augmented decomposition function G−1:0,2nl⟶0,1n×l which can decompose an l-dimensional vector z=z0,z1,…,zl−1 to its binary representation and output an n×l-dimensional binary matrix such that G−1z=g−1z0,g−1z1,…,g−1zl−1 and z=g⋅G−1z.Lemma 1 (leftover hash lemma [2]).
Setx1,…,xm⟵ℤM uniformly and independently, set s1,…,sm⟵0,1, and set y=∑i=1msiximodM. Then x1,…,xm,y is 1/2M/2m-uniform over ZMm+1.We can write the above leftover hash lemma as the following version, and we can see the obvious equivalence between the two lemmas.Lemma 2.
Setx=x1,…,xm⟵ZM uniformly and independently, set s⟵0,1m, and let y=x,smodM. Then x,y is 1/2M/2m-uniform over ZMm+1.Lemma 3 (see [10]).
Setx=x1,…,xm⟵ZM uniformly and independently, and set S⟵0,1m×n for some n; and let y=x⋅SmodM. Then x,y is 1/2M/2m-uniform over ZMm+n.


## 2.3. Approximate GCD

Since the first FHE scheme based on the approximate greatest common divisor (AGCD) problem was proposed in DGHV [2], there have been some AGCD variants proposed. The first noise-free AGCD variant was proposed in [23]. It generates a special public key element x0=pq0 without noise component r0 and sets q0 to be a random square free 2λ-rough integer to thwart some attacks based on factorization. Afterward, the first decisional and noise-free AGCD variant was proposed in [11]. In homomorphic evaluation, a noise-free x0 will not introduce an extra noise component and will simplify the noise analysis; however, this could make the scheme vulnerable to thwart quantum attacks. Therefore, to improve the security, some decisional-AGCD variants with a noise component in x0 were proposed in [7, 8, 10]. In the present work, we consider the decisional noisy variant proposed in BBL17 [10], and formally define it as follows.Definition 1.
Letρ,η,γ,p be some integers satisfying γ>η>ρ>0, and p is an η-bit odd integer. Define the distribution Dγ,ρp supported over 0,2γ as follows:(1)Dγ,ρp=Sampleq⟵ℤ∩0,2γ/p,r⟵ℤ∩−2ρ,2ρ:Outputx=p⋅q+r.Definition 2.
((ρ,η,γ)-AGCD). The ρ,η,γ-AGCD problem is to find p when given polynomially many samples from Dγ,ρp. The ρ,η,γ-decisional-AGCD problem is to distinguish between Dγ,ρp and the uniform distribution U0,2γ∩ℤ when given polynomially many samples from Dγ,ρp and U0,2γ∩ℤ.
In the following, we define the truncated distribution and sample from this distribution via rejection sampling.Definition 3.
(see [10]). Let X be a distribution supported over Z, and let k∈Z. The distribution X≤k is the distribution X conditioned on X≤k. If PrX≤k=0, then X≤k is undefined. Analogously, we can define X≥k.Lemma 4.
Letx0>2γ−1. Then, the distribution Dγ,ρp<x0 and U0,2γ∩ℤ are computationally indistinguishable under the ρ,η,γ-decisional-AGCD assumption.Proof.
First, we samplexi⟵Dγ,ρp<x0 via rejection sampling. It is easy to see that the rejection probability when sampling each xi is at most 1/2 since x0>2γ−1. Therefore, the distribution Dγ,ρp<x0 is efficiently sampleable up to a negligible statistical distance with Dγ,ρp since PrDγ,ρp<x0<x0 is noticeable. Second, we replace the samplings of the xi’s by xi⟵U0,x0∩Z. Similar to the above procedure, we can deduce that the statistical distance between U0,x0∩Z and U0,2γ∩ℤ is negligible. Since the distribution Dγ,ρp and U0,2γ∩ℤ are computationally indistinguishable under the ρ,η,γ-decisional-AGCD assumption, we finally conclude that the distribution Dγ,ρp<x0 and U0,x0∩Z are computationally indistinguishable.


## 2.4. The GSW-Style FHE Scheme over the Integers

We recall the first complete GSW-style FHE-OI scheme proposed in BBL17 [10].(i)
BBL.Keygen1λ: Generate the public parameters params=γ,ρ,η,τ according to the security parameter λ. Sample uniformly an η-bit integer p. First sample an integer x0⟵Dγ,ρp>2γ−1 and then τ integers xi1≤i≤τ⟵Dγ,ρp<x0. Write x=x1,…xτ, let pk=params,x,x0 and sk=p.(ii)
BBL.Encpk,m: Randomly sample a matrix S⟵0,1τ×γ and compute(2)c=m⋅g+xSx0,which is a vector of dimensionγ=logx0.(iii)
BBL.Addx0,c1,c2: Given the public key element x0 and two ciphertexts c1 and c2, compute(3)cadd=c1+c2x0.Note that this addition procedure is done when it is known that at most one of the plaintext messages is 1.(iv)
BBL.Multx0,c1,c2: Given the public key element x0 and two ciphertexts c1 and c2, compute(4)cmult=c1⋅G−1c2x0.(v)
BBL.Decsk,c: Compute f=c⋅g−1p/2modp, and output the following:(5)m⟵1,Iff≥p/4,0,Iff<p/4.


## 3. Our Basic Scheme

In this section, we first describe the construction of our GSW-style FHE scheme. Then, we analyze the correctness and noise growth, and finally prove its underlying security.


### 3.1. Construction

Recall that for a speciﬁcη-bit odd integer p, we define the distribution as follows:(6)Dγ,ρp=Sampleq⟵ℤ∩0,2γ/p,r⟵ℤ∩−2ρ,2ρ:Outputx=p⋅q+r.(i)
HE.KeyGen1λ: Given a security parameter λ, choose the parameters ρ,γ,η,τ according to λ and some constraints to ensure the correctness and security (see analysis below). Sample uniformly an η-bit odd integer p. Sample an integer x0⟵Dγ,ρp>2γ−1 via rejection sampling. For 1≤i≤τ, sample xi⟵Dγ,ρp<x0 via rejection sampling, and define x=x1,…xτ. Sample an integer y⟵Dγ,ρp<x0 and resample until y/p is odd, write y=pq′+r′. Output the secret key sk=p and the public key pk=x0,x1,…,xτ,y.(ii)
HE.EncVecpk,m: Given a message m∈0,1, uniformly sample a matrix S⟵0,1τ×γ and output a γ-dimensional vector c:(7)c=m⋅g+xSx0.(iii)
HE.EncIntpk,m: Given a message m∈0,1, uniformly sample a vector s⟵0,1τ and output an integer c:(8)c=m⋅y2+x,sx0.(iv)
HE.Addci,ci: Given two ciphertexts ci or ci for i∈1,2, output the following:Integer-integer addition:(9)cadd=c1+c2x0.Vector-vector addition:(10)cadd=c1+c2x0.Integer-vector addition:(11)cadd=c1+c2⋅g−1y2x0.(v)
HE.Multci,ci: Given two ciphertexts ci or ci for i∈1,2, output the following:Vector-vector multiplication:(12)cmult=c1⋅G−1c2x0.Vector-integer multiplication:(13)cmult=c1⋅g−1c2x0.(vi)
HE.DecVecsk,c: Given a γ-dimensional vector ciphertext c, first compute c=c⋅g−1p/2, and then output the following:(14)m=2cp2.(vii)
HE.DecIntsk,c: Given an integer ciphertext c, output the following:(15)m=2cp2.


### 3.2. Analysis of Correctness and Noise Growth

We first prove the correctness of our scheme and analyze the noise growth in encryption, decryption, and homomorphic operations procedures. Then we convert our scheme into a leveled FHE-OI scheme by analyzing the multiplicative circuit depth L. Finally, we show that when performing homomorphic multiplications in sequence, the resulting ciphertext can have a smaller noise growth.Lemma 5 (Encryption noise of Integer Ciphertext).
Letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λ and c⟵HE.EncIntpk,m for a message m∈0,1, then(16)c=p2m+rmodp,where r≤2τ+12ρ.Proof.
For a public key element vectorx=x1,…xτ and a random vector s⟵0,1τ, it is easy to see that x,s=∑i∈Sxi, where xi=pqi+ri, and S⊆1,2,…,τ. Denote y/2=pq′/2+r′/2+δ, where δ∈−1/2,1/2∩ℝ; hence, we can write(17)c=m⋅y2+x,sx0=mpq′2+r′2+δ+∑i∈Sxi−kx0.
Sinceq′ is odd, we have modulo p and(18)c=p2m+∑i∈Sri−kr0+r′2+δmmodp,for some k∈0,τ∩Z. As a result, we have r=∑i∈Sri−kr0+r′/2+δm, where r≤τ2ρ+τ2ρ+2ρ−1+1/2≤2τ+12ρ.Lemma 6 (encryption noise of vector ciphertext).
Letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λ and c⟵HE.EncVecpk,m for a message m∈0,1; then,(19)c=mg+pq+r,where r≤2τ⋅2ρ.Proof.
For a public key elementxi=pqi+ri where i∈0,τ∩Z, write x=x1,…xτ=pq′+r′, with q′=q1,…,qτ and r′=r1,…,rτ. Then, we have(20)c=m⋅g+xSx0=m⋅g+p⋅q′S+r′S−kpq0+r0.
Defineq=q′S−kq0 and r=r′S−kr0, and then we have c=mg+pq+r. Since S∈0,1τ×γ and k∈0,τγ, we have r′S≤τ2ρ and kr0≤τ2ρ. Therefore, r=r′S−kr0≤r′S+kr0≤2τ⋅2ρ.Lemma 7 (noise of integer-integer addition).
Letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λ and ci⟵HE.EncIntpk,mi with ci=p/2mi+rimodp for i∈1,2 and mi∈0,1. Then,(21)cadd=p2m1+m2+rmodp,where r≤r1+r2+2ρ..Proof.
Sinceci=p/2mi+rimodp, we have(22)cadd=c1+c2x0=p2m1+m2+r1+r2−kr0modp,where k∈−1,1∩Z. Hence, we have r=r1+r2−kr0≤r1+r2+2ρ.Lemma 8 (noise of integer-vector addition).
Letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λ, c1⟵HE.EncIntpk,m1 with c1=p/2m1+r1modp and c2⟵HE.EncVecpk,m2 with c2=m2g+pq2+r2. Then,(23)cadd=p2m1+m2+rmodp,where r≤r1+γr2+γ2ρ.Proof.
Writec1=p/2m1+r1modp, c2=m2g+pq2+r2, and define(24)c2=c2⋅g−1y2=m2g+pq2+r2g−1y2=m2gg−1y2+pq2g−1y2+r2g−1y2=y2m2+pq2g−1y2+r2g−1y2=p2m2+r2g−1y2+r′2+δm2modp=p2m2+r2modp,where r2=r2g−1y/2+r′/2+δm2≤γr2+2ρ−1+1/2≤γr2+2ρ. Hence, we can write(25)cadd=c1+c2⋅g−1y2x0=c1+c2x0=p2m1+m2+r1+r2−kr0modp,for some k∈0,γ+2/2∩Z. As a result, we have r=r1+r2−kr0≤r1+γr2+2ρ+γ+22ρ−1≤r1+γr2+γ2ρ.Lemma 9 (noise of vector-vector addition).
Letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λ and ci⟵HE.EncVecpk,mi with ci=mig+pqi+ri for i∈1,2 and mi∈0,1. Then,(26)cadd=m1+m2g+pq+r,where r≤r1+r2+2ρ.Proof.
cadd=c1+c2x0=m1+m2g+pq1+q2−kq0+r1+r2−kr0, where k∈−1,1γ∩Zγ. Define q=q1+q2−kq0, and then we have cadd=m1+m2g+pq+r, where r=r1+r2−kr0. Hence, we have r≤r1+r2+kr0≤r1+r2+2ρ.Lemma 10 (noise of vector-vector multiplication).
Letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λ and ci⟵HE.EncVecpk,mi with ci=mig+pqi+ri for i∈1,2 and mi∈0,1. Then,(27)cmult=m1m2g+pq+r,where r≤γr1+r2+γ2ρ.Proof.
Writec1=m1g+pq1+r1 and c2=m2g+pq2+r2, and then we have(28)cmult=c1⋅G−1c2x0=m1g+pq1+r1G−1c2−kx0=m1gG−1c2+pq1G−1c2−kq0+r1G−1c2−kr0=m1m2g+pq2+r2+pq1G−1c2−kq0+r1G−1c2−kr0=m1m2g+pq1G−1c2−kq0+m1q2+r1G−1c2+m1r2−kr0.
Defineq=q1G−1c2−kq0+m1q2 and r=r1G−1c2+m1r2−kr0. Since c1⋅G−1c2≤γc1,c1≤x0/2 and c1⋅G−1c2−kx0≤x0/2, we have k∈0,γ+1/2∩Z; hence, we can write cmult=m1m2g+pq+r, where r≤r1G−1c2+m1r2+kr0≤γr1+r2+γ2ρ.Lemma 11 (noise of vector-integer multiplication).
Letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λmi∈0,1,c1⟵HE.EncVecpk,m1 with c1=m1g+pq1+r1 and c2⟵HE.EncIntpk,m2 with c2=p/2m2+r2modp. Then,(29)cmult=p2m1m2+rmodp,where r≤γr1+r2+γ2ρ.Proof.
Writec2=p/2m2+pq2+r2modp, and then we have(30)cmult=c1⋅g−1c2x0=m1g+pq1+r1g−1c2−kx0=m1gg−1c2+pq1g−1c2−kq0+r1g−1c2−kr0=m1p2m2+pq2+r2+pq1g−1c2−kq0+r1g−1c2−kr0=p2m1m2+pq1g−1c2+m1q2−kq0+r1g−1c2+m1r2−kr0=p2m1m2+r1g−1c2+m1r2−kr0modp=p2m1m2+rmodp,where r=r1g−1c2+m1r2−kr0 and k∈0,γ+1/2∩Z. As a result, we have r≤γr1+r2+γ2ρ.Lemma 12 (decryption noise of integer ciphertext).
Letsk=p⟵HE.KeyGen1λ and an integer ciphertext c with c=p/2m+rmodp for a message m∈0,1. Then,(31)HE.DecIntsk,c=2cp2=m,if r<p/4−1/2.Proof.
Writec=p/2m+pq+rmodp. Since p is odd, we have(32)2cp=2p+1/2m+pq+rp=m+2q+2r+mp,which is correctly decrypted to m when 2r+1/p<1/2. Hence, we have r<p/4−1/2.Lemma 13 (decryption noise of vector ciphertext).
Letsk=p⟵HE.KeyGen1λ and a vector ciphertext c with c=mg+pq+r for a message m∈0,1. Then,(33)HE.DecVecsk,c=2c⋅g−1p/2p2=m,if r<1/ηp/4−1/2.Proof.
For a ciphertextc=mg+pq+r, first compute(34)c=c⋅g−1p2=mg+pq+rg−1p2=mgg−1p2+pqg−1p2+rg−1p2=p2m+pq+r,where q=qg−1p/2 and r=rg−1p/2 with r≤ηr. By Lemma 12, the ciphertext c is correctly decrypted to m when r<p/4−1/2. Hence, we have r<1/ηp/4−1/2.
The following lemma shows that our HE scheme can be converted to a leveled FHE-OI scheme to evaluate any binary circuit with depthL if the parameters satisfy some constraints.Lemma 14.
Given any binary circuit C with depthL, the HE scheme can be converted to a leveled FHE-OI scheme to evaluate this circuit if(35)η−ρ≥Llogγ+1+log2τ+1+logη+2.Proof.
Assume that the given circuit C only consists of multiplication gates; then, a ciphertext will undergoL homomorphic multiplications. We first consider the vector-vector multiplications. For i∈1,L, let ci=mig+pqi+ri be the ciphertext after the i-th homomorphic multiplication, and c0 be a fresh ciphertext. Let Ri be the upper bound on the noise magnitude ri. First, we have R0=2τ2ρ by Lemma 6; then, after the i-th homomorphic multiplication, we have Ri=γ+1Ri−1+γ2ρ by Lemma 10. By solving the recurrence equation, we obtain(36)RL≤γ+1L2τ+12ρ−2ρ,which should be smaller than 1/ηp/4−1/2 for decryption correctness by Lemma 13. Hence, we have η−ρ≥Llogγ+1+log2τ+1+logη+2.
Note that vector-integer multiplications have a similar noise growth than vector-vector multiplications, and hence, we omit vector-integer multiplication in the analysis of vector-vector multiplication.Lemma 15 (sequentialization of homomorphic multiplication).
Letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λ and ci⟵HE.EncVecpk,mi with ci=mig+pqi+ri for i∈1,k∩ℤ and mi∈0,1, where k is an arbitrary positive integer larger than 1. Then, for any fixed multiplication sequence(37)c=c1G−1c2G−1⋅⋅⋅ck−1G−1ckx0x0x0,the noise component r in c satisfies r≤γr1+γr2⋅⋅⋅+γrk−1+rk+k−1γ2ρ≤k−12τ+1γ2ρ+τ2ρ+1.Proof.
Definec′=ck−1G−1ckx0; hence, r′≤γrk−1+rk+γ2ρ by Lemma 13. Define c″=ck−2G−1c′x0. Then we have r″≤γrk−2+r′+γ2ρ. By recursively performing the above procedure, we finally obtain a ciphertext c with the noise component r satisfying r≤γr1+γr2⋅⋅⋅+γrk−1+rk+k−1γ2ρ≤k−12τ+1γ2ρ+τ2ρ+1.
The above lemma implies that when we perform homomorphic multiplications betweenL+1 fresh ciphertexts and undergo at most L multiplications, if we operate these ciphertexts by a fixed multiplication sequence in Lemma 15, then the resulting ciphertext will have a noise growth of L2τ+1γ2ρ+τ2ρ+1. This growth is in contrast to the noise blowup in general homomorphic multiplications, i.e., γ+1L2τ+12ρ−2ρ in Lemma 14. This is a unique property in the GSW-style FHE scheme since the noise terms in ciphertexts grow asymmetrically. We can realize better noise management and evaluate a circuit with a multiplicative depth larger than L by applying this multiplication sequence in homomorphic evaluation.
Note that the method of sequentialization in homomorphic multiplication can also be applied to vector-integer multiplication since it has the same asymmetrical property as vector-vector multiplication and the noise growth is similar. Here we omit the analysis of vector-integer multiplication.


### 3.3. Parameters

We present some constraints in choosing parameters to ensure the correctness and security against known attacks. LetL be the circuit depth in homomorphic evaluation and let λ be the security parameter.ρ is the bit-length of the noise r in public key elements, and it should satisfy ρ≥λ to protect against brute force attacks on the noise [3, 5, 24, 25].η is the bit-length of the secret key p, and it should satisfy η≥ρ+Llogγ+1+log2τ+1+logη+2 to ensure decryption correctness (see Lemma 14).γ is the bit-length of the public key elements xi, y and it should satisfy γ≥Ωλ/logλη−ρ2 to thwart different lattice reduction attacks on the AGCD (as studied in [8]), such as orthogonal lattice attacks [2, 26], the simultaneous Diophantine approximation attack [27], and the multivariate polynomial attack [28].τ is the number of integers in the public keys, and it should satisfy τ=γ+Ωλ to be able to use the leftover hash lemma in the security proof.To satisfy the above constraints, we can take(38)ρ=λ,η=λ+ΩLlogλ,γ=ΩL2λlogλ,τ=γ+Ωλ.


### 3.4. Semantic Security

We show that the security of our HE scheme can be based on the decisional-AGCD problem; the main proof process is to show that it is difficult to distinguish the ciphertext from a uniform integer modulex0.Theorem 1.
The HE scheme is IND-CPA secure under theρ,η,γ-decisional-AGCD assumption.Proof.
We will use a three-step hybrid argument to prove that both the integer and vector ciphertexts in our HE scheme have computational indistinguishability and there is no such a probabilistic polynomial-time adversaryA that can distinguish these ciphertexts.
HybridH0: Let pk=x0,x,y⟵HE.KeyGen1λ), c⟵HE.EncVecpk,m=m⋅g+xSx0 and c⟵HE.EncIntpk,m=m⋅y/2+x,sx0 for a message m∈0,1. By the leftover hash lemma in Lemmas 2 and 3, the tuple (x,xS (mod x0),x,s (mod x0)) is within an exponentially small statistical distance by 1/2x0/τ=neglλ. As a result, the tuple (x,xS (mod x0),x,s (mod x0)c,c) is within an exponentially small statistical distance by neglλ, independent of the underlying plaintext. Hence, we have(39)PrH0A1λ,pk=1−PrH0A1λ,pk,c,c=1≤neglλ.
HybridH1: Let U be the uniform distribution over 0,2γ∩Z. In this hybrid, we replace the xis in the public keys by sampling from U0,2γ∩ℤ. We first sample x0′⟵U0,2γ∩Z>2γ−1 via rejection sampling. Then, we sample xi′⟵U0,2γ∩Z<x0 via rejection sampling for i∈1,τ∩Z, write x′=x1′,…,xτ′, and output pk′=x0′,x′,y. The resulting public key distribution is computationally indistinguishable from the genuine public key distribution in H0 by Lemma 4. Hence, we have(40)PrH0A1λ,pk=1−PrH1A1λ,pk′=1≤neglλ.
HybridH2: Define c′=m⋅g+x′Sx0′ and c′=m⋅y/2+x′,sx0′ for m∈0,1. By the leftover hash lemma in Lemmas 2 and 3, the tuple (x′,x′S (mod x0′),x′,s (mod x0′)) is within an exponentially small statistical distance by 1/2x0′/τ=neglλ. As a result, the tuple (x′,x′S (mod x0′),x′,s (mod x0′)c′,c′) is within an exponentially small statistical distance by neglλ, independent of the underlying plaintext. Hence, we have(41)PrH1A1λ,pk′=1−PrH2A1λ,pk′,c′,c′=1≤neglλ.
Finally, we conclude that(42)PrH0A1λ,pk,c,c=1−PrH2A1λ,pk′,c′,c′=1≤neglλ,which proves the IND-CPA security of the HE scheme.


## 3.1. Construction

Recall that for a speciﬁcη-bit odd integer p, we define the distribution as follows:(6)Dγ,ρp=Sampleq⟵ℤ∩0,2γ/p,r⟵ℤ∩−2ρ,2ρ:Outputx=p⋅q+r.(i)
HE.KeyGen1λ: Given a security parameter λ, choose the parameters ρ,γ,η,τ according to λ and some constraints to ensure the correctness and security (see analysis below). Sample uniformly an η-bit odd integer p. Sample an integer x0⟵Dγ,ρp>2γ−1 via rejection sampling. For 1≤i≤τ, sample xi⟵Dγ,ρp<x0 via rejection sampling, and define x=x1,…xτ. Sample an integer y⟵Dγ,ρp<x0 and resample until y/p is odd, write y=pq′+r′. Output the secret key sk=p and the public key pk=x0,x1,…,xτ,y.(ii)
HE.EncVecpk,m: Given a message m∈0,1, uniformly sample a matrix S⟵0,1τ×γ and output a γ-dimensional vector c:(7)c=m⋅g+xSx0.(iii)
HE.EncIntpk,m: Given a message m∈0,1, uniformly sample a vector s⟵0,1τ and output an integer c:(8)c=m⋅y2+x,sx0.(iv)
HE.Addci,ci: Given two ciphertexts ci or ci for i∈1,2, output the following:Integer-integer addition:(9)cadd=c1+c2x0.Vector-vector addition:(10)cadd=c1+c2x0.Integer-vector addition:(11)cadd=c1+c2⋅g−1y2x0.(v)
HE.Multci,ci: Given two ciphertexts ci or ci for i∈1,2, output the following:Vector-vector multiplication:(12)cmult=c1⋅G−1c2x0.Vector-integer multiplication:(13)cmult=c1⋅g−1c2x0.(vi)
HE.DecVecsk,c: Given a γ-dimensional vector ciphertext c, first compute c=c⋅g−1p/2, and then output the following:(14)m=2cp2.(vii)
HE.DecIntsk,c: Given an integer ciphertext c, output the following:(15)m=2cp2.


## 3.2. Analysis of Correctness and Noise Growth

We first prove the correctness of our scheme and analyze the noise growth in encryption, decryption, and homomorphic operations procedures. Then we convert our scheme into a leveled FHE-OI scheme by analyzing the multiplicative circuit depth L. Finally, we show that when performing homomorphic multiplications in sequence, the resulting ciphertext can have a smaller noise growth.Lemma 5 (Encryption noise of Integer Ciphertext).
Letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λ and c⟵HE.EncIntpk,m for a message m∈0,1, then(16)c=p2m+rmodp,where r≤2τ+12ρ.Proof.
For a public key element vectorx=x1,…xτ and a random vector s⟵0,1τ, it is easy to see that x,s=∑i∈Sxi, where xi=pqi+ri, and S⊆1,2,…,τ. Denote y/2=pq′/2+r′/2+δ, where δ∈−1/2,1/2∩ℝ; hence, we can write(17)c=m⋅y2+x,sx0=mpq′2+r′2+δ+∑i∈Sxi−kx0.
Sinceq′ is odd, we have modulo p and(18)c=p2m+∑i∈Sri−kr0+r′2+δmmodp,for some k∈0,τ∩Z. As a result, we have r=∑i∈Sri−kr0+r′/2+δm, where r≤τ2ρ+τ2ρ+2ρ−1+1/2≤2τ+12ρ.Lemma 6 (encryption noise of vector ciphertext).
Letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λ and c⟵HE.EncVecpk,m for a message m∈0,1; then,(19)c=mg+pq+r,where r≤2τ⋅2ρ.Proof.
For a public key elementxi=pqi+ri where i∈0,τ∩Z, write x=x1,…xτ=pq′+r′, with q′=q1,…,qτ and r′=r1,…,rτ. Then, we have(20)c=m⋅g+xSx0=m⋅g+p⋅q′S+r′S−kpq0+r0.
Defineq=q′S−kq0 and r=r′S−kr0, and then we have c=mg+pq+r. Since S∈0,1τ×γ and k∈0,τγ, we have r′S≤τ2ρ and kr0≤τ2ρ. Therefore, r=r′S−kr0≤r′S+kr0≤2τ⋅2ρ.Lemma 7 (noise of integer-integer addition).
Letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λ and ci⟵HE.EncIntpk,mi with ci=p/2mi+rimodp for i∈1,2 and mi∈0,1. Then,(21)cadd=p2m1+m2+rmodp,where r≤r1+r2+2ρ..Proof.
Sinceci=p/2mi+rimodp, we have(22)cadd=c1+c2x0=p2m1+m2+r1+r2−kr0modp,where k∈−1,1∩Z. Hence, we have r=r1+r2−kr0≤r1+r2+2ρ.Lemma 8 (noise of integer-vector addition).
Letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λ, c1⟵HE.EncIntpk,m1 with c1=p/2m1+r1modp and c2⟵HE.EncVecpk,m2 with c2=m2g+pq2+r2. Then,(23)cadd=p2m1+m2+rmodp,where r≤r1+γr2+γ2ρ.Proof.
Writec1=p/2m1+r1modp, c2=m2g+pq2+r2, and define(24)c2=c2⋅g−1y2=m2g+pq2+r2g−1y2=m2gg−1y2+pq2g−1y2+r2g−1y2=y2m2+pq2g−1y2+r2g−1y2=p2m2+r2g−1y2+r′2+δm2modp=p2m2+r2modp,where r2=r2g−1y/2+r′/2+δm2≤γr2+2ρ−1+1/2≤γr2+2ρ. Hence, we can write(25)cadd=c1+c2⋅g−1y2x0=c1+c2x0=p2m1+m2+r1+r2−kr0modp,for some k∈0,γ+2/2∩Z. As a result, we have r=r1+r2−kr0≤r1+γr2+2ρ+γ+22ρ−1≤r1+γr2+γ2ρ.Lemma 9 (noise of vector-vector addition).
Letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λ and ci⟵HE.EncVecpk,mi with ci=mig+pqi+ri for i∈1,2 and mi∈0,1. Then,(26)cadd=m1+m2g+pq+r,where r≤r1+r2+2ρ.Proof.
cadd=c1+c2x0=m1+m2g+pq1+q2−kq0+r1+r2−kr0, where k∈−1,1γ∩Zγ. Define q=q1+q2−kq0, and then we have cadd=m1+m2g+pq+r, where r=r1+r2−kr0. Hence, we have r≤r1+r2+kr0≤r1+r2+2ρ.Lemma 10 (noise of vector-vector multiplication).
Letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λ and ci⟵HE.EncVecpk,mi with ci=mig+pqi+ri for i∈1,2 and mi∈0,1. Then,(27)cmult=m1m2g+pq+r,where r≤γr1+r2+γ2ρ.Proof.
Writec1=m1g+pq1+r1 and c2=m2g+pq2+r2, and then we have(28)cmult=c1⋅G−1c2x0=m1g+pq1+r1G−1c2−kx0=m1gG−1c2+pq1G−1c2−kq0+r1G−1c2−kr0=m1m2g+pq2+r2+pq1G−1c2−kq0+r1G−1c2−kr0=m1m2g+pq1G−1c2−kq0+m1q2+r1G−1c2+m1r2−kr0.
Defineq=q1G−1c2−kq0+m1q2 and r=r1G−1c2+m1r2−kr0. Since c1⋅G−1c2≤γc1,c1≤x0/2 and c1⋅G−1c2−kx0≤x0/2, we have k∈0,γ+1/2∩Z; hence, we can write cmult=m1m2g+pq+r, where r≤r1G−1c2+m1r2+kr0≤γr1+r2+γ2ρ.Lemma 11 (noise of vector-integer multiplication).
Letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λmi∈0,1,c1⟵HE.EncVecpk,m1 with c1=m1g+pq1+r1 and c2⟵HE.EncIntpk,m2 with c2=p/2m2+r2modp. Then,(29)cmult=p2m1m2+rmodp,where r≤γr1+r2+γ2ρ.Proof.
Writec2=p/2m2+pq2+r2modp, and then we have(30)cmult=c1⋅g−1c2x0=m1g+pq1+r1g−1c2−kx0=m1gg−1c2+pq1g−1c2−kq0+r1g−1c2−kr0=m1p2m2+pq2+r2+pq1g−1c2−kq0+r1g−1c2−kr0=p2m1m2+pq1g−1c2+m1q2−kq0+r1g−1c2+m1r2−kr0=p2m1m2+r1g−1c2+m1r2−kr0modp=p2m1m2+rmodp,where r=r1g−1c2+m1r2−kr0 and k∈0,γ+1/2∩Z. As a result, we have r≤γr1+r2+γ2ρ.Lemma 12 (decryption noise of integer ciphertext).
Letsk=p⟵HE.KeyGen1λ and an integer ciphertext c with c=p/2m+rmodp for a message m∈0,1. Then,(31)HE.DecIntsk,c=2cp2=m,if r<p/4−1/2.Proof.
Writec=p/2m+pq+rmodp. Since p is odd, we have(32)2cp=2p+1/2m+pq+rp=m+2q+2r+mp,which is correctly decrypted to m when 2r+1/p<1/2. Hence, we have r<p/4−1/2.Lemma 13 (decryption noise of vector ciphertext).
Letsk=p⟵HE.KeyGen1λ and a vector ciphertext c with c=mg+pq+r for a message m∈0,1. Then,(33)HE.DecVecsk,c=2c⋅g−1p/2p2=m,if r<1/ηp/4−1/2.Proof.
For a ciphertextc=mg+pq+r, first compute(34)c=c⋅g−1p2=mg+pq+rg−1p2=mgg−1p2+pqg−1p2+rg−1p2=p2m+pq+r,where q=qg−1p/2 and r=rg−1p/2 with r≤ηr. By Lemma 12, the ciphertext c is correctly decrypted to m when r<p/4−1/2. Hence, we have r<1/ηp/4−1/2.
The following lemma shows that our HE scheme can be converted to a leveled FHE-OI scheme to evaluate any binary circuit with depthL if the parameters satisfy some constraints.Lemma 14.
Given any binary circuit C with depthL, the HE scheme can be converted to a leveled FHE-OI scheme to evaluate this circuit if(35)η−ρ≥Llogγ+1+log2τ+1+logη+2.Proof.
Assume that the given circuit C only consists of multiplication gates; then, a ciphertext will undergoL homomorphic multiplications. We first consider the vector-vector multiplications. For i∈1,L, let ci=mig+pqi+ri be the ciphertext after the i-th homomorphic multiplication, and c0 be a fresh ciphertext. Let Ri be the upper bound on the noise magnitude ri. First, we have R0=2τ2ρ by Lemma 6; then, after the i-th homomorphic multiplication, we have Ri=γ+1Ri−1+γ2ρ by Lemma 10. By solving the recurrence equation, we obtain(36)RL≤γ+1L2τ+12ρ−2ρ,which should be smaller than 1/ηp/4−1/2 for decryption correctness by Lemma 13. Hence, we have η−ρ≥Llogγ+1+log2τ+1+logη+2.
Note that vector-integer multiplications have a similar noise growth than vector-vector multiplications, and hence, we omit vector-integer multiplication in the analysis of vector-vector multiplication.Lemma 15 (sequentialization of homomorphic multiplication).
Letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λ and ci⟵HE.EncVecpk,mi with ci=mig+pqi+ri for i∈1,k∩ℤ and mi∈0,1, where k is an arbitrary positive integer larger than 1. Then, for any fixed multiplication sequence(37)c=c1G−1c2G−1⋅⋅⋅ck−1G−1ckx0x0x0,the noise component r in c satisfies r≤γr1+γr2⋅⋅⋅+γrk−1+rk+k−1γ2ρ≤k−12τ+1γ2ρ+τ2ρ+1.Proof.
Definec′=ck−1G−1ckx0; hence, r′≤γrk−1+rk+γ2ρ by Lemma 13. Define c″=ck−2G−1c′x0. Then we have r″≤γrk−2+r′+γ2ρ. By recursively performing the above procedure, we finally obtain a ciphertext c with the noise component r satisfying r≤γr1+γr2⋅⋅⋅+γrk−1+rk+k−1γ2ρ≤k−12τ+1γ2ρ+τ2ρ+1.
The above lemma implies that when we perform homomorphic multiplications betweenL+1 fresh ciphertexts and undergo at most L multiplications, if we operate these ciphertexts by a fixed multiplication sequence in Lemma 15, then the resulting ciphertext will have a noise growth of L2τ+1γ2ρ+τ2ρ+1. This growth is in contrast to the noise blowup in general homomorphic multiplications, i.e., γ+1L2τ+12ρ−2ρ in Lemma 14. This is a unique property in the GSW-style FHE scheme since the noise terms in ciphertexts grow asymmetrically. We can realize better noise management and evaluate a circuit with a multiplicative depth larger than L by applying this multiplication sequence in homomorphic evaluation.
Note that the method of sequentialization in homomorphic multiplication can also be applied to vector-integer multiplication since it has the same asymmetrical property as vector-vector multiplication and the noise growth is similar. Here we omit the analysis of vector-integer multiplication.


## 3.3. Parameters

We present some constraints in choosing parameters to ensure the correctness and security against known attacks. LetL be the circuit depth in homomorphic evaluation and let λ be the security parameter.ρ is the bit-length of the noise r in public key elements, and it should satisfy ρ≥λ to protect against brute force attacks on the noise [3, 5, 24, 25].η is the bit-length of the secret key p, and it should satisfy η≥ρ+Llogγ+1+log2τ+1+logη+2 to ensure decryption correctness (see Lemma 14).γ is the bit-length of the public key elements xi, y and it should satisfy γ≥Ωλ/logλη−ρ2 to thwart different lattice reduction attacks on the AGCD (as studied in [8]), such as orthogonal lattice attacks [2, 26], the simultaneous Diophantine approximation attack [27], and the multivariate polynomial attack [28].τ is the number of integers in the public keys, and it should satisfy τ=γ+Ωλ to be able to use the leftover hash lemma in the security proof.To satisfy the above constraints, we can take(38)ρ=λ,η=λ+ΩLlogλ,γ=ΩL2λlogλ,τ=γ+Ωλ.


## 3.4. Semantic Security

We show that the security of our HE scheme can be based on the decisional-AGCD problem; the main proof process is to show that it is difficult to distinguish the ciphertext from a uniform integer modulex0.Theorem 1.
The HE scheme is IND-CPA secure under theρ,η,γ-decisional-AGCD assumption.Proof.
We will use a three-step hybrid argument to prove that both the integer and vector ciphertexts in our HE scheme have computational indistinguishability and there is no such a probabilistic polynomial-time adversaryA that can distinguish these ciphertexts.
HybridH0: Let pk=x0,x,y⟵HE.KeyGen1λ), c⟵HE.EncVecpk,m=m⋅g+xSx0 and c⟵HE.EncIntpk,m=m⋅y/2+x,sx0 for a message m∈0,1. By the leftover hash lemma in Lemmas 2 and 3, the tuple (x,xS (mod x0),x,s (mod x0)) is within an exponentially small statistical distance by 1/2x0/τ=neglλ. As a result, the tuple (x,xS (mod x0),x,s (mod x0)c,c) is within an exponentially small statistical distance by neglλ, independent of the underlying plaintext. Hence, we have(39)PrH0A1λ,pk=1−PrH0A1λ,pk,c,c=1≤neglλ.
HybridH1: Let U be the uniform distribution over 0,2γ∩Z. In this hybrid, we replace the xis in the public keys by sampling from U0,2γ∩ℤ. We first sample x0′⟵U0,2γ∩Z>2γ−1 via rejection sampling. Then, we sample xi′⟵U0,2γ∩Z<x0 via rejection sampling for i∈1,τ∩Z, write x′=x1′,…,xτ′, and output pk′=x0′,x′,y. The resulting public key distribution is computationally indistinguishable from the genuine public key distribution in H0 by Lemma 4. Hence, we have(40)PrH0A1λ,pk=1−PrH1A1λ,pk′=1≤neglλ.
HybridH2: Define c′=m⋅g+x′Sx0′ and c′=m⋅y/2+x′,sx0′ for m∈0,1. By the leftover hash lemma in Lemmas 2 and 3, the tuple (x′,x′S (mod x0′),x′,s (mod x0′)) is within an exponentially small statistical distance by 1/2x0′/τ=neglλ. As a result, the tuple (x′,x′S (mod x0′),x′,s (mod x0′)c′,c′) is within an exponentially small statistical distance by neglλ, independent of the underlying plaintext. Hence, we have(41)PrH1A1λ,pk′=1−PrH2A1λ,pk′,c′,c′=1≤neglλ.
Finally, we conclude that(42)PrH0A1λ,pk,c,c=1−PrH2A1λ,pk′,c′,c′=1≤neglλ,which proves the IND-CPA security of the HE scheme.


## 4. Ciphertext Compression

The above HE scheme reduces the ciphertext expansion in BBL17 [10] by generating two types of ciphertexts. Moreover, the computational efficiency in homomorphic evaluation can be improved by hybrid homomorphic operations between integers and vectors. However, the size of the vector ciphertext (Ογ2) is still a bottleneck to making our scheme more efficient.In this section, we will use a technique of ciphertext compression to reduce the size of both integer and vector ciphertexts. The technique was first proposed in CS15 [8], and we observe that it can also be applied to our HE scheme.Note that the plaintext bitm is embedded into the most signiﬁcant bit of the integer ciphertext c modulo p, i.e., c=p/2m+rmodp. For vector ciphertext c, first compute c′=c⋅g−1p/2; then, c′ has the same form as integer ciphertext c (see the proof in Lemma 13). In this case, some least signiﬁcant bits of ciphertexts c and c′ are irrelevant for decryption correctness, and therefore, we can truncate these bits to obtain a ciphertext of smaller size. However, the number of bits we can truncate must be limited to an upper bound since the decryption failure probability becomes overwhelming if we truncate more bits. According to CS15 [8], truncating a ciphertext by ρ bits can result in optimal performance. We follow this approach and describe the truncation procedure in the HE scheme below.DefineN=2ρ. For integer ciphertext c, define c^=c/N so that Nc^−c≤N/2. For vector ciphertext c, define c^=ci/Nρ≤i≤γ−1γ−ρ, where ci is the i-th coordinate in vector c. In the following, we formally present the truncated version of the HE scheme (we call this truncated scheme THE).(i)
[THE Encryption](1)
For encryption of the integer ciphertext, letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λ and c⟵HE.EncIntpk,m with c=p/2m+pq+rmodp for a message m∈0,1. Then,(43)c^=cN=p2mN+pNq+rN=p2mN+pNq+rN+δ,whereδ∈−1/21/2∩ℝ, and the noise component is r/N+δ≤2τ+12ρ/N+1/2 by Lemma 5.(2)
For encryption of the vector ciphertext, letsk=p,pk=x0,x1,…,xτ,y⟵HE.KeyGen1λ and c⟵HE.EncVecpk,m with c=mg+pq+r for a message m∈0,1. Write c=ci0≤i≤γ−1γ, and then we have ci=m⋅2i+pqi+ri. Then,(44)c^=ciNρ≤i≤γ−1γ−ρ=m⋅2iN+pNqi+riNρ≤i≤γ−1γ−ρ=m⋅2i−ρ+pNqi+riN+δiρ≤i≤γ−1γ−ρ=mg′+pNq′+r′N+δ′,whereg′=20,21,…,2γ−ρ−1, δ′=δiρ≤i≤γ−1γ−ρ, δi∈−1/2,1/2∩ℝ, q′=qiρ≤i≤γ−1γ−ρ, r′=riρ≤i≤γ−1γ−ρ, and the noise component is r′/N+δ′≤1/Nr′+δ′≤2τ⋅2ρ/N+1/2 by Lemma 6.(ii)
[THE Addition](1)
For integer-integer addition,(45)c^add=c^1+c^2x^0=p2m1N+pNq1+r1N+δ1+p2m2N+pNq2+r2N+δ2−kpNq0+r0N+δ0=p2m1+m2N+pNq1+q2−kq0+r1+r2−kr0N+δ1+δ2−kδ0=p2m1+m2N+pNq+rN+δ,whereq=q1+q2−kq0, r=r1+r2−kr0, δ=δ1+δ2−kδ0, δ0,δ1,δ2∈−1/2,1/2∩ℝ, and k∈−1,1∩Z. The noise component is r/N+δ≤r1+r2+2ρ/N+δ1+δ2+1/2.(2)
For vector-vector addition,(46)c^add=c^1+c^2x^0=m1g′+pNq1′+r1′N+δ1′+m2g′+pNq2′+r2′N+δ2′−k′pNq0+r0N+δ0=m1+m2g′+pNq1′+q2′−k′q0+r1′+r2′−k′r0N+δ1′+δ2′−k′δ0=m1+m2g′+pNq′+r′N+δ′,whereq′=q1′+q2′−k′q0, r′=r1′+r2′−k′r0, δ′=δ1′+δ2′−k′δ0, and k′∈−1,1γ−ρ∩Zγ−ρ. The noise component is r′/N+δ′≤r1+r2+2ρ/N+δ1'+δ2'+1/2.(3)
For integer-vector addition, first compute(47)c^2=c^2⋅g−1y2N=m2g′+pNq2′+r2′N+δ2′g−1y2N=m2g′g−1y2N+pNq2′g−1y2N+r2′g−1y/2NN+δ2′g−1y2N=pq′+r′2N+′m2+pNq2′g−1y2N+r2′g−1y/2NN+δ2′g−1y2N≡p2m2N+pNq2′g−1y2N+r2′g−1y/2N+r′/2+Nδ′m2N+δ2′g−1y2N=p2m2N+pNq2+r2N+δ2,whereq2=q2′g−1y/2N, r2=r2′g−1y/2N+r′/2+Nδ′m2, δ′∈−1/2,1/2∩ℝandδ2=δ2′g−1y/2N We have r2≤γ−ρr2′+2ρ−1+N/2≤γ−ρr2′+2ρ, δ2≤γ−ρδ2′. Then, compute(48)c^add=c^1+c^2x^0=p2m1+m2N+pNq1+q2−kq0+r1+r2−kr0N+δ1+δ2−kδ0=p2m1+m2N+pNq+rN+δ,whereq=q1+q2−kq0, r=r1+r2−kr0, δ=δ1+δ2−kδ0, and k∈0,γ−ρ+2/2∩Z with r≤r1+r2+γ−ρ+22ρ−1, δ≤δ1+δ2+γ−ρ+2/4. The noise component is r/N+δ≤r1+γ−ρr2′+γ−ρ2ρ/N+δ1+γ−ρδ2′+γ−ρ/2.(iii)
[THE Multiplication](1)
For vector-vector multiplication,(49)c^mult=c^1⋅G−1c^2x^0=m1g′+pNq1′+r1′N+δ1′G−1c^2−k′x^0=m1g′G−1c^2+pNq1′G−1c^2+r1′G−1c^2N+δ1′G−1c^2−k′pNq0+r0N+δ0=m1m2g′+pNq2′+r2′N+δ2′+pNq1′G−1c^2−k′q0+r1′G−1c^2−k′r0N+δ1′G−1c^2−k′δ0=m1m2g′+pNq1′G−1c^2+m1q2′−k′q0+r1′G−1c^2+m1r2′−k′r0N+δ1′G−1c^2+m1δ2′−k′δ0=m1m2g′+pNq′+r′N+δ′,whereq′=q1′G−1c^2+m1q2′−k′q0, r′=r1′G−1c^2+m1r2′−k′r0, δ′=δ1′G−1c^2+m1δ2′−k′δ0, and k′∈0,γ−ρ+1/2γ−ρ∩Zγ−ρ. The noise component is r′/N+δ'≤γ−ρr1′+r2′+γ−ρ2ρ/N+γ−ρδ1′+δ2′+γ−ρ/2.(2)
For vector-integer multiplication,(50)c^mult=c^1⋅g−1c^2x^0=m1g′+pNq1′+r1′N+δ1′g−1c^2−kx^0=m1g′g−1c^2+pNq1′g−1c^2+r1′g−1c^2N+δ1′g−1c^2−kpNq0+r0N+δ0=m1p2m2N+pNq2+r2N+δ2+pNq1′g−1c^2−kq0+r1′g−1c^2−kr0N+δ1′g−1c^2−kδ0=p2m1m2N+pNq1′g−1c^2+m1q2−kq0+r1′g−1c^2+m1r2−kr0N+δ1′g−1c^2+m1δ2−kδ0=p2m1m2N+pNq+rN+δ,whereq=q1′g−1c^2+m1q2−kq0, r=r1′g−1c^2+m1r2−kr0, δ=δ1′g−1c^2+m1δ2−kδ0, and k∈0,γ−ρ+1/2∩Z. The noise component is r/N+δ≤γ−ρr1′+r2+γ−ρ2ρ/N+γ−ρδ1′+δ2+γ−ρ/2.(iv)
[THE Decryption](1)
For decryption of the integer ciphertext,(51)2c^P/N2=2p/2m/N+p/Nq+r/N+δp/N2=m+2q+m+2r+2Nδp2,which is correctly decrypted tom when m+2r+2Nδ/p<1/2. Hence, we have r/N+δ<p/4N−1/2N.(2)
For decryption of the vector ciphertext, first compute(52)c^=c^⋅g−1p2N=mg′+pNq′+r′N+δ′g−1p2N=mg′g−1p2N+pNq′g−1p2N+r′g−1p/2NN+δ′g−1p2N=p2Nm+pNq+rN+δ,whereq=q′g−1p/2N, r=r′g−1p/2N, and δ=δ′g−1p/2N with r≤η−ρr′ and δ≤η−ρδ′. Then, compute(53)2c^p/N2=2p/2N+δ′m+p/Nq+r/N+δp/N2=m+2q+2Nδ′m+2r+2Nδp2,whereδ′∈−1/2,1/2∩ℝ. To ensure the decryption correctness, equation (53) should satisfy 2Nδ′m+2r+2Nδ/p<1/2, which is equivalent to r/N+δ<p/4N−1/2. Hence, we have r′/N+δ′<1/η−ρp/4N−1/2.By applying the above THE scheme, the size of integer and vector ciphertexts in HE scheme can be reduced toγ−ρ and γ−ρ2. Besides, the noise growth in homomorphic evaluation is similar between the two schemes. As a result, if the γ−ρ is set small, the spatial and computational efficiency in the THE scheme can be significantly improved.In CS15 [8], the authors set γ−ρ=λ+ΩLlogλ to obtain an integer ciphertext of small size, but this was proved insecure in subsequent works. In [22], the authors proposed an optimized OL attack to obtain the γ−ρ most signiﬁcant bits of the secret key p, and the computational complexity was Ω2λ/logλ. Therefore, to thwart this optimized OL attack and obtain a security level of Ο2λ, we need to set γ−ρ=λlogλ+ΩLlogλ, which significantly reduces the size of ciphertexts. Moreover, the truncated scheme is as secure as before. Consequently, we have a better spatial and computational efficiency compared to the HE scheme.To satisfy the above conditions and the constraints in Section3.3, we can set(54)γ=ΩL2λlogλ,η=γ−λlogλ,ρ=η−ΩLlogλ.


## 5. Comparison with Prior Works

In this section, we make a comparison between our scheme and prior schemes, such as CLT14 [7], CS15 [8], BBL17 [10], and Per20b [19]. We show that our scheme has more advantages in regards to spatial and computational efficiency.Our HE scheme reduces the ciphertext expansion by generating integer and vector ciphertexts instead of only generating vector ciphertexts as in BBL17 [10]. Additionally, the size of both ciphertexts can be further reduced by applying the THE scheme. Compared to CLT14 [7], the vector ciphertexts in the HE scheme have a larger size since the CLT14 [7] scheme only consists of integer ciphertexts; moreover, by applying the THE scheme, the vector ciphertexts are similar to the integer ciphertexts in CLT14 [7]. However, we cannot compare our schemes with Per20b [19] directly since Per20b used a variant called RAGCD and it has a larger message space such that m∈Zt. However, we can convert Per20b into a general AGCD scheme and set message space to m∈0,1 by restricting the parameters to some concrete values. Roughly, we can take N=1,B=1,l=γ,b=2 and set the size of scalar and vector ciphertexts in Per20b equal to ΩL2λlogλ and γl=ΩL4λ2log2λ. In this way, we can see that our schemes have similar performance as Per20b. Table 1 shows the concrete parameters of the size of ciphertexts in our schemes and prior schemes.Table 1
Ciphertext size comparison with across various schemes.
SchemeSize of ciphertextCLT14 [7]—Ο˜L2λ+λ2CS15 [8]Basic schemeΩL2λlogλTruncated schemeλ+ΩLlogλ (Not secure)BBL17 [10]—Ο˜λ4+L4Per20b [19]Scalar ciphertextΩL2λlog2N2BlbVector ciphertextΩlL2λlog2N2BlbOur HEInteger ciphertextΩL2λlogλVector ciphertextΩL4λ2log2λOur THEInteger ciphertextλlogλ+ΩLlogλVector ciphertextλ2log2λ+ΩL2log2λIn homomorphic evaluation, since the multiplication procedure takes up most of the running time, it determines the final computational efficiency. In the following, we show that the homomorphic multiplication in our scheme has more advantages than prior schemes.Note that the vector-vector multiplication in our HE scheme includes the general multiplication operation between a vector and a decomposed vector (a binary matrix). Vector-vector multiplication must computeγ times (for each coefficient) about γ/2 modular additions of γ-bit numbers; this procedure has an asymptotic computational complexity of Ογ2logγ, which is identical to that of prior schemes. However, the vector-integer multiplication in our HE scheme is between a vector and a decomposed integer (a binary vector), and it only requires computation of about γ/2 modular additions of γ-bit numbers and has a computational complexity of Ογlogγ. This complexity is smaller than that of CLT14, CS15, and BBL17, and is identical to the vector-scalar multiplication of Per20b. Furthermore, by applying the THE scheme, both kinds of multiplications are faster than in prior schemes since they have a smaller computational complexity of Ογ−ρ2logγ−ρ and Ογ−ρlogγ−ρ. Table 2 shows the asymptotic computational complexity of homomorphic multiplication in our scheme and prior schemes.Table 2
Comparison of multiplication complexity across various schemes.
SchemeMultiplication complexityCLT14 [7]—Ογ2logγCS15 [8]Basic schemeΟγ2logγTruncated schemeΟγ−ρ2logγ−ρBBL17 [10]—Ογ2logγPer20b [19]Vector-ScalarΟγlogγVector-VectorΟγ2logγOur HEVector-IntegerΟγlogγVector-VectorΟγ2logγOur THEVector-IntegerΟγ−ρlogγ−ρVector-VectorΟγ−ρ2logγ−ρ


## 6. Conclusion

In this work, we present a GSW-style FHE-OI scheme and reduce the ciphertext expansion by generating integer and vector ciphertexts. The computational efficiency in homomorphic evaluation is improved by hybrid homomorphic operations between integers and vectors, especially when performing vector-integer multiplications. Our computational complexity is better than those of all prior leveled FHE-OI schemes. By applying sequentialization in homomorphic multiplications, the noise growth in the resulting ciphertext is smaller than that produced through general multiplications, and therefore, our scheme can evaluate a circuit with a larger multiplicative depth under the same parameter settings as general multiplications. Finally, the efficiency in our scheme can be further improved by a technique of ciphertext compression called truncation, and the optimized scheme is as secure as before when it comes to thwarting known attacks. Note that our scheme can also be generalized to SIMD operations such as the batch technique based on Chinese remainder theorem and larger prime message space.



---

*Source: 8823787-2021-03-05.xml*