Multikey Fully Homomorphic Encryption: Removing Noise Flooding in Distributed Decryption via the Smudging Lemma on Discrete Gaussian Distribution
The current multikey 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 h...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2025-01-01
|
| Series: | IET Information Security |
| Online Access: | http://dx.doi.org/10.1049/ise2/7550044 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850036122138181632 |
|---|---|
| author | Xiaokang Dai Wenyuan Wu Yong Feng |
| author_facet | Xiaokang Dai Wenyuan Wu Yong Feng |
| author_sort | Xiaokang Dai |
| collection | DOAJ |
| description | The current multikey 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 subexponential approximation factor O~n⋅2nL (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 learning with error (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 2ωλL logλ to 2Oλ+L as the same level as the FHE. |
| format | Article |
| id | doaj-art-03822ab02ba64c85bdbc7ef3106064b1 |
| institution | DOAJ |
| issn | 1751-8717 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | IET Information Security |
| spelling | doaj-art-03822ab02ba64c85bdbc7ef3106064b12025-08-20T02:57:17ZengWileyIET Information Security1751-87172025-01-01202510.1049/ise2/7550044Multikey Fully Homomorphic Encryption: Removing Noise Flooding in Distributed Decryption via the Smudging Lemma on Discrete Gaussian DistributionXiaokang Dai0Wenyuan Wu1Yong Feng2Chongqing Key Laboratory of Automated Reasoning and CognitionChongqing Key Laboratory of Automated Reasoning and CognitionChongqing Key Laboratory of Automated Reasoning and CognitionThe current multikey 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 subexponential approximation factor O~n⋅2nL (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 learning with error (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 2ωλL logλ to 2Oλ+L as the same level as the FHE.http://dx.doi.org/10.1049/ise2/7550044 |
| spellingShingle | Xiaokang Dai Wenyuan Wu Yong Feng Multikey Fully Homomorphic Encryption: Removing Noise Flooding in Distributed Decryption via the Smudging Lemma on Discrete Gaussian Distribution IET Information Security |
| title | Multikey Fully Homomorphic Encryption: Removing Noise Flooding in Distributed Decryption via the Smudging Lemma on Discrete Gaussian Distribution |
| title_full | Multikey Fully Homomorphic Encryption: Removing Noise Flooding in Distributed Decryption via the Smudging Lemma on Discrete Gaussian Distribution |
| title_fullStr | Multikey Fully Homomorphic Encryption: Removing Noise Flooding in Distributed Decryption via the Smudging Lemma on Discrete Gaussian Distribution |
| title_full_unstemmed | Multikey Fully Homomorphic Encryption: Removing Noise Flooding in Distributed Decryption via the Smudging Lemma on Discrete Gaussian Distribution |
| title_short | Multikey Fully Homomorphic Encryption: Removing Noise Flooding in Distributed Decryption via the Smudging Lemma on Discrete Gaussian Distribution |
| title_sort | multikey fully homomorphic encryption removing noise flooding in distributed decryption via the smudging lemma on discrete gaussian distribution |
| url | http://dx.doi.org/10.1049/ise2/7550044 |
| work_keys_str_mv | AT xiaokangdai multikeyfullyhomomorphicencryptionremovingnoisefloodingindistributeddecryptionviathesmudginglemmaondiscretegaussiandistribution AT wenyuanwu multikeyfullyhomomorphicencryptionremovingnoisefloodingindistributeddecryptionviathesmudginglemmaondiscretegaussiandistribution AT yongfeng multikeyfullyhomomorphicencryptionremovingnoisefloodingindistributeddecryptionviathesmudginglemmaondiscretegaussiandistribution |