Enhancing Multi-Key Fully Homomorphic Encryption with Efficient Key Switching and Batched Multi-Hop Computations - Liang Zhou; Ruwei Huang; Bingbing Wang (Applied Sciences)
Multi-Key Fully Homomorphic Encryption (MKFHE) offers a powerful solution for secure multi-party computations, where data encrypted under different keys can be jointly computed without decryption. However, existing MKFHE schemes still face challenges such as large parameter sizes, inefficient evaluation key generation, complex homomorphic multiplication processes, and limited scalability in multi-hop scenarios. In this paper, we propose an enhanced multi-hop MKFHE scheme based on the Brakerski-Gentry-Vaikuntanathan (BGV) framework. Our approach eliminates the need for an auxiliary Gentry-Sahai-Waters (GSW)-type scheme, simplifying the design and significantly reducing the public key size. We propose novel algorithms for evaluation key generation and key switching that simplify the computation while allowing each party to independently precompute and share its evaluation keys, thereby reducing both computational overhead and storage costs. Additionally, we combine the tensor product and key switching processes through homomorphic gadget decomposition, developing a new homomorphic multiplication algorithm and achieving linear complexity with respect to the number of parties. Furthermore, by leveraging the Polynomial Chinese Remainder Theorem (Polynomial CRT), we design a ciphertext packing technique that transforms our BGV-type MKFHE scheme into a batched scheme with improved amortized performance. Our schemes feature stronger multi-hop properties and operate without requiring a predefined maximum number of parties, offering enhanced flexibility and scalability compared to existing similar schemes.