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

International Conference on Distributed Computing

Brief Announcement: Towards Byzantine Broadcast in Generalized Communication and Adversarial Models

Chen-Da Liu-Zhang, Varun Maram, Ueli M. Maurer

Published Oct 1, 2019• 0 citations
Publisher

Abstract

Byzantine broadcast is a primitive which allows a specific party to distribute a message consistently among n parties, even if up to t parties exhibit malicious behaviour. In the classical model with a complete network of bilateral authenticated channels, the seminal result of Pease et al. [Pease et al., 1980] shows that broadcast is achievable if and only if t < n/3. There are two generalizations suggested for the broadcast problem - w.r.t. the adversarial model and the communication model. Fitzi and Maurer [Fitzi and Maurer, 1998] consider a (non-threshold) general adversary that is characterized by the subsets of parties that could be corrupted, and show that broadcast can be realized from bilateral channels if and only if the union of no three possible corrupted sets equals the entire set of n parties. On the other hand, Considine et al. [Considine et al., 2005] extend the standard model of bilateral channels with the existence of b-minicast channels that allow to locally broadcast among any subset of b parties; the authors show that in this enhanced model of communication, secure broadcast tolerating up to t corrupted parties is possible if and only if t < (b-1)/(b+1) n. These generalizations are unified in the work by Raykov [Raykov P., 2015], where a tight condition on the possible corrupted sets such that broadcast is achievable from a complete set of b-minicasts is shown. This paper investigates the achievability of broadcast in general networks, i.e., networks where only some subsets of minicast channels may be available, thereby addressing open problems posed in [Jaffe et al., 2012; Raykov P., 2015]. Our contributions include: 1) proposing a hierarchy over all possible general adversaries for a clean analysis of the broadcast problem in general networks, 2) showing the infeasibility of a prominent technique - used to achieve broadcast in general 3-minicast networks [Ravikant et al., 2004] - with regard to higher b-minicast networks, and 3) providing some necessary conditions on general networks for broadcast to be possible while tolerating general adversaries.

DOI
10.3929/ethz-b-000377527

Related papers

On Broadcast in Generalized Network and Adversarial Models

Chen-Da Liu-Zhang, Varun Maram, Ueli M. Maurer

Broadcast is a primitive which allows a specific party to distribute a message consistently among n parties, even if up to t parties exhibit malicious behaviour. In the classical model with a complete network of bilateral authenticated channels, the seminal result of Pease et al. [Pease et al., 1980] shows that broadcast is achievable if and only if t < n/3. There are two generalizations suggested for the broadcast problem - with respect to the adversarial model and the communication model. Fitzi and Maurer [Fitzi and Maurer, 1998] consider a (non-threshold) general adversary that is characterized by the subsets of parties that could be corrupted, and show that broadcast can be realized from bilateral channels if and only if the union of no three possible corrupted sets equals the entire set of n parties. On the other hand, Considine et al. [Considine et al., 2005] extend the standard model of bilateral channels with the existence of b-minicast channels that allow to locally broadcast among any subset of b parties; the authors show that in this enhanced model of communication, secure broadcast tolerating up to t corrupted parties is possible if and only if t < (b-1)/(b+1)n. These generalizations are unified in the work by Raykov [Raykov P., 2015], where a tight condition on the possible corrupted sets is presented such that broadcast is achievable from a complete set of b-minicasts. This paper investigates the achievability of broadcast in general networks, i.e., networks where only some subsets of minicast channels may be available, thereby addressing open problems posed in [Jaffe et al., 2012; Raykov P., 2015]. To that end, we propose a hierarchy over all possible general adversaries, and identify for each class of general adversaries 1) a set of minicast channels that are necessary to achieve broadcast and 2) a set of minicast channels that are sufficient to achieve broadcast. In particular, this allows us to derive bounds on the amount of b-minicasts that are necessary and that suffice towards constructing broadcast in general b-minicast networks.

Leibniz international proceedings in informatics•Dec 1, 2020•0 citations

Broadcast Achievability in Incomplete Minicast Models

Maram, Sai Varun Reddy

