Multi-Key Fully Homomorphic Encryption: removing noise flooding in distributed decryption via the smudging lemma on discrete Gaussian distribution

Xiaokang Dai; Wenyuan Wu; Yong Feng

Paper 2022/055

Multi-Key Fully Homomorphic Encryption: removing noise flooding in distributed decryption via the smudging lemma on discrete Gaussian distribution

Xiaokang Dai, University of Chinese Academy of Sciences, Beijing, 100049 China, Chongqing Key Laboratory of Automated Reasoning and Cognition,Chongqing Institute of Green and Intelligent Technology, Chongqing, 400714, China

Wenyuan Wu, Chongqing Key Laboratory of Automated Reasoning and Cognition,Chongqing Institute of Green and Intelligent Technology, Chongqing, 400714, China

Yong Feng, Chongqing Key Laboratory of Automated Reasoning and Cognition,Chongqing Institute of Green and Intelligent Technology, Chongqing, 400714, China

Abstract

The current Multi-key Fully Homomorphic Encryption (MKFHE) needs to add exponential noise in the distributed decryption phase to ensure the simulatability of partial decryption. Such a large noise causes the ciphertext modulus of the scheme to increase exponentially compared to the Single-key Fully Homomorphic Encryption (FHE), further reducing the efficiency of the scheme and making the hardness problem on the lattice on which the scheme relies have a sub-exponential approximation factor (which means that the security of the scheme is reduced). To address this problem, this paper analyzes in detail the noise in partial decryption of the MKFHE based on the LWE problem. It points out that this part of the noise is composed of private key and the noise in initial ciphertext. Therefore, as long as the encryption scheme is leak-resistant and the noise in partial decryption is independent of the noise in the initial ciphertext, the semantic security of the ciphertext can be guaranteed. In order to make the noise in the initial ciphertext independent of the noise in the partial decryption, this paper proves the smudging lemma on discrete Gaussian distribution and achieves this goal by multiplying the initial ciphertext by a ``dummy" ciphertext with a plaintext of 1. Based on the above method, this paper removes the exponential noise in the distributed decryption phase for the first time and reduces the ciphertext modulus of MKFHE from to as the same level as the FHE.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Multi-key homomorphic encryption Noise flooding Leakage resilient cryptography.
Contact author(s): daixiaokang @ cigit ac cn
wuwenyuan @ cigit ac cn
yongfeng @ cigit ac cn
History: 2025-06-10: last of 27 revisions; 2022-01-18: received; See all versions
Short URL: https://ia.cr/2022/055
License: CC BY

BibTeX

@misc{cryptoeprint:2022/055,
      author = {Xiaokang Dai and Wenyuan Wu and Yong Feng},
      title = {Multi-Key Fully Homomorphic Encryption: removing noise flooding in distributed decryption via the smudging lemma on discrete Gaussian distribution},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/055},
      year = {2022},
      url = {https://eprint.iacr.org/2022/055}
}