Paper 2026/1559

Revisiting Shamir Secret Sharing for Threshold Fully Homomorphic Encryption

Abstract

Recent advances in lattice-based threshold cryptography, including threshold fully homomorphic encryption (ThFHE) and threshold public key encryption (ThPKE), commonly employ Shamir secret sharing over rings. While conceptually simple, these schemes suffer from rapidly growing denominator-clearing factors required for secret reconstruction as the number of parties $N$ increases, which in turn necessitates larger ciphertext moduli and complex reconstruction procedures. In this work, we revisit the notion of subtractive sets underlying ring-based Shamir secret sharing and present a refined framework for constructing integer-reconstructible sharing over cyclotomic rings. To that end, we introduce a new geometric analysis of Lagrange coefficients and show that the resulting reconstruction factors can be made significantly smaller under specific settings. In particular, our framework enables smaller ciphertext sizes in $(t,N)$-threshold settings, and yields improved correctness and efficiency when applied to any ring-based threshold construction employing Shamir secret sharing over cyclotomic rings. Specifically, in lattice-based one-round $(t, N)$-ThFHE schemes, our approach reduces the bit-size of ciphertext moduli from $O(N)$ to $O(t\log (N/t^2))$ while ensuring efficient denominator handling. For lattice-based ThPKE, our method yields a new bound on reconstruction factors that improves upon the recent state-of-the-art result of Pilvi. Moreover, we implement ThFHE schemes over cyclotomic rings based on our framework and demonstrate their practical efficiency. Our experimental results show that each algorithm completes within $0.2$ seconds for $N=64$ and remains scalable for larger configurations with $N\geq 256$.