# A More Efficient Fully Homomorphic Encryption Scheme Based on GSW and DM Schemes

Authors: Xun Wang; Tao Luo; Jianfeng Li
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Achieving both simplicity and efficiency in fully homomorphic encryption (FHE) schemes is important for practical applications. In the simple FHE scheme proposed by Ducas and Micciancio (DM), ciphertexts are refreshed after each homomorphic operation. And ciphertext refreshing has become a major bottleneck for the overall efficiency of the scheme. In this paper, we propose a more efficient FHE scheme with fewer ciphertext refreshings. Based on the DM scheme and another simple FHE scheme proposed by Gentry, Sahai, and Waters (GSW), ciphertext matrix operations and ciphertext vector additions are both applied in our scheme. Compared with the DM scheme, one more homomorphic NOT AND (NAND) operation can be performed on ciphertexts before ciphertext refreshing. Results show that, under the same security parameters, the computational cost of our scheme is obviously lower than that of GSW and DM schemes for a depth-2 binary circuit with NAND gates. And the error rate of our scheme is kept at a sufficiently low level.


---

## Body

## 1. Introduction

With the rapid development of computer networks and big data, the cloud has been playing an important role in storing and processing huge amounts of data [1]. The cloud provides abundant, flexible, and on-demand remote storage and computational resources for network users. However, the cloud is not fully trustable, and users do not have full control power on the data stored in the cloud. Data in the cloud are faced with the risk of leakage, and personal privacy is seriously threatened. In some recent research works, approaches based on network defense have been proposed for guaranteeing cloud security [2–6]. Nevertheless, data encryption provides a more fundamental and universal privacy protection for data in the cloud. In traditional encryption techniques, when the encrypted data are stored in the cloud, they need to be decrypted before computation, and personal privacy is still seriously threatened. Homomorphic encryption allows ciphertext operations to be performed directly; thus an untrusted third party can process the ciphertexts without decrypting them. The decryption of the result of ciphertext operation is equivalent to the result of corresponding plaintext operation. Furthermore, fully homomorphic encryption (FHE) allows arbitrary operations to be performed on ciphertexts. Concretely, let Enc and Dec denote encryption and decryption algorithms, respectively. And let mi and ci denote the plaintexts and corresponding ciphertexts, respectively, where i=1,2,…,l and ci=Enc(mi). For a function fm of plaintexts m1,m2,…,ml, and a corresponding function fc of ciphertexts c1,c2,…,cl, FHE schemes satisfy the following property:(1)Decfcc1,c2,…,cl=fmm1,m2,…,mlThis ideal property can be applied to privacy protection in the cloud, where personal data are stored and processed in encrypted form.In FHE schemes, ciphertexts are generated with a random noise to ensure semantic security. The noise grows as homomorphic operations proceed. When the noise magnitude exceeds a certain threshold, ciphertext will no longer be correctly decrypted. By means of bootstrapping proposed by Gentry [7], ciphertext noise can be reduced and further homomorphic operations can be performed. However, due to its inherent complexity, bootstrapping has become a major bottleneck for the efficiency of all FHE schemes. Although there are many studies on improving the efficiency of FHE schemes [8–27], they are still not simple and efficient enough to be widely adopted in the real world. Designing a conceptually simple and efficient FHE scheme has become a challenging issue.In this paper, a new FHE scheme is proposed to achieve both conceptual simplicity and higher efficiency. The scheme is constructed using the ideas of ciphertext matrix operations in the FHE scheme proposed by Gentry, Sahai and Waters (GSW) [19] and ciphertext vector additions in the FHE scheme proposed by Ducas and Micciancio (DM) [21]. Both these schemes are conceptually simpler than most other FHE schemes, while suffering from low efficiency. We have proved that, compared with DM, our scheme allows one more homomorphic operation to be performed before ciphertext refreshing. And the computational cost of our scheme is significantly lower than that of DM and GSW under the same security parameters, with the error rate kept at a sufficiently low level. Our scheme not only inherits the advantage of conceptual simplicity in DM and GSW but is also more efficient.Assumptions. The assumptions in our scheme are specified as follows: (1) the hardness of the Learning with Errors (LWE) problem [28]; (2) circular security in ciphertext refreshing; that is, one can safely encrypt a secret key under its associated public key [7]; (3) the operations on the binary circuit which are performed parallelly. And the computational cost at each level is represented as that of a specific gate at the level.Contributions. The main contributions of our scheme are summarized as follows: (1) To the best of our knowledge, our scheme is one of the few FHE schemes which take both simplicity and efficiency into consideration. (2) Our scheme inherits the advantage of conceptual simplicity in DM and GSW, which are conceptually simpler than most other FHE schemes. (3) Our scheme combines the advantage of efficient homomorphic operation in DM with the advantage of moderate growth of noise magnitude in GSW. When compared with DM, it allows one more homomorphic operation to be performed before ciphertext refreshing. Under the same security parameters, the computational cost of our scheme is obviously lower than that of DM and GSW, and the error rate is kept at a sufficiently low level.Organization. The rest of this paper is organized as follows: the related work is discussed in Section 2; some preliminaries are given in Section 3; a review of GSW and DM is presented in Section 4; our more efficient FHE scheme, along with its correctness, security, and applicability analysis, is presented in Section 5; the comparison of our scheme with DM and GSW in terms of overall efficiency and error rate is given in Section 6; finally, conclusions are drawn in Section 7.


## 2. Related Work

### 2.1. Construction of FHE Schemes

Gentry proposed the first FHE scheme in 2009 [7], which marks a milestone in the research of homomorphic encryption. Gentry’s FHE scheme is based on ideal lattices, which includes the following major steps: (1) the construction of a somewhat homomorphic encryption scheme (SWHE) which allows limited homomorphic additions and multiplications to be performed on ciphertexts; (2) the squashing step for reducing the complexity of decryption algorithm; (3) the bootstrapping technique for reducing ciphertext noise via re-encryption and homomorphic decryption. Despite its significant contribution, Gentry’s scheme sufferes from a rather low efficiency. Following Gentry’s work, some other FHE schemes based on ideal lattices have been proposed on improving the efficiency of Gentry’s scheme [8–11]. However, the inherent complicated key generation process, along with large key/ciphertext sizes, has made these schemes impractical for real-world applications.In 2010, Dijk et al. proposed a FHE scheme over the integers [29]. Both the keys and ciphertexts are integers, which are much simpler than previous FHE schemes based on ideal lattices. However, the scheme also suffers from low efficiency due to large key/ciphertext sizes. Although some improved FHE schemes on integers have been proposed [12–15], keys and ciphertexts in these schemes are still too large to be deployed in any practical system.Recently, most FHE schemes have been constructed based on the LWE problem, which is a computational problem over lattices [28]. LWE has now drawn the attention of more and more cryptographic researchers with its relatively small key/ciphertext sizes and strong security. Brakerski and Vaikuntanathan presented the first LWE-based FHE scheme (BV) in 2011 [30]. The relinearization technique was introduced for controlling ciphertext dimension in homomorphic multiplications. And the dimension-modulus reduction technique was proposed as a new method for simplifying the decryption algorithm to make the scheme bootstrappable, thus fully homomorphic. Compared with the squashing technique proposed by Gentry, the sparse subset-sum assumption was removed in dimension-modulus reduction, making it more natural. Brakerski, Gentry, and Vaikuntanathan proposed a leveled FHE scheme (BGV) in 2012 [16]. The relinearization and dimension-modulus reduction techniques were improved as the key-switching and modulus-switching techniques in BGV, for more efficient control of ciphertext dimension and noise magnitude. Brakerski then introduced a scale-invariant leveled FHE scheme (Bra12) without modulus switching. Compared with previous LWE-based FHE schemes, Bra12 is simpler, and ciphertext noise magnitude grows by a constant multiplicative factor as homomorphic operations proceed, instead of exponentially. However, in all of these schemes, the complex process of key switching (or relinearization) still introduces a huge computational cost, which is unattractive in practice.In 2013, a new leveled FHE scheme, known as GSW, was proposed by Gentry, Sahai and Waters [19]. GSW is based on approximate eigenvectors of matrices. The ciphertexts in GSW are square matrices, and homomorphic additions and multiplications are just matrix additions and multiplications, respectively. Therefore, ciphertext dimension always keeps constant and key switching is no longer necessary. Scale-invariance can also be achieved in GSW via the flatten technique; thus modulus switching is also no longer necessary. GSW is simpler and more natural than previous LWE-based FHE schemes. However, matrix multiplication still brings about a high computational cost. Ducas and Miccianico proposed a new FHE scheme with homomorphic NOT AND (NAND) gates [21], which is known as the DM scheme. Homomorphic operations in DM are just ciphertext vector additions, which are very simple operations. However, ciphertexts in DM need to be refreshed after each homomorphic operation, which becomes a bottleneck for the overall efficiency. Although GSW and DM are conceptually simpler than most other FHE schemes, both of them still suffer from efficiency bottlenecks.Other research works on the construction of LWE-based FHE schemes generally focus on improving the efficiency [22–25] and optimizing the bootstrapping algorithm [26, 27]. In some recent research works, multikey FHE schemes are proposed for secure multiparty computation [31, 32]. However, these schemes involve either key-switching, or ciphertext matrix operations, which are both computationally costing. Some of them are not conceptually simple. Therefore, it is necessary to construct a new FHE scheme with both conceptual simplicity and higher efficiency.


### 2.2. Applications of Homomorphic Encryption Schemes

As homomorphic encryption supports operations on encrypted data, it is definitely more powerful than traditional encryption techniques and has a vast area of applications. In recent years, with the wide adoption of cloud storage and cloud computation in real-world applications, there have been many applications of homomorphic encryption schemes on privacy protection in the cloud.Searchable encryption is a basic application of homomorphic encryption, where users can execute secure queries on encrypted data. The query results are obtained through homomorphic operations between the encrypted query and the encrypted data. A lot of researchers have proposed secure information retrieval schemes based on homomorphic encryption [33–36]. Meng Shen et al. proposed a graph encryption scheme which makes use of SWHE and enables approximate Constrained Shortest Distance (CSD) querying over encrypted graph [37]. Another common application of homomorphic encryption schemes is secure e-voting, where the ballots of voters are encrypted and homomorphic operations are performed on these data [38–41]. The property of homomorphic encryption makes it possible to tally all encrypted ballots without accessing the plaintext content of any individual ballot; thus voter’s privacy is protected. Recently, with the rapid development of artificial intelligence and machine learning, privacy protection in machine learning has also drawn the attention of many researchers. Many studies on encrypted machine learning have emerged, where homomorphic encryption schemes are adopted for computation on encrypted data. Xiaoqiang Sun et al. implemented three private classification algorithms based on homomorphic encryption [42], which were hyperplane decision-based classification, Naïve Bayes classification, and decision tree classification. M Kim et al. proposed secure logistic regression for biomedical data [43]. There are also lots of research works on secure deep learning based on homomorphic encryption [44–46]. The activation functions in deep learning algorithms are usually approximated as polynomials, which can be homomorphically evaluated by homomorphic encryption schemes. Other recent applications of homomorphic encryption include integrity verification [47, 48], data aggregation [49, 50], and secure multiparty computation [32, 51].Moreover, homomorphic encryption can be applied in the defense against phishing attack, where user’s personal information is encrypted, and the verification is completed via homomorphic operations. Even if personal information is leaked to the phishing server, nothing can be learned from the encrypted data. Longfei Wu et al. proposed a novel automated lightweight antiphishing scheme for mobile platforms, which is highly beneficial for mobile users [52]. Adopting homomorphic encryption in the scheme would provide an even stronger defense against phishing attacks. With the rise of self-awareness of privacy protection and the development of homomorphic encryption, there will be more and more applications of homomorphic encryption in the future.


## 2.1. Construction of FHE Schemes

