Paper 2021/775

Completeness Theorems for Adaptively Secure Broadcast

Ran Cohen, Interdisciplinary Center Herzliya
Juan Garay, Texas A&M University
Vassilis Zikas, Purdue University West Lafayette
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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Broadcast adaptive security cryptographic protocols time-lock puzzle
Contact author(s)
cohenran @ idc ac il
garay @ cse tamu edu
vzikas @ cs purdue edu
History
2022-05-31: last of 2 revisions
2021-06-09: received
See all versions
Short URL
https://ia.cr/2021/775
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/775,
      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{https://eprint.iacr.org/2021/775}},
      url = {https://eprint.iacr.org/2021/775}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.