Paper 2026/973

Asynchronous Shamir-Based Threshold FHE: Smaller Moduli and Strong Simulation Security

Abstract

We study $t$-out-of-$n$ threshold fully homomorphic encryption (ThFHE) based on Shamir secret sharing (SSS) in the asynchronous setting. With SSS, a partial decryption share is a single ring element; this allows to avoid the large number of ring elements stored per party required by prior strongly secure constructions based on $\{0,1\}$ reconstruction coefficients. However, this reduction introduces a fundamental trade-off: Lagrange reconstruction during distributed decryption severely amplifies noise, forcing a substantially larger ciphertext modulus. In this work, we give SSS-based asynchronous ThFHE constructions over standard RLWE-based FHE schemes (BFV, BGV, and CKKS) for both standard and strong simulation security. Through tight analysis of the modulus constraints, our constructions simultaneously reduce the required modulus, compared with prior asynchronous Shamir-based constructions, and the per-party storage, compared with the prior strongly secure construction. For example, for $n=512$ under standard simulation security, our analysis reduces the modulus overhead of distributed decryption by $33 \%$ at $t=n/2$ and by up to $90\%$ for $t$ close to $n$, relative to the prior works. Under strong simulation security, the per-party storage for $n=16$ and $t=8$ at $128$-bit security drops from $79$ GB in prior work to $897$ KB.

Note: This paper is an extended version of our CRYPTO 2026 paper. Damien Stehlé conducted this work while at CryptoLab Inc.