Welcome to the resource topic for 2025/1834
Title:
Ajax: Fast Threshold Fully Homomorphic Encryption without Noise Flooding
Authors: Zhenkai Hu, Haofei Liang, Xiao Wang, Xiang Xie, Kang Yang, Yu Yu, Wenhao Zhang
Abstract:Threshold fully homomorphic encryption (ThFHE) enables multiple parties to perform arbitrary computation over encrypted data, while the secret key is distributed across the parties. The main task of designing ThFHE is to construct threshold key-generation and decryption protocols for FHE schemes. Among existing FHE schemes, FHEW-like cryptosystems enjoy the advantage of fast bootstrapping and small parameters.
However, known ThFHE solutions use the noise-flooding'' technique to realize threshold decryption, which requires either large parameters or switching to a scheme with large parameters via bootstrapping, leading to a slow decryption process. Besides, for key generation, existing ThFHE schemes either assume a generic MPC or a trusted setup, or incur noise growth that is linear in the number $n$ of parties. In this paper, we propose a fast ThFHE scheme Ajax, by designing threshold key-generation and decryption protocols for FHEW-like cryptosystems. In particular, for threshold decryption, we eliminate the need for noise flooding, and instead present a new technique called mask-then-open’’ based on random double sharings over different rings, while keeping the advantage of small parameters.
For threshold key generation, we show a simple approach to reduce the noise growth from n times to max(0.038n,2) times in the honest-majority setting, where at most t=\floor{(n-1)/2} parties are corrupted. Our end-to-end implementation reports the running time 17.6 s and 0.9 ms (resp., 91.9 s and 4.4 ms) of generating a set of keys and decrypting a single ciphertext respectively, for n=3 (resp., n=21) parties under the network of 1 Gbps bandwidth and 1 ms ping time. Compared to the state-of-the-art implementation, our protocol improves the end-to-end performance of the threshold decryption protocol by a factor of at least 5.7\times \sim 283.6\times across different network latencies from t=1 to t=13. Our approaches can also be applied in other types of FHE schemes like BGV, BFV, and CKKS.
In addition, we show how to strengthen our protocols in order to guarantee the security against malicious adversaries.
ePrint: https://eprint.iacr.org/2025/1834
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 .