Revisiting Shamir Secret Sharing for Threshold Fully Homomorphic Encryption¶
Year: 2026
type: technique collection: schemes status: auto
Links: ePrint 2026/1559
Summary¶
Auto-extracted summary (unreviewed)
The paper revisits ring-based Shamir secret sharing for threshold FHE and threshold PKE, introducing a refined framework for integer-reconstructible sharing over cyclotomic rings based on subtractive sets and a new geometric analysis of Lagrange coefficients. This shrinks the denominator-clearing factors so that one-round (t,N)-ThFHE needs ciphertext moduli of only O(t log(N/t^2)) bits instead of O(N), and gives a better reconstruction-factor bound than Pilvi for ThPKE. An OpenFHE/BFV implementation shows every ThFHE algorithm finishing within 0.2 s for N=64, with speedups of up to 789x over the BGG+18 baseline and scalability to N>=256.
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 π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 (π‘, π)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 latticebased one-round (π‘, π)-ThFHE schemes, our approach reduces the bit-size of ciphertext moduli from π(π) to π(π‘log(π/π‘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 π= 64 and remains scalable for larger configurations with πβ₯256.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Refined framework for integer-reconstructible Shamir secret sharing over cyclotomic rings via subtractive sets | llm | 0.85 |
| contribution | Geometric analysis of Lagrange coefficients yielding much smaller reconstruction (denominator-clearing) factors | llm | 0.85 |
| contribution | Ciphertext modulus bit-size for one-round (t,N)-ThFHE reduced from O(N) to O(t log(N/t^2)) | llm | 0.85 |
| contribution | New reconstruction-factor bound for lattice-based ThPKE improving on Pilvi | llm | 0.85 |
| contribution | Implementation of ThFHE over cyclotomic rings with experimental comparison against BGG+18 and CL25 | llm | 0.85 |
| schemes | secret sharing | llm | 0.85 |
| schemes | Shamir secret sharing | llm | 0.85 |
| schemes | threshold FHE | llm | 0.85 |
| schemes | BFV | llm | 0.85 |
| libraries | OpenFHE | llm | 0.85 |
| libraries | Lattigo | llm | 0.85 |
| tasks | threshold FHE | llm | 0.85 |
| tasks | distributed (threshold) decryption | llm | 0.85 |
| hardware | Apple M3 Max CPU, 48 GB unified memory | llm | 0.85 |
| security level | 128-bit computational, 40-bit statistical | llm | 0.85 |
| threat model | (t,N)-threshold parties with one-round distributed decryption | llm | 0.85 |
| interaction | other | llm | 0.85 |
| code url | https://github.com/seunghu-kim/2adic-ss.git (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/Yijia-Oneplus-Chang/Usenix2025.git.ThFHE (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/malb/lattice-estimator (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/seunghu-kim/2adic-ss.git | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | ciphertext modulus bit-size: O(t log(N/t^2)) instead of O(N) (one-round (t,N)-ThFHE) | llm | 0.85 |
| key result | latency per ThFHE algorithm: < 0.2 s (N=64, Apple M3 Max) | llm | 0.85 |
| key result | speedup over BGG+18 (Setup / Enc / PartDec / FinDec): 351-789x / 52-103x / 23-47x / 4-20x (N=64, varying t) | llm | 0.85 |
| key result | Setup / Enc / PartDec time: 4.60 ms / 0.94 ms / 1.28 ms ((N,t)=(64,6)) | llm | 0.85 |
| key result | estimated ciphertext size: 33.44 KB (ours+BGG+18) vs 9699 KB (BGG+18) vs 130 KB (BFM+25) (N=64, t=5) | llm | 0.85 |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: Secret sharing 31 [p.1], Threshold HE 12 [p.2], BFV 5 [p.8], Multiparty HE 3 [p.14], MPC 3 [p.9], CKKS 2 [p.8], BGV 2 [p.8], Zero-knowledge proofs 2 [p.9]
- library: OpenFHE 3 [p.9], Lattigo 3 [p.9], Concrete (Zama) 2 [p.2]
- hardware: Apple silicon 1 [p.11]
- technique: Federated learning 2 [p.14], Malicious model 2 [p.9]
- assumption: Lattice-based 26 [p.1], LWE 7 [p.9], RLWE 3 [p.9], IND-CPA 2 [p.14]
- topic: Homomorphic encryption 82 [p.1], Open source 5 [p.10], Benchmark 2 [p.10]
Related papers¶
- this paper follow up of Multiparty Homomorphic Encryption from Ring-Learning-with-Errors β follow-up listed for scheme "Multiparty HE (MHE) for BFV/CKKS"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s36-2_eprint-2026-1559.pdf |
schemes | 17 | 2.1 MB | 7df9d4006115 |
Database key: revisiting-shamir-secret-sharing-for-threshold-fully-homomorphic Β· created 2026-11-05 Β· updated 2026-11-05 Β· edit with python3 tools/paperdb.py set revisiting-shamir-secret-sharing-for-threshold-fully-homomorphic COLUMN VALUE