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

Broadcast (and Round) Efficient Verifiable Secret Sharing ∗

Juan A. Garay, Clint Givens, Rafail Ostrovsky, Pavel Raykov

Published Jan 1, 2013• 0 citations
OpenAlex

Abstract

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

Related papers

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

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

Broadcast-Efficient Secure Multiparty Computation.

Juan A. Garay, Clint Givens, Rafail Ostrovsky

Secure multiparty computation (MPC) is perhaps the most popular paradigm in the area of cryptographic protocols. It allows several mutually untrustworthy parties to jointly compute a function of their private inputs, without revealing to each other information about those inputs. In the case of unconditional (information-theoretic) security, protocols are known which tolerate a dishonest minority of players, who may coordinate their attack and deviate arbitrarily from the protocol specification. It is typically assumed in these results that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Broadcast allows one party to send a consistent message to all other parties, guaranteeing consistency even if the broadcaster is corrupted. Because broadcast cannot be simulated on the point-to-point network when more than a third of the parties are corrupt, it is impossible to construct general 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 MPC, primarily in terms of round complexity and communication complexity. In this work we propose a refinement of the round complexity which we term broadcast complexity. We view the broadcast channel as an expensive resource

•Jan 1, 2012•3 citations

Round efficient computationally secure multi-party computation revisited

Laasya Bangalore, Ashish Choudhury, Gayathri Garimella

In this work, we consider the problem of secure multi-party computation (MPC) with n parties where at most t are under the control of a computationally bounded adversary given the constraint t < n/2. We aim to design a round efficient protocol by minimizing the number of rounds in which the broadcast primitive is involved. In this setting, the previous best protocol can be attributed to Katz-Koo (EUROCRYPT 2007) which is set in the offline-online paradigm (where the parties generate preprocessing data during the offline phase to lighten the computation in the online phase). Their online phase is a constant round protocol with no invocations of broadcast, while the offline phase protocol needs total 29 rounds with a broadcast invocation in one round. Our work improves the round complexity of their offline phase protocol, by running in 4 rounds, with only a single broadcast round. Additionally, we also improve the communication complexity of the offline phase protocol by a factor of Ω(n3). As a technical contribution, we present the first two round computationally-secure verifiable secret-sharing (VSS) scheme that invokes broadcast in only one round.

International Conference on Distributed Computing and Networking (ICDCN)•Jan 4, 2019•3 citations

Round and Communication Efficient Unconditionally-secure MPC with t < n/3 in Partially Synchronous Network.

Ashish Choudhury, Arpita Patra, Divya Ravi

In this work, we study unconditionally-secure multi-party computation (MPC) tolerating \(t < n/3\) corruptions, where n is the total number of parties involved. In this setting, it is well known that if the underlying network is completely asynchronous, then one can achieve only statistical security; moreover it is impossible to ensure input provision and consider inputs of all the honest parties. The best known statistically-secure asynchronous MPC (AMPC) with \(t<n/3\) requires a communication of \(\varOmega (n^5)\) field elements per multiplication. We consider a partially synchronous setting, where the parties are assumed to be globally synchronized initially for few rounds and then the network becomes completely asynchronous. In such a setting, we present a MPC protocol, which requires \(\mathcal {O}(n^2)\) communication per multiplication while ensuring input provision. Our MPC protocol relies on a new four round, communication efficient statistical verifiable secret-sharing (VSS) protocol with broadcast communication complexity independent of the number of secret-shared values.

•Jan 1, 2017•0 citations

Efficient Statistical Asynchronous Verifiable Secret Sharing and Multiparty Computation with Optimal Resilience.

Arpita Patra, Ashish Choudhary, Chandrasekharan Pandu Rangan

