Achieving Message-Encapsulated Leveled FHE for IoT Privacy Protection

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.

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]], 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.

Firstly, the public key of the Message-encapsulation Fully Homomorphic Encryption scheme of Hiromasa et al. [[2]] is as follows:

$$\begin{array}{}\text{(1)}& \left(\mathbf{B}≔\mathbf{A}\cdot \mathbf{T}+\mathbf{E}\left(\mathrm{mod}q\right)\left|\mathbf{A}\right.\right)\in {\mathbb{Z}}_q^{m\times t}\times {\mathbb{Z}}_q^{m\times n}.\end{array}$$

Among them are the secret matrix $\mathbf{T}⟵{\mathbb{Z}}_q^{n\times t}$ and the noise matrix $\mathbf{E}⟵{\chi }^{m\times 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:

$$\begin{array}{}\text{(2)}& \left(\mathbf{A}\cdot {\mathbf{e}}_1,...,\mathbf{A}\cdot {\mathbf{e}}_t\left|\mathbf{A}\right.\right)\in {\mathbb{Z}}_q^{m\times t}\times {\mathbb{Z}}_q^{m\times n}.\end{array}$$

Among them, there is ${\mathbf{e}}_1,...,\mathbf{A}\cdot {\mathbf{e}}_t⟵{\chi }^{n\times 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 $m\left(m\ge n\log q\right)$ 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], [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:

$$\begin{array}{}\text{(3)}& {\mathbf{A}}^{\prime }=\left[{\mathbf{b}}_1,...,{\mathbf{b}}_t\left|\mathbf{A}\right.\right]\in {\mathbb{Z}}_q^{m\times \left(n+t\right)}.\end{array}$$

• Among them, ${\mathbf{b}}_1=\mathbf{A}\cdot {\mathbf{t}}_i+e_i\left(\mathrm{mod}q\right)$ and $i\in \left[t\right]$ is an LWE instance. This is significantly different from existing message-encapsulation PKE schemes (for example, [[14]]) and message-encapsulation FHE schemes (for example, [[1]]) and is also the fundamental difference between other schemes and the FHE scheme constructed in this paper. Private keys corresponding to the public key $\left[{\mathbf{b}}_1,...,{\mathbf{b}}_t\right]\left|\mathbf{A}\right.$ is shaped as follows:

$$\begin{array}{}\text{(4)}& \mathbf{s}{\mathbf{k}}_i≔\left[0,...,1,...,0\left|{\mathbf{t}}_i\right.\right]\in {\mathbb{Z}}_q^{1\times \left(n+t\right)},i\in \left[t\right].\end{array}$$

• (2) Next, we use the public key matrix ${\mathbf{A}}^{\prime }$ 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,

$$\begin{array}{}\text{(5)}& \mathbf{M}≔\text{diag}\left(\left.m_1,...,m_t\right|1,...,1\right)\in {\mathbb{Z}}_q^{\left(n+t\right)\times \left(n+t\right)},\end{array}$$

and while constructing a private key matrix with private keys,

$$\begin{array}{}\text{(6)}& \mathbf{S}≔\left[\left.\mathbf{E}\right|\left(\begin{array}{c}{t}_1\\ ⋮\\ t_t\end{array}\right)\right]\in {\mathbb{Z}}_q^{\left(n+t\right)\times \left(n+t\right)}.\end{array}$$

$\mathbf{E}\left(n\times n\right)$ is the identity matrix, and we can get

$$\begin{array}{}\text{(7)}& \mathbf{S}\cdot \mathbf{M}≔\left[\left.\text{diag}\left(m_1,...,m_t\right)\right|\left(\begin{array}{c}{t}_1\\ ⋮\\ t_t\end{array}\right)\right].\end{array}$$

Finally, using the matrix $\mathbf{W}≔\left[\text{diag}\left(\lfloor \left(q/2\right)\rfloor ,...,\lfloor \left(q/2\right)\rfloor \right)\left|0\right.\right]$ we constructed, calculation of $\mathbf{S}\mathbf{M}\cdot GG-1\left(W\right)$ can directly recover the message vector $\left(m_1,...,m_t\right)$ . See Section 4 for a detailed analysis.

The rest of this paper is organized as follows. In Section 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.

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

For $n\in \mathbb{N}$ , we use $\left[n\right]$ to represent aggregation $\left\{1,...,n\right\}$ . For a real number $x\in ℝ$ , we use $\lfloor x\rfloor$ to represent the largest integer that is not greater than $x$ , $\lfloor x\rfloor ≔\lfloor x+\left(1/2\right)\rfloor$ to represent the nearest integer to $x$ . We represent vectors in bold lowercase letters, for example, $\mathbf{x}$ , and the matrix in bold uppercase letters, for example, $\mathbf{A}$ . In addition, we use ${\mathbf{A}}_{i,j}$ to represent elements in ${\mathbf{A}}_{i,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 ${\approx }_c$ and ${\approx }_s$ . In addition to this, we also define ${‖\mathbf{v}‖}_{\infty }=\max \left\{\left|v_1\right|,...,\left|v_n\right|\right\}$ and $‖\mathbf{R}‖={\max }_i‖{\mathbf{r}}_i‖$ . For convenience, we use $‖v‖$ to represent its $l_2$ norm.

We need to use the following variant of the Left-over Hash Lemma (LHL) [[16]].

(Matrix-Vector LHL). Let $\lambda \in \mathbb{Z},n,q\in \mathbb{N},m\ge n\log q+2\lambda ,\mathbf{r}\stackrel{R}{⟵}{\left\{\mathrm{0,1}\right\}}^m$ and $\mathbf{y}\stackrel{R}{⟵}{\mathbb{Z}}_q^n$ . We select a uniform random matrix $\mathbf{A}\stackrel{R}{⟵}{\mathbb{Z}}_q^{m\times n}$ , and then, the statistical distance of the distribution $\left(\mathbf{A},{\mathbf{A}}^T\mathbf{r}\right)$ and $\left(\mathbf{A},\mathbf{y}\right)$ is as follows:

$$\begin{array}{}\text{(8)}& \Delta \left(\left(\mathbf{A},{\mathbf{A}}^T\cdot \mathbf{r}\right),\left(\mathbf{A},\mathbf{y}\right)\right)\le 2^{-\lambda }.\end{array}$$

LWEs is the main computational assumption that cryptosystems and our variants rely on.

(LWE Distribution). For safety parameters, let $n=n\left(\lambda \right)$ and $m=m\left(\lambda \right)$ be integers, let $\chi =\chi \left(\lambda \right)$ be the $\mathbb{Z}$ error distribution with the bound of $B=B\left(\lambda \right)$ , and let $q=q\left(\lambda \right)\ge 2$ be an integer modulo of any polynomial $p=p\left(\lambda \right)$ that meets $q\ge 2^p\cdot B$ . Then, we select a vector $\mathbf{s}\in {\mathbb{Z}}_q^{n\times 1}$ and call it a secret, the LWE distribution ${\mathcal{A}}_{s,\chi }$ in ${\mathbb{Z}}_q^n\times {\mathbb{Z}}_q$ is selected uniformly and randomly, and we select $\mathbf{e}⟵{\chi }^{m\times 1}$ and output $\left(\mathbf{A},\mathbf{b}=A\cdot s+e\left(\mathrm{mod}q\right)\right)$ .

There are two kinds of the LWE hypothesis: the search-LWE and the decision-LWE. The decision-LWE is defined as follows:

(Decision- ${\text{LWE}}_{n,q,\chi ,m}$ ). Assume an independent selected $\left(\mathbf{A},\mathbf{b}\right)\in {\mathbb{Z}}_q^{m\times n}\times {\mathbb{Z}}_q^{m\times 1}$ , which is selected according to one of the following distributions: (1) for ${\mathcal{A}}_{s,\chi }$ from a uniform and random $\mathbf{s}\in {\mathbb{Z}}_q^n$ (i.e., $\left\{\left(\mathbf{A},\mathbf{b}\right):\mathbf{A}⟵{\mathbb{Z}}_q^{m\times n},\mathbf{s}⟵{\mathbb{Z}}_q^{n\times 1},\mathbf{e}⟵{\chi }^{m\times 1},\mathbf{b}=\mathbf{A}\cdot s+e\left(\mathrm{mod}q\right)\right\}$ ) or (2) uniform distribution (i.e., $\left\{\left(\mathbf{A},\mathbf{b}\right):\mathbf{A}⟵{\mathbb{Z}}_q^{m\times n},\mathbf{b}⟵{\mathbb{Z}}_q^{m\times 1}\right\}$ ). The two distributions mentioned above are computable indistinguishable.

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.

In our structure, we need to analyze the behavior of choosing the wrong element from the Gaussian distribution.

(B Bounded [[3]]). A distribution $\chi =\chi \left(\lambda \right)$ on an integer if the following exists:

$$\begin{array}{}\text{(9)}& \underset{x\stackrel{\text{\$}}{⟵}\chi }{\mathrm{Pr}}\left[\left|x\right|\ge B\right]\le 2^{-\tilde{\Omega }\left(n\right)},\end{array}$$

and then, it is called $B$ -bound (represented as $\left|\chi \right|\le B$ ).

For the analysis of our scheme, the vector selected from the Gaussian distribution needs to have a certain bound on its norm.

(See [[20]]). 1. For $\forall k>0,\mathrm{Pr}\left[\left|e\right|>k\cdot \sigma ,e⟵D_{\sigma }^1\right]\le 2\cdot \exp \left(-\left(k^2/2\right)\right)$ ; 2. for $\forall k>0$ , there is $\mathrm{Pr}\left[‖\mathbf{e}‖>k\cdot \sigma \cdot \sqrt{m}\mathbf{e}⟵D_{\sigma }^m\right]\le k^m\cdot \exp \left(\left(m/2\right)\cdot \left(1-k^2\right)\right)$ Therefore, in this paper, we set $\left|e\right|\le B$ and $‖e‖\le 2\sqrt{m}B$ .

In this paper, we assume $\sigma \ge 2\sqrt{n}$ . So, if $\mathbf{e}⟵D_{\sigma }^m$ , then on average, $‖e‖\approx \sqrt{m}\cdot \sigma$ . It can be known from Lemma 2.2 (2) that there is a high possibility that $‖\mathbf{e}‖\le 2\sigma \sqrt{m}$ . Therefore, in this paper, we set $\left|e\right|\le B$ and $‖\mathbf{e}‖\le 2\sqrt{m}B$ .

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.

(See [[21]]). Let a fixed function $L=L\left(\lambda \right)$ be the level of Fully Homomorphic Encryption. For a kind of circuit ${\left\{{\mathcal{C}}_{\lambda }\right\}}_{\lambda \in N}$ , the L-FHE scheme includes four Probabilistic Polynomial Times (PPTs), and the algorithm is as follows:

$$\begin{array}{}\text{(10)}& \left(\text{KeyGen},\text{Enc},\text{Dec},\text{Eval}\right).\end{array}$$

• The key generation algorithm (KeyGen) is a randomization algorithm that inputs security parameters $1^{\lambda }$ and outputs public keys ( $\text{pk}$ ) and private keys ( $\text{sk}$ )
• The encryption algorithm Enc is a randomization algorithm that inputs a public key ( $\text{pk}$ ) and a message $m\in {\left\{\mathrm{0,1}\right\}}^{\ast }$ and outputs a ciphertext $c$
• The decryption algorithm Dec is a deterministic algorithm that inputs the private key $\text{sk}$ and ciphertext and outputs the decrypted message $m\in {\left\{\mathrm{0,1}\right\}}^{\ast }$
• The homomorphic algorithm Eval inputs a public key $\text{pk}$ , a circuit $C\in {\mathcal{C}}_{\lambda }$ , and a sequence of ciphertexts $c_1,...,c_{\ell \left(\lambda \right)}$ , here let $\ell \left(\lambda \right)$ be a polynomial related to $\lambda$ the and outputs the computed ciphertext $c^{\mathrm{\star }}$
• The correctness requirements are as follows:
• For arbitrary $\lambda ,m\in {\left\{\mathrm{0,1}\right\}}^{\ast }$ and $\left(\text{pk},\text{sk}\right)$ output by $\text{KeyGen}\left(1^{\lambda }\right)$ , we have

$$\begin{array}{}\text{(11)}& m=\text{Dec}\left(\text{sk},\left(\text{Enc}\left(\text{pk},m\right)\right)\right).\end{array}$$

• For arbitrary $\lambda$ , arbitrary $m_1,...,m_l\in {\left\{\mathrm{0,1}\right\}}^{\ast }$ , and $C\in {\mathcal{C}}_{\lambda }$ , we have

$$\begin{array}{}\text{(12)}& \mathcal{C}\left(m_1,...,m_{\ell }\right)=\text{Dec}\left(\text{sk},\left(\text{Eval}\left(\text{pk},\left(C,\text{Enc}\left(pk,m_1\right),...,\text{Enc}\left(pk,m_{\ell }\right)\right)\right)\right)\right).\end{array}$$

(CPA Security [[21]]). One FHE scheme is indistinguishable from the choice of plaintext attack ( $\text{IND}-\text{CPA}$ ): the condition that security needs to be satisfied is that for any PPT adversary $\mathcal{A}$ , the following probabilities related to are negligible:

$$\begin{array}{c}\text{(13)}& \left|\mathrm{Pr}\right.\left[\mathcal{A}\left(\text{pk},\text{Enc}\left(\text{pk},m_0\right)\right)=1\right],-\left.\mathrm{Pr}\left[\mathcal{A}\left(\text{pk},\text{Enc}\left(\text{pk},m_1\right)\right)=1\right]\right|=\text{negl}\left(\lambda \right).\end{array}$$

Among them, $\left(\text{pk},\text{sk}\right)⟵\text{KeyGen}\left(1^{\lambda }\right)$ and $m_0\cdot m_1$ 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.

(Compactness [[21]]). For a class of loops ${\left\{{ℂ}_k\right\}}_{k\in \mathbb{N}}$ , if there is a polynomial $\alpha =\alpha \left(\lambda \right)$ such that the length of output ciphertext of Eval is at most $\alpha$ , then an $L$ Fully Homomorphic Encryption is compact (if it is nontrivial, then for all $\lambda$ , some $C\in {\left\{ℂ\right\}}_{\lambda }$ , and we have $\alpha \left(\lambda \right)\le \left|C\right|$ ).

Let us review some of the basic tools proposed by Brakerski and Vaikuntanathan [[23]] and Gentry et al. [[4]]. We fix $q,m\in \mathbb{N}$ . Let $l=\lfloor \log \left(q\right)\rfloor +1$ , and therefore, $2^{l-1}\le q<2^l$ and $N=m\cdot l$ .

(See [[24]]). The algorithm BitComp enters a vector $\mathbf{v}\in {\mathbb{Z}}_q^m$ and outputs an $N$ -dimensional vector ${\left(v_{\mathrm{1,0}},...,v_{1,l-1},...,v_{m,0},...,v_{m,l-1}\right)}^T\in {\left\{\mathrm{0,1}\right\}}^N$ where $v_{i,j}$ is the $j$ bit in the binary representation of $v_i$ (sorted by minimum impact to maximum impact). In other words,

$$\begin{array}{}\text{(14)}& v_i={\displaystyle \sum _{j=0}^{l-1}{2}^j{v}_{i,j}}.\end{array}$$

(See [[24]]). Algorithm enters a vector

$$\begin{array}{}\text{(15)}& \mathbf{v}={\left(v_{\mathrm{1,0}},...,v_{1,l-1},...,v_{m,0},...,v_{m,l-1}\right)}^T{\in }_q^N\end{array}$$

and output ${\left({\displaystyle {\sum }_{j=0}^{l-1}{2}^j},...,v_{1,j},...,{\displaystyle {\sum }_{j=0}^{l-1}{2}^{j{v}_{m,j}}}\right)}^T{\in }_q^m$ .

Note that the input vector $\mathbf{v}$ does not need to be binary and any of the input vector algorithms in ${\mathbb{Z}}^N$ are already defined.

(See [[24]]). The algorithm Flatten enters a vector $\mathbf{v}\in {\mathbb{Z}}_q^N$ and outputs an $N$ -dimension binary vector (i.e., an element from $0,1^N$ ) defined as

$$\begin{array}{}\text{(16)}& \text{Flatten}\left(\mathbf{v}\right)=\text{BitDecomp}\left({\text{BitDecomp}}^{-1}\left(\mathbf{v}\right)\right).\end{array}$$

(See [[24]]). The algorithm PoweOftwo enters an $m$ -dimension vector $\mathbf{v}\in {\mathbb{Z}}_q^N$ and outputs an $N$ -dimension vector in ${\mathbb{Z}}_q^N$ . The output is as follows:

$$\begin{array}{}\text{(17)}& {\left(v_1,2v_1,...,2^{l-1}{v}_1,...,v_m,2v_m,...,2^{l-1}{v}_m\right)}^T.\end{array}$$

(See [[26]]). For any $N\ge m\lfloor \log q\rfloor$ , there is a fixed effective computable matrix $\mathbf{G}\in {\mathbb{Z}}_q^{m\times N}$ and a valid computable deterministic "short-image" function ${\mathbf{G}}^{-1}\left(\cdot \right)$ that meets the following conditions. For arbitrary $m^{\prime }$ , we enter a matrix $\mathbf{M}\in {\mathbb{Z}}_q^{m\times m^{\prime }}$ and the inverse function ${\mathbf{G}}^{-1}\left(\mathbf{M}\right)$ outputs a matrix ${\mathbf{G}}^{-1}\left(\mathbf{M}\right)\in {\left\{\mathrm{0,1}\right\}}^{N\times m^{\prime }}$ so that $\mathbf{G}{\mathbf{G}}^{-1}\left(\mathbf{M}\right)=\mathbf{M}$ .

In fact, we can also express the abovementioned definitions and results as follows using the language of $\mathbf{G}$ and ${\mathbf{G}}^{-1}$ . Micciancio and Peikert's [[26]] matrix $\mathbf{G}$ can be expressed as $\mathbf{G}={\mathbf{I}}_m\otimes \in {\mathbb{Z}}_q^{m\times N}$ , where $\mathbf{g}={\left(\mathrm{1,2,4},...,2^{l-1}\right)}^T$ . For $\mathbf{v}\in {\mathbb{Z}}_q^m$ , there is $\left(\mathbf{v}\right)={\mathbf{v}}^T\mathbf{G}$ . For $\mathbf{v}\in {\mathbb{Z}}_q^N$ , there is ${\text{BitDecomp}}^{-1}\left(\mathbf{v}\right)=\mathbf{G}\mathbf{v}$ . For $\mathbf{a}\in {\mathbb{Z}}_q^m$ , the algorithm $\text{BitDecomp}\left(\mathbf{a}\right)$ is renamed as ${\mathbf{G}}^{-1}\left(\mathbf{a}\right)$ . For $\mathbf{v}\in {\mathbb{Z}}_q^m$ , there is $\text{Power Of two}\left(\mathbf{v}\right)={\mathbf{v}}^T\mathbf{G}$ . For $\mathbf{v}\in {\mathbb{Z}}_q^N$ , there is ${\text{BitDecomp}}^{-1}\left(\mathbf{v}\right)=\mathbf{G}\mathbf{v}$ . For $\mathbf{a}\in {\mathbb{Z}}_q^m$ , the algorithm $\text{BitDecomp}\left(a\right)$ is renamed as ${\mathbf{G}}^{-1}\left(\mathbf{a}\right)$ .

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 $\text{BitDecomp}$ , ${\text{BitDecomp}}^{-1}$ , and $\text{Flatten}$ , but the ideas from [[19], [27]] borrowed into this paper are defined using tool matrix $\mathbf{G}$ . Let $\lambda$ be the security parameter and $L$ be the number of levels of homomorphic encryption.

• $\text{GSW}.\text{Setup}\left(1^{\lambda },1^L\right)$ :
• (1) Select a module $q$ of bit $\mathcal{K}=\text{mathcal}K\left(\lambda ,L\right)$ , error distribution $\chi =\chi \left(\lambda ,L\right)$ on the parameter $n=n\left(\lambda ,L\right)\in \mathbb{N}$ and $\mathbb{Z}$ , so that the $\left(q,n,\chi \right)-\text{LWE}$ problem is at least $2^{\lambda }$ secure for known attacks. Choose a parameter $m=m\left(\lambda ,L\right)=O\left(n\log \left(q\right)\right)$ .
• (2) Output: $\text{params}=\left(n,q,\chi ,m\right)$ . We express $l=\lfloor \log \left(q\right)\rfloor +1$ and $N=\left(n+1\right)\cdot l$ .
• $\text{GSW}.\text{KeyGen}\left(\text{params}\right)$ :
• (1) Select $\mathbf{t}={\left(t_1,...,t_n\right)}^T⟵{\mathbb{Z}}_q^n$ and calculate

$$\begin{array}{}\text{(18)}& \mathbf{s}⟵{\left(1,-{\mathbf{t}}^T\right)}^T={\left(1,-t_1,...,-t_n\right)}^T\in {\mathbb{Z}}_q^{\left(n+1\right)\times 1}.\end{array}$$

• (2) Generate a matrix $\mathbf{B}⟵{\mathbb{Z}}_q^{mm\times n}$ and a vector $\mathbf{e}⟵{\chi }^m$ .
• (3) Calculate $\mathbf{b}=\mathbf{B}\mathbf{t}+\mathbf{e}\in {\mathbb{Z}}_q^m$ and construct matrix $\mathbf{A}=\left(\left.b\right|B\right)\in {\mathbb{Z}}_q^{m\times \left(n+1\right)}$ . Obviously, we observed.
• (4) Return to $\text{sk}⟵\mathbf{s}$ and $\text{pk}⟵\mathbf{A}$ .
• $\text{GSW}.\text{Enc}\left(\text{params},\text{pk},\mu \right)$ : in order to encrypt a single-bit message $\mu \in \left\{\mathrm{0,1}\right\}$ ,
• (1) Let $\mathbf{G}$ be the abovementioned matrix $\left(n+1\right)\times N$
• (2) Select a matrix $\mathbf{R}⟵{\left\{\mathrm{0,1}\right\}}^{m\times N}$ evenly
• (3) Calculate

$$\begin{array}{}\text{(19)}& \mathbf{C}=\mu G+A^T\mathbf{R}\left(\mathrm{mod}q\right)\in {\mathbb{Z}}_q^{\left(n+1\right)\times N}\end{array}$$

• In the original GSW scheme,
• $\text{Flatten}\left(\mu \mathbf{I}+\text{BitDecomp}\left(\mathbf{R}\mathbf{A}\right)\right)\in {\left\{\mathrm{0,1}\right\}}^{N\times N}$ , where $\mathbf{I}$ is an identity matrix.
• $\text{GSW}.\text{Dec}\left(\text{params},\text{sk},C\right)$ :
• (1) We have $\text{sk}=\mathbf{s}\in {\mathbb{Z}}_q^{n+1}$ .
• (2) Let $I$ meet $\left(q/4\right)<2^{I-1}\le \left(q/2\right)$ . Let ${\mathbf{C}}_I$ be column $I$ of $\mathbf{C}$ .
• (3) Calculate $x⟵〈{\mathbf{C}}_I,\mathbf{s}〉\left(\mathrm{mod}q\right)$ within the scope of $\left(-\left(q/2\right),\left(q/2\right)\right]$ ; note $〈{\mathbf{C}}_I,\mathbf{s}〉={\mathbf{C}}_I^T\mathbf{s}$ and

$$\begin{array}{}\text{(20)}& {\mathbf{C}}^T\mathbf{s}=\mu {\mathbf{G}}^T\mathbf{s}+{\mathbf{R}}^T\mathbf{A}\mathbf{s}=\mu {\left(\mathrm{1,2,4},...\right)}^T+{\mathbf{R}}^T\mathbf{e}.\end{array}$$

• From that mentioned above, it can be seen that column $I$ of the ciphertext matrix $\mathbf{C}$ selected in the calculation corresponds to coordinate $I$ of the vector $〈{\mathbf{C}}_I,\mathbf{s}〉$ , i.e. $\mu 2^{I-1}+{\mathbf{R}}_I^T\mathbf{e}$ .
• (4) Output ${\mu }^{\prime }=\left|\lfloor {\left(x/2\right)}^{I-1}\rfloor \right|$ .
• So, if it is $\left|x\right|<2^{I-2}\le \left(q/4\right)$ , then it returns to 0, and if it is $\left|x\right|>2^{I-2}$ , then it returns to 1.
• $\text{GSW}.\text{Eval}\left(\text{params},C_1,...,C_l\right)$ :
• $\text{GSW}.\text{Mult}\left({\mathbf{C}}_1,{\mathbf{C}}_2\right)$ : calculate and output

$$\begin{array}{}\text{(21)}& {\mathbf{C}}_1{\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)=\left({\mu }_1\mathbf{G}+{\mathbf{A}}^T{\mathbf{R}}_1\right){\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)={\mu }_1{\mathbf{C}}_2+{\mathbf{A}}^T{\mathbf{R}}_1{\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)={\mathbf{A}}^T\left({\mathbf{R}}_1{\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)+{\mu }_1{\mathbf{R}}_2+{\mu }_1{\mu }_2\mathbf{G}\left(\mathrm{mod}q\right)\right).\end{array}$$

• $\text{GSW}.\text{Add}\left({\mathbf{C}}_1,{\mathbf{C}}_2\right)\in {\mathbb{Z}}_q^{\left(n+1\right)\times N}$ : output

$$\begin{array}{}\text{(22)}& {\mathbf{C}}_1+{\mathbf{C}}_2=\left({\mu }_1+{\mu }_2\right)\mathbf{G}+{\mathbf{A}}^T\left({\mathbf{R}}_1+{\mathbf{R}}_2\right).\end{array}$$

Note that ${\mathbf{C}}_1{\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)\in {\mathbb{Z}}_q^{\left(n+1\right)\times N}$ . In addition, use $\mathbf{G}-{\mathbf{C}}_1{\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)$ to calculate homomorphic $\text{NAND}$ gates.

Note that, in [[19]], the decryption algorithm is to select a suitable vector $\mathbf{w}$ and calculate $\mathbf{s}\mathbf{C}{\mathbf{G}}^{-1}\left({\mathbf{w}}^T\right)$ . 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.

When $q$ is a power of 2, there is also a variant of the message in ${\mathbb{Z}}_q$ . See more details in [[4]].

A brief proof of the following theorem is given in [[4]].

Let $\left(n,q,\chi \right)$ be public parameter so that the ${\text{LWE}}_{\left(n,q,\chi \right)}$ hypothesis is true, and let $m=O\left(n\log \left(q\right)\right)$ . Then, we can say that the GSW scheme is $\text{IND}-\text{CPA}$ safe.

The most important step of the proof is to prove that $\left(\mathbf{A},\mathbf{R}\mathbf{A}\right)$ and the uniform distribution is computational indistinguishable.

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]].

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 $\lambda$ , set $t$ to be the private keys number, and then, can encrypt the $t$ -bit messages at one time.

Let $q=q\left(\lambda \right)$ be an integer, and let $\chi =\chi \left(\lambda \right)$ be a distribution set on $\mathbb{Z}$ . The definition of the variant of the GSW scheme is similar to the cryptosystem proposed in [[19], [27]]. More specifically,

• $\text{params}⟵\text{MFHE}.\text{Setup}\left(1^{\lambda },1^L\right)$ :
• (1) In particular, we first select the modulo $q=q\left(\lambda \right)$ , and the dimension of lattice $n=n\left(\lambda ,L\right)$ . We appropriately select the error distribution for $\chi =\chi \left(\lambda ,L\right)$ for $2^{\lambda }$ security against known LWE attacks, Finally, we select the parameter $m=m\left(\lambda ,L\right)=O\left(n\log q\right)$ and a parameter $t=O\left(\log \left(n\right)\right)$ .
• (2) Let $l=\lfloor \log q\rfloor +1$ and $N=\left(n+t\right)\cdots l$ , and then, output $\text{params}=\left(n,q,\chi ,m,t\right)$ .
• $\left(\text{pk},\text{sk}\right)⟵\text{MFHE}.\text{KeyGen}\left(\text{params}\right)$ :
• (1) For $i\in \left[t\right]$ , select ${\mathbf{t}}_i^T=\left(t_{i,1},...,t_{i,n}\right)$ from ${\mathbb{Z}}_q^{1\times n}$ and output

$$\begin{array}{}\text{(23)}& \mathbf{s}{\mathbf{k}}_i≔{\mathbf{s}}_i={\left({\mathbf{I}}_i\mathrm{\mid }-{\mathbf{t}}_i^T\right)}^T={\left(\left.0,...,1,...,0\right|-t_{i,1},...,-t_{i,n}\right)}^T\in {\mathbb{Z}}_q^{\left(n+t\right)\times 1},\end{array}$$

• the $i$ position of which is 1.
• (2) Select a matrix $\mathbf{B}⟵{\mathbb{Z}}_q^{m\times n}$ and $t$ vectors ${\mathbf{e}}_i⟵{\chi }^{m\times 1}$ , $i\in \left[t\right]$ evenly, and then, calculate ${\mathbf{b}}_i=\mathbf{B}\cdot t_i+{\mathbf{e}}_i\left(\mathrm{mod}q\right)$ and output

$$\begin{array}{}\text{(24)}& \text{pk}=\mathbf{P}=\left[{\mathbf{b}}_1\left|\cdots \right|{\mathbf{b}}_t\left|\mathbf{B}\right.\right]\in {\mathbb{Z}}_q^{m\times \left(n+t\right)},\end{array}$$

• where the size of $\text{pk}$ is $O\left(nm\cdot {\log }^{2}q\right)$ . In addition, we observed that $\mathbf{P}\cdot s_i={\mathbf{e}}_i\left(\mathrm{mod}q\right)$ .
• (3) Output $\text{pk}⟵\mathbf{P}$ and $\text{sk}⟵\mathbf{S}≔\left\{{\mathbf{s}}_1,...,{\mathbf{s}}_t\right\}$ . It is worth noting that $\mathbf{P}\cdot S=\left[{\mathbf{e}}_1,...,{\mathbf{e}}_t\right]\left(\mathrm{mod}q\right)$ .
• $\mathbf{C}⟵\text{MFHE}.\text{Enc}\left(\text{params,pk},\mathbf{M}\right)$ :
• (1) To encrypt $t$ -bit ${\mu }_i\in \mathrm{0,1}$ , ${\mu }_i\in \mathrm{0,1}$ , embed the $t$ bits into a $\left(t\times t\right)$ -dimension matrix first, $\mathbf{U}=\text{diag}\left({\mu }_{\mathrm{1,1}},...,{\mu }_{t,t}\right)\in 0,1^{t\times t}$ , where ${\mu }_{i,j}=0$ , $i\ne j$ , and $j\in \left[t\right]$ . Later, for simplicity, ${\mu }_{i,j}$ will be abbreviated as ${\mu }_i$ , and the message matrix is constructed using a plaintext matrix $\mathbf{U}$ .

$$\begin{array}{}\text{(25)}& \mathbf{M}=\left(\begin{array}{cc}{\mathbf{U}}_{t\times t}& 0_{t\times n}\\ 0_{n\times t}& {\mathbf{E}}_{n\times n}\end{array}\right)\in {\left\{\mathrm{0,1}\right\}}^{\left(n+t\right)\times \left(n+t\right)},\end{array}$$

• where $\mathbf{U}$ is a random diagonal matrix, and note that $\mathbf{E}$ is a $\left(n\times n\right)$ -dimensional matrix.
• (2) Then, select a uniform matrix $\mathbf{R}⟵0,1^{m\times N}$ . Calculate and output cipher text:

$$\begin{array}{}\text{(26)}& \mathbf{C}=M\cdot G+{\mathbf{P}}^T\cdot \mathbf{R}\left(\mathrm{mod}q\right)\in {\mathbb{Z}}_q^{\left(n+t\right)\times N}.\end{array}$$

• Now, we propose a decryption algorithm for the MFHE scheme which allows us to recover all the message bits at the one time.
• $\mathbf{U}⟵\text{MFHE}.\text{Dec}\left(\text{params,pk},\mathbf{C}\right)$ :
• (1) First, assume that the user has a private key matrix $\mathbf{S}=\left({\mathbf{s}}_1,...,{\mathbf{s}}_t\right)\in {\mathbb{Z}}_q^{\left(n+t\right)\times t}$ as follows:

$$\begin{array}{}\text{(27)}& \mathbf{S}≔\left({\mathbf{s}}_1,...,{\mathbf{s}}_t\right)=\left(\begin{array}{ccc}1& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & 1\\ -t_{\mathrm{1,1}}& \cdots & -t_{t,1}\\ ⋮& \ddots & ⋮\\ -t_{1,n}& \cdots & -t_{t,n}\end{array}\right).\end{array}$$

• What needs to be noted here is

$$\begin{array}{}\text{(28)}& \mathbf{P}\cdot S=\left[{\mathbf{b}}_1-\mathbf{B}{\mathbf{t}}_1,...,{\mathbf{b}}_t-\mathbf{B}{\mathbf{b}}_t\right]=\left[{\mathbf{e}}_1,...,{\mathbf{e}}_t\right]\left(\mathrm{mod}\in {\mathbb{Z}}_q^{m\times t}\right).\end{array}$$

• Therefore, it is easy for us to get the bound of $\mathbf{P}\cdot S$ which is less than or equal to $t\left|\mathbf{e}\right|$ , i.e. $‖\mathbf{P}\cdot S‖\le t\left|\mathbf{e}\right|$ .
• (2) Define the matrix $\mathbf{W}{\mathbb{Z}}_q^{t\times \left(\left(+t\right.\right)}$ as follows:

$$\begin{array}{}\text{(29)}& {\mathbf{W}}^T≔\left(\begin{array}{ccc}⌈\frac{q}{2}⌉& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & ⌈\frac{q}{2}⌉\\ 0& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & 0\end{array}\right).\end{array}$$

• (3) Calculate and output

$$\begin{array}{}\text{(30)}& {\mathbf{V}}_{i,j}=〈\mathbf{S},\mathbf{C}〉\cdot {\mathbf{G}}^{-1}\left({\mathbf{W}}^T\right)\left(\mathrm{mod}q\right)\in {\mathbb{Z}}_q^{t\times t}.\end{array}$$

• Among them, we have $〈\mathbf{S},\mathbf{C}〉\in {\mathbb{Z}}_q^{t\times t}$ , i.e.,

$$\begin{array}{}\text{(31)}& 〈\mathbf{S},\mathbf{C}〉={\mathbf{S}}^T{\mathbf{P}}^T\mathbf{R}+{\mathbf{S}}^T\mathbf{M}\mathbf{G}={\left[{\mathbf{e}}_1,...,{\mathbf{e}}_t\right]}^T\mathbf{R}+{\mathbf{S}}^T\mathbf{M}\mathbf{G}\left(\mathrm{mod}q\right).\end{array}$$

• (4) Finally, use the results mentioned above to output the complete message $\mathbf{U}=‖\lfloor \left({\mathbf{V}}_{i,j}/\left(q/2\right)\right)\rfloor ‖\in {\left\{\mathrm{0,1}\right\}}^{t\times t}$ .
• $\text{MFHE}.\text{Eval}\left(\text{params},{\mathbf{C}}_1,...,{\mathbf{C}}_l\right)$ :there are two algorithms, which are, homomorphic addition and homomorphic multiplication. For any two plaintext matrices ${\mathbf{U}}_1,{\mathbf{U}}_2\in {\left\{\mathrm{0,1}\right\}}^{t\times t}$ , we get the ciphertext separately.

$$\begin{array}{c}\text{(32)}& {\mathbf{C}}_1={\mathbf{M}}_1\cdot \mathbf{G}+{\mathbf{P}}^T\cdot {\mathbf{R}}_1,{\mathbf{C}}_2={\mathbf{M}}_2\cdot \mathbf{G}+{\mathbf{P}}^T\cdot {\mathbf{R}}_2.\end{array}$$

• Therefore, the homomorphic addition and multiplication are as follows:
• $\text{MFHE}.\text{Mult}\left({\mathbf{C}}_1,{\mathbf{C}}_2\right)\in {\mathbb{Z}}_q^{\left(n+t\right)\times N}$ : output

$$\begin{array}{}\text{(33)}& {\mathbf{C}}_1{\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)=\left({\mathbf{M}}_1\mathbf{G}+{\mathbf{P}}^T{\mathbf{R}}_1\right)\cdot {\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)={\mathbf{P}}^T{\mathbf{R}}_1{\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)+{\mathbf{M}}_1{\mathbf{P}}^T{\mathbf{R}}_2+{\mathbf{M}}_1{\mathbf{M}}_2\mathbf{G}\left(\mathrm{mod}q\right).\end{array}$$

• $\text{MFHE}.\text{Add}\left({\mathbf{C}}_1,{\mathbf{C}}_2\right)\in {\mathbb{Z}}_q^{\left(n+t\right)\times N}:\text{output}{\mathbf{C}}_1+{\mathbf{C}}_2=\left({\mathbf{M}}_1+{\mathbf{M}}_2\right)\mathbf{G}+{\mathbf{P}}^T\left({\mathbf{R}}_1+{\mathbf{R}}_2\right)$ .
• Here, we can calculate a homomorphic NAND gate from the output.

Generally, we can choose different private keys ${\text{sk}}_i$ to decrypt column $j$ of the ciphertext ${\mathbf{C}}_j$ bit-by-bit and get the $i$ bit message of $C_j$ , 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 $\mathbf{S}$ based on the abovementioned decryption algorithm. We calculate ${\mathbf{V}}_{i,j}={\mathbf{S}}^T\mathbf{C}\cdot G^{-1}\left({\mathbf{W}}^T\right)$ as follows:

$$\begin{array}{}\text{(34)}& {\mathbf{V}}_{i,j}=⌈\frac{q}{2}⌉\cdot \mathbf{U}+\left(\begin{array}{c}{\mathbf{e}}_1^T\mathbf{R}\\ ⋮\\ {\mathbf{e}}_t^T\mathbf{R}\end{array}\right)\cdot {\mathbf{G}}^{-1}\left({\mathbf{W}}^T\right)\in {\mathbb{Z}}_q^{t\times t}.\end{array}$$

The magnitude of the noise can be simply calculated and verified to grow linearly compared to single-bit decryption algorithm.

• ${\mu }_{i,j}⟵\text{MFHE}.\text{bitDec}\left(\text{params},{\text{sk}}_i,\mathbf{C},{\mathbf{w}}_j\right)$ :
• (1) Suppose we want to decrypt the bit ${\mu }_{i,j}$ of row $i$ and column $j$ , so let ${\text{sk}}_i={\mathbf{s}}_i≔$ , then define a vector so that the position is, and the other positions are 0, $j\in \left[t\right]$ .

$$\begin{array}{}\text{(35)}& {\mathbf{w}}_j^T=\left[\underset{t}{\underbrace{0,...,{⌈\frac{q}{2}⌉}_j,...,0}}\left|\underset{n}{\underbrace{0,...,0}}\right.\right].\end{array}$$

• (2) For $i,j$ to $t$ , calculate

$$\begin{array}{}\text{(36)}& {\nu }_{i,j}={\mathbf{s}}_i^T\mathbf{C}\cdot {\mathbf{G}}^{-1}\left({\mathbf{w}}_j^T\right)\left(\text{mod}q\right)\in {\mathbb{Z}}_q.\end{array}$$

• The inner product of $〈{\mathbf{s}}_i,\mathbf{C}〉$ equals to

$$\begin{array}{}\text{(37)}& {\mathbf{s}}_i^T{\mathbf{P}}^T\mathbf{R}+{\mathbf{s}}_i^T\mathbf{M}\mathbf{G}={\mathbf{e}}_i^T\mathbf{R}+{\mathbf{s}}_i^T\mathbf{M}\mathbf{G}\left(\mathrm{mod}q\right){\mathbb{Z}}_q^{1\times N}.\end{array}$$

• (3) Output a message ${\mu }_{i,j}=‖\lfloor \left({\mathbf{V}}_{i,j}/\left(q/2\right)\right)\rfloor ‖\in \left\{\mathrm{0,1}\right\}$ , in which $\lfloor \cdot \rfloor$ represents the operation that rounds to the nearest integer. Therefore the value belongs to $\left\{\mathrm{0,1}\right\}$ . 4. Finally, by repeating it $t^2$ times, the entire message can be recovered. The $\text{bitDec}$ algorithm here is similar to the algorithm in [[2]], which is achieved by recovering each element separately.

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 of $⌈\left(q/2\right)⌉$ in the vector $\mathbf{w}$ . That is, dot-multiply ${\mathbf{s}}_i^T\mathbf{C}$ and ${\mathbf{G}}^{-1}\left({\mathbf{w}}_j\right)$ to obtain the bits of the row and column of the plaintext matrix.

We can get all the bits of the message by using the $\text{bitDec}$ decryption algorithm and appropriate private key.

It can be seen that our message-encapsulation GSW scheme is to implement $t\times t$ -bit homomorphic addition. However, since the $\left(i,j\right)$ element of ${\mathbf{U}}_1\times {\mathbf{U}}_2$ is not a product of ${\mu }_{1_{i,j}}\times {\mu }_{2_{i,j}}$ , only $t$ -bit homomorphic multiplication is supported.

Next, we analyze the correctness of the MFHE scheme.

We call the message matrix $\mathbf{U}\in {\mathbb{Z}}_q^{t\times t}$ which is obtained by decrypting the ciphertext under $t$ different private keys ${\mathbf{s}}_i,i\in \left[t\right]$ (see (2)). The noise of a single-bit message is as follows:

$$\begin{array}{}\text{(38)}& {\text{noise}}_{\left({\mathbf{s}}_i,\mathbf{M}\right)}={\mathbf{s}}_i^T\mathbf{C}-{\mathbf{s}}_i^T\mathbf{M}\mathbf{G}={\mathbf{s}}_i^T{\mathbf{P}}^T\mathbf{R}={\mathbf{e}}_i^T\mathbf{R}.\end{array}$$

For flexible single-bit decryption algorithm $\text{bitDec}$ , we represent the noise vector as $\text{noise}\in {\mathbb{Z}}_q^{1\times N}$ . For simplicity, we abbreviate ${\text{noise}}_{\left({\mathbf{s}}_i,\mathbf{M}\right)}\left(\mathbf{C}\right)$ to ${\text{noise}}_{{\mathbf{s}}_i}$ when $\mathbf{M}$ and $\mathbf{C}$ do not affect the contextual understanding.

Note that, in our setup, due to the structure of the new public key, ${\text{noise}}_{{\mathbf{s}}_i}$ is the noise of row $i$ of the plaintext matrix $\mathbf{U}$ , not the single-bit noise.

Obviously, using Definition 4.1, for convenience, for a decryption algorithm $\text{Dec}$ , if the noise meets

$$\begin{array}{}\text{(39)}& {\text{Noise}}_{\left(\mathbf{S},\mathbf{M}\right)}\left(\mathbf{C}\right)={\mathbf{S}}^T\cdot {\mathbf{P}}^T\cdot \mathbf{R}=\left(\begin{array}{c}{\text{noise}}_{{\mathbf{s}}_1}\\ ⋮\\ {\text{noise}}_{{\mathbf{s}}_t}\end{array}\right)\left(\mathrm{mod}q\right),\end{array}$$

where $\mathbf{S}=\left[{\mathbf{s}}_1,...,{\mathbf{s}}_t\right]$ is a one-time private key matrix, we can represent the entire noise matrix as

$$\begin{array}{}\text{(40)}& {\text{Noise}}_{\left(\mathbf{S},\mathbf{M}\right)}\left(\mathbf{C}\right)={\left({\text{noise}}_{s_1},...,{\text{noise}}_{s_t}\right)}^T\in {\mathbb{Z}}_q^{t\times N}.\end{array}$$

For convenience, we will abbreviate ${\text{Noise}}_{\left(\mathbf{S},\mathbf{M}\right)}\left(\mathbf{C}\right)$ as ${\text{Noise}}_{\mathbf{S}}$ when $\mathbf{M}$ and $\mathbf{C}$ do not affect the contextual understanding.

In order to analyze the correctness, for convenience, we first define the following noise ciphertext concept.

( $E$ -Noise Ciphertext). A ciphertext matrix $\mathbf{C}\in {\mathbb{Z}}_q^{\left(m+1\right)\times N}$ with $E$ noise, which makes in a private key ${\mathbf{s}}_i\in {\mathbb{Z}}_q^{\left(n+t\right)\times 1}$ , for a corresponding message $\mathbf{M},〈{\mathbf{s}}_i,\mathbf{C}〉={\mathbf{s}}_i^T\cdot \mathbf{M}\cdot G+{\mathbf{e}}_i^T\cdot \mathbf{R}$ . Then, let the norm of ${\text{noise}}_{{\mathbf{s}}_i}$ be

$$\begin{array}{}\text{(41)}& ‖{\text{noise}}_{{\mathbf{s}}_i}‖\le ‖{\mathbf{e}}_i^T\mathbf{R}‖\le {‖{\mathbf{e}}_i^T‖}_2\cdot {‖\mathbf{R}‖}_{\infty }\le \sqrt{N}\cdot 2\sqrt{m}B\le E.\end{array}$$

For a one-time private key matrix $\mathbf{S}\in {\mathbb{Z}}_q^{\left(n+t\right)\times t}$ , we can get ${\text{Noise}}_{\mathbf{S}}={\left[{\mathbf{e}}_1,...,{\mathbf{e}}_t\right]}^T\cdot \mathbf{R}$ when we run the Dec algorithm. So, in this case, we get

$$\begin{array}{}\text{(42)}& ‖{\text{Noise}}_{\mathbf{S}}‖\le t\cdot ‖{\text{noise}}_{{\mathbf{s}}_i}‖\le t\cdot E.\end{array}$$

For a plaintext matrix $\mathbf{U}$ (a combination of $\mathbf{M}$ ) and a private key ${\mathbf{s}}_i,i\in \left[t\right]$ , the noise vector of the ciphertext $\mathbf{C}$ meets

$$\begin{array}{}\text{(43)}& t‖{\text{noise}}_{{\mathbf{s}}_i}‖=‖{\text{Noise}}_{\mathbf{S}}‖.\end{array}$$

In the following, we analyze the correctness of the decryption.

Let $\mathbf{C}$ be an $E$ noise encryption of $\mathbf{M}$ . If we can recover ${\mu }_{i,j}$ (an element of $\mathbf{U}$ ) from the ciphertext $\mathbf{C}$ under the private key ${\mathbf{s}}_i$ , then there is

$$\begin{array}{}\text{(44)}& {\mu }_{i,j}≔〈{\mathbf{s}}_i,\mathbf{C}〉\cdot {\mathbf{G}}^{-1}\left({\mathbf{w}}_j^T\right)=\left({\text{noise}}_{{\mathbf{s}}_i}+{\mathbf{s}}_i^T\mathbf{M}\mathbf{G}\right)\cdot {\mathbf{G}}^{-1}\left({\mathbf{w}}_j^T\right),\end{array}$$

so that

$$\begin{array}{}\text{(45)}& {‖{\text{noise}}_{{\mathbf{s}}_i}\cdot {\mathbf{G}}^{-1}\left({\mathbf{w}}_j^T\right)‖}_{\infty }\le ‖{\text{noise}}_{{\mathbf{s}}_i}‖\cdot ‖{\mathbf{G}}^{-1}\left({\mathbf{w}}_j^T\right)‖\le N\cdot E<\frac{q}{8}.\end{array}$$

Obviously, by using Lemma 4.2 we can simply prove Lemma 4.7, and we will not go into details here.

Let $\mathbf{C}$ be an $E$ noise encryption in $\mathbf{M}$ . If we can recover all $\mathbf{U}$ from the ciphertext $\mathbf{C}$ , then there is a private key matrix $\mathbf{S}$ such that

$$\begin{array}{}\text{(46)}& \mathbf{V}=〈\mathbf{S},\mathbf{C}〉\cdot {\mathbf{G}}^{-1}\left({\mathbf{W}}^T\right)=\left({\text{Noise}}_{\mathbf{S}}+{\mathbf{S}}^T\mathbf{M}\mathbf{G}\right)\cdot {\mathbf{G}}^{-1}\left({\mathbf{W}}^T\right),\end{array}$$

where ${‖{\text{Noise}}_{SS}\cdot {\mathbf{G}}^{-1}\left({\mathbf{W}}^T\right)‖}_{\infty }\le N\cdot tE<\left(q/8\right)$ .

This proof can be obtained directly from Lemma 4.2 and Lemma 4.7. Now, we know that as long as ${‖{\text{Noise}}_{\mathbf{S}}\cdot {\mathbf{G}}^{-1}\left({\mathbf{W}}^T\right)‖}_{\infty }\le \left(q/8\right)$ , the decryption runs correctly, i.e., $E<\left(q/4tN\right)$ . Therefore, we call the value $E=\left(q/4tN\right)$ 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.

For the convenience of reading, let ${\mathrm{\Upsilon }}_{{\mathbf{C}}_1}≔{\text{Noise}}_{\left(\mathbf{S},{\mathbf{M}}_1\right)}\left({\mathbf{C}}_1\right)$ and ${\mathrm{\Upsilon }}_{{\mathbf{C}}_2}≔{\text{Noise}}_{\left(SS,{\mathbf{M}}_2\right)}\left({\mathbf{C}}_2\right)$ .

(See [[8]]). The boundary of the noise of homomorphic addition, homomorphic multiplication, and homomorphic negative is as follows:

• Addition: for ${\mathbf{M}}_1,{\mathbf{M}}_2\in {\left\{\mathrm{0,1}\right\}}^{\left(n+t\right)\times \left(n+t\right)}$ , the following condition is met:

$$\begin{array}{}\text{(47)}& ‖{\text{Noise}}_{\left(\mathbf{S},{\mathbf{M}}_1+{\mathbf{M}}_2\right)}\left({\mathbf{C}}_1+{\mathbf{C}}_2\right)‖\le ‖{{\rm Y}}_{{\mathbf{C}}_1}‖+‖{{\rm Y}}_{{\mathbf{C}}_2}‖.\end{array}$$

• Multiplication: for ${\mathbf{M}}_1,{\mathbf{M}}_2$ , the following condition is met:

$$\begin{array}{}\text{(48)}& ‖{\text{Noise}}_{\left(\mathbf{S},\left({\mathbf{M}}_1\cdot {\mathbf{M}}_2\right)\right)}\left({\mathbf{C}}_1{\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)\right)‖\le {‖{\mathbf{U}}_1‖}_2\cdot {‖{\Upsilon }_{{\mathbf{C}}_2}‖}_{\infty }+{‖{\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)‖}_{\infty }\cdot {‖{\Upsilon }_{{\mathbf{C}}_1}‖}_{\infty }.\end{array}$$

• NAND: for $\mathbf{M}$ , the following condition is met:

$$\begin{array}{}\text{(49)}& ‖{\text{Noise}}_{\left(\mathbf{S},\mathbf{M}\right)}\left(\mathbf{G}-\mathbf{C}\right)‖=‖{\text{Noise}}_{\left(\mathbf{S},\mathbf{M}\right)}\left(\mathbf{C}\right)‖.\end{array}$$

Let $\mathbf{S}\in {\mathbb{Z}}^{\left(n+t\right)\times t}$ be a private key matrix. Let ${\mathbf{C}}_1,{\mathbf{C}}_2\in {\mathbb{Z}}_q^{\left(m+1\right)\times N}$ be the ciphertext of the encrypted message ${\mathbf{M}}_1,{\mathbf{M}}_2\in {\left\{\mathrm{0,1}\right\}}^{\left(n+t\right)\times \left(n+t\right)}$ separately. Then,

• Homomorphic addition, that is, add ciphertext and ciphertext ${\mathbf{C}}^{\text{Add}}={\mathbf{C}}_1+{\mathbf{C}}_2\left(\mathrm{mod}q\right)$ , so that

$$\begin{array}{}\text{(50)}& 〈\mathbf{S},{\mathbf{C}}^{\text{Add}}〉={\text{Noise}}_{\left(SS,{\mathbf{M}}_1+{\mathbf{M}}_2\right)}+{\mathbf{S}}^T\cdot {\mathbf{M}}^{\text{Add}}\cdot \mathbf{G}.\end{array}$$

• Where ${\mathbf{M}}^{\text{Add}}={\mathbf{M}}_1+{\mathbf{M}}_2$ and the noise is

$$\begin{array}{}\text{(51)}& {\text{Noise}}_{\left(\mathbf{S},{\mathbf{M}}_1+{\mathbf{M}}_2\right)}={\text{Noise}}_{\left(\mathbf{S},{\mathbf{M}}_1\right)}+{\text{Noise}}_{\left(\mathbf{S},{\mathbf{M}}_2\right)}.\end{array}$$

• Obviously, the noise is $t\cdot \left(E_1+E_2\right)$ .
• Homomorphic multiplication: that is, multiply the ciphertext and ciphertext ${\mathbf{C}}^{\text{Mult}}={\mathbf{C}}_1{\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)\in {\mathbb{Z}}_q^{\left(n+t\right)\times N}$ , so that

$$\begin{array}{}\text{(52)}& {\mathbf{C}}^{\text{Mult}}={\mathbf{M}}_1{\mathbf{M}}_2\mathbf{G}+\left({\mathbf{P}}^T{\mathbf{R}}_1{\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)+{\mathbf{M}}_1{\mathbf{P}}^T{\mathbf{R}}_2\right).\end{array}$$

• Then, we have $〈\mathbf{S},{\mathbf{C}}^{\text{Mult}}〉$ which equals to

$$\begin{array}{}\text{(53)}& {\mathbf{S}}^T\left({\mathbf{M}}_1{\mathbf{M}}_2\mathbf{G}+\left({\mathbf{P}}^T{\mathbf{R}}_1{\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)+{\mathbf{M}}_1{\mathbf{P}}^T{\mathbf{R}}_2\right)\right).\end{array}$$

• For convenience, we first set the noise to

$$\begin{array}{}\text{(54)}& {\text{Noise}}_{\left(\mathbf{S},{\mathbf{M}}_1{\mathbf{M}}_2\right)}={\mathbf{S}}^T\left({\mathbf{P}}^T{\mathbf{R}}_1{\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)+{\mathbf{M}}_1{\mathbf{P}}^T{\mathbf{R}}_2\right).\end{array}$$

• Obviously, according to Lemma 4.2, there is

$$\begin{array}{}\text{(55)}& ‖{{\rm Y}}_{{\mathbf{C}}_1}‖=‖{\mathbf{S}}^T{\mathbf{P}}^T{\mathbf{R}}_1‖\le ‖{\left[{\mathbf{e}}_1,...,{\mathbf{e}}_t\right]}^T\cdot {\mathbf{R}}_1‖\le t{E}_1,\end{array}$$

• and ${\mathbf{C}}_2$ is a $\left(n+t\right)\times N$ binary matrix ( ${\mathbf{G}}^{-1}\in {\mathbb{Z}}_q^{N\times \left(n+t\right)}$ ). Therefore, in this case,

$$\begin{array}{}\text{(56)}& ‖{\mathbf{S}}^T{\mathbf{P}}^T{\mathbf{R}}_1\cdot {\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)‖\le t{E}_2\cdot ‖{\mathbf{G}}^{-1}\left({\mathbf{C}}_2\right)‖\le N\cdot t{E}_2\end{array}$$