research-article

Public Access

Global-Scale Secure Multiparty Computation

Authors:

Samuel Ranellucci,

Jonathan KatzAuthors Info & Claims

CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

Pages 39 - 56

https://doi.org/10.1145/3133956.3133979

Published: 30 October 2017 Publication History

Abstract

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.

References

[1]

Arash Afshar, Payman Mohassel, Benny Pinkas, and Ben Riva. 2014. Non-Interactive Secure Computation Based on Cut-and-Choose Eurocrypt 2014 (LNCS), Vol. Vol. 8441. 387--404.

[2]

Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara 2016. High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority ACM CCS 2016. 805--817.

[3]

Donald Beaver, Silvio Micali, and Phillip Rogaway. 1990. The round complexity of secure protocols. In Proceedings of the twenty-second annual ACM symposium on Theory of computing. ACM, 503--513.

Digital Library

[4]

Mihir Bellare, Viet Tung Hoang, Sriram Keelveedhi, and Phillip Rogaway 2013. Efficient Garbling from a Fixed-Key Blockcipher. IEEE Symposium on Security & Privacy. 478--492.

Digital Library

[5]

Assaf Ben-David, Noam Nisan, and Benny Pinkas. 2008. FairplayMP: a system for secure multi-party computation ACM CCS 2008. 257--266.

[6]

Aner Ben-Efraim, Yehuda Lindell, and Eran Omri. 2016. Optimizing Semi-Honest Secure Multiparty Computation for the Internet ACM CCS 2016. 578--590.

[7]

Rikke Bendlin, Ivan Damgård, Claudio Orlandi, and Sarah Zakarias 2011. Semi-homomorphic Encryption and Multiparty Computation Eurocrypt 2011 (LNCS), Vol. Vol. 6632. 169--188.

[8]

Dan Bogdanov, Liina Kamm, Baldur Kubo, Reimo Rebane, Ville Sokk, and Riivo Talviste. 2016. Students and Taxes: A Privacy-Preserving Social Study Using Secure Computation Privacy Enhancing Technologies Symposium (PETS).

[9]

Dan Bogdanov, Sven Laur, and Jan Willemson 2008. Sharemind: A Framework for Fast Privacy-Preserving Computations ESORICS 2008 (LNCS), Vol. Vol. 5283. 192--206.

[10]

Peter Bogetoft, Dan Lund Christensen, Ivan Damgård, Martin Geisler, Thomas Jakobsen, Mikkel Krøigaard, Janus Dam Nielsen, Jesper Buus Nielsen, Kurt Nielsen, Jakob Pagter, Michael I. Schwartzbach, and Tomas Toft 2009. Secure Multiparty Computation Goes Live. In FC 2009 (LNCS), Vol. Vol. 5628. 325--343.

Digital Library

[11]

Martin Burkhart, Mario Strasser, Dilip Many, and Xenofontas Dimitropoulos 2010. SEPIA: Privacy-preserving aggregation of multi-domain network events and statistics 19th USENIX Security Symposium, bibfieldeditorIan Goldberg (Ed.). USENIX Association, Washington, D.C., USA.

[12]

Sai Sheshank Burra, Enrique Larraia, Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, Emmanuela Orsini, Peter Scholl, and Nigel P. Smart 2015. High Performance Multi-Party Computation for Binary Circuits Based on Oblivious Transfer. Cryptology ePrint Archive, Report 2015/472. (2015). shownotehttp://eprint.iacr.org/2015/472.

[13]

Seung Geol Choi, Kyung-Wook Hwang, Jonathan Katz, Tal Malkin, and Dan Rubenstein. 2012. Secure Multi-Party Computation of Boolean Circuits with Applications to Privacy in On-Line Marketplaces. In CT-RSA 2012 (LNCS), Vol. Vol. 7178. 416--432.

Digital Library

[14]

Seung Geol Choi, Jonathan Katz, Alex J. Malozemoff, and Vassilis Zikas 2014. Efficient Three-Party Computation from Cut-and-Choose Crypto 2014, Part II (LNCS), Vol. Vol. 8617. 513--530.

[15]

Ivan Damgård, Martin Geisler, Mikkel Krøigaard, and Jesper Buus Nielsen 2009. Asynchronous Multiparty Computation: Theory and Implementation PKC 2009 (LNCS), Vol. Vol. 5443. 160--179.

[16]

Ivan Damgård and Yuval Ishai 2005. Constant-Round Multiparty Computation Using a Black-Box Pseudorandom Generator Crypto 2005 (LNCS), Vol. Vol. 3621. 378--394.

[17]

Ivan Damgård, Marcel Keller, Enrique Larraia, Christian Miles, and Nigel P. Smart. 2012. Implementing AES via an Actively/Covertly Secure Dishonest-Majority MPC Protocol SCN 12 (LNCS), Vol. Vol. 7485. 241--263.

