Cryptology ePrint Archive: Report 2020/784

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

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

Abstract: 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.

Category / Keywords: cryptographic protocols / Universal Composability, Time Lock Puzzle, Verifiable Delay Function, Output Independent Abort, Multiparty Computation, Randomness Beacons, Public Verifiability

Date: received 24 Jun 2020, last revised 4 Mar 2021

Contact author: cbaum at cs au dk, bernardo at bmdavid com, rafael at dowsley net, jbn at cs au dk, oechsner at cs au dk

Available format(s): PDF | BibTeX Citation

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

Version: 20210304:174844 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]