Paper 2020/784

CRAFT: Composable Randomness Beacons and Output-Independent Abort MPC From Time

Carsten Baum, Bernardo David, Rafael Dowsley, Jesper Buus Nielsen, and Sabine Oechsner


Recently, time-based primitives such as time-lock puzzles (TLP) and verifiable delay functions (VDF) have received a lot of attention due to their power as building blocks for cryptographic protocols. However, even though exciting improvements on their efficiency and security (e.g. achieving non-malleability) have been made, most of the existing constructions do not offer general composability guarantees and thus have limited applicability. Baum et al. (EUROCRYPT 2021) presented in TARDIS the first (im)possibility results on constructing TLPs with Universally Composable (UC) security and an application to secure two-party computation with output-independent abort (OIA-2PC), where an adversary has to decide to abort before learning the output. While these results establish the feasibility of UC-secure TLPs and applications, they are limited to the two-party scenario and suffer from complexity overheads. In this paper, we introduce the first UC constructions of VDFs and of the related notion of publicly verifiable TLPs. We use these primitives to prove folklore results on randomness beacons based on VDFs widely used in industry, as well as introducing a more efficient construction based on publicly verifiable TLPs. We also present the first UC-secure construction of multiparty computation with punishable output-independent aborts (POIA-MPC) (i.e. MPC with OIA and financial punishment for cheating), which both establishes the feasibility of OIA-MPC and improves on the efficiency of the state-of-the-art in both (non-OIA) UC-secure MPC with punishable aborts and OIA-2PC.

Note: Added results on VDFs, other results are unchanged.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Universal ComposabilityTime Lock PuzzleVerifiable Delay FunctionOutput Independent AbortMultiparty ComputationRandomness BeaconsPublic Verifiability
Contact author(s)
cbaum @ cs au dk
bernardo @ bmdavid com
rafael @ dowsley net
jbn @ cs au dk
oechsner @ cs au dk
2021-03-04: revised
2020-06-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Carsten Baum and Bernardo David and Rafael Dowsley and Jesper Buus Nielsen and Sabine Oechsner},
      title = {CRAFT: Composable Randomness Beacons and Output-Independent Abort MPC From Time},
      howpublished = {Cryptology ePrint Archive, Paper 2020/784},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.