research-article

On the practical importance of communication complexity for secure multi-party computation protocols

Authors:

Florian Kerschbaum,

Daniel Dahlmeier,

Axel Schröpfer,

Debmalya BiswasAuthors Info & Claims

SAC '09: Proceedings of the 2009 ACM symposium on Applied Computing

Pages 2008 - 2015

https://doi.org/10.1145/1529282.1529730

Published: 08 March 2009 Publication History

Abstract

Many advancements in the area of Secure Multi-Party Computation (SMC) protocols use improvements in communication complexity as a justification. We conducted an experimental study of a specific protocol for a real-world sized problem under realistic conditions and it suggests that the practical performance of the protocol is almost independent of the network performance. We argue that our result can be generalized to a whole class of SMC protocols.

References

[1]

M. Atallah, M. Bykova, J. Li, K. Frikken, and M. Topkara. Private Collaborative Forecasting and Benchmarking. Proceedings of the ACM Workshop on Privacy in an Electronic Society, 2004.

Digital Library

[2]

J. Benaloh. Verifiable Secret-Ballot Elections. PhD thesis, Yale University, 1987.

Digital Library

[3]

M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. Proceedings of the 20th ACM symposium on theory of computing, 1988.

Digital Library

[4]

P. Bogetoft, D. Christensen, I. Damgard, M. Geisler, T. Jakobsen, M. Kroigaard, J. Nielsen, J. Nielsen, K. Nielsen, J. Pagter, M. Schwartzbach and T. Toft. Multiparty Computation Goes Live. Available at http://eprint.iacr.org/2008/068, 2008.

[5]

P. Bogetoft, I. Damgard, T. Jakobsen, K. Nielsen, J. Pagter, and T. Toft. A Practical Implementation of Secure Auctions Based on Multiparty Integer Computation. Proceedings of Financial Cryptography, 2006.

Digital Library

[6]

J. Brickell, D. Porter, V. Shmatikov, E. Witchel. Privacy-Preserving Remote Diagnostics. Proceedings of the 14th ACM Conference on Computer and Communications Security, 2007.

Digital Library

[7]

I. Damgard, and M. Jurik. A Generalisation, a Simplification and some Applications of Pailliers Probabilistic Public-Key System. Proceedings of International Conference on Theory and Practice of Public-Key Cryptography, 2001.

Digital Library

[8]

S. Even, O. Goldreich, and A. Lempel. A randomized protocol for signing contracts. Communications of the ACM 28(6), 1985.

Digital Library

[9]

J. Feigenbaum, B. Pinkas, R. Ryger, and F. Saint-Jean. Secure Computation of Surveys. Proceedings of the EU Workshop on Secure Multiparty Protocols, 2004. Available at http://www.cs.yale.edu/homes/jf/SMP2004.pdf.

[10]

O. Goldreich. Secure Multi-party Computation. Available at www.wisdom.weizmann.ac.il/~oded/pp.html, 2002.

[11]

O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. Proceedings of the 19th ACM conference on theory of computing, 1987.

Digital Library

[12]

S. Goldwasser. Multi party computations: past and present. Proceedings of the 16th ACM symposium on principles of distributed computing, 1997.

Digital Library

[13]

S. Jha, L. Kruger, and V. Shmatikov. Towards Practical Privacy for Genomic Computation. Proceedings of the IEEE Symposium on Security and Privacy, 2008.

Digital Library

[14]

F. Kerschbaum. Practical Privacy-Preserving Benchmarking. Proceedings of the 23rd IFIP International Information Security Conference, 2008.

[15]

F. Kerschbaum, and O. Terzidis. Filtering for Private Collaborative Benchmarking. Proceedings of the International Conference on Emerging Trends in Information and Communication Security, 2006.

Digital Library

[16]

N. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, 1996.

Digital Library

[17]

D. Malkhi, N. Nisan, B. Pinkas, and Y. Sella. Fairplay - A Secure Two-party Computation System. Proceedings of the USENIX security symposium, 2004.

Digital Library

[18]

D. Naccache, and J. Stern. A New Public-Key Cryptosystem Based on Higher Residues. Proceedings of the ACM Conference on Computer and Communications Security, 1998.

Digital Library

[19]

M. Naor, and B. Pinkas. Efficient Oblivious Transfer Protocols. Proceedings of the symposium on data structures and algorithms, 2001.

Digital Library

[20]

M. Naor, B. Pinkas and R. Sumner. Privacy Preserving Auctions and Mechanism Design. Proceedings of the 1st ACM Conference on Electronic Commerce, 1999.

Digital Library

[21]

T. Okamoto, and S. Uchiyama. A new public-key cryptosystem as secure as factoring. Proceedings of EUROCRYPT, 1998.

[22]

P. Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. Proceedings of EUROCRYPT, 1999.

Digital Library

[23]

M. Rabin. How to exchange secrets by oblivious transfer. Technical Memo TR--81, Aiken Computation Laboratory, 1981.

[24]

L. Rizzo. Dummynet: a simple approach to the evaluation of network protocols. ACM Computer Communication Review 27(1), 1997.

Digital Library

[25]

A. Shamir. How to share a secret. Communications of the ACM 22(11), 1979.

Digital Library

[26]

R. Sion, B. Carbunar. On the Computational Practicality of Private Information Retrieval. em Proceedings of the Network and Distributed System Security Symposium, 2007.

[27]

A. Yao. Protocols for Secure Computations. Proceedings of the IEEE Symposium on foundations of computer science 23, 1982.

Digital Library

Cited By

