**Millions of Millionaires: Multiparty Computation in Large Networks**

*Mahdi Zamani and Mahnush Movahedi and Jared Saia*

**Abstract: **We describe a general Multi-Party Computation (MPC) protocol for arithmetic circuits that is secure against a static malicious adversary corrupting up to a 1/10 fraction of the parties. The protocol requires each party to send an average of soft-O(m/n) bits, and compute soft-O(m/n) operations in a network of size n, where m is the size of circuit. This is achieved by increasing latency from constant to O(d) , where d is the depth of the circuit. Our protocol has a setup phase that is independent of the circuit and relies on Threshold Fully Homomorphic Encryption (TFHE). The setup requires each party to send soft-O(k^2) messages and compute soft-O(k^2) operations, where k is the security parameter. We provide results from microbenchmarks conducted over a sorting network showing that our protocol may be practical for deployment in large networks. For example, we consider a network of size 2^25 (over 33 million), where each party has an input item of size 20 bytes. To securely sort the items, our protocol requires each party on average to send only 5 kilobytes per item sorted.

**Category / Keywords: **cryptographic protocols / secure computation; multiparty computation; threshold cryptography; secret sharing; applications

**Date: **received 27 Feb 2014, last revised 23 Mar 2014

**Contact author: **zamani at cs unm edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20140324:034602 (All versions of this report)

**Short URL: **ia.cr/2014/149

[ Cryptology ePrint archive ]