Paper 2023/1512

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

Michele Ciampi, The University of Edinburgh
Rafail Ostrovsky, University of California, Los Angeles
Luisa Siniscalchi, Technical University of Denmark
Hendrik Waldner, University of Maryland, College Park, Max Planck Institute for Security and Privacy
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 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2023
DOI
10.1007/978-3-031-38557-5_15
Keywords
multiparty computationround-optimalblack-box
Contact author(s)
michele ciampi @ ed ac uk
rafail @ cs ucla edu
luisi @ dtu dk
hwaldner @ umd edu
History
2023-10-06: approved
2023-10-03: received
See all versions
Short URL
https://ia.cr/2023/1512
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1512,
      author = {Michele Ciampi and Rafail Ostrovsky and Luisa Siniscalchi and Hendrik Waldner},
      title = {List Oblivious Transfer and Applications to Round-Optimal Black-Box Multiparty Coin Tossing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1512},
      year = {2023},
      doi = {10.1007/978-3-031-38557-5_15},
      url = {https://eprint.iacr.org/2023/1512}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.