Efficient Multi-Key Homomorphic Encryption with Packed Ciphertexts with Application to Oblivious Neural Network Inference

By Hao Chen, Wei Dai, Miran Kim, Yongsoo Song. 2019

240 citations recorded by the source corpus.

Homomorphic Encryption (HE) is a cryptosystem which supports computation on encrypted data. Ló pez-Alt et al. (STOC 2012) proposed a generalized notion of HE, called Multi-Key Homomorphic Encryption (MKHE), which is capable of performing arithmetic operations on ciphertexts encrypted under different keys. In this paper, we present multi-key variants of two HE schemes with packed ciphertexts. We present new relinearization algorithms which are simpler and faster than previous method by Chen et al. (TCC 2017). We then generalize the bootstrapping techniques for HE to obtain multi-key fully homomorphic encryption schemes. We provide a proof-of-concept implementation of both MKHE schemes using Microsoft SEAL. For example, when the dimension of base ring is 8192, homomorphic multiplication between multi-key BFV (resp. CKKS) ciphertexts associated with four parties followed by a relinearization takes about 116 (resp. 67) milliseconds. Our MKHE schemes have a wide range of applications in secure computation between multiple data providers. As a benchmark, we homomorphically classify an image using a pre-trained neural network model, where input data and model are encrypted under different keys. Our implementation takes about 1.8 seconds to evaluate one convolutional layer followed by two fully connected layers on an encrypted image from the MNIST dataset.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Privacy‐preserving federated learning based on multi‐key homomorphic encryption (2021, background): “Chen et al.(22) proposed MK‐BFV and MK‐CKKS, multi‐key variants of the fully homomorphic encryption schemes BFV(34,35) and CKKS.”
Contact Tracing Mobile Apps for COVID-19: Privacy Considerations and Related Trade-offs (2020, background): “The messages are encrypted under different public keys, but it may be possible to use multi-key homomorphic encryption schemes [39; 40] which allow computation over ciphertexts encrypted with different public keys to”
Cheetah: Lean and Fast Secure Two-Party Deep Neural Network Inference (2022, methodology): “Besides the OT-based nonlinear protocols in CrypTFlow2, SCIHE also offers many optimized implementation of state-of-the-arts including the secure convolution [36, 44], and the matrix–vector multiplication from [13, 27] using an old version of SEAL.”
HEAX: High-Performance Architecture for Computation on Homomorphically Encrypted Data in the Cloud (2019, background): “With the special modulus p and a rescaling at the end of key switching, explained in [15], key switching is almost noise-free.”