Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM Symposium on Principles of Distributed Computing (PODC)

Information-Theoretic Optimistic Verifiable Secret Sharing

Chen-Da Liu-Zhang, Martin Hirt, Emanuele Marsicano

Published Jul 1, 2026• 0 citations
Publisher

Abstract

Verifiable secret sharing (VSS) is a fundamental primitive for secure computation and its round complexity has been well studied. The works of Gennaro et al. [STOC'01] and Fitzi et al. [TCC'06] settled the landscape in the perfect-security setting, showing that for the optimal corruption threshold t < n/3, the exact round complexity is three, and for the sub-optimal corruption threshold t < n/4 it is two rounds. Similarly, Patra et al. [CRYPTO'09] and Kumaresan et al. [ASIACRYPT'10] settled the landscape in the statistical setting, showing that for t < n/2 (resp. t < n/3), the exact round complexity is three (resp. two).

DOI
10.1145/3796701.3815927

Related papers

Improving the Round Complexity of VSS in Point-to-Point Networks.

Jonathan I. Katz, Chiu‐Yuen Koo, Ranjit Kumaresan

We revisit the following question: what is the optimal round complexity of verifiable secret sharing (VSS)? We focus here on the case of perfectly-secure VSS where the number of corrupted parties t satisfies t < n/3, with n being the total number of parties. Work of Gennaro et al. (STOC 2001) and Fitzi et al. (TCC 2006) shows that, assuming a broadcast channel, 3 rounds are necessary and sufficient for efficient VSS. The efficient 3-round protocol of Fitzi et al., however, treats the broadcast channel as being available “for free” and does not attempt to minimize its usage. This approach leads to relatively poor round complexity when protocols are compiled for a point-to-point network. We show here a VSS protocol that is simultaneously optimal in terms of both the number of rounds and the number of invocations of broadcast. Our protocol also has a certain “2-level sharing” property that makes it useful for constructing protocols for general secure computation.

•Jan 1, 2007•0 citations

The Round Complexity of General VSS.

Ashish Choudhury, Kaoru Kurosawa, Arpita Patra

The round complexity of verifiable secret sharing (VSS) schemes has been studied extensively for threshold adversaries. In particular, Fitzi et al. showed an efficient 3-round VSS for n ≥ 3t+1 [4], where an infinitely powerful adversary can corrupt t (or less) parties out of n parties. This paper shows that for non-threshold adversaries, 1. Two round VSS is possible iff the underlying adversary structure satisfies Q 4 condition; 2. Three round VSS is possible iff the underlying adversary structure satisfies Q 3 condition. Further as a special case of our three round protocol, we can obtain a more efficient 3-round VSS than the VSS of Fitzi et al. for n = 3t + 1. More precisely, the communication complexity of the reconstruction phase is reduced from O(n 3) to O(n 2). We finally point out a flaw in the reconstruction phase of VSS of Fitzi et al., and show how to fix it.

•Jan 1, 2010•0 citations

Broadcast and verifiable secret sharing: new security models and round optimal constructions

Jonathan I. Katz, Ranjit Kumaresan

Broadcast and verifiable secret sharing (VSS) are central building blocks for secure multi-party computation. These protocols are required to be resilient against a Byzantine adversary who controls at most t out of the n parties running the protocol. In this dissertation, we consider the design of fault-tolerant protocols for broadcast and verifiable secret sharing with stronger security guarantees and improved round complexity. Broadcast allows a party to send the same message to all parties, and all parties are assured they have received identical messages. Given a public-key infrastructure (PKI) and digital signatures, it is possible to construct broadcast protocols tolerating any number of corrupted parties. We address two important issues related to broadcast: (1) Almost all existing protocols do not distinguish between corrupted parties (who do not follow the protocol) and honest parties whose secret (signing) keys have been compromised (but who continue to behave honestly); (2) all existing protocols for broadcast are insecure against an adaptive adversary who can choose which parties to corrupt as the protocol progresses. We propose new security models that capture these issues, and present tight feasibility and impossibility results. In the problem of verifiable secret sharing, there is a designated player who shares a secret during an initial sharing phase such that the secret is hidden from an adversary that corrupts at most t parties. In a subsequent reconstruction phase of the protocol, a unique secret, well-defined by the view of honest players in the sharing phase, is reconstructed. The round complexity of VSS protocols is a very important metric of their efficiency. We show two improvements regarding the round complexity of information-theoretic VSS. First, we construct an efficient perfectly secure VSS protocol tolerating t < n/3 corrupted parties that is simultaneously optimal in both the number of rounds and the number of invocations of broadcast. Second, we construct a statistically secure VSS protocol tolerating t < n/2 corrupted parties that has optimal round complexity, and an efficient statistical VSS protocol tolerating t < n/2 corrupted parties that requires one additional round.

