# A Compact Multi-Identity Fully Homomorphic Encryption Scheme Without Fresh Ciphertexts
## 5 Multi-Identity Full Homomorphic Encryption Scheme
### The Decomposition Method  
Previous MIBFHE schemes required the IBFHE encryption algorithm to generate fresh ciphertexts for homomorphic operations. These fresh ciphertexts were then extended using the Mask System technique to produce extended ciphertexts that support multi-identity operations.In contrast, the decomposition method can directly extend the ciphertexts of the IBE scheme into extended ciphertexts that support multi-identity homomorphic operations, eliminating the need for the intermediate step of generating fresh ciphertexts. Before introducing the decomposition method, we will briefly outline the ciphertext extension approach using the Mask System. Assume there are \((D=2)\) participants, and any number of participants \(D\) can be analogously processed using this method. Suppose in the IBFHE scheme, under participant identities \(id_{1}\) and \(id_{2}\) the fresh ciphertexts \(\mathbf{C}_{1}\) and \(\mathbf{C}_{2}\) are obtained by encrypting plaintext bit messages \(msg_{1}\) and \(msg_{2}\), respectively. Here, identities \(id_{1}\) and \(id_{2}\) correspond to private keys \(\mathbf{sk}_{1}\) and \(\mathbf{sk}_{2}\), which satisfy \(\mathbf{sk}_{1}^{T}\mathbf{C}_{1}=msg_{1}\mathbf{sk}_{1}^{T}\mathbf{M}+ \mathbf{e}_{1}\) and \(\mathbf{sk}_{2}^{T}\mathbf{C}_{2}=msg_{2}\mathbf{sk}_{2}^{T}\mathbf{M}+ \mathbf{e}_{2}\) and \(\mathbf{M}\) represents the preimage matrix, satisfying \(\mathbf{MM}^{-1}(\mathbf{A})=\mathbf{A}\). By expanding the ciphertexts \(\mathbf{C}_{1}\), \(\mathbf{C}_{2}\in\mathbb{Z}_{Q}^{m^{\prime}\times N}\) according to the number of participants \(D\), they become extended ciphertexts \(\mathbf{\hat{C}}_{1},\mathbf{\hat{C}}_{2}\in\mathbb{Z}_{Q}^{2m^{\prime}\times 2N}\), satisfying  
\[\left[\mathbf{sk}_{1}^{T},\mathbf{sk}_{2}^{T}\right]\mathbf{\hat{C}}_{1}=msg_ {1}\left[\mathbf{sk}_{1}^{T},\mathbf{sk}_{2}^{T}\right] \begin{bmatrix} \mathbf{M}&0\\ 0&\mathbf{M}\end{bmatrix} +\text{error},\]  
\[\left[\mathbf{sk}_{1}^{T},\mathbf{sk}_{2}^{T}\right]\mathbf{\hat{C}}_{2}=msg_ {2}\left[\mathbf{sk}_{1}^{T},\mathbf{sk}_{2}^{T}\right] \begin{bmatrix} \mathbf{M}&0\\ 0&\mathbf{M}\end{bmatrix} +\text{error}.\]  
The general method for converting a IBFHE scheme into a MIBFHE scheme involves expanding the ciphertext matrix, originally encrypted under a single identity, into a general matrix with dimensions \(Dm^{\prime}\times DN\), where \(N=m^{\prime}\,\log q\). In this way, the extended ciphertexts \(\mathbf{\hat{C}}_{1}\) and \(\mathbf{\hat{C}}_{2}\) corresponding to \(id_{1}\) and \(id_{2}\), respectively, both have dimensions \(2m^{\prime}\times 2N\). Homomorphic operations can be performed by inputting \(\mathbf{\hat{C}}_{1}\) and \(\mathbf{\hat{C}}_{2}\) into a binary logic circuit \(f\). Previous MIBFHE schemes required the IBFHE encryption algorithm to generate fresh ciphertexts \(\mathbf{C}\) for homomorphic operations. These fresh ciphertexts were then extended using the Mask System technique to produce extended ciphertexts \(\mathbf{\hat{C}}\) that support multi-identity operations. Next, we describe using the decomposition method to extend ciphertexts. First, we restructure the form of the extended ciphertext and decompose the new ciphertext into two parts. The new ciphertext can be defined as: \(\mathbf{C}=\mathbf{AR}+msg\mathbf{F}_{n}\). The first part is a combination of the public key matrix \(\mathbf{A}\) and the trapdoor \(\mathbf{R}\), and the second part is a combination of the plaintext \(msg\) and the public matrix \(\mathbf{F}\). With this ciphertext form, the second part of the new ciphertext can be directly extended during decryption. The method of ciphertext extension is no longer to extend the entire ciphertext \(\mathbf{C}\rightarrow\mathbf{\hat{C}}\), but to extend the first and second parts of the ciphertext separately. Adding these two parts together naturally gives us the extended ciphertext we desire.