Broadcast is a primitive which allows a specific party to distribute a message consistently among n parties, even if up to t parties exhibit malicious behaviour.In the classical model with a complete network of bilateral authenticated channels, the seminal result of [15] shows that broadcast is achievable if and only if t < n/3.There are two generalizations suggested for the broadcast problem -with respect to the adversarial model and the communication model.Fitzi and Maurer [10] consider a (non-threshold) general adversary that is characterized by the subsets of parties that could be corrupted, and show that broadcast can be realized from bilateral channels if and only if the union of no three possible corrupted sets equals the entire set of n parties.On the other hand, [4] extends the standard model of bilateral channels with the existence of b-minicast channels that allow to locally broadcast among any subset of b parties; the authors show that in this enhanced model of communication, secure broadcast tolerating up to t corrupted parties is possible if and only if t < b-1 b+1 n.These generalizations are unified in [14] where Raykov studies the problem of achieving broadcast from a complete set of b-minicast channels that is secure under general adversaries, and gives a tight characterization of the possible corrupted subsets of parties against which broadcast is (im)possible.This thesis initiates the study of achievability of broadcast in scenarios where only some subset of b-minicast channels are available, thereby addressing an open problem posed by [14].Even though the broadcast problem has been studied for the concrete case of incomplete 3minicast networks in [16] and [12], not much work has been done with respect to general b-minicast models.Our major contribution is the identification of types of minicast channels that are essential for broadcast secure against general adversaries.In particular, this allows us to derive a bound on the amount of b-minicasts required for some party to broadcast.Inspired by the result of [14], the thesis also proves some properties for an interesting class of adversaries, named chain adversaries, that are relevant to the problem at hand, and proposes a hierarchy over all possible general adversaries targeting a set of n parties.We conclude the discussion by showing why a prominent method to construct broadcast protocols -used by [16] for 3-minicast models -is not feasible when it comes to incomplete b-minicast models.

•Mar 1, 2019•0 citations

From Partial to Global Asynchronous Broadcast

Diana Ghinea

Broadcast is a fundamental primitive in distributed computing.It allows a sender to consistently distribute a message among n recipients.The seminal result of Pease et al. [JACM'80] shows that in a complete network of synchronous bilateral channels, achieving broadcast is possible if and only if the number of corruptions is bounded by t < n/3.To overcome this bound, Fitzi and Maurer [STOC'00], Considine et al. [JC'05], and Raykov [ICALP'15] strengthen the communication network by assuming partial broadcast channels, which guarantee consistency among a subset of recipients.We extend this line of research to the asynchronous setting.We consider asynchronous broadcast protocols assuming a communication network where each party can broadcast to any subset of b -1 recipients.A natural question is to investigate the trade-off between the size b and the corruption threshold t.We answer this question by showing feasibility and impossibility results:• An asynchronous broadcast protocol Π n,3 BC for b = 3, that is secure up to t < n/2 corruptions.• An asynchronous broadcast protocol Π n,n BC for b = n, that is secure up to t < n -1 corruptions.• An asynchronous broadcast protocol Π n,(b,n) BC I would like to express my deepest gratitude to Dr. Martin Hirt and Chen-Da Liu Zhang for offering me the opportunity to work on such an interesting problem, and for closely supervising every step towards the completion of my thesis.Each result of this work is based on the guidance and motivation they gave me during our countless inspiring discussions filled with enthusiasm.I am extremely grateful to my five-times host at Google, Dr. Holger Brandsmeier, for inspiring and encouraging me to study at ETH, while proposing me unique challenges that helped me push my limits and widen my ambitions.Besides, I thank the whole team for creating an enjoyable work environment, especially last summer, when I mixed work with the exams session.I want to thank my mother, Carmen Mincȃ, and my grandmother, Ana Mincȃ, for raising me to follow my dreams

•Jan 1, 2020•0 citations

Hierarchy of three-party consistency specifications

Julian Loss, Ueli M. Maurer, Daniel Tschudi

In the theory of distributed systems and in cryptography one considers a set of n parties which wish to securely perform a certain computation, even if some of the parties are dishonest. Broadcast, one of the most fundamental and widely used such primitives, allows one (possibly cheating) party to distribute a value m consistently to the other parties, in a context where only bilateral (authenticated) channels between parties are available. A well-known result [LSP82] states that this is possible if and only if strictly less than a third of the parties are dishonest. Broadcast guarantees a very strong form of consistency. This paper investigates generalizations of the broadcast setting in two directions: weaker forms of consistency guarantees are considered, and other resources than merely bilateral channels are assumed to be available. The ultimate goal of this line of work is to arrive at a complete classification of consistency specifications [Mau04]. As a concrete result in this direction we present a complete classification of three-party specifications with a binary input and binary outputs.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•0 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, 1997•165 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
Byzantine broadcast is a primitive which allows a specific party to distribute a message consistently among n parties, even if up to t parties exhibit malicious behaviour. In the classical model with a complete network of bilateral authenticated channels, the seminal result of Pease et al. [Pease et al., 1980] shows that broadcast is achievable if and only if t < n/3. There are two generalizations suggested for the broadcast problem - w.r.t. the adversarial model and the communication model. Fitzi and Maurer [Fitzi and Maurer, 1998] consider a (non-threshold) general adversary that is characterized by the subsets of parties that could be corrupted, and show that broadcast can be realized from bilateral channels if and only if the union of no three possible corrupted sets equals the entire set of n parties. On the other hand, Considine et al. [Considine et al., 2005] extend the standard model of bilateral channels with the existence of b-minicast channels that allow to locally broadcast among any subset of b parties; the authors show that in this enhanced model of communication, secure broadcast tolerating up to t corrupted parties is possible if and only if t < (b-1)/(b+1) n. These generalizations are unified in the work by Raykov [Raykov P., 2015], where a tight condition on the possible corrupted sets such that broadcast is achievable from a complete set of b-minicasts is shown. This paper investigates the achievability of broadcast in general networks, i.e., networks where only some subsets of minicast channels may be available, thereby addressing open problems posed in [Jaffe et al., 2012; Raykov P., 2015]. Our contributions include: 1) proposing a hierarchy over all possible general adversaries for a clean analysis of the broadcast problem in general networks, 2) showing the infeasibility of a prominent technique - used to achieve broadcast in general 3-minicast networks [Ravikant et al., 2004] - with regard to higher b-minicast networks, and 3) providing some necessary conditions on general networks for broadcast to be possible while tolerating general adversaries.
Broadcast is a primitive which allows a specific party to distribute a message consistently among n parties, even if up to t parties exhibit malicious behaviour. In the classical model with a complete network of bilateral authenticated channels, the seminal result of Pease et al. [Pease et al., 1980] shows that broadcast is achievable if and only if t < n/3. There are two generalizations suggested for the broadcast problem - with respect to the adversarial model and the communication model. Fitzi and Maurer [Fitzi and Maurer, 1998] consider a (non-threshold) general adversary that is characterized by the subsets of parties that could be corrupted, and show that broadcast can be realized from bilateral channels if and only if the union of no three possible corrupted sets equals the entire set of n parties. On the other hand, Considine et al. [Considine et al., 2005] extend the standard model of bilateral channels with the existence of b-minicast channels that allow to locally broadcast among any subset of b parties; the authors show that in this enhanced model of communication, secure broadcast tolerating up to t corrupted parties is possible if and only if t < (b-1)/(b+1)n. These generalizations are unified in the work by Raykov [Raykov P., 2015], where a tight condition on the possible corrupted sets is presented such that broadcast is achievable from a complete set of b-minicasts. This paper investigates the achievability of broadcast in general networks, i.e., networks where only some subsets of minicast channels may be available, thereby addressing open problems posed in [Jaffe et al., 2012; Raykov P., 2015]. To that end, we propose a hierarchy over all possible general adversaries, and identify for each class of general adversaries 1) a set of minicast channels that are necessary to achieve broadcast and 2) a set of minicast channels that are sufficient to achieve broadcast. In particular, this allows us to derive bounds on the amount of b-minicasts that are necessary and that suffice towards constructing broadcast in general b-minicast networks.
Broadcast is a primitive which allows a specific party to distribute a message consistently among n parties, even if up to t parties exhibit malicious behaviour.In the classical model with a complete network of bilateral authenticated channels, the seminal result of [15] shows that broadcast is achievable if and only if t < n/3.There are two generalizations suggested for the broadcast problem -with respect to the adversarial model and the communication model.Fitzi and Maurer [10] consider a (non-threshold) general adversary that is characterized by the subsets of parties that could be corrupted, and show that broadcast can be realized from bilateral channels if and only if the union of no three possible corrupted sets equals the entire set of n parties.On the other hand, [4] extends the standard model of bilateral channels with the existence of b-minicast channels that allow to locally broadcast among any subset of b parties; the authors show that in this enhanced model of communication, secure broadcast tolerating up to t corrupted parties is possible if and only if t < b-1 b+1 n.These generalizations are unified in [14] where Raykov studies the problem of achieving broadcast from a complete set of b-minicast channels that is secure under general adversaries, and gives a tight characterization of the possible corrupted subsets of parties against which broadcast is (im)possible.This thesis initiates the study of achievability of broadcast in scenarios where only some subset of b-minicast channels are available, thereby addressing an open problem posed by [14].Even though the broadcast problem has been studied for the concrete case of incomplete 3minicast networks in [16] and [12], not much work has been done with respect to general b-minicast models.Our major contribution is the identification of types of minicast channels that are essential for broadcast secure against general adversaries.In particular, this allows us to derive a bound on the amount of b-minicasts required for some party to broadcast.Inspired by the result of [14], the thesis also proves some properties for an interesting class of adversaries, named chain adversaries, that are relevant to the problem at hand, and proposes a hierarchy over all possible general adversaries targeting a set of n parties.We conclude the discussion by showing why a prominent method to construct broadcast protocols -used by [16] for 3-minicast models -is not feasible when it comes to incomplete b-minicast models.
Broadcast is a fundamental primitive in distributed computing.It allows a sender to consistently distribute a message among n recipients.The seminal result of Pease et al. [JACM'80] shows that in a complete network of synchronous bilateral channels, achieving broadcast is possible if and only if the number of corruptions is bounded by t < n/3.To overcome this bound, Fitzi and Maurer [STOC'00], Considine et al. [JC'05], and Raykov [ICALP'15] strengthen the communication network by assuming partial broadcast channels, which guarantee consistency among a subset of recipients.We extend this line of research to the asynchronous setting.We consider asynchronous broadcast protocols assuming a communication network where each party can broadcast to any subset of b -1 recipients.A natural question is to investigate the trade-off between the size b and the corruption threshold t.We answer this question by showing feasibility and impossibility results:• An asynchronous broadcast protocol Π n,3 BC for b = 3, that is secure up to t < n/2 corruptions.• An asynchronous broadcast protocol Π n,n BC for b = n, that is secure up to t < n -1 corruptions.• An asynchronous broadcast protocol Π n,(b,n) BC I would like to express my deepest gratitude to Dr. Martin Hirt and Chen-Da Liu Zhang for offering me the opportunity to work on such an interesting problem, and for closely supervising every step towards the completion of my thesis.Each result of this work is based on the guidance and motivation they gave me during our countless inspiring discussions filled with enthusiasm.I am extremely grateful to my five-times host at Google, Dr. Holger Brandsmeier, for inspiring and encouraging me to study at ETH, while proposing me unique challenges that helped me push my limits and widen my ambitions.Besides, I thank the whole team for creating an enjoyable work environment, especially last summer, when I mixed work with the exams session.I want to thank my mother, Carmen Mincȃ, and my grandmother, Ana Mincȃ, for raising me to follow my dreams
In the theory of distributed systems and in cryptography one considers a set of n parties which wish to securely perform a certain computation, even if some of the parties are dishonest. Broadcast, one of the most fundamental and widely used such primitives, allows one (possibly cheating) party to distribute a value m consistently to the other parties, in a context where only bilateral (authenticated) channels between parties are available. A well-known result [LSP82] states that this is possible if and only if strictly less than a third of the parties are dishonest. Broadcast guarantees a very strong form of consistency. This paper investigates generalizations of the broadcast setting in two directions: weaker forms of consistency guarantees are considered, and other resources than merely bilateral channels are assumed to be available. The ultimate goal of this line of work is to arrive at a complete classification of consistency specifications [Mau04]. As a concrete result in this direction we present a complete classification of three-party specifications with a binary input and binary outputs.
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.
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.