Paper 2020/1419

The Resiliency of MPC with Low Interaction: The Benefit of Making Errors

Benny Applebaum, Eliran Kachlon, and Arpita Patra


We study information-theoretic secure multiparty protocols that achieve full security, including guaranteed output delivery, at the presence of an active adversary that corrupts a constant fraction of the parties. It is known that 2 rounds are insufficient for such protocols even when the adversary corrupts only two parties (Gennaro, Ishai, Kushilevitz, and Rabin; Crypto 2002), and that perfect protocols can be implemented in $3$ rounds as long as the adversary corrupts less than a quarter of the parties (Applebaum , Brakerski, and Tsabary; Eurocrypt, 2019). Furthermore, it was recently shown that the quarter threshold is tight for any 3-round \emph{perfectly-secure} protocol (Applebaum, Kachlon, and Patra; FOCS 2020). Nevertheless, one may still hope to achieve a better-than-quarter threshold at the expense of allowing some negligible correctness errors and/or statistical deviations in the security. Our main results show that this is indeed the case. Every function can be computed by 3-round protocols with \emph{statistical} security as long as the adversary corrupts less than a third of the parties. Moreover, we show that any better resiliency threshold requires $4$ rounds. Our protocol is computationally inefficient and has an exponential dependency in the circuit's depth $d$ and in the number of parties $n$. We show that this overhead can be avoided by relaxing security to computational, assuming the existence of a non-interactive commitment (NICOM). Previous 3-round computational protocols were based on stronger public-key assumptions. When instantiated with statistically-hiding NICOM, our protocol provides \emph{everlasting statistical} security, i.e., it is secure against adversaries that are computationally unlimited \emph{after} the protocol execution. To prove these results, we introduce a new hybrid model that allows for 2-round protocols with a linear resiliency threshold. Here too we prove that, for perfect protocols, the best achievable resiliency is $n/4$, whereas statistical protocols can achieve a threshold of $n/3$. In the plain model, we also construct the first 2-round $n/3$-statistical verifiable secret sharing that supports second-level sharing and prove a matching lower-bound, extending the results of Patra, Choudhary, Rabin, and Rangan (Crypto 2009). Overall, our results refine the differences between statistical and perfect models of security and show that there are efficiency gaps even for thresholds that are realizable in both models.

Note: Fixed rendering issues - text was somewhat blurry in the previous version.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2020
foundationssecure computationsecret sharinginformation-theoretic cryptography
Contact author(s)
benny applebaum @ gmail com
elirn chalon @ gmail com
arpita @ iisc ac in
2022-05-02: revised
2020-11-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benny Applebaum and Eliran Kachlon and Arpita Patra},
      title = {The Resiliency of {MPC} with Low Interaction: The Benefit of Making Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1419},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.