Paper 2025/2001

On Computational VSS for General Access Structures

Abstract

Verifiable Secret Sharing (VSS) schemes are fundamental building blocks in distributed cryptography. While most existing works focus on threshold structures, many real-world applications require more general access structures, where participants have different levels of power and only certain subsets are authorized to reconstruct the secret. Existing computational VSS schemes for general access structures typically rely on Discrete Logarithm (DL)-based homomorphic commitments, which limits their applicability, particularly in scenarios requiring Post-Quantum (PQ) security. In this work, we present a generalized version of $\mathrm{\Pi}$, a unified framework introduced at PKC 2025 for constructing computational VSS schemes without relying on homomorphic commitments. Our framework supports arbitrary monotone $\mathcal{Q}_2$ access structures, encompassing replicated and threshold secret sharing (e.g., Shamir's scheme), while preserving the efficiency and modularity of $\mathrm{\Pi}$. Notably, it requires only a random oracle and any commitment scheme satisfying hiding and binding, making it compatible with a wide range of instantiations, including PQ-secure commitments. In particular, our hash-based instantiation yields the first symmetric-key-based VSS scheme for general access structures. Compared to prior general-access VSS schemes based on homomorphic commitments (e.g., variants of Pedersen scheme from FC 2003), our DL-based constructions eliminate the need for homomorphic commitments and achieve asymptotic improvements in verification and reconstruction costs. We believe that this extension enhances the versatility of the original $\mathrm{\Pi}$ framework and paves the way for its deployment in a broader range of practical distributed systems.