Paper 2023/1669

$\Pi$: A Unified Framework for Verifiable Secret Sharing

Abstract

An $(n, t)$-Non-Interactive Verifiable Secret Sharing (NI-VSS) scheme allows a dealer to share a secret among $n$ parties, s.t. all the parties can verify the validity of their shares and only a set of them, i.e., more than $t$, can access the secret. In this paper, we present $\Pi$, as a unified framework for building NI-VSS schemes in the majority honest setting. Notably, $\Pi$ does not rely on homomorphic commitments; instead requires a Random Oracle (RO) and any commitment scheme that extra to its core attributes hiding and binding, it might be homomorphic and/or PQ-secure. - When employing Discrete Logarithm (DL)-based commitments, $\Pi$ enables the construction of two novel NI-VSS schemes in the RO model, named $\Pi_P$ and $\Pi_F$. In comparison to the well-known Pedersen and Feldman VSS schemes, both $\Pi_P$ and $\Pi_F$ require $O(1)$ exponentiations in the verification process, as opposed to $O(t)$, albeit at the expense of a slightly slower sharing phase and increased communication. - By instantiating $\Pi$ with a hash-based commitment scheme, we obtain an efficient NI-VSS scheme in the quantum RO model, labeled $\Pi_{LA}$ (pronounced [paɪla]). $\Pi_{LA}$ outperforms the recent construction by Atapoor, Baghery, Cozzo, and Pedersen from Asiacrypt'23 by a constant factor in all metrics. $\Pi_{LA}$ can also be viewed as an amplified version of the $\it{simple}$ NI-VSS scheme, proposed by Gennaro, Rabin, and Rabin, at PODC'98. - Building upon $\Pi_F$, we construct a Publicly VSS (PVSS) scheme, labeled $\Pi_S$, that can be seen as a new variant of Schoenmakers' scheme from Crypto'99. To this end, we first define the Polynomial Discrete Logarithm (PDL) problem, as a generalization of DL and then build a variant of the Schnorr Proof of Knowledge (PoK) scheme based on the new hardness assumption. We think the PDL relation and the associated PoK scheme can be independently interesting for Shamir-based threshold protocols. We believe $\Pi$ is general enough to be employed in various contexts such as lattices, isogenies, and an extensive array of practical use cases.

Note: In Turkish, 'Pay' (pronounced [paɪ]) is a noun for Share, and 'Payla' means Share it.