research-article

Efficient, Constant-Round and Actively Secure MPC: Beyond the Three-Party Case

Authors:

Nishanth Chandran,

Payman Mohassel,

Satyanarayana VusirikalaAuthors Info & Claims

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

Pages 277 - 294

https://doi.org/10.1145/3133956.3134100

Published: 30 October 2017 Publication History

Abstract

While the feasibility of constant-round and actively secure MPC has been known for over two decades, the last few years have witnessed a flurry of designs and implementations that make its deployment a palpable reality. To our knowledge, however, existing concretely efficient MPC constructions are only for up to three parties.

In this paper we design and implement a new actively secure 5PC protocol tolerating two corruptions that requires 8 rounds of interaction, only uses fast symmetric-key operations, and incurs 60% less communication than the passively secure state-of-the-art solution from the work of Ben-Efraim, Lindell, and Omri [CCS 2016]. For example, securely evaluating the AES circuit when the parties are in different regions of the U.S. and Europe only takes 1.8s which is 2.6x faster than the passively secure 5PC in the same environment.

Instrumental for our efficiency gains (less interaction, only symmetric key primitives) is a new 4-party primitive we call Attested OT, which in addition to Sender and Receiver involves two additional "assistant parties" who will attest to the respective inputs of both parties, and which might be of broader applicability in practically relevant MPC scenarios. Finally, we also show how to generalize our construction to n parties with similar efficiency properties where the corruption threshold is t ≈ √n, and propose a combinatorial problem which, if solved optimally, can yield even better corruption thresholds for the same cost.

Supplemental Material

MP4 File

Download
2443.93 MB

References

[1]

abhi shelat and Chih-Hao Shen 2011. Two-Output Secure Computation with Malicious Adversaries Advances in Cryptology - EUROCRYPT 2011 - 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15--19, 2011. Proceedings. 386--405. https://doi.org/10.1007/978-3-642-20465-4_22

[2]

abhi shelat and Chih-Hao Shen 2013. Fast two-party secure computation with minimal assumptions 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS'13, Berlin, Germany, November 4-8, 2013. 523--534. https://doi.org/10.1145/2508859.2516698

Digital Library

[3]

Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara 2016. High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, 805--817.

[4]

Donald Beaver, Silvio Micali, and Phillip Rogaway. 1990. The Round Complexity of Secure Protocols (Extended Abstract) Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13--17, 1990, Baltimore, Maryland, USA. 503--513. https://doi.org/10.1145/100216.100287

Digital Library

[5]

Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. 2012. Foundations of garbled circuits. In the ACM Conference on Computer and Communications Security, CCS'12, Raleigh, NC, USA, October 16--18, 2012. 784--796. https://doi.org/10.1145/2382196.2382279

Digital Library

[6]

Assaf Ben-David, Noam Nisan, and Benny Pinkas. 2008. FairplayMP: a system for secure multi-party computation Proceedings of the 15th ACM conference on Computer and communications security. ACM, 257--266.

[7]

Aner Ben-Efraim, Yehuda Lindell, and Eran Omri. 2016. Implementation of protocol from BLO16. https://github.com/cryptobiu/Semi-Honest-BMR. (2016).

[8]

Aner Ben-Efraim, Yehuda Lindell, and Eran Omri. 2016. Optimizing Semi-Honest Secure Multiparty Computation for the Internet Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24--28, 2016. 578--590.

[9]

Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. 1988. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract), See citeNDBLP:conf/stoc/STOC20, 1--10.

[10]

John Black. 2006. The Ideal-Cipher Model, Revisited: An Uninstantiable Blockcipher-Based Hash Function Fast Software Encryption, 13th International Workshop, FSE 2006 (Lecture Notes in Computer Science), Vol. Vol. 4047. Springer, 328--340. https://doi.org/10.1007/11799313_21

Digital Library

[11]

Dan Bogdanov, Sven Laur, and Jan Willemson 2008. Sharemind: A framework for fast privacy-preserving computations European Symposium on Research in Computer Security. Springer, 192--206.

[12]

Ran Canetti. 2000. Security and Composition of Multiparty Cryptographic Protocols. Vol. 13, 1 (2000), 143--202.

Digital Library

[13]

Ran Canetti. 2001. Universally Composable Security: A New Paradigm for Cryptographic Protocols 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA. 136--145. https://doi.org/10.1109/SFCS.2001.959888

[14]

