# An Effective NTRU-Based Fully Homomorphic Encryption Scheme

Authors: Xiaoyue Qin; Ruwei Huang; Huifeng Fan
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Fully homomorphic encryption (FHE) supports arbitrary computations on ciphertexts without decryption to protect users’ privacy. However, currently, there are still some shortcomings in research studies on FHE. For example, the NTRU-based FHE scheme constructed using the approximate eigenvector method requires complex matrix multiplications, and the power-of-two cyclotomic ring cannot prevent subfield attacks. To address these problems, this paper proposed a NTRU-based FHE scheme constructed based on the power-of-prime cyclotomic ring and made the following improvements: (1) the power-of-prime cyclotomic ring is immune to subfield attacks; (2) complex matrix multiplications are replaced with matrix-vector multiplications to modify the ciphertext forms and decryption structures, so as to gain advantages in storage, transportation, and computations; (3) the single instruction multiple data (SIMD) technology is introduced, and homomorphic operations are executed through the Chinese remainder theorem, further improving the scheme computation and storage efficiency. The ciphertext of the scheme is in a form of a vector, and no key exchange is required for homomorphic operations. In addition, this scheme can eliminate the decisional small polynomial ratio (DSPR) assumption under certain conditions and only relies on the ring learning with errors (RLWE) assumption. The standard security model can prove that this scheme is secure against chosen-plaintext (IND-CPA) attacks. Compared with similar schemes, the proposed scheme improves the efficiency at least by a factor oflφx/d+1 and quadratically decreases the noise growth rate.


---

## Body

## 1. Introduction

Fully homomorphic encryption supports arbitrary computations on the ciphertext without the requirement of decryption, and the result obtained is same as direct computations on plaintext after decryption. This can well solve the contradiction between the security of user privacy and the outsourcing of data storage and computation in an outsourced computing environment. Therefore, fully homomorphic encryption is widely applied in cloud computing, healthcare, blockchain, and other industries [1]. The existing FHE schemes can be divided into three types: integer-type [2], Regev-type [3], and NTRU-type [4]. The first two types of schemes have low efficiency of homomorphic computations and large cost of key generation, while in the NTRU-based FHE scheme, algorithms can only use modular multiplication and modular inverse, which results in a faster decryption speed [5, 6] and plays a promising role in the resource-constrained IoT environment. It can provide mutual authentication for devices and servers as well as resistance to known attacks. IoT devices based on the NTRU-based scheme can be connected to authentication schemes such as those described in the literature [7, 8], improving the overall authentication efficiency of schemes as well as preventing quantum attacks. Therefore, the study of the NTRU-based FHE scheme is of great significance.In 2013, Gentry et al. proposed a FHE scheme, which was constructed based on the technique of approximate eigenvectors [9]. The homomorphic addition and homomorphic multiplication of this scheme are achieved by doing simple addition and multiplication on the matrix. The scheme is relatively simple, fast, and easy to understand, and the implementation of homomorphic computations can be achieved without computing the public key and only with the help of the user’s public key [10]. In addition, the authors pointed out that the technique can be applied to construct an FHE scheme based on NTRU. However, no specific implementation was provided. The F-NTRU scheme proposed by Dor and Sunar [11] and the improved scheme proposed by Li et al. [12] are all constructed by adopting the flattening technique and the BitDecomp technique to derive an NTRU-based scheme based on approximate eigenvectors. However, the ciphertext of the FHE scheme constructed using approximate eigenvectors is in the form of a matrix. The ciphertext size is relatively large, and complex matrix multiplications are required, which greatly affects the computational efficiency. In 2018, Khedr and Gulak [13] used NTT (FastNumber-TheoreticTransform) to perform matrix multiplication instead of circular convolution in the F-NTRU scheme to make the computation simple, but none of these improvements can essentially avoid matrix multiplication.Meanwhile, the security of the above schemes is based on the power-of-two cyclotomic ring. The schemes based on this cyclotomic ring have a simple structure, but they cannot prevent subfield attacks [14, 15] and use SIMD techniques [16]. Migliore et al. [17] also verified that the F-NTRU scheme suffers from the possibility of subfield attacks, so finding a more secure ring to guarantee the security of the scheme is especially important. In 2016, Doroz et al. [18] proposed for the first time a DHS16 scheme based on the power-of-prime cyclotomic ring to improve the LTV12 scheme [19], which improves the efficiency of the scheme in practical applications but does not give a theoretical proof of security. In 2018, Yu et al. [20] changed the ring structure of the SS11 scheme [21] to a power-of-prime cyclotomic ring and improved the key generation algorithm using a Gaussian distribution with regular embedding to make its security proven.To address the abovementioned problems that occurred in the process of constructing FHE schemes using approximate eigenvectors, this paper firstly applies the existing power-of-two cyclotomic polynomial to the power-of-prime cyclotomic polynomial in terms of security enhancement and gives an NTRU-type FHE scheme based on the power-of-prime cyclotomic ring. The scheme eliminates the DSPR assumption under certain conditions, and its security only depends on the RLWE assumption. The standard security model can prove that this scheme is secure against chosen-plaintext (IND-CPA) attacks. In terms of improving efficiency, the scheme introduces SIMD techniques and uses matrix-vector multiplication instead of complex matrix multiplication, which greatly enhances the efficiency. The ciphertext of the scheme is in a form of a vector, which is more advantageous in storage, transportation, and computation. In addition, the calculation order of multiplication can further optimize the noise management.


## 2. Basic Knowledge

The power-of-prime cyclotomic ring [22]on which this scheme is based is a special case of cyclotomic polynomial. The construction of the key generation algorithm involves Gaussian distribution under regular embedding [23]. The security of this scheme depends on RLWE assumption as well as DSPR assumption [24], and the security model proves that this scheme is secure against IND-CPA attacks [25]. This section focuses on the cyclotomic polynomial, RLWE assumption, DSPR assumption, Gaussian distribution with regular embedding, and definition of the security model.


### 2.1. Symbolic Representation

If A indicates an algorithm,x←A indicates that x is obtained based on that algorithm. If A indicates a collection, x←A indicates that x is randomly chosen from Collection A. For any integer q, if Zq=−q/2,q/2∩Z, integer x,xq indicates xmodq∈Zq. Use lowercase letters to represent a multidimensional vector. For example, for vector y, yi indicates its ith component. The polynomial of an indeterminate of x is represented using lowercase letters, for example, fx.


### 2.2. Cyclotomic Polynomial

Definition 1 (cyclotomic polynomial, see [22]).
Assume FieldK is the field of characteristic P, n is a positive integer that cannot be divided by P with no remainder, ξn is a primitive nth root of unity in Field K, and the polynomial Φnx=∏i=1,gcdi,n=1nx−ξi is called the nth cyclotomic polynomial in Field K. Adjoin a primitive nth root of unity to Field Q of rational numbers to get an extension field K=Qξn, which is called the nth cyclotomic field.(i)
Whenn=2d,d∈Z∗, Φnx=xn+1(ii)
Whenn is a prime number, Φnx=xn−1+xn−2+…+x+1(iii)
Whend is a prime number, n=dv,v∈Z∗, Φnx=Φdxdv−1, R=Zx/Φnx, and Rq=R/qR is the power-of-prime cyclotomic polynomial ring.Theorem 1 (see [22]).
IfFq is a finite field and n is a positive integer, the sufficient and necessary condition for cyclotomic polynomial of order nQn to be reducible over Fqx is that the exponent of q mod n is Φnx (that is, q is the primitive root of mod n). It can be seen from Theorem 1 that if n≡±1mod8 is a prime or the square exponent of a prime, Qn is reducible over F2x [26].Theorem 2 (see [22]).
IfFq is a finite field, n is a positive integer, and gcdn,d=1, cyclotomic polynomial Φnx can be decomposed into the product of φx/d different monic irreducible polynomials fix of degree 2 in Fqx, that is, Φnx=∏i=0l−1fix, where d is the exponent of q mod n, meeting the requirement of being the minimum integer of qd≡1modn, and l=φx/d.Theorem 3 (see [27]).
Ifn∈N, Φnx=xn+1, and Ring R=Zx/Φnx, for any aandb∈R, the function is(1)ab≤ab,ab∞≤na∞b∞.Theorem 4 (see [20]).
Ifn=dv,d is a prime number, and Φnx=Φdxdv−1, then R=Zx/Φnx. For any aandb∈R, in the worst case, the function(2)ab∞≤2φna∞b∞.


### 2.3. Gaussian Distribution with Regular Embedding

Definition 2 (Gaussian distribution with regular embedding, see [26]).
Assume thatPX∈Zx is a monic reducible polynomial of degree n, R=Zx/Px, the roots of PX in the field of complex numbers are w1,w2,…,wn, respectively, V=wjn−iij,0≤i≤n−1,and1≤j≤n is called a regular transformation matrix. Let t=tn−1xn−1+tn−2xn−2+⋯+t0ϵR, the embedding of coefficients is represented by tn−1,tn−2,…,t0, and the transformation of regular embedding is represented by σt=tn−1,tn−2,…,t0Vσ, and Gaussian distribution with regular embedding is represented as follows:(3)t=σ−1t=σt⋅V−1,Dzn,σx=ρσxρσZn.


