research-article

Open access

An architecture for practical actively secure MPC with dishonest majority

Authors:

Nigel P. SmartAuthors Info & Claims

CCS '13: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security

Pages 549 - 560

https://doi.org/10.1145/2508859.2516744

Published: 04 November 2013 Publication History

Abstract

We present a runtime environment for executing secure programs via a multi-party computation protocol in the preprocessing model. The runtime environment is general and allows arbitrary reactive computations to be performed. A particularly novel aspect is that it automatically determines the minimum number of rounds needed for a computation, given a specific instruction sequence, and it then uses this to minimize the overall cost of the computation. Various experiments are reported on, on various non-trivial functionalities. We show how, by utilizing the ability of modern processors to execute multiple threads at a time, one can obtain various tradeoffs between latency and throughput

References

[1]

M. Aliasgari, M. Blanton, Y. Zhang, and A. Steele. Secure computation on floating point numbers. In Network and Distributed System Security Symposium -- NDSS 2013, 2013.

[2]

D. Beaver. Efficient multiparty protocols using circuit randomization. In J. Feigenbaum, editor, CRYPTO, volume 576 of Lecture Notes in Computer Science, pages 420--432. Springer, 1991.

Digital Library

[3]

A. Ben-David, N. Nisan, and B. Pinkas. FairplayMP: a system for secure multi-party computation. In P. Ning, P. F. Syverson, and S. Jha, editors, ACM Conference on Computer and Communications Security, pages 257--266. ACM, 2008.

Digital Library

[4]

M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In J. Simon, editor, STOC, pages 1--10. ACM, 1988.

Digital Library

[5]

R. Bendlin, I. Damgård, C. Orlandi, and S. Zakarias. Semi-homomorphic encryption and multiparty computation. In EUROCRYPT, volume 6632 of Lecture Notes in Computer Science, pages 169--188, 2011.

Digital Library

[6]

D. Bogdanov, S. Laur, and J. Willemson. Sharemind: A framework for fast privacy-preserving computations. In ESORICS, volume 5283 of Lecture Notes in Computer Science, pages 192--206. Springer, 2008.

Digital Library

[7]

O. Catrina and S. de Hoogh. Improved primitives for secure multiparty integer computation. In J. A. Garay and R. D. Prisco, editors, SCN, volume 6280 of Lecture Notes in Computer Science, pages 182--199. Springer, 2010.

Digital Library

[8]

O. Catrina and A. Saxena. Secure computation with fixed-point numbers. In Financial Cryptography, volume 6052 of Lecture Notes in Computer Science, pages 35--50. Springer, 2010.

Digital Library

[9]

S. G. Choi, K.-W. Hwang, J. Katz, T. Malkin, and D. Rubenstein. Secure multi-party computation of boolean circuits with applications to privacy in on-line marketplaces. In O. Dunkelman, editor, CT-RSA, volume 7178 of Lecture Notes in Computer Science, pages 416--432. Springer, 2012.

Digital Library

[10]

I. Damgård, M. Fitzi, E. Kiltz, J. B. Nielsen, and T. Toft. Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation. In S. Halevi and T. Rabin, editors, Theory of Cryptography -- TCC 2006, volume 3876 of Lecture Notes in Computer Science, pages 285--304. Springer, 2006.

Digital Library

[11]

I. Damgård, M. Geisler, M. Krøigaard, and J. B. Nielsen. Asynchronous multiparty computation: Theory and implementation. In S. Jarecki and G. Tsudik, editors, Public Key Cryptography -- PKC 2009, volume 5443 of Lecture Notes in Computer Science, pages 160--179. Springer, 2009.

Digital Library

[12]

I. Damgård and M. Keller. Secure multiparty AES. In R. Sion, editor, Financial Cryptography, volume 6052 of Lecture Notes in Computer Science, pages 367--374. Springer, 2010.

Digital Library

[13]

I. Damgård, M. Keller, E. Larraia, C. Miles, and N. P. Smart. Implementing AES via an actively/covertly secure dishonest-majority MPC protocol. In SCN, volume 7485 ofLecture Notes in Computer Science, pages 241--263. Springer, 2012.

Digital Library

[14]

I. Damgard, M. Keller, E. Larraia, V. Pastro, P. Scholl, and N. P. Smart. Practical Covertly Secure MPC for Dishonest Majority -- or: Breaking the SPDZ Limits. In To appear - ESORICS. Springer, 2013.

[15]

I. Damgård, V. Pastro, N. P. Smart, and S. Zakarias. Multiparty computation from somewhat homomorphic encryption. In CRYPTO, volume 7417 of Lecture Notes in Computer Science, pages 643--662. Springer, 2012.

[16]