Verifiable Secret Sharing (VSS) is a fundamental primitive used as a building block in many distributed cryptographic tasks, such as Secure Multiparty Computation (MPC) and Byzantine Agreement (BA). An important variant of VSS is Asynchronous VSS (AVSS) which is designed to work over asynchronous networks. AVSS is a two phase (Sharing, Reconstruction) protocol carried out among n parties in the presence of a computationally unbounded active adversary, who can corrupt up to t parties. We assume that every two parties in the network are directly connected by a pairwise secure channel. In this paper, we present a new statistical AVSS protocol with optimal 5 resilience; i.e. with n = 3t + 1. Our protocol privately communicates

•Jan 1, 2009•6 citations
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
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.
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.
Secure multiparty computation (MPC) is perhaps the most popular paradigm in the area of cryptographic protocols. It allows several mutually untrustworthy parties to jointly compute a function of their private inputs, without revealing to each other information about those inputs. In the case of unconditional (information-theoretic) security, protocols are known which tolerate a dishonest minority of players, who may coordinate their attack and deviate arbitrarily from the protocol specification. It is typically assumed in these results that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Broadcast allows one party to send a consistent message to all other parties, guaranteeing consistency even if the broadcaster is corrupted. Because broadcast cannot be simulated on the point-to-point network when more than a third of the parties are corrupt, it is impossible to construct general 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 MPC, primarily in terms of round complexity and communication complexity. In this work we propose a refinement of the round complexity which we term broadcast complexity. We view the broadcast channel as an expensive resource
In this work, we consider the problem of secure multi-party computation (MPC) with n parties where at most t are under the control of a computationally bounded adversary given the constraint t < n/2. We aim to design a round efficient protocol by minimizing the number of rounds in which the broadcast primitive is involved. In this setting, the previous best protocol can be attributed to Katz-Koo (EUROCRYPT 2007) which is set in the offline-online paradigm (where the parties generate preprocessing data during the offline phase to lighten the computation in the online phase). Their online phase is a constant round protocol with no invocations of broadcast, while the offline phase protocol needs total 29 rounds with a broadcast invocation in one round. Our work improves the round complexity of their offline phase protocol, by running in 4 rounds, with only a single broadcast round. Additionally, we also improve the communication complexity of the offline phase protocol by a factor of Ω(n3). As a technical contribution, we present the first two round computationally-secure verifiable secret-sharing (VSS) scheme that invokes broadcast in only one round.
In this work, we study unconditionally-secure multi-party computation (MPC) tolerating t<n/3t < n/3t<n/3 corruptions, where n is the total number of parties involved. In this setting, it is well known that if the underlying network is completely asynchronous, then one can achieve only statistical security; moreover it is impossible to ensure input provision and consider inputs of all the honest parties. The best known statistically-secure asynchronous MPC (AMPC) with t<n/3t<n/3t<n/3 requires a communication of Ω(n5)\varOmega (n^5)Ω(n5) field elements per multiplication. We consider a partially synchronous setting, where the parties are assumed to be globally synchronized initially for few rounds and then the network becomes completely asynchronous. In such a setting, we present a MPC protocol, which requires O(n2)\mathcal {O}(n^2)O(n2) communication per multiplication while ensuring input provision. Our MPC protocol relies on a new four round, communication efficient statistical verifiable secret-sharing (VSS) protocol with broadcast communication complexity independent of the number of secret-shared values.
Verifiable Secret Sharing (VSS) is a fundamental primitive used as a building block in many distributed cryptographic tasks, such as Secure Multiparty Computation (MPC) and Byzantine Agreement (BA). An important variant of VSS is Asynchronous VSS (AVSS) which is designed to work over asynchronous networks. AVSS is a two phase (Sharing, Reconstruction) protocol carried out among n parties in the presence of a computationally unbounded active adversary, who can corrupt up to t parties. We assume that every two parties in the network are directly connected by a pairwise secure channel. In this paper, we present a new statistical AVSS protocol with optimal 5 resilience; i.e. with n = 3t + 1. Our protocol privately communicates