### 2.4. RLWEΦ,n,q,χ Assumption

Definition 3 (RLWEΦ,n,q,χ assumption, see [27]).
Assumen=dv, d is a prime number, and Φnx=Φdxdv−1. Define polynomial ring R=Zx/Φnx, Rq=R/qR, and a discrete Gaussian distribution χ on ring R with regular embedding. The RLWE Φ,n,q,χ assumption states that, for a random ring element s←Rq, given a polynomial ai,bi=ai⋅s+ei∈Rq2 where ai is uniformly random in Rq and ei is drawn from an error distribution χ, it is very hard to distinguish whether bi is drawn from computations or directly from the uniform distribution of Rq.


### 2.5. DSPRΦ,n,q,χ Assumption

Definition 4 (DSPRΦ,n,q,χ assumption, see [24]).
Letn=dv, d is a prime number, and Φnx=Φdxdv−1. Define polynomial ring R=Zx/Φnx, Rq=R/qR, and a discrete Gaussian distribution χ on ring R with regular embedding. The DSPR Φ,n,q,χ assumption is that it is hard to distinguish whether the element f of the polynomial h=g/f, where f and g are sampled from distribution χ, is drawn from a uniformly random element of Rq or is reversible in Rq=R/qR.


### 2.6. Security Model

Definition 5 (security model, see [25]).
Define a game between the attacker and challenger. This game is divided into four phases.
Setup phase: the challenger runs the key generation algorithm of the encryption scheme to generate a public key and makes the attacker get the public key.
Oracle machine access phase: the attacker chooses the plaintext and initiates queries to the oracle machine for encryption. After the attacker gets the ciphertext in a response, the attacker can submit the chosen plaintext multiple times in different stages and get the ciphertexts corresponding different plaintexts.
Challenge phase: the attacker chooses two plaintext messagesm0 and m1 and sends them to the challenger. The challenger chooses b∈0,1 and sends the ciphertext c=Encpkmb to the attacker.
Guess phase: the attacker gives his guessb′ corresponding to the ciphertext. When b′=b, the attacker wins.
Assume that there is an encryption schemeε for the public key within the bounded polynomial time, and a tiny function neglλ that gets the advantage of the attacker A is(4)AdvIND−CPAA=PrApk,Encpkm0=1−PrApk,Encpkm1=1=neglλ,where neglλ can be ignored and λ is the security parameter of the scheme. The game includes an attacker of polynomial time attacker A. Let AdvIND−CPAA be the probability that attacker A wins in the game. This scheme is secure against IND-CPA attacks.


## 2.1. Symbolic Representation

If A indicates an algorithm,x←A indicates that x is obtained based on that algorithm. If A indicates a collection, x←A indicates that x is randomly chosen from Collection A. For any integer q, if Zq=−q/2,q/2∩Z, integer x,xq indicates xmodq∈Zq. Use lowercase letters to represent a multidimensional vector. For example, for vector y, yi indicates its ith component. The polynomial of an indeterminate of x is represented using lowercase letters, for example, fx.


## 2.2. Cyclotomic Polynomial

Definition 1 (cyclotomic polynomial, see [22]).
Assume FieldK is the field of characteristic P, n is a positive integer that cannot be divided by P with no remainder, ξn is a primitive nth root of unity in Field K, and the polynomial Φnx=∏i=1,gcdi,n=1nx−ξi is called the nth cyclotomic polynomial in Field K. Adjoin a primitive nth root of unity to Field Q of rational numbers to get an extension field K=Qξn, which is called the nth cyclotomic field.(i)
Whenn=2d,d∈Z∗, Φnx=xn+1(ii)
Whenn is a prime number, Φnx=xn−1+xn−2+…+x+1(iii)
Whend is a prime number, n=dv,v∈Z∗, Φnx=Φdxdv−1, R=Zx/Φnx, and Rq=R/qR is the power-of-prime cyclotomic polynomial ring.Theorem 1 (see [22]).
IfFq is a finite field and n is a positive integer, the sufficient and necessary condition for cyclotomic polynomial of order nQn to be reducible over Fqx is that the exponent of q mod n is Φnx (that is, q is the primitive root of mod n). It can be seen from Theorem 1 that if n≡±1mod8 is a prime or the square exponent of a prime, Qn is reducible over F2x [26].Theorem 2 (see [22]).
IfFq is a finite field, n is a positive integer, and gcdn,d=1, cyclotomic polynomial Φnx can be decomposed into the product of φx/d different monic irreducible polynomials fix of degree 2 in Fqx, that is, Φnx=∏i=0l−1fix, where d is the exponent of q mod n, meeting the requirement of being the minimum integer of qd≡1modn, and l=φx/d.Theorem 3 (see [27]).
Ifn∈N, Φnx=xn+1, and Ring R=Zx/Φnx, for any aandb∈R, the function is(1)ab≤ab,ab∞≤na∞b∞.Theorem 4 (see [20]).
Ifn=dv,d is a prime number, and Φnx=Φdxdv−1, then R=Zx/Φnx. For any aandb∈R, in the worst case, the function(2)ab∞≤2φna∞b∞.


## 2.3. Gaussian Distribution with Regular Embedding

Definition 2 (Gaussian distribution with regular embedding, see [26]).
Assume thatPX∈Zx is a monic reducible polynomial of degree n, R=Zx/Px, the roots of PX in the field of complex numbers are w1,w2,…,wn, respectively, V=wjn−iij,0≤i≤n−1,and1≤j≤n is called a regular transformation matrix. Let t=tn−1xn−1+tn−2xn−2+⋯+t0ϵR, the embedding of coefficients is represented by tn−1,tn−2,…,t0, and the transformation of regular embedding is represented by σt=tn−1,tn−2,…,t0Vσ, and Gaussian distribution with regular embedding is represented as follows:(3)t=σ−1t=σt⋅V−1,Dzn,σx=ρσxρσZn.


## 2.4. RLWEΦ,n,q,χ Assumption

Definition 3 (RLWEΦ,n,q,χ assumption, see [27]).
Assumen=dv, d is a prime number, and Φnx=Φdxdv−1. Define polynomial ring R=Zx/Φnx, Rq=R/qR, and a discrete Gaussian distribution χ on ring R with regular embedding. The RLWE Φ,n,q,χ assumption states that, for a random ring element s←Rq, given a polynomial ai,bi=ai⋅s+ei∈Rq2 where ai is uniformly random in Rq and ei is drawn from an error distribution χ, it is very hard to distinguish whether bi is drawn from computations or directly from the uniform distribution of Rq.


## 2.5. DSPRΦ,n,q,χ Assumption

Definition 4 (DSPRΦ,n,q,χ assumption, see [24]).
Letn=dv, d is a prime number, and Φnx=Φdxdv−1. Define polynomial ring R=Zx/Φnx, Rq=R/qR, and a discrete Gaussian distribution χ on ring R with regular embedding. The DSPR Φ,n,q,χ assumption is that it is hard to distinguish whether the element f of the polynomial h=g/f, where f and g are sampled from distribution χ, is drawn from a uniformly random element of Rq or is reversible in Rq=R/qR.


## 2.6. Security Model

Definition 5 (security model, see [25]).
Define a game between the attacker and challenger. This game is divided into four phases.
Setup phase: the challenger runs the key generation algorithm of the encryption scheme to generate a public key and makes the attacker get the public key.
Oracle machine access phase: the attacker chooses the plaintext and initiates queries to the oracle machine for encryption. After the attacker gets the ciphertext in a response, the attacker can submit the chosen plaintext multiple times in different stages and get the ciphertexts corresponding different plaintexts.
Challenge phase: the attacker chooses two plaintext messagesm0 and m1 and sends them to the challenger. The challenger chooses b∈0,1 and sends the ciphertext c=Encpkmb to the attacker.
Guess phase: the attacker gives his guessb′ corresponding to the ciphertext. When b′=b, the attacker wins.
Assume that there is an encryption schemeε for the public key within the bounded polynomial time, and a tiny function neglλ that gets the advantage of the attacker A is(4)AdvIND−CPAA=PrApk,Encpkm0=1−PrApk,Encpkm1=1=neglλ,where neglλ can be ignored and λ is the security parameter of the scheme. The game includes an attacker of polynomial time attacker A. Let AdvIND−CPAA be the probability that attacker A wins in the game. This scheme is secure against IND-CPA attacks.


## 3. Efficient NTRU-Based Fully Homomorphic Encryption

This section first introduces the SIMD technique for plaintext batch processing, then describes the algorithm construction of the scheme in this paper, and finally proves the correctness of the encryption and decryption process and homomorphic operations of the scheme and provides an analysis of the noise growth during the process.


### 3.1. SIMD Technique

It can be derived from Theorems1 and 2 that the power-of-prime cyclotomic ring can be decomposed into multiple irreducible polynomials in Fqx. Therefore, in this paper, we use the Chinese remainder theorem [28] to batch process the data of plaintext slots and perform homomorphic computations in parallel to improve the execution efficiency of the scheme. The specific procedure is given below.Decompose the entire plaintext spaceRp=R/pR into l subrings with the same size. The corresponding plaintext slots are Z2x/f1x,…,Z2x/flx, inside which mix plaintexts are waiting to be encrypted. Then, combine l plaintexts in the slots into a plaintext space. cx and c′x indicate the ciphertexts obtained after encryption using a same plaintext space, respectively, and their corresponding plaintexts are m1x,m2x,…,mlx and m1′x,m2′x,…,ml′x, respectively.The homomorphic operations that are performed in parallel onl plaintexts are as follows:(5)laddm1x,m2x,…,mlx,m1′x,m2′x,…,ml′x=m1x+m1′x,…,mlx+ml′x,lmultm1x,m2x,…,mlx,m1′x,m2′x,…,ml′x=m1x⋅m1′x,…,mlx⋅ml′x,where ladd and lmult indicate the batch homomorphic addition and homomorphic multiplication operations on plaintexts, respectively. Therefore, homomorphic operations can be regarded as being executed in parallel on the plaintext slots by using the SIMD technique. Because data at different indexes within the arrays can never interact, ladd and lmult operations are not sufficient to perform arbitrary computations on encrypted arrays. To obtain a complete operation set of data arrays, this paper introduces the lpermute operation described in the literature [29] to impose an arbitrary ordering on data in arrays and supports plaintext slots of mx⟶mx2i to move cyclically by i plaintext slots. When i=1, the plaintext slot of mx moves by one slot. Accordingly, the plaintext of each plaintext slot is changed to m2x,mlx,…,m1x, so as to perform the whole operations on the data. When the ciphertext requires decryption, the Chinese remainder theorem is used for reversible processing to decrypt to l plaintexts.


### 3.2. Scheme Construction

Assume thatλ is a security parameter, L is the number of circuit layers, and n is a dimension and a power of a prime number. Let R=Zx/Φnx, where Φnx=∏i=1,gcdi,n=1nx−ξi is cyclotomic polynomial, the number of times for each fix is d,φn=dl=nλ,L,Fqdl is the vector space of plaintexts, and mapping CRTq is the isomorphic mapping from Fqdl to Rq.


#### 3.2.1. Key Generation Algorithm

Select a relatively large standard errorσ, and make f represent f=p⋅f′+1 where f′ is a polynomial sampled from a discrete Gaussian distribution Dzn,σx with regular embedding. Input nandq∈Z,p∈Rq∗,andσ∈R, where Rq∗ is a collection of reversible elements in Rq. Rq=R/qR=Zqx/Φ. Output sk,pk∈R×Rq∗. The detailed procedure is as follows:First samplef′ from a discrete Gaussian distribution Dzn,σx with regular embedding; let f=p⋅f′+1. If fmodq∉Rq∗, sample again.Then, sampleg from a discrete Gaussian distribution Dzn,σx with regular embedding. If gmodq∉Rq∗, sample again.Finally, returnsk=f and pk=h=pgf−1∈Rq∗.


#### 3.2.2. Encryption Algorithm

Use the Chinese remainder theorem to calculate the plaintextm←CRTqm1x,m2x,…,mlx∈Rq. Let m′ represent m,21m,…,2l−1m. c is the length corresponding to message m′ and is the ciphertext of l=logq. Column vector c=c0,c1,…,cl−1T, where ci=2im+hsi+pei.


#### 3.2.3. Additive Homomorphism

c+ represents the result obtained by performing the homomorphic addition operation on two plaintexts. c' and c'′ represent the fresh ciphertexts in a form of a column vector. Because the ciphertexts are in the same form, only a simple addition operation is needed to achieve the homomorphic addition operation:(6)c+=c′+c″.


#### 3.2.4. Multiplicative Homomorphism

c∗ indicates the result obtained by performing the homomorphic multiplication operation on two ciphertexts. The ciphertext c∗ obtained through calculation is a column vector, which is in a same form as the original ciphertext. Therefore, no key exchange is required:(7)c∗=BitDecompc′⋅c″.


#### 3.2.5. Decryption Algorithm

c′ indicates the fresh ciphertext in a form of a column vector. When performing decryption operations, the first element c0′ of this ciphertext is selected for calculation:(8)m=c0′fmodp.According tom1x,m2x,…,mlxm←CRTq−1x∈Fqdl, l plaintexts can be decrypted.


### 3.3. Correctness Analysis

In this section, the encryption and decryption process of the scheme and the corresponding noise growth are analyzed.It can be known from the encryption and decryption algorithms that(9)DecEncm=c0′fmodp=mf+pgs0+pe0fmodp,=mf+pgs0+e0fmodp=mfmodp.Becausef≡1modp, c0′fmodp=m can be obtained from formula (9). Combine the Chinese remainder theorem m1x,m2x,…,mlxm←CRTq−1x∈Fqdl to decrypt to l plaintexts.Theorem 1 (encryption noise).
q,n,Rq,andχ are parameters of the preceding encryption scheme. The upper bound of χ is B. For any ←χ, calculate f=p⋅f′+1 and make f≡1modp. If fmodq∉Rq∗, sample again. Let h=Keygenf and c′←Ench,m; then, v exits and v∞≤2pφn1+pB2+B, which establishes the following equation:(10)c0′f=mf+pgs0+e0f∈Rq,where v=pgs0+e0f is the noise of the ciphertext. mf=mp⋅f′+1 contains part of noise of mf′ to correct messages that have few packaging [30]. Therefore, this part of noise is ignored in this paper.Proof.
According to the basic encryption schemec0′f=mf+pgs0+pe0f, let v=pgs0+pe0f be the noise of the fresh ciphertext. As the upper bound of χ is B, we can know that the upper bound of coefficient g,s,ande is B, and the upper bound of coefficient f is pB+1. Combining Theorem 4, we can obtain that the upper bound of coefficient gs0 is 2φnB2 and the upper bound of coefficient of e0f is 2φnBpB+1. Above all, the upper bound of coefficient v is 2pφn1+pB2+B, which is v∝≤2pφn1+pB2+B.Theorem 2 (decryption noise).
For anyfandc′∈Rq, f≡1modp. If c0′f=mf+v∈Rq is met and v∝≤q/2p, then(11)Decf,c0′=m.Proof.
Ifv∝≤q/2p, then(12)Decf,c0′=c0′fmodp=mf+pgs0+e0fmodp=mfmodp=m.
Combining Theorem1, we can reach the conclusion that when the noise is less than q/2p, the decryption is successful.


### 3.4. Homomorphism Analysis

Letc′ and c″ be the ciphertexts that are encrypted using the proposed scheme. The corresponding private key is f. It can be found from the decryption definition that cf=c0,c1,…,cl−1Tf=20mf+hs0f+pe0f,21mf+hs1f+pe1f,…,2l−1mf+hsl−1f+pel−1fT=20m,21m,…,2l−1mTf+hsg+pef=mPower of2f+2v, where v=hsg+pef.


#### 3.4.1. Additive Homomorphism

Letc+ be a ciphertext that is equivalent to the encryption of the sum of the two plaintexts. The ciphertext form is not changed, and the following can prove the additive homomorphism:(13)c+f=c′+c″f=c′f+c″f=m1Powerof2f+2v1+m2Powerof2f+2v2,=m1+m2Powerof2f+2v1+v2.From formula (13), ciphertext c+ can be seen as a result of the sum of two plaintexts. Therefore, this scheme has the additive homomorphism.


#### 3.4.2. Addition Noise

Letc0+ represent the first row of the fresh ciphertext on which the homomorphic addition operation is performed. E=2pφn1+pB2+B. According to the addition definition, c0+f=m1+m2Powerof2f+v1+v2, where v1=ps0′g+pe0′f and v2=ps0″g+pe0″f. Because v∝≤E, we can get v1+v2∝≤2E≤4φn1+pB2+B.


#### 3.4.3. Multiplicative Homomorphism

Letc∗ be a ciphertext that is equivalent to the encryption of the multiplication result of two plaintexts. The following can prove the multiplicative homomorphism:(14)c∗f=BitDecompc′⋅c″f=BitDecompc′⋅m2Powerof2f+2v2,=c′fm2+2BitDecompc′v2=m2m1Powerof2f+2v1+2BitDecompc′v2=m2m1Powerof2f+2v1m2+2BitDecompc′v2,where the value ranges of v1, v2, and BitDecompc′ are small. It can be seen from formula (14) that c∗ can be decrypted to the multiplication result of two plaintexts; therefore, this scheme has multiplicative homomorphism.


#### 3.4.4. Multiplication Noise

