# Efficient Multi-Identity Full Homomorphic Encryption Scheme on Lattice
## 3 Identity-Based Encryption Scheme
### Construction  
The basic parameter definition of the scheme: Let \(n\) as security parameter, \(q=q(n)\) as modulus, \(m=O(n\log q)\), randomly uniform matrix \(\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}\) and its corresponding trapdoor \(\mathbf{R}\in\mathbb{Z}^{\overline{m}\times w}\), where \(\overline{m}=m-nk,w=nk,k=\lceil\log q\rceil,m^{\prime}=m+1\); Construct a gadget matrix \(\mathbf{G}=\mathbf{I}_{n}\otimes\mathbf{g}^{\mathsf{T}}\in\mathbb{Z}^{n\times w}\) for \(\mathbf{g}^{\mathsf{T}}=\left[1,2^{1},2^{2},\ldots,2^{k-1}\right]\in\mathbb{Z}_{q }^{k}\) and \(\mathbf{I}_{n}\) is an \(n\times n\) identity matrix; encoding function with FRD (full-rank differences) \(\mathbf{H}:\mathbb{Z}_{q}^{n}\rightarrow\mathbb{Z}_{q}^{n\times n}\).  
* **IBE.Setup\((1^{n})\)**: : Input the security parameter \(n\) and generate the basic parameter \(q=q(n),m=O(n\log q)\). Randomly and uniformly choose a matrix \(\overline{\mathbf{A}}\in\mathbb{Z}_{q}^{n\times\overline{m}}\) and an n-dimensional vector \(\mathbf{u}\in\mathbb{Z}_{q}^{n}\). Run the trapdoor generation algorithm \(\text{{\bf TrapGen}}(1^{n},1^{m},q)\) to generate matrix \(\mathbf{A}=\left[\overline{\mathbf{A}}\right]-\overline{\mathbf{A}}\mathbf{R}\big{]}\in \mathbb{Z}_{q}^{n\times m}\) and its trapdoor matrix \(\mathbf{R}\in\mathbb{Z}^{\overline{m}\times w}\). Output master public key \(MPK=(\mathbf{A},\mathbf{u})\) and master secret key \(MSK=\mathbf{R}\).
* **IBE.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}\). Using FRD encoding function \(\mathbf{H}:\mathbb{Z}_{q}^{n}\rightarrow\mathbb{Z}_{q}^{n\times n}\), map each user's \(id\) to an invertible matrix \(\mathbf{H}_{id}\in\mathbb{Z}_{q}^{n\times n}\). Let \(\mathbf{A}_{id}=\mathbf{A}+[\mathbf{0}|\mathbf{H}_{id}\mathbf{G}]=\left[\overline{\mathbf{A}}|\mathbf{H} _{id}\mathbf{G}-\overline{\mathbf{A}}\mathbf{R}\right]\in\mathbb{Z}_{q}^{n\times m}\), run the sampling algorithm \(\text{{\bf SampleD}}(\mathbf{A}_{id},\mathbf{R},\mathbf{u},\sigma)\) to generate secret key \(\mathbf{t}_{id}\in\mathbb{Z}_{q}^{m}\) corresponding to each user's \(id\), satisfying \(\mathbf{A}_{id}\mathbf{t}_{id}=\mathbf{u}\) mod \(q\). Set \(\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\).
* **IBE.Enc\((MPK,id,\mathbf{b})\)**: : Input the master public key \(MPK\), user's identity vector \(id\in\mathbb{Z}_{q}^{n}\) and encrypted plaintext message \(\mathbf{b}\in\{0,1\}\). Let \(\mu=\left(\mathbf{b}_{2}^{\frac{q}{2}},0,\ldots,0\right)\in\mathbb{Z}_{q}^{m^{ \prime}}\). Randomly choose a uniform vector \(\mathbf{y}\stackrel{{\$}}{{\leftarrow}}\{0,1\}^{n}\) and an error vector \(\mathbf{e}\stackrel{{\$}}{{\leftarrow}}\chi_{\mathbf{y}_{a}}^{m^{ \prime}}\) according to the LWE error distribution. Output ciphertext vector \(\mathbf{c}_{id}=\mathbf{A}_{id}^{\mathsf{T}}\mathbf{y}+\mu+\mathbf{e}\in\mathbb{Z}_{q}^{m^{ \prime}}\).
* **IBE.Dec\((MPK,\mathbf{s}_{id},\mathbf{c}_{id})\)**: : Input the master public key \(MPK\), user's secret key \(\mathbf{s}_{id}\) and ciphertext \(\mathbf{c}_{id}\) to decrypt. Compute \(\mathbf{b}^{\prime}=\mathbf{s}_{id}^{\mathsf{T}}\cdot\mathbf{c}_{id}\in\mathbb{Z}_{q}\). If \(\left\|\mathbf{b}^{\prime}-\left|\frac{q}{2}\right|\right|<\left|\frac{q}{4}\right|\), output \(\mathbf{b}=1\); If \(\left\|\mathbf{b}^{\prime}\right\|<\left|\frac{q}{4}\right|\), output \(\mathbf{b}=0\).