Adaptively Secure Broadcast, Revisited

Juan Garay
AT&T Labs - Research


We consider the classical problem of synchronous broadcast with dishonest majority, in a setting where 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 completely insecure against an adaptive adversary who can choose which parties to corrupt as the protocol progresses; moreover, they prove that adaptively secure broadcast is impossible in this setting. The communication model used by Hirt and Zikas, however, is non-standard; we argue that in most real-world networks their model is unrealistically pessimistic. We revisit the question of adaptively secure broadcast in the standard synchronous model (with rushing), and show that broadcast is possible in this setting for an arbitrary number of corruptions. (Our positive result holds under a strong, simulation-based definition in the framework of universal composability.) We also study the impact of adaptive-adversary attacks on secure multi-party computation protocols, where broadcast is commonly used as a subcomponent. This is joint work with Jonathan Katz, Ranjit Kumaresan and Hong-Sheng Zhou (University of Maryland).