1. Global-Scale Secure Multiparty Computation 2017 CCS GarbledCircuits Implementation MPC
    Xiao Wang, Samuel Ranellucci, and Jonathan Katz
    [View PDF on acmccs.github.io]
    [Show BibTex Citation]

    @inproceedings{10.1145/3133956.3133979,
    author = {Wang, Xiao and Ranellucci, Samuel and Katz, Jonathan},
    title = {Global-Scale Secure Multiparty Computation},
    year = {2017},
    isbn = {9781450349468},
    publisher = {Association for Computing Machinery},
    address = {New York, NY, USA},
    url = {https://doi.org/10.1145/3133956.3133979},
    doi = {10.1145/3133956.3133979},
    booktitle = {Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security},
    pages = {39–56},
    numpages = {18},
    keywords = {secure computation, garbled circuit, multi-party computation},
    location = {Dallas, Texas, USA},
    series = {CCS ’17}
    }

We propose a new, constant-round protocol for multi-party computation of boolean circuits that is secure against an arbitrary number of malicious corruptions. At a high level, we extend and generalize recent work of Wang et al. in the two-party setting. Namely, we design an efficient preprocessing phase that allows the parties to generate authenticated information; we then show how to use this information to distributively construct a single “authenticated” garbled circuit that is evaluated by one party.

Our resulting protocol improves upon the state-of-the-art both asymptotically and concretely. We validate these claims via several experiments demonstrating both the efficiency and scalability of our protocol:

Efficiency: For three-party computation over a LAN, our protocol requires only 95 ms to evaluate AES. This is roughly a 700X improvement over the best prior work, and only 2.5X slower than the best known result in the two-party setting. In general, for n-party computation our protocol improves upon prior work (which was never implemented) by a factor of more than 230n, e.g., an improvement of 3 orders of magnitude for 5-party computation.

Scalability: We successfully executed our protocol with a large number of parties located all over the world, computing (for example) AES with 128 parties across 5 continents in under 3 minutes. Our work represents the largest-scale demonstration of secure computation to date.

  1.