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

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

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

Recently, time-based primitives such as time-lock puzzles (TLPs) and verifiable delay functions (VDFs) 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 (PV-TLPs). We use our new UC VDF to prove a folklore result on VDF-based randomness beacons used in industry and build an improved randomness beacon from our new UC PV-TLPs. We moreover construct the first multiparty computation protocol with punishable output-independent aborts (POIA-MPC), i.e. MPC with OIA and financial punishment for cheating. Our novel POIA-MPC both establishes the feasibility of (non-punishable) OIA-MPC and significantly improves on the efficiency of state-of-the-art OIA-2PC and (non-OIA) MPC with punishable aborts.
Original languageEnglish
Title of host publicationPublic-Key Cryptography – PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
EditorsA. Boldyreva, V. Kolesnikov
PublisherSpringer Science and Business Media Deutschland GmbH
Pages439-470
ISBN (Print)9783031313677
DOIs
Publication statusPublished - 2023
Externally publishedYes
Event26th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2023 - Atlanta, United States
Duration: 7 May 202310 May 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2023
Country/TerritoryUnited States
CityAtlanta
Period7/05/2310/05/23

Funding

Abstract. Recently, time-based primitives such as time-lock puzzles (TLPs) and verifiable delay functions (VDFs) 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 C. Baum–Funded by the European Research Council (ERC) under the European Unions’ Horizon 2020 program under grant agreement No 669255 (MPCPRO). B. David–Supported by the Concordium Foundation and the Independent Research Fund Denmark grants number 9040-00399B (TrA2C), 9131-00075B (PUMA) and 0165-00079B (P2DP). R. Dowsley–Partially done while Rafael Dowsley was with Bar-Ilan University and supported by the BIU Center for Research in Applied Cryptography and Cyber Security in conjunction with the Israel National Cyber Bureau in the Prime Minister’s Office. R. Kishore–Supported by the Independent Research Fund Denmark grant number 9131-00075B (PUMA). J.B. Nielsen–Partially funded by The Concordium Foundation; The Danish Independent Research Council under Grant-ID DFF-8021-00366B (BETHE); The Carlsberg Foundation under the Semper Ardens Research Project CF18-112 (BCM). S. Oechsner–Supported by Input Output (iohk.io) through their funding of the Edinburgh Blockchain Technology Lab. Partially done while Sabine Oechsner was with Aarhus University and supported by the Danish Independent Research Council under Grant-ID DFF-8021-00366B (BETHE) and Concordium Foundation.

FundersFunder number
Concordium Foundation
European Unions’ Horizon 2020 program669255
Aarhus Universitet
European Research Council
CarlsbergfondetCF18-112
Danmarks Frie ForskningsfondDFF-8021-00366B
Danmarks Frie ForskningsfondTrA2C, 0165-00079B, 9040-00399B, 9131-00075B

    Fingerprint

    Dive into the research topics of 'CRAFT: Composable Randomness Beacons and Output-Independent Abort MPC From Time'. Together they form a unique fingerprint.

    Cite this