Cryptology ePrint Archive: Report 2017/1003

Secure Multi-Party Computation in Large Networks

Varsha Dani and Valerie King and Mahnush Movahedi and 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.

Category / Keywords: Secure multi-party computation, Secret sharing, Information-theoretic security, Universal composability

Original Publication (in the same form): Journal of Distributed Computing
DOI:
10.1007/s00446-016-0284-9

Date: received 19 Sep 2017, last revised 11 Oct 2017

Contact author: mzamani at visa com

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2017/1003

[ Cryptology ePrint archive ]