# A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts
## 5 Multi-Identity Full Homomorphic Encryption Scheme
### Our MIBFHE Construction  
The WZ-MIBFHE scheme is composed of five components: **MIBFHE.Setup**, **MIBFHE.Extract**, **MIBFHE.Enc**, **MIBFHE.Eval**, and **MIBFHE.Dec**. The basic parameters of the scheme are defined as follows: Let \(\lambda\) be the security parameter, \(Q=pq\) be the modulus, \(m=O(n\log q)\), \(\mathbf{A}\in\mathbb{Z}_{Q}^{n\times m}\) be a uniformly random matrix, and \(\mathbf{R}\in\mathbb{Z}^{m_{1}\times n\omega}\) be its trapdoor, where \(m_{1}=n\log q\) and \(m=m_{1}+n\omega\). 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\left[1,b^{1},b^{2},\ldots,b^{\omega-1}\right]\in\mathbb{ Z}_{Q}^{1\times\omega}\), \(\mathbf{I}_{n}\) is an \(n\times n\) identity matrix, and \(\omega=\log_{b}q\). Let \(m^{\prime}=m+1\). 1. **MIBFHE.Setup\(\left(1^{\lambda},1^{L},1^{D}\right)\)**: Takes as input the security parameter \(\lambda\), the maximum circuit depth \(L\) for homomorphic operations, and the maximum number of users \(D\) allowed in the scheme. Execute **IBE.Setup** and output \(MPK=(\mathbf{A},\mathbf{H})\) and \(MSK=\mathbf{R}\). 2. **MIBFHE.Extract\((MPK,MSK,\left[id_{i}\right])\)**: Input \(MPK\), \(MSK\), and \(\left[id_{i}\right]_{i\in[D]}\in\mathbb{Z}_{Q}^{m\times 1}\). Run **IBE.Extract** to sequentially generate the private keys \(\mathbf{sk}_{id_{1}},\ldots,\mathbf{sk}_{id_{D}}\) corresponding to the identities \(id_{1},\ldots,id_{D}\), and the corresponding identity public key matrices \(\mathbf{A}_{id_{1}}^{{}^{\prime}},\ldots,\mathbf{A}_{id_{D}}^{{}^{\prime}}\). Output the private keys set \(\left\{\mathbf{sk}_{id_{i}}\right\}_{i\in[D]}\) and the identity public key matrices set \(\left\{\mathbf{A}_{id_{i}}^{{}^{\prime}}\right\}_{i\in[D]}\). 3. **MIBFHE.Enc\((MPK,\left\{id_{i}\right\},msg)\)**: Input \(MPK\), the user identity vectors \(\left\{id_{i}\right\}_{i\in[D]}\), and the plaintext \(msg\in\left\{0,1\right\}\). Let \(\hat{\mathbf{sk}}_{id}=\left(\mathbf{sk}_{id_{1}},\ldots,\mathbf{sk}_{id_{D}} \right)\in\mathbb{Z}_{Q}^{Dm^{\prime}}\) be the concatenation of the private keys corresponding to the \(D\) identities. Select a series of matrices to compute the extended ciphertext \(\hat{\mathbf{C}}_{id_{i}}=\mathbf{X}_{id_{i}}+\mathbf{Y}_{id_{i}}\in\mathbb{ Z}_{q}^{D(m\times 1)\times D(m\times 1)\omega}\). First, compute \(\mathbf{X}_{id_{i}}\): \[\mathbf{X}_{id_{i}}= \begin{bmatrix}\mathbf{A}_{id_{i}}\overset{\sim}{\mathbf{M} }_{i}^{1}&&\cdots&&0\\ \vdots&\ddots&&\\ \mathbf{A}_{id_{i}}\overset{\sim}{\mathbf{M}}_{i}&\cdots&\mathbf{A}_{id_{i}} \overset{\sim}{\mathbf{M}}_{i}^{i}&\cdots&\mathbf{A}_{id_{i}}\overset{\sim}{ \mathbf{M}}_{i}^{D}\\ \vdots&&&\ddots&\\ 0&&0&&\mathbf{A}_{id_{i}}\overset{\sim}{\mathbf{M}}_{i}^{D}\end{bmatrix} \] (1) where \(\left(\overset{\sim}{\mathbf{M}}_{i}^{1},\overset{\sim}{\mathbf{M}}_{i}^{2}, \cdots,\overset{\sim}{\mathbf{M}}_{i}^{D}\right)\in\left\{0,1\right\}^{n\times m ^{\prime}\omega}\) are random matrices. Compute: \[\mathbf{sk}_{id_{i}}\mathbf{A}_{id_{j}}^{{}^{\prime}}+\mathbf{sk}_{id_{i}} \mathbf{A}_{id_{i}}^{{}^{\prime}} =\left(-1,\mathbf{t}_{id_{i}}^{T}\right) \begin{pmatrix}\mathbf{u}_ {id_{j}}^{T}\\ \mathbf{A}^{T}\end{pmatrix} +\left(-1,\mathbf{t}_{id_{j}}^{T}\right) \begin{pmatrix} \mathbf{u}_{id_{i}}^{T}\\ \mathbf{A}^{T}\end{pmatrix}