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

ACM Symposium on Principles of Distributed Computing (PODC)

Adaptively secure broadcast, revisited

Juan A. Garay, Jonathan I. Katz, Ranjit Kumaresan, Hong-Sheng Zhou

Published Jun 6, 2011• 54 citations
Publisher

Abstract

We consider the classical problem of synchronous broadcast with dishonest majority, when a public-key infrastructure and digital signatures are available. In a surprising result, Hirt and Zikas (Eurocrypt 2010) recently observed that all existing protocols for this task are insecure against an adaptive adversary who can choose which parties to corrupt as the protocol progresses. Moreover, they prove an impossibility result for adaptively secure broadcast in their setting. We argue that the communication model adopted by Hirt and Zikas is unrealistically pes-simistic. We revisit the problem of adaptively secure broadcast in a more natural synchronous model (with rushing), and show that broadcast is possible in this setting for an arbitrary num-ber of corruptions. Our positive result holds under a strong, simulation-based definition in the universal-composability framework. We also study the impact of adaptive attacks on protocols for secure multi-party computation where broadcast is used as a sub-routine. 1

DOI
10.1145/1993806.1993832

Related papers

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

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

Communication lower bounds for cryptographic broadcast protocols

Erica Blum, Elette Boyle, Ran Cohen +1 more

Abstract Broadcast protocols enable a set of n parties to agree on the input of a designated sender, even facing attacks by malicious parties. In the honest-majority setting, randomization and cryptography were harnessed to achieve low-communication broadcast with sub-quadratic total communication and balanced sub-linear cost per party. However, comparatively little is known in the dishonest-majority setting. Here, the most communication-efficient constructions are based on Dolev and Strong (SICOMP ’83), and sub-quadratic broadcast has not been achieved. On the other hand, the only nontrivial $$\omega (n)$$ ω ( n ) communication lower bounds are restricted to deterministic protocols, or against strong adaptive adversaries that can perform “after the fact” removal of messages. We provide new communication lower bounds in this space, which hold against arbitrary cryptography and setup assumptions, as well as a simple sub-quadratic broadcast protocol showing near tightness of our first bound.

arXiv:2309.01466•Distributed Computing•Jan 7, 2025•5 citations

Adaptively secure multi-party computation

Ran Canetti, Uri Feige, Oded Goldreich +1 more

A fundamental problem in designing secure multi-party protocols is how to deal with adaptive adversaries (i.e., adversaries that may choose the corrupted parties during the course of the computation), in a setting where the channels are insecure and secure communication is achieved by cryptographic primitives based on the computational limitations of the adversary.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1996•557 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

On adaptive vs. non-adaptive security of multiparty protocols.

Ran Canetti, Ivan Damgård, Stefan Dziembowski +2 more

Security analysis of multiparty cryptographic protocols distinguishes between two types of adversarial settings: In the non-adaptive setting, the set of corrupted parties is chosen in advance, before the interaction begins. In the adaptive setting, the adversary chooses who to corrupt during the course of the computation. We study the relations between adaptive security (i.e., security in the adaptive setting) and non-adaptive security, according to two definitions and in several models of computation. While affirming some prevailing beliefs, we also obtain some unexpected results. Some highlights of our results are: . According to the definition of Dodis-Micali-Rogaway (which is set in the information-theoretic model), adaptive and non-adaptive security are equivalent. This holds for both honest-but-curious and Byzantine adversaries, and for any number of parties. . According to the definition of Canetti, for honest-but-curious adversaries, adaptive security is equivalent to...

•Jan 1, 2001•8 citations
We consider the classical problem of synchronous broadcast with dishonest majority, when a public-key infrastructure and digital signatures are available. In a surprising result, Hirt and Zikas (Eurocrypt 2010) recently observed that all existing protocols for this task are insecure against an adaptive adversary who can choose which parties to corrupt as the protocol progresses. Moreover, they prove an impossibility result for adaptively secure broadcast in their setting. We argue that the communication model adopted by Hirt and Zikas is unrealistically pes-simistic. We revisit the problem of adaptively secure broadcast in a more natural synchronous model (with rushing), and show that broadcast is possible in this setting for an arbitrary num-ber of corruptions. Our positive result holds under a strong, simulation-based definition in the universal-composability framework. We also study the impact of adaptive attacks on protocols for secure multi-party computation where broadcast is used as a sub-routine. 1
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.
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.
Abstract Broadcast protocols enable a set of n parties to agree on the input of a designated sender, even facing attacks by malicious parties. In the honest-majority setting, randomization and cryptography were harnessed to achieve low-communication broadcast with sub-quadratic total communication and balanced sub-linear cost per party. However, comparatively little is known in the dishonest-majority setting. Here, the most communication-efficient constructions are based on Dolev and Strong (SICOMP ’83), and sub-quadratic broadcast has not been achieved. On the other hand, the only nontrivial ω(n)\omega (n)ω(n) ω ( n ) communication lower bounds are restricted to deterministic protocols, or against strong adaptive adversaries that can perform “after the fact” removal of messages. We provide new communication lower bounds in this space, which hold against arbitrary cryptography and setup assumptions, as well as a simple sub-quadratic broadcast protocol showing near tightness of our first bound.
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
Security analysis of multiparty cryptographic protocols distinguishes between two types of adversarial settings: In the non-adaptive setting, the set of corrupted parties is chosen in advance, before the interaction begins. In the adaptive setting, the adversary chooses who to corrupt during the course of the computation. We study the relations between adaptive security (i.e., security in the adaptive setting) and non-adaptive security, according to two definitions and in several models of computation. While affirming some prevailing beliefs, we also obtain some unexpected results. Some highlights of our results are: . According to the definition of Dodis-Micali-Rogaway (which is set in the information-theoretic model), adaptive and non-adaptive security are equivalent. This holds for both honest-but-curious and Byzantine adversaries, and for any number of parties. . According to the definition of Canetti, for honest-but-curious adversaries, adaptive security is equivalent to...