The round complexity of verifiable secret sharing and secure multicast
- 6 July 2001
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 580-589
- https://doi.org/10.1145/380752.380853
Abstract
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.VSS allows a dealer to share a secret among several players in a way that would later allow a unique reconstruction of the secret. It is a well-studied primitive, which is used as a building block in virtually every general protocol for secure multi-party computation. Secure multicast is perhaps the simplest non-trivial instance of a secure computation. It allows a dealer to securely distribute an identical message to all players in a prescribed subset M. Both types of protocols are parameterized by the number of players, n, and a security threshold, t, which bounds the total number of malicious players (possibly including the dealer).We focus on a standard setting of perfect information-theoretic security, where all players have access to secure point-to-point channels and a common broadcast medium. For both types of primitives we prove, using related techniques, tight tradeoffs between the round complexity and the achievable security threshold. Specifically, for the VSS problem we show:2-round VSS is possible iff n4t, where the ``if'' direction is realized by an efficient protocol.3-round VSS is possible iff n3t, where the ``if'' direction is realized by an inefficient protocol.4-round efficient VSS is possible if n3t.For the secure multicast problem we show:2-round secure multicast is (efficiently) possible iffKeywords
This publication has 22 references indexed in Scilit:
- Security and Composition of Multiparty Cryptographic ProtocolsJournal of Cryptology, 2000
- Locally random reductions: Improvements and applicationsJournal of Cryptology, 1997
- Robust sharing of secrets when the dealer is honest or cheatingJournal of the ACM, 1994
- Fast consensus in networks of bounded degreeDistributed Computing, 1993
- Noninteractive Zero-KnowledgeSIAM Journal on Computing, 1991
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systemsJournal of the ACM, 1991
- Non-cryptographic fault-tolerant computing in constant number of rounds of interactionPublished by Association for Computing Machinery (ACM) ,1989
- Verifiable secret sharing and multiparty protocols with honest majorityPublished by Association for Computing Machinery (ACM) ,1989
- Reaching Agreement in the Presence of FaultsJournal of the ACM, 1980
- How to share a secretCommunications of the ACM, 1979