Take a look at the new version of this page: [ beta version ]. Tell us what you think.

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: Mikhail Atallah , Marina Bykova , Jiangtao Li , Keith Frikken , Mercan Topkara, Private collaborative forecasting and benchmarking, Proceedings of the 2004 ACM workshop on Privacy in the electronic society, October 28-28, 2004, Washington DC, USA [doi>10.1145/1029179.1029204]
• 2: Josh Daniel Cohen Benaloh, Verifiable secret-ballot elections, Yale University, New Haven, CT, 1987
• 3: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 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.
• 6: Justin Brickell , Donald E. Porter , Vitaly Shmatikov , Emmett Witchel, Privacy-preserving remote diagnostics, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315307]
• 7: Ivan Damgård , Mats Jurik, A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.119-136, February 13-15, 2001
• 8: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• 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 , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 12: Shafi Goldwasser, Multi party computations: past and present, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.1-6, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259405]
• 13: Somesh Jha , Louis Kruger , Vitaly Shmatikov, Towards Practical Privacy for Genomic Computation, Proceedings of the 2008 IEEE Symposium on Security and Privacy, p.216-230, May 18-21, 2008 [doi>10.1109/SP.2008.34]
• 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.
• 16: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 17: Dahlia Malkhi , Noam Nisan , Benny Pinkas , Yaron Sella, Fairplay—a secure two-party computation system, Proceedings of the 13th conference on USENIX Security Symposium, p.20-20, August 09-13, 2004, San Diego, CA
• 18: David Naccache , Jacques Stern, A new public key cryptosystem based on higher residues, Proceedings of the 5th ACM conference on Computer and communications security, p.59-66, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288106]
• 19: M. Naor, and B. Pinkas. Efficient Oblivious Transfer Protocols. Proceedings of the symposium on data structures and algorithms, 2001.
• 20: Moni Naor , Benny Pinkas , Reuban Sumner, Privacy preserving auctions and mechanism design, Proceedings of the 1st ACM conference on Electronic commerce, p.129-139, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337028]
• 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.
• 23: M. Rabin. How to exchange secrets by oblivious transfer. Technical Memo TR--81, Aiken Computation Laboratory, 1981.
• 24: Luigi Rizzo, Dummynet: a simple approach to the evaluation of network protocols, ACM SIGCOMM Computer Communication Review, v.27 n.1, p.31-41, Jan. 1997 [doi>10.1145/251007.251012]
• 25: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 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: Andrew C. Yao, Protocols for secure computations, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, p.160-164, November 03-05, 1982 [doi>10.1109/SFCS.1982.88]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

General Terms:
Experimentation, Measurement, Performance, Security

Keywords:
experimentation, performance measurement, secure multi-party computation, synchronization