Tulva: Practical Asynchronous Threshold FHE
Tulva adds practical asynchronous threshold decryption to base FHE schemes, with millisecond EVM-oriented benchmarks.
Tulva adds an asynchronous threshold decryption mechanism to nearly any base fully homomorphic encryption scheme without changing ciphertexts beyond an appended random tag. It supports varied (t,K) profiles and ring degrees of at least 256, with 6–25 bits of partial decryption per plaintext bit, and proves security against partial-decryption queries under standard LWE. An open-source implementation reports 3.7 ms secret-dependent partial decryption and 0.5 ms public share combination for a 16-out-of-512 threshold on commodity hardware, plus end-to-end costs for privacy-preserving EVM workloads. Versus a CCS 2025 synchronous scheme, it swaps interactive secret-correlated randomness for a 0.5-second public preprocessing step, removes online interaction, and supports 32 times more users.
- Modular async threshold decryption leaves base FHE ciphertexts unchanged aside from a tag.
- Security under partial-decryption queries rests on standard LWE.
- 16-of-512 partial decryption takes 3.7 ms; share combination 0.5 ms.
- Replaces interactive prep with 0.5 s public preprocessing and supports 32x more users.
Full article189 words · extracted from arxiv.org · click to collapse
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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2610.20521