Paper 2014/149

Millions of Millionaires: Multiparty Computation in Large Networks

Mahdi Zamani, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
secure computationmultiparty computationthreshold cryptographysecret sharingapplications
Contact author(s)
zamani @ cs unm edu
History
2014-03-24: last of 2 revisions
2014-02-27: received
See all versions
Short URL
https://ia.cr/2014/149
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/149,
      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{https://eprint.iacr.org/2014/149}},
      url = {https://eprint.iacr.org/2014/149}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.