Welcome to the resource topic for 2022/1460
Title:
Towards Practical Multi-key TFHE: Parallelizable, Key-Compatible, Quasi-linear Complexity
Authors: Hyesun Kwak, Seonhong Min, Yongsoo Song
Abstract: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 .