Paper 2022/347

Asymptotically Faster Multi-Key Homomorphic Encryption from Homomorphic Gadget Decomposition

Taechan Kim, Samsung Research
Hyesun Kwak, Seoul National University
Dongwon Lee, Seoul National University
Jinyeong Seo, Seoul National University
Yongsoo Song, Seoul National University

Homomorphic Encryption (HE) is a cryptosytem that allows us to perform an arbitrary computation on encrypted data. The standard HE, however, has a disadvantage in that the authority is concentrated in the secret key owner as the computation can be performed only on ciphertexts under the same key. In order to overcome this problem, research is underway on Multi-Key Homomorphic Encryption (MKHE), which enables operations between encrypted data possibly under different keys. Despite its strength to cover privacy of multiple parties, the existing MKHE schemes suffer from poor performance that the multiplication cost grows at least quadratically with the number of parties involved. In this paper, we propose a new notion of the gadget decomposition, which enables arithmetic operations to be performed on the decomposed vectors with guarantee of functionality and noise bound. We redesign the multi-key multiplication algorithm of Chen et al. (ACM CCS 2019) using the homomorphic property of gadget decomposition and thereby reduce the complexity significantly from quadratic to linear in the number of parties involved. Finally, we implement our MKHE schemes and provide benchmarks which outperform the previous results.

Available format(s)
Public-key cryptography
Publication info
Multi-key Homomorphic Encryption Gadget decomposition
Contact author(s)
taechan kim @ samsung com
hskwak @ snu ac kr
dongwonlee95 @ gmail com
jinyeong seo @ snu ac kr
y song @ snu ac kr
2022-10-11: last of 3 revisions
2022-03-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Taechan Kim and Hyesun Kwak and Dongwon Lee and Jinyeong Seo and Yongsoo Song},
      title = {Asymptotically Faster Multi-Key Homomorphic Encryption from Homomorphic Gadget Decomposition},
      howpublished = {Cryptology ePrint Archive, Paper 2022/347},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.