Paper 2020/581

The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency

Benny Applebaum, Eliran Kachlon, and Arpita Patra


In STOC 1988, Ben-Or, Goldwasser, and Wigderson (BGW) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with perfect (information-theoretic and error-free) security at the presence of an active (aka Byzantine) rushing adversary that controls up to $n/3$ of the parties. We study the round complexity of general secure multiparty computation in the BGW model. Our main result shows that every functionality can be realized in only four rounds of interaction, and that some functionalities cannot be computed in three rounds. This completely settles the round-complexity of perfect actively-secure optimally-resilient MPC, resolving a long line of research. Our lower-bound is based on a novel round-reduction technique that allows us to lift existing three-round lower-bounds for verifiable secret sharing to four-round lower-bounds for general MPC. To prove the upper-bound, we develop new round-efficient protocols for computing degree-2 functionalities over large fields, and establish the completeness of such functionalities. The latter result extends the recent completeness theorem of Applebaum, Brakerski and Tsabary (TCC 2018, Eurocrypt 2019) that was limited to the binary field.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
MPCround complexityinformation theory
Contact author(s)
benny applebaum @ gmail com
elirn chalon @ gmail com
arpita @ iisc ac in
2020-05-18: received
Short URL
Creative Commons Attribution


      author = {Benny Applebaum and Eliran Kachlon and Arpita Patra},
      title = {The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency},
      howpublished = {Cryptology ePrint Archive, Paper 2020/581},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.