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

IEEE Transactions on Parallel and Distributed Systems

A protocol to achieve independence in constant rounds

Rosario Gennaro

Published Jul 1, 2000• 17 citations
Publisher

Abstract

Independence is a fundamental property needed to achieve security in fault-tolerant distributed computing. In practice, distributed communication networks are neither fully synchronous or fully asynchronous, but rather loosely synchronized. By this, we mean that in a communication protocol, messages at a given round may depend on messages from other players at the same round. These possible dependencies among messages create problems if we need n players to announce independently chosen values. This task is called simultaneous broadcast. In this paper, we present the first constant round protocol for simultaneous broadcast in a reasonable computation model (which includes a common shared random string among the players). The protocol is provably secure under general cryptographic assumptions. In the process, we develop a new and stronger formal definition for this problem. Previously known protocols for this task required either O(log n) or expected constant rounds to complete (depending on the computation model considered).

DOI
10.1109/71.877748

Related papers

Achieving independence in logarithmic number of rounds

Benny Chor, Michael O. Rabin

Simultaneous broadcast [CGMAJ is a fundamental tool in designing secure protocols for fault tolerant distributed computing.A system that supports it enables n processes to globally commit to independently chosen values (a significantly harder task than mere agreement).It is also a basic building block in a recent %ompleteness" theorem of [GMWZ].In this paper we present a new protocol for simultaneous broadcast.Building upon past work, we introduce a novel method of concurrently alternating and interleaving n executions of verifiable secret sharing protocols.This approach greatly improves the time complexity (number of communication rounds) of simultaneous broadcast.Previous protocols (combination of [CGMA] and [GMW]) q re uired the complete serialization of the ra verifiable secret sharings, resulting in n(n) communication rounds.Our protocol is constructive, and requires only log n + log log n serial executions of verifiable secret sharings.It preserves maximum fault tolerance (t < n/2 faults), and polynomial resource bounds (internal computation and communication bits).The same improvement appiies to the general simulation in [GMWX].In light of its improved performance, it is significant that our our protocol has a fairly simple correctness proof.In the slippery business of distributed cryptographic protocols, simpler proofs are important.

ACM Symposium on Principles of Distributed Computing (PODC)•Jan 1, 1987•48 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

Security, Fault Tolerance, and Communication Complexity in Distributed Systems

Donald Beaver

We present efficient and practical algorithms for a large, distributed system of processors to achieve reliable computations in a secure manner. Specifically, we address the problem of computing a general function of several private inputs distributed among the processors of a network, while ensuring the correctness of the results and the privacy of the inputs, despite accidental or malicious faults in the system. [...] Our algorithms maintain a low cost in local processing time, are the first to achieve optimal levels of fault-tolerance, and most importantly, have low communication complexity. In contrast to the best known previous methods, which require large numbers of rounds even for fairly simple computations, we devise protocols that use small messages and a constant number of rounds regardless of the complexity of the function to be computed. Through direct algebraic approaches, we separate the communication complexity of secure computing from the computational complexity of the function to be computed. We examine security under both the modern approach of computational complexity-based cryptography and the classical approach of unconditional, information-theoretic security. We [...] support formal proofs of claims to security, addressing an important deficiency in the literature. Our protocols are provably secure. In the realm of information-theoretic security, we characterize those functions which two parties can compute jointly with absolute privacy. We also characterize those functions which a weak processor can compute using the aid of powerful processors without having to reveal the instances of the problem it would like to solve. Our methods include a promising new technique called a locally random reduction, which has given rise not only to efficient solutions for many of the problems considered in this work but to several powerful new results in complexity theory.

arXiv:2101.12143•Jan 28, 2021•9 citations

Security, fault tolerance, and communication complexity in distributed systems

Michael O. Rabin, Donald Beaver

We present efficient and practical algorithms for a large, distributed system of processors to achieve reliable computations in a secure manner. Specifically, we address the problem of computing a general function of several private inputs distributed among the processors of a network, while ensuring the correctness of the results and the privacy of the inputs, despite accidental or malicious faults in the system. Communication is often the most significant bottleneck in distributed computing. Our algorithms maintain a low cost in local processing time, are the first to achieve optimal levels of fault-tolerance, and most importantly, have low communication complexity. In contrast to the best known previous methods, which require large numbers of rounds even for fairly simple computations, we devise protocols that use small messages and a constant number of rounds regardless of the complexity of the function to be computed. Through direct algebraic approaches, we separate the communication complexity of secure computing from the computational complexity of the function to be computed. We examine security under both the modern approach of computational complexity-based cryptography and the classical approach of unconditional, information-theoretic security. We develop a clear and concise set of definitions that support formal proofs of claims to security, addressing an important deficiency in the literature. Our protocols are provably secure. In the realm of information-theoretic security, we characterize those functions which two parties can compute jointly with absolute privacy. We also characterize those functions which a weak processor can compute using the aid of powerful processors without having to reveal the instances of the problem it would like to solve. Our methods include a promising new technique called a locally random reduction, which has given rise not only to efficient solutions for many of the problems considered in this work but to several powerful new results in complexity theory.

•Jan 1, 1990•17 citations

Round-Preserving Parallel Composition of Probabilistic-Termination Cryptographic Protocols

Ran Cohen, Sandro Coretti, Juan A. Garay +1 more

An important benchmark for multi-party computation protocols (MPC) is their round complexity. For several important MPC tasks, such as broadcast, (tight) lower bounds on the round complexity are known. However, some of these lower bounds can be circumvented when the termination round of every party is not a priori known, and simultaneous termination is not guaranteed. Protocols with this property are called probabilistic-termination (PT) protocols. Running PT protocols in parallel affects the round complexity of the resulting protocol in somewhat unexpected ways. For instance, an execution of m protocols with constant expected round complexity might take $$O(\log m)$$ rounds to complete. In a seminal work, Ben-Or and El-Yaniv (Distributed Computing ‘03) developed a technique for a parallel execution of arbitrarily many broadcast protocols, while preserving expected round complexity. More recently, Cohen et al. (CRYPTO ‘16) devised a framework for universal composition of PT protocols, and provided the first composable parallel-broadcast protocol with a simulation-based proof. These constructions crucially rely on the fact that broadcast is “privacy-free,” and do not generalize to arbitrary protocols in a straightforward way. This raises the question of whether it is possible to execute arbitrary PT protocols in parallel, without increasing the round complexity. In this paper we tackle this question and provide both feasibility and infeasibility results. We construct a round-preserving protocol compiler, tolerating any dishonest minority of actively corrupted parties, that compiles arbitrary protocols into a protocol realizing their parallel composition, while having a black-box access to the underlying protocols. Furthermore, we prove that the same cannot be achieved, using known techniques, given only black-box access to the functionalities realized by the protocols, unless merely security against semi-honest corruptions is required, for which case we provide a protocol. To prove our results, we utilize the language and results by Cohen et al., which we extend to capture parallel composition and reactive functionalities, and to handle the case of an honest majority.

Journal of Cryptology•Mar 9, 2021•14 citations

The round complexity of secure protocols

Donald Beaver, Silvio M. Micali, Phillip Rogaway

In a network of n players, each player i having private input zi, we show how the players can collaboratively evaluate a function f(zl, ..., zn) in a way that does not compromise the privacy of the players' inputs, and yet requires only a constant number of rounds of interaction.The underlying model of computation is a complete network of private channels, with broadcast, and a majority of the players must behave honestly.Our solution assumes the existence of a one-way function.share bi to player i.For some parameter t, t < n/2, we require that no t players get information about b from their pieces; and yet, b is recoverable, and is known to be recoverable, given the cooperation of the n -t good players--even if the t bad players try to obstruct b's recovery, or try to alter the recovered value.The value b which a player has effectively "committed to" is independent of the values that honest players may concurrently be committing to.After the sharing stage, a computation stage follows, in which each player, given his own shares of xl, ..., x,~, computes his own share of f(zt,..., z,~).To accomplish this, the function f to be evaluated is represented by a

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1990•824 citations
Independence is a fundamental property needed to achieve security in fault-tolerant distributed computing. In practice, distributed communication networks are neither fully synchronous or fully asynchronous, but rather loosely synchronized. By this, we mean that in a communication protocol, messages at a given round may depend on messages from other players at the same round. These possible dependencies among messages create problems if we need n players to announce independently chosen values. This task is called simultaneous broadcast. In this paper, we present the first constant round protocol for simultaneous broadcast in a reasonable computation model (which includes a common shared random string among the players). The protocol is provably secure under general cryptographic assumptions. In the process, we develop a new and stronger formal definition for this problem. Previously known protocols for this task required either O(log n) or expected constant rounds to complete (depending on the computation model considered).
Simultaneous broadcast [CGMAJ is a fundamental tool in designing secure protocols for fault tolerant distributed computing.A system that supports it enables n processes to globally commit to independently chosen values (a significantly harder task than mere agreement).It is also a basic building block in a recent %ompleteness" theorem of [GMWZ].In this paper we present a new protocol for simultaneous broadcast.Building upon past work, we introduce a novel method of concurrently alternating and interleaving n executions of verifiable secret sharing protocols.This approach greatly improves the time complexity (number of communication rounds) of simultaneous broadcast.Previous protocols (combination of [CGMA] and [GMW]) q re uired the complete serialization of the ra verifiable secret sharings, resulting in n(n) communication rounds.Our protocol is constructive, and requires only log n + log log n serial executions of verifiable secret sharings.It preserves maximum fault tolerance (t < n/2 faults), and polynomial resource bounds (internal computation and communication bits).The same improvement appiies to the general simulation in [GMWX].In light of its improved performance, it is significant that our our protocol has a fairly simple correctness proof.In the slippery business of distributed cryptographic protocols, simpler proofs are important.
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 present efficient and practical algorithms for a large, distributed system of processors to achieve reliable computations in a secure manner. Specifically, we address the problem of computing a general function of several private inputs distributed among the processors of a network, while ensuring the correctness of the results and the privacy of the inputs, despite accidental or malicious faults in the system. [...] Our algorithms maintain a low cost in local processing time, are the first to achieve optimal levels of fault-tolerance, and most importantly, have low communication complexity. In contrast to the best known previous methods, which require large numbers of rounds even for fairly simple computations, we devise protocols that use small messages and a constant number of rounds regardless of the complexity of the function to be computed. Through direct algebraic approaches, we separate the communication complexity of secure computing from the computational complexity of the function to be computed. We examine security under both the modern approach of computational complexity-based cryptography and the classical approach of unconditional, information-theoretic security. We [...] support formal proofs of claims to security, addressing an important deficiency in the literature. Our protocols are provably secure. In the realm of information-theoretic security, we characterize those functions which two parties can compute jointly with absolute privacy. We also characterize those functions which a weak processor can compute using the aid of powerful processors without having to reveal the instances of the problem it would like to solve. Our methods include a promising new technique called a locally random reduction, which has given rise not only to efficient solutions for many of the problems considered in this work but to several powerful new results in complexity theory.
We present efficient and practical algorithms for a large, distributed system of processors to achieve reliable computations in a secure manner. Specifically, we address the problem of computing a general function of several private inputs distributed among the processors of a network, while ensuring the correctness of the results and the privacy of the inputs, despite accidental or malicious faults in the system. Communication is often the most significant bottleneck in distributed computing. Our algorithms maintain a low cost in local processing time, are the first to achieve optimal levels of fault-tolerance, and most importantly, have low communication complexity. In contrast to the best known previous methods, which require large numbers of rounds even for fairly simple computations, we devise protocols that use small messages and a constant number of rounds regardless of the complexity of the function to be computed. Through direct algebraic approaches, we separate the communication complexity of secure computing from the computational complexity of the function to be computed. We examine security under both the modern approach of computational complexity-based cryptography and the classical approach of unconditional, information-theoretic security. We develop a clear and concise set of definitions that support formal proofs of claims to security, addressing an important deficiency in the literature. Our protocols are provably secure. In the realm of information-theoretic security, we characterize those functions which two parties can compute jointly with absolute privacy. We also characterize those functions which a weak processor can compute using the aid of powerful processors without having to reveal the instances of the problem it would like to solve. Our methods include a promising new technique called a locally random reduction, which has given rise not only to efficient solutions for many of the problems considered in this work but to several powerful new results in complexity theory.
An important benchmark for multi-party computation protocols (MPC) is their round complexity. For several important MPC tasks, such as broadcast, (tight) lower bounds on the round complexity are known. However, some of these lower bounds can be circumvented when the termination round of every party is not a priori known, and simultaneous termination is not guaranteed. Protocols with this property are called probabilistic-termination (PT) protocols. Running PT protocols in parallel affects the round complexity of the resulting protocol in somewhat unexpected ways. For instance, an execution of m protocols with constant expected round complexity might take O(log⁡m)O(\log m)O(logm) rounds to complete. In a seminal work, Ben-Or and El-Yaniv (Distributed Computing ‘03) developed a technique for a parallel execution of arbitrarily many broadcast protocols, while preserving expected round complexity. More recently, Cohen et al. (CRYPTO ‘16) devised a framework for universal composition of PT protocols, and provided the first composable parallel-broadcast protocol with a simulation-based proof. These constructions crucially rely on the fact that broadcast is “privacy-free,” and do not generalize to arbitrary protocols in a straightforward way. This raises the question of whether it is possible to execute arbitrary PT protocols in parallel, without increasing the round complexity. In this paper we tackle this question and provide both feasibility and infeasibility results. We construct a round-preserving protocol compiler, tolerating any dishonest minority of actively corrupted parties, that compiles arbitrary protocols into a protocol realizing their parallel composition, while having a black-box access to the underlying protocols. Furthermore, we prove that the same cannot be achieved, using known techniques, given only black-box access to the functionalities realized by the protocols, unless merely security against semi-honest corruptions is required, for which case we provide a protocol. To prove our results, we utilize the language and results by Cohen et al., which we extend to capture parallel composition and reactive functionalities, and to handle the case of an honest majority.
In a network of n players, each player i having private input zi, we show how the players can collaboratively evaluate a function f(zl, ..., zn) in a way that does not compromise the privacy of the players' inputs, and yet requires only a constant number of rounds of interaction.The underlying model of computation is a complete network of private channels, with broadcast, and a majority of the players must behave honestly.Our solution assumes the existence of a one-way function.share bi to player i.For some parameter t, t < n/2, we require that no t players get information about b from their pieces; and yet, b is recoverable, and is known to be recoverable, given the cooperation of the n -t good players--even if the t bad players try to obstruct b's recovery, or try to alter the recovered value.The value b which a player has effectively "committed to" is independent of the values that honest players may concurrently be committing to.After the sharing stage, a computation stage follows, in which each player, given his own shares of xl, ..., x,~, computes his own share of f(zt,..., z,~).To accomplish this, the function f to be evaluated is represented by a