Dynamic Multi-Key FHE in Asymmetric Key Setting From LWE

Multi-key Fully homomorphic encryption (MFHE) schemes allow computation on the encrypted data under different keys. However, traditional multi-key FHE schemes based on Learning with errors (LWE) have the undesirable property that is the number of keys has to be fixed in advance. A dynamic multi-key FHE scheme is the most versatile variant which the information about the participants is not required before key generation. To support further homomorphic computation on extended ciphertexts and ciphertexts encrypted under additional keys, Peikert and Shiehian (TCC '16) proposed a leveled dynamic multi-key FHE scheme. Nevertheless, it introduces the circular-security assumption for the LWE parameters to ensure its security, which provides weaker security to the scheme. The problem of how to construct a LWE-based dynamic multi-key FHE scheme is still open. To address the above problem, in this work, we present a dynamic multi-key FHE scheme based on the LWE assumption in public key setting. The ciphertext can be extended and performed homomorphic evaluation with the ciphertexts encrypted under additional keys. Compared with current constructions, our proposed method requires fewer "local" memory and the process of ciphertext extension is distributed. Our proposed method provides a new way to extend the ciphertext such that the ciphertext homomorphism computation is more efficient. Our scheme is proven to be secure under standard LWE assumptions without using the circular-security assumption.