A practical TFHE-based multi-Key homomorphic encryption with linear complexity and low noise growth

Akin, Yavuz; Klemsa, Jakub; Önen, Melek
ESORICS 2023, 28th European Symposium on Research in Computer Security, September 25-29, 2023, The Hague, The Netherlands / Also published in LNCS, Vol.14344, 12 January 2024

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" role="presentation" style="margin: 0px; box-sizing: inherit; display: inline-block; line-height: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; position: relative;">


 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.9×" role="presentation" style="margin: 0px; box-sizing: inherit; display: inline-block; line-height: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; position: relative;">


6.9×

, 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 seven setups, each running 1000" role="presentation" style="margin: 0px; box-sizing: inherit; display: inline-block; line-height: normal; word-spacing: normal; overflow-wrap: normal; text-wrap: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; position: relative;">


100000

 trials.


DOI
HAL
Type:
Conférence
City:
La Hague
Date:
2023-09-25
Department:
Sécurité numérique
Eurecom Ref:
7264
Copyright:
© Springer. Personal use of this material is permitted. The definitive version of this paper was published in ESORICS 2023, 28th European Symposium on Research in Computer Security, September 25-29, 2023, The Hague, The Netherlands / Also published in LNCS, Vol.14344, 12 January 2024 and is available at : https://doi.org/10.1007/978-3-031-50594-2_1

PERMALINK : https://www.eurecom.fr/publication/7264