Gentry proposed the first FHE scheme in 2009 [7], which marks a milestone in the research of homomorphic encryption. Gentry’s FHE scheme is based on ideal lattices, which includes the following major steps: (1) the construction of a somewhat homomorphic encryption scheme (SWHE) which allows limited homomorphic additions and multiplications to be performed on ciphertexts; (2) the squashing step for reducing the complexity of decryption algorithm; (3) the bootstrapping technique for reducing ciphertext noise via re-encryption and homomorphic decryption. Despite its significant contribution, Gentry’s scheme sufferes from a rather low efficiency. Following Gentry’s work, some other FHE schemes based on ideal lattices have been proposed on improving the efficiency of Gentry’s scheme [8–11]. However, the inherent complicated key generation process, along with large key/ciphertext sizes, has made these schemes impractical for real-world applications.In 2010, Dijk et al. proposed a FHE scheme over the integers [29]. Both the keys and ciphertexts are integers, which are much simpler than previous FHE schemes based on ideal lattices. However, the scheme also suffers from low efficiency due to large key/ciphertext sizes. Although some improved FHE schemes on integers have been proposed [12–15], keys and ciphertexts in these schemes are still too large to be deployed in any practical system.Recently, most FHE schemes have been constructed based on the LWE problem, which is a computational problem over lattices [28]. LWE has now drawn the attention of more and more cryptographic researchers with its relatively small key/ciphertext sizes and strong security. Brakerski and Vaikuntanathan presented the first LWE-based FHE scheme (BV) in 2011 [30]. The relinearization technique was introduced for controlling ciphertext dimension in homomorphic multiplications. And the dimension-modulus reduction technique was proposed as a new method for simplifying the decryption algorithm to make the scheme bootstrappable, thus fully homomorphic. Compared with the squashing technique proposed by Gentry, the sparse subset-sum assumption was removed in dimension-modulus reduction, making it more natural. Brakerski, Gentry, and Vaikuntanathan proposed a leveled FHE scheme (BGV) in 2012 [16]. The relinearization and dimension-modulus reduction techniques were improved as the key-switching and modulus-switching techniques in BGV, for more efficient control of ciphertext dimension and noise magnitude. Brakerski then introduced a scale-invariant leveled FHE scheme (Bra12) without modulus switching. Compared with previous LWE-based FHE schemes, Bra12 is simpler, and ciphertext noise magnitude grows by a constant multiplicative factor as homomorphic operations proceed, instead of exponentially. However, in all of these schemes, the complex process of key switching (or relinearization) still introduces a huge computational cost, which is unattractive in practice.In 2013, a new leveled FHE scheme, known as GSW, was proposed by Gentry, Sahai and Waters [19]. GSW is based on approximate eigenvectors of matrices. The ciphertexts in GSW are square matrices, and homomorphic additions and multiplications are just matrix additions and multiplications, respectively. Therefore, ciphertext dimension always keeps constant and key switching is no longer necessary. Scale-invariance can also be achieved in GSW via the flatten technique; thus modulus switching is also no longer necessary. GSW is simpler and more natural than previous LWE-based FHE schemes. However, matrix multiplication still brings about a high computational cost. Ducas and Miccianico proposed a new FHE scheme with homomorphic NOT AND (NAND) gates [21], which is known as the DM scheme. Homomorphic operations in DM are just ciphertext vector additions, which are very simple operations. However, ciphertexts in DM need to be refreshed after each homomorphic operation, which becomes a bottleneck for the overall efficiency. Although GSW and DM are conceptually simpler than most other FHE schemes, both of them still suffer from efficiency bottlenecks.Other research works on the construction of LWE-based FHE schemes generally focus on improving the efficiency [22–25] and optimizing the bootstrapping algorithm [26, 27]. In some recent research works, multikey FHE schemes are proposed for secure multiparty computation [31, 32]. However, these schemes involve either key-switching, or ciphertext matrix operations, which are both computationally costing. Some of them are not conceptually simple. Therefore, it is necessary to construct a new FHE scheme with both conceptual simplicity and higher efficiency.


## 2.2. Applications of Homomorphic Encryption Schemes

As homomorphic encryption supports operations on encrypted data, it is definitely more powerful than traditional encryption techniques and has a vast area of applications. In recent years, with the wide adoption of cloud storage and cloud computation in real-world applications, there have been many applications of homomorphic encryption schemes on privacy protection in the cloud.Searchable encryption is a basic application of homomorphic encryption, where users can execute secure queries on encrypted data. The query results are obtained through homomorphic operations between the encrypted query and the encrypted data. A lot of researchers have proposed secure information retrieval schemes based on homomorphic encryption [33–36]. Meng Shen et al. proposed a graph encryption scheme which makes use of SWHE and enables approximate Constrained Shortest Distance (CSD) querying over encrypted graph [37]. Another common application of homomorphic encryption schemes is secure e-voting, where the ballots of voters are encrypted and homomorphic operations are performed on these data [38–41]. The property of homomorphic encryption makes it possible to tally all encrypted ballots without accessing the plaintext content of any individual ballot; thus voter’s privacy is protected. Recently, with the rapid development of artificial intelligence and machine learning, privacy protection in machine learning has also drawn the attention of many researchers. Many studies on encrypted machine learning have emerged, where homomorphic encryption schemes are adopted for computation on encrypted data. Xiaoqiang Sun et al. implemented three private classification algorithms based on homomorphic encryption [42], which were hyperplane decision-based classification, Naïve Bayes classification, and decision tree classification. M Kim et al. proposed secure logistic regression for biomedical data [43]. There are also lots of research works on secure deep learning based on homomorphic encryption [44–46]. The activation functions in deep learning algorithms are usually approximated as polynomials, which can be homomorphically evaluated by homomorphic encryption schemes. Other recent applications of homomorphic encryption include integrity verification [47, 48], data aggregation [49, 50], and secure multiparty computation [32, 51].Moreover, homomorphic encryption can be applied in the defense against phishing attack, where user’s personal information is encrypted, and the verification is completed via homomorphic operations. Even if personal information is leaked to the phishing server, nothing can be learned from the encrypted data. Longfei Wu et al. proposed a novel automated lightweight antiphishing scheme for mobile platforms, which is highly beneficial for mobile users [52]. Adopting homomorphic encryption in the scheme would provide an even stronger defense against phishing attacks. With the rise of self-awareness of privacy protection and the development of homomorphic encryption, there will be more and more applications of homomorphic encryption in the future.


## 3. Preliminaries

### 3.1. Notations

The mathematical symbols in this paper are shown in Table1.Table 1
List of mathematical symbols with their meanings.
Symbol Meaning Regular letters (with possibly superscripts and subscripts), e.g.q,n′,B. Scalars. Bold lowercase letters (with possibly superscripts and subscripts), e.g.e,c′. Vectors. Bold uppercase letters (with possibly superscripts and subscripts), e.g.A,C′. Matrices. Z The set of all integers. C The set of all complex numbers. Z + The set of all positive integers. Z q The set of integers modulo an integerq, which are reduced to (-q/2,q/2]. Z q m × n The set ofm×n matrices with all coefficients in Zq. Z [ X ] The set of all polynomials with integer coefficients. B ( n , p ) Binomial distribution with parametersn,p. x Rounding ofx to the nearest integer. a , b or a⋅b Inner product of vectorsa,b. A  | |  b The horizontal concatenation of matrixA and vector b. a ∞ The infinite norm of vectora, a∞=maxi⁡|ai|. d ← D IfD is a distribution, d is sampled according to D; If D is a set, d is uniformly sampled from D. negl( λ ) A negligible amount:negl(λ)=o(λ-c) for any constant c>0 as λ→+∞.


### 3.2. The LWE Problem

LWE is a computational problem over lattices, which is proposed by Regev [28]. For security parameter λ, let n=n(λ) and q=q(λ) denote the dimension and modulus of the vector, respectively, and let χ=χ(λ) denote the random distribution on Z for the random errors. The vector s is generated by sampling s←Z. For vector a←Zqn and error e←χ, output the following LWE instance (a,b)=(a,(a·s+e)modq)∈Zqn+1. The LWE assumption is that the distribution χ′ formed by different LWE instances is computationally indistinguishable from the uniform distribution on Zqn+1.


### 3.3. The Cyclotomic Ring

LetN be a power of 2, the 2N-th cyclotomic polynomial is Φ2N(X)=XN+1, and the corresponding polynomial ring is R=Z[X]/XN+1. RQ=R/QR denotes the residue ring of R modulo an integer Q. Each element in R is a polynomial with integer coefficients whose degree is at most N-1, and each element in RQ is an element in R with all its coefficients modulo Q. For polynomial r=∑i=0N-1riXi∈R, let CF(r)=(r0,…,rN-1) denote the coefficient vector of the polynomial. And let ACR(r) denote the following matrix: the first column is CF(r), and the other columns are the anticyclic rotations of CF(r) with the cycled entries negated, as shown in (2)ACRr=r0-rN-1⋯-r1r1r0⋯-r2⋮⋮⋱⋮rN-1rN-2⋯r0


### 3.4. BitDecomp and Flatten Techniques

LetBD(·) denote the BitDecomp operation, and let a,b∈Zqk, l=log⁡q+1, N=kl. The BitDecomp operation is defined as follows:(3)BDa=a1,0,…,a1,l-1,…,ak,0,…,ak,l-1where ai,j is the j-th bit in ai’s binary representation from the lowest to the highest bit. After BitDecomp, the upper bound of a’s l1 norm goes down from nq to nlog⁡q. Let BD-1(·) denote the inverse operation of BD(·); for a vector a′=(a1,0,…,a1,l-1,…,ak,0,…,ak,l-1)∈ZqN, the operation BD-1(·) is defined as follows:(4)BD-1a′=∑j=0l-12ja1,j,…,∑j=0l-12jak,j∈ZqkLetFL(·) denote the flatten operation; for a vector a′∈Zqk, FL(·) is defined as follows:(5)FLa′=BDBD-1a′∈0,1NThere is another operationPowersofTwo(·) which comes hand in hand with BD(·). Let PT(·) denote the operation PowersofTwo(·), which is defined as follows:(6)PTb=b1,2b1,…,2l-1b1,…,bk,2bk,…,2l-1bk∈ZqNAn obvious property between BD(·) and PT(·) is shown as follows:(7)BDa,PTb=a,bFor a vector a′∈ZqN, the following property also holds:(8)a′,PTb=BD-1a′,b=FLa′,PTbIt can be observed from (8) that an important advantage of FL(·) lies in that it makes the coefficients of a vector small, without affecting its inner product with the vector PTb. When the above operations are applied to a matrix, they are performed for each row of the matrix.


## 3.1. Notations

The mathematical symbols in this paper are shown in Table1.Table 1
List of mathematical symbols with their meanings.
Symbol Meaning Regular letters (with possibly superscripts and subscripts), e.g.q,n′,B. Scalars. Bold lowercase letters (with possibly superscripts and subscripts), e.g.e,c′. Vectors. Bold uppercase letters (with possibly superscripts and subscripts), e.g.A,C′. Matrices. Z The set of all integers. C The set of all complex numbers. Z + The set of all positive integers. Z q The set of integers modulo an integerq, which are reduced to (-q/2,q/2]. Z q m × n The set ofm×n matrices with all coefficients in Zq. Z [ X ] The set of all polynomials with integer coefficients. B ( n , p ) Binomial distribution with parametersn,p. x Rounding ofx to the nearest integer. a , b or a⋅b Inner product of vectorsa,b. A  | |  b The horizontal concatenation of matrixA and vector b. a ∞ The infinite norm of vectora, a∞=maxi⁡|ai|. d ← D IfD is a distribution, d is sampled according to D; If D is a set, d is uniformly sampled from D. negl( λ ) A negligible amount:negl(λ)=o(λ-c) for any constant c>0 as λ→+∞.


## 3.2. The LWE Problem

LWE is a computational problem over lattices, which is proposed by Regev [28]. For security parameter λ, let n=n(λ) and q=q(λ) denote the dimension and modulus of the vector, respectively, and let χ=χ(λ) denote the random distribution on Z for the random errors. The vector s is generated by sampling s←Z. For vector a←Zqn and error e←χ, output the following LWE instance (a,b)=(a,(a·s+e)modq)∈Zqn+1. The LWE assumption is that the distribution χ′ formed by different LWE instances is computationally indistinguishable from the uniform distribution on Zqn+1.


