Paper 2022/1460

Towards Practical Multi-key TFHE: Parallelizable, Key-Compatible, Quasi-linear Complexity

Hyesun Kwak, Seoul National University
Seonhong Min, Seoul National University
Yongsoo Song, Seoul National University

Multi-key homomorphic encryption is a generalized notion of homomorphic encryption supporting arbitrary computation on ciphertexts, possibly encrypted under different keys. In this paper, we revisit the work of Chen, Chillotti and Song (ASIACRYPT 2019) and present yet another multi-key variant of the TFHE scheme. The previous construction by Chen et al. involves a blind rotation procedure where the complexity of each iteration gradually increases as it continuously operates on ciphertexts under different keys. Hence, the complexity of gate bootstrapping grows quadratically with respect to the number of associated keys. Our scheme is based on a new blind rotation algorithm which consists of two separate phases. We first split a given multi-key ciphertext into several single-key ciphertexts, take each of them as input to the blind rotation procedure, and obtain accumulators corresponding to individual keys. Then, we merge these single-key accumulators into a single multi-key accumulator. In particular, we develop a novel homomorphic operation between single-key and multi-key ciphertexts to instantiate our pipeline. Therefore, our construction achieves an almost linear time complexity since the gate bootstrapping is dominated by the first phase of blind rotation which requires only independent single-key operations. It also enjoys with great advantages of parallelizability and key-compatibility. We implement the proposed scheme and provide its performance benchmark. For example, our 16-key gate bootstrapping takes about 5.65s, which is 4.38x faster compared to the prior work.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2024
Multi-key homomorphic encryptionTFHE
Contact author(s)
hskwak @ snu ac kr
minsh @ snu ac kr
yssong618 @ gmail com
2024-01-23: last of 4 revisions
2022-10-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hyesun Kwak and Seonhong Min and Yongsoo Song},
      title = {Towards Practical Multi-key {TFHE}: Parallelizable, Key-Compatible, Quasi-linear Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1460},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.