Tulva enables practical asynchronous threshold fully homomorphic encryption
Tulva: Practical Asynchronous Threshold FHE
Cryptography and Security
Summary
Fully homomorphic encryption (FHE) lets computers work on encrypted data without seeing the actual data, but sharing the secret keys safely among many users is tricky. The authors present Tulva, a way to split the key and decrypt data collaboratively without waiting for everyone to act simultaneously, improving speed and flexibility. Tulva works with many existing FHE systems, making it easier and faster to decrypt encrypted data safely. They tested Tulva on typical Ethereum smart contract scenarios and showed it performs well on regular computers.
What this means in practice
- •For blockchain developers: Implement secure multi-party decryption for privacy-preserving smart contracts without synchronous coordination.
- •For cloud security teams: Enable distributed encrypted data processing with flexible and scalable threshold decryption access control on commodity hardware.
Authors
Valerio Cini, Antonio Guimarães, Russell W. F. Lai, Michał Osadnik, Ivy K. Y. Woo
Abstract
We present Tulva, a practical threshold FHE scheme which equips a base FHE scheme with an asynchronous threshold decryption mechanism in a modular way. Our scheme simultaneously (1) is compatible with virtually any base FHE scheme and leaves its ciphertexts unchanged apart from an appended random tag, (2) supports a wide range of threshold profiles $(t,K)$ and ring degrees $\geq 256$ with 6-25 bits partial decryption per plaintext bit, and (3) achieves security in the presence of partial decryption queries on challenge ciphertexts based on the standard LWE assumption. We provide an open-source implementation, benchmark its threshold decryption performance and evaluate the end-to-end costs for typical privacy-preserving Ethereum Virtual Machine (EVM) use cases. For 16-out-of-512 threshold and a publicly preprocessed ciphertext, computing secret-dependent partial decryption and public share combination requires only 3.7 ms and 0.5 ms, respectively, on commodity hardware. Compared with the state-of-the-art synchronous scheme [Zyskind et al., CCS'25], we replace their ciphertext-independent yet interactive preparation of secret-correlated randomness with a public, ciphertext-dependent 0.5 s preprocessing step, eliminate interaction in the online phase while maintaining similar decryption time on the same machine, and support 32$\times$ more total users.