Paper 2026/1949

Verifiable Weighted Secret Sharing based on Chinese Remainder Theorem

Abstract

In this work, we present the first practical verifiable weighted secret sharing (VWSS) scheme based on the Chinese Remainder Theorem (CRT). Classical secret sharing schemes, such as Shamir’s, assume participants with equal weights, which is inadequate for emerging applications like stake-based DAO voting and proof-of-stake blockchains, where parties naturally have unequal voting power or stakes. While prior work (e.g., Garg et al., Crypto'23) demonstrated that CRT-based (ramp) secret sharing can support weighted access structures more efficiently than linear secret sharing schemes, existing constructions only guarantee security against honest-but-curious dealers. In contrast to traditional linear secret sharing schemes, extending verifiability to CRT-based weighted secret sharing remains challenging, as current approaches either fail to support weighted access structures or incur prohibitive computational overhead on the dealer, limiting their practicality. To address this gap, we develop novel $\Sigma$-protocols for the \emph{unbounded} proof-of-mod (UPoM) relation using integer commitments in groups of unknown order, which may be of independent interest. Combining our UPoM protocols and new observations on the structural properties of CRT-based secret sharing, we construct a VWSS scheme in which the dealer broadcasts only $O(|A|)$ commitments to secret shares, where $A$ is a subset of parties whose total weight meets the reconstruction threshold $T$. This improves upon the closest prior CRT-based VWSS scheme (Shehata et al., CVC'25), which requires the dealer to broadcast commitments to the secret shares of all parties. Concretely, for a system with four participants and total weight $524$, our scheme generates VWSS proofs in around $0.2$ seconds, \emph{orders of magnitude faster} than the construction of CVC'25, highlighting its practicality for real-world applications.