Adaptively secure broadcast

Martin Hirt*, Vassilis Zikas

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

A broadcast protocol allows a sender to distribute a message through a point-to-point network to a set of parties, such that (i) all parties receive the same message, even if the sender is corrupted, and (ii) this is the sender's message, if he is honest. Broadcast protocols satisfying these properties are known to exist if and only if t < n/3, where n denotes the total number of parties, and t denotes the maximal number of corruptions. When a setup allowing signatures is available to the parties, then such protocols exist even for t < n. Since its invention in [LSP82], broadcast has been used as a primitive in numerous multi-party protocols making it one of the fundamental primitives in the distributed-protocols literature. The security of these protocols is analyzed in a model where a broadcast primitive which behaves in an ideal way is assumed. Clearly, a definition of broadcast should allow for secure composition, namely, it should be secure to replace an assumed broadcast primitive by a protocol satisfying this definition. Following recent cryptographic reasoning, to allow secure composition the ideal behavior of broadcast can be described as an ideal functionality, and a simulation-based definition can be used. In this work, we show that the property-based definition of broadcast does not imply the simulation-based definition for the natural broadcast functionality. In fact, most broadcast protocols in the literature do not securely realize this functionality, which raises a composability issue for these broadcast protocols. In particular, we do not know of any broadcast protocol which could be securely invoked in a multi-party computation protocol in the secure-channels model. The problem is that existing protocols for broadcast do not preserve the secrecy of the message while being broadcasted, and in particular allow the adversary to corrupt the sender (and change the message), depending on the message being broadcasted. For example, when every party should broadcast a random bit, the adversary could corrupt those parties who intend to broadcast 0, and make them broadcast 1. More concretely, we show that simulatable broadcast in a model with secure channels is possible if and only if t < n/3, respectively t ≤ n/2 when a signature setup is available. The positive results are proven by constructing secure broadcast protocols.

Original languageEnglish
Title of host publicationAdvances in Cryptology - Eurocrypt 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Place of PublicationBerlin, Heidelberg
Number of pages20
ISBN (Electronic)978-3-642-13190-5
ISBN (Print)978-3-642-13189-9
Publication statusPublished - 21 Jul 2010
Event29th Annual International Conference on the Theory and Applications of Cryptographic Techniques - French Riviera, France
Duration: 30 May 20103 Jun 2010

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Berlin, Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference29th Annual International Conference on the Theory and Applications of Cryptographic Techniques
Abbreviated titleEUROCRYPT 2020
CityFrench Riviera


Dive into the research topics of 'Adaptively secure broadcast'. Together they form a unique fingerprint.

Cite this