Paper 2022/347
Asymptotically Faster Multi-Key Homomorphic Encryption from Homomorphic Gadget Decomposition
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- 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 - History
- 2022-10-11: last of 3 revisions
- 2022-03-14: received
- See all versions
- Short URL
- https://ia.cr/2022/347
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/347, 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{https://eprint.iacr.org/2022/347}}, url = {https://eprint.iacr.org/2022/347} }