A practical approach to solve Secure Multi-party Computation problems

ABSTRACT

Secure Multi-party Computation (SMC) problems deal with the following situation: Two (or many) parties want to jointly perform a computation. Each party needs to contribute its private input to this computation, but no party should disclose its private inputs to the other parties, or to any third party. With the proliferation of the Internet, SMC problems becomes more and more important. So far no practical solution has emerged, largely because SMC studies have been focusing on zero information disclosure, an ideal security model that is expensive to achieve.Aiming at developing practical solutions to SMC problems, we propose a new paradigm, in which we use an acceptable security model that allows partial information disclosure. Our conjecture is that by lowering the restriction on the security, we can achieve a much better performance. The paradigm is motivated by the observation that in practice people do accept a less secure but much more efficient solution because sometimes disclosing information about their private data to certain degree is a risk that many people would rather take if the performance gain is so significant. Moreover, in our paradigm, the security is adjustable, such that users can adjust the level of security based on their definition of the acceptable security. We have developed a number of techniques under this new paradigm, and are currently conducting extensive studies based on this new paradigm.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 2: Mikhail J. Atallah , Wenliang Du, Secure Multi-party Computational Geometry, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.165-179, August 08-10, 2001
• 3: M. J. Atallah, F. Kerschbaum, and W. Du. Private file comparision. Technical report, Purdue University, 2001.
• 4: Donald Beaver, Commodity-based cryptography (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.446-455, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258637]
• 5: Donald Beaver, Server-assisted cryptography, Proceedings of the 1998 workshop on New security paradigms, p.92-106, September 22-26, 1998, Charlottesville, Virginia, United States [doi>10.1145/310889.310923]
• 6: C. Cachin, S. Micali, and M. Stadler. Computationally private information retrieval with polylogarithmic communication. Advances in Cryptology: EUROCRYPT '99, Lecture Notes in Computer Science, 1592:402--414, 1999.
• 7: Ran Canetti , Yuval Ishai , Ravi Kumar , Michael K. Reiter , Ronitt Rubinfeld , Rebecca N. Wright, Selective private function evaluation with applications to private statistics, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.293-304, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384047]
• 8: Benny Chor , Niv Gilboa, Computationally private information retrieval (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.304-313, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258609]
• 9: B. Chor , O. Goldreich , E. Kushilevitz , M. Sudan, Private information retrieval, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.41, October 23-25, 1995
• 10: Giovanni Di-Crescenzo , Yuval Ishai , Rafail Ostrovsky, Universal service-providers for database private information retrieval (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.91-100, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277713]
• 11: Wenliang Du , Mikhail J. Atallah , Eugene H. Spafford, A study of several specific secure two-party computation problems, 2001
• 12: W. Du and M. J. Atallah. Protocols for secure remote database access with approximate matching. In 7th ACM Conference on Computer and Communications Security (ACMCCS 2000), The First Workshop on Security and Privacy in E-Commerce, Athens, Greece, November 1--4 2000.
• 13: Wenliang Du , Mikhail J. Atallah, Privacy-Preserving Cooperative Scientific Computations, Proceedings of the 14th IEEE Workshop on Computer Security Foundations, p.273, June 11-13, 2001
• 14: W. Du , M. Atallah, Privacy-Preserving Cooperative Statistical Analysis, Proceedings of the 17th Annual Computer Security Applications Conference, p.102, December 10-14, 2001
• 15: Wenliang Du , Mikhail J. Atallah, Secure multi-party computation problems and their applications: a review and open problems, Proceedings of the 2001 workshop on New security paradigms, September 10-13, 2001, Cloudcroft, New Mexico [doi>10.1145/508171.508174]
• 16: Yael Gertner , Shafi Goldwasser , Tal Malkin, A Random Server Model for Private Information Retrieval or How to Achieve Information Theoretic PIR Avoiding Database Replication, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.200-217, October 08-10, 1998
• 17: Yael Gertner , Yuval Ishai , Eyal Kushilevitz , Tal Malkin, Protecting data privacy in private information retrieval schemes, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.151-160, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276723]
• 18: O. Goldreich. Secure multi-party computation (working draft). Available from http://www.wisdom.weizmann, ac.il/home/oded/public_html/foc.html, 1998.
• 19: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 20: 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]
• 21: Yuval Ishai , Eyal Kushilevitz, Improved upper bounds on information-theoretic private information retrieval (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.79-88, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301275]
• 22: E. Kushilevitz , R. Ostrovsky, Replication is not needed: single database, computationally-private information retrieval, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.364, October 19-22, 1997
• 23: Yehuda Lindell , Benny Pinkas, Privacy Preserving Data Mining, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.36-54, August 20-24, 2000
• 24: Moni Naor , Benny Pinkas, Oblivious transfer and polynomial evaluation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.245-254, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301312]
• 25: A. C. Yao. Protocols for secure computations. In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, 1982.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Electronic data interchange (EDI)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Information flow controls

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Privacy

General Terms:
Experimentation, Performance, Security

Keywords:
privacy, secure multi-party computation, security