"Preview Talk" (by team Tulva) @ TCPT3, in reply to the NIST Threshold Call
Abstract: While fully homomorphic encryption (FHE) enables computation on encrypted data, whoever holds the secret key can decrypt every input and output, creating a single point of failure. Threshold FHE alleviates this problem by distributing the decryption key among K shareholders in such a way that any threshold t of them can jointly decrypt a ciphertext. In this talk, I will present Tulva, a compiler that turns a lattice-based FHE scheme into a threshold FHE scheme with asynchronous decryption: each participating party produces its own partial decryption share, and the message is recovered only when sufficiently many shares are combined. Parties may produce these shares asynchronously, without even agreeing in advance on who will participate. Tulva adopts a two-layer design: a base FHE layer that inherits the format and efficiency of the FHE scheme, and a threshold layer that handles threshold decryption. It is almost agnostic to the FHE scheme, supporting the common BGV/BFV, FHEW/TFHE and discrete CKKS families, with implementations differing only in a public ciphertext preprocessing step. Tulva targets a security model where an adversary can selectively corrupt |C| parties and request for partial decryptions of honestly generated ciphertexts, including the challenge ciphertext. The message encrypted in the challenge ciphertext remains hidden so long as the adversary sees fewer than t - |C| of its partial decryptions. Practically, Tulva-compiled threshold FHE schemes feature very small decryption shares, flexible threshold configurations with large numbers of parties, fast non-interactive decryption, and black-box integration with state-of-the-art FHE schemes.
Joint work: Valerio Cini, Antonio Guimarães, Aaron Kaiser, Russell W. F. Lai, Michał Osadnik, Ivy K. Y. Woo.
Suggested readings
- Preview Writeup (PDF): Tulva: Asynchronous Threshold FHE Transform with Small Decryption Shares
- Pilvi: Lattice Threshold PKE with Small Decryption Shares and Improved Security (ia.cr/2025/1691)
- Leaky LWE: Learning with Errors with Semi-Adaptive Secret- and Error-Leakage (cic.iacr.org/p/2/3/21)
