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, imec-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 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. Our 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. The practicality of the proposed NI-VSS is confirmed by our implementation results, establishing it as a viable choice for large-scale threshold protocols. Using the proposed NI-VSS scheme, a dealer can share a secret with 4096 parties in less than 2 seconds, and the shareholders can verify the validity of their shares in less than 2 milliseconds. We demonstrate the potential of new NI-VSS scheme by revisiting several threshold protocols and improving their efficiency. Specifically, we present two DKG protocols for CSIDH-based primitives, that outperform the current state of the art. Furthermore, we show similar improvements in some threshold signatures built based on Schnorr and CSI-FiSh 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.

Available format(s)
Cryptographic protocols
Publication info
Verifiable Secret SharingZK Proofs on Secret Shared DataDKGThreshold SignaturesCSIDH
Contact author(s)
shahla atapoor @ kuleuven be
baghery karim @ gmail com
daniele cozzo phd @ gmail com
robi pedersen @ esat kuleuven be
2023-06-26: approved
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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.