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

Lecture notes in computer science

The Round Complexity of Verifiable Secret Sharing: The Statistical Case

Ranjit Kumaresan, Arpita Patra, Chandrasekharan Pandu Rangan

Published Jan 1, 2010• 46 citations
Publisher
DOI
10.1007/978-3-642-17373-8_25

Related papers

Broadcast (and Round) Efficient Verifiable Secret Sharing

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

Lecture notes in computer science•Jan 1, 2014•10 citations

Constant-round reconstruction for rational secret sharing

Akinori Kawachi, Yoshio Okamoto, Tanaka Keisuke +1 more

IEICE Technical Report; IEICE Tech. Rep.•Nov 26, 2010•0 citations

General Constructions of Rational Secret Sharing with Expected Constant-Round Reconstruction

KEISUKE TANAKA, 亮周 河内, Akinori Kawachi +2 more

•Dec 1, 2016•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

Verifiable Secret Sharing as Secure Computation

Rosario Gennaro, Silvio M. Micali

Lecture notes in computer science•Jan 1, 1995•33 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
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.