Cryptology ePrint Archive: Report 2019/116

Multi-Key Homomophic Encryption from TFHE

Hao Chen and Ilaria Chillotti and Yongsoo Song

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.

Category / Keywords: public-key cryptography / Multi-key homomorphic encryption, Bootstrapping

Original Publication (in the same form): IACR-ASIACRYPT-2019

Date: received 5 Feb 2019, last revised 12 Sep 2019

Contact author: yongsoo song at microsoft com

Available format(s): PDF | BibTeX Citation

Version: 20190912:072406 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]