Paper 2017/1003
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.
Metadata
- Available format(s)
-
PDF
- 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
- 2017-10-13: received
- Short URL
- https://ia.cr/2017/1003
- License
-
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},
url = {https://eprint.iacr.org/2017/1003}
}