Paper 2019/524

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

Hao Chen, Wei Dai, Miran Kim, and Yongsoo Song


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. The 26th ACM Conference on Computer and Communications Security (CCS 2019)
multi-key homomorphic encryptionpacked ciphertextring learning with errorsneural networks
Contact author(s)
yongsoo song @ microsoft com
2019-09-19: last of 2 revisions
2019-05-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hao Chen and Wei Dai and Miran Kim and Yongsoo Song},
      title = {Efficient Multi-Key Homomorphic Encryption with Packed Ciphertexts with Application to Oblivious Neural Network Inference},
      howpublished = {Cryptology ePrint Archive, Paper 2019/524},
      year = {2019},
      doi = {10.1145/3319535.3363207},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.