W. Henecka, S. Kögl, A.-R. Sadeghi, T. Schneider, and I. Wehrenberg. Tasty: tool for automating secure two-party computations. In E. Al-Shaer, A. D. Keromytis, and V. Shmatikov, editors, ACM Conference on Computer and Communications Security, pages 451--462. ACM, 2010.

Digital Library

[17]

Y. Huang, D. Evans, J. Katz, and L. Malka. Faster secure two-party computation using garbled circuits. In USENIX Security Symposium. USENIX Association, 2011.

Digital Library

[18]

K. V. Jónsson, G. Kreitz, and M. Uddin. Secure multi-party sorting and applications. IACR Cryptology ePrint Archive, 2011:122, 2011.

[19]

F. Kerschbaum. Automatically optimizing secure computation. In Y. Chen, G. Danezis, and V. Shmatikov, editors, ACM Conference on Computer and Communications Security, pages 703--714. ACM, 2011.

Digital Library

[20]

B. Kreuter, A. Shelat, and C.-H. Shen. Towards billion-gate secure computation with malicious adversaries. In USENIX Security Symposium -- 2012, pages 285--300, 2012.

Digital Library

[21]

J. Launchbury, I. S. Diatchki, T. DuBuisson, and A. Adams-Moran. Efficient lookup-table protocol in secure multiparty computation. In P. Thiemann and R. B. Findler, editors, ICFP, pages 189--200. ACM, 2012.

Digital Library

[22]

S. Laur, R. Talviste, and J. Willemson. Aes block cipher implementation and secure database join on the sharemind secure multi-party computation framework, 2012.

[23]

Y. Lindell, E. Oxman, and B. Pinkas. The IPS compiler: Optimizations, variants and concrete efficiency. In P. Rogaway, editor, CRYPTO, volume 6841 of Lecture Notes in Computer Science, pages 259--276. Springer, 2011.

Digital Library

[24]

Y. Lindell, B. Pinkas, and N. P. Smart. Implementing two-party computation efficiently with security against malicious adversaries. In R. Ostrovsky, R. D. Prisco, and I. Visconti, editors, Security and Cryptography for Networks -- SCN 2008, volume 5229 of Lecture Notes in Computer Science, pages 2--20. Springer, 2008.

Digital Library

[25]

D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay - Secure two-party computation system. In USENIX Security Symposium -- 2004, pages 287--302, 2004.

Digital Library

[26]

J. B. Nielsen, P. S. Nordholt, C. Orlandi, and S. S. Burra. A new approach to practical active-secure two-party computation. In CRYPTO, volume 7417 of Lecture Notes in Computer Science, pages 681--700. Springer, 2012.

[27]

J. B. Nielsen and C. Orlandi. LEGO for two-party secure computation. In TCC, volume 5444 of Lecture Notes in Computer Science, pages 368--386. Springer, 2009.

Digital Library

[28]

B. Pinkas, T. Schneider, N. P. Smart, and S. C. Williams. Secure two-party computation is practical. In M. Matsui, editor, Advances in Cryptology -- ASIACRYPT 2009, volume 5912 of Lecture Notes in Computer Science, pages 250--267. Springer, 2009.

Digital Library

[29]

A. Rastogi, P. Mardziel, M. Hicks, and M. A. Hammer. Knowledge inference for optimizing secure multi-party computation. Manuscript, 2013.

[30]

SecureSCM Project:. Cryptographic aspects - security analysis, 2010. secureSCM deliverable D9.2.

[31]

A. Shelat and C.-H. Shen. Two-output secure computation with malicious adversaries. In K. G. Paterson, editor, EUROCRYPT, volume 6632 of Lecture Notes in Computer Science, pages 386--405. Springer, 2011.

Digital Library

[32]

SIMAP Project. SIMAP: Secure information management and processing. http://alexandra.dk/uk/Projects/Pages/SIMAP.aspx.

Cited By

Ben-Itzhak YMöllering HPinkas BSchneider TSuresh ATkachenko OVargaftik SWeinert CYalame HYanai A(2024)ScionFL: Efficient and Robust Secure Quantized Aggregation2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)10.1109/SaTML59370.2024.00031(490-511)Online publication date: 9-Apr-2024
https://doi.org/10.1109/SaTML59370.2024.00031
Liang ZWang H(2024)FedST: secure federated shapelet transformation for time series classificationThe VLDB Journal10.1007/s00778-024-00865-w33:5(1617-1641)Online publication date: 26-Jul-2024
https://doi.org/10.1007/s00778-024-00865-w
Levy BIshaq MSherman BKennard LMilanova AZikas VMeng WJensen CCremers CKirda E(2023)COMBINE: COMpilation and Backend-INdependent vEctorization for Multi-Party ComputationProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623181(2531-2545)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623181
Show More Cited By

Index Terms

An architecture for practical actively secure MPC with dishonest majority
1. Security and privacy

Recommendations

