Paper 2014/149

Millions of Millionaires: Multiparty Computation in Large Networks

Mahdi Zamani, Mahnush Movahedi, and Jared Saia


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
secure computationmultiparty computationthreshold cryptographysecret sharingapplications
Contact author(s)
zamani @ cs unm edu
2014-03-24: last of 2 revisions
2014-02-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mahdi Zamani and Mahnush Movahedi and Jared Saia},
      title = {Millions of Millionaires: Multiparty Computation in Large Networks},
      howpublished = {Cryptology ePrint Archive, Paper 2014/149},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.