## 3.3. The Cyclotomic Ring

LetN be a power of 2, the 2N-th cyclotomic polynomial is Φ2N(X)=XN+1, and the corresponding polynomial ring is R=Z[X]/XN+1. RQ=R/QR denotes the residue ring of R modulo an integer Q. Each element in R is a polynomial with integer coefficients whose degree is at most N-1, and each element in RQ is an element in R with all its coefficients modulo Q. For polynomial r=∑i=0N-1riXi∈R, let CF(r)=(r0,…,rN-1) denote the coefficient vector of the polynomial. And let ACR(r) denote the following matrix: the first column is CF(r), and the other columns are the anticyclic rotations of CF(r) with the cycled entries negated, as shown in (2)ACRr=r0-rN-1⋯-r1r1r0⋯-r2⋮⋮⋱⋮rN-1rN-2⋯r0


## 3.4. BitDecomp and Flatten Techniques

LetBD(·) denote the BitDecomp operation, and let a,b∈Zqk, l=log⁡q+1, N=kl. The BitDecomp operation is defined as follows:(3)BDa=a1,0,…,a1,l-1,…,ak,0,…,ak,l-1where ai,j is the j-th bit in ai’s binary representation from the lowest to the highest bit. After BitDecomp, the upper bound of a’s l1 norm goes down from nq to nlog⁡q. Let BD-1(·) denote the inverse operation of BD(·); for a vector a′=(a1,0,…,a1,l-1,…,ak,0,…,ak,l-1)∈ZqN, the operation BD-1(·) is defined as follows:(4)BD-1a′=∑j=0l-12ja1,j,…,∑j=0l-12jak,j∈ZqkLetFL(·) denote the flatten operation; for a vector a′∈Zqk, FL(·) is defined as follows:(5)FLa′=BDBD-1a′∈0,1NThere is another operationPowersofTwo(·) which comes hand in hand with BD(·). Let PT(·) denote the operation PowersofTwo(·), which is defined as follows:(6)PTb=b1,2b1,…,2l-1b1,…,bk,2bk,…,2l-1bk∈ZqNAn obvious property between BD(·) and PT(·) is shown as follows:(7)BDa,PTb=a,bFor a vector a′∈ZqN, the following property also holds:(8)a′,PTb=BD-1a′,b=FLa′,PTbIt can be observed from (8) that an important advantage of FL(·) lies in that it makes the coefficients of a vector small, without affecting its inner product with the vector PTb. When the above operations are applied to a matrix, they are performed for each row of the matrix.


## 4. A Review of GSW and DM Schemes

### 4.1. The GSW Scheme

GSW is constructed based on approximate eigenvectors of matrices. And homomorphic operations in GSW are just ciphertext matrix operations. GSW is more natural and concise than previous LWE-based FHE schemes which require key switching (or relinearization). The main algorithms in GSW are shown as follows:(i)
GSW.KeyGen(λ,L): λ,L denote the security parameter and multiplicative depth, respectively. Ciphertext dimension n=n(λ,L), modulus q=q(λ,L), and noise distribution χ=χ(λ,L) are set to guarantee a security level of λ. Let m=O(nlog⁡q), l=log⁡q+1, N=n+1l, and parameter set params=(n,q,χ,m). Sample t←Zqn, let s=(1,-t)∈Zqn+1, and output secret key sk=v=PT(s). Sample B←Zqm×n,e←χm, let b=B·t+e, A=b∥B, and output public key pk=A.(ii)
GSW.Encparams,pk,μ: for plaintext message μ∈Zq, sample R←{0,1}N×m; output ciphertext: (9)C=FLμ·IN+BDR·A∈ZqN×NwhereIN denotes the N-dimensional identity matrix.(iii)
GSW.HomNANDC1,C2: on input ciphertext pair C1,C2∈ZqN×N, output ciphertext(10)CNAND=FLIN-C1C2As a result of the homomorphic NAND operation,CNAND satisfies the following property:(11)CNAND·v=1-μ1μ2v-μ2e1-C1e2where μ1,μ2 are the plaintext messages in C1,C2, respectively, and e1,e2 are the corresponding ciphertext noises. Let B0 denote the upper bound of the noise magnitudes in C1,C2, that is, the upper bound for the l∞ norms of e1,e2. It is obvious that maxe1∞,e2∞<B0. Actually, C1,C2∈{0,1}N×N as a result of the flatten operation. As μ2∈{0,1}, the noise in CNAND is upper bounded by (N+1)B0, as shown by (11).The overall algorithm flow of GSW is shown in Figure1.Figure 1
Overall algorithm flow of the GSW scheme.


### 4.2. The DM Scheme

DM is a FHE scheme based on a LWE symmetric encryption scheme. Homomorphic operations in DM correspond to ciphertext vector additions. DM is conceptually simple for its simple homomorphic operation. The main algorithms in DM are shown as follows:(i)
DM.KeyGenλ: λ denotes the security parameter. Integer t≥2 is the plaintext modulus. Ciphertext dimension n=n(λ), modulus q=q(λ), and ciphertext noise distribution χ=χ(λ) are set to guarantee a security level of λ. Here x<q/2t for any x←χ. Let params denote the parameter set params=(n,q,t,χ). The key is uniformly sampled from Zqn: pk/sk←Zqn.(ii)
DM.Encm,pk,params: the plaintext and ciphertext spaces are Zt,Zq, respectively. Sample a←Zqn, e←χ, on input plaintext message m∈Zt, and output ciphertext:(12)LWEst/qm=a,a·s+mqt+e∈Zqn+1(iii)
DM.HomNAND(a1,b1),(a2,b2): on input ciphertexts ci=(ai,bi), i∈{1,2} and ci∈LWEs4/q(mi,q/16) encrypts the plaintext message mi, output c=(a,b)∈LWEs2/q(1-m1m2,q/4). In particular,(13)a,b=-a1-a2,58q-b1-b2The ciphertext(a,b) is a ciphertext of 1-m1m2 with noise magnitude less than q/4, which guarantees correct decryption. Homomorphic NAND operations in DM are completed by a few additions between ciphertext vectors, which are simpler and faster than tensor products or matrix operations in previous schemes. However, ciphertext magnitude would be at least q/4 after a further homomorphic operation, then the ciphertext would no longer be correctly decrypted. After each homomorphic operation, ciphertext needs to be refreshed to keep the noise magnitude small.An efficient ciphertext refreshing algorithm based on Ring-GSW is proposed in DM for reducing ciphertext noise. In the refreshing algorithm, ciphertext(a,b)∈LWEs2/q(m,q/4) and refreshing key Krf are taken as input, and base Br is used to encode the ciphertext (a,b). Krf consists of the following ciphertexts:(14)Ki,c,j=EcsiBrjmodq,c∈0,…,Br-1,j=0,…,dr-1,i=1,…,nwhere dr=logBrq and E(·) denotes the encryption algorithm in the ciphertext refreshing algorithm. The ciphertext refreshing algorithm is shown as in Algorithm 1, where Init(·) and Incr(·) denote the initialization and homomorphic addition of the accumulator ACC, respectively. ACC is initialized as an encryption of b+q/4. When the main loop in Algorithm 1 ends, the underlying plaintext v of the accumulator satisfies(15)v-q4=b+∑i,jai,jsiBrj=b+∑isi∑jBrjai,j=b-∑iaisi=q2m+ewhere e is the noise in the input ciphertext (a,b). As e<q/4, it is clear that 0<v<q/2 when m=0 and q/2<v<q when m=1. In other words, extracting the most significant bit (msb) in v would yield the plaintext m.Algorithm 1: D M .   R e f r e s h ( ( a , b ) ,  K r f ).
1Init(ACC,b+q/4) 2fori=1,…,ndo 3Expand-aias-ai=∑jai,jBrj(modq) 4forj=0,…,dr-1doIncr(ACC,Ki,ai,j,j) 5endfor 6OutputmsbExtract(ACC)During themsbExtract process in Algorithm 1, the accumulator ACC, along with a switching key Kks and a testing vector t=-∑i=0q/2-1CF(Yi), is taken as input. Here Y=X2N/q, and z∈R is the secret key used in the encryption algorithm of the ciphertext refreshing algorithm. The details of msbExtract are shown in Algorithm 2.Algorithm 2: m s b E x t r a c t ( A C C ,  K k s , t ).
1   a t , b t = 0 t , t t , 0 t , … , 0 t ⋅ A C R ( A C C ) 2   c = a , b 0 + u ∈ L W E C F ( z ) t / Q ( m s b ( v ) ) 3   c ′ = K e y S w i t c h ( c , K k s ) ∈ L W E s t / Q ( m s b ( v ) ) 4   c ′ ′ = M o d S w i t c h ( c ′ ) ∈ L W E s t / q ( m s b ( v ) )The ciphertextc in the 2nd step of Algorithm 2 is(16)c=a,b0+u=a·CFz+t·e+2u·msbvwhere a=tt·ACR(a), a,b′ is the 2nd row of ACC and u=Q/2t or Q/2t. As u≈Q/2t, c is an encryption of msb(v)=m. Thus, c∈LWECF(z)t/Q(msb(v)). After key and modulus switching, c is transformed to a ciphertext under key s modulo q. Under an appropriate parameter setting, the noise magnitude of the refreshed ciphertext would be lower than q/16, and further homomorphic operations can be performed.The overall algorithm flow of DM is shown in Figure2, where m=1-m1m2.Figure 2
Overall algorithm flow of the DM scheme.


## 4.1. The GSW Scheme

GSW is constructed based on approximate eigenvectors of matrices. And homomorphic operations in GSW are just ciphertext matrix operations. GSW is more natural and concise than previous LWE-based FHE schemes which require key switching (or relinearization). The main algorithms in GSW are shown as follows:(i)
GSW.KeyGen(λ,L): λ,L denote the security parameter and multiplicative depth, respectively. Ciphertext dimension n=n(λ,L), modulus q=q(λ,L), and noise distribution χ=χ(λ,L) are set to guarantee a security level of λ. Let m=O(nlog⁡q), l=log⁡q+1, N=n+1l, and parameter set params=(n,q,χ,m). Sample t←Zqn, let s=(1,-t)∈Zqn+1, and output secret key sk=v=PT(s). Sample B←Zqm×n,e←χm, let b=B·t+e, A=b∥B, and output public key pk=A.(ii)
GSW.Encparams,pk,μ: for plaintext message μ∈Zq, sample R←{0,1}N×m; output ciphertext: (9)C=FLμ·IN+BDR·A∈ZqN×NwhereIN denotes the N-dimensional identity matrix.(iii)
GSW.HomNANDC1,C2: on input ciphertext pair C1,C2∈ZqN×N, output ciphertext(10)CNAND=FLIN-C1C2As a result of the homomorphic NAND operation,CNAND satisfies the following property:(11)CNAND·v=1-μ1μ2v-μ2e1-C1e2where μ1,μ2 are the plaintext messages in C1,C2, respectively, and e1,e2 are the corresponding ciphertext noises. Let B0 denote the upper bound of the noise magnitudes in C1,C2, that is, the upper bound for the l∞ norms of e1,e2. It is obvious that maxe1∞,e2∞<B0. Actually, C1,C2∈{0,1}N×N as a result of the flatten operation. As μ2∈{0,1}, the noise in CNAND is upper bounded by (N+1)B0, as shown by (11).The overall algorithm flow of GSW is shown in Figure1.Figure 1
Overall algorithm flow of the GSW scheme.


## 4.2. The DM Scheme

