Paper 2019/116

Multi-Key Homomophic Encryption from TFHE

Hao Chen, Ilaria Chillotti, and Yongsoo Song


In this paper, we propose a Multi-Key Homomorphic Encryption (MKHE) scheme by generalizing the low-latency homomorphic encryption by Chillotti et al. (ASIACRYPT 2016). Our scheme can evaluate a binary gate on ciphertexts encrypted under different keys followed by a bootstrapping. The biggest challenge to meeting the goal is to design a multiplication between a bootstrapping key of a single party and a multi-key RLWE ciphertext. We propose two different algorithms for this hybrid product. Our first method improves the ciphertext extension by Mukherjee and Wichs (EUROCRYPT 2016) to provide better performance. The other one is a whole new approach which has advantages in storage, complexity, and noise growth. Compared to previous work, our construction is more efficient in terms of both asymptotic and concrete complexity. The length of ciphertexts and the computational costs of a binary gate grow linearly and quadratically on the number of parties, respectively. We provide experimental results demonstrating the running time of a homomorphic NAND gate with bootstrapping. To the best of our knowledge, this is the first attempt in the literature to implement an MKHE scheme.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2019
Multi-key homomorphic encryptionBootstrapping
Contact author(s)
yongsoo song @ microsoft com
2019-09-12: last of 2 revisions
2019-02-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hao Chen and Ilaria Chillotti and Yongsoo Song},
      title = {Multi-Key Homomophic Encryption from TFHE},
      howpublished = {Cryptology ePrint Archive, Paper 2019/116},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.