Paper 2022/623

Fast Fully Secure Multi-Party Computation over Any Ring with Two-Thirds Honest Majority

Anders Dalskov, Daniel Escudero, and Ariel Nof


We introduce a new MPC protocol to securely compute any functionality over an arbitrary black-box finite ring (which may not be commutative), tolerating $t<n/3$ active corruptions while \textit{guaranteeing output delivery} (G.O.D.). Our protocol is based on replicated secret-sharing, whose share size is known to grow exponentially with the number of parties $n$. However, even though the internal storage and computation in our protocol remains exponential, the communication complexity of our protocol is \emph{constant}, except for a light constant-round check that is performed at the end before revealing the output. Furthermore, the amortized communication complexity of our protocol is not only constant, but very small: only $1 + \frac{t-1}{n}<1\frac{1}{3}$ ring elements per party, per multiplication gate over two rounds of interaction. This improves over the state-of-the art protocol in the same setting by Furukawa and Lindell (CCS 2019), which has a communication complexity of $2\frac{2}{3}$ \emph{field} elements per party, per multiplication gate and while achieving fairness only. As an alternative, we also describe a variant of our protocol which has only one round of interaction per multiplication gate on average, and amortized communication cost of $\le 1\frac{1}{2}$ ring elements per party on average for any natural circuit. Motivated by the fact that efficiency of distributed protocols are much more penalized by high communication complexity than local computation/storage, we perform a detailed analysis together with experiments in order to explore how large the number of parties can be, before the storage and computation overhead becomes prohibitive. Our results show that our techniques are viable even for a moderate number of parties (e.g., $n>10$).

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.The ACM Conference on Computer and Communications Security 2022 (CCS'22)
Multiparty ComputationHonest MajorityRobust Computation
Contact author(s)
daniel escudero @ protonmail com
ariel nof @ biu ac il
anderspkd @ fastmail com
2022-05-23: received
Short URL
Creative Commons Attribution


      author = {Anders Dalskov and Daniel Escudero and Ariel Nof},
      title = {Fast Fully Secure Multi-Party Computation over Any Ring with Two-Thirds Honest Majority},
      howpublished = {Cryptology ePrint Archive, Paper 2022/623},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.