International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Michele Ciampi , The University of Edinburgh, Edinburgh, UK
Rafail Ostrovsky , University of California, Los Angeles, US
Luisa Siniscalchi , Technical University of Denmark, Copenhagen, Denmark
Hendrik Waldner , University of Maryland, College Park, US and Max Planck Institute for Security and Privacy, Bochum, Germany
Download:
DOI: 10.1007/978-3-031-38557-5_15 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: 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 results 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.
BibTeX
@inproceedings{crypto-2023-33201,
  title={List Oblivious Transfer and Applications to Round-Optimal Black-Box Multiparty Coin Tossing},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-38557-5_15},
  author={Michele Ciampi and Rafail Ostrovsky and Luisa Siniscalchi and Hendrik Waldner},
  year=2023
}