Paper 2025/318 Original: eprint.iacr.org/2025/318 ↗

Accountable Verifiable Secret Sharing and Applications

Abstract

Verifiable Secret Sharing (VSS) ensures consistent sharing and correct reconstruction, but does not identify the shareholders involved. Traceable Secret Sharing (TSS) expands secret sharing with two guarantees: $\textit{traceability}$, which identifies the makers of a reconstruction box through black-box queries; and $\textit{non-imputability}$, which prevents false accusations against honest shareholders. However, full traceability is practically expensive: existing Shamir-based schemes require multiple carefully chosen queries to a $\textit{stateless}$ reconstruction box. Moreover, Goyal et al. (ePrint 2025/1980) show that the strongest form of black-box tracing is incompatible with simultaneously achieving non-imputability and tracer secrecy. We introduce $\textit{Accountable VSS}$ (Acc-VSS), a practical extension of VSS that achieves the next-best goal: $\textit{accountability}$, a strict relaxation of traceability requiring that (i) the contributors to every accepted reconstruction be publicly identifiable from its transcript with a $\textit{single}$ query, and (ii) no honest shareholder be falsely accused, even by an adversary holding all other shares. Accountability thus replaces black-box, multi-query tracing with a transcript check executable by any external verifier or smart-contract judge. In this paper, (i) we give a generic transformation from any computationally secure Shamir-based VSS to Acc-VSS, adding only one field element per share; it uses a long-term identity secret to each share and a conjunctive NIZK to bind partial reconstructions to the shareholder and the dealer's commitments; (ii) we instantiate it with Feldman and Pedersen VSS and prove the security of both schemes; (iii) we prove a self-contained $\textit{single-query}$ impossibility lemma motivating our relaxation; and (iv) we show how Acc-VSS uniformly yields accountable threshold ElGamal decryption, Schnorr/FROST signing, and distributed key generation. For the benchmarked VSS-based threshold-decryption protocol, accountability adds at most $20.3\%$ end-to-end overhead for $n=20$ and less than $6\%$ for $n=100$. Encrypted mempools, end-to-end-verifiable e-voting tallies, and validator-slashing in proof-of-stake systems all reduce to this framework.