Paper 2022/237

Public Randomness Extraction with Ephemeral Roles and Worst-Case Corruptions

Jesper Buus Nielsen, Aarhus University
João Ribeiro, Carnegie Mellon University
Maciej Obremski, National University of Singapore

We distill a simple information-theoretic model for randomness extraction motivated by the task of generating publicly verifiable randomness in blockchain settings and which is closely related to You-Only-Speak-Once (YOSO) protocols (CRYPTO 2021). With the goal of avoiding denial-of-service attacks, parties speak only once and in sequence by broadcasting a public value and forwarding secret values to future parties. Additionally, an unbounded adversary can corrupt any chosen subset of at most $t$ parties. In contrast, existing YOSO protocols only handle random corruptions. As a notable example, considering worst-case corruptions allows us to reduce trust in the role assignment mechanism, which is assumed to be perfectly random in YOSO. We study the maximum corruption threshold $t$ which allows for unconditional randomness extraction in our model: - With respect to feasibility, we give protocols for $t$ corruptions and $n=6t+1$ or $n=5t$ parties depending on whether the adversary learns secret values forwarded to corrupted parties immediately once they are sent or only once the corrupted party is executed, respectively. Both settings are motivated by practical implementations of secret value forwarding. To design such protocols, we go beyond the committee-based approach that is sufficient for random corruptions in YOSO but turns out to be sub-optimal for chosen corruptions. - To complement our protocols, we show that low-error randomness extraction is impossible with corruption threshold $t$ and $n\leq 4t$ in the stronger adversarial network model.

Note: Randomized author ordering. A previous version of this work claimed an impossibility result for $n \leq 4t$ parties in what we call the "execution-leaks" model. However, the presented proof only works in the stronger "sending-leaks" model, and it is not clear whether this claim for the execution-leaks model is true. The paper has been updated accordingly.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2022
Randomness extractionYOSOWorst-case corruptions
Contact author(s)
jbn @ cs au dk
jlourenc @ cs cmu edu
obremski math @ gmail com
2024-05-29: last of 3 revisions
2022-02-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jesper Buus Nielsen and João Ribeiro and Maciej Obremski},
      title = {Public Randomness Extraction with Ephemeral Roles and Worst-Case Corruptions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/237},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.