Welcome to the resource topic for 2021/775
Title:
Completeness Theorems for Adaptively Secure Broadcast
Authors: Ran Cohen, Juan Garay, and Vassilis Zikas
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., that 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 devise a complete characterization of adaptively secure broadcast both in the property-based and in the simulation-based setting, and assuming a wide class of common setups. 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 of 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 was 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.
ePrint: https://eprint.iacr.org/2021/775
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .