[Resource Topic] 2022/1460: Towards Practical Multi-key TFHE: Parallelizable, Key-Compatible, Quasi-linear Complexity

Welcome to the resource topic for 2022/1460

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

Authors: Hyesun Kwak, Seonhong Min, Yongsoo Song


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 operates on ciphertexts under different keys. Hence, the complexity of gate bootstrapping grows quadratically with respect to the number of associated keys. On the other hand, 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 RLEV and multi-key RLWE 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. Finally, we implement the proposed scheme and provide its performance benchmark. For example, our experiment of 16-key gate bootstrapping demonstrates about 5.3x speedup over prior work.

ePrint: https://eprint.iacr.org/2022/1460

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .