Paper 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.

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