Welcome to the resource topic for 2025/1804
Title:
HELIOS: Multi-Key Fully Homomorphic Encryption with Sublinear Bootstrapping
Authors: Binwu Xiang, Seonhong Min, Intak Hwang, Zhiwei Wang, Haoqi He, Yuanju Wei, Kang Yang, Jiang Zhang, Yi Deng, Yu Yu
Abstract:Multi-key fully homomorphic encryption (MK-FHE) enables secure computation over ciphertexts under different keys, but its practicality is hindered by inefficient bootstrapping.In this work, we propose HELIOS, a new MK-FHE scheme with highly efficient bootstrapping. Our bootstrapping framework improves upon the best-known complexity, reducing it from {O}(dkn) to {O}(kn), and further to {O}(\sqrt{kn}) under parallelization, where d is the gadget length (typically scaling with the number of parties k) and n is the LWE dimension.The framework consists of two main components: (i) a ciphertext conversion algorithm that transforms a multi-key LWE ciphertext into k vectorized RLWE ciphertexts via k optimized blind rotations and dk key-switching operations, and (ii) a hybrid accumulator that aggregates these into a single multi-key RLWE ciphertext.
We implemented HELIOS on both CPU and GPU platforms to demonstrate its practicality. For k=16, we achieve 3.3\times and 7.2\times improvements on CPU, compared to the state-of-the-art schemes by Kwak et al. (PKC 2024) and by Xiang et al. (ASIACRYPT 2024), respectively. We further achieve a 195\times GPU acceleration, compared to our CPU runtime.
As a byproduct, we design a new distributed-decryption protocol, which allows us to obtain a ciphertext with a small noise bound, and thus does not blow up the parameters.
ePrint: https://eprint.iacr.org/2025/1804
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 .