# Efficient Multi-Identity Full Homomorphic Encryption Scheme on Lattice
## 4 Identity-Based Full Homomorphic Encryption Scheme
### Construction  
The basic parameter definition of the scheme: Let \(n\) as security parameter, \(\mathbf{L}\) represents the maximum depth of homomorphic calculation allowed for the circuit, \(q=q(n,\mathbf{L})\) is a sufficiently large prime, and \(m,m^{\prime},\overline{m},w,k\) and FRD encoding function \(\mathbf{H}\) are the same as the definitions in the above IBE encryption scheme. Define \(N=(m+1)k\). We construct another gadget matrix \(\mathbf{M}=\mathbf{I}_{m^{\prime}}\otimes\mathbf{g}^{\mathrm{T}}\in\mathbb{Z}^{m^{\prime }\times N}\), where \(\mathbf{g}^{T}=\left[1,2^{1},2^{2},\ldots,2^{k-1}\right]\in\mathbb{Z}_{q}^{k}\) and \(\mathbf{I}_{m^{\prime}}\) is a \(m^{\prime}\times m^{\prime}\) identity matrix. According to Lemma 2, for any matrix \(\mathbf{A}\in\mathbb{Z}_{q}^{m^{\prime}\times N}\), there exists a function \(\mathbf{M}^{-1}(\cdot)\) such that \(\mathbf{M}^{-1}(\mathbf{A})\in\{0,1\}^{N\times N}\), satisfying \(\mathbf{M}\mathbf{M}^{-1}(\mathbf{A})=\mathbf{A}\). * **IBFHE.Setup\(\left(1^{n},1^{L}\right)\)** : Input the security parameter \(n\) and the maximum depth \(\mathbf{L}\) that the circuit allows homomorphic operations. Run the **IBE.Setup** algorithm to generate matrix \(\mathbf{A}=\left[\overline{\mathbf{A}}|-\overline{\mathbf{A}}\overline{\mathbf{R}}\right] \in\mathbb{Z}_{q}^{n\times m}\). Output the master public key \(MPK=(\mathbf{A},\mathbf{u})\) and the master secret key \(MSK=\mathbf{R}\). * **IBFHE.Extract\((MPK,MSK,id)\)** : Input the master public key \(MPK\), master secret key \(MSK\), and user's identity vector \(id\in\mathbb{Z}_{q}^{n}\). Run the **IBE.Extract** algorithm to generate matrix \(\mathbf{A}_{id}^{{}^{\prime}}=\left[\mathbf{u}\middle|\mathbf{A}_{id}\right]\in\mathbb{Z }_{q}^{n\times m^{\prime}}\). Output secret key \(\mathbf{s}_{id}=(1,-\mathbf{t}_{id})\in\mathbb{Z}_{q}^{m^{\prime}}\), satisfying \(\mathbf{A}_{id}^{{}^{\prime}}\mathbf{s}_{id}=0\)_mod_\(q\). * **IBFHE.Enc\((MPK,id,\mu)\)** : Input the master public key \(MPK\), user's identity vector \(id\in\mathbb{Z}_{q}^{n}\) and encrypted plaintext message \(\mu\in\{0,1\}\). Randomly choose uniform vectors \(\mathbf{y}_{i}\stackrel{{\xi}}{{\leftarrow}}\{0,1\}^{n}\) and error vectors \(\mathbf{e}_{i}\stackrel{{\xi}}{{\leftarrow}}\chi_{\overline{\mathbf{v}}_{ \mathbf{v}}_{\mathbf{v}}}^{m^{\prime}}\) according to the LWE error distribution. N vectors \(\mathbf{y}_{i}\) are connected to form the matrix \(\mathbf{Y}=\left[\mathbf{y}_{1},\ldots,\mathbf{y}_{N}\right]\in\mathbb{Z}^{n\times N}\), and N vectors \(\mathbf{e}_{i}\) are connected to form the matrix \(\mathbf{E}=\left[\mathbf{e}_{1},\ldots,\mathbf{e}_{N}\right]\in\mathbb{Z}_{q}^{m^{\prime }\times N}\), where \(i\in[N]\). Output the ciphertext matrix \(\mathbf{C}=A_{id}^{m^{\prime}}\mathbf{Y}+\mu\mathbf{M}+\mathbf{E}\in\mathbb{Z}_{q}^{m^{\prime }\times N}\). * **IBFHE.Eval\((MPK,f,\left(\mathbf{C}_{1},\ldots,\mathbf{C}_{t}\right))\)** : Input the master public key \(MPK\), Boolean circuit \(f\), and ciphertext \(\mathbf{C}_{1},\ldots,\mathbf{C}_{t}\) which are the different ciphertext of the same \(id\) with secret key \(\mathbf{s}_{id}\). Output the operation ciphertext \(\mathbf{C}=f(\mathbf{C}_{1},\ldots,\mathbf{C}_{t})\), where the homomorphic addition is \(\mathbf{C}_{Add}=\mathbf{C}_{1}+\mathbf{C}_{2}\) and the homomorphic multiplication is \(\mathbf{C}_{Mult}=\mathbf{C}_{1}\mathbf{M}^{-1}(\mathbf{C}_{2})\). According to the definitions of addition and multiplication, the homomorphic NAND gate operation is defined as \(\mathbf{C}_{NAND}=\mathbf{M}-\mathbf{C}_{1}\mathbf{M}^{-1}(\mathbf{C}_{2})\). \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Scheme** & **Dimension** & **Ciphertext** & **Public Key** & **Secret Key** & **Gaussian Parameter** \\ \hline
[26] & \(6n\log q\) & \(2m+1\) & \(n\times(3m+1)\) & \(m\times m\) & \(m\omega(\log n)\) \\ Ours-IBE & \(2n\log q\) & \(m+1\) & \(n\times(m+1)\) & \((m\times m)/4\) & \(\sqrt{m}\omega(\log n)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparison of main parameters of IBE scheme.