On the Round Complexity of Black-Box Secure MPC

Yuval Ishai, Dakshita Khurana, Amit Sahai, Akshayaram Srinivasan

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


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 with 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 random oblivious transfer (OT) correlations, 2-round protocols making black-box use of a pseudorandom generator were known. However, such protocols were obtained via a round-collapsing “protocol garbling” technique that has poor concrete efficiency and makes non-black-box use of an underlying maliciously 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 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 to construct non-malleable 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Proceedings
EditorsTal Malkin, Chris Peikert
Number of pages30
ISBN (Print)9783030842444
StatePublished - 2021
Event41st Annual International Cryptology Conference, CRYPTO 2021 - Virtual, Online
Duration: Aug 16 2021Aug 20 2021

Publication series

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


Conference41st Annual International Cryptology Conference, CRYPTO 2021
CityVirtual, Online

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On the Round Complexity of Black-Box Secure MPC'. Together they form a unique fingerprint.

Cite this