Oliver Zajonc

Multiparty fully homomorphic encryption (MPFHE) is a generalization of (multi-key) fully homomorphic encryption ((MK)FHE) that lives on the cusp between multiparty computation (MPC) and FHE, enabling a computation over encrypted data using multiple keys. However, contrary to MKFHE, it seeks to reduce the noise inflation based on the number of parties by allowing the parties to first compute shared data in MPC before executing the computation in FHE. However, many works use specific constructions, e.g. Chang-Li, Koirala et. al., and Ma et. al., reliant on the behaviour of a particular scheme and do not consider security against colluding servers and parties, e.g. Passelègue-Stehlé, Okada-Takagi, and Mouchet et. al. In this work we present a new framework that is secure against collusion between servers and parties and allows the use of a broad spectrum of MPC and FHE protocols, while eliminating the noise inflation based on the participating number of parties. We then show a case study of this using the FINAL scheme and show that we reduce the required key material by 60–99.9% compared to the MKFHE FINAL scheme, FINALLY, and 65–70% compared to the Park-Rovira scheme in all cases, and by up to 71% compared to the AKÖ scheme when there are 4 or more parties. Moreover, we reduce the bootstrapping time for the AKÖ, Park-Rovira, and KMS schemes by 75–99.7%.

Multi-key fully homomorphic encryption (MKFHE), a generalization of fully homomorphic encryption (FHE), enables a computation over encrypted data under multiple keys. The first MKFHE schemes were based on the NTRU primitive, however these early NTRU based FHE schemes were found to be insecure due to the problem of over-stretched parameters. Recently, in the case of standard (non-multi key) FHE a secure version, called FINAL, of NTRU has been found. In this work we extend FINAL to an MKFHE scheme, this allows us to benefit from some of the performance advantages provided by NTRU based primitives. Thus, our scheme provides competitive performance against current state-of-the-art multi-key TFHE, in particular reducing the computational complexity from quadratic to linear in the number of keys.