Paper 2023/418

The Round Complexity of Statistical MPC with Optimal Resiliency

Benny Applebaum, Tel Aviv University
Eliran Kachlon, Tel Aviv University
Arpita Patra, Indian Institute of Science Bangalore

In STOC 1989, Rabin and Ben-Or (RB) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with statistical (information-theoretic) security in the presence of an active (aka Byzantine) rushing adversary that controls up to half of the parties. We study the round complexity of general secure multiparty computation and several related tasks in the RB model. Our main result shows that every functionality can be realized in only four rounds of interaction which is known to be optimal. This completely settles the round complexity of statistical actively-secure optimally-resilient MPC, resolving a long line of research. Along the way, we construct the first round-optimal statistically-secure verifiable secret sharing protocol (Chor, Goldwasser, Micali, and Awerbuch; STOC 1985), show that every single-input functionality (e.g., multi-verifier zero-knowledge) can be realized in 3 rounds, and prove that the latter bound is optimal. The complexity of all our protocols is exponential in the number of parties, and the question of deriving polynomially-efficient protocols is left for future research. Our main technical contribution is a construction of a new type of statistically-secure signature scheme whose existence was open even for smaller resiliency thresholds. We also describe a new statistical compiler that lifts up passively-secure protocols to actively-secure protocols in a round-efficient way via the aid of protocols for single-input functionalities. This compiler can be viewed as a statistical variant of the GMW compiler (Goldreich, Micali, Wigderson; STOC, 1987) that originally employed zero-knowledge proofs and public-key encryption.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. STOC 2023
MPCverifiable secret sharinground complexity
Contact author(s)
bennyap @ post tau ac il
elirn chalon @ gmail com
arpita @ iisc ac in
2023-03-24: approved
2023-03-23: received
See all versions
Short URL
Creative Commons Attribution


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