DM is a FHE scheme based on a LWE symmetric encryption scheme. Homomorphic operations in DM correspond to ciphertext vector additions. DM is conceptually simple for its simple homomorphic operation. The main algorithms in DM are shown as follows:(i)
DM.KeyGenλ: λ denotes the security parameter. Integer t≥2 is the plaintext modulus. Ciphertext dimension n=n(λ), modulus q=q(λ), and ciphertext noise distribution χ=χ(λ) are set to guarantee a security level of λ. Here x<q/2t for any x←χ. Let params denote the parameter set params=(n,q,t,χ). The key is uniformly sampled from Zqn: pk/sk←Zqn.(ii)
DM.Encm,pk,params: the plaintext and ciphertext spaces are Zt,Zq, respectively. Sample a←Zqn, e←χ, on input plaintext message m∈Zt, and output ciphertext:(12)LWEst/qm=a,a·s+mqt+e∈Zqn+1(iii)
DM.HomNAND(a1,b1),(a2,b2): on input ciphertexts ci=(ai,bi), i∈{1,2} and ci∈LWEs4/q(mi,q/16) encrypts the plaintext message mi, output c=(a,b)∈LWEs2/q(1-m1m2,q/4). In particular,(13)a,b=-a1-a2,58q-b1-b2The ciphertext(a,b) is a ciphertext of 1-m1m2 with noise magnitude less than q/4, which guarantees correct decryption. Homomorphic NAND operations in DM are completed by a few additions between ciphertext vectors, which are simpler and faster than tensor products or matrix operations in previous schemes. However, ciphertext magnitude would be at least q/4 after a further homomorphic operation, then the ciphertext would no longer be correctly decrypted. After each homomorphic operation, ciphertext needs to be refreshed to keep the noise magnitude small.An efficient ciphertext refreshing algorithm based on Ring-GSW is proposed in DM for reducing ciphertext noise. In the refreshing algorithm, ciphertext(a,b)∈LWEs2/q(m,q/4) and refreshing key Krf are taken as input, and base Br is used to encode the ciphertext (a,b). Krf consists of the following ciphertexts:(14)Ki,c,j=EcsiBrjmodq,c∈0,…,Br-1,j=0,…,dr-1,i=1,…,nwhere dr=logBrq and E(·) denotes the encryption algorithm in the ciphertext refreshing algorithm. The ciphertext refreshing algorithm is shown as in Algorithm 1, where Init(·) and Incr(·) denote the initialization and homomorphic addition of the accumulator ACC, respectively. ACC is initialized as an encryption of b+q/4. When the main loop in Algorithm 1 ends, the underlying plaintext v of the accumulator satisfies(15)v-q4=b+∑i,jai,jsiBrj=b+∑isi∑jBrjai,j=b-∑iaisi=q2m+ewhere e is the noise in the input ciphertext (a,b). As e<q/4, it is clear that 0<v<q/2 when m=0 and q/2<v<q when m=1. In other words, extracting the most significant bit (msb) in v would yield the plaintext m.Algorithm 1: D M .   R e f r e s h ( ( a , b ) ,  K r f ).
1Init(ACC,b+q/4) 2fori=1,…,ndo 3Expand-aias-ai=∑jai,jBrj(modq) 4forj=0,…,dr-1doIncr(ACC,Ki,ai,j,j) 5endfor 6OutputmsbExtract(ACC)During themsbExtract process in Algorithm 1, the accumulator ACC, along with a switching key Kks and a testing vector t=-∑i=0q/2-1CF(Yi), is taken as input. Here Y=X2N/q, and z∈R is the secret key used in the encryption algorithm of the ciphertext refreshing algorithm. The details of msbExtract are shown in Algorithm 2.Algorithm 2: m s b E x t r a c t ( A C C ,  K k s , t ).
1   a t , b t = 0 t , t t , 0 t , … , 0 t ⋅ A C R ( A C C ) 2   c = a , b 0 + u ∈ L W E C F ( z ) t / Q ( m s b ( v ) ) 3   c ′ = K e y S w i t c h ( c , K k s ) ∈ L W E s t / Q ( m s b ( v ) ) 4   c ′ ′ = M o d S w i t c h ( c ′ ) ∈ L W E s t / q ( m s b ( v ) )The ciphertextc in the 2nd step of Algorithm 2 is(16)c=a,b0+u=a·CFz+t·e+2u·msbvwhere a=tt·ACR(a), a,b′ is the 2nd row of ACC and u=Q/2t or Q/2t. As u≈Q/2t, c is an encryption of msb(v)=m. Thus, c∈LWECF(z)t/Q(msb(v)). After key and modulus switching, c is transformed to a ciphertext under key s modulo q. Under an appropriate parameter setting, the noise magnitude of the refreshed ciphertext would be lower than q/16, and further homomorphic operations can be performed.The overall algorithm flow of DM is shown in Figure2, where m=1-m1m2.Figure 2
Overall algorithm flow of the DM scheme.


## 5. Efficient FHE Scheme Based on GSW and DM Schemes

Aimed at the problem of overly frequent ciphertext refreshings in DM, a new FHE scheme (NHE) is proposed to achieve a higher efficiency. The ciphertext matrix operations in GSW and ciphertext vector additions in DM are both applied in our scheme. And the advantage of conceptual simplicity of both GSW and DM is inherited in our scheme. Moreover, our scheme combines the advantage of efficient homomorphic operation in DM with the advantage of moderate growth of noise magnitude in GSW. The whole scheme is briefly shown here, and some related details will be illustrated later.(i)
NHE.KeyGenλ: here λ denotes the security parameter. Modulus q=q(λ)=2k(k∈Z+), dimension n=n(λ), and ciphertext noise distribution χ=χ(λ) are set to guarantee a security level of λ. Concretely, χ is a discrete Gaussian distribution over integers with zero mean and standard deviation σ. Let params denote the parameter set (n,q,χ), and let l=log⁡q+1,N=(n+1)l. Sample t←Zqn,s=(1,-t)∈Zqn+1; output secret key sk=v=PT(s)∈ZqN. Sample B←ZqN×n,e←χN, let b=Bt+e, A=b∥B, and output public key pk=A.(ii)
NHE.Encm,pk: on input plaintext message m∈{0,1}, output ciphertext(17)C=FLmIN+BDA∈ZqN×N(iii)
NHE.HomNANDC1,C2: the input ciphertexts C1,C2∈ZqN×N correspond to encryptions of m1,m2∈{0,1}, respectively. Each ciphertext is assumed to have an internal attribute level indicating the number of homomorphic operations it has gone through. The level of any ciphertext is 0 in the beginning and increases by 1 after each homomorphic operation. For C1,C2 such that C1.level=C2.level=0, homomorphic NAND operation is performed as follows:(18)C′=FLIN-C1C2Then the(l-2)-th row is extracted from C′ as the ciphertext c′∈ZqN for the next homomorphic NAND operation. Clearly, c′.level=1. For a pair of ciphertexts c1′,c2′∈ZqN such that c1′.level=c2′.level=1, homomorphic NAND operation is performed as follows:(19)cNAND=FL-c1′-c2′+c0∈0,1Nwherec0 is an auxiliary vector such that c0=BD((5q/8,0))∈{0,1}N. The homomorphic operations in (18) and (19) are based on the ideas of ciphertext matrix operations in GSW and ciphertext vector additions in DM, respectively.(iv)
NHE.KeySwitchcNAND,Kks: the switching key Kks consists of the following ciphertexts: ki,c∈LWEs′q/q(cvi),i=1,…,N,c∈{0,1}, where s′←{0,1}n′ is the new secret key. On input ciphertext cNAND and the switching key Kks, output ciphertext(20)cNAND′=∑iki,ci∈Zqn′+1The above ciphertextcNAND′ is a ciphertext under the new secret key s′ instead of v.(v)
NHE.ModSwitchcNAND′: on input ciphertext cNAND′, output ciphertext(21)cNAND′′=q′qcNAND′∈Zq′n′+1whereq′=2k′(k′∈Z+) and q′<q. cNAND′′ is the final ciphertext after 2 homomorphic NAND operations. The modulus in cNAND′′ is transformed from q to q′. Moreover, dimension and modulus of cNAND′′ are set to be the same as those of the ciphertexts in DM.N H E . K e y S w i t c h corresponds to the sum of some (n′+1)-dimensional vectors, and NHE.ModSwitch corresponds to rounding for each coefficient in a single vector. Both algorithms involve just simple operations, which have no significant effect on the simplicity of our scheme. The overall algorithm flow of our scheme is shown in Figure 3. Here the algorithms NHE.HomNANDGSW and NHE.HomNANDDM denote the algorithms in (18) and (19), respectively.Figure 3
Overall algorithm flow of our scheme.


### 5.1. Correctness Analysis

Assuming there are 4 fresh ciphertextsC11,C12,C21,C22∈ZqN×N, as shown in Figure 3. Each coefficient of the noise vectors in the above ciphertexts follows a discrete Gaussian distribution with zero mean and standard deviation σ. According to the property of discrete Gaussian distribution, the probability of each coefficient being in the interval -6σ,6σ is p0, which is very close to 1. The probability of the all the noises in C11,C12,C21,C22 being upper bounded by B0=6σ is thus p1=p04N.It can be learned from (18) that the ciphertext C′ satisfies(22)C′v=1-m1m2v-m2e1+C1e2where e1,e2 are the noise vectors in C1,C2, respectively. As the first l coefficients in v are (v1,v2,…,vl)=(1,2,…,2l-1) and l=log⁡q+1, it is clear that vl-2=q/4. Let Cl-2′ denote the (l-2)-th row in C′; we have(23)Cl-2′v=1-m1m2q4+ewhere e=C1,l-2·e2-m2e1,l-2. And e1,l-2,C1,l-2 are the (l-2)-th coefficient in e1 and the (l-2)-th row in C1, respectively. e should satisfy the constraint e<q/16 to guarantee correct decryption after the next homomorphic operation.Assume the ciphertextsc1′,c2′ in (19) encrypt m1′,m2′∈{0,1}, respectively, and the ciphertext noises in c1′,c2′ are e1′,e2′, respectively. Clearly, ci′·v=mi′(q/4)+ei′,i∈{1,2}. It is clear that(24)-c1′-c2′·v=-m1′+m2′q4-e1′+e2′(25)c0·v=5q/8,0,1,-t=5q/8Let the plaintext spaces of ci′(i=1,2) and cNAND be Z4 and Z2, respectively, as in DM. The noise in the ciphertext cNAND is(26)eNAND=cNAND·v-1-m1′m2′q2=-m1′+m2′q4-e1′+e2′+58q-1-m1′m2′q2=q412-m1′-m2′2-e1′+e2′For each ciphertextki,c in the switching key Kks, we have ki,c=(aks,aks·s′+cvi+eks) where aks←Zqn′,eks←χ. Thus, the ciphertext cNAND′ can be further expressed as(27)cNAND′=∑i=1Naks,i,∑i=1Naks,i·s′+cNAND·v+∑i=1Neks,i∈Zqn′+1where aks,i←Zqn′,eks,i←χ,i=1,…,N. The noise in cNAND′ is(28)eNAND′=cNAND·v-1-m1′m2′q2+∑i=1Neks,i=eNAND+∑i=1Neks,iLetcre denote the error vector brought about by the rounding operation in (21); we have(29)cre=q′qcNAND′-q′qcNAND′∈-12,12n′+1The noise introduced by modulus switching is(30)ere=cre,-n+1·s′+cre,n+1where cre,-(n+1) is the subvector extracted from all the coefficients in cre except the (n+1)-th coefficient, and cre,n+1 is the (n+1)-th coefficient in cre. Then the noise of cNAND′′ can be expressed as(31)eNAND′′=q′qeNAND+∑i=1Neks,i+ereAccording to (11), the upper bounds for e1′,e2′ are both N+1B0, where B0 is the upper bound of the fresh ciphertexts generated in (17). Under an appropriate parameter setting, we further have(32)max⁡e1′,e2′≤N+1B0<q32Then it can be learned from (26), (31), and (32) that the noise magnitude in cNAND′′ satisfies(33)eNAND′′<3q′16+q′q∑i=1Neks,i+ereAll the random noiseseks,i(i=1,…,N) are drawn from an identical discrete Gaussian distribution. The discrete Gaussian distribution can be considered as the corresponding continuous Gaussian distribution with all the instances rounded down to the nearest integer. Assuming N random real numbers are generated from a continuous Gaussian distribution with zero mean and standard deviation σ, their sum also follows a Gaussian distribution with zero mean and standard deviation Nσ. The probability of the above sum lying in the interval -6Nσ,6Nσ satisfies p2>1-10-8. As the downward rounding has an error magnitude of at most N, we have(34)∑i=1Neks,i≤6Nσ+NUnder an appropriate parameter setting, we have(35)q′q∑i=1Neks,i<ϵ1where ϵ1 is a very small positive number.For vectorsaks,i(i=1,…,N) which are independently and uniformly sampled from Zqn′, it is clear that ∑i=1Naks,i also follows a uniform distribution over Zqn′. And each coefficient in cre,-(n+1) follows the uniform distribution over the following set:(36)Sre=-12+δ,-12+2δ,…,12-δ,12where δ=q′/q=2k′-k. The uniform distribution over Sre can be considered as the continuous uniform distribution over -1/2,1/2 with all the instances rounded up to the nearest element in Sre. Let usum denote the sum of nr(0≤nr≤n′) independent random real numbers from the uniform distribution over 0,1. The probability density function of usum is given by(37)fnrx=1nr-1!∑j=0k-1jCnrjx-jnr-1,x∈k,k+1where k∈{0,1,…,nr-1} and Cnrj is the number of combinations when choosing j items from nr items. Thus, the corresponding cumulative distribution function is(38)Fnrx=1nr!∑j=0k-1jCnrjx-jnr,x∈k,k+1Letp3,nr denote the probability of usum lying in the interval nr/2-B1,nr/2+B1; we have(39)p3,nr=Fnrnr2+B1-Fnrnr2-B1where B1 is a positive integer. For nr independent random real numbers from the uniform distribution over -1/2,1/2, p3,nr is the probability of their sum lying in the interval -B1,B1. Let p3=minp3,nrnr=0,1,…,n′ be the lowest probability among p3,nr(nr=0,1,…n′). p3 would be close to 1 as long as B1 is sufficiently large. And the absolute value of the above sum can be considered as upper bounded by B1. When the above nr independent random real numbers are rounded up to the nearest element in Sre, an extra error is introduced. The absolute value of the error is upper bounded by nrδ. As long as δ is sufficiently small, the following is satisfied:(40)nrδ≤n′δ<ϵ2where ϵ2 is another very small positive number. Thus we have(41)ere<B1+ϵ2+12According to the requirement for correct decryption, B1 should satisfy(42)B1≤q′16-ϵ1+ϵ2+12When q′ is sufficiently large, p3 is still guaranteed to be close to 1 even if B1 is under the above constraint. According to (33), the upper bound of noise magnitude in the ciphertext cNAND′′ is(43)B2=3q′16+B1+ϵ1+ϵ2+12≤q′4Then we have eNAND′′<B2≤q′/4, and correct decryption is guaranteed. The ciphertext cNAND′′ can be refreshed using the ciphertext refreshing algorithm in DM, and further homomorphic operations can be performed.Therefore, the correctness of our scheme lies in that the three incidents corresponding to the probabilitiesp1,p2,p3 are all true. The error rate of our scheme is pNHE,err=1-p1p2p3.


