## 2 Preliminaries
### Multi-Key Fully Homomorphic Encryption (MKFHE)  
MKFHE is a cryptographic scheme that extends traditional FHE by enabling computations on ciphertexts encrypted under different keys. In contrast to single-key FHE, which requires all data to be encrypted under the same secret key, MKFHE allows encrypted data from multiple parties, each using its own secret key, to be processed together. This makes MKFHE a more flexible and scalable solution for privacy-preserving computations in multi-party settings.  
An MKFHE scheme consists of five probabilistic polynomial-time (PPT) algorithms: Setup, KeyGen, Enc, Eval, and Dec. These algorithms are described as follows:  
* **Setup:**\(pp\leftarrow\) MKFHE.Setup\(\left(1^{\lambda}\right)\). The setup algorithm takes the security parameter \(\lambda\) as input and outputs the public parameters \(pp\). These public parameters are implicitly used by other algorithms in the scheme.
* **Key Generation:**\((\textbf{pk},\textbf{sk})\leftarrow\) MKFHE.KeyGen\((pp)\). The key generation algorithm takes the public parameters \(pp\) as input and generates a public key **pk** and a secret key **sk** for each participating party. Each party holds its own secret key while sharing the public key.  
* **Encryption:**\(\mathbf{c}\leftarrow\) MKFHE.Enc(\(\mathbf{pk},m\)). The encryption algorithm takes a message \(m\) and the corresponding public key \(\mathbf{pk}\) as inputs, encrypting the message to produce a ciphertext \(\mathbf{c}\).
* **Evaluation:**\(\mathbf{c^{\prime}}\leftarrow\) MKFHE.Eval\(\left(\mathcal{C},\left(\mathbf{pk}_{1},\ldots,\mathbf{pk}_{j}\right),\left( \mathbf{c}_{1},\ldots,\mathbf{c}_{i}\right)\right)\). The evaluation algorithm allows for computations on multiple ciphertexts \(\mathbf{c}_{1},\ldots,\mathbf{c}_{i}\), each encrypted under a (possibly repeated) public key from the set \(\left\{\mathbf{pk}_{1},\ldots,\mathbf{pk}_{j}\right\}\), where \(j\leq i\) denotes the number of distinct public keys involved. It performs homomorphic operations on these ciphertexts based on a given circuit \(\mathcal{C}\), producing a new ciphertext \(\mathbf{c^{\prime}}\) that is the encrypted result of the computation.
* **Decryption:**\(m\leftarrow\) MKFHE.Dec\(\left(\mathbf{c^{\prime}},\left(\mathbf{sk}_{1},\ldots,\mathbf{sk}_{j}\right)\right)\). The decryption algorithm takes a ciphertext \(\mathbf{c^{\prime}}\) and the corresponding secret keys \(\mathbf{sk}_{1},\ldots,\mathbf{sk}_{j}\) for the participating parties as input, decrypting the ciphertext to recover a plaintext message \(m\).  
Each MKFHE ciphertext implicitly contains references to the public keys associated with it. Initially, a ciphertext corresponds to a single key, but as computations proceed with ciphertexts encrypted under different keys, the reference set expands. When decrypting a ciphertext, all associated secret keys must be used.  
**Correctness and security:** An MKFHE scheme is correct if, for any set of ciphertexts \(\mathbf{c}_{1},\ldots,\mathbf{c}_{i}\), the decryption of the result obtained from the homomorphic evaluation matches the result of applying the circuit \(\mathcal{C}\) to the decrypted inputs with an overwhelming probability, i.e.,  
An MKFHE scheme is IND-CPA secure if, for any pair of messages \(m_{1},m_{2}\), the distributions of ciphertexts MKFHE.Enc(\(\mathbf{pk},m_{1}\)) and MKFHE.Enc(\(\mathbf{pk},m_{2}\)) are computationally indistinguishable.