# Achieving Message-Encapsulated Leveled FHE for IoT Privacy Protection

Authors: Weiping Ouyang; Chunguang Ma; Guoyin Zhang; Keming Diao
Journal: Mobile Information Systems
 (2020)

---

## Abstract

The rapid development of the Internet of Things has made the issue of privacy protection even more concerning. Privacy protection has affected the large-scale application of the Internet of Things. Fully Homomorphic Encryption (FHE) is a newly emerging public key encryption scheme, which can be used to prevent information leakage. It allows performing arbitrary algebraic operations on data which are encrypted, such that the operation performed on the ciphertext is directly transformed into the corresponding plaintext. Recently, overwhelming majority of FHE schemes are confined to single-bit encryption, whereas how to achieve a multibit FHE scheme is still an open problem. This problem is partially (rather than fully) solved by Hiromasa-Abe-Okamoto (PKC′15), who proposed a packed message FHE scheme which only supports decryption in a bit-by-bit manner. Followed by that, Li-Ma-Morais-Du (Inscrypt′16) proposed a multibit FHE scheme which can decrypt the ciphertext at one time, but their scheme is based on dual LWE assumption. Armed with the abovementioned two schemes, in this paper, we propose an efficient packed message FHE that supports the decryption in two ways: single-bit decryption and one-time decryption.


---

## Body

## 1. Introduction

In recent years, the Internet of Things (IoT) has become an attractive system paradigm to drive a substantive leap on goods and services and has been widely used in intelligent transportation, intelligent power grid, environmental monitoring and perception, intelligent home appliances, and other fields. It covers traditional equipment to general household equipment, which brings more efficiency and convenience to the users. Because many of the data transmitted in the Internet of Things are confidential information or personal privacy information, it usually needs to be encrypted first. With more and more encrypted data stored on the server, it is very frequent for us to retrieve and process these data. Although there are some algorithms for retrieving encrypted data, they are only suitable for small-scale data, and the cost is too high. The encrypted data retrieval method based on the Fully Homomorphic Encryption (FHE) can solve this problem. By directly retrieving the encrypted data, it not only ensures that the retrieved data will not be analyzed, but also carries out homomorphic operation on the retrieved data without changing the sequence of the corresponding plaintext. It can not only protect the user’s data security but also improve the retrieval efficiency. Since the first introduction of Gentry in 2009, the construction and optimization of the Fully Homomorphic Encryption scheme have been paid special attention by researchers. However, most of the existing Fully Homomorphic Encryption schemes only allow cryptographic calculations for a single bit, and the efficiency is not satisfactory. Although the cascading (or simple combination) approach can be used to implement message-encapsulated calculations, the performance of such a simple message-encapsulated FHE is not ideal.In an application scenario, in many cases, it is necessary to calculate data of multiple bits at a time, and thus, constructing an efficient Message-encapsulation Fully Homomorphic encryption becomes an urgent requirement. At present, the research in this area has made initial progress [1, 2], which has increased the efficiency of FHE to a certain extent, but comprehensively, its efficiency still needs to be improved. Specifically, the following are considered:(1)
Brakerski’s scheme [1] is constructed on the basis of the Brakerski’s [3] scheme and is a typical representative of the second generation of FHE. But, the latter scheme needs to implement homomorphic calculations by calculating the evaluation key, which increases the computational cost.(2)
Hiromasa-Abe-Okamoto (HAO) [2] is based on the GSW [4] scheme and is a typical representative of the third generation of FHE. HAO constructs a message-encapsulation FHE scheme in the form of encapsulated messages, but it cannot implement one-time decryption and only decrypts the ciphertext bit-by-bit, so the scheme is still very inefficient.An important question arises: Besides those mentioned above, is it possible to design an efficient method to decrypt the ciphertext of the message-encapsulation GSW-FHE scheme at one time?Li et al. [5] used dual Regev [6] to construct a public key with multiple instances of the small short integer solution (SIS). Inspired by this work, we will construct public keys with multiple instances of LWEs (Learning with errors), and this constructs a Message-Encapsulation FHE scheme that can be decrypted at one time.


### 1.1. Our Contribution

Firstly, the public key of the Message-encapsulation Fully Homomorphic Encryption scheme of Hiromasa et al. [2] is as follows:(1)B≔A⋅T+EmodqA∈ℤqm×t×ℤqm×n.Among them are the secret matrixT⟵ℤqn×t and the noise matrix E⟵χm×t. Then, the plaintext message is encapsulated in a matrix, and the public key of the abovementioned form is used to encrypt the message. However, the obtained ciphertext matrix cannot recover all the plaintext bits at one time, but can only be decrypted bit-by-bit.Secondly, we notice that the public key matrix of the message-encapsulated fully homomorphic encryption scheme constructed by Li et al. [5] is as follows:(2)A⋅e1,…,A⋅etA∈ℤqm×t×ℤqm×n.Among them, there ise1,…,A⋅et⟵χn×1. Although Li et al.’s scheme [5] supports bit-by-bit encryption and one-time decryption, the scheme relies on the minimum integer solution hypothesis (see detailed analysis in [7]), and its parameter size depends on mm≥nlogq instead of causing the size of the evaluation key and the ciphertext to be too large.Based on the abovementioned observations, in this paper, we construct a public key matrix first with multiple LWE instances. Different from the typical FHE scheme [3, 4, 8] and follow-up works [9–13], its public key matrix contains only one LWE instance. Then, using the new public key, we construct a message-encapsulation GSW-class FEH scheme (MFHE). We give an overview of the scheme in the following:(1)
Firstly, we use a new public key matrix with multiple LWE instances as follows:(3)A′=b1,…,btA∈ℤqm×n+t.Among them,b1=A⋅ti+eimodq and i∈t is an LWE instance. This is significantly different from existing message-encapsulation PKE schemes (for example, [14, 15]) and message-encapsulation FHE schemes (for example, [1, 2]) and is also the fundamental difference between other schemes and the FHE scheme constructed in this paper. Private keys corresponding to the public key b1,…,btA is shaped as follows:(4)ski≔0,…,1,…,0ti∈ℤq1×n+t,i∈t.(2)
Next, we use the public key matrixA′ we constructed to encrypt multibit messages. The difference is that we use the message-encapsulation method of Li et al. [5] and Hiromasa et al. [2] to embed multibit messages into the plaintext of a diagonal matrix. That is,(5)M≔diagm1,…,mt1,…,1∈ℤqn+t×n+t,and while constructing a private key matrix with private keys,(6)S≔Et1⋮tt∈ℤqn+t×n+t.En×n is the identity matrix, and we can get(7)S⋅M≔diagm1,…,mtt1⋮tt.Finally, using the matrixW≔diag⌊q/2⌋,…,⌊q/2⌋0 we constructed, calculation of SM⋅GG−1W can directly recover the message vector m1,…,mt . See Section 4 for a detailed analysis.


### 1.2. Organization and Structure of the Paper

The rest of this paper is organized as follows. InSection 2, the definitions and symbols used in this paper are introduced. In Section 3, we review the scheme of Gentry-Sahai-Waters et al. In Section 4, we introduce the Message-encapsulation FHE (MFHE) scheme we constructed. Finally, we give a summary of the full paper in Chapter 5.


## 1.1. Our Contribution

