# Efficient SMC Protocol Based on Multi-Bit Fully Homomorphic Encryption
## 3 Efficient Fully Homomorphic Encryption Scheme  
This scheme is an improved NFHE scheme based on GSW13 in reference [18], and the structure of the scheme is as follows. The modulus \(q\) and the dimension \(N\) are settled, and the ciphertext \(\mathbf{C}\) is an \(N\times N\)-dimensional matrix defined on \(\mathbb{Z}_{p}\). In addition, each componentof the matrix is much smaller than \(q\). The private key \(\mathbf{sk}\) of \(\mathbf{C}\) is an \(N\)-dimensional vector defined on \(\mathbb{Z}_{p}\). Let the plain-text \(\mu\) be a small integer. When \(\mathbf{C}\cdot\mathbf{sk}=\mu\cdot\mathbf{sk}+\mathbf{e}\), \(\mathbf{C}\) is called the ciphertext of \(\mu\), where \(\mathbf{e}\) is the small error vector. In the decryption process, first extract the \(i\)-th row \(\mathbf{C}_{i}\) of \(\mathbf{C}\), then calculate \(x\leftarrow\left\langle\mathbf{C}_{i},\mathbf{sk}\right\rangle=\mu\cdot sk_{i}+e_{i}\), and finally output \(\mu=\lfloor x/sk_{i}\rfloor\), where \(sk_{i}\) is the \(i\)-th element of \(\mathbf{sk}\), \(e_{i}\) is the \(i\)-th element of \(\mathbf{e}\), and \(i\in[0,N-1]\). The message \(\mu\) can be regarded as an eigenvalue of the ciphertext matrix \(\mathbf{C}\), and the private key \(\mathbf{sk}\) is the approximate eigenvector of \(\mathbf{C}\) corresponding to the eigenvalue \(\mu\). The structure of the scheme is as follows. First of all, defining functions such as \(\text{mbDpt}(\mathbf{a})\), \(\text{mbDpt}^{(-1)}(\mathbf{a}^{\prime})\), \(\text{mbFlatten}(\mathbf{a}^{\prime})\), and \(\text{pofmb}(\mathbf{b})\), the expansion method of the NFHE scheme is given. Then, based on the above functions, the five polynomial time algorithms included in the NFHE program are designed, namely the key generation algorithm \(\text{NFHE.Keygen}(n,q)\), the encryption algorithm \(\text{NFHE.Encrypt}(pk,\mu)\), the decryption algorithm \(\text{NFHE.Decrypt}(\mathbf{sk},\mathbf{C})\), the homomorphic addition algorithm \(\text{NFHE.Add}(C_{1},C_{2})\), and the homomorphic multiplication algorithm \(\text{NFHE.Mult}(C_{1},C_{2})\). Let \(\mathbf{a}\) and \(\mathbf{b}\) be vectors on \(\mathbb{Z}_{q}^{k}\). \(k\) is a positive integer, \(q\) is a modulus, and \(p\) is a power of \(2\). \(t=\left\lceil\log_{p}q\right\rceil\), and \(N=kt\). The definition of each function is shown in the following formula. \[\text{mbDpt}(\mathbf{a})=\mathbf{a}^{\prime}=(a_{1,1},\cdots,a_{1,t},\cdots,a_{k,1}, \cdots,a_{k,t})\in\mathbb{Z}_{p}^{N}\]  
where \(\mathbf{a}^{\prime}\) is an \(N\)-dimensional vector, \(a_{i}=\sum\limits_{j=1}^{t}a_{i,j}p^{j-1}\), \(a_{i,j}\in\mathbb{Z}_{p}\). \[\text{mbDpt}^{(-1)}(\mathbf{a}^{\prime})=\left(\sum p^{j}\cdot a_{1,j},\cdots,\sum p ^{j}\cdot a_{k,j}\right)\]  
\[\text{mbFlatten}(\mathbf{a}^{\prime})=\text{mbDpt}(\text{mbDpt}^{(-1)}(\mathbf{a}^{ \prime}))\]  
\[\text{pofmb}(\mathbf{b})=\left(b_{1},pb_{1},\cdots,p^{t-1}b_{1},\cdots,b_{k},pb_{ k},\cdots,p^{t-1}b_{k}\right)\]  
1. Key generation algorithm \(\text{NFHE.Keygen}(n,q)\). For a positive integer \(n\), the depth of the homomorphic operation is \(l\). Randomly and uniformly select \(\mathbf{A}\overset{\mathcal{R}}{\leftarrow}\mathbb{Z}_{q}^{n\times n}\) from \(\mathbb{Z}_{q}^{n\times n}\), and sample \(\mathbf{s}\) from the discrete Gaussian distribution \(\chi^{n\times l}\) on \(\mathbb{Z}^{n\times l}\). In addition, \(\mathbf{e}\leftarrow\chi^{n}\). The public key is \(pk=(\mathbf{A},\mathbf{b}=\mathbf{A}\cdot\mathbf{s}+\mathbf{e})\in\mathbb{Z}_{q}^{n\times n} \times\mathbb{Z}_{q}^{n}\), and the private key is \(\mathbf{sk}=\left( \begin{array}{c}-\mathbf{s}\\ 1\end{array} \right)\in\mathbb{Z}_{q}^{n+1}\). 2. Encryption algorithm \(\text{NFHE.Encrypt}(pk,\mu)\). For the plain-text \(\mu\in\{0,1\}\) to be encrypted, randomly selecting \(\mathbf{r}_{i}\), \(e_{i,1}\leftarrow\chi^{n}\) and \(e_{i,2}\leftarrow\chi\), \(i=1,\cdots,(n+1)\cdot t\), calculate \(C_{i,1}=\mathbf{A}^{T}\cdot\mathbf{r}_{i}+e_{i,1}\in\mathbb{Z}_{q}^{n}\) and \(C_{i,2}=\mathbf{b}^{T}\cdot\mathbf{r}_{2}+e_{i,2}\in\mathbb{Z}_{q}\).