Paper 2021/1412

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

Hyesun Kwak and Dongwon Lee and Yongsoo Song and Sameer Wagh

Abstract

Homomorphic Encryption (HE), first demonstrated in 2009, is a class of encryption schemes that enables computation over encrypted data. Recent advances in the design of better protocols 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 as 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, thereby enjoying the best of both worlds. In this framework, a group of parties generates a public key jointly which results in the compactness of ciphertexts and the efficiency of homomorphic operations similar to MPHE. However, unlike MPHE, it also supports computations on encrypted data under different keys similar to MKHE. We provide the first construction of such an MGHE scheme from BFV and demonstrate experimental results. More importantly, the joint 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 re-factoring of the relinearization key.