David Chaum, Claude Crépeau, and Ivan Damgård. 1988. Multiparty Unconditionally Secure Protocols (Extended Abstract), See citeNDBLP:conf/stoc/STOC20, 11--19.

[15]

Koji Chida, Gembu Morohashi, Hitoshi Fuji, Fumihiko Magata, Akiko Fujimura, Koki Hamada, Dai Ikarashi, and Ryuichi Yamamoto. 2014. Implementation and evaluation of an efficient secure computation system using R for healthcare statistics. Journal of the American Medical Informatics Association, Vol. 21, e2 (2014), e326--e331.

[16]

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 Cryptographers' Track at the RSA Conference. Springer, 416--432.

Digital Library

[17]

Seung Geol Choi, Jonathan Katz, Alex J. Malozemoff, and Vassilis Zikas 2014. Efficient Three-Party Computation from Cut-and-Choose Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17--21, 2014, Proceedings, Part II. 513--530. https://doi.org/10.1007/978-3-662-44381-1_29

[18]

Ronald Cramer, Ivan Damgård, and Yuval Ishai. 2005. Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10--12, 2005, Proceedings. 342--362. https://doi.org/10.1007/978-3-540-30576-7_19

Digital Library

[19]

Ivan Damgård and Yuval Ishai 2005. Constant-Round Multiparty Computation Using a Black-Box Pseudorandom Generator Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings. 378--394. https://doi.org/10.1007/11535218_23

Digital Library

[20]

Ivan Damgård, 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 European Symposium on Research in Computer Security. Springer, 1--18.

[21]

Ivan Damgård, Valerio Pastro, Nigel Smart, and Sarah Zakarias 2012. Multiparty computation from somewhat homomorphic encryption. Advances in Cryptology-CRYPTO 2012. Springer, 643--662.

Digital Library

[22]

Jun Furukawa, Yehuda Lindell, Ariel Nof, and Or Weinstein. 2016. High-throughput secure three-party computation for malicious adversaries and an honest majority. Springer, 554--581.

[23]

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

[24]

Vipul Goyal, Payman Mohassel, and Adam Smith. 2008. Efficient two party and multi party computation against covert adversaries Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 289--306.

[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). shownotehttp://eprint.iacr.org/2017/214.

[26]

Thomas Holenstein, Robin Künzler, and Stefano Tessaro. 2010. Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited. CoRR Vol. abs/1011.1264 (2010). http://arxiv.org/abs/1011.1264

[27]

Yan Huang, Jonathan Katz, and David Evans 2013. Efficient Secure Two-Party Computation Using Symmetric Cut-and-Choose CRYPTO (2) (Lecture Notes in Computer Science), Vol. Vol. 8043. Springer, 18--35.

[28]

Yan Huang, Jonathan Katz, Vladimir Kolesnikov, Ranjit Kumaresan, and Alex J Malozemoff 2014. Amortizing garbled circuits. In International Cryptology Conference. Springer, 458--475.

[29]

Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. 2003. Extending Oblivious Transfers Efficiently. In Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings. 145--161. https://doi.org/10.1007/978-3-540-45146-4_9

[30]

Yuval Ishai, Ranjit Kumaresan, Eyal Kushilevitz, and Anat Paskin-Cherniavsky 2015. Secure Computation with Minimal Interaction, Revisited CRYPTO (2) (Lecture Notes in Computer Science), Vol. Vol. 9216. Springer, 359--378.

[31]

Yuval Ishai, Eyal Kushilevitz, and Anat Paskin. 2010. Secure Multiparty Computation with Minimal Interaction CRYPTO (Lecture Notes in Computer Science), Vol. Vol. 6223. Springer, 577--594.

[32]

Jonathan Katz, Samuel Ranellucci, and Xiao Wang. 2017. Authenticated Garbling and Efficient Maliciously Secure Multi-Party Computation. Cryptology ePrint Archive, Report 2017/189. (2017). shownotehttp://eprint.iacr.org/2017/189.

[33]

Marcel Keller, Peter Scholl, and Nigel P Smart. 2013. An architecture for practical actively secure MPC with dishonest majority Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security. ACM, 549--560.

[34]

Benjamin Kreuter, abhi shelat, and Chih-Hao Shen. 2012. Billion-Gate Secure Computation with Malicious Adversaries Proceedings of the 21th USENIX Security Symposium, Bellevue, WA, USA, August 8--10, 2012. 285--300. https://www.usenix.org/conference/usenixsecurity12/technical-sessions/presentation/kreuter

