eprint.iacr.org will be offline for approximately an hour for routine maintenance again at 10pm UTC on Wednesday, April 17.

Paper 2023/992

VSS from Distributed ZK Proofs and Applications

Shahla Atapoor, COSIC, KU Leuven
Karim Baghery, COSIC, KU Leuven
Daniele Cozzo, IMDEA Software Institute, COSIC, KU Leuven
Robi Pedersen, COSIC, KU Leuven

Non-Interactive Verifiable Secret Sharing (NI-VSS) is a technique for distributing a secret among a group of individuals in a verifiable manner, such that shareholders can verify the validity of their received share and only a specific number of them can access the secret. VSS is a fundamental tool in cryptography and distributed computing. In this paper, we present an extremely efficient NI-VSS scheme using Zero-Knowledge (ZK) proofs on secret shared data. While prior VSS schemes have implicitly used ZK proofs on secret shared data, we specifically use their formal definition recently provided by Boneh et al. in CRYPTO 2019. The proposed NI-VSS scheme uses a quantum random oracle and a quantum computationally hiding commitment scheme in a black-box manner, which ensures its ease of use, especially in post-quantum threshold protocols. Implementation results further solidify its practicality and superiority over current constructions. With the new VSS scheme, for parameter sets $(n, t)=(128, 63)$ and $(2048, 1023)$, a dealer can share a secret in less than $0.02$ and $2.0$ seconds, respectively, and shareholders can verify their shares in less than $0.4$ and $5.0$ milliseconds. Compared to the well-established Pedersen VSS scheme, for the same parameter sets, at the cost of slightly higher communication, the new scheme is respectively $22.5\times$ and $3.25\times$ faster in the sharing phase, and notably needs $271\times$ and $479\times$ less time in the verification. Leveraging the new NI-VSS scheme, we revisit several classic and PQ-secure threshold protocols and improve their efficiency. Our revisions led to more efficient versions of both the Pedersen DKG protocol and the GJKR threshold signature scheme. We show similar efficiency enhancements and improved resilience to malicious parties in isogeny-based DKG and threshold signature schemes. We think, due to its remarkable efficiency and ease of use, the new NI-VSS scheme can be a valuable tool for a wide range of threshold protocols.

Note: This is the full version of the Asiacrypt 2023 paper.

Available format(s)
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
Verifiable Secret SharingZK Proofs on Secret Shared DataShamir Secret SharingDKGThreshold SignaturesIsogenies
Contact author(s)
shahla atapoor @ kuleuven be
baghery karim @ gmail com
daniele cozzo phd @ gmail com
robi pedersen @ esat kuleuven be
2023-10-05: revised
2023-06-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shahla Atapoor and Karim Baghery and Daniele Cozzo and Robi Pedersen},
      title = {VSS from Distributed ZK Proofs and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2023/992},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/992}},
      url = {https://eprint.iacr.org/2023/992}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.