Cryptology ePrint Archive: Report 2019/524

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

Hao Chen and Wei Dai and Miran Kim and Yongsoo Song

Abstract: 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.

Category / Keywords: public-key cryptography / multi-key homomorphic encryption; packed ciphertext; ring learning with errors; neural networks

Original Publication (in the same form): The 26th ACM Conference on Computer and Communications Security (CCS 2019)

Date: received 19 May 2019, last revised 19 Sep 2019

Contact author: yongsoo song at microsoft com

Available format(s): PDF | BibTeX Citation

Version: 20190919:223334 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]