[35]

John Launchbury, Iavor S Diatchki, Thomas DuBuisson, and Andy Adams-Moran 2012. Efficient lookup-table protocol in secure multiparty computation ACM SIGPLAN Notices, Vol. Vol. 47. ACM, 189--200.

[36]

Yehuda Lindell. 2013. Fast Cut-and-Choose Based Protocols for Malicious and Covert Adversaries Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18--22, 2013. Proceedings, Part II. 1--17. https://doi.org/10.1007/978-3-642-40084-1_1

[37]

Yehuda Lindell and Benny Pinkas 2007. An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries. In Advances in Cryptology - EUROCRYPT 2007, 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, May 20-24, 2007, Proceedings. 52--78. https://doi.org/10.1007/978-3-540-72540-4_4

Digital Library

[38]

Yehuda Lindell and Benny Pinkas 2012. Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer. J. Cryptology, Vol. 25, 4 (2012), 680--722. https://doi.org/10.1007/s00145-011-9107-0

Digital Library

[39]

Yehuda Lindell, Benny Pinkas, and Nigel P. Smart. 2008. Implementing Two-Party Computation Efficiently with Security Against Malicious Adversaries Security and Cryptography for Networks, 6th International Conference, SCN 2008, Amalfi, Italy, September 10-12, 2008. Proceedings. 2--20. https://doi.org/10.1007/978-3-540-85855-3_2

Digital Library

[40]

Yehuda Lindell, Benny Pinkas, Nigel P. Smart, and Avishay Yanai 2015. Efficient Constant Round Multi-party Computation Combining BMR and SPDZ CRYPTO (2) (Lecture Notes in Computer Science), Vol. Vol. 9216. Springer, 319--338.

[41]

Yehuda Lindell and Ben Riva 2014. Cut-and-choose Yao-based secure computation in the online/offline and batch settings International Cryptology Conference. Springer, 476--494.

[42]

Yehuda Lindell and Ben Riva 2015. Blazing fast 2pc in the offline/online setting with security for malicious adversaries Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. ACM, 579--590.

[43]

Payman Mohassel and Matthew Franklin 2006. Efficiency tradeoffs for malicious two-party computation. (2006), 458--473 pages.

[44]

Payman Mohassel and Ben Riva 2013. Garbled Circuits Checking Garbled Circuits: More Efficient and Secure Two-Party Computation Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part II. 36--53. https://doi.org/10.1007/978-3-642-40084-1_3

[45]

Payman Mohassel, Mike Rosulek, and Ye Zhang 2015. Fast and Secure Three-party Computation: The Garbled Circuit Approach Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12-6, 2015. 591--602. https://doi.org/10.1145/2810103.2813705

Digital Library

[46]

Jesper Buus Nielsen and Claudio Orlandi 2009. LEGO for Two-Party Secure Computation. Springer Berlin Heidelberg, Berlin, Heidelberg, 368--386. https://doi.org/10.1007/978-3-642-00457-5_22

Digital Library

[47]

Benny Pinkas, Thomas Schneider, Nigel P. Smart, and Stephen C. Williams 2009. Secure Two-Party Computation Is Practical. In Advances in Cryptology - ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009. Proceedings. 250--267. https://doi.org/10.1007/978-3-642-10366-7_15

Digital Library

[48]

Claude E Shannon. 1949. Communication theory of secrecy systems. Bell Labs Technical Journal Vol. 28, 4 (1949), 656--715.

[49]

David P. Woodruff. 2007. Revisiting the Efficiency of Malicious Two-Party Computation Advances in Cryptology - EUROCRYPT 2007, 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, May 20-24, 2007, Proceedings (Lecture Notes in Computer Science), Vol. Vol. 4515. Springer, 79--96. https://doi.org/10.1007/978-3-540-72540-4_5

Digital Library

[50]

Andrew Chi-Chih Yao. 1982. Protocols for Secure Computations (Extended Abstract) FOCS. IEEE, 160--164.

[51]

Yihua Zhang, Aaron Steele, and Marina Blanton. 2013. PICCO: a general-purpose compiler for private distributed computation Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security. ACM, 813--826.

Cited By

