Skip to content

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]

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