Paper 2025/2261

TSS-PV: Traceable Secret Sharing with Public Verifiability

Abstract

High-value custodial systems require both Public Verifiability to audit key distribution and Traceability to identify insider leakage via black-box \textit{reconstruction boxes}. Existing schemes achieve one property but not both, leaving practical systems exposed to either undetectable dealer misbehavior or untraceable share leakage. Combining these properties introduces the Provenance Paradox: a verifiability-aware reconstruction box with access to verification predicates and public transcripts can reject dummy shares used for tracing because they have no provenance in the public transcript. We present TSS-PV, the first publicly verifiable traceable secret sharing scheme that resolves this paradox. Our key insight is to inject indistinguishable dummy shares during the sharing phase itself, ensuring they are committed to the public transcript before any reconstruction box is constructed. We formalize syntax and security under a modular adversarial model: public verifiability holds against fully malicious dealers and parties; traceability identifies leaking parties after honest distribution; and non-imputability prevents a malicious dealer from framing honest parties. Both tracing properties assume a verifiability-aware perfect reconstruction box. We instantiate TSS-PV over cyclic groups using Schnorr-based NIZKs including a new $\Sigma$-protocol for power-chain relations and a recent generic tracing framework (CRYPTO'24). Public verification costs scale linearly in the number of parties; tracing costs are quadratic. A Curve25519 prototype on commodity hardware demonstrates practicality: for $32\text{ - }256$ parties, distribution verification completes in $\approx 14\text{ - }107$ ms, tracing in $\approx0.23\text{ - }78$ s, and trace verification in $\approx 0.13\text{ - }26$ s.