Millions of Millionaires: Multiparty Computation in Large Networks.
Mahdi Zamani, Mahnush Movahedi, Jared Saia · IACR Cryptology ePrint Archive · 2014
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/7 fraction of the parties. The protocol requires each party to send an average of O ( m n log 3 n ) bits, and compute O ( m n log 4 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 O(κ) messages and compute O(κ) operations, where κ 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 (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 5 kilobytes per item sorted.