## 1 Introduction
### Related Works  
The first MKFHE scheme was introduced by [PERSON] et al. in 2012 [11]. Their construction enabled homomorphic evaluations over ciphertexts encrypted under different keys, with the computation results jointly decrypted by all participating parties. This approach addressed the challenge of collaborative encrypted computation across multiple users. However, this scheme relied on a non-standard security assumption related to NTRU [21] and suffered from exponential complexity growth with the number of participants, making it impractical for large-scale applications. In 2015, [PERSON] et al. [12] extended the GSW scheme [8] to support a multi-identity (multi-key) setting, constructing the first MKFHE scheme based on the Learning with Errors (LWE) problem [22], thereby establishing its security under a standard security assumption. This work laid the foundation for subsequent optimizations and extensions of MKFHE. [PERSON] et al. [13] later simplified the scheme in [12] and proposed a new ciphertext extension algorithm, allowing for a single-round distributed decryption process for multi-key ciphertexts. This optimization enabled the construction of two-round MPC protocols. However, similar to [12], their scheme was limited to single-hop, meaning that the number of participants in the homomorphic computation had to be predefined. Furthermore, it did not support dynamic joining--once the homomorphic computation was performed, the resulting ciphertexts could not be further computed with ciphertexts from newly added participants. To address this limitation, [PERSON] et al. [14] proposed a multi-hop MKFHE scheme based on the GSW framework, eliminating the need for prior knowledge of parties. The multi-hop nature of the scheme allows the output ciphertexts to continue being computed with ciphertexts from newly joined parties, enabling real-time, dynamic participation. Compared to [13], their approach also significantly reduced ciphertext size, though it still imposed a limitation on the maximum number of participants. Shortly thereafter, [PERSON] and [PERSON] [15] proposed a fully dynamic MKFHE scheme based on the LWE assumption, allowing parties to dynamically join homomorphic computations without requiring a predefined number of participants. Their scheme supported an arbitrary polynomial number of parties and unlimited-depth homomorphic evaluations, with the spatial complexity of ciphertext extension and homomorphic operations growing only linearly with the number of parties. However, it relied on bootstrapping for ciphertextextension, and the generation of bootstrapping keys still required extending encrypted secret keys, significantly degrading efficiency. In 2017, [PERSON] et al. [16] proposed a batched multi-hop MKFHE scheme based on the BGV scheme [5], with security under the standard Ring Learning with Errors (RLWE) assumption [23]. Their scheme allowed ring elements to be encrypted as plaintexts, achieving higher computational efficiency. Additionally, they introduced methods for constructing two-round MPC protocols and threshold decryption protocols. In 2019, [PERSON] et al. [17] optimized the construction in [16], reducing the length of the extended ciphertext by nearly half. They also introduced a directed decryption protocol, enabling extended ciphertexts to be decrypted by specific designated users. This enhancement removed the limitation that only participating parties in the homomorphic evaluation could decrypt the result, thereby giving data owners greater control over access to decrypted information. In the same year, [PERSON] et al. [18] constructed a TFHE-type MKFHE scheme, leveraging the low-latency homomorphic encryption techniques from TFHE [10]. They achieved a reduced concrete complexity, but their scheme did not support the packing technique, thereby resulting in a large expansion rate similar to TFHE. Later, [PERSON] et al. [19] designed multi-key variants of BFV [6; 7] and CKKS [9], optimizing the relinearization (key switching) process in batched MKFHE.