•Jan 1, 2012•1 citation

Broadcast (and Round) Efficient Verifiable Secret Sharing ∗

Juan A. Garay, Clint Givens, Rafail Ostrovsky +1 more

Verifiable secret sharing (VSS) is a fundamental cryptographic primitive, lying at the core of secure multi-party computation (MPC) and, as the distributed analogue of a commitment functionality, used in numerous applications. In this paper we focus on unconditionally secure VSS protocols with honest majority. In this setting it is typically assumed that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Because broadcast cannot be simulated on a point-to-point network when a third or more of the parties are corrupt, it is impossible to construct VSS (and more generally, MPC) protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of VSS, primarily in terms of round complexity. In this work we consider a refinement of the round complexity of VSS, by adding a measure we term broadcast complexity. We view the broadcast channel as an expensive resource and seek to minimize the number of rounds in which it is invoked as well. We construct a (linear) VSS protocol which uses the broadcast channel only twice in the sharing phase, while running in an overall constant number of rounds. 1

•Jan 1, 2013•0 citations

Network-Agnostic Verifiable Secret Sharing With Cryptographic Security

Nidhish Bhimrajka, Ashish Choudhury, Supreeth Varadarajan

Verifiable Secret-Sharing(VSS) is a fundamental primitive in secure distributed computing that allows a designated dealer to share a secret amongnparties in the presence of an adversary controlling at mosttof them. We study VSS in the presence ofcomputationally-boundedadversaries. Known VSS protocols tolerate up totstaperfectsecurity (Appan et al. IEEE IT 2023) where the threshold conditions arenotknown to be optimal or withstatistical security(Appan et al. TCC 2023) where the threshold conditions are optimal, but the parties need to performexponentialamount of computation and communication. Using our VSS protocol, we design a secureMulti-Party Computation(MPC) protocol in theplain Public Key Infrastructure (PKI) model, i.e., without assuming an expensive trusted setup. Although our proposed MPC protocol incurs higher communication complexity than state-of-the-art network-agnostic MPC protocols, it motivates alternative directions for designingcomputationally inexpensiveMPC protocols based on a plain PKI setup, which has not been explored in the domain of computationally secure networkagnostic MPC and offers valuable insights into designing it.

IEEE Transactions on Information Theory•Dec 11, 2025•0 citations

The round complexity of verifiable secret sharing and secure multicast

Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz Z +1 more

The round complexity of interactive protocols is one of their most important complexity measures. In this work we study the exact round complexity of two basic secure computation tasks: Verifiable Secret Sharing (VSS) and Secure Multicast.

