Adaptively secure broadcast, revisited

TitleAdaptively secure broadcast, revisited
Publication TypeJournal Articles
Year of Publication2011
AuthorsGaray JA, Katz J, Kumaresan R, Zhou HS
JournalProceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing
Date Published2011///

We consider the classical problem of synchronous broadcast with dishonest majority, whena 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.