Zhenkai Hu, Shanghai Jiao Tong University and State Key Laboratory of Cryptology; Haofei Liang, Shanghai Jiao Tong University; Xiao Wang, Northwestern University; Xiang Xie, East China Normal University and Primus Labs; Kang Yang, State Key Laboratory of Cryptology; Yu Yu, Shanghai Jiao Tong University; Wenhao Zhang, Northwestern University
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=(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× 283.6× 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.
Open Access Media
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.
