# A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts
## 3 Identity-Based Encryption Scheme
### Security Analysis
Simulator \(\mathcal{S}\) for the \(LWE_{\lambda,\mathcal{O},\mathcal{X}}\) assumption can use the adversary \(\mathcal{A}\) to distinguish whether the oracle \(\mathcal{O}\) is a truly random oracle \(\mathcal{O}_{\mathsf{S}}\) or a pseudo-random oracle\(\mathcal{O}_{\mathsf{S}}\). The steps for the simulator \(\mathcal{S}\) are as follows:  
**Instance:** The challenger \(\mathcal{C}\) samples \(m_{1}+1\) samples \((\mathbf{u}_{i},\mathbf{v}_{i})\in\mathbb{Z}_{Q}^{n\times 1}\times\mathbb{Z}_{Q}\) from the oracle \(\mathcal{O}\), where \(i=0,1,\ldots,m_{1}\). **Target:** The adversary \(\mathcal{A}\) declares the target identity \(id^{*}\) to be attacked to the challenger \(\mathcal{C}\). **Setup:** The challenger \(\mathcal{C}\) sets up the MPK based on the target identity \(id^{*}\) declared by the adversary \(\mathcal{A}\). 1. The challenger C constructs the matrix \(\ \widetilde{\mathbf{A}}=(\mathbf{u}_{1}\ \parallel\mathbf{u}_{2}\ \parallel\cdots\parallel \mathbf{u}_{m_{1}})\in\mathbb{Z}_{Q}^{n\times m_{1}}\) using the sampled samples. 2. Let \(\mathbf{u}_{0}\) be the public random vector \(\mathbf{u}=\mathbf{u}_{0}\in\mathbb{Z}_{Q}^{n\times 1}\). 3. Choose \(\mathbf{R}\) from the distribution \(\mathcal{D}^{m_{1}\times m\omega}\) and form the matrix \(\mathbf{A}_{1}=-\mathbf{H}_{id^{*}}\mathbf{F}-\widetilde{\mathbf{A}}\mathbf{R}\). 4. Output the public parameters \(\left\{\mathbf{u},\widetilde{\mathbf{A}},\mathbf{A}_{1}\right\}\) to the adversary \(\mathcal{A}\). **Queries 1:** As in Game 2,the challenger \(\mathcal{C}\) provide the adversary \(\mathcal{A}\) with each private key query for \(id\
eq id^{*}\). **Challenge:** The adversary \(\mathcal{A}\) provides the challenge identity \(id^{*}\) associated with the challenge plaintext \(msg^{*}\in\{0,1\}\). The challenger \(\mathcal{C}\) then generates the challenge ciphertext for the target identity \(id^{*}\) using the following process:  
1. Let \(\mathbf{v}^{*}=(v_{1},\ldots,v_{m_{1}})^{T}\in\mathbb{Z}_{Q}^{m_{1}\times 1}\);
2. Hide the plaintext bit message \(msg^{*}\) with \(c_{0}^{*}=v_{0}+msg^{*}\Big{|}\frac{Q}{2}\Big{|}\);
3. Let \(\mathbf{c}_{1}^{*}= \begin{bmatrix}\mathbf{v}^{*}\\ -\mathbf{R}^{T}\mathbf{v}^{*}+\mathbf{e}\end{bmatrix} \in\mathbb{Z}_{Q}^{m}\), where \(\mathbf{e}\stackrel{{\widetilde{\mathbf{v}}}}{{\leftarrow}} \mathbb{Z}_{Q}^{n\omega}\);
4. Select a random bit \(r\stackrel{{\mathcal{S}}}{{\leftarrow}}\{0,1\}\). If \(r=0\), the challenger sends \(\mathbf{c}^{*}=(\mathbf{c}_{0}^{*},\mathbf{c}_{1}^{*})\) to the adversary \(\mathcal{A}\); if \(r=1\), a vector \(\mathbf{c}_{id}\in\mathbb{Z}_{Q}^{m^{\prime}}\) is uniformly sampled and sent to \(\mathcal{A}\). When \(\mathcal{O}=\mathcal{O}_{s}\), the distribution of \(\mathbf{c}^{*}\) is indistinguishable from the challenge ciphertext in Game 2. By the definition of \(LWE_{\lambda,\mathcal{Q},\mathcal{X}}\), \(\mathbf{v}_{0}=\mathbf{u}_{0}^{T}\mathbf{s}\mathbf{k}+\mathbf{e}_{0}\) and \(\mathbf{v}^{*}=\widetilde{\mathbf{A}}^{-T}\mathbf{s}\mathbf{k}+\mathbf{e}_{1}\). Furthermore, \(\mathbf{A}_{id^{*}}= \begin{bmatrix}\widetilde{\mathbf{A}}\parallel(\mathbf{ H}_{id^{*}}-\mathbf{H}_{id^{*}})\mathbf{F}-\widetilde{\mathbf{A}}\mathbf{R} \end{bmatrix} = \begin{bmatrix}\widetilde{\mathbf{A}}\parallel-\widetilde{ \mathbf{A}}\mathbf{R}\end{bmatrix} \), we get \[\mathbf{c}_{1}^{*}= \begin{bmatrix}\mathbf{v}^{*}\\ -\mathbf{R}^{T}\mathbf{v}^{*}+\mathbf{e}\end{bmatrix} =\mathbf{A}_{id^{*}}^{T} \mathbf{s}\mathbf{k}+ \begin{bmatrix}\mathbf{e}_{1}\\ -\mathbf{R}^{T}\mathbf{e}_{1}+\mathbf{e}\end{bmatrix} \] which is exactly the challenge ciphertext \(\mathbf{c}_{1}\) in Game 2, The part \(\mathbf{c}_{0}^{*}=\mathbf{v}_{0}+msg^{*}\Big{|}\frac{Q}{2}\Big{|}=\mathbf{u}_{ 0}^{T}\mathbf{s}\mathbf{k}+\mathbf{e}_{0}+msg^{*}\Big{|}\frac{Q}{2}\Big{|}\) is the challenge ciphertext \(\mathbf{c}_{0}\), Thus, \(\mathbf{c}^{*}\) is a valid ciphertext for the plaintext bit \(msg^{*}\) associated with the identity \(id^{*}\).