Gupta DBhatt SBhatt PGupta MTosun A(2022)Game Theory Based Privacy Preserving Approach for Collaborative Deep Learning in IoTDeep Learning for Security and Privacy Preservation in IoT10.1007/978-981-16-6186-0_8(127-149)Online publication date: 4-Apr-2022
https://doi.org/10.1007/978-981-16-6186-0_8
Gupta DKayode OBhatt SGupta MTosun A(2020)Learner’s Dilemma: IoT Devices Training Strategies in Collaborative Deep Learning2020 IEEE 6th World Forum on Internet of Things (WF-IoT)10.1109/WF-IoT48130.2020.9221446(1-6)Online publication date: Jun-2020
https://doi.org/10.1109/WF-IoT48130.2020.9221446
Liu JWang ZShu MZhang FLeng SSun X(2019)Secure Communication of Fractional Complex Chaotic Systems Based on Fractional Difference Function SynchronizationComplexity10.1155/2019/72427912019Online publication date: 18-Aug-2019
https://dl.acm.org/doi/10.1155/2019/7242791
Show More Cited By

Index Terms

On the practical importance of communication complexity for secure multi-party computation protocols
1. Security and privacy
  1. Cryptography
  2. Systems security
    1. Operating systems security
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles
        Organizing principles for web applications

Recommendations

On the Communication Complexity of Secure Multi-Party Computation With Aborts
PODC '24: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing

A central goal of cryptography is Secure Multi-party Computation (MPC), where n parties desire to compute a function of their joint inputs without letting any party learn about the inputs of its peers. Unfortunately, it is well-known that MPC ...
Secure Multi-Party Computation without Agreement

It has recently been shown that authenticated Byzantine agreement, in which more than a third of the parties are corrupted, cannot be securely realized under concurrent or parallel (stateless) composition. This result puts into question any usage of ...
An efficient fair UC-secure protocol for two-party computation

With the development of modern Internet and mobile networks, there is an increasing need for collaborative privacy-preserving applications. Secure multi-party computation SMPC gives a general solution to these applications and has become a hot topic. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '09: Proceedings of the 2009 ACM symposium on Applied Computing

March 2009

2347 pages

ISBN:9781605581668

DOI:10.1145/1529282

Conference Chairs:
Sung Y. Shin
South Dakota State University, United States
,
Sascha Ossowski
University Rey Juan Carlos, Spain

Copyright © 2009 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

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 March 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SAC09

Sponsor:

SIGAPP

SAC09: The 2009 ACM Symposium on Applied Computing

March 8, 2009 - March 12, 2008

Hawaii, Honolulu

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
309
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gupta DBhatt SBhatt PGupta MTosun A(2022)Game Theory Based Privacy Preserving Approach for Collaborative Deep Learning in IoTDeep Learning for Security and Privacy Preservation in IoT10.1007/978-981-16-6186-0_8(127-149)Online publication date: 4-Apr-2022
https://doi.org/10.1007/978-981-16-6186-0_8
Gupta DKayode OBhatt SGupta MTosun A(2020)Learner’s Dilemma: IoT Devices Training Strategies in Collaborative Deep Learning2020 IEEE 6th World Forum on Internet of Things (WF-IoT)10.1109/WF-IoT48130.2020.9221446(1-6)Online publication date: Jun-2020
https://doi.org/10.1109/WF-IoT48130.2020.9221446
Liu JWang ZShu MZhang FLeng SSun X(2019)Secure Communication of Fractional Complex Chaotic Systems Based on Fractional Difference Function SynchronizationComplexity10.1155/2019/72427912019Online publication date: 18-Aug-2019
https://dl.acm.org/doi/10.1155/2019/7242791
Sobati-Moghadam SFayoumi A(2018)Private Collaborative Business Benchmarking in the CloudIntelligent Computing10.1007/978-3-030-01177-2_101(1359-1365)Online publication date: 2-Nov-2018
https://doi.org/10.1007/978-3-030-01177-2_101
von Maltitz MCarle G(2018)A Performance and Resource Consumption Assessment of Secret Sharing Based Secure Multiparty ComputationData Privacy Management, Cryptocurrencies and Blockchain Technology10.1007/978-3-030-00305-0_25(357-372)Online publication date: 7-Sep-2018
https://doi.org/10.1007/978-3-030-00305-0_25
Tueno AKerschbaum FBernau DForesti S(2017)Selective access for supply chain management in the cloud2017 IEEE Conference on Communications and Network Security (CNS)10.1109/CNS.2017.8228710(476-482)Online publication date: Oct-2017
https://doi.org/10.1109/CNS.2017.8228710
Kerschbaum FHärterich M(2017)Searchable Encryption to Reduce Encryption Degradation in Adjustably Encrypted DatabasesData and Applications Security and Privacy XXXI10.1007/978-3-319-61176-1_18(325-336)Online publication date: 22-Jun-2017
https://doi.org/10.1007/978-3-319-61176-1_18
Böhler JBernau DKerschbaum F(2017)Privacy-Preserving Outlier Detection for Data StreamsData and Applications Security and Privacy XXXI10.1007/978-3-319-61176-1_12(225-238)Online publication date: 22-Jun-2017
https://doi.org/10.1007/978-3-319-61176-1_12
Fuhry BTighzert WKerschbaum FPayer MMangard SWeippl EKatzenbeisser SAndroulaki EReiter M(2016)Encrypting Analytical Web ApplicationsProceedings of the 2016 ACM on Cloud Computing Security Workshop10.1145/2996429.2996438(35-46)Online publication date: 28-Oct-2016
https://dl.acm.org/doi/10.1145/2996429.2996438
Kerschbaum FLim H(2015)Privacy-Preserving Observation in Public SpacesComputer Security -- ESORICS 201510.1007/978-3-319-24177-7_5(81-100)Online publication date: 18-Nov-2015
https://doi.org/10.1007/978-3-319-24177-7_5
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents