Paper 2021/346

Round-optimal Honest-majority MPC in Minicrypt and with Everlasting Security

Benny Applebaum, Eliran Kachlon, and Arpita Patra


We study the round complexity of secure multiparty computation (MPC) in the challenging model where full security, including guaranteed output delivery, should be achieved at the presence of an active rushing adversary who corrupts up to half of parties. It is known that 2 rounds are insufficient in this model (Gennaro et al., Crypto 2002), and that 3 round protocols can achieve computational security under public-key assumptions (Gordon et al., Crypto 2015; Ananth et al., Crypto 2018; and Badrinarayanan et al., Asiacrypt 2020). However, despite much effort, it is unknown whether public-key assumptions are inherently needed for such protocols, and whether one can achieve similar results with security against computationally-unbounded adversaries. In this paper, we use Minicrypt-type assumptions to realize 3-round MPC with full and active security. Our protocols come in two flavors: for a small (logarithmic) number of parties $n$, we achieve an optimal resiliency threshold of $t\leq \lfloor (n-1)/2\rfloor$, and for a large (polynomial) number of parties we achieve an almost-optimal resiliency threshold of $t\leq 0.5n(1-\epsilon)$ for an arbitrarily small constant $\epsilon > 0$. Both protocols can be based on sub-exponentially hard injective one-way functions in the plain model. If the parties have an access to a collision resistance hash function, we can derive statistical everlasting security for every NC1 functionality, i.e., the protocol is secure against adversaries that are computationally bounded during the execution of the protocol and become computationally unlimited after the protocol execution. As a secondary contribution, we show that in the strong honest-majority setting ($t<n/3$), every NC1 functionality can be computed in 3 rounds with everlasting security and complexity polynomial in $n$ based on one-way functions. Previously, such a result was only known based on collision-resistance hash function.

Note: The current version significantly deviates from the previous version. Specifically: 1. Protocols for single-input functionality that appeared in the previous version have been strengthened and moved to another paper (Eprint report 2022/167). 2. The derivation of the 3-round MPC protocols was significantly changed and modularized leading to a new compiler. 3. New results for the strong-honest-majority setting (t< n/3) were added. Overall, the current version of this writeup together with (Eprint report 2022/167) fully subsumes the previous versions of this paper.

Available format(s)
Cryptographic protocols
Publication info
Preprint. Minor revision.
multiparty computationround complexityeverlasting security
Contact author(s)
bennyap @ post tau ac il
elirn chalon @ gmail com
arpita @ iisc ac in
2022-03-07: last of 2 revisions
2021-03-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benny Applebaum and Eliran Kachlon and Arpita Patra},
      title = {Round-optimal Honest-majority MPC in Minicrypt and with Everlasting Security},
      howpublished = {Cryptology ePrint Archive, Paper 2021/346},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.