VSS from Distributed ZK Proofs and Applications

Shahla Atapoor; Karim Baghery; Daniele Cozzo; Robi Pedersen

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

Abstract

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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A minor revision of an IACR publication in ASIACRYPT 2023
Keywords: Verifiable Secret Sharing ZK Proofs on Secret Shared Data Shamir Secret Sharing DKG Threshold Signatures Isogenies
Contact author(s): shahla atapoor @ kuleuven be
baghery karim @ gmail com
daniele cozzo phd @ gmail com
robi pedersen @ esat kuleuven be
History: 2023-10-05: revised; 2023-06-26: received; See all versions
Short URL: https://ia.cr/2023/992
License: CC BY

BibTeX

@misc{cryptoeprint:2023/992,
      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},
      url = {https://eprint.iacr.org/2023/992}
}