[18]

Ivan Damgr ard, Marcel Keller, Enrique Larraia, Valerio Pastro, Peter Scholl, and Nigel P. Smart. 2013. Practical Covertly Secure MPC for Dishonest Majority - Or: Breaking the SPDZ Limits ESORICS 2013 (LNCS), Vol. Vol. 8134. 1--18.

[19]

Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias 2012. Multiparty Computation from Somewhat Homomorphic Encryption Crypto 2012 (LNCS), Vol. Vol. 7417. 643--662.

[20]

Tore Kasper Frederiksen, Marcel Keller, Emmanuela Orsini, and Peter Scholl 2015. A Unified Approach to MPC with Preprocessing Using OT ASIACRYPT 2015, Part I (LNCS), Vol. Vol. 9452. 711--735.

[21]

Jun Furukawa, Yehuda Lindell, Ariel Nof, and Or Weinstein. 2017. High-Throughput Secure Three-Party Computation for Malicious Adversaries and an Honest Majority Eurocrypt 2017, Part II (LNCS), Vol. Vol. 10211. 225--255.

[22]

Oded Goldreich. 2009. Foundations of Cryptography: Volume 2, Basic Applications. Vol. Vol. 2. Cambridge University Press.

Digital Library

[23]

Oded Goldreich, Silvio Micali, and Avi Wigderson. 1987. How to Play any Mental Game, or A Completeness Theorem for Protocols with Honest Majority 19th ACM STOC. 218--229.

[24]

Shafi Goldwasser and Yehuda Lindell 2005. Secure Multi-Party Computation without Agreement. Journal of Cryptology Vol. 18, 3 (July 2005), 247--287.

Digital Library

[25]

Carmit Hazay, Peter Scholl, and Eduardo Soria-Vazquez. 2017. Low Cost Constant Round MPC Combining BMR and Oblivious Transfer. Cryptology ePrint Archive, Report 2017/214. (2017). shownoteTo appear in Asiacrypt 2017.

[26]

Thomas P. Jakobsen, Marc X. Makkes, and Janus Dam Nielsen. 2010. Efficient Implementation of the Orlandi Protocol ACNS 10 (LNCS), Vol. Vol. 6123. 255--272.

[27]

Marcel Keller, Emmanuela Orsini, and Peter Scholl. 2015. Actively Secure OT Extension with Optimal Overhead Crypto 2015, Part I (LNCS), Vol. Vol. 9215. 724--741.

[28]

Marcel Keller, Emmanuela Orsini, and Peter Scholl. 2016. MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer ACM CCS 2016. 830--842.

Digital Library

[29]

Marcel Keller, Peter Scholl, and Nigel P. Smart. 2013. An architecture for practical actively secure MPC with dishonest majority ACM CCS 2013. 549--560.

[30]

Enrique Larraia, Emmanuela Orsini, and Nigel P. Smart. 2014. Dishonest Majority Multi-Party Computation for Binary Circuits Crypto 2014, Part II (LNCS), Vol. Vol. 8617. 495--512.

[31]

Yehuda Lindell, Benny Pinkas, Nigel P. Smart, and Avishay Yanai 2015. Efficient Constant Round Multi-party Computation Combining BMR and SPDZ Crypto 2015, Part II (LNCS), Vol. Vol. 9216. 319--338.

[32]

Yehuda Lindell, Nigel P. Smart, and Eduardo Soria-Vazquez. 2016. More Efficient Constant-Round Multi-party Computation from BMR and SHE TCC 2016-B, Part I (LNCS), Vol. Vol. 9985. 554--581.

[33]

Payman Mohassel, Mike Rosulek, and Ye Zhang 2015. Fast and Secure Three-party Computation: The Garbled Circuit Approach ACM CCS 2015. 591--602.

Digital Library

[34]

Jesper Nielsen, Thomas Schneider, and Roberto Trifiletti. 2017. Constant-Round Maliciously Secure 2PC with Function-Independent Preprocessing Using LEGO Network and Distributed System Security Symposium (NDSS).

[35]

Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, and Sai Sheshank Burra. 2012. A New Approach to Practical Active-Secure Two-Party Computation Crypto 2012 (LNCS), Vol. Vol. 7417. 681--700.

[36]

Xiao Wang, Alex J. Malozemoff, and Jonathan Katz. 2016. EMP-Toolkit: Efficient Multiparty Computation Toolkit. https://github.com/emp-toolkit. (2016).

[37]

Xiao Wang, Samuel Ranellucci, and Jonathan Katz. 2017. Authenticated Garbling and Efficient Maliciously Secure Two-Party Computation ACM CCS 2017.

[38]

Andrew Chi-Chih Yao. 1986. How to Generate and Exchange Secrets. In IEEE FOCS. 162--167.

Digital Library

Cited By

