# A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts
## 4 Modified Identity-Based Encryption Scheme
### Modified IBE Construction  
The parameters of the scheme are defined as follows: difine security parameter as \(\lambda\), \(n=n(\lambda)\), and Let \(Q=p\cdot q\) represent the modulus, where \(p\) and \(q\) are both positive integers. \(m_{1}=n\text{log}\,q\), \(m=m_{1}+n\omega\), \(m^{\prime}=m+1\), and \(\omega=\text{log}_{q}\,q\). Let \(B_{\chi}\) be the bounded error distribution \(\chi=\chi(\lambda)\). Construct an gadget matrix \(\mathbf{F}=\mathbf{I}_{n}\otimes\mathbf{f}^{T}\in\mathbb{Z}^{n\times n\omega}\), where \(\mathbf{f}^{T}=p\cdot\left[1,b^{1},b^{2},\dots,b^{\omega-1}\right]\in\mathbb{ Z}_{Q}^{1\times\omega}\), \(\mathbf{I}_{n}\) is an \(n\times n\) identity matrix, and \(b\) is a small integer. The IBE scheme constructed in this chapter consists of four parts: **IBE.Setup**, **IBE.Extract**, **IBE.Enc**, **IBE.Dec**. 1. **IBE.Setup\((1^{\lambda})\)**: Input the security parameter \(\lambda\), choose \(n=n(\lambda)\), and the error distribution \(\chi=\chi(\lambda)\). Generate the basic parameters \(Q=pq\), \(m=m_{1}+n\omega\). Uniformly select an invertible matrix \(\mathbf{H}\stackrel{{\mathcal{S}}}{{\leftarrow}}\mathbb{Z}_{Q}^ {n\times n}\), a uniformly random matrix \(\overline{\mathbf{A}}\stackrel{{\mathcal{S}}}{{\leftarrow}} \mathbb{Z}_{Q}^{n\times m_{1}}\) and a collision-resistant hash function \(H\): \(\mathbb{Z}_{Q}^{*}\rightarrow\mathbb{Z}_{Q}^{n}\). Sample the trapdoor matrix \(\mathbf{R}\leftarrow\ D_{R^{m_{1}\times m\omega},\sigma}\), 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}\), and provide the master public key \(MPK=(\mathbf{A},\mathbf{H})\) along with the master private key \(MSK=\mathbf{R}\). For different identities, the matrix \(\mathbf{A}\) remains unchanged. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Scheme** & **Dimension** & **Master Private Key** & **Identity Public Key** & **Ciphertext Size** \\  & & **Size** & **Size** & **Size** \\ \hline ABB10 [18] & \(6n\text{log}\,q\) & \(36n^{2}\text{log}^{2}\,q\) & \(18n^{2}\text{log}\,q+n\) & \(2m+1\) \\ Fan [22] & \(2n\text{log}\,q\) & \(n^{2}\text{log}^{2}\,q\) & \(2n^{2}\text{log}\,q+n\) & \(m+1\) \\ Ours & \(n\,\text{log}\,q+n\,\text{log}\,q\) & \(n\text{log}\,q\times n\,\text{log}\,q\) & \(n^{2}\,\text{log}\,q+n^{2}\,\text{log}\,q+n\) & \(m+1\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Primary Comparison of Parameters in Similar Schemes. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Scheme** & **Dimension** & **Master Private Key** & **Identity Public Key** & **Ciphertext Size** \\  & & **Size** & **Size** & **Size** \\ \hline ABB10 [18] & \(48n\) & \(2304\ n^{2}\) & \(432n^{2}+n\) & \(2m+1\) \\ Fan [22] & \(16n\) & \(256n^{2}\) & \(48n^{2}+n\) & \(m+1\) \\ Ours & \(9.75n\) & \(14n^{2}\) & \(9.75n^{2}+n\) & \(m+1\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Comparison of Instantiated Parameters. * \(\mathbf{IBE.Extract}(MPK,MSK,id)\): Provide the master public key \(MPK\), the master private key \(MSK\), and the user identity vector \(id\in\mathbb{Z}_{Q}^{*}\) as input. Use the hash function \(H:\mathbb{Z}_{Q}^{*}\rightarrow\mathbb{Z}_{Q}^{m}\) to map each user identity \(id\) into an identity vector \(\mathbf{u}_{id}\in\mathbb{Z}_{Q}^{n}\). Let the user identity public key matrix be \(\mathbf{A}_{id}=\mathbf{A}+[0\parallel\mathbf{HG}]=\left[\mathbf{A} \parallel\mathbf{HF}-\overline{\mathbf{A}}\mathbf{R}\right]\in\mathbb{Z}_{Q}^ {m\times m}\). For each different identity, the matrix \(\mathbf{A}_{id}\) remains the same. Run \(\mathbf{ApproxPreSample}(\mathbf{A}_{id},\mathbf{R},\mathbf{u}_{id},\sigma)\) to generate a sampling vector \(\mathbf{t}_{id}\in\mathbb{Z}_{Q}^{m}\) that follows the discrete Gaussian distribution \(\mathcal{D}_{\Lambda_{Q}^{n}(\mathbf{A}_{id}),\sigma}\), satisfying \(\mathbf{A}_{id}\mathbf{t}_{id}=\mathbf{u}_{id}-\mathbf{e}_{app}\)_mod_\(Q\).