# A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts
## 3 Identity-Based Encryption Scheme
### Our IBE Construction  
The parameters of the scheme are defined as follows: Let \(\lambda\) be the security parameter, \(Q=pq\) be the modulus where \(p\) and \(q\) are positive integers, and let \(m_{1}=n\log q\), \(m=m_{1}+n\omega\), \(m^{\prime}=m+1\), and \(\omega=\log_{b}q\). Let \(B_{\chi}\) be the bounded error distribution, \(\chi=\chi(\lambda)\). Construct a gadget matrix \(\mathbf{F}=\mathbf{I}_{n}\otimes\mathbf{f}^{T}\in\mathbb{Z}^{n\times n\omega}\) where \(\mathbf{f}^{T}=p\cdot[1,b^{1},b^{2},\ldots,b^{\omega-1}]\in\mathbb{Z}_{Q}^{1 \times\omega}\), \(\mathbf{I}_{n}\) is an \(n\times n\) identity matrix, and \(b\) is a small integer. The identity encoding Full-Rank Differences (FRD) function \(\mathbf{H}:\mathbb{Z}_{Q}^{\times 1}\rightarrow\mathbb{Z}_{Q}^{n\times n}\) satisfies \(\mathbf{H}_{id_{1}}-\mathbf{H}_{id_{2}}\
eq 0\). The IBE scheme constructed in this paper consists of four parts: the initialization algorithm **IBE.Setup**, the key generation algorithm **IBE.Extract**, the encryption algorithm **IBE.Enc**, and the decryption algorithm **IBE.Dec**:  
1. \(\textbf{IBE.Setup}(1^{\lambda})\): Input the security parameter \(\lambda\), choose \(n=n(\lambda)\), error distribution \(\chi=\chi(\lambda)\). Let \(Q=pq\) and \(m=m_{1}+n\omega\). Uniformly and randomly select an \(n\)-dimensional vector \(\mathbf{u}\stackrel{{\xi}}{{\leftarrow}}\mathbb{Z}_{Q}^{n\times 1}\), a matrix \(\overline{\mathbf{A}}\stackrel{{\xi}}{{\leftarrow}}\mathbb{Z}_{Q} ^{n\times m_{1}}\), and generate a uniformly random matrix \(\mathbf{A}=\left[\overline{\mathbf{A}}\parallel-\overline{\mathbf{A}}\mathbf{ R}\right]\in\mathbb{Z}_{Q}^{n\times m}\) with a trapdoor matrix \(\mathbf{R}\in\mathbb{Z}_{Q}^{m_{1}\times n\omega}\). Outputs \(MPK=(\mathbf{A},\mathbf{u})\) as the master public key and \(MSK=\mathbf{R}\) as the master secret key. 2. \(\textbf{IBE.Extract}(MPK,MSK,id)\): Provide the \(MPK\), \(MSK\), and the user identity vector \(id\in\mathbb{Z}_{Q}^{n\times 1}\) as input. Use the identity encoding FRD function \(\mathbf{H}:\mathbb{Z}_{Q}^{n\times 1}\rightarrow\mathbb{Z}_{Q}^{n\times n}\) to generate an invertible matrix \(\mathbf{H}_{id}\in\mathbb{Z}_{Q}^{n\times n}\) corresponding to each identity \(id\). Let the user identity public key matrix be \(\mathbf{A}_{id}=\mathbf{A}+\left[0\parallel\mathbf{H}\mathbf{G}\right]=\left[ \mathbf{A}\parallel\mathbf{H}\mathbf{F}-\overline{\mathbf{A}}\mathbf{R} \right]\in\mathbb{Z}_{Q}^{n\times m}\). Run the preimage sampling algorithm \(\textbf{ApproxPreSamp}(\mathbf{A}_{id},\mathbf{R},\mathbf{u},\sigma)\) to generate a sampling vector \(\mathbf{t}_{id}\in\mathbb{Z}_{Q}^{m\times 1}\) that follows the discrete Gaussian distribution \(\mathcal{D}_{\overline{\mathbf{A}}_{id}^{\prime}(\mathbf{A}_{id}),\sigma}\), satisfying \(\mathbf{A}_{id}\mathbf{t}_{id}=\mathbf{u}_{id}-\mathbf{e}_{app}\)\(mod\)\(Q\), where \(\mathbf{e}_{app}\) is the approximation error of the trapdoor. Let \(\mathbf{A}_{id}^{\prime}=\left[\mathbf{u}\parallel\mathbf{A}_{id}\right]\in \mathbb{Z}_{Q}^{n\times m^{\prime}}\). Output the private key for each user identity \(\mathbf{s}\mathbf{k}_{id}=\left(1,-\mathbf{t}_{id}\right)\in\mathbb{Z}_{Q}^{ m\times 1}\), satisfying \(\mathbf{A}_{id}^{\prime}\mathbf{s}\mathbf{k}_{id}=\mathbf{e}_{app}\)\(mod\)\(Q\). 3. \(\textbf{IBE.Enc}(MPK,id,msg)\): Provide as input the \(MPK\), user identity \(id\), and a plaintext bit message \(msg\in\left\{0,1\right\}\). Define the vector \(\bar{\mathbf{v}}=\left(msg\cdot\frac{Q}{2},0,\ldots,0\right)\in\mathbb{Z}_{q} ^{m^{\prime}}\). Uniformly and randomly select a vector \(\mathbf{y}\stackrel{{\xi}}{{\leftarrow}}\{0,1\}^{n\times 1}\), and uniformly randomly select an error vector \(\mathbf{e}\stackrel{{\xi}}{{\leftarrow}}\mathcal{N}_{\mathbf{x}} ^{m^{\prime}\times 1}\) from the LWE error distribution, with \(\left\|\mathbf{e}\right\|<B_{\chi}\). Output the ciphertext \(\mathbf{c}_{id}=\mathbf{A}_{id}^{\prime T}\mathbf{y}+\bar{\mathbf{v}}+\mathbf{ e}\in\mathbb{Z}_{Q}^{m^{\prime}\times 1}\). 4.