Firstly, the public key of the Message-encapsulation Fully Homomorphic Encryption scheme of Hiromasa et al. [2] is as follows:(1)B≔A⋅T+EmodqA∈ℤqm×t×ℤqm×n.Among them are the secret matrixT⟵ℤqn×t and the noise matrix E⟵χm×t. Then, the plaintext message is encapsulated in a matrix, and the public key of the abovementioned form is used to encrypt the message. However, the obtained ciphertext matrix cannot recover all the plaintext bits at one time, but can only be decrypted bit-by-bit.Secondly, we notice that the public key matrix of the message-encapsulated fully homomorphic encryption scheme constructed by Li et al. [5] is as follows:(2)A⋅e1,…,A⋅etA∈ℤqm×t×ℤqm×n.Among them, there ise1,…,A⋅et⟵χn×1. Although Li et al.’s scheme [5] supports bit-by-bit encryption and one-time decryption, the scheme relies on the minimum integer solution hypothesis (see detailed analysis in [7]), and its parameter size depends on mm≥nlogq instead of causing the size of the evaluation key and the ciphertext to be too large.Based on the abovementioned observations, in this paper, we construct a public key matrix first with multiple LWE instances. Different from the typical FHE scheme [3, 4, 8] and follow-up works [9–13], its public key matrix contains only one LWE instance. Then, using the new public key, we construct a message-encapsulation GSW-class FEH scheme (MFHE). We give an overview of the scheme in the following:(1)
Firstly, we use a new public key matrix with multiple LWE instances as follows:(3)A′=b1,…,btA∈ℤqm×n+t.Among them,b1=A⋅ti+eimodq and i∈t is an LWE instance. This is significantly different from existing message-encapsulation PKE schemes (for example, [14, 15]) and message-encapsulation FHE schemes (for example, [1, 2]) and is also the fundamental difference between other schemes and the FHE scheme constructed in this paper. Private keys corresponding to the public key b1,…,btA is shaped as follows:(4)ski≔0,…,1,…,0ti∈ℤq1×n+t,i∈t.(2)
Next, we use the public key matrixA′ we constructed to encrypt multibit messages. The difference is that we use the message-encapsulation method of Li et al. [5] and Hiromasa et al. [2] to embed multibit messages into the plaintext of a diagonal matrix. That is,(5)M≔diagm1,…,mt1,…,1∈ℤqn+t×n+t,and while constructing a private key matrix with private keys,(6)S≔Et1⋮tt∈ℤqn+t×n+t.En×n is the identity matrix, and we can get(7)S⋅M≔diagm1,…,mtt1⋮tt.Finally, using the matrixW≔diag⌊q/2⌋,…,⌊q/2⌋0 we constructed, calculation of SM⋅GG−1W can directly recover the message vector m1,…,mt . See Section 4 for a detailed analysis.


## 1.2. Organization and Structure of the Paper

The rest of this paper is organized as follows. InSection 2, the definitions and symbols used in this paper are introduced. In Section 3, we review the scheme of Gentry-Sahai-Waters et al. In Section 4, we introduce the Message-encapsulation FHE (MFHE) scheme we constructed. Finally, we give a summary of the full paper in Chapter 5.


## 2. Preliminaries

In this section, we give the preparatory knowledge needed, including definitions and lemmas.


### 2.1. Symbols

Forn∈ℕ, we use n to represent aggregation 1,…,n. For a real number x∈ℝ, we use ⌊x⌋ to represent the largest integer that is not greater than x, ⌊x⌋≔⌊x+1/2⌋ to represent the nearest integer to x. We represent vectors in bold lowercase letters, for example, x, and the matrix in bold uppercase letters, for example, A. In addition, we use Ai,j to represent elements in Ai,j from row i and column j. We use “≔” to indicate the assignment. It is worth noting that we use the definition of computationally indistinguishable and statistics indistinguishable and they are represented by ≈c and ≈s. In addition to this, we also define v∞=maxv1,…,vn and R=maxiri. For convenience, we use v to represent its l2 norm.We need to use the following variant of the Left-over Hash Lemma (LHL) [16].Lemma 1.
(Matrix-Vector LHL). Letλ∈ℤ,n,q∈ℕ,m≥nlogq+2λ,r⟵R0,1m and y⟵Rℤqn. We select a uniform random matrix A⟵Rℤqm×n, and then, the statistical distance of the distribution A,ATr and A,y is as follows:(8)ΔA,AT⋅r,A,y≤2−λ.


### 2.2. Learning with Errors (LWEs)

LWEs is the main computational assumption that cryptosystems and our variants rely on.Definition 1.
(LWE Distribution). For safety parameters, letn=nλ and m=mλ be integers, let χ=χλ be the ℤ error distribution with the bound of B=Bλ, and let q=qλ≥2 be an integer modulo of any polynomial p=pλ that meets q≥2p⋅B. Then, we select a vector s∈ℤqn×1 and call it a secret, the LWE distribution As,χ in ℤqn×ℤq is selected uniformly and randomly, and we select e⟵χm×1 and output A,b=A⋅s+emodq.
There are two kinds of the LWE hypothesis: the search-LWE and the decision-LWE. The decision-LWE is defined as follows:Definition 2.
(Decision-LWEn,q,χ,m). Assume an independent selected A,b∈ℤqm×n×ℤqm×1, which is selected according to one of the following distributions: (1) for As,χ from a uniform and random s∈ℤqn (i.e., A,b:A⟵ℤqm×n,s⟵ℤqn×1,e⟵χm×1,b=A⋅s+emodq) or (2) uniform distribution (i.e., A,b:A⟵ℤqm×n,b⟵ℤqm×1). The two distributions mentioned above are computable indistinguishable.Note 1.
Regev and others [6, 17–19] introduce the convention between the approximate shortest vector problem (for appropriate parameters) in the LWE hypothesis. We have omitted the lemma of the results of these schemes; see [6, 17–19] for details.


### 2.3. Discrete Gauss

In our structure, we need to analyze the behavior of choosing the wrong element from the Gaussian distribution.Definition 3.
(B Bounded [3]). A distribution χ=χλ on an integer if the following exists:(9)Prx⟵$χx≥B≤2−Ω˜n,and then, it is called B-bound (represented as χ≤B).
For the analysis of our scheme, the vector selected from the Gaussian distribution needs to have a certain bound on its norm.Lemma 2.
(See [20]). 1. For ∀k>0,Pre>k⋅σ,e⟵Dσ1≤2⋅exp−k2/2; 2. for ∀k>0, there is Pre>k⋅σ⋅me⟵Dσm≤km⋅expm/2⋅1−k2 Therefore, in this paper, we set e≤B and e≤2mB.
In this paper, we assumeσ≥2n. So, if e⟵Dσm, then on average, e≈m⋅σ. It can be known from Lemma 2.2 (2) that there is a high possibility that e≤2σm. Therefore, in this paper, we set e≤B and e≤2mB.


### 2.4. Leveled Fully Homomorphic Encryption

In public-key cryptography, the cipher keeps a public key and encrypts the message in order that the corresponding private key holder can recover the original plaintext message.Definition 4.
(See [21]). Let a fixed function L=Lλ be the level of Fully Homomorphic Encryption. For a kind of circuit Cλλ∈N, the L-FHE scheme includes four Probabilistic Polynomial Times (PPTs), and the algorithm is as follows:(10)KeyGen,Enc,Dec,Eval.The key generation algorithm (KeyGen) is a randomization algorithm that inputs security parameters1λ and outputs public keys (pk) and private keys (sk)The encryption algorithm Enc is a randomization algorithm that inputs a public key (pk) and a message m∈0,1∗ and outputs a ciphertext cThe decryption algorithm Dec is a deterministic algorithm that inputs the private keysk and ciphertext and outputs the decrypted message m∈0,1∗The homomorphic algorithm Eval inputs a public keypk, a circuit C∈Cλ, and a sequence of ciphertexts c1,…,cℓλ, here let ℓλ be a polynomial related to λ the and outputs the computed ciphertext c⋆The correctness requirements are as follows:For arbitraryλ,m∈0,1∗ and pk,sk output by KeyGen1λ, we have(11)m=Decsk,Encpk,m.For arbitraryλ, arbitrary m1,…,ml∈0,1∗, and C∈Cλ, we have(12)Cm1,…,mℓ=Decsk,Evalpk,C,Encpk,m1,…,Encpk,mℓ.Definition 5.
(CPA Security [21]). One FHE scheme is indistinguishable from the choice of plaintext attack (IND−CPA): the condition that security needs to be satisfied is that for any PPT adversary A, the following probabilities related to are negligible:(13)PrApk,Encpk,m0=1,−PrApk,Encpk,m1=1=neglλ.
Among them,pk,sk⟵KeyGen1λ and m0⋅m1 is arbitrarily selected from the plaintext space by the adversary.
The security definition of a message-encapsulation GSW (MFHE) is the same as GSW for a single bit. Because in public key settings, the security of single message encryption implies the security of multiple message encryption. See section 11 in [22] for more details.Definition 6.
(Compactness [21]). For a class of loops ℂkk∈ℕ, if there is a polynomial α=αλ such that the length of output ciphertext of Eval is at most α, then an L Fully Homomorphic Encryption is compact (if it is nontrivial, then for all λ, some C∈ℂλ, and we have αλ≤C).


