### Secure Multi-Party Computation in Large Networks

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

##### Abstract

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
DOI
10.1007/s00446-016-0284-9
Keywords
Secure multi-party computationSecret sharingInformation-theoretic securityUniversal composability
Contact author(s)
mzamani @ visa com
History
Short URL
https://ia.cr/2017/1003

CC BY

BibTeX

@misc{cryptoeprint:2017/1003,
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{https://eprint.iacr.org/2017/1003}},
url = {https://eprint.iacr.org/2017/1003}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.