Paper 2017/1003

Secure Multi-Party Computation in Large Networks

Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia, and Mahdi Zamani


We describe scalable protocols for solving the secure multi-party computation (MPC) problem among a significant number of parties. We consider both the synchronous and the asynchronous communication models. In the synchronous setting, our protocol is secure against a static malicious adversary corrupting less than a $1/3$ fraction of the parties. In the asynchronous environment, we allow the adversary to corrupt less than a $1/8$ fraction of parties. For any deterministic function that can be computed by an arithmetic circuit with $m$ gates, both of our protocols require each party to send a number of messages and perform an amount of computation that is $\tilde{O}(m/n + \sqrt n)$. We also show that our protocols provide statistical and universally-composable security. To achieve our asynchronous MPC result, we define the threshold counting problem and present a distributed protocol to solve it in the asynchronous setting. This protocol is load balanced, with computation, communication and latency complexity of $O(\log{n})$, and can also be used for designing other load-balanced applications in the asynchronous communication model.

Available format(s)
Publication info
Published elsewhere. Journal of Distributed Computing
Secure multi-party computationSecret sharingInformation-theoretic securityUniversal composability
Contact author(s)
mzamani @ visa com
2017-10-13: received
Short URL
Creative Commons Attribution


      author = {Varsha Dani and Valerie King and Mahnush Movahedi and Jared Saia and Mahdi Zamani},
      title = {Secure Multi-Party Computation in Large Networks},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1003},
      year = {2017},
      doi = {10.1007/s00446-016-0284-9},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.