### 2.5. Basic Tools

Let us review some of the basic tools proposed by Brakerski and Vaikuntanathan [23] and Gentry et al. [4]. We fix q,m∈ℕ. Let l=⌊logq⌋+1, and therefore, 2l−1≤q<2l and N=m⋅l.Definition 7.
(See [24, 25]). The algorithm BitComp enters a vector v∈ℤqm and outputs an N-dimensional vector v1,0,…,v1,l−1,…,vm,0,…,vm,l−1T∈0,1N where vi,j is the j bit in the binary representation of vi (sorted by minimum impact to maximum impact). In other words,(14)vi=∑j=0l−12jvi,j.Definition 8.
(See [24, 25]). Algorithm enters a vector(15)v=v1,0,…,v1,l−1,…,vm,0,…,vm,l−1T∈qNand output ∑j=0l−12j,…,v1,j,…,∑j=0l−12jvm,jT∈qm.
Note that the input vectorv does not need to be binary and any of the input vector algorithms in ℤN are already defined.Definition 9.
(See [24, 25]). The algorithm Flatten enters a vector v∈ℤqN and outputs an N-dimension binary vector (i.e., an element from 0,1N) defined as(16)Flattenv=BitDecompBitDecomp−1v.Definition 10.
(See [24, 25]). The algorithm PoweOftwo enters an m-dimension vector v∈ℤqN and outputs an N-dimension vector in ℤqN. The output is as follows:(17)v1,2v1,…,2l−1v1,…,vm,2vm,…,2l−1vmT.Lemma 3.
(See [26]). For any N≥m⌊logq⌋, there is a fixed effective computable matrix G∈ℤqm×N and a valid computable deterministic “short-image” function G−1⋅ that meets the following conditions. For arbitrary m′, we enter a matrix M∈ℤqm×m′ and the inverse function G−1M outputs a matrix G−1M∈0,1N×m′ so that GG−1M=M.Note 2.
In fact, we can also express the abovementioned definitions and results as follows using the language ofG and G−1. Micciancio and Peikert’s [26] matrix G can be expressed as G=Im⊗∈ℤqm×N, where g=1,2,4,…,2l−1T. For v∈ℤqm, there is v=vTG. For v∈ℤqN, there is BitDecomp−1v=Gv. For a∈ℤqm, the algorithm BitDecompa is renamed as G−1a. For v∈ℤqm, there is Power Of twov=vTG. For v∈ℤqN, there is BitDecomp−1v=Gv. For a∈ℤqm, the algorithm BitDecompa is renamed as G−1a.


## 2.1. Symbols

Forn∈ℕ, we use n to represent aggregation 1,…,n. For a real number x∈ℝ, we use ⌊x⌋ to represent the largest integer that is not greater than x, ⌊x⌋≔⌊x+1/2⌋ to represent the nearest integer to x. We represent vectors in bold lowercase letters, for example, x, and the matrix in bold uppercase letters, for example, A. In addition, we use Ai,j to represent elements in Ai,j from row i and column j. We use “≔” to indicate the assignment. It is worth noting that we use the definition of computationally indistinguishable and statistics indistinguishable and they are represented by ≈c and ≈s. In addition to this, we also define v∞=maxv1,…,vn and R=maxiri. For convenience, we use v to represent its l2 norm.We need to use the following variant of the Left-over Hash Lemma (LHL) [16].Lemma 1.
(Matrix-Vector LHL). Letλ∈ℤ,n,q∈ℕ,m≥nlogq+2λ,r⟵R0,1m and y⟵Rℤqn. We select a uniform random matrix A⟵Rℤqm×n, and then, the statistical distance of the distribution A,ATr and A,y is as follows:(8)ΔA,AT⋅r,A,y≤2−λ.


## 2.2. Learning with Errors (LWEs)

LWEs is the main computational assumption that cryptosystems and our variants rely on.Definition 1.
(LWE Distribution). For safety parameters, letn=nλ and m=mλ be integers, let χ=χλ be the ℤ error distribution with the bound of B=Bλ, and let q=qλ≥2 be an integer modulo of any polynomial p=pλ that meets q≥2p⋅B. Then, we select a vector s∈ℤqn×1 and call it a secret, the LWE distribution As,χ in ℤqn×ℤq is selected uniformly and randomly, and we select e⟵χm×1 and output A,b=A⋅s+emodq.
There are two kinds of the LWE hypothesis: the search-LWE and the decision-LWE. The decision-LWE is defined as follows:Definition 2.
(Decision-LWEn,q,χ,m). Assume an independent selected A,b∈ℤqm×n×ℤqm×1, which is selected according to one of the following distributions: (1) for As,χ from a uniform and random s∈ℤqn (i.e., A,b:A⟵ℤqm×n,s⟵ℤqn×1,e⟵χm×1,b=A⋅s+emodq) or (2) uniform distribution (i.e., A,b:A⟵ℤqm×n,b⟵ℤqm×1). The two distributions mentioned above are computable indistinguishable.Note 1.
Regev and others [6, 17–19] introduce the convention between the approximate shortest vector problem (for appropriate parameters) in the LWE hypothesis. We have omitted the lemma of the results of these schemes; see [6, 17–19] for details.


## 2.3. Discrete Gauss

In our structure, we need to analyze the behavior of choosing the wrong element from the Gaussian distribution.Definition 3.
(B Bounded [3]). A distribution χ=χλ on an integer if the following exists:(9)Prx⟵$χx≥B≤2−Ω˜n,and then, it is called B-bound (represented as χ≤B).
For the analysis of our scheme, the vector selected from the Gaussian distribution needs to have a certain bound on its norm.Lemma 2.
(See [20]). 1. For ∀k>0,Pre>k⋅σ,e⟵Dσ1≤2⋅exp−k2/2; 2. for ∀k>0, there is Pre>k⋅σ⋅me⟵Dσm≤km⋅expm/2⋅1−k2 Therefore, in this paper, we set e≤B and e≤2mB.
In this paper, we assumeσ≥2n. So, if e⟵Dσm, then on average, e≈m⋅σ. It can be known from Lemma 2.2 (2) that there is a high possibility that e≤2σm. Therefore, in this paper, we set e≤B and e≤2mB.


## 2.4. Leveled Fully Homomorphic Encryption

