List Oblivious Transfer and Applications to Round-Optimal Black-Box Multiparty Coin Tossing

Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Hendrik Waldner

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

In this work we study the problem of minimizing the round complexity for securely evaluating multiparty functionalities while making black-box use of polynomial time assumptions. In Eurocrypt 2016, Garg et al. showed that assuming all parties have access to a broadcast channel, then at least four rounds of communication are required to securely realize non-trivial functionalities in the plain model.

A sequence of works follow-up the result of Garg et al. matching this lower bound under a variety of assumptions. Unfortunately, none of these works make black-box use of the underlying cryptographic primitives. In Crypto 2021, Ishai, Khurana, Sahai, and Srinivasan came closer to matching the four-round lower bound, obtaining a five-round protocol that makes black-box use of oblivious transfer and PKE with pseudorandom public keys.

In this work, we show how to realize any input-less functionality (e.g., coin-tossing, generation of key-pairs, and so on) in four rounds while making black-box use of two-round oblivious transfer. As an additional result, we construct the first four-round MPC protocol for generic functionalities that makes black-box use of the underlying primitives, achieving security against non-aborting adversaries.

Our protocols are based on a new primitive called list two-party computation. This primitive offers relaxed security compared to the standard notion of secure two-party computation. Despite this relaxation, we argue that this tool suffices for our applications. List two-party computation is of independent interest, as we argue it can also be used for the generation of setups, like oblivious transfer correlated randomness, in three rounds. Prior to our work, generating such a setup required at least four rounds of interactions or a trusted third party.
Original languageEnglish
Title of host publicationCRYPTO 2023
Subtitle of host publication43rd International Cryptology Conference
Publication statusPublished - 9 Aug 2023
Event43rd International Cryptology Conference - Santa Barbara, United States
Duration: 19 Aug 202324 Aug 2023
Conference number: 43

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference43rd International Cryptology Conference
Abbreviated titleCRYPTO 2023
Country/TerritoryUnited States
CitySanta Barbara
Internet address


Dive into the research topics of 'List Oblivious Transfer and Applications to Round-Optimal Black-Box Multiparty Coin Tossing'. Together they form a unique fingerprint.

Cite this