Paper 2026/973
Asynchronous Lagrange-Based Threshold FHE with Smaller Modulus Overhead
, Korea University, Korea University, Korea University, Cryptolab Inc., 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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published by the IACR in CRYPTO 2026
- Keywords
- Homomorphic encryptionThreshold cryptography
- Contact author(s)
-
munsanwon2 @ korea ac kr
changminlee @ korea ac kr
hwani0814 @ korea ac kr
alain passelegue @ cryptolab co kr
damien stehle @ gmail com - History
- 2026-05-27: revised
- 2026-05-16: received
- See all versions
- Short URL
- https://ia.cr/2026/973
- License
-
CC BY
BibTeX
@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}
}