Lian RZheng YWang C(2024)PrivRo: A Privacy-Preserving Crowdsourcing Service With Robust Quality AwarenessIEEE Transactions on Services Computing10.1109/TSC.2024.337715817:4(1682-1697)Online publication date: Jul-2024
https://doi.org/10.1109/TSC.2024.3377158
Miao GWu S(2024)Efficient Privacy-Preserving Logistic Model With Malicious SecurityIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.340231919(5751-5766)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3402319
Zhai MWu QLiu YQin BDai XGao QSusilo W(2024)Secret Multiple Leaders & Committee Election With Application to Sharding BlockchainIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.339058419(5060-5074)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3390584
Show More Cited By

Index Terms

Global-Scale Secure Multiparty Computation
1. Theory of computation
  1. Computational complexity and cryptography
    1. Cryptographic protocols

Recommendations

Authenticated Garbling and Efficient Maliciously Secure Two-Party Computation
CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security
We propose a simple and efficient framework for obtaining efficient constant-round protocols for maliciously secure two-party computation. Our framework uses a function-independent preprocessing phase to generate authenticated information for the two ...
Zero-knowledge from secure multiparty computation
STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

We present a general construction of a zero-knowledge proof for an NP relation R(x,w) which only makes a black-box use of a secure protocol for a related multi-partyfunctionality f. The latter protocol is only required to be secure against a small ...
Two-Round Adaptively Secure Multiparty Computation from Standard Assumptions
Theory of Cryptography
Abstract
We present the first two-round multiparty computation (MPC) protocols secure against malicious adaptive corruption in the common reference string (CRS) model, based on DDH, LWE, or QR. Prior two-round adaptively secure protocols were known only in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

October 2017

2682 pages

ISBN:9781450349468

DOI:10.1145/3133956

General Chair:
Bhavani Thuraisingham
The University of Texas at Dallas, USA
,
Program Chairs:
David Evans
University of Virginia
,
Tal Malkin
Columbia University
,
Dongyan Xu
Purdue University

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 October 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

DARPA SPAWAR
NSF

Conference

CCS '17

Sponsor:

SIGSAC

CCS '17: 2017 ACM SIGSAC Conference on Computer and Communications Security

October 30 - November 3, 2017

Texas, Dallas, USA

Acceptance Rates

CCS '17 Paper Acceptance Rate 151 of 836 submissions, 18%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

108
Total Citations
View Citations
2,056
Total Downloads

Downloads (Last 12 months)450
Downloads (Last 6 weeks)70

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lian RZheng YWang C(2024)PrivRo: A Privacy-Preserving Crowdsourcing Service With Robust Quality AwarenessIEEE Transactions on Services Computing10.1109/TSC.2024.337715817:4(1682-1697)Online publication date: Jul-2024
https://doi.org/10.1109/TSC.2024.3377158
Miao GWu S(2024)Efficient Privacy-Preserving Logistic Model With Malicious SecurityIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.340231919(5751-5766)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3402319
Zhai MWu QLiu YQin BDai XGao QSusilo W(2024)Secret Multiple Leaders & Committee Election With Application to Sharding BlockchainIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.339058419(5060-5074)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3390584
Xu RLi BLi CJoshi JMa SZhou TDong JLi J(2024) TAPFed : Threshold Secure Aggregation for Privacy-Preserving Federated Learning IEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.3350206(1-14)Online publication date: 2024
https://doi.org/10.1109/TDSC.2024.3350206
Lu YZhang BRen K(2024)Maliciously Secure MPC From Semi-Honest 2PC in the Server-Aided ModelIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.332239721:4(3109-3125)Online publication date: Jul-2024
https://doi.org/10.1109/TDSC.2023.3322397
Ngong IGibson NNear J(2024)Olympia: A Simulation Framework for Evaluating the Concrete Scalability of Secure Aggregation Protocols2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)10.1109/SaTML59370.2024.00033(534-551)Online publication date: 9-Apr-2024
https://doi.org/10.1109/SaTML59370.2024.00033
Zhang WGuo XYang KZhu RYu YWang X(2024)Efficient Actively Secure DPF and RAM-based 2PC with One-Bit Leakage2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00205(561-577)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00205
Garg RYang KKatz JWang X(2024)Scalable Mixed-Mode MPC2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00106(523-541)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00106
Han YXu CLi SLu J(2024)Two-Factor Distributed Authentication Scheme for Cloud Storage2024 9th International Conference on Computer and Communication Systems (ICCCS)10.1109/ICCCS61882.2024.10602986(297-303)Online publication date: 19-Apr-2024
https://doi.org/10.1109/ICCCS61882.2024.10602986
Zhou ZZhang BZhou HRen K(2024)Practical Constructions for Single Input Functionality Against a Dishonest Majority2024 IEEE 9th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP60621.2024.00029(398-414)Online publication date: 8-Jul-2024
https://doi.org/10.1109/EuroSP60621.2024.00029
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents