HERDS: Multi-key Fully Homomorphic Encryption with Sublinear Bootstrapping

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 HERDS, 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(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 HERDS on both CPU and GPU platforms to demonstrate its practicality. For k=16, we achieve 3.3× and 7.2× 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× 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.