Paper 2026/973

Asynchronous Lagrange-Based Threshold FHE with Smaller Modulus Overhead

Changmin Lee, Korea University

JeongHwan Lee, Korea University

Alain Passelègue, Cryptolab Inc.

Damien Stehlé, Cryptolab Inc.

Abstract

We study $t$-out-of-$n$ threshold fully homomorphic encryption (ThFHE) based on Shamir secret sharing (SSS) in the asynchronous setting. A central bottleneck for SSS-based ThFHE is that Lagrange reconstruction during distributed decryption can amplify noise, forcing a substantially larger ciphertext modulus to maintain correctness. In this work, we revisit SSS-based ThFHE and give a rigorous analysis of the correctness and simulation-security constraints that govern parameter choices. We then compare families of Lagrange interpolation points through the lens of these constraints. Our main contributions are analytic bounds that closely track empirical behavior and significantly reduce the modulus overhead required for distributed decryption. For example, for $n = 512$, our analysis reduces this modulus overhead (in bits) by 30% for $t = n/2$ and by up to 90% for $t$ close to $n$, compared to prior parameterizations.

@misc{cryptoeprint:2026/973,
      author = {Won Kim and Changmin Lee and JeongHwan Lee and Alain Passelègue and Damien Stehlé},
      title = {Asynchronous Lagrange-Based Threshold {FHE} with Smaller Modulus Overhead},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/973},
      year = {2026},
      url = {https://eprint.iacr.org/2026/973}
}