Paper 2026/2290

Jambon: Asynchronous Universally Composable Threshold FHE with Low Communication

Abstract

Threshold fully homomorphic encryption distributes decryption authority among multiple parties, but achieving strong security can significantly increase the required ciphertext modulus and the size of each decryption response. Existing parameter analyses typically focus on threshold decryption alone. In particular, the recent work of Kim et al. (KLL$^+$26) analyzes correctness and strong simulation security of partial decryption without covering distributed key generation (DKG). When the parties generate the keys themselves, the DKG and partial-decryption protocols must satisfy their respective correctness and security requirements. We revisit correctness and simulation-security requirements for threshold decryption when it is composed with DKG. We then introduce Jambon, which applies deterministic rounding to partial decryptions to further reduce the modulus used for decryption responses. The composed security bound accounts separately for setup and decryption errors. We prove exact recovery for BFV and extend the approach to CKKS under an additional condition. Under the stated temporary-HE assumptions and resource hybrids, we establish universally composable security with strong threshold privacy against static malicious corruption in the random-oracle model. We prove security for the DKG and its composition with verifiable partial decryption. Under the stated algebraic and statistical parameters, Jambon's numerical decryption responses are at least $60\%$ smaller than the native responses of the updated KLL$^+$26 strong-security construction at every threshold considered for $256$, $512$, and $1024$ parties. This comparison uses the specified sufficient bounds and excludes proof and setup traffic.