Liu YFeng QPeng CLuo MHe D(2023)Asymmetric Secure Multi-party Signing Protocol for the Identity-Based Signature Scheme in the IEEE P1363 Standard for Public Key CryptographyEmerging Information Security and Applications10.1007/978-3-031-23098-1_1(1-20)Online publication date: 4-Jan-2023
https://doi.org/10.1007/978-3-031-23098-1_1
Feng DYang K(2022)Concretely efficient secure multi-party computation protocols: survey and moreSecurity and Safety10.1051/sands/20210011(2021001)Online publication date: 14-Jun-2022
https://doi.org/10.1051/sands/2021001
Tsuchida HNishide T(2021)Client-aided Robust Bit-composition Protocol with Deterministic Cheater Identification in Standard ModelJournal of Information Processing10.2197/ipsjjip.29.51529(515-524)Online publication date: 2021
https://doi.org/10.2197/ipsjjip.29.515
Show More Cited By

Index Terms

Efficient, Constant-Round and Actively Secure MPC: Beyond the Three-Party Case
1. Security and privacy
  1. Cryptography
    1. Mathematical foundations of cryptography

Recommendations

Two-round Multiparty Secure Computation from Minimal Assumptions
We provide new two-round multiparty secure computation (MPC) protocols in the dishonest majority setting assuming the minimal assumption that two-round oblivious transfer (OT) exists. If the assumed two-round OT protocol is secure against semi-honest ...
Efficient Constant-Round Multi-party Computation Combining BMR and SPDZ

Recently, there has been huge progress in the field of concretely efficient secure computation, even while providing security in the presence of malicious adversaries. This is especially the case in the two-party setting, where constant-round protocols ...
Round-Optimal Secure Multi-Party Computation
Advances in Cryptology – CRYPTO 2018
Abstract
Secure multi-party computation (MPC) is a central cryptographic task that allows a set of mutually distrustful parties to jointly compute some function of their private inputs where security should hold in the presence of a malicious adversary ...

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 ACM 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

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

10
Total Citations
View Citations
422
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)4

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu YFeng QPeng CLuo MHe D(2023)Asymmetric Secure Multi-party Signing Protocol for the Identity-Based Signature Scheme in the IEEE P1363 Standard for Public Key CryptographyEmerging Information Security and Applications10.1007/978-3-031-23098-1_1(1-20)Online publication date: 4-Jan-2023
https://doi.org/10.1007/978-3-031-23098-1_1
Feng DYang K(2022)Concretely efficient secure multi-party computation protocols: survey and moreSecurity and Safety10.1051/sands/20210011(2021001)Online publication date: 14-Jun-2022
https://doi.org/10.1051/sands/2021001
Tsuchida HNishide T(2021)Client-aided Robust Bit-composition Protocol with Deterministic Cheater Identification in Standard ModelJournal of Information Processing10.2197/ipsjjip.29.51529(515-524)Online publication date: 2021
https://doi.org/10.2197/ipsjjip.29.515
Patra ARavi D(2021)On the Exact Round Complexity of Secure Three-Party ComputationJournal of Cryptology10.1007/s00145-021-09404-034:4Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s00145-021-09404-0
Choudhury AHegde A(2020)High Throughput Secure MPC over Small Population in Hybrid Networks (Extended Abstract)Progress in Cryptology – INDOCRYPT 202010.1007/978-3-030-65277-7_37(832-855)Online publication date: 13-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-65277-7_37
Chaudhari HChoudhury APatra ASuresh ASion RPapamanthou C(2019)ASTRAProceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security Workshop10.1145/3338466.3358922(81-92)Online publication date: 11-Nov-2019
https://dl.acm.org/doi/10.1145/3338466.3358922
Byali MHazay CPatra ASingla SCavallaro LKinder JWang XKatz J(2019)Fast Actively Secure Five-Party Computation with Security Beyond AbortProceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security10.1145/3319535.3345657(1573-1590)Online publication date: 6-Nov-2019
https://dl.acm.org/doi/10.1145/3319535.3345657
Ben-Efraim AOmri E(2019)Concrete Efficiency Improvements for Multiparty Garbling with an Honest MajorityProgress in Cryptology – LATINCRYPT 201710.1007/978-3-030-25283-0_16(289-308)Online publication date: 20-Jul-2019
https://doi.org/10.1007/978-3-030-25283-0_16
Byali MJoseph APatra ARavi DLie DMannan MBackes MWang X(2018)Fast Secure Computation for Small Population over the InternetProceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security10.1145/3243734.3243784(677-694)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.1145/3243734.3243784
Mohassel PRindal PLie DMannan MBackes MWang X(2018)ABY3Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security10.1145/3243734.3243760(35-52)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.1145/3243734.3243760

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents