International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Multi-Key Homomorphic Encryption from TFHE

Authors:
Hao Chen
Ilaria Chillotti
Yongsoo Song
Download:
DOI: 10.1007/978-3-030-34621-8_16
Search ePrint
Search Google
Abstract: 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.
BibTeX
@article{asiacrypt-2019-30047,
  title={Multi-Key Homomorphic Encryption from TFHE},
  booktitle={Advances in Cryptology – ASIACRYPT 2019},
  series={Advances in Cryptology – ASIACRYPT 2019},
  publisher={Springer},
  volume={11922},
  pages={446-472},
  doi={10.1007/978-3-030-34621-8_16},
  author={Hao Chen and Ilaria Chillotti and Yongsoo Song},
  year=2019
}