ACM Symposium on Theory of Computing (STOC)•Jul 6, 2001•137 citations
Verifiable secret sharing (VSS) is a fundamental primitive for secure computation and its round complexity has been well studied. The works of Gennaro et al. [STOC'01] and Fitzi et al. [TCC'06] settled the landscape in the perfect-security setting, showing that for the optimal corruption threshold t < n/3, the exact round complexity is three, and for the sub-optimal corruption threshold t < n/4 it is two rounds. Similarly, Patra et al. [CRYPTO'09] and Kumaresan et al. [ASIACRYPT'10] settled the landscape in the statistical setting, showing that for t < n/2 (resp. t < n/3), the exact round complexity is three (resp. two).
We revisit the following question: what is the optimal round complexity of verifiable secret sharing (VSS)? We focus here on the case of perfectly-secure VSS where the number of corrupted parties t satisfies t < n/3, with n being the total number of parties. Work of Gennaro et al. (STOC 2001) and Fitzi et al. (TCC 2006) shows that, assuming a broadcast channel, 3 rounds are necessary and sufficient for efficient VSS. The efficient 3-round protocol of Fitzi et al., however, treats the broadcast channel as being available “for free” and does not attempt to minimize its usage. This approach leads to relatively poor round complexity when protocols are compiled for a point-to-point network. We show here a VSS protocol that is simultaneously optimal in terms of both the number of rounds and the number of invocations of broadcast. Our protocol also has a certain “2-level sharing” property that makes it useful for constructing protocols for general secure computation.
The round complexity of verifiable secret sharing (VSS) schemes has been studied extensively for threshold adversaries. In particular, Fitzi et al. showed an efficient 3-round VSS for n ≥ 3t+1 [4], where an infinitely powerful adversary can corrupt t (or less) parties out of n parties. This paper shows that for non-threshold adversaries, 1. Two round VSS is possible iff the underlying adversary structure satisfies Q 4 condition; 2. Three round VSS is possible iff the underlying adversary structure satisfies Q 3 condition. Further as a special case of our three round protocol, we can obtain a more efficient 3-round VSS than the VSS of Fitzi et al. for n = 3t + 1. More precisely, the communication complexity of the reconstruction phase is reduced from O(n 3) to O(n 2). We finally point out a flaw in the reconstruction phase of VSS of Fitzi et al., and show how to fix it.
Broadcast and verifiable secret sharing (VSS) are central building blocks for secure multi-party computation. These protocols are required to be resilient against a Byzantine adversary who controls at most t out of the n parties running the protocol. In this dissertation, we consider the design of fault-tolerant protocols for broadcast and verifiable secret sharing with stronger security guarantees and improved round complexity. Broadcast allows a party to send the same message to all parties, and all parties are assured they have received identical messages. Given a public-key infrastructure (PKI) and digital signatures, it is possible to construct broadcast protocols tolerating any number of corrupted parties. We address two important issues related to broadcast: (1) Almost all existing protocols do not distinguish between corrupted parties (who do not follow the protocol) and honest parties whose secret (signing) keys have been compromised (but who continue to behave honestly); (2) all existing protocols for broadcast are insecure against an adaptive adversary who can choose which parties to corrupt as the protocol progresses. We propose new security models that capture these issues, and present tight feasibility and impossibility results. In the problem of verifiable secret sharing, there is a designated player who shares a secret during an initial sharing phase such that the secret is hidden from an adversary that corrupts at most t parties. In a subsequent reconstruction phase of the protocol, a unique secret, well-defined by the view of honest players in the sharing phase, is reconstructed. The round complexity of VSS protocols is a very important metric of their efficiency. We show two improvements regarding the round complexity of information-theoretic VSS. First, we construct an efficient perfectly secure VSS protocol tolerating t < n/3 corrupted parties that is simultaneously optimal in both the number of rounds and the number of invocations of broadcast. Second, we construct a statistically secure VSS protocol tolerating t < n/2 corrupted parties that has optimal round complexity, and an efficient statistical VSS protocol tolerating t < n/2 corrupted parties that requires one additional round.
Verifiable secret sharing (VSS) is a fundamental cryptographic primitive, lying at the core of secure multi-party computation (MPC) and, as the distributed analogue of a commitment functionality, used in numerous applications. In this paper we focus on unconditionally secure VSS protocols with honest majority. In this setting it is typically assumed that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Because broadcast cannot be simulated on a point-to-point network when a third or more of the parties are corrupt, it is impossible to construct VSS (and more generally, MPC) protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of VSS, primarily in terms of round complexity. In this work we consider a refinement of the round complexity of VSS, by adding a measure we term broadcast complexity. We view the broadcast channel as an expensive resource and seek to minimize the number of rounds in which it is invoked as well. We construct a (linear) VSS protocol which uses the broadcast channel only twice in the sharing phase, while running in an overall constant number of rounds. 1
Verifiable Secret-Sharing(VSS) is a fundamental primitive in secure distributed computing that allows a designated dealer to share a secret amongnparties in the presence of an adversary controlling at mosttof them. We study VSS in the presence ofcomputationally-boundedadversaries. Known VSS protocols tolerate up totstaperfectsecurity (Appan et al. IEEE IT 2023) where the threshold conditions arenotknown to be optimal or withstatistical security(Appan et al. TCC 2023) where the threshold conditions are optimal, but the parties need to performexponentialamount of computation and communication. Using our VSS protocol, we design a secureMulti-Party Computation(MPC) protocol in theplain Public Key Infrastructure (PKI) model, i.e., without assuming an expensive trusted setup. Although our proposed MPC protocol incurs higher communication complexity than state-of-the-art network-agnostic MPC protocols, it motivates alternative directions for designingcomputationally inexpensiveMPC protocols based on a plain PKI setup, which has not been explored in the domain of computationally secure networkagnostic MPC and offers valuable insights into designing it.