ACM Symposium on Principles of Distributed Computing (PODC)

Detectable byzantine agreement secure against faulty majorities

Matthias Fitzi, Daniel Gottesman, Martin Hirt, Thomas Holenstein, Adam Smith

Published Jul 21, 2002• 73 citations

Abstract

It is well-known that n players, connected only by pairwise secure channels, can achieve Byzantine agreement only if the number t of cheaters satisfies t < n/3, even with respect to computational security. However, for many applications it is sufficient to achieve detectable broadcast. With this primitive, broadcast is only guaranteed when all players are non-faulty ("honest"), but all non-faulty players always reach agreement on whether broadcast was achieved or not. We show that detectable broadcast can be achieved regardless of the number of faulty players (i.e., for all t < n). We give a protocol which is unconditionally secure, as well as two more efficient protocols which are secure with respect to computational assumptions, and the existence of quantum channels, respectively.These protocols allow for secure multi-party computation tolerating any t < n, assuming only pairwise authenticated channels. Moreover, they allow for the setup of public-key infrastructures that are consistent among all participants --- using neither a trusted party nor broadcast channels.Finally, we show that it is not even necessary for players to begin the protocol at the same time step. We give a "detectable Firing Squad" protocol which can be initiated by a single user at any time and such that either all honest players end up with synchronized clocks, or all honest players abort.

DOI: 10.1145/571825.571841

Related papers

Unconditional Byzantine Agreement and Multi-Party Computation Secure Against Dishonest Minorities from Scratch

Matthias Fitzi, Nicolas Gisin, Ueli M. Maurer +1 more

Abstract. It is well-known that n players, connected only by pairwise secure channels, can achieve unconditional broadcast if and only if the number t of cheaters satisfies t < n/3. In this paper, we show that this bound can be improved — at the sole price that the adversary can prevent successful completion of the protocol, but in which case all players will have agreement about this fact. Moreover, a first time slot during which the adversary forgets to cheat can be reliably detected and exploited in order to allow for future broadcasts with t < n/2. This even allows for secure multi-party computation with t < n/2 after the first detection of such a time slot.

Jan 1, 20027 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, 20121 citation

Verifiable secret sharing and multiparty protocols with honest majority

Tal Rabin, Michael Ben-Or

Under the assumption that each participant can broadcast a message to all other participants and that each pair of participants can communicate secretly, we present a verifiable secret sharing protocol, and show that any multiparty protocol, or game with incomplete information, can be achieved if a majority of the players are honest. The secrecy achieved is unconditional and does not rely on any assumption about computational intractability. Applications of these results to Byzantine Agreement are also presented.

ACM Symposium on Theory of Computing (STOC)Jan 1, 1989940 citations

On the Complexity of Broadcast Setup

Martin Hirt, Pavel Raykov

Abstract. Byzantine broadcast is a distributed primitive that allows a specific party (called “sender”) to consistently distribute a value v among n parties in the presence of potential misbehavior of up to t of the parties. Broadcast requires that correct parties always agree on the same value and if the sender is correct, then the agreed value is v. Broadcast without a setup (i.e., from scratch) is achievable from point-to-point channels if and only if t < n/3. In case t ≥ n/3 a trusted setup is required. The setup may be assumed to be given initially or generated by the parties in a setup phase. It is known that generating setup for protocols with cryptographic security is relatively simple and only consists of setting up a public-key infrastructure. However, generating setup for information-theoretically secure protocols is much more involved. In this paper we study the complexity of setup generation for information-theoretic protocols using point-to-point channels and temporarily available broadcast channels. We optimize the number of rounds in which the temporary broadcast channels are used while minimizing the number of bits broadcast with them. We give the first information-theoretically secure broadcast protocol tolerating t < n/2 that uses the temporary broadcast channels during only 1 round in the setup phase. Furthermore, only O(n 3) bits need to be broadcast with the temporary broadcast channels during that round, independently of the security parameter employed. The broadcast protocol presented in this paper allows to construct the first informationtheoretically secure MPC protocol which uses a broadcast channel during only one round. Additionally, the presented broadcast protocol supports refreshing, which allows to broadcast an a priori unknown number of times given a fixed-size setup.

Jan 1, 20130 citations

Complete characterization of adversaries tolerable in secure multi-party computation (extended abstract)

Martin Hirt, Ueli M. Maurer

The classical results in unconditional multi-party computation among a set of n players state that less than n/2 passive or Iess than n/3 active adversaries can be tolerated; assuming a broadcast channel the threshold for active adversaries is ta/2.Strictly generalizing these results we specify the set of potential y misbehaving players as an arbitrary set of subsets of the player set.We prove the necessary and sufficient conditions for the existence of secure multi-party protocols in terms of the potentially misbehaving player sets.For every function there exists a protocol secure against a set of potential passive collusions if and only if no two of these collusions add up to the full player set.The same condition applies for active adversaries when assuming a broadcast chzmnel.Without broadcast channels, for every function there exists a protocol secure against a set of potential active adverse player sets if and only if no three of these sets add up to the full player set.The complexities of the protocols not using a broadcast channel are polynomial, that of the protocol with broadcast is only slightly higher.

ACM Symposium on Principles of Distributed Computing (PODC)Jan 1, 1997165 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, 20123 citations