After the homomorphic addition operation is performed on two ciphertexts, the noise is the sum of the noises of two ciphertexts. After the homomorphic multiplication operation is performed, the noise is the multiplication result of the noises of two ciphertexts. Therefore, the factor that affects the correctness of decryption is multiplicative homomorphism. Therefore, this paper presents the noise obtained by performing the homomorphic multiplication and the calculated noise of the ciphertext circuit layerL.Letc0∗ represent the first row of the fresh ciphertext after the homomorphic multiplication operation was performed on it. Let v∗ represent the noise after a homomorphic multiplication operation. According to the multiplication definition, we have a formula c∗f=m2m1Powerof2f+2v1m2+2BitDecompc′v2, where v1=ps0′g+pe0′f, v2=ps0″g+pe0″f, v∝≤E, and c0′ is the first row of matrix BitDecompc′, a polynomial containing l−1 coefficients whose value is 0 or 1. Through the formula, we can get BitDecompc′v2∝≤nlE. Because m indicates φx/d plaintexts of mx, we can get 2v1m2∝≤2φx/dE. Therefore, v∝∗≤2nlE+2φx/dE.Assume that the noise of theith layer is ci; according to the homomorphic operation, we can get ci=ci−1∗ci−1. The calculated noise of this scheme after the second multiplication circuit is as follows:(15)c3=c2∗c2=2nlE+2E∗2nlE+2E=2nlE+2E2.A homomorphic multiplication operation is performed on2φx/d plaintexts. Therefore, the maximum noise deduced from the calculation of a circuit with a depth of L is(16)cL=2nlE+2EdL/φX.As long as2nlE+2EdL/φX does not exceed q/2p, the encryption of ciphertexts is correct. To compare with the F-NTRU scheme in terms of the noise, this paper analyzes the noise growth of the F-NTRU scheme.Letc′ and c″ be the ciphertexts encrypted by using the F-NTRU scheme. The corresponding private key is f,c0∗ represents the first row of the ciphertext after a homomorphic multiplication operation is performed, and v∗ represents the noise after a homomorphic multiplication operation is performed. According to the F-NTRU scheme, the multiplication definition is(17)c0∗f=m1⋅m2+c0″⋅c0,0′+c0″⋅m1+c0′⋅m2+⋯+c0,l−1′⋅cl−1″f.ci′=psi′g+pei′f=v and ci″=psi″g+pei″f=v. Because v∝≤E, we can get that c0″⋅m1∝=c0′⋅m2∝≤E, c0″⋅c0,0′+⋯+c0,l−1'⋅cl−1∝″=c0′⋅c0″≤nE2. Therefore, in the F-NTRU scheme, the noise after a homomorphic multiplication operation is performed is v∗∝≤2E+nE2. Assume that the noise of the ith layer is ci, ci=ci−1∗ci−1 according to the homomorphic operation, and the noise calculated after the second multiplication circuit in the F-NTRU scheme is as follows:(18)c3=c2∗c2=2E+nE2∗2E+nE2=2E+nE22.A homomorphic multiplication operation is performed on two plaintexts. Therefore, the maximum noise deduced from the calculation of a circuit with a depth ofL is(19)cL=2E+nE2L.As long as2E+nE2L does not exceed the encryption condition of the F-NTRU scheme, the ciphertext can be decrypted correctly. Combining the noise analysis of this scheme, we can get that compared with the F-NTRU scheme, the noise growth of this scheme after a homomorphic multiplication operation is performed decreases quadratically. In addition, the noise growth frequency of the F-NTRU scheme is φx/d times of this scheme. Therefore, this scheme has a better performance in the noise management.


#### 3.4.5. Multiplication Computation Optimization

As the noise depends mainly on the noise of the first ciphertext, changing the order of multiplication can optimize the homomorphic computation of the scheme. For example, there are 4 initial ciphertexts denoted asc1, c2, c3, and c4. The original order of computation is first calculate c5=c1⋅c2, then calculate c6=c3⋅c4, and then get the final ciphertext c7 obtained by calculating c7=c5⋅c6. However, when the order of computation changes to first calculate c5=c1⋅c2, then calculate c6=c3⋅c5, and then get the final ciphertext c7 obtained by calculating c7=c4⋅c6, the dependence on the noise of the multiplied ciphertext can be reduced because the noise growth of such schemes is asymmetric. For example, in the literature [31] when using the first computation order, the noise obtained after the calculation of the circuit with a depth of L is N+1L·E. However, when the second computation order is used, the noise obtained after the same calculation is L·N+1·E. The noise of the former grows exponentially, while the noise of the latter grows linearly; therefore, changing the multiplication order can optimize the homomorphic computation of the scheme and reduce the noise growth rate of the homomorphic multiplication, which means that the latter computation order can meet the calculation of a circuit with a depth more than L for the same noise threshold. For details, see the literature [32].


### 3.5. Security Analysis

Theorem 3.
Assume thatn=dv,d, and q≥8n are prime numbers, and q≡1modn is met. When r≥φn2ln6/π⋅q1/φn, there exists a probability of 1−n−ω1 that fandg meet the following formulas:(20)f≤ωnlnn.pr,(21)g≤ωlnn⋅r.
The security of this scheme at this time only relies on the RLWEΦ,n,q,χ assumption.Proof.
Whenfandg meet the above situation, there exists a probability of 1−n−ω1 that formulas (20) and (21) can be established [21]. For polynomial f′, same parameters also apply to the formula f=p⋅f′+1, that is, there exists a probability of 1−n−ω1 that f≤p⋅f′+1≤ωnlnn.p. Combining Theorem 4, we can get that there exists a probability of 1−n−ω1 that f≤1+2φnpf′≤ωnlnn.pr. For a power-of-two cyclotomic ring and a power-of-prime cyclotomic ring, we already prove that, in normal cases, polynomial f,gh have a relatively smaller value. Therefore, sample fandg with a certain width of r, and make the public key h distribute uniformly when its norm growth does not affect a single homomorphic multiplication operation. Combining the inverse property, we can get that the inverses of f,g, f−1,andg−1 that belong to Rq. Therefore, we get the following formula:(22)gf=g⋅f−1.
In the DSPR assumption,h=2g/f can be changed to 2h′. In the RLWE Φ,n,q,χ assumption, c∗=hs+2e+m can be changed to c∗=u+m. In c∗=hs+2e+m, the value range of e is very small and can be ignored. Combining formula (22), we can convert the form of fraction in the DSPR assumption to the form of multiplication in the RLWE Φ,n,q,χ assumption. Therefore, the security of this scheme can be reducible over the RLWE Φ,n,q,χ assumption.Theorem 4.
Assume thatλ is a security parameter, L is the number of layers of a circuit, and n is a dimension and a power of a prime number. Let R=Zx/Φnx. Under the prerequisite of RLWE Φ,n,q,χ assumption, this scheme is secure against IND-CPA attacks.Proof.
The following adopts the game hopping method to prove. In the formulas,AdvIND−CPAA indicates the advantage of attacker A in the Game.
Game0: standard IND-CPA game, that is, the challenger invokes the KeyGen algorithm of the scheme and makes attacker A get the generated public key pk. A has the capability of accessing the oracle machine for encryption. The challenger outputs the ciphertext c=Encpkmb, and attacker A tries to distinguish the plaintexts corresponding to c. In mb,b∈0,1,Game0 the advantage of attacker A is(23)AdvIND−CPAA=PrApk,Encpkm0=1−PrApk,Encpkm1=1.
Game1: the difference between Game1and Game0 is the method to generate a public key. In Game1, public key pk is not sampled from the Gaussian distribution with regular embedding and a private key sk. But it is directly selected at random in a uniform way from Rq∗. It can be obtained from Definition 3 that the result generated from the discrete Gaussian distribution cannot be distinguished from the distribution probability of Rq∗. It can be seen from the literature [33] that the error between the result generated from the discrete Gaussian distribution and the distributed result of Rq∗ is within 2−Ωn. Therefore, we get the following formula:(24)AdvGame1A−AdvIND−CPAA≤2−Ωn.
Game2: the difference between Game2and  Game1 is that the encryption algorithm of Game2 is not performed according to the scheme, but is randomly selected in a uniform way from 0,1. From Theorem 3, we can get that the DSPR Φ,n,q,χ assumption in this scheme has been reducible over RLWE Φ,n,q,χ. Therefore, in Game2 and Game1, the advantage difference of attacker A lies in the solution to the RLWE Φ,n,q,χ problem:(25)AdvGame2A−AdvGame1A≤RLWEΦ,n,q,χAdvA.
Game3: in Game3, the ciphertext c given by the challenger is no longer generated by the encryption algorithm. It is selected randomly in a uniform way from 0,1. The security analysis of Game3 is the same as Game2. We get the following formula:(26)AdvGame3A−AdvGame2A≤RLWEΦ,n,q,χAdvA.
InGame3, the public key pk and ciphertext c given by the challenger are all random, which are not related to plain text mb,b∈0,1. Therefore, attacker A has no advantage in Game3 that means(27)AdvGame3A=0.
From formulas (23)–(27), we can get(28)AdvIND−CPAA≤2−Ωn+RLWEΦ,n,q,χAdvA+RLWEΦ,n,q,χAdvA.
Above all, in theRLWEΦ,n,q,χ assumption, RLWEΦ,n,q,χAdvA can be ignored, which meets the requirement of Definition 5. Therefore, this scheme is secure against IND-CPA attacks.


