# Efficient Multi-Identity Full Homomorphic Encryption Scheme on Lattice
## 3 Identity-Based Encryption Scheme
### Security Reduction
The steps are as follows:  
**Instance** Challenger \(\mathcal{C}\) requests from \(\mathcal{O}\) and receives \(\overline{m}+1\) samples \((\mathbf{u}_{i},\mathbf{v}_{i})\in\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}\), for \(i=0,1,\ldots,\overline{m}+1\). **Target** Adversary \(\mathcal{A}\) declares to challenger \(\mathcal{C}\) the target identity of the planned attack \(id^{*}\)  
**Setup** Challenger \(\mathcal{C}\) sets \(MPK\) according to the target identity \(id^{*}\). 1. Challenger \(\mathcal{C}\) uses the known samples to construct matrix \(\overline{\mathbf{A}}=(\mathbf{u}_{1},\mathbf{u}_{2},\ldots,\mathbf{u}_{\overline{m}})\in \mathbb{Z}_{q}^{n\times\overline{m}}\). 2. Take \(\mathbf{u}_{0}\) as a common random vector \(\mathbf{u}=\mathbf{u}_{0}\in\mathbb{Z}_{q}^{n}\). 3. Select \(\mathbf{R}\leftarrow\mathcal{D}^{\overline{m}\times w}\) from the distribution \(\mathcal{D}\) and construct the matrix \(\mathbf{A}_{1}=-\mathbf{H}_{id}\cdot\mathbf{G}-\overline{\mathbf{R}}\). 4. Send the common parameter \(\{\mathbf{u},\overline{\mathbf{A}},\mathbf{A}_{1}\}\) to the adversary \(\mathcal{A}\). From Left over Hash lemma [29], for an adversary \(\mathcal{A}\), matrix \(\mathbf{A}_{1}\) is uniformly indistinguishable. **Queries1** Similar to Game2, Challenger \(\mathcal{C}\) responds to each secret key query of adversary \(\mathcal{A}\). **Challenge** The adversary submits challenge plaintext \(\mathbf{b}^{*}\in\{0,1\}\) to challenger \(\mathcal{C}\), and challenger \(\mathcal{C}\) outputs challenge ciphertext \(\mathbf{c}_{id}^{*}\) for target identity \(id^{*}\):  
1. Let \(\mathbf{v}^{*}=(\mathbf{v}_{1},\ldots,\mathbf{v}_{\overline{m}})^{\mathrm{T}}\in\mathbb{Z }_{q}^{n}\). 2. Hide plaintext message \(\mathbf{b}^{*}\) through constructing \(\mathbf{c}_{0}^{*}=\mathbf{v}_{0}+\mathbf{b}^{*}\frac{q}{2}\). 3. Let \(\mathbf{c}_{1}^{*}= \begin{bmatrix}\mathbf{v}^{*}\\ -\mathbf{R}^{\mathrm{T}}\mathbf{v}^{*}+\mathbf{e}^{\prime}\end{bmatrix} \in\mathbb{Z}_{q}^{ m}\),for \(\mathbf{e}^{\prime}\frac{\overline{\mathbf{v}}_{*}}{\mathbb{Z}}_{q}^{w}\). 4. Select random bit \(r\stackrel{{\mathcal{S}}}{{\leftarrow}}\{0,1\}\). When \(r=0\), send \(\mathbf{c}^{*}=\left(\mathbf{c}_{0}^{*},\mathbf{c}_{1}^{*}\right)\) to the adversary \(\mathcal{A}\); when \(r=1\), randomly and uniformly select \(\mathbf{c}_{id}\in\mathbb{Z}_{q}^{n^{\prime}}\) to pass to the adversary \(\mathcal{A}\). **Attention:** When \(\mathcal{O}=\mathcal{O}_{\mathbf{s}}\), the distribution of \(\mathbf{c}^{*}\) is indistinguishable from the challenge ciphertext in Game2. From the definition of the LWE problem, we can know that \(\mathbf{v}^{*}=\overline{\mathbf{A}}^{\mathrm{T}}\mathbf{s}+\mathbf{e}\,\mathbf{A}_{id^{*}}= \left[\overline{\mathbf{A}}|(\mathbf{H}_{id^{*}}-\mathbf{H}_{id^{*}})\,\mathbf{G}-\overline{ \mathbf{A}}\mathbf{R}\right]=\left[\overline{\mathbf{A}}|-\overline{\mathbf{A}}\mathbf{R}\right]\).Thus  
\[\mathbf{c}_{1}^{*}= \begin{bmatrix}\mathbf{v}^{*}\\ -\mathbf{R}^{\mathrm{T}}\mathbf{v}^{*}+\mathbf{e}^{\prime}\end{bmatrix} = \begin{bmatrix} \overline{\mathbf{A}}^{\mathrm{T}}\mathbf{s}+\mathbf{e}\\ -\mathbf{R}^{\mathrm{T}}\left(\overline{\mathbf{A}}^{\mathrm{T}}\mathbf{s}+\mathbf{e}^{\prime }\right)+\mathbf{e}^{\prime}\end{bmatrix} =\mathbf{A}_{id^{*}}^{\mathrm{T}}\mathbf{s}+ \begin{bmatrix}\mathbf{e}\\ -\mathbf{R}^{\mathrm{T}}\mathbf{e}+\mathbf{e}^{\prime}\end{bmatrix} \]  
The right side of the equation is the challenge ciphertext \(\mathbf{c}_{1}\) in Game 2; \(\mathbf{c}_{0}^{*}=\mathbf{u}_{0}^{\mathrm{T}}\mathbf{s}+\mathbf{e}^{\prime}+\mathbf{b}^{*}\lfloor \frac{q}{2}\rfloor\) is the challenge ciphertext \(\mathbf{c}_{0}\) in Game2, for \(\mathbf{e}^{\prime\prime}\frac{\overline{\mathbf{v}}}{\underline{\mathbf{c}}^{*}}\,\, \mathbb{Z}_{q}\). Thus \(\mathbf{c}^{*}\) is a valid ciphertext of \(\mathbf{b}^{*}\) corresponding to identity \(id^{*}\). When \(\mathcal{O}=\mathcal{O}_{\mathbf{S}}\), \(\mathbf{v}_{0}\in\mathbb{Z}_{q}\) and \(\mathbf{v}^{*}\in\mathbb{Z}_{q}^{n\overline{m}}\) are then uniformly selected.