In public-key cryptography, the cipher keeps a public key and encrypts the message in order that the corresponding private key holder can recover the original plaintext message.Definition 4.
(See [21]). Let a fixed function L=Lλ be the level of Fully Homomorphic Encryption. For a kind of circuit Cλλ∈N, the L-FHE scheme includes four Probabilistic Polynomial Times (PPTs), and the algorithm is as follows:(10)KeyGen,Enc,Dec,Eval.The key generation algorithm (KeyGen) is a randomization algorithm that inputs security parameters1λ and outputs public keys (pk) and private keys (sk)The encryption algorithm Enc is a randomization algorithm that inputs a public key (pk) and a message m∈0,1∗ and outputs a ciphertext cThe decryption algorithm Dec is a deterministic algorithm that inputs the private keysk and ciphertext and outputs the decrypted message m∈0,1∗The homomorphic algorithm Eval inputs a public keypk, a circuit C∈Cλ, and a sequence of ciphertexts c1,…,cℓλ, here let ℓλ be a polynomial related to λ the and outputs the computed ciphertext c⋆The correctness requirements are as follows:For arbitraryλ,m∈0,1∗ and pk,sk output by KeyGen1λ, we have(11)m=Decsk,Encpk,m.For arbitraryλ, arbitrary m1,…,ml∈0,1∗, and C∈Cλ, we have(12)Cm1,…,mℓ=Decsk,Evalpk,C,Encpk,m1,…,Encpk,mℓ.Definition 5.
(CPA Security [21]). One FHE scheme is indistinguishable from the choice of plaintext attack (IND−CPA): the condition that security needs to be satisfied is that for any PPT adversary A, the following probabilities related to are negligible:(13)PrApk,Encpk,m0=1,−PrApk,Encpk,m1=1=neglλ.
Among them,pk,sk⟵KeyGen1λ and m0⋅m1 is arbitrarily selected from the plaintext space by the adversary.
The security definition of a message-encapsulation GSW (MFHE) is the same as GSW for a single bit. Because in public key settings, the security of single message encryption implies the security of multiple message encryption. See section 11 in [22] for more details.Definition 6.
(Compactness [21]). For a class of loops ℂkk∈ℕ, if there is a polynomial α=αλ such that the length of output ciphertext of Eval is at most α, then an L Fully Homomorphic Encryption is compact (if it is nontrivial, then for all λ, some C∈ℂλ, and we have αλ≤C).


## 2.5. Basic Tools

Let us review some of the basic tools proposed by Brakerski and Vaikuntanathan [23] and Gentry et al. [4]. We fix q,m∈ℕ. Let l=⌊logq⌋+1, and therefore, 2l−1≤q<2l and N=m⋅l.Definition 7.
(See [24, 25]). The algorithm BitComp enters a vector v∈ℤqm and outputs an N-dimensional vector v1,0,…,v1,l−1,…,vm,0,…,vm,l−1T∈0,1N where vi,j is the j bit in the binary representation of vi (sorted by minimum impact to maximum impact). In other words,(14)vi=∑j=0l−12jvi,j.Definition 8.
(See [24, 25]). Algorithm enters a vector(15)v=v1,0,…,v1,l−1,…,vm,0,…,vm,l−1T∈qNand output ∑j=0l−12j,…,v1,j,…,∑j=0l−12jvm,jT∈qm.
Note that the input vectorv does not need to be binary and any of the input vector algorithms in ℤN are already defined.Definition 9.
(See [24, 25]). The algorithm Flatten enters a vector v∈ℤqN and outputs an N-dimension binary vector (i.e., an element from 0,1N) defined as(16)Flattenv=BitDecompBitDecomp−1v.Definition 10.
(See [24, 25]). The algorithm PoweOftwo enters an m-dimension vector v∈ℤqN and outputs an N-dimension vector in ℤqN. The output is as follows:(17)v1,2v1,…,2l−1v1,…,vm,2vm,…,2l−1vmT.Lemma 3.
(See [26]). For any N≥m⌊logq⌋, there is a fixed effective computable matrix G∈ℤqm×N and a valid computable deterministic “short-image” function G−1⋅ that meets the following conditions. For arbitrary m′, we enter a matrix M∈ℤqm×m′ and the inverse function G−1M outputs a matrix G−1M∈0,1N×m′ so that GG−1M=M.Note 2.
In fact, we can also express the abovementioned definitions and results as follows using the language ofG and G−1. Micciancio and Peikert’s [26] matrix G can be expressed as G=Im⊗∈ℤqm×N, where g=1,2,4,…,2l−1T. For v∈ℤqm, there is v=vTG. For v∈ℤqN, there is BitDecomp−1v=Gv. For a∈ℤqm, the algorithm BitDecompa is renamed as G−1a. For v∈ℤqm, there is Power Of twov=vTG. For v∈ℤqN, there is BitDecomp−1v=Gv. For a∈ℤqm, the algorithm BitDecompa is renamed as G−1a.


## 3. Gentry–Sahai–Waters (GSW) Scheme

Before our work, we first review the GSW scheme and, then, summarize the safety of the scheme of Gentry et al. [4].We review the algorithms which make up the GSW scheme [4]. These algorithms were originally defined based on functions BitDecomp, BitDecomp−1, and Flatten, but the ideas from [19, 27] borrowed into this paper are defined using tool matrix G. Let λ be the security parameter and L be the number of levels of homomorphic encryption.GSW.Setup1λ,1L:(1)
Select a moduleq of bit K=mathcalKλ,L, error distribution χ=χλ,L on the parameter n=nλ,L∈ℕ and ℤ, so that the q,n,χ−LWE problem is at least 2λ secure for known attacks. Choose a parameter m=mλ,L=Onlogq.(2)
Output:params=n,q,χ,m. We express l=⌊logq⌋+1 and N=n+1⋅l.GSW.KeyGenparams:(1)
Selectt=t1,…,tnT⟵ℤqn and calculate(18)s⟵1,−tTT=1,−t1,…,−tnT∈ℤqn+1×1.(2)
Generate a matrixB⟵ℤqmm×n and a vector e⟵χm.(3)
Calculateb=Bt+e∈ℤqm and construct matrix A=bB∈ℤqm×n+1. Obviously, we observed.(4)
Return tosk⟵s and pk⟵A.GSW.Encparams,pk,μ: in order to encrypt a single-bit message μ∈0,1,(1)
LetG be the abovementioned matrix n+1×N(2)
Select a matrixR⟵0,1m×N evenly(3)
Calculate(19)C=μG+ATRmodq∈ℤqn+1×NIn the original GSW scheme,FlattenμI+BitDecompRA∈0,1N×N, where I is an identity matrix.GSW.Decparams,sk,C:(1)
We havesk=s∈ℤqn+1.(2)
LetI meet q/4<2I−1≤q/2. Let CI be column I of C.(3)
Calculatex⟵CI,smodq within the scope of −q/2,q/2; note CI,s=CITs and(20)CTs=μGTs+RTAs=μ1,2,4,…T+RTe.From that mentioned above, it can be seen that columnI of the ciphertext matrix C selected in the calculation corresponds to coordinate I of the vector CI,s, i.e. μ2I−1+RITe.(4)
Outputμ′=⌊x/2I−1⌋.So, if it isx<2I−2≤q/4, then it returns to 0, and if it is x>2I−2, then it returns to 1.GSW.Evalparams,C1,…,Cl:GSW.MultC1,C2: calculate and output(21)C1G−1C2=μ1G+ATR1G−1C2=μ1C2+ATR1G−1C2=ATR1G−1C2+μ1R2+μ1μ2Gmodq.GSW.AddC1,C2∈ℤqn+1×N: output(22)C1+C2=μ1+μ2G+ATR1+R2.Note thatC1G−1C2∈ℤqn+1×N. In addition, use G−C1G−1C2 to calculate homomorphic NAND gates.Note 3.
Note that, in [19], the decryption algorithm is to select a suitable vector w and calculate sCG−1wT. It is much less efficient than the original one (all about calculation time and error item size). So, we used the GSW decryption algorithm in our scheme.
Whenq is a power of 2, there is also a variant of the message in ℤq. See more details in [4].


### 3.1. Security

A brief proof of the following theorem is given in [4].Theorem 1.
Letn,q,χ be public parameter so that the LWEn,q,χ hypothesis is true, and let m=Onlogq. Then, we can say that the GSW scheme is IND−CPA safe.
The most important step of the proof is to prove thatA,RA and the uniform distribution is computational indistinguishable.Note 4.
The correctness of the GSW scheme is obtained by analyzing the scale of the noise during encryption, decryption, and homomorphism. Always ensure that the maximum noise level in the abovementioned process is still less than 1/4, which can be decrypted correctly. This work is not the focus of this paper, so it will not be repeated. See more details [4].


## 3.1. Security

A brief proof of the following theorem is given in [4].Theorem 1.
Letn,q,χ be public parameter so that the LWEn,q,χ hypothesis is true, and let m=Onlogq. Then, we can say that the GSW scheme is IND−CPA safe.
The most important step of the proof is to prove thatA,RA and the uniform distribution is computational indistinguishable.Note 4.
The correctness of the GSW scheme is obtained by analyzing the scale of the noise during encryption, decryption, and homomorphism. Always ensure that the maximum noise level in the abovementioned process is still less than 1/4, which can be decrypted correctly. This work is not the focus of this paper, so it will not be repeated. See more details [4].


## 4. Message-Encapsulation FHE

### 4.1. Message-Encapsulation FHE (MFHE Scheme)

Now, we introduce our MFHE scheme as follows: a message-encapsulation public-key encryption scheme based on the difficulty of the LWE hypothesis. We give the security parameterλ, set t to be the private keys number, and then, can encrypt the t-bit messages at one time.Letq=qλ be an integer, and let χ=χλ be a distribution set on ℤ. The definition of the variant of the GSW scheme is similar to the cryptosystem proposed in [19, 27, 28]. More specifically,params⟵MFHE.Setup1λ,1L:(1)
In particular, we first select the moduloq=qλ, and the dimension of lattice n=nλ,L. We appropriately select the error distribution for χ=χλ,L for 2λ security against known LWE attacks, Finally, we select the parameter m=mλ,L=Onlogq and a parameter t=Ologn.(2)
Letl=⌊logq⌋+1 and N=n+t⋯l, and then, output params=n,q,χ,m,t.pk,sk⟵MFHE.KeyGenparams:(1)
Fori∈t, select tiT=ti,1,…,ti,n from ℤq1×n and output(23)ski≔si=Ii∣−tiTT=0,…,1,…,0−ti,1,…,−ti,nT∈ℤqn+t×1,thei position of which is 1.(2)
Select a matrixB⟵ℤqm×n and t vectors ei⟵χm×1, i∈t evenly, and then, calculate bi=B⋅ti+eimodq and output(24)pk=P=b1⋯btB∈ℤqm×n+t,where the size ofpk is Onm⋅log2q. In addition, we observed that P⋅si=eimodq.(3)
Outputpk⟵P and sk⟵S≔s1,…,st. It is worth noting that P⋅S=e1,…,etmodq.C⟵MFHE.Encparams,pk,M:(1)
To encryptt-bit μi∈0,1, μi∈0,1, embed the t bits into a t×t-dimension matrix first, U=diagμ1,1,…,μt,t∈0,1t×t, where μi,j=0, i≠j, and j∈t. Later, for simplicity, μi,j will be abbreviated as μi, and the message matrix is constructed using a plaintext matrix U.(25)M=Ut×t0t×n0n×tEn×n∈0,1n+t×n+t,whereU is a random diagonal matrix, and note that E is a n×n-dimensional matrix.(2)
Then, select a uniform matrixR⟵0,1m×N. Calculate and output cipher text:(26)C=M⋅G+PT⋅Rmodq∈ℤqn+t×N.Now, we propose a decryption algorithm for the MFHE scheme which allows us to recover all the message bits at the one time.U⟵MFHE.Decparams,pk,C:(1)
First, assume that the user has a private key matrixS=s1,…,st∈ℤqn+t×t as follows:(27)S≔s1,…,st=1⋯0⋮⋱⋮0⋯1−t1,1⋯−tt,1⋮⋱⋮−t1,n⋯−tt,n.What needs to be noted here is(28)P⋅S=b1−Bt1,…,bt−Bbt=e1,…,etmod∈ℤqm×t.Therefore, it is easy for us to get the bound ofP⋅S which is less than or equal to te, i.e. P⋅S≤te.(2)
Define the matrixWℤqt×+t as follows:(29)WT≔q2⋯0⋮⋱⋮0⋯q20⋯0⋮⋱⋮0⋯0.(3)
Calculate and output(30)Vi,j=S,C⋅G−1WTmodq∈ℤqt×t.Among them, we haveS,C∈ℤqt×t, i.e.,(31)S,C=STPTR+STMG=e1,…,etTR+STMGmodq.(4)
Finally, use the results mentioned above to output the complete messageU=⌊Vi,j/q/2⌋∈0,1t×t.MFHE.Evalparams,C1,…,Cl:there are two algorithms, which are, homomorphic addition and homomorphic multiplication. For any two plaintext matrices U1,U2∈0,1t×t, we get the ciphertext separately.(32)C1=M1⋅G+PT⋅R1,C2=M2⋅G+PT⋅R2.Therefore, the homomorphic addition and multiplication are as follows:MFHE.MultC1,C2∈ℤqn+t×N: output(33)C1G−1C2=M1G+PTR1⋅G−1C2=PTR1G−1C2+M1PTR2+M1M2Gmodq.MFHE.AddC1,C2∈ℤqn+t×N:outputC1+C2=M1+M2G+PTR1+R2.Here, we can calculate a homomorphic NAND gate from the output.Note 5.
Generally, we can choose different private keysski to decrypt column j of the ciphertext Cj bit-by-bit and get the i bit message of Cj, that is, we can get the bit in row i and column j under the i private key. However, it is actually possible to recover the entire message using the private key matrix S based on the abovementioned decryption algorithm. We calculate Vi,j=STC⋅G−1WT as follows:(34)Vi,j=q2⋅U+e1TR⋮etTR⋅G−1WT∈ℤqt×t.
The magnitude of the noise can be simply calculated and verified to grow linearly compared to single-bit decryption algorithm.μi,j⟵MFHE.bitDecparams,ski,C,wj:(1)
Suppose we want to decrypt the bitμi,j of row i and column j, so let ski=si≔, then define a vector so that the position is, and the other positions are 0, j∈t.(35)wjT=0,…,q2j,…,0︸t0,…,0︸n.(2)
Fori,j to t, calculate(36)νi,j=siTC⋅G−1wjTmodq∈ℤq.The inner product ofsi,C equals to(37)siTPTR+siTMG=eiTR+siTMGmodqℤq1×N.(3)
Output a messageμi,j=⌊Vi,j/q/2⌋∈0,1, in which ⌊⋅⌋ represents the operation that rounds to the nearest integer. Therefore the value belongs to 0,1. 4. Finally, by repeating it t2 times, the entire message can be recovered. The bitDec algorithm here is similar to the algorithm in [2], which is achieved by recovering each element separately.Note 6.
It should be noted here that due to the structural characteristics of the public key in our scheme, accurate decryption is achieved by dynamically adjusting the position ofq/2 in the vector w. That is, dot-multiply siTC and G−1wj to obtain the bits of the row and column of the plaintext matrix.
We can get all the bits of the message by using thebitDec decryption algorithm and appropriate private key.Note 7.
It can be seen that our message-encapsulation GSW scheme is to implementt×t-bit homomorphic addition. However, since the i,j element of U1×U2 is not a product of μ1i,j×μ2i,j, only t-bit homomorphic multiplication is supported.


### 4.2. Correctness Analysis

Next, we analyze the correctness of the MFHE scheme.Definition 11.
We call the message matrixU∈ℤqt×t which is obtained by decrypting the ciphertext under t different private keys si,i∈t (see (2)). The noise of a single-bit message is as follows:(38)noisesi,M=siTC−siTMG=siTPTR=eiTR.
For flexible single-bit decryption algorithmbitDec, we represent the noise vector as noise∈ℤq1×N. For simplicity, we abbreviate noisesi,MC to noisesi when M and C do not affect the contextual understanding.
Note that, in our setup, due to the structure of the new public key,noisesi is the noise of row i of the plaintext matrix U, not the single-bit noise.Lemma 4.
Obviously, using Definition 4.1, for convenience, for a decryption algorithmDec, if the noise meets(39)NoiseS,MC=ST⋅PT⋅R=noises1⋮noisestmodq,where S=s1,…,st is a one-time private key matrix, we can represent the entire noise matrix as(40)NoiseS,MC=noises1,…,noisestT∈ℤqt×N.
For convenience, we will abbreviateNoiseS,MC as NoiseS when M and C do not affect the contextual understanding.
In order to analyze the correctness, for convenience, we first define the following noise ciphertext concept.Definition 12.
(E-Noise Ciphertext). A ciphertext matrix C∈ℤqm+1×N with E noise, which makes in a private key si∈ℤqn+t×1, for a corresponding message M,si,C=siT⋅M⋅G+eiT⋅R. Then, let the norm of noisesi be(41)noisesi≤eiTR≤eiT2⋅R∞≤N⋅2mB≤E.Lemma 5.
For a one-time private key matrixS∈ℤqn+t×t, we can get NoiseS=e1,…,etT⋅R when we run the Dec algorithm. So, in this case, we get(42)NoiseS≤t⋅noisesi≤t⋅E.Lemma 6.
For a plaintext matrixU (a combination of M) and a private key si,i∈t, the noise vector of the ciphertext C meets(43)tnoisesi=NoiseS.
In the following, we analyze the correctness of the decryption.Lemma 7.
LetC be an E noise encryption of M. If we can recover μi,j (an element of U) from the ciphertext C under the private key si, then there is(44)μi,j≔si,C⋅G−1wjT=noisesi+siTMG⋅G−1wjT,so that(45)noisesi⋅G−1wjT∞≤noisesi⋅G−1wjT≤N⋅E<q8.Proof.
Obviously, by using Lemma 4.2 we can simply prove Lemma 4.7, and we will not go into details here.Lemma 8.
LetC be an E noise encryption in M. If we can recover all U from the ciphertext C, then there is a private key matrix S such that(46)V=S,C⋅G−1WT=NoiseS+STMG⋅G−1WT,where NoiseSS⋅G−1WT∞≤N⋅tE<q/8.Proof.
This proof can be obtained directly from Lemma 4.2 and Lemma 4.7. Now, we know that as long asNoiseS⋅G−1WT∞≤q/8, the decryption runs correctly, i.e., E<q/4tN. Therefore, we call the value E=q/4tN as the bound of noise.
The analysis of the homomorphic operation is given in the following. Before introducing the boundary of noise, the following notes are given.Note 8.
For the convenience of reading, letϒC1≔NoiseS,M1C1 and ϒC2≔NoiseSS,M2C2.Lemma 9.
(See [8]). The boundary of the noise of homomorphic addition, homomorphic multiplication, and homomorphic negative is as follows:Addition: forM1,M2∈0,1n+t×n+t, the following condition is met:(47)NoiseS,M1+M2C1+C2≤ΥC1+ΥC2.Multiplication: forM1,M2, the following condition is met:(48)NoiseS,M1⋅M2C1G−1C2≤U12⋅ϒC2∞+G−1C2∞⋅ϒC1∞.NAND: forM, the following condition is met:(49)NoiseS,MG−C=NoiseS,MC.Proof.
LetS∈ℤn+t×t be a private key matrix. Let C1,C2∈ℤqm+1×N be the ciphertext of the encrypted message M1,M2∈0,1n+t×n+t separately. Then,Homomorphic addition, that is, add ciphertext and ciphertextCAdd=C1+C2modq, so that(50)S,CAdd=NoiseSS,M1+M2+ST⋅MAdd⋅G.WhereMAdd=M1+M2 and the noise is(51)NoiseS,M1+M2=NoiseS,M1+NoiseS,M2.Obviously, the noise ist⋅E1+E2.Homomorphic multiplication: that is, multiply the ciphertext and ciphertextCMult=C1G−1C2∈ℤqn+t×N, so that(52)CMult=M1M2G+PTR1G−1C2+M1PTR2.Then, we haveS,CMult which equals to(53)STM1M2G+PTR1G−1C2+M1PTR2.For convenience, we first set the noise to(54)NoiseS,M1M2=STPTR1G−1C2+M1PTR2.Obviously, according to Lemma 4.2, there is(55)ΥC1=STPTR1≤e1,…,etT⋅R1≤tE1,andC2 is a n+t×N binary matrix (G−1∈ℤqN×n+t). Therefore, in this case,(56)STPTR1⋅G−1C2≤tE2⋅G−1C2≤N⋅tE2exists. Also, pay attention to that(57)ST⋅M1PT=uib1T−tiTBT⋮uibtT−tiTBT.The boundary of (ui⋅biT−tiT⋅BT) is eiT. Therefore,(58)ST⋅M1PT≤e1T,…,etTT≤maxieiT.In this case, we can easily get the boundaryΥC2≔ST⋅M1PTR2≤eiTR≤E2. In other words, U12⋅ΥC2∞≤t⋅E2. Therefore, we have NoiseSS,M1⋅M2C1G−1C2≤NtE2+tE2, and the ciphertext CMult is Nt+r⋅E noisy.NAND gate: the same operation is true for the NAND gate, and output matrix product isG−C1G−1C2. Consider a Boolean circuit whose computational depth is L while containing NAND gates. It takes the new ciphertext as input, that is, the E noise ciphertext, the noise multiplied by a factor which is at most Nt+t at each level, that is, the norm of the error element increases by a factor which is, at most, Nt+t. Therefore, the wrong element norm of the final ciphertext is bounded as Efinal=Nt+tL⋅E.
In order to ensure the correctness of the decryption,Efinal≤⌊q/2⌋/4 needs to be true. That is to say, the inequality Nt+tL⋅E≤⌊q/2⌋/4 must be true, which is guaranteed by the parameters we choose. The proof is completed.


### 4.3.IND−CPA Security Analysis

In the following, we use Theorem 4.1 to prove that the message-encapsulation GSW scheme based on the LWE assumption that it isIND−CPA safe and that the scheme is indistinguishable from the original GSW scheme [4].Theorem 2.
Letm>n∈ℕ,q∈ℕ and χ be a discrete Gaussian distribution on ℤ, which makes the n,q,χ,m−LWE problem difficult. Let t be an integer that makes t=Ologn true. Define two distributions X and Y as follows:X is a distribution on the m×t+n matrix b1⋯btB. Among them, B∈ℤqm×n is uniformly selected, for all 1≤i≤t, bi=Bti+eimodq, in which ti are uniformly selected from ℤqn, and ei is selected from a discrete Gaussian distribution χ.Y is evenly distributed on ℤqm×t+n.
Therefore, the distributionX and Y is computational indistinguishable.Theorem 3.
Letparams=n,q,χ,m,t so that the assumption LWEn,q,χ,m is true and m=Onlogq. Then, the MFHE scheme is IND−CPA safe.Proof.
The proof of security contains two steps:First, we use Theorem 4.11 to prove that, under theLWE assumption, the matrix P=b1,…,bt,B∈ℤqm×n+t and the randomly chosen matrix are computationally indistinguishableThen, using the Left-over Hash Lemma, a uniform random valueC′ can be used to replace the ciphertext C=MG+PTR, that is, PT⋅R is indistinguishable from the uniform distribution
The brief proof is over. See more details in [4].


## 4.1. Message-Encapsulation FHE (MFHE Scheme)

Now, we introduce our MFHE scheme as follows: a message-encapsulation public-key encryption scheme based on the difficulty of the LWE hypothesis. We give the security parameterλ, set t to be the private keys number, and then, can encrypt the t-bit messages at one time.Letq=qλ be an integer, and let χ=χλ be a distribution set on ℤ. The definition of the variant of the GSW scheme is similar to the cryptosystem proposed in [19, 27, 28]. More specifically,params⟵MFHE.Setup1λ,1L:(1)
In particular, we first select the moduloq=qλ, and the dimension of lattice n=nλ,L. We appropriately select the error distribution for χ=χλ,L for 2λ security against known LWE attacks, Finally, we select the parameter m=mλ,L=Onlogq and a parameter t=Ologn.(2)
Letl=⌊logq⌋+1 and N=n+t⋯l, and then, output params=n,q,χ,m,t.pk,sk⟵MFHE.KeyGenparams:(1)
Fori∈t, select tiT=ti,1,…,ti,n from ℤq1×n and output(23)ski≔si=Ii∣−tiTT=0,…,1,…,0−ti,1,…,−ti,nT∈ℤqn+t×1,thei position of which is 1.(2)
Select a matrixB⟵ℤqm×n and t vectors ei⟵χm×1, i∈t evenly, and then, calculate bi=B⋅ti+eimodq and output(24)pk=P=b1⋯btB∈ℤqm×n+t,where the size ofpk is Onm⋅log2q. In addition, we observed that P⋅si=eimodq.(3)
Outputpk⟵P and sk⟵S≔s1,…,st. It is worth noting that P⋅S=e1,…,etmodq.C⟵MFHE.Encparams,pk,M:(1)
To encryptt-bit μi∈0,1, μi∈0,1, embed the t bits into a t×t-dimension matrix first, U=diagμ1,1,…,μt,t∈0,1t×t, where μi,j=0, i≠j, and j∈t. Later, for simplicity, μi,j will be abbreviated as μi, and the message matrix is constructed using a plaintext matrix U.(25)M=Ut×t0t×n0n×tEn×n∈0,1n+t×n+t,whereU is a random diagonal matrix, and note that E is a n×n-dimensional matrix.(2)
Then, select a uniform matrixR⟵0,1m×N. Calculate and output cipher text:(26)C=M⋅G+PT⋅Rmodq∈ℤqn+t×N.Now, we propose a decryption algorithm for the MFHE scheme which allows us to recover all the message bits at the one time.U⟵MFHE.Decparams,pk,C:(1)
First, assume that the user has a private key matrixS=s1,…,st∈ℤqn+t×t as follows:(27)S≔s1,…,st=1⋯0⋮⋱⋮0⋯1−t1,1⋯−tt,1⋮⋱⋮−t1,n⋯−tt,n.What needs to be noted here is(28)P⋅S=b1−Bt1,…,bt−Bbt=e1,…,etmod∈ℤqm×t.Therefore, it is easy for us to get the bound ofP⋅S which is less than or equal to te, i.e. P⋅S≤te.(2)
Define the matrixWℤqt×+t as follows:(29)WT≔q2⋯0⋮⋱⋮0⋯q20⋯0⋮⋱⋮0⋯0.(3)
Calculate and output(30)Vi,j=S,C⋅G−1WTmodq∈ℤqt×t.Among them, we haveS,C∈ℤqt×t, i.e.,(31)S,C=STPTR+STMG=e1,…,etTR+STMGmodq.(4)
Finally, use the results mentioned above to output the complete messageU=⌊Vi,j/q/2⌋∈0,1t×t.MFHE.Evalparams,C1,…,Cl:there are two algorithms, which are, homomorphic addition and homomorphic multiplication. For any two plaintext matrices U1,U2∈0,1t×t, we get the ciphertext separately.(32)C1=M1⋅G+PT⋅R1,C2=M2⋅G+PT⋅R2.Therefore, the homomorphic addition and multiplication are as follows:MFHE.MultC1,C2∈ℤqn+t×N: output(33)C1G−1C2=M1G+PTR1⋅G−1C2=PTR1G−1C2+M1PTR2+M1M2Gmodq.MFHE.AddC1,C2∈ℤqn+t×N:outputC1+C2=M1+M2G+PTR1+R2.Here, we can calculate a homomorphic NAND gate from the output.Note 5.
Generally, we can choose different private keysski to decrypt column j of the ciphertext Cj bit-by-bit and get the i bit message of Cj, that is, we can get the bit in row i and column j under the i private key. However, it is actually possible to recover the entire message using the private key matrix S based on the abovementioned decryption algorithm. We calculate Vi,j=STC⋅G−1WT as follows:(34)Vi,j=q2⋅U+e1TR⋮etTR⋅G−1WT∈ℤqt×t.
The magnitude of the noise can be simply calculated and verified to grow linearly compared to single-bit decryption algorithm.μi,j⟵MFHE.bitDecparams,ski,C,wj:(1)
Suppose we want to decrypt the bitμi,j of row i and column j, so let ski=si≔, then define a vector so that the position is, and the other positions are 0, j∈t.(35)wjT=0,…,q2j,…,0︸t0,…,0︸n.(2)
Fori,j to t, calculate(36)νi,j=siTC⋅G−1wjTmodq∈ℤq.The inner product ofsi,C equals to(37)siTPTR+siTMG=eiTR+siTMGmodqℤq1×N.(3)
Output a messageμi,j=⌊Vi,j/q/2⌋∈0,1, in which ⌊⋅⌋ represents the operation that rounds to the nearest integer. Therefore the value belongs to 0,1. 4. Finally, by repeating it t2 times, the entire message can be recovered. The bitDec algorithm here is similar to the algorithm in [2], which is achieved by recovering each element separately.Note 6.
It should be noted here that due to the structural characteristics of the public key in our scheme, accurate decryption is achieved by dynamically adjusting the position ofq/2 in the vector w. That is, dot-multiply siTC and G−1wj to obtain the bits of the row and column of the plaintext matrix.
We can get all the bits of the message by using thebitDec decryption algorithm and appropriate private key.Note 7.
It can be seen that our message-encapsulation GSW scheme is to implementt×t-bit homomorphic addition. However, since the i,j element of U1×U2 is not a product of μ1i,j×μ2i,j, only t-bit homomorphic multiplication is supported.


## 4.2. Correctness Analysis

Next, we analyze the correctness of the MFHE scheme.Definition 11.
We call the message matrixU∈ℤqt×t which is obtained by decrypting the ciphertext under t different private keys si,i∈t (see (2)). The noise of a single-bit message is as follows:(38)noisesi,M=siTC−siTMG=siTPTR=eiTR.
For flexible single-bit decryption algorithmbitDec, we represent the noise vector as noise∈ℤq1×N. For simplicity, we abbreviate noisesi,MC to noisesi when M and C do not affect the contextual understanding.
Note that, in our setup, due to the structure of the new public key,noisesi is the noise of row i of the plaintext matrix U, not the single-bit noise.Lemma 4.
Obviously, using Definition 4.1, for convenience, for a decryption algorithmDec, if the noise meets(39)NoiseS,MC=ST⋅PT⋅R=noises1⋮noisestmodq,where S=s1,…,st is a one-time private key matrix, we can represent the entire noise matrix as(40)NoiseS,MC=noises1,…,noisestT∈ℤqt×N.
For convenience, we will abbreviateNoiseS,MC as NoiseS when M and C do not affect the contextual understanding.
In order to analyze the correctness, for convenience, we first define the following noise ciphertext concept.Definition 12.
(E-Noise Ciphertext). A ciphertext matrix C∈ℤqm+1×N with E noise, which makes in a private key si∈ℤqn+t×1, for a corresponding message M,si,C=siT⋅M⋅G+eiT⋅R. Then, let the norm of noisesi be(41)noisesi≤eiTR≤eiT2⋅R∞≤N⋅2mB≤E.Lemma 5.
For a one-time private key matrixS∈ℤqn+t×t, we can get NoiseS=e1,…,etT⋅R when we run the Dec algorithm. So, in this case, we get(42)NoiseS≤t⋅noisesi≤t⋅E.Lemma 6.
For a plaintext matrixU (a combination of M) and a private key si,i∈t, the noise vector of the ciphertext C meets(43)tnoisesi=NoiseS.
In the following, we analyze the correctness of the decryption.Lemma 7.
LetC be an E noise encryption of M. If we can recover μi,j (an element of U) from the ciphertext C under the private key si, then there is(44)μi,j≔si,C⋅G−1wjT=noisesi+siTMG⋅G−1wjT,so that(45)noisesi⋅G−1wjT∞≤noisesi⋅G−1wjT≤N⋅E<q8.Proof.
Obviously, by using Lemma 4.2 we can simply prove Lemma 4.7, and we will not go into details here.Lemma 8.
LetC be an E noise encryption in M. If we can recover all U from the ciphertext C, then there is a private key matrix S such that(46)V=S,C⋅G−1WT=NoiseS+STMG⋅G−1WT,where NoiseSS⋅G−1WT∞≤N⋅tE<q/8.Proof.
This proof can be obtained directly from Lemma 4.2 and Lemma 4.7. Now, we know that as long asNoiseS⋅G−1WT∞≤q/8, the decryption runs correctly, i.e., E<q/4tN. Therefore, we call the value E=q/4tN as the bound of noise.
The analysis of the homomorphic operation is given in the following. Before introducing the boundary of noise, the following notes are given.Note 8.
For the convenience of reading, letϒC1≔NoiseS,M1C1 and ϒC2≔NoiseSS,M2C2.Lemma 9.
(See [8]). The boundary of the noise of homomorphic addition, homomorphic multiplication, and homomorphic negative is as follows:Addition: forM1,M2∈0,1n+t×n+t, the following condition is met:(47)NoiseS,M1+M2C1+C2≤ΥC1+ΥC2.Multiplication: forM1,M2, the following condition is met:(48)NoiseS,M1⋅M2C1G−1C2≤U12⋅ϒC2∞+G−1C2∞⋅ϒC1∞.NAND: forM, the following condition is met:(49)NoiseS,MG−C=NoiseS,MC.Proof.
LetS∈ℤn+t×t be a private key matrix. Let C1,C2∈ℤqm+1×N be the ciphertext of the encrypted message M1,M2∈0,1n+t×n+t separately. Then,Homomorphic addition, that is, add ciphertext and ciphertextCAdd=C1+C2modq, so that(50)S,CAdd=NoiseSS,M1+M2+ST⋅MAdd⋅G.WhereMAdd=M1+M2 and the noise is(51)NoiseS,M1+M2=NoiseS,M1+NoiseS,M2.Obviously, the noise ist⋅E1+E2.Homomorphic multiplication: that is, multiply the ciphertext and ciphertextCMult=C1G−1C2∈ℤqn+t×N, so that(52)CMult=M1M2G+PTR1G−1C2+M1PTR2.Then, we haveS,CMult which equals to(53)STM1M2G+PTR1G−1C2+M1PTR2.For convenience, we first set the noise to(54)NoiseS,M1M2=STPTR1G−1C2+M1PTR2.Obviously, according to Lemma 4.2, there is(55)ΥC1=STPTR1≤e1,…,etT⋅R1≤tE1,andC2 is a n+t×N binary matrix (G−1∈ℤqN×n+t). Therefore, in this case,(56)STPTR1⋅G−1C2≤tE2⋅G−1C2≤N⋅tE2exists. Also, pay attention to that(57)ST⋅M1PT=uib1T−tiTBT⋮uibtT−tiTBT.The boundary of (ui⋅biT−tiT⋅BT) is eiT. Therefore,(58)ST⋅M1PT≤e1T,…,etTT≤maxieiT.In this case, we can easily get the boundaryΥC2≔ST⋅M1PTR2≤eiTR≤E2. In other words, U12⋅ΥC2∞≤t⋅E2. Therefore, we have NoiseSS,M1⋅M2C1G−1C2≤NtE2+tE2, and the ciphertext CMult is Nt+r⋅E noisy.NAND gate: the same operation is true for the NAND gate, and output matrix product isG−C1G−1C2. Consider a Boolean circuit whose computational depth is L while containing NAND gates. It takes the new ciphertext as input, that is, the E noise ciphertext, the noise multiplied by a factor which is at most Nt+t at each level, that is, the norm of the error element increases by a factor which is, at most, Nt+t. Therefore, the wrong element norm of the final ciphertext is bounded as Efinal=Nt+tL⋅E.
In order to ensure the correctness of the decryption,Efinal≤⌊q/2⌋/4 needs to be true. That is to say, the inequality Nt+tL⋅E≤⌊q/2⌋/4 must be true, which is guaranteed by the parameters we choose. The proof is completed.


## 4.3.IND−CPA Security Analysis

In the following, we use Theorem 4.1 to prove that the message-encapsulation GSW scheme based on the LWE assumption that it isIND−CPA safe and that the scheme is indistinguishable from the original GSW scheme [4].Theorem 2.
Letm>n∈ℕ,q∈ℕ and χ be a discrete Gaussian distribution on ℤ, which makes the n,q,χ,m−LWE problem difficult. Let t be an integer that makes t=Ologn true. Define two distributions X and Y as follows:X is a distribution on the m×t+n matrix b1⋯btB. Among them, B∈ℤqm×n is uniformly selected, for all 1≤i≤t, bi=Bti+eimodq, in which ti are uniformly selected from ℤqn, and ei is selected from a discrete Gaussian distribution χ.Y is evenly distributed on ℤqm×t+n.
Therefore, the distributionX and Y is computational indistinguishable.Theorem 3.
Letparams=n,q,χ,m,t so that the assumption LWEn,q,χ,m is true and m=Onlogq. Then, the MFHE scheme is IND−CPA safe.Proof.
The proof of security contains two steps:First, we use Theorem 4.11 to prove that, under theLWE assumption, the matrix P=b1,…,bt,B∈ℤqm×n+t and the randomly chosen matrix are computationally indistinguishableThen, using the Left-over Hash Lemma, a uniform random valueC′ can be used to replace the ciphertext C=MG+PTR, that is, PT⋅R is indistinguishable from the uniform distribution
The brief proof is over. See more details in [4].


## 5. Conclusions

In this paper, we construct an efficient message-encapsulation FHE scheme. The scheme can achieve the decryption at one time and can also flexibly decrypt bit-by-bit. In Table1, we give a comparison of the parameters of this scheme with the existing schemes. It can be seen from the comparison that compared with the previous ones, the scheme keeps the key length substantially, and this scheme is based on more conventional assumptions and, meanwhile, reduces the ciphertext length to some extent. The proposal of this scheme makes the full homomorphic encryption take a big step from theoretical research to large-scale application. It is conducive to greatly improving the efficiency of encrypted data processing (such as retrieval and operation) in the Internet of things, saving the energy consumption of nodes in the Internet of Things, and ensuring that the data are not statistically analyzed, which has a better application scenario [29–31].Table 1
Comparison of the related works.
UnderlyingHAOOurs-MFHELMDO[AssumptionLWELWEdual-LWE‖msg‖ttt‖pk‖OmnlogqOnmlogqOmnlogq‖sk‖OntlogqOntlogqOntlogq‖ct‖OnNlogqOnNlogqOnN′logqflexibledec√√√one−timedec×√√_‖msg‖: message length_N:n+tl_‖ct‖: cipher text length_N′:m+tlIn addition, there are many interesting open issues that may be resolved in the future. For example, our thinking has certain reference value for enhancing big data security and constructing a message-encapsulated casual transmission protocol, but it also has certain challenges.



---

*Source: 8862920-2020-10-14.xml*