Paper 2023/065

A Practical TFHE-Based Multi-Key Homomorphic Encryption with Linear Complexity and Low Noise Growth

Jakub Klemsa, EURECOM, Czech Technical University in Prague
Melek Önen, EURECOM
Yavuz Akın, EURECOM

Fully Homomorphic Encryption enables arbitrary computations over encrypted data and it has a multitude of applications, e.g., secure cloud computing in healthcare or finance. Multi-Key Homomorphic Encryption (MKHE) further allows to process encrypted data from multiple sources: the data can be encrypted with keys owned by different parties. In this paper, we propose a new variant of MKHE instantiated with the TFHE scheme. Compared to previous attempts by Chen et al. and by Kwak et al., our scheme achieves computation runtime that is linear in the number of involved parties and it outperforms the faster scheme by a factor of 4.5-6.9x, at the cost of a slightly extended pre-computation. In addition, for our scheme, we propose and practically evaluate parameters for up to 128 parties, which enjoy the same estimated security as parameters suggested for the previous schemes (100 bits). It is also worth noting that our scheme—unlike the previous schemes—did not experience any error in any of our nine experiments, each running 1 000 trials.

Note: Minor corrections.

Available format(s)
Publication info
Published elsewhere. ESORICS'23
Multi-key homomorphic encryptionTFHE schemeSecure cloud computing
Contact author(s)
fakubo @ gmail com
2023-04-21: revised
2023-01-20: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-ShareAlike


      author = {Jakub Klemsa and Melek Önen and Yavuz Akın},
      title = {A Practical TFHE-Based Multi-Key Homomorphic Encryption with Linear Complexity and Low Noise Growth},
      howpublished = {Cryptology ePrint Archive, Paper 2023/065},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.