Paper 2023/1669

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

Karim Baghery, COSIC, KU Leuven
Abstract

An $(n, t)$-Verifiable Secret Sharing (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 VSS schemes in the honest majority setting. Notably, $\Pi$ does not rely on homomorphic commitments; instead requires a random oracle and any commitment scheme that extra to its core attributes hiding and binding, it might be homomorphic and/or post-quantum (PQ) secure. - When employing Discrete Logarithm (DL)-based commitments, $\Pi$ enables the construction of two novel VSS schemes in the RO model, named $\Pi_P$ and $\Pi_F$. Compared to the well-known Pedersen and Feldman VSS schemes, both $\Pi_P$ and $\Pi_F$ require $O(1)$ (resp. $O(t)$) exponentiations in the verification (resp. reconstruction) process, as opposed to $O(t)$ (resp. $O(t^2)$), albeit at the expense of a constant factor slower sharing and increased communication. - By instantiating $\Pi$ with a hash-based commitment, we obtain a novel PQ-secure VSS scheme, labeled $\Pi_{LA}$. $\Pi_{LA}$ outperforms the recent protocol by Atapoor, Baghery, Cozzo, and Pedersen from Asiacrypt'23 by a constant factor in all metrics. $\Pi_{LA}$ can also be seen as an amplified version of the simple 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Verifiable Secret SharingPolynomial Discrete Logarithm
Contact author(s)
baghery karim @ gmail com
History
2024-05-23: last of 2 revisions
2023-10-27: received
See all versions
Short URL
https://ia.cr/2023/1669
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1669,
      author = {Karim Baghery},
      title = {$\Pi$: A Unified Framework for Verifiable Secret Sharing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1669},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1669}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.