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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Homomorphic Encryption
Contact author(s)
y song @ snu ac kr
History
2022-02-22: revised
2021-10-24: received
See all versions
Short URL
https://ia.cr/2021/1412
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1412,
      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{https://eprint.iacr.org/2021/1412}},
      url = {https://eprint.iacr.org/2021/1412}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.