Paper 2021/1467
On the Round Complexity of Black-box Secure MPC
Yuval Ishai, Dakshita Khurana, Amit Sahai, and Akshayaram Srinivasan
Abstract
We consider the question of minimizing the round complexity of secure multiparty computation (MPC) protocols that make a black-box use of simple cryptographic primitives in the setting of security against any number of malicious parties. In the plain model, previous black-box protocols required a high constant number of rounds (>15). This is far from the known lower bound of 4 rounds for protocols with black-box simulators. When allowing a random oblivious transfer (OT) correlation setup, 2-round protocols making a black-box use of a pseudorandom generator were previously known. However, such protocols were obtained via a round-collapsing ``protocol garbling'' technique that has poor concrete efficiency and makes a non-black-box use of an underlying malicious-secure protocol. We improve this state of affairs by presenting the following types of black-box protocols. - 4-round ``pairwise MPC'' in the plain model. This round-optimal protocol enables each ordered pair of parties to compute a function of both inputs whose output is delivered to the second party. The protocol makes black-box use of any public-key encryption (PKE) with pseudorandom public keys. As a special case, we get a black-box round-optimal realization of secure (copies of) OT between every ordered pair of parties. - 2-round MPC from OT correlations. This round-optimal protocol makes a black-box use of any general 2-round MPC protocol satisfying an augmented notion of {\em semi-honest} security. In the two-party case, this yields new kinds of 2-round black-box protocols. - 5-round MPC in the plain model. This protocol makes a black-box use of PKE with pseudorandom public keys, and 2-round oblivious transfer with ``semi-malicious'' security. A key technical tool for the first result is a novel combination of split-state non-malleable codes (Dziembowski, Pietrzak and Wichs, JACM '18) with standalone secure two-party protocols. The second result is based on a new round-optimized variant of the ``IPS compiler'' (Ishai, Prabhakaran and Sahai, Crypto '08). The third result is obtained via a specialized combination of these two techniques.
Note: Full version of the Crypto 2021 paper.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in CRYPTO 2021
- Keywords
- black-boxoblivious transfermulti-party computation
- Contact author(s)
-
yuvali @ cs technion ac il
dakshita @ illinois edu
sahai @ cs ucla edu
akshayaram srinivasan @ tifr res in - History
- 2021-11-06: received
- Short URL
- https://ia.cr/2021/1467
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1467,
author = {Yuval Ishai and Dakshita Khurana and Amit Sahai and Akshayaram Srinivasan},
title = {On the Round Complexity of Black-box Secure MPC},
howpublished = {Cryptology ePrint Archive, Paper 2021/1467},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1467}},
url = {https://eprint.iacr.org/2021/1467}
}