## 3.1. SIMD Technique

It can be derived from Theorems1 and 2 that the power-of-prime cyclotomic ring can be decomposed into multiple irreducible polynomials in Fqx. Therefore, in this paper, we use the Chinese remainder theorem [28] to batch process the data of plaintext slots and perform homomorphic computations in parallel to improve the execution efficiency of the scheme. The specific procedure is given below.Decompose the entire plaintext spaceRp=R/pR into l subrings with the same size. The corresponding plaintext slots are Z2x/f1x,…,Z2x/flx, inside which mix plaintexts are waiting to be encrypted. Then, combine l plaintexts in the slots into a plaintext space. cx and c′x indicate the ciphertexts obtained after encryption using a same plaintext space, respectively, and their corresponding plaintexts are m1x,m2x,…,mlx and m1′x,m2′x,…,ml′x, respectively.The homomorphic operations that are performed in parallel onl plaintexts are as follows:(5)laddm1x,m2x,…,mlx,m1′x,m2′x,…,ml′x=m1x+m1′x,…,mlx+ml′x,lmultm1x,m2x,…,mlx,m1′x,m2′x,…,ml′x=m1x⋅m1′x,…,mlx⋅ml′x,where ladd and lmult indicate the batch homomorphic addition and homomorphic multiplication operations on plaintexts, respectively. Therefore, homomorphic operations can be regarded as being executed in parallel on the plaintext slots by using the SIMD technique. Because data at different indexes within the arrays can never interact, ladd and lmult operations are not sufficient to perform arbitrary computations on encrypted arrays. To obtain a complete operation set of data arrays, this paper introduces the lpermute operation described in the literature [29] to impose an arbitrary ordering on data in arrays and supports plaintext slots of mx⟶mx2i to move cyclically by i plaintext slots. When i=1, the plaintext slot of mx moves by one slot. Accordingly, the plaintext of each plaintext slot is changed to m2x,mlx,…,m1x, so as to perform the whole operations on the data. When the ciphertext requires decryption, the Chinese remainder theorem is used for reversible processing to decrypt to l plaintexts.


## 3.2. Scheme Construction

Assume thatλ is a security parameter, L is the number of circuit layers, and n is a dimension and a power of a prime number. Let R=Zx/Φnx, where Φnx=∏i=1,gcdi,n=1nx−ξi is cyclotomic polynomial, the number of times for each fix is d,φn=dl=nλ,L,Fqdl is the vector space of plaintexts, and mapping CRTq is the isomorphic mapping from Fqdl to Rq.


### 3.2.1. Key Generation Algorithm

Select a relatively large standard errorσ, and make f represent f=p⋅f′+1 where f′ is a polynomial sampled from a discrete Gaussian distribution Dzn,σx with regular embedding. Input nandq∈Z,p∈Rq∗,andσ∈R, where Rq∗ is a collection of reversible elements in Rq. Rq=R/qR=Zqx/Φ. Output sk,pk∈R×Rq∗. The detailed procedure is as follows:First samplef′ from a discrete Gaussian distribution Dzn,σx with regular embedding; let f=p⋅f′+1. If fmodq∉Rq∗, sample again.Then, sampleg from a discrete Gaussian distribution Dzn,σx with regular embedding. If gmodq∉Rq∗, sample again.Finally, returnsk=f and pk=h=pgf−1∈Rq∗.


### 3.2.2. Encryption Algorithm

Use the Chinese remainder theorem to calculate the plaintextm←CRTqm1x,m2x,…,mlx∈Rq. Let m′ represent m,21m,…,2l−1m. c is the length corresponding to message m′ and is the ciphertext of l=logq. Column vector c=c0,c1,…,cl−1T, where ci=2im+hsi+pei.


### 3.2.3. Additive Homomorphism

c+ represents the result obtained by performing the homomorphic addition operation on two plaintexts. c' and c'′ represent the fresh ciphertexts in a form of a column vector. Because the ciphertexts are in the same form, only a simple addition operation is needed to achieve the homomorphic addition operation:(6)c+=c′+c″.


### 3.2.4. Multiplicative Homomorphism

c∗ indicates the result obtained by performing the homomorphic multiplication operation on two ciphertexts. The ciphertext c∗ obtained through calculation is a column vector, which is in a same form as the original ciphertext. Therefore, no key exchange is required:(7)c∗=BitDecompc′⋅c″.


### 3.2.5. Decryption Algorithm

c′ indicates the fresh ciphertext in a form of a column vector. When performing decryption operations, the first element c0′ of this ciphertext is selected for calculation:(8)m=c0′fmodp.According tom1x,m2x,…,mlxm←CRTq−1x∈Fqdl, l plaintexts can be decrypted.


## 3.2.1. Key Generation Algorithm

Select a relatively large standard errorσ, and make f represent f=p⋅f′+1 where f′ is a polynomial sampled from a discrete Gaussian distribution Dzn,σx with regular embedding. Input nandq∈Z,p∈Rq∗,andσ∈R, where Rq∗ is a collection of reversible elements in Rq. Rq=R/qR=Zqx/Φ. Output sk,pk∈R×Rq∗. The detailed procedure is as follows:First samplef′ from a discrete Gaussian distribution Dzn,σx with regular embedding; let f=p⋅f′+1. If fmodq∉Rq∗, sample again.Then, sampleg from a discrete Gaussian distribution Dzn,σx with regular embedding. If gmodq∉Rq∗, sample again.Finally, returnsk=f and pk=h=pgf−1∈Rq∗.


## 3.2.2. Encryption Algorithm

Use the Chinese remainder theorem to calculate the plaintextm←CRTqm1x,m2x,…,mlx∈Rq. Let m′ represent m,21m,…,2l−1m. c is the length corresponding to message m′ and is the ciphertext of l=logq. Column vector c=c0,c1,…,cl−1T, where ci=2im+hsi+pei.


## 3.2.3. Additive Homomorphism

c+ represents the result obtained by performing the homomorphic addition operation on two plaintexts. c' and c'′ represent the fresh ciphertexts in a form of a column vector. Because the ciphertexts are in the same form, only a simple addition operation is needed to achieve the homomorphic addition operation:(6)c+=c′+c″.


## 3.2.4. Multiplicative Homomorphism

c∗ indicates the result obtained by performing the homomorphic multiplication operation on two ciphertexts. The ciphertext c∗ obtained through calculation is a column vector, which is in a same form as the original ciphertext. Therefore, no key exchange is required:(7)c∗=BitDecompc′⋅c″.


## 3.2.5. Decryption Algorithm

c′ indicates the fresh ciphertext in a form of a column vector. When performing decryption operations, the first element c0′ of this ciphertext is selected for calculation:(8)m=c0′fmodp.According tom1x,m2x,…,mlxm←CRTq−1x∈Fqdl, l plaintexts can be decrypted.


## 3.3. Correctness Analysis

In this section, the encryption and decryption process of the scheme and the corresponding noise growth are analyzed.It can be known from the encryption and decryption algorithms that(9)DecEncm=c0′fmodp=mf+pgs0+pe0fmodp,=mf+pgs0+e0fmodp=mfmodp.Becausef≡1modp, c0′fmodp=m can be obtained from formula (9). Combine the Chinese remainder theorem m1x,m2x,…,mlxm←CRTq−1x∈Fqdl to decrypt to l plaintexts.Theorem 1 (encryption noise).
q,n,Rq,andχ are parameters of the preceding encryption scheme. The upper bound of χ is B. For any ←χ, calculate f=p⋅f′+1 and make f≡1modp. If fmodq∉Rq∗, sample again. Let h=Keygenf and c′←Ench,m; then, v exits and v∞≤2pφn1+pB2+B, which establishes the following equation:(10)c0′f=mf+pgs0+e0f∈Rq,where v=pgs0+e0f is the noise of the ciphertext. mf=mp⋅f′+1 contains part of noise of mf′ to correct messages that have few packaging [30]. Therefore, this part of noise is ignored in this paper.Proof.
According to the basic encryption schemec0′f=mf+pgs0+pe0f, let v=pgs0+pe0f be the noise of the fresh ciphertext. As the upper bound of χ is B, we can know that the upper bound of coefficient g,s,ande is B, and the upper bound of coefficient f is pB+1. Combining Theorem 4, we can obtain that the upper bound of coefficient gs0 is 2φnB2 and the upper bound of coefficient of e0f is 2φnBpB+1. Above all, the upper bound of coefficient v is 2pφn1+pB2+B, which is v∝≤2pφn1+pB2+B.Theorem 2 (decryption noise).
For anyfandc′∈Rq, f≡1modp. If c0′f=mf+v∈Rq is met and v∝≤q/2p, then(11)Decf,c0′=m.Proof.
Ifv∝≤q/2p, then(12)Decf,c0′=c0′fmodp=mf+pgs0+e0fmodp=mfmodp=m.
Combining Theorem1, we can reach the conclusion that when the noise is less than q/2p, the decryption is successful.