### 5.2. Security Analysis

We first give a formal definition for the threat/security model of indistinguishability under chosen plaintext attack (IND-CPA) and then conduct a security analysis for our scheme in line with the model. The IND-CPA threat/security model is defined as the following challenge-guess game between the challenger and the adversary:(i)
Initialization. The challenger C runs the Keygen algorithm to obtain the public and private keys, (pk,sk)←NHE.KeyGenλ, and sends the public key pk to the adversary A.(ii)
Challenge. The adversary A selects a pair of plaintexts m0,m1 and sends them to the challenger. The challenger C randomly selects a plaintext mb such that b←{0,1}, encrypts the plaintext: c←NHE.Encpk,mb, and then sends the ciphertext c to the adversary A.(iii)
Guess.The adversary A guesses the plaintext on receiving ciphertext c and outputs plaintext mb′(b′∈{0,1}). If b′=b, then the adversary A wins the game.LetA(c) denote the index (0/1) of the adversary’s output plaintext on receiving ciphertext c. The adversary’s advantage adv(A) is defined as the difference between the probabilities that the adversary guesses mb and m1-b, as shown in (44)(44)advA=PrAc=b-PrAc=1-bThe scheme is IND-CPA secure if for any polynomial time adversary A, the adversary’s advantage adv(A) is negligible: adv(A)=negl(λ).Generally, the ciphertexts in homomorphic encryption schemes are stored outside the local storage. Thus, the storage providers, such as cloud service providers and remote servers, might be the direct potential adversaries. Moreover, there are eavesdroppers who are trying to steal the stored data. And there may be coconspirators with an untrusted storage provider who get the stored data from the untrusted storage provider. They might also be the potential adversaries. In our scheme, both the public key and ciphertexts can be revealed to them.Thus, it is common for the adversaries to conduct chosen plaintext attacks (CPA). The IND-CPA security of our scheme is analyzed as follows.It can be learned from (17) that, for the initial ciphertext C, we have BD-1(C)=mG+A where G=BD-1(IN). As BD-1(C) can be transformed to C via BitDecomp, C is secure if BD-1(C) effectively hides the plaintext m[19]. The matrix A=b∥B∈ZqN×(n+1) consists of N independent LWE instances (Bi·t+ei,Bi),i=1,…N where Bi←Zqn,t←Zqn,ei←χ.Suppose a polynomial time adversaryA participates in the challenge-guess game as described above. If A achieves nonnegligible advantage in the game, then the LWE problem can be solved with equivalent advantage. According to the LWE assumption, no polynomial algorithm can solve the LWE problem with nonnegligible advantage. Thus, the adversary’s advantage adv(A) should be negligible. Our scheme is IND-CPA secure with respect to the initial ciphertexts. For a final ciphertext cNAND′′, it can be regarded as a ciphertext from a LWE symmetric encryption scheme with secret key s′. In this case, the challenger in the challenge-guess game retains the secret key and performs encryption using the secret key. Following the above analysis, it is easy to show that our scheme is also IND-CPA secure with respect to the final ciphertexts. Therefore, our scheme achieves IND-CPA security under the LWE assumption.


### 5.3. Applicability Analysis

In general, our scheme supports arbitrary operations on encrypted data; it is universally applicable for privacy-preserving computations in the real world, such as financial and medical data analysis. The underlying plaintexts in each homomorphic NAND operation in our scheme are a pair of bits, which are at the lowest level of data granularity. Thus, our scheme is highly flexible and extensible and can be adjusted to various kinds of computations on encrypted data. As our scheme is conceptually simple, it can be easily implemented, deployed, and maintained in real-world applications. Furthermore, the efficiency of our scheme is relatively high, and the efficient ciphertext refreshing algorithm in DM can be utilized in our scheme for efficient computation on encrypted data in real-world applications.


## 5.1. Correctness Analysis

Assuming there are 4 fresh ciphertextsC11,C12,C21,C22∈ZqN×N, as shown in Figure 3. Each coefficient of the noise vectors in the above ciphertexts follows a discrete Gaussian distribution with zero mean and standard deviation σ. According to the property of discrete Gaussian distribution, the probability of each coefficient being in the interval -6σ,6σ is p0, which is very close to 1. The probability of the all the noises in C11,C12,C21,C22 being upper bounded by B0=6σ is thus p1=p04N.It can be learned from (18) that the ciphertext C′ satisfies(22)C′v=1-m1m2v-m2e1+C1e2where e1,e2 are the noise vectors in C1,C2, respectively. As the first l coefficients in v are (v1,v2,…,vl)=(1,2,…,2l-1) and l=log⁡q+1, it is clear that vl-2=q/4. Let Cl-2′ denote the (l-2)-th row in C′; we have(23)Cl-2′v=1-m1m2q4+ewhere e=C1,l-2·e2-m2e1,l-2. And e1,l-2,C1,l-2 are the (l-2)-th coefficient in e1 and the (l-2)-th row in C1, respectively. e should satisfy the constraint e<q/16 to guarantee correct decryption after the next homomorphic operation.Assume the ciphertextsc1′,c2′ in (19) encrypt m1′,m2′∈{0,1}, respectively, and the ciphertext noises in c1′,c2′ are e1′,e2′, respectively. Clearly, ci′·v=mi′(q/4)+ei′,i∈{1,2}. It is clear that(24)-c1′-c2′·v=-m1′+m2′q4-e1′+e2′(25)c0·v=5q/8,0,1,-t=5q/8Let the plaintext spaces of ci′(i=1,2) and cNAND be Z4 and Z2, respectively, as in DM. The noise in the ciphertext cNAND is(26)eNAND=cNAND·v-1-m1′m2′q2=-m1′+m2′q4-e1′+e2′+58q-1-m1′m2′q2=q412-m1′-m2′2-e1′+e2′For each ciphertextki,c in the switching key Kks, we have ki,c=(aks,aks·s′+cvi+eks) where aks←Zqn′,eks←χ. Thus, the ciphertext cNAND′ can be further expressed as(27)cNAND′=∑i=1Naks,i,∑i=1Naks,i·s′+cNAND·v+∑i=1Neks,i∈Zqn′+1where aks,i←Zqn′,eks,i←χ,i=1,…,N. The noise in cNAND′ is(28)eNAND′=cNAND·v-1-m1′m2′q2+∑i=1Neks,i=eNAND+∑i=1Neks,iLetcre denote the error vector brought about by the rounding operation in (21); we have(29)cre=q′qcNAND′-q′qcNAND′∈-12,12n′+1The noise introduced by modulus switching is(30)ere=cre,-n+1·s′+cre,n+1where cre,-(n+1) is the subvector extracted from all the coefficients in cre except the (n+1)-th coefficient, and cre,n+1 is the (n+1)-th coefficient in cre. Then the noise of cNAND′′ can be expressed as(31)eNAND′′=q′qeNAND+∑i=1Neks,i+ereAccording to (11), the upper bounds for e1′,e2′ are both N+1B0, where B0 is the upper bound of the fresh ciphertexts generated in (17). Under an appropriate parameter setting, we further have(32)max⁡e1′,e2′≤N+1B0<q32Then it can be learned from (26), (31), and (32) that the noise magnitude in cNAND′′ satisfies(33)eNAND′′<3q′16+q′q∑i=1Neks,i+ereAll the random noiseseks,i(i=1,…,N) are drawn from an identical discrete Gaussian distribution. The discrete Gaussian distribution can be considered as the corresponding continuous Gaussian distribution with all the instances rounded down to the nearest integer. Assuming N random real numbers are generated from a continuous Gaussian distribution with zero mean and standard deviation σ, their sum also follows a Gaussian distribution with zero mean and standard deviation Nσ. The probability of the above sum lying in the interval -6Nσ,6Nσ satisfies p2>1-10-8. As the downward rounding has an error magnitude of at most N, we have(34)∑i=1Neks,i≤6Nσ+NUnder an appropriate parameter setting, we have(35)q′q∑i=1Neks,i<ϵ1where ϵ1 is a very small positive number.For vectorsaks,i(i=1,…,N) which are independently and uniformly sampled from Zqn′, it is clear that ∑i=1Naks,i also follows a uniform distribution over Zqn′. And each coefficient in cre,-(n+1) follows the uniform distribution over the following set:(36)Sre=-12+δ,-12+2δ,…,12-δ,12where δ=q′/q=2k′-k. The uniform distribution over Sre can be considered as the continuous uniform distribution over -1/2,1/2 with all the instances rounded up to the nearest element in Sre. Let usum denote the sum of nr(0≤nr≤n′) independent random real numbers from the uniform distribution over 0,1. The probability density function of usum is given by(37)fnrx=1nr-1!∑j=0k-1jCnrjx-jnr-1,x∈k,k+1where k∈{0,1,…,nr-1} and Cnrj is the number of combinations when choosing j items from nr items. Thus, the corresponding cumulative distribution function is(38)Fnrx=1nr!∑j=0k-1jCnrjx-jnr,x∈k,k+1Letp3,nr denote the probability of usum lying in the interval nr/2-B1,nr/2+B1; we have(39)p3,nr=Fnrnr2+B1-Fnrnr2-B1where B1 is a positive integer. For nr independent random real numbers from the uniform distribution over -1/2,1/2, p3,nr is the probability of their sum lying in the interval -B1,B1. Let p3=minp3,nrnr=0,1,…,n′ be the lowest probability among p3,nr(nr=0,1,…n′). p3 would be close to 1 as long as B1 is sufficiently large. And the absolute value of the above sum can be considered as upper bounded by B1. When the above nr independent random real numbers are rounded up to the nearest element in Sre, an extra error is introduced. The absolute value of the error is upper bounded by nrδ. As long as δ is sufficiently small, the following is satisfied:(40)nrδ≤n′δ<ϵ2where ϵ2 is another very small positive number. Thus we have(41)ere<B1+ϵ2+12According to the requirement for correct decryption, B1 should satisfy(42)B1≤q′16-ϵ1+ϵ2+12When q′ is sufficiently large, p3 is still guaranteed to be close to 1 even if B1 is under the above constraint. According to (33), the upper bound of noise magnitude in the ciphertext cNAND′′ is(43)B2=3q′16+B1+ϵ1+ϵ2+12≤q′4Then we have eNAND′′<B2≤q′/4, and correct decryption is guaranteed. The ciphertext cNAND′′ can be refreshed using the ciphertext refreshing algorithm in DM, and further homomorphic operations can be performed.Therefore, the correctness of our scheme lies in that the three incidents corresponding to the probabilitiesp1,p2,p3 are all true. The error rate of our scheme is pNHE,err=1-p1p2p3.


## 5.2. Security Analysis

We first give a formal definition for the threat/security model of indistinguishability under chosen plaintext attack (IND-CPA) and then conduct a security analysis for our scheme in line with the model. The IND-CPA threat/security model is defined as the following challenge-guess game between the challenger and the adversary:(i)
Initialization. The challenger C runs the Keygen algorithm to obtain the public and private keys, (pk,sk)←NHE.KeyGenλ, and sends the public key pk to the adversary A.(ii)
Challenge. The adversary A selects a pair of plaintexts m0,m1 and sends them to the challenger. The challenger C randomly selects a plaintext mb such that b←{0,1}, encrypts the plaintext: c←NHE.Encpk,mb, and then sends the ciphertext c to the adversary A.(iii)
Guess.The adversary A guesses the plaintext on receiving ciphertext c and outputs plaintext mb′(b′∈{0,1}). If b′=b, then the adversary A wins the game.LetA(c) denote the index (0/1) of the adversary’s output plaintext on receiving ciphertext c. The adversary’s advantage adv(A) is defined as the difference between the probabilities that the adversary guesses mb and m1-b, as shown in (44)(44)advA=PrAc=b-PrAc=1-bThe scheme is IND-CPA secure if for any polynomial time adversary A, the adversary’s advantage adv(A) is negligible: adv(A)=negl(λ).Generally, the ciphertexts in homomorphic encryption schemes are stored outside the local storage. Thus, the storage providers, such as cloud service providers and remote servers, might be the direct potential adversaries. Moreover, there are eavesdroppers who are trying to steal the stored data. And there may be coconspirators with an untrusted storage provider who get the stored data from the untrusted storage provider. They might also be the potential adversaries. In our scheme, both the public key and ciphertexts can be revealed to them.Thus, it is common for the adversaries to conduct chosen plaintext attacks (CPA). The IND-CPA security of our scheme is analyzed as follows.It can be learned from (17) that, for the initial ciphertext C, we have BD-1(C)=mG+A where G=BD-1(IN). As BD-1(C) can be transformed to C via BitDecomp, C is secure if BD-1(C) effectively hides the plaintext m[19]. The matrix A=b∥B∈ZqN×(n+1) consists of N independent LWE instances (Bi·t+ei,Bi),i=1,…N where Bi←Zqn,t←Zqn,ei←χ.Suppose a polynomial time adversaryA participates in the challenge-guess game as described above. If A achieves nonnegligible advantage in the game, then the LWE problem can be solved with equivalent advantage. According to the LWE assumption, no polynomial algorithm can solve the LWE problem with nonnegligible advantage. Thus, the adversary’s advantage adv(A) should be negligible. Our scheme is IND-CPA secure with respect to the initial ciphertexts. For a final ciphertext cNAND′′, it can be regarded as a ciphertext from a LWE symmetric encryption scheme with secret key s′. In this case, the challenger in the challenge-guess game retains the secret key and performs encryption using the secret key. Following the above analysis, it is easy to show that our scheme is also IND-CPA secure with respect to the final ciphertexts. Therefore, our scheme achieves IND-CPA security under the LWE assumption.


## 5.3. Applicability Analysis

In general, our scheme supports arbitrary operations on encrypted data; it is universally applicable for privacy-preserving computations in the real world, such as financial and medical data analysis. The underlying plaintexts in each homomorphic NAND operation in our scheme are a pair of bits, which are at the lowest level of data granularity. Thus, our scheme is highly flexible and extensible and can be adjusted to various kinds of computations on encrypted data. As our scheme is conceptually simple, it can be easily implemented, deployed, and maintained in real-world applications. Furthermore, the efficiency of our scheme is relatively high, and the efficient ciphertext refreshing algorithm in DM can be utilized in our scheme for efficient computation on encrypted data in real-world applications.


## 6. Performance Comparison

In this section, the homomorphic operations in DM, GSW, and our scheme are performed twice on a depth-2 binary circuit with NAND gates. We first present an analysis for the computational costs and error rates of the three schemes. Then based on the above analysis, we present a comparison for the three schemes in terms of computational costs and error rates. To avoid name clashes, the parameters in each scheme are all local to the scheme and apply only to the scheme.


### 6.1. Computational Cost of DM

For a pair of fresh ciphertextsc0,c1∈Zqn+1, the number of additions needed in the homomorphic operation in (13) is(45)nDM,1=n+2It can be learned fromDM.Refresh that Incr(ACC,C) is performed ndr times. The operation in Incr(ACC,C) can be simplified as the multiplication between the 2nd row in ACC and the ciphertext C.The above multiplication needs 2 inner products between a pair of2dg-dimensional vectors in RQ2dg. The fast Fourier transform (FFT) of the coefficient vector of each polynomial in RQ with maximum degree N can be represented as a vector in CN2 where N2=N/2+1. Inner product between a pair of vectors in RQ2dg needs 2N2dg additions and 2N2dg multiplications on complex numbers. Each multiplication on complex numbers needs 4 multiplications and 2 additions on real numbers, and each addition on complex numbers needs 2 additions on real numbers. As multiplication generally takes a longer time than addition, each multiplication on complex numbers needs at least 6 additions. Therefore, the number of additions needed in Incr(ACC,C) is at least(46)nDM,2=2·6+2·2N2dg=32N2dgThe key switching in the3rd step of Algorithm 2 needs Ndks additions on (n+1)-dimensional vectors. Here dks=logBksq and Bks is the base for encoding ciphertexts, as illustrated in DM [21]. Thus the total additions needed in key switching is(47)nDM,3=Ndksn+1The number of additions needed in the next homomorphic operation is the same as (45). As some other steps are omitted here, a lower bound is obtained for the number of needed operations. According to (45)~(47), the number of additions needed in DM is at least(48)nDM=2nDM,1+ndr·nDM,2+nDM,3=32N2ndgdr+n+1Ndks+2+2


### 6.2. Computational Cost of Our Scheme

For fresh ciphertextsC1,C2∈ZqN×N, the first homomorphic NAND operation in (18) can be simplified as(49)Cl-2′=FLIN,l-2-C1,l-2C2where IN,l-2,C1,l-2 are the (l-2)-th rows of the matrices IN,C1, respectively. Let Ci,l+1:Nl+1:N∈Zqnl×nl denote the submatrix extracted from the (l+1)-th to the N-th rows and columns of Ci(i=1,2). It is clear that each coefficient in Ci,l+1:Nl+1:N(i=1,2) follows a uniform distribution over {0,1}. Let C1,l-2l+1:N∈Zqnl denote the subvector extracted from the (l+1)-th to the N-th coefficients in C1,l-2. It is clear that each coefficient in C1,l-2l+1:N also follows a uniform distribution over {0,1}.Letnadd,i denote the number of additions needed in the multiplication between C1,l-2l+1:N and the i-th column in C2,l+1:Nl+1:N, i=1,…,nl. For the above operation, we need to add 1 to the intermediate result only when both coefficients being multiplied are nonzero. Thus, the probability of needing 1 addition for the multiplication between each pair of coefficients is 1/4. Thus nadd,i follows the binomial distribution Bnl,1/4. Let p4 denote the probability of nadd,i being no more than nb(nb<nl). And let p5=p4nl denote the probability that nadd,i is no more than nb for each i=1,…,nl. When nb is sufficiently large, both p4 and p5 would be close to 1, the multiplication between C1,l-2l+1:N and each column in C2,l+1:Nl+1:N can be simplified as at most nb additions.For the multiplication between the other coefficients inC1,l-2 and C2, an upper bound for the number of needed additions can be derived assuming 1 addition for each corresponding coefficient pair:(50)nadd′=Nl+lN-l=2N-llConsidering the substraction betweenIN,l-2 and C1,l-2C2, an upper bound for the number of needed additions in the 1st homomorphic NAND operation is obtained:(51)nNHE,1=nbnl+nadd′+1=nb+lN-l+Nl+1In the followingFL(·) operation, BD-1(·) is performed followed by a BD(·) operation. In BD-1(·), multiplying a power of 2 is just a shift operation, which generally takes less time than addition. Regarding each shift operation as an addition, an upper bound for the amount of computation can be derived. According to (3), (n+1)(l-1) shift operations and (n+1)(l-1) additions are needed in total in the BD-1(·) operation. In the following BD(·) operation, 2 shifts and 1 addition are needed for each bit generated from BD(·). The 2 shifts correspond to shifting right then left by 1 bit each, and the addition corresponds to the subtraction between the original data and the data after the 2 shifts. The amount of computation needed for generating each bit in BD(·) is upper bounded by 3 additions. Thus the number of additions needed in the flatten operation is upper bounded by the following:(52)nNHE,2=2n+1l-1+3N=n+15l-2According to (19), the number of additions in the 2nd homomorphic NAND operation is(53)nNHE,3=2NAnd the following FL(·) operation again needs at most nNHE,2 additions. According to (20), the number of additions needed in key switching is(54)nNHE,4=Nn′+1Asq′/q=2k′-k, modulus switching for each coefficient in the vector is just the process of shifting right for k-k′ bits and then adding 1 or 0 to the lowest bit before the binary point. Thus the amount of computation in modulus switching for each coefficient can be represented as 2 additions. The number of additions needed in modulus switching is(55)nNHE,5=2n′+1Therefore, the number of additions needed in our scheme is upper bounded by(56)nNHE=∑i=15nNHE,i=nb+n′+2l+3N+10n-nb-l+10l+2n′-4n-1


### 6.3. Computational Cost of GSW

In GSW, as the ciphertext needs to maintain the matrix structure in the2nd homomorphic operation, the 1st homomorphic operation should be performed as matrix operation. The encryption algorithm of GSW is modified as that in our scheme for a better contrast. The computational cost for the multiplication between each row of a matrix and another matrix is shown in (51). And the computational cost of the 2nd homomorphic operation in GSW is omitted here. A lower bound is then obtained for the computational cost of GSW. From (51), it can be learned that the computational cost of GSW is at least(57)nGSW=Nnb+lN-l+Nl+1


### 6.4. Performance Comparison among DM, GSW, and Our Scheme

#### 6.4.1. Parameter Configuration

For convenience, the modulus in each of the above schemes is set to be a power of 2. The parameters in DM are initially set identical to the corresponding simulation parameters in the original DM scheme [21]. The secret key s in DM is uniformly sampled from {0,1}n. For the binary LWE problem, the dimension n should increase to nlog⁡n to ensure equivalent security level as the standard LWE problem [53, 54]. The adversary’s advantage is set to adv=2-64 for all the schemes. For a LWE problem with modulus q, dimension n, and discrete Gaussian noise distribution χ with Gaussian parameter r, the following should be satisfied to guarantee a security level of λ[55]:(58)n≥log22qr·ln⁡1/advπ·log22λ·adv+1107.2qAccording to (58) and the simulation parameters, it can be learned that DM guarantees a security parameter of λ=58. When λ changes, the modulus q is kept unchanged, and the dimension n is set as the smallest integer which guarantees a security level λ for the ciphertext. The error rate pDM,biterr for each homomorphic operation in DM can be derived according to the standard deviation β of the Gaussian noise in the refreshed ciphertext [21]. Specifically, pDM,biterr is the probability that the ciphertext noise magnitude does not exceed q/16. For depth-2 binary circuit with NAND gates, the error rate of DM is(59)pDM,err=1-1-pDM,biterr3For our scheme, the final modulusq′ and dimension n′ are set to be the same as those in DM. The standard deviation of the Gaussian noise is set to σ=3. The modulus and dimension of the initial ciphertext are set according to (32) and (58). Meanwhile, they are set to be as small as possible for efficient operations. nb is the upper bound for the number of additions needed in the multiplication between C1,l-2l+1:N and each column in C2,l+1:Nl+1:N, as illustrated in Section 6.2. Here nb is set to be as small as possible under the constraints p4>1-10-12,p5>1-10-8, where p4,p5 are the probabilities illustrated in Section 6.2. Thus (51) holds and the computational cost of our scheme is made as low as possible. When the security parameter λ changes, the final modulus q′ is kept unchanged, and the final dimension n′ is set as the smallest integer which guarantees a security level λ for the final ciphertext. In order to lower the error rate of our scheme, ϵ1,ϵ2 are set to be as small as possible under the constraints in (35) and (40). Thus B1 is made larger under the constraint (42), which promotes the probability p3. As discussed in the end of Section 5.1, the error rate of our scheme is(60)pNHE,err=1-p1p2p3For the GSW scheme, the standard deviation of the Gaussian noise is also set asσ=3, as in our scheme. And modulus q and dimension N are set as small as possible under the constraint of correct decryption after 2 homomorphic NAND operations. Meanwhile, the ciphertext should guarantee a security level of λ. As long as the noise of the initial 4 ciphertexts are upper bounded by B0=6σ, decryption of the final ciphertext would be correct. Therefore, the error rate of GSW is(61)pGSW,err=1-p1=1-p04N


#### 6.4.2. Performance Comparison

Here a group of security parameters are considered, and the other parameters are set according to the configurations discussed above.pDM,err,pGSW,err,pNHE,err denote the error rates in DM, GSW, and our scheme, respectively, and nDM,nGSW,nNHE denote the corresponding computational costs, as shown in previous discussions. The computational costs and error rates of DM, GSW, and our scheme under different security parameters are shown in Table 2. The error rates are obtained from (59)~(61), and the computational costs are obtained from (48)(56)(57).Table 2
Computational costs and error rates of DM, GSW, and our scheme.
S e c u r i t y   P a r a m e t e r 58 64 70 76 82 88 p D M , e r r ( × 10 - 10 ) 0.54 1.95 7.04 22.07 61.43 154.53 p G S W , e r r ( × 10 - 5 ) 4.27 4.51 4.76 5.00 5.55 5.80 p N H E , e r r ( × 10 - 5 ) 1.89 2.30 3.18 4.31 6.03 8.52 n D M ( × 10 7 ) 5.28 5.61 5.99 6.37 6.75 7.13 n G S W ( × 10 12 ) 1.68 1.97 2.31 2.68 3.64 4.16 n N H E ( × 10 7 ) 1.66 1.85 2.41 2.65 2.92 3.19From Table2, it can be learned that the error rates of GSW and our scheme are higher than that of DM. Nevertheless, they can still be considered to be sufficiently low for being lower than 10-4. The main reason is that the noise magnitudes in multiple initial ciphertexts are constrained in a fixed range. Although p0 is very close to 1, p1=p04N is much lower than p0, thus pGSW,err,pNHE,err are both obviously higher than 1-p0. In DM, pDM,biterr is dependent only on the standard deviation of the refreshed ciphertext, which is sufficiently small compared with q/16. Thus pDM,biterr is a rather low probability. Moreover, pDM,err depends on the error rates of the 3 homomorphic NAND operations, which is only slightly higher than pDM,biterr.It is also shown in Table2 that pNHE,err<pGSW,err for small security parameter, and pNHE,err>pGSW,err when the security parameter is sufficiently large. This is because pNHE,err is affected by p3, the probability of the sum’s absolute value being no more than B1. As the security parameter gets larger, the ciphertext dimension also gets higher, while the upper bound B1 is kept unchanged. When more random errors are summed up, p3 would decrease by a certain extent, and the decrease of p3 is more significant than that of p1=p04N as the increase of N. With the increase of the security parameter, pNHE,err increases faster than pGSW,err.On the other hand, the overall efficiency of our scheme is significantly higher than that of DM and GSW. Specifically,nNHE is more than 50 percent lower than nDM, and several orders of magnitudes lower than nGSW. The main reason lies in that ciphertext refreshing is removed in our scheme, and the 1st homomorphic operation is simplified as a vector-matrix multiplication. The computational cost is further reduced after considering the uniform randomness on {0,1} for most coefficients. By contrast, the 1st homomorphic operation in GSW is performed as matrix multiplication. And ciphertext dimension in GSW is higher than that of the initial ciphertext in our scheme. In DM, ciphertext refreshing introduces a rather high computational cost.


## 6.1. Computational Cost of DM

For a pair of fresh ciphertextsc0,c1∈Zqn+1, the number of additions needed in the homomorphic operation in (13) is(45)nDM,1=n+2It can be learned fromDM.Refresh that Incr(ACC,C) is performed ndr times. The operation in Incr(ACC,C) can be simplified as the multiplication between the 2nd row in ACC and the ciphertext C.The above multiplication needs 2 inner products between a pair of2dg-dimensional vectors in RQ2dg. The fast Fourier transform (FFT) of the coefficient vector of each polynomial in RQ with maximum degree N can be represented as a vector in CN2 where N2=N/2+1. Inner product between a pair of vectors in RQ2dg needs 2N2dg additions and 2N2dg multiplications on complex numbers. Each multiplication on complex numbers needs 4 multiplications and 2 additions on real numbers, and each addition on complex numbers needs 2 additions on real numbers. As multiplication generally takes a longer time than addition, each multiplication on complex numbers needs at least 6 additions. Therefore, the number of additions needed in Incr(ACC,C) is at least(46)nDM,2=2·6+2·2N2dg=32N2dgThe key switching in the3rd step of Algorithm 2 needs Ndks additions on (n+1)-dimensional vectors. Here dks=logBksq and Bks is the base for encoding ciphertexts, as illustrated in DM [21]. Thus the total additions needed in key switching is(47)nDM,3=Ndksn+1The number of additions needed in the next homomorphic operation is the same as (45). As some other steps are omitted here, a lower bound is obtained for the number of needed operations. According to (45)~(47), the number of additions needed in DM is at least(48)nDM=2nDM,1+ndr·nDM,2+nDM,3=32N2ndgdr+n+1Ndks+2+2


## 6.2. Computational Cost of Our Scheme

For fresh ciphertextsC1,C2∈ZqN×N, the first homomorphic NAND operation in (18) can be simplified as(49)Cl-2′=FLIN,l-2-C1,l-2C2where IN,l-2,C1,l-2 are the (l-2)-th rows of the matrices IN,C1, respectively. Let Ci,l+1:Nl+1:N∈Zqnl×nl denote the submatrix extracted from the (l+1)-th to the N-th rows and columns of Ci(i=1,2). It is clear that each coefficient in Ci,l+1:Nl+1:N(i=1,2) follows a uniform distribution over {0,1}. Let C1,l-2l+1:N∈Zqnl denote the subvector extracted from the (l+1)-th to the N-th coefficients in C1,l-2. It is clear that each coefficient in C1,l-2l+1:N also follows a uniform distribution over {0,1}.Letnadd,i denote the number of additions needed in the multiplication between C1,l-2l+1:N and the i-th column in C2,l+1:Nl+1:N, i=1,…,nl. For the above operation, we need to add 1 to the intermediate result only when both coefficients being multiplied are nonzero. Thus, the probability of needing 1 addition for the multiplication between each pair of coefficients is 1/4. Thus nadd,i follows the binomial distribution Bnl,1/4. Let p4 denote the probability of nadd,i being no more than nb(nb<nl). And let p5=p4nl denote the probability that nadd,i is no more than nb for each i=1,…,nl. When nb is sufficiently large, both p4 and p5 would be close to 1, the multiplication between C1,l-2l+1:N and each column in C2,l+1:Nl+1:N can be simplified as at most nb additions.For the multiplication between the other coefficients inC1,l-2 and C2, an upper bound for the number of needed additions can be derived assuming 1 addition for each corresponding coefficient pair:(50)nadd′=Nl+lN-l=2N-llConsidering the substraction betweenIN,l-2 and C1,l-2C2, an upper bound for the number of needed additions in the 1st homomorphic NAND operation is obtained:(51)nNHE,1=nbnl+nadd′+1=nb+lN-l+Nl+1In the followingFL(·) operation, BD-1(·) is performed followed by a BD(·) operation. In BD-1(·), multiplying a power of 2 is just a shift operation, which generally takes less time than addition. Regarding each shift operation as an addition, an upper bound for the amount of computation can be derived. According to (3), (n+1)(l-1) shift operations and (n+1)(l-1) additions are needed in total in the BD-1(·) operation. In the following BD(·) operation, 2 shifts and 1 addition are needed for each bit generated from BD(·). The 2 shifts correspond to shifting right then left by 1 bit each, and the addition corresponds to the subtraction between the original data and the data after the 2 shifts. The amount of computation needed for generating each bit in BD(·) is upper bounded by 3 additions. Thus the number of additions needed in the flatten operation is upper bounded by the following:(52)nNHE,2=2n+1l-1+3N=n+15l-2According to (19), the number of additions in the 2nd homomorphic NAND operation is(53)nNHE,3=2NAnd the following FL(·) operation again needs at most nNHE,2 additions. According to (20), the number of additions needed in key switching is(54)nNHE,4=Nn′+1Asq′/q=2k′-k, modulus switching for each coefficient in the vector is just the process of shifting right for k-k′ bits and then adding 1 or 0 to the lowest bit before the binary point. Thus the amount of computation in modulus switching for each coefficient can be represented as 2 additions. The number of additions needed in modulus switching is(55)nNHE,5=2n′+1Therefore, the number of additions needed in our scheme is upper bounded by(56)nNHE=∑i=15nNHE,i=nb+n′+2l+3N+10n-nb-l+10l+2n′-4n-1


## 6.3. Computational Cost of GSW

In GSW, as the ciphertext needs to maintain the matrix structure in the2nd homomorphic operation, the 1st homomorphic operation should be performed as matrix operation. The encryption algorithm of GSW is modified as that in our scheme for a better contrast. The computational cost for the multiplication between each row of a matrix and another matrix is shown in (51). And the computational cost of the 2nd homomorphic operation in GSW is omitted here. A lower bound is then obtained for the computational cost of GSW. From (51), it can be learned that the computational cost of GSW is at least(57)nGSW=Nnb+lN-l+Nl+1


## 6.4. Performance Comparison among DM, GSW, and Our Scheme

### 6.4.1. Parameter Configuration

For convenience, the modulus in each of the above schemes is set to be a power of 2. The parameters in DM are initially set identical to the corresponding simulation parameters in the original DM scheme [21]. The secret key s in DM is uniformly sampled from {0,1}n. For the binary LWE problem, the dimension n should increase to nlog⁡n to ensure equivalent security level as the standard LWE problem [53, 54]. The adversary’s advantage is set to adv=2-64 for all the schemes. For a LWE problem with modulus q, dimension n, and discrete Gaussian noise distribution χ with Gaussian parameter r, the following should be satisfied to guarantee a security level of λ[55]:(58)n≥log22qr·ln⁡1/advπ·log22λ·adv+1107.2qAccording to (58) and the simulation parameters, it can be learned that DM guarantees a security parameter of λ=58. When λ changes, the modulus q is kept unchanged, and the dimension n is set as the smallest integer which guarantees a security level λ for the ciphertext. The error rate pDM,biterr for each homomorphic operation in DM can be derived according to the standard deviation β of the Gaussian noise in the refreshed ciphertext [21]. Specifically, pDM,biterr is the probability that the ciphertext noise magnitude does not exceed q/16. For depth-2 binary circuit with NAND gates, the error rate of DM is(59)pDM,err=1-1-pDM,biterr3For our scheme, the final modulusq′ and dimension n′ are set to be the same as those in DM. The standard deviation of the Gaussian noise is set to σ=3. The modulus and dimension of the initial ciphertext are set according to (32) and (58). Meanwhile, they are set to be as small as possible for efficient operations. nb is the upper bound for the number of additions needed in the multiplication between C1,l-2l+1:N and each column in C2,l+1:Nl+1:N, as illustrated in Section 6.2. Here nb is set to be as small as possible under the constraints p4>1-10-12,p5>1-10-8, where p4,p5 are the probabilities illustrated in Section 6.2. Thus (51) holds and the computational cost of our scheme is made as low as possible. When the security parameter λ changes, the final modulus q′ is kept unchanged, and the final dimension n′ is set as the smallest integer which guarantees a security level λ for the final ciphertext. In order to lower the error rate of our scheme, ϵ1,ϵ2 are set to be as small as possible under the constraints in (35) and (40). Thus B1 is made larger under the constraint (42), which promotes the probability p3. As discussed in the end of Section 5.1, the error rate of our scheme is(60)pNHE,err=1-p1p2p3For the GSW scheme, the standard deviation of the Gaussian noise is also set asσ=3, as in our scheme. And modulus q and dimension N are set as small as possible under the constraint of correct decryption after 2 homomorphic NAND operations. Meanwhile, the ciphertext should guarantee a security level of λ. As long as the noise of the initial 4 ciphertexts are upper bounded by B0=6σ, decryption of the final ciphertext would be correct. Therefore, the error rate of GSW is(61)pGSW,err=1-p1=1-p04N


### 6.4.2. Performance Comparison

Here a group of security parameters are considered, and the other parameters are set according to the configurations discussed above.pDM,err,pGSW,err,pNHE,err denote the error rates in DM, GSW, and our scheme, respectively, and nDM,nGSW,nNHE denote the corresponding computational costs, as shown in previous discussions. The computational costs and error rates of DM, GSW, and our scheme under different security parameters are shown in Table 2. The error rates are obtained from (59)~(61), and the computational costs are obtained from (48)(56)(57).Table 2
Computational costs and error rates of DM, GSW, and our scheme.
S e c u r i t y   P a r a m e t e r 58 64 70 76 82 88 p D M , e r r ( × 10 - 10 ) 0.54 1.95 7.04 22.07 61.43 154.53 p G S W , e r r ( × 10 - 5 ) 4.27 4.51 4.76 5.00 5.55 5.80 p N H E , e r r ( × 10 - 5 ) 1.89 2.30 3.18 4.31 6.03 8.52 n D M ( × 10 7 ) 5.28 5.61 5.99 6.37 6.75 7.13 n G S W ( × 10 12 ) 1.68 1.97 2.31 2.68 3.64 4.16 n N H E ( × 10 7 ) 1.66 1.85 2.41 2.65 2.92 3.19From Table2, it can be learned that the error rates of GSW and our scheme are higher than that of DM. Nevertheless, they can still be considered to be sufficiently low for being lower than 10-4. The main reason is that the noise magnitudes in multiple initial ciphertexts are constrained in a fixed range. Although p0 is very close to 1, p1=p04N is much lower than p0, thus pGSW,err,pNHE,err are both obviously higher than 1-p0. In DM, pDM,biterr is dependent only on the standard deviation of the refreshed ciphertext, which is sufficiently small compared with q/16. Thus pDM,biterr is a rather low probability. Moreover, pDM,err depends on the error rates of the 3 homomorphic NAND operations, which is only slightly higher than pDM,biterr.It is also shown in Table2 that pNHE,err<pGSW,err for small security parameter, and pNHE,err>pGSW,err when the security parameter is sufficiently large. This is because pNHE,err is affected by p3, the probability of the sum’s absolute value being no more than B1. As the security parameter gets larger, the ciphertext dimension also gets higher, while the upper bound B1 is kept unchanged. When more random errors are summed up, p3 would decrease by a certain extent, and the decrease of p3 is more significant than that of p1=p04N as the increase of N. With the increase of the security parameter, pNHE,err increases faster than pGSW,err.On the other hand, the overall efficiency of our scheme is significantly higher than that of DM and GSW. Specifically,nNHE is more than 50 percent lower than nDM, and several orders of magnitudes lower than nGSW. The main reason lies in that ciphertext refreshing is removed in our scheme, and the 1st homomorphic operation is simplified as a vector-matrix multiplication. The computational cost is further reduced after considering the uniform randomness on {0,1} for most coefficients. By contrast, the 1st homomorphic operation in GSW is performed as matrix multiplication. And ciphertext dimension in GSW is higher than that of the initial ciphertext in our scheme. In DM, ciphertext refreshing introduces a rather high computational cost.


## 6.4.1. Parameter Configuration

For convenience, the modulus in each of the above schemes is set to be a power of 2. The parameters in DM are initially set identical to the corresponding simulation parameters in the original DM scheme [21]. The secret key s in DM is uniformly sampled from {0,1}n. For the binary LWE problem, the dimension n should increase to nlog⁡n to ensure equivalent security level as the standard LWE problem [53, 54]. The adversary’s advantage is set to adv=2-64 for all the schemes. For a LWE problem with modulus q, dimension n, and discrete Gaussian noise distribution χ with Gaussian parameter r, the following should be satisfied to guarantee a security level of λ[55]:(58)n≥log22qr·ln⁡1/advπ·log22λ·adv+1107.2qAccording to (58) and the simulation parameters, it can be learned that DM guarantees a security parameter of λ=58. When λ changes, the modulus q is kept unchanged, and the dimension n is set as the smallest integer which guarantees a security level λ for the ciphertext. The error rate pDM,biterr for each homomorphic operation in DM can be derived according to the standard deviation β of the Gaussian noise in the refreshed ciphertext [21]. Specifically, pDM,biterr is the probability that the ciphertext noise magnitude does not exceed q/16. For depth-2 binary circuit with NAND gates, the error rate of DM is(59)pDM,err=1-1-pDM,biterr3For our scheme, the final modulusq′ and dimension n′ are set to be the same as those in DM. The standard deviation of the Gaussian noise is set to σ=3. The modulus and dimension of the initial ciphertext are set according to (32) and (58). Meanwhile, they are set to be as small as possible for efficient operations. nb is the upper bound for the number of additions needed in the multiplication between C1,l-2l+1:N and each column in C2,l+1:Nl+1:N, as illustrated in Section 6.2. Here nb is set to be as small as possible under the constraints p4>1-10-12,p5>1-10-8, where p4,p5 are the probabilities illustrated in Section 6.2. Thus (51) holds and the computational cost of our scheme is made as low as possible. When the security parameter λ changes, the final modulus q′ is kept unchanged, and the final dimension n′ is set as the smallest integer which guarantees a security level λ for the final ciphertext. In order to lower the error rate of our scheme, ϵ1,ϵ2 are set to be as small as possible under the constraints in (35) and (40). Thus B1 is made larger under the constraint (42), which promotes the probability p3. As discussed in the end of Section 5.1, the error rate of our scheme is(60)pNHE,err=1-p1p2p3For the GSW scheme, the standard deviation of the Gaussian noise is also set asσ=3, as in our scheme. And modulus q and dimension N are set as small as possible under the constraint of correct decryption after 2 homomorphic NAND operations. Meanwhile, the ciphertext should guarantee a security level of λ. As long as the noise of the initial 4 ciphertexts are upper bounded by B0=6σ, decryption of the final ciphertext would be correct. Therefore, the error rate of GSW is(61)pGSW,err=1-p1=1-p04N


## 6.4.2. Performance Comparison

Here a group of security parameters are considered, and the other parameters are set according to the configurations discussed above.pDM,err,pGSW,err,pNHE,err denote the error rates in DM, GSW, and our scheme, respectively, and nDM,nGSW,nNHE denote the corresponding computational costs, as shown in previous discussions. The computational costs and error rates of DM, GSW, and our scheme under different security parameters are shown in Table 2. The error rates are obtained from (59)~(61), and the computational costs are obtained from (48)(56)(57).Table 2
Computational costs and error rates of DM, GSW, and our scheme.
S e c u r i t y   P a r a m e t e r 58 64 70 76 82 88 p D M , e r r ( × 10 - 10 ) 0.54 1.95 7.04 22.07 61.43 154.53 p G S W , e r r ( × 10 - 5 ) 4.27 4.51 4.76 5.00 5.55 5.80 p N H E , e r r ( × 10 - 5 ) 1.89 2.30 3.18 4.31 6.03 8.52 n D M ( × 10 7 ) 5.28 5.61 5.99 6.37 6.75 7.13 n G S W ( × 10 12 ) 1.68 1.97 2.31 2.68 3.64 4.16 n N H E ( × 10 7 ) 1.66 1.85 2.41 2.65 2.92 3.19From Table2, it can be learned that the error rates of GSW and our scheme are higher than that of DM. Nevertheless, they can still be considered to be sufficiently low for being lower than 10-4. The main reason is that the noise magnitudes in multiple initial ciphertexts are constrained in a fixed range. Although p0 is very close to 1, p1=p04N is much lower than p0, thus pGSW,err,pNHE,err are both obviously higher than 1-p0. In DM, pDM,biterr is dependent only on the standard deviation of the refreshed ciphertext, which is sufficiently small compared with q/16. Thus pDM,biterr is a rather low probability. Moreover, pDM,err depends on the error rates of the 3 homomorphic NAND operations, which is only slightly higher than pDM,biterr.It is also shown in Table2 that pNHE,err<pGSW,err for small security parameter, and pNHE,err>pGSW,err when the security parameter is sufficiently large. This is because pNHE,err is affected by p3, the probability of the sum’s absolute value being no more than B1. As the security parameter gets larger, the ciphertext dimension also gets higher, while the upper bound B1 is kept unchanged. When more random errors are summed up, p3 would decrease by a certain extent, and the decrease of p3 is more significant than that of p1=p04N as the increase of N. With the increase of the security parameter, pNHE,err increases faster than pGSW,err.On the other hand, the overall efficiency of our scheme is significantly higher than that of DM and GSW. Specifically,nNHE is more than 50 percent lower than nDM, and several orders of magnitudes lower than nGSW. The main reason lies in that ciphertext refreshing is removed in our scheme, and the 1st homomorphic operation is simplified as a vector-matrix multiplication. The computational cost is further reduced after considering the uniform randomness on {0,1} for most coefficients. By contrast, the 1st homomorphic operation in GSW is performed as matrix multiplication. And ciphertext dimension in GSW is higher than that of the initial ciphertext in our scheme. In DM, ciphertext refreshing introduces a rather high computational cost.


## 7. Conclusions

Aiming at the problem of low efficiency caused by overly frequent ciphertext refreshings in DM, we propose a new FHE scheme to achieve a higher efficiency. We utilize ciphertext matrix operations in GSW and ciphertext vector additions in DM to construct our scheme. Furthermore, we combine the advantage of efficient homomorphic operation in DM with the advantage of moderate growth of ciphertext noise magnitude in GSW. Our scheme inherits the conceptual simplicity of DM and GSW and allows 2 homomorphic NAND operations to be performed on ciphertexts before ciphertext refreshing. Results show that under the same security parameters, the computational cost of our scheme is obviously lower than that in DM and GSW for a depth-2 binary circuit with NAND gates. Thus our scheme is significantly more efficient than DM and GSW. Meanwhile, the error rate of our scheme is kept at a sufficiently low level.Our work focuses on constructing a simple and efficient FHE scheme based on DM and GSW schemes. We also analyze its correctness, security, and applicability and present a comparison with DM and GSW schemes in terms of computational costs and error rates. Our FHE scheme is intended for universal privacy-preserving computations in the real world. However, our work is limited to the theoretical level. Concrete implementation for our scheme is not considered in our work. And the application of our scheme to real-world algorithms needs to be further explored.



---

*Source: 8706940-2018-12-16.xml*