In this work, we show that, contrary to previous perception, the above limitation is not an artifact of simulation-based security, but that it also applies to the property-based broadcast definition adapted for adaptive adversaries. We then turn to the resource-restricting cryptography (RRC) paradigm, which was proven useful in circumventing strong impossibility results, and ask whether it also allows us to circumvent 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? It turns out that they do not, which serves as yet another motivation for simulation-based security, especially when dealing with adaptive adversaries. Nonetheless, we show that a positive result can be achieved if we turn to what is essentially a non-committing version of TLPs, which uses access to a programmable random oracle.
Category / Keywords: cryptographic protocols / Broadcast, adaptive security, cryptographic protocols Date: received 8 Jun 2021 Contact author: rancohen at ccs neu edu, garay at cse tamu edu, vzikas at cs purdue edu Available format(s): PDF | BibTeX Citation Version: 20210609:063121 (All versions of this report) Short URL: ia.cr/2021/775