Hybrid-secure MPC: trading information-theoretic robustness for computational privacy
PODC '10: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing

Most protocols for distributed, fault-tolerant computation, or multi-party computation (MPC), provide security guarantees in an all-or-nothing fashion. In contrast, a hybrid-secure protocol provides different security guarantees depending on the set of ...
Protocols for Multiparty Coin Toss with a Dishonest Majority

Coin-tossing protocols are protocols that generate a random bit with uniform distribution, although some corrupted parties might try to bias the output. These protocols are used as a building block in many cryptographic protocols. Cleve (Proc. of the ...
Bounded-concurrent secure multi-party computation with a dishonest majority
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

We show how to securely realize any multi-party functionality in a way that preserves security under an a-priori bounded number of concurrent executions, regardless of the number of corrupted parties. Previous protocols for the above task either rely on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '13: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security

November 2013

1530 pages

ISBN:9781450324779

DOI:10.1145/2508859

General Chair:
Ahmad-Reza Sadeghi
TU Darmstadt, CASED, Intel ICRI-SC, Germany
,
Program Chairs:
Virgil Gligor
Carnegie Mellon University, USA
,
Moti Yung
Columbia University, USA

Copyright © 2013 Owner/Author.

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2013

Check for updates

Author Tag

multi-party computation

Qualifiers

Research-article

Conference

CCS'13

Sponsor:

SIGSAC

CCS'13: 2013 ACM SIGSAC Conference on Computer and Communications Security

November 4 - 8, 2013

Berlin, Germany

Acceptance Rates

CCS '13 Paper Acceptance Rate 105 of 530 submissions, 20%;

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

Upcoming Conference

CCS '24

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 14 - 18, 2024

Salt Lake City , UT , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
1,427
Total Downloads

Downloads (Last 12 months)192
Downloads (Last 6 weeks)35

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ben-Itzhak YMöllering HPinkas BSchneider TSuresh ATkachenko OVargaftik SWeinert CYalame HYanai A(2024)ScionFL: Efficient and Robust Secure Quantized Aggregation2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)10.1109/SaTML59370.2024.00031(490-511)Online publication date: 9-Apr-2024
https://doi.org/10.1109/SaTML59370.2024.00031
Liang ZWang H(2024)FedST: secure federated shapelet transformation for time series classificationThe VLDB Journal10.1007/s00778-024-00865-w33:5(1617-1641)Online publication date: 26-Jul-2024
https://doi.org/10.1007/s00778-024-00865-w
Levy BIshaq MSherman BKennard LMilanova AZikas VMeng WJensen CCremers CKirda E(2023)COMBINE: COMpilation and Backend-INdependent vEctorization for Multi-Party ComputationProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623181(2531-2545)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623181
Tang GPang BChen LZhang Z(2023)Efficient Lattice-Based Threshold Signatures With Functional InterchangeabilityIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.329340818(4173-4187)Online publication date: 2023
https://doi.org/10.1109/TIFS.2023.3293408
Wu PNing JHuang XLiu J(2023)Differentially Oblivious Two-Party Pattern Matching With Sublinear Round ComplexityIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2022.320675820:5(4101-4117)Online publication date: 1-Sep-2023
https://doi.org/10.1109/TDSC.2022.3206758
Koti NPatil SPatra ASuresh A(2023)MPClan: Protocol Suite for Privacy-Conscious ComputationsJournal of Cryptology10.1007/s00145-023-09469-z36:3Online publication date: 24-May-2023
https://dl.acm.org/doi/10.1007/s00145-023-09469-z
Belorgey MCarpov SDeforth KJetchev DSae-Tang AVuille MGama NKatz JLeontiadis IMohammadi M(2023)Manticore: A Framework for Efficient Multiparty Computation Supporting Real Number and Boolean ArithmeticJournal of Cryptology10.1007/s00145-023-09464-436:3Online publication date: 11-Jul-2023
https://doi.org/10.1007/s00145-023-09464-4
Furukawa JLindell YNof AWeinstein O(2023)High-Throughput Secure Three-Party Computation with an Honest MajorityJournal of Cryptology10.1007/s00145-023-09461-736:3Online publication date: 22-May-2023
https://dl.acm.org/doi/10.1007/s00145-023-09461-7
Wang CBater JNayak KMachanavajjhala AIves ZBonifati AEl Abbadi A(2022)IncShrink: Architecting Efficient Outsourced Databases using Incremental MPC and Differential PrivacyProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3526151(818-832)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3526151
Zhou XXu ZWang CGao MSalapura VZahran MChong FTang L(2022)PPMLACProceedings of the 49th Annual International Symposium on Computer Architecture10.1145/3470496.3527392(87-101)Online publication date: 18-Jun-2022
https://dl.acm.org/doi/10.1145/3470496.3527392
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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