Paper 2021/775

Completeness Theorems for Adaptively Secure Broadcast

Ran Cohen, Reichman University
Juan Garay, Texas A&M University
Vassilis Zikas, Purdue University West Lafayette

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 (a task that is achievable against a static adversary). The contributions of this paper are two-fold. First, we show 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, in neither setting, property-based or simulation-based. 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 question 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. Importantly, and as a contribution of independent interest, we also present the first (limited) composition theorem in the resource-restricted setting, which is needed for the complexity-based, non-idealized treatment of TLPs in the context of other protocols.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2023
Broadcastadaptive securitycryptographic protocolstime-lock puzzle
Contact author(s)
cohenran @ runi ac il
garay @ cse tamu edu
vzikas @ cs purdue edu
2023-06-06: last of 4 revisions
2021-06-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ran Cohen and Juan Garay and Vassilis Zikas},
      title = {Completeness Theorems for Adaptively Secure Broadcast},
      howpublished = {Cryptology ePrint Archive, Paper 2021/775},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.