Paper 2021/775

Completeness Theorems for Adaptively Secure Broadcast

Abstract

The advent of blockchain protocols has reignited the interest in adaptively secure broadcast, as it is by now well understood that broadcasting over a diffusion network allows an adaptive adversary to corrupt the sender depending on the message it attempts to send and change it. Hirt and Zikas [Eurocrypt '10] proved that this is an inherent limitation of broadcast in the simulation-based setting, i.e., this task is impossible against an adaptive adversary corrupting a strict majority of the parties. The contributions of this paper are two-fold. First, we investigate the feasibility of adaptively secure broadcast for a wide class of common setups, both in the property-based and in the simulation-based settings. In the property-based setting, we devise a characterization of the feasibility landscape covering a broad class of protocols---effectively all known broadcast protocol from the literature; for simulation-based security, our characterization is complete---i.e., it covers all possible protocols. Our investigation reveals that, contrary to previous perception, the above limitation of adaptively secure broadcast is not an artifact of simulation-based security, but rather an inherent issue in adaptive security. In particular, we show that: (1) it also applies to the property-based broadcast definition adapted for adaptive adversaries, and (2) unlike other impossibilities in adaptive security, this impossibility cannot be circumvented by adding a programmable random oracle. Second, we turn to the resource-restricted cryptography (RRC) paradigm [Garay et al., Eurocrypt '20], which has proven useful in circumventing impossibility results, and ask whether it also affects the above negative result. We answer this question in the affirmative, by showing that time-lock puzzles (TLPs)---which can be viewed as an instance of RRC---indeed allow for achieving the property-based definition and circumvent the impossibility of adaptively secure broadcast. The natural question is then, do TLPs also allow for simulation-based adaptively secure broadcast against corrupted majorities? We answer this in the negative. Nonetheless, we show that a positive result can be achieved via a non-committing analogue of TLPs in the programmable random-oracle model. As a contribution of independent interest, we also present the first (limited) composition theorem in the resource-restricted setting.