Paper 2021/1412

A Unified Framework of Homomorphic Encryption for Multiple Parties with Non-Interactive Setup

Hyesun Kwak, Dongwon Lee, Yongsoo Song, and Sameer Wagh


Homomorphic Encryption (HE), first constructed in 2009, is a class of encryption schemes that enables computation over encrypted data. Variants of HE in the context of multiple parties have led to the development of two different lines of HE schemes -- Multi-Party Homomorphic Encryption (MPHE) and Multi-Key Homomorphic Encryption (MKHE). These primitives cater to different applications and each approach has its own pros and cons. At a high level, MPHE schemes tend to be much more efficient but require the set of computing parties to be fixed throughout the entire operation, frequently a limiting assumption. On the other hand, MKHE schemes tend to have poor scaling (quadratic) with the number of parties but allow us to add new parties to the joint computation anytime since they support computation between ciphertexts under different keys. In this work, we formalize a new variant of HE called Multi-Group Homomorphic Encryption (MGHE). Stated informally, an MGHE scheme provides a seamless integration between MPHE and MKHE, and combines the best of both these primitives. In an MGHE scheme, a group of parties generates a public key jointly which results in the compact ciphertexts and efficient homomorphic operations, similar to MPHE. However, unlike MPHE, it also supports computations on encrypted data under different keys, a property enjoyed by MKHE schemes. We provide a concrete construction of such an MGHE scheme from the BFV scheme. The public key generation procedure of our scheme is fully non-interactive so that the set of computing parties does not have to be determined and no information about other parties is needed in advance of individual key generation. At the heart of our construction is a novel refactoring of the relinearization key to avoid interaction as typically needed. We also implement our scheme and demonstrate that the this generalization does not incur any additional overhead and in fact, can be more performant than existing MPHE and MKHE schemes.

Available format(s)
Public-key cryptography
Publication info
Preprint. Minor revision.
Homomorphic Encryption
Contact author(s)
y song @ snu ac kr
2022-02-22: revised
2021-10-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hyesun Kwak and Dongwon Lee and Yongsoo Song and Sameer Wagh},
      title = {A Unified Framework of Homomorphic Encryption for Multiple Parties with Non-Interactive Setup},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1412},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.