## 3.4. Homomorphism Analysis

Letc′ and c″ be the ciphertexts that are encrypted using the proposed scheme. The corresponding private key is f. It can be found from the decryption definition that cf=c0,c1,…,cl−1Tf=20mf+hs0f+pe0f,21mf+hs1f+pe1f,…,2l−1mf+hsl−1f+pel−1fT=20m,21m,…,2l−1mTf+hsg+pef=mPower of2f+2v, where v=hsg+pef.


### 3.4.1. Additive Homomorphism

Letc+ be a ciphertext that is equivalent to the encryption of the sum of the two plaintexts. The ciphertext form is not changed, and the following can prove the additive homomorphism:(13)c+f=c′+c″f=c′f+c″f=m1Powerof2f+2v1+m2Powerof2f+2v2,=m1+m2Powerof2f+2v1+v2.From formula (13), ciphertext c+ can be seen as a result of the sum of two plaintexts. Therefore, this scheme has the additive homomorphism.


### 3.4.2. Addition Noise

Letc0+ represent the first row of the fresh ciphertext on which the homomorphic addition operation is performed. E=2pφn1+pB2+B. According to the addition definition, c0+f=m1+m2Powerof2f+v1+v2, where v1=ps0′g+pe0′f and v2=ps0″g+pe0″f. Because v∝≤E, we can get v1+v2∝≤2E≤4φn1+pB2+B.


### 3.4.3. Multiplicative Homomorphism

Letc∗ be a ciphertext that is equivalent to the encryption of the multiplication result of two plaintexts. The following can prove the multiplicative homomorphism:(14)c∗f=BitDecompc′⋅c″f=BitDecompc′⋅m2Powerof2f+2v2,=c′fm2+2BitDecompc′v2=m2m1Powerof2f+2v1+2BitDecompc′v2=m2m1Powerof2f+2v1m2+2BitDecompc′v2,where the value ranges of v1, v2, and BitDecompc′ are small. It can be seen from formula (14) that c∗ can be decrypted to the multiplication result of two plaintexts; therefore, this scheme has multiplicative homomorphism.


### 3.4.4. Multiplication Noise

After the homomorphic addition operation is performed on two ciphertexts, the noise is the sum of the noises of two ciphertexts. After the homomorphic multiplication operation is performed, the noise is the multiplication result of the noises of two ciphertexts. Therefore, the factor that affects the correctness of decryption is multiplicative homomorphism. Therefore, this paper presents the noise obtained by performing the homomorphic multiplication and the calculated noise of the ciphertext circuit layerL.Letc0∗ represent the first row of the fresh ciphertext after the homomorphic multiplication operation was performed on it. Let v∗ represent the noise after a homomorphic multiplication operation. According to the multiplication definition, we have a formula c∗f=m2m1Powerof2f+2v1m2+2BitDecompc′v2, where v1=ps0′g+pe0′f, v2=ps0″g+pe0″f, v∝≤E, and c0′ is the first row of matrix BitDecompc′, a polynomial containing l−1 coefficients whose value is 0 or 1. Through the formula, we can get BitDecompc′v2∝≤nlE. Because m indicates φx/d plaintexts of mx, we can get 2v1m2∝≤2φx/dE. Therefore, v∝∗≤2nlE+2φx/dE.Assume that the noise of theith layer is ci; according to the homomorphic operation, we can get ci=ci−1∗ci−1. The calculated noise of this scheme after the second multiplication circuit is as follows:(15)c3=c2∗c2=2nlE+2E∗2nlE+2E=2nlE+2E2.A homomorphic multiplication operation is performed on2φx/d plaintexts. Therefore, the maximum noise deduced from the calculation of a circuit with a depth of L is(16)cL=2nlE+2EdL/φX.As long as2nlE+2EdL/φX does not exceed q/2p, the encryption of ciphertexts is correct. To compare with the F-NTRU scheme in terms of the noise, this paper analyzes the noise growth of the F-NTRU scheme.Letc′ and c″ be the ciphertexts encrypted by using the F-NTRU scheme. The corresponding private key is f,c0∗ represents the first row of the ciphertext after a homomorphic multiplication operation is performed, and v∗ represents the noise after a homomorphic multiplication operation is performed. According to the F-NTRU scheme, the multiplication definition is(17)c0∗f=m1⋅m2+c0″⋅c0,0′+c0″⋅m1+c0′⋅m2+⋯+c0,l−1′⋅cl−1″f.ci′=psi′g+pei′f=v and ci″=psi″g+pei″f=v. Because v∝≤E, we can get that c0″⋅m1∝=c0′⋅m2∝≤E, c0″⋅c0,0′+⋯+c0,l−1'⋅cl−1∝″=c0′⋅c0″≤nE2. Therefore, in the F-NTRU scheme, the noise after a homomorphic multiplication operation is performed is v∗∝≤2E+nE2. Assume that the noise of the ith layer is ci, ci=ci−1∗ci−1 according to the homomorphic operation, and the noise calculated after the second multiplication circuit in the F-NTRU scheme is as follows:(18)c3=c2∗c2=2E+nE2∗2E+nE2=2E+nE22.A homomorphic multiplication operation is performed on two plaintexts. Therefore, the maximum noise deduced from the calculation of a circuit with a depth ofL is(19)cL=2E+nE2L.As long as2E+nE2L does not exceed the encryption condition of the F-NTRU scheme, the ciphertext can be decrypted correctly. Combining the noise analysis of this scheme, we can get that compared with the F-NTRU scheme, the noise growth of this scheme after a homomorphic multiplication operation is performed decreases quadratically. In addition, the noise growth frequency of the F-NTRU scheme is φx/d times of this scheme. Therefore, this scheme has a better performance in the noise management.


### 3.4.5. Multiplication Computation Optimization

As the noise depends mainly on the noise of the first ciphertext, changing the order of multiplication can optimize the homomorphic computation of the scheme. For example, there are 4 initial ciphertexts denoted asc1, c2, c3, and c4. The original order of computation is first calculate c5=c1⋅c2, then calculate c6=c3⋅c4, and then get the final ciphertext c7 obtained by calculating c7=c5⋅c6. However, when the order of computation changes to first calculate c5=c1⋅c2, then calculate c6=c3⋅c5, and then get the final ciphertext c7 obtained by calculating c7=c4⋅c6, the dependence on the noise of the multiplied ciphertext can be reduced because the noise growth of such schemes is asymmetric. For example, in the literature [31] when using the first computation order, the noise obtained after the calculation of the circuit with a depth of L is N+1L·E. However, when the second computation order is used, the noise obtained after the same calculation is L·N+1·E. The noise of the former grows exponentially, while the noise of the latter grows linearly; therefore, changing the multiplication order can optimize the homomorphic computation of the scheme and reduce the noise growth rate of the homomorphic multiplication, which means that the latter computation order can meet the calculation of a circuit with a depth more than L for the same noise threshold. For details, see the literature [32].


## 3.4.1. Additive Homomorphism

Letc+ be a ciphertext that is equivalent to the encryption of the sum of the two plaintexts. The ciphertext form is not changed, and the following can prove the additive homomorphism:(13)c+f=c′+c″f=c′f+c″f=m1Powerof2f+2v1+m2Powerof2f+2v2,=m1+m2Powerof2f+2v1+v2.From formula (13), ciphertext c+ can be seen as a result of the sum of two plaintexts. Therefore, this scheme has the additive homomorphism.


## 3.4.2. Addition Noise

Letc0+ represent the first row of the fresh ciphertext on which the homomorphic addition operation is performed. E=2pφn1+pB2+B. According to the addition definition, c0+f=m1+m2Powerof2f+v1+v2, where v1=ps0′g+pe0′f and v2=ps0″g+pe0″f. Because v∝≤E, we can get v1+v2∝≤2E≤4φn1+pB2+B.


## 3.4.3. Multiplicative Homomorphism

Letc∗ be a ciphertext that is equivalent to the encryption of the multiplication result of two plaintexts. The following can prove the multiplicative homomorphism:(14)c∗f=BitDecompc′⋅c″f=BitDecompc′⋅m2Powerof2f+2v2,=c′fm2+2BitDecompc′v2=m2m1Powerof2f+2v1+2BitDecompc′v2=m2m1Powerof2f+2v1m2+2BitDecompc′v2,where the value ranges of v1, v2, and BitDecompc′ are small. It can be seen from formula (14) that c∗ can be decrypted to the multiplication result of two plaintexts; therefore, this scheme has multiplicative homomorphism.


## 3.4.4. Multiplication Noise

After the homomorphic addition operation is performed on two ciphertexts, the noise is the sum of the noises of two ciphertexts. After the homomorphic multiplication operation is performed, the noise is the multiplication result of the noises of two ciphertexts. Therefore, the factor that affects the correctness of decryption is multiplicative homomorphism. Therefore, this paper presents the noise obtained by performing the homomorphic multiplication and the calculated noise of the ciphertext circuit layerL.Letc0∗ represent the first row of the fresh ciphertext after the homomorphic multiplication operation was performed on it. Let v∗ represent the noise after a homomorphic multiplication operation. According to the multiplication definition, we have a formula c∗f=m2m1Powerof2f+2v1m2+2BitDecompc′v2, where v1=ps0′g+pe0′f, v2=ps0″g+pe0″f, v∝≤E, and c0′ is the first row of matrix BitDecompc′, a polynomial containing l−1 coefficients whose value is 0 or 1. Through the formula, we can get BitDecompc′v2∝≤nlE. Because m indicates φx/d plaintexts of mx, we can get 2v1m2∝≤2φx/dE. Therefore, v∝∗≤2nlE+2φx/dE.Assume that the noise of theith layer is ci; according to the homomorphic operation, we can get ci=ci−1∗ci−1. The calculated noise of this scheme after the second multiplication circuit is as follows:(15)c3=c2∗c2=2nlE+2E∗2nlE+2E=2nlE+2E2.A homomorphic multiplication operation is performed on2φx/d plaintexts. Therefore, the maximum noise deduced from the calculation of a circuit with a depth of L is(16)cL=2nlE+2EdL/φX.As long as2nlE+2EdL/φX does not exceed q/2p, the encryption of ciphertexts is correct. To compare with the F-NTRU scheme in terms of the noise, this paper analyzes the noise growth of the F-NTRU scheme.Letc′ and c″ be the ciphertexts encrypted by using the F-NTRU scheme. The corresponding private key is f,c0∗ represents the first row of the ciphertext after a homomorphic multiplication operation is performed, and v∗ represents the noise after a homomorphic multiplication operation is performed. According to the F-NTRU scheme, the multiplication definition is(17)c0∗f=m1⋅m2+c0″⋅c0,0′+c0″⋅m1+c0′⋅m2+⋯+c0,l−1′⋅cl−1″f.ci′=psi′g+pei′f=v and ci″=psi″g+pei″f=v. Because v∝≤E, we can get that c0″⋅m1∝=c0′⋅m2∝≤E, c0″⋅c0,0′+⋯+c0,l−1'⋅cl−1∝″=c0′⋅c0″≤nE2. Therefore, in the F-NTRU scheme, the noise after a homomorphic multiplication operation is performed is v∗∝≤2E+nE2. Assume that the noise of the ith layer is ci, ci=ci−1∗ci−1 according to the homomorphic operation, and the noise calculated after the second multiplication circuit in the F-NTRU scheme is as follows:(18)c3=c2∗c2=2E+nE2∗2E+nE2=2E+nE22.A homomorphic multiplication operation is performed on two plaintexts. Therefore, the maximum noise deduced from the calculation of a circuit with a depth ofL is(19)cL=2E+nE2L.As long as2E+nE2L does not exceed the encryption condition of the F-NTRU scheme, the ciphertext can be decrypted correctly. Combining the noise analysis of this scheme, we can get that compared with the F-NTRU scheme, the noise growth of this scheme after a homomorphic multiplication operation is performed decreases quadratically. In addition, the noise growth frequency of the F-NTRU scheme is φx/d times of this scheme. Therefore, this scheme has a better performance in the noise management.


## 3.4.5. Multiplication Computation Optimization

As the noise depends mainly on the noise of the first ciphertext, changing the order of multiplication can optimize the homomorphic computation of the scheme. For example, there are 4 initial ciphertexts denoted asc1, c2, c3, and c4. The original order of computation is first calculate c5=c1⋅c2, then calculate c6=c3⋅c4, and then get the final ciphertext c7 obtained by calculating c7=c5⋅c6. However, when the order of computation changes to first calculate c5=c1⋅c2, then calculate c6=c3⋅c5, and then get the final ciphertext c7 obtained by calculating c7=c4⋅c6, the dependence on the noise of the multiplied ciphertext can be reduced because the noise growth of such schemes is asymmetric. For example, in the literature [31] when using the first computation order, the noise obtained after the calculation of the circuit with a depth of L is N+1L·E. However, when the second computation order is used, the noise obtained after the same calculation is L·N+1·E. The noise of the former grows exponentially, while the noise of the latter grows linearly; therefore, changing the multiplication order can optimize the homomorphic computation of the scheme and reduce the noise growth rate of the homomorphic multiplication, which means that the latter computation order can meet the calculation of a circuit with a depth more than L for the same noise threshold. For details, see the literature [32].


## 3.5. Security Analysis

Theorem 3.
Assume thatn=dv,d, and q≥8n are prime numbers, and q≡1modn is met. When r≥φn2ln6/π⋅q1/φn, there exists a probability of 1−n−ω1 that fandg meet the following formulas:(20)f≤ωnlnn.pr,(21)g≤ωlnn⋅r.
The security of this scheme at this time only relies on the RLWEΦ,n,q,χ assumption.Proof.
Whenfandg meet the above situation, there exists a probability of 1−n−ω1 that formulas (20) and (21) can be established [21]. For polynomial f′, same parameters also apply to the formula f=p⋅f′+1, that is, there exists a probability of 1−n−ω1 that f≤p⋅f′+1≤ωnlnn.p. Combining Theorem 4, we can get that there exists a probability of 1−n−ω1 that f≤1+2φnpf′≤ωnlnn.pr. For a power-of-two cyclotomic ring and a power-of-prime cyclotomic ring, we already prove that, in normal cases, polynomial f,gh have a relatively smaller value. Therefore, sample fandg with a certain width of r, and make the public key h distribute uniformly when its norm growth does not affect a single homomorphic multiplication operation. Combining the inverse property, we can get that the inverses of f,g, f−1,andg−1 that belong to Rq. Therefore, we get the following formula:(22)gf=g⋅f−1.
In the DSPR assumption,h=2g/f can be changed to 2h′. In the RLWE Φ,n,q,χ assumption, c∗=hs+2e+m can be changed to c∗=u+m. In c∗=hs+2e+m, the value range of e is very small and can be ignored. Combining formula (22), we can convert the form of fraction in the DSPR assumption to the form of multiplication in the RLWE Φ,n,q,χ assumption. Therefore, the security of this scheme can be reducible over the RLWE Φ,n,q,χ assumption.Theorem 4.
Assume thatλ is a security parameter, L is the number of layers of a circuit, and n is a dimension and a power of a prime number. Let R=Zx/Φnx. Under the prerequisite of RLWE Φ,n,q,χ assumption, this scheme is secure against IND-CPA attacks.Proof.
The following adopts the game hopping method to prove. In the formulas,AdvIND−CPAA indicates the advantage of attacker A in the Game.
Game0: standard IND-CPA game, that is, the challenger invokes the KeyGen algorithm of the scheme and makes attacker A get the generated public key pk. A has the capability of accessing the oracle machine for encryption. The challenger outputs the ciphertext c=Encpkmb, and attacker A tries to distinguish the plaintexts corresponding to c. In mb,b∈0,1,Game0 the advantage of attacker A is(23)AdvIND−CPAA=PrApk,Encpkm0=1−PrApk,Encpkm1=1.
Game1: the difference between Game1and Game0 is the method to generate a public key. In Game1, public key pk is not sampled from the Gaussian distribution with regular embedding and a private key sk. But it is directly selected at random in a uniform way from Rq∗. It can be obtained from Definition 3 that the result generated from the discrete Gaussian distribution cannot be distinguished from the distribution probability of Rq∗. It can be seen from the literature [33] that the error between the result generated from the discrete Gaussian distribution and the distributed result of Rq∗ is within 2−Ωn. Therefore, we get the following formula:(24)AdvGame1A−AdvIND−CPAA≤2−Ωn.
Game2: the difference between Game2and  Game1 is that the encryption algorithm of Game2 is not performed according to the scheme, but is randomly selected in a uniform way from 0,1. From Theorem 3, we can get that the DSPR Φ,n,q,χ assumption in this scheme has been reducible over RLWE Φ,n,q,χ. Therefore, in Game2 and Game1, the advantage difference of attacker A lies in the solution to the RLWE Φ,n,q,χ problem:(25)AdvGame2A−AdvGame1A≤RLWEΦ,n,q,χAdvA.
Game3: in Game3, the ciphertext c given by the challenger is no longer generated by the encryption algorithm. It is selected randomly in a uniform way from 0,1. The security analysis of Game3 is the same as Game2. We get the following formula:(26)AdvGame3A−AdvGame2A≤RLWEΦ,n,q,χAdvA.
InGame3, the public key pk and ciphertext c given by the challenger are all random, which are not related to plain text mb,b∈0,1. Therefore, attacker A has no advantage in Game3 that means(27)AdvGame3A=0.
From formulas (23)–(27), we can get(28)AdvIND−CPAA≤2−Ωn+RLWEΦ,n,q,χAdvA+RLWEΦ,n,q,χAdvA.
Above all, in theRLWEΦ,n,q,χ assumption, RLWEΦ,n,q,χAdvA can be ignored, which meets the requirement of Definition 5. Therefore, this scheme is secure against IND-CPA attacks.


## 4. Performance Analysis

In this section, the proposed scheme and the F-NTRU scheme are analyzed to show the advantages of the proposed scheme in terms of ciphertext size and homomorphic computational complexity.


### 4.1. Ciphertext Size Analysis

The ciphertext of the F-NTRU scheme consists of two polynomials whose number of times is less than2n, and the ciphertext extension is in a matrix form of ⌈logq⌉⋅⌈logq⌉. From Theorem 3, we can get that the upper bound of the size is ⌈logq⌉2⋅n⋅logq2. The public key used by the F-NTRU scheme consists of two polynomials, and the size is n⋅logq2. During decryption, a polynomial private key has the number of times less than 2n and coefficient less than 2B+1, and the size is log2B+1. In this scheme, the ciphertext is a polynomial in a form of a dimension vector logq. It can be deduced from Theorem 4 that the ciphertext size of this scheme is 2⌈logq⌉⋅φn⋅logq2. The cyclotomic polynomial of the public key and private key of the scheme in this paper is different from that of the F-NTRU scheme. Therefore, the sizes of the public key and private key in this scheme are changed and are 2φn⋅logq2 and log2B+1, respectively, compared with the F-NTRU scheme. The details are shown in Table 1.Table 1
Comparison of the size of ciphertext.
SchemeCiphertext sizePublic key sizePrivate key sizePolynomialF-NTRU⌈logq⌉2⋅n⋅logq2n⋅logq2log2B+1Φnx=xn+1Scheme in this paper2⌈logq⌉⋅φn⋅logq22φn⋅logq2log2B+1Φnx=Φdxdv−1As can be seen from Table1, compared with the F-NTRU scheme, this scheme optimizes the public key size while keeping the private key size unchanged. The ciphertext size of this scheme is reduced from quadratic to cubic, which gains more advantages in storage and transmission.


### 4.2. Computational Complexity Analysis

Assume that the time for performing a vector addition operation isTadd and for performing a vector multiplication operation is Tmult. In the F-NTRU scheme, performing a homomorphic addition operation C′+C″ is equivalent to performing l times of vector addition operations and performing a homomorphic multiplication operation C′⋅C″ is equivalent to performing l×l times of vector multiplication operations. However, in this scheme, performing a homomorphic addition operation C′+C″ is equivalent to performing one single vector addition operation and performing a homomorphic multiplication operation BitDecompc′⋅c″ is equivalent to performing l times of vector multiplication operations. Because in the BitDecompc′ matrix form of BitDecompc′⋅c″, c″ is in a form of a vector. The computational volume of the matrix calculation and a column vector operation actually equal l times of vector multiplication operations. In addition, in this scheme, multiple plaintexts are packed into one ciphertext using the Chinese remainder theorem for parallel processing, which effectively improves the computational efficiency. For details, see Table 2:Table 2
Comparison of computational complexity.
SchemeCiphertextCommunication volume (pieces)Computational volume for addition operationsComputational volume for multiplication operationsF-NTRU2φx/d2φx/dφx/d⋅l⋅Taddφx/d⋅l⋅l⋅TmultScheme in this paper2φx/d2Taddl⋅TmultFrom Table2, it can be seen that this scheme improves the efficiency by a factor of l +1 by changing the ciphertext to a form of a vector. The adoption of the batch processing technique also helps enhance the computational efficiency by a factor of φx/d+1. Therefore, in terms of efficiency, this scheme overall improves by a factor of lφx/d+1 compared with the F-NTRU scheme. In terms of communication cost, the plaintext space in this scheme is divided into φx/d plaintext slots, which has lower communication cost and computational cost. Normally, matrix-vector multiplication is Ol2 order of magnitude faster than matrix multiplication, but since this scheme does not use the flattening technique to binarize the ciphertexts, the multiplication operation of values is slower than that of binarized values. Fortunately, the actual time spent in computing a large number of products of matrix vectors (value 0) is greatly reduced. This is a major breakthrough in terms of efficiency after the matrix multiplication is replaced with the matrix-vector multiplication in this scheme.


## 4.1. Ciphertext Size Analysis

The ciphertext of the F-NTRU scheme consists of two polynomials whose number of times is less than2n, and the ciphertext extension is in a matrix form of ⌈logq⌉⋅⌈logq⌉. From Theorem 3, we can get that the upper bound of the size is ⌈logq⌉2⋅n⋅logq2. The public key used by the F-NTRU scheme consists of two polynomials, and the size is n⋅logq2. During decryption, a polynomial private key has the number of times less than 2n and coefficient less than 2B+1, and the size is log2B+1. In this scheme, the ciphertext is a polynomial in a form of a dimension vector logq. It can be deduced from Theorem 4 that the ciphertext size of this scheme is 2⌈logq⌉⋅φn⋅logq2. The cyclotomic polynomial of the public key and private key of the scheme in this paper is different from that of the F-NTRU scheme. Therefore, the sizes of the public key and private key in this scheme are changed and are 2φn⋅logq2 and log2B+1, respectively, compared with the F-NTRU scheme. The details are shown in Table 1.Table 1
Comparison of the size of ciphertext.
SchemeCiphertext sizePublic key sizePrivate key sizePolynomialF-NTRU⌈logq⌉2⋅n⋅logq2n⋅logq2log2B+1Φnx=xn+1Scheme in this paper2⌈logq⌉⋅φn⋅logq22φn⋅logq2log2B+1Φnx=Φdxdv−1As can be seen from Table1, compared with the F-NTRU scheme, this scheme optimizes the public key size while keeping the private key size unchanged. The ciphertext size of this scheme is reduced from quadratic to cubic, which gains more advantages in storage and transmission.


## 4.2. Computational Complexity Analysis

Assume that the time for performing a vector addition operation isTadd and for performing a vector multiplication operation is Tmult. In the F-NTRU scheme, performing a homomorphic addition operation C′+C″ is equivalent to performing l times of vector addition operations and performing a homomorphic multiplication operation C′⋅C″ is equivalent to performing l×l times of vector multiplication operations. However, in this scheme, performing a homomorphic addition operation C′+C″ is equivalent to performing one single vector addition operation and performing a homomorphic multiplication operation BitDecompc′⋅c″ is equivalent to performing l times of vector multiplication operations. Because in the BitDecompc′ matrix form of BitDecompc′⋅c″, c″ is in a form of a vector. The computational volume of the matrix calculation and a column vector operation actually equal l times of vector multiplication operations. In addition, in this scheme, multiple plaintexts are packed into one ciphertext using the Chinese remainder theorem for parallel processing, which effectively improves the computational efficiency. For details, see Table 2:Table 2
Comparison of computational complexity.
SchemeCiphertextCommunication volume (pieces)Computational volume for addition operationsComputational volume for multiplication operationsF-NTRU2φx/d2φx/dφx/d⋅l⋅Taddφx/d⋅l⋅l⋅TmultScheme in this paper2φx/d2Taddl⋅TmultFrom Table2, it can be seen that this scheme improves the efficiency by a factor of l +1 by changing the ciphertext to a form of a vector. The adoption of the batch processing technique also helps enhance the computational efficiency by a factor of φx/d+1. Therefore, in terms of efficiency, this scheme overall improves by a factor of lφx/d+1 compared with the F-NTRU scheme. In terms of communication cost, the plaintext space in this scheme is divided into φx/d plaintext slots, which has lower communication cost and computational cost. Normally, matrix-vector multiplication is Ol2 order of magnitude faster than matrix multiplication, but since this scheme does not use the flattening technique to binarize the ciphertexts, the multiplication operation of values is slower than that of binarized values. Fortunately, the actual time spent in computing a large number of products of matrix vectors (value 0) is greatly reduced. This is a major breakthrough in terms of efficiency after the matrix multiplication is replaced with the matrix-vector multiplication in this scheme.


## 5. Conclusion

To solve the problems of constructing fully homomorphic encryption schemes using approximate eigenvectors, this paper proposes an NTRU-based fully homomorphic encryption scheme based on a power-of-prime cyclotomic ring. This scheme can eliminate the DSPR assumption under certain conditions so that the scheme only relies on the RLWE assumption and can also be secure against IND-CPA attacks. The ciphertext of this scheme is in a form of a vector, and the use of matrix-vector multiplication operations instead of complex matrix multiplication operations effectively improves the efficiency of the scheme. Meanwhile, the noise growth decreases quadratically. Combining the multiplication execution order optimization method, the scheme performs better in noise management. Compared with the F-NTRU scheme, the ciphertext of this scheme has obvious advantages in storage, transportation, and computation, but the reduction in the number of times to decompose polynomial mods using the Chinese remainder theorem in this scheme affects the security of the RLWEΦ,n,q,χ assumption. Therefore, security parameters need to be selected more stringently in order to ensure the data security.



---

*Source: 9914961-2021-08-09.xml*