Secure multi-party computation problems and their applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Secure multi-party computation problems and their applications: a review and open problems

Full text

Pdf (909 KB)

Source

New Security Paradigms Workshop archive
Proceedings of the 2001 workshop on New security paradigms table of contents

Cloudcroft, New Mexico

SESSION: Session 1: creative mathematics table of contents

Pages: 13 - 22

Year of Publication: 2001

ISBN:1-58113-457-6

Authors

Wenliang Du	Syracuse University, Syracuse, NY
Mikhail J. Atallah	Purdue University, West Lafayette, IN

Sponsor

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 96, Citation Count: 24

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/508171.508174 What is a DOI?

ABSTRACT

The growth of the Internet has triggered tremendous opportunities for cooperative computation, where people are jointly conducting computation tasks based on the private inputs they each supplies. These computations could occur between mutually untrusted parties, or even between competitors. For example, customers might send to a remote database queries that contain private information; two competing financial organizations might jointly invest in a project that must satisfy both organizations' private and valuable constraints, and so on. Today, to conduct such computations, one entity must usually know the inputs from all the participants; however if nobody can be trusted enough to know all the inputs, privacy will become a primary concern.This problem is referred to as Secure Multi-party Computation Problem (SMC) in the literature. Research in the SMC area has been focusing on only a limited set of specific SMC problems, while privacy concerned cooperative computations call for SMC studies in a variety of computation domains. Before we can study the problems, we need to identify and define the specific SMC problems for those computation domains. We have developed a framework to facilitate this problem-discovery task. Based on our framework, we have identified and defined a number of new SMC problems for a spectrum of computation domains. Those problems include privacy-preserving database query, privacy-preserving scientific computations, privacy-preserving intrusion detection, privacy-preserving statistical analysis, privacy-preserving geometric computations, and privacy-preserving data mining.The goal of this paper is not only to present our results, but also to serve as a guideline so other people can identify useful SMC problems in their own computation domains.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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	H. Kargupta, B. Park, D. Hershberger and, E. Johnson. Collective data mining: A new perspective toward distributed data mining. Advances in Distributed and Parallel Knowledge Discovery, 1999.
	3	Alberto Apostolico , Zvi Galil, Pattern matching algorithms, Oxford University Press, Oxford, 1997
	4	Joachim Biskup , Ulrich Flegel, On pseudonymization of audit data for intrusion detection, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.161-180, January 2001, Berkeley, California, United States
	5	Joachim Biskup , Ulrich Flegel, Transaction-Based Pseudonyms in Audit Data for Privacy Respecting Intrusion Detection, Proceedings of the Third International Workshop on Recent Advances in Intrusion Detection, p.28-48, October 02-04, 2000
	6	Christian Cachin, Efficient private bidding and auctions with an oblivious third party, Proceedings of the 6th ACM conference on Computer and communications security, p.120-127, November 01-04, 1999, Kent Ridge Digital Labs, Singapore [doi>10.1145/319709.319726]
	7	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]
	8	Gilles Brassard , Claude Crépeau , Jean-Marc Robert, All-or-nothing disclosure of secrets, Proceedings on Advances in cryptology---CRYPTO '86, p.234-238, January 1987, Santa Barbara, California, United States
	9	Maxime Crochemore , Wojciech Rytter, Text algorithms, Oxford University Press, Inc., New York, NY, 1994
	10	Yvo Desmedt, Some Recent Research Aspects of Threshold Cryptography, Proceedings of the First International Workshop on Information Security, p.158-173, September 17-19, 1997
	11	Wenliang Du and Mikhail 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 2000.
	12	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
	13	W. Du , M. Atallah, Privacy-Preserving Cooperative Statistical Analysis, Proceedings of the 17th Annual Computer Security Applications Conference, p.102, December 10-14, 2001
	14	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
	15	P. Gemmell. An introduction to threshold cryptography. In CryptoBytes, volume 2. RSA Laboratories, 1997.
	16	O. Goldreich. Secure multi-party computation (working draft). Available from http://www.wisdom.weizmann.ac.il/home/oded/public_html/foc.html, 1998.
	17	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]
	18	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]
	19	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
	20	Rafael C. Gonzalez , Richard E. Woods, Digital Image Processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
	21	M. S. Goodstadt and V. Gruson. The randomized response technique: A test on drug use. Journal of the American Statistical Association, 70(352):814-818, December 1975.
	22	Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
	23	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]
	24	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]
	25	Anil K. Jain, Fundamentals of digital image processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
	26	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
	27	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
	28	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]
	29	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
	30	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.
	31	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]
	32	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]
	33	K. H. Pollock and Y. Bek. A comparison of three randomized response models for quantitative data. Journal of the American Statistical Association, 71(356):994-886, December 1976.
	34	M. Rabin. How to exchange secrets by oblivious transfer. Technical Report Tech. Memo TR-81, Aiken Computation Laboratory, 1981.
	35	Bruce Schneier, Applied cryptography (2nd ed.): protocols, algorithms, and source code in C, John Wiley & Sons, Inc., New York, NY, 1995
	36	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]
	37	S. L. Warner. Randomized response: A surey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63-69, March 1965.
	38	S. L. Warner. Randomized response: A surey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 66(336):884-888, December 1971.
	39	A. C. Yao. Protocols for secure computations. In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, 1982.

CITED BY 24

	Shun-Dong Li , Yi-Qi Dai, Secure two-party computational geometry, Journal of Computer Science and Technology, v.20 n.2, p.258-263, March 2005
	Yong-Long Luo , Liu-Sheng Huang , Hong Zhong, Secure two-party point-circle inclusion problem, Journal of Computer Science and Technology, v.22 n.1, p.88-91, January 2007
	Yifei Yao , Yonglong Luo , Liusheng Huang , Weiwei Jing , Wei Yang , Weijiang Xu, Privacy-preserving technology and its applications in statistics measurements, Proceedings of the 2nd international conference on Scalable information systems, June 06-08, 2007, Suzhou, China
	Li Shundong , Wang Daoshun , Dai Yiqi , Luo Ping, Symmetric cryptographic solution to Yao's millionaires' problem and an evaluation of secure multiparty computations, Information Sciences: an International Journal, v.178 n.1, p.244-255, January, 2008
	Hillol Kargupta , Souptik Datta , Qi Wang , Krishnamoorthy Sivakumar, Random-data perturbation techniques and privacy-preserving data mining, Knowledge and Information Systems, v.7 n.4, p.387-414, May 2005
	Ashish P. Sanil , Alan F. Karr , Xiaodong Lin , Jerome P. Reiter, Privacy preserving regression modelling via distributed computation, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
	V. Kapoor , P. Poncelet , F. Trousset , M. Teisseire, Privacy preserving sequential pattern mining in distributed databases, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
	Jaideep Vaidya , Chris Clifton, Leveraging the "Multi" in secure multi-party computation, Proceedings of the 2003 ACM workshop on Privacy in the electronic society, October 30, 2003, Washington, DC
	Jaideep Vaidya , Chris Clifton, Privacy-preserving k-means clustering over vertically partitioned data, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
	Shibnath Mukherjee , Zhiyuan Chen , Aryya Gangopadhyay, A fuzzy programming approach for data reduction and privacy in distance-based mining, International Journal of Information and Computer Security, v.2 n.1, p.27-47, January 2008
	Michael E. Locasto , Angelos Stavrou , Angelos D. Keromytis, Dark application communities, Proceedings of the 2006 workshop on New security paradigms, September 19-22, 2006, Germany
	Jaideep Vaidya , Murat Kantarcıoğlu , Chris Clifton, Privacy-preserving Naïve Bayes classification, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.4, p.879-898, July 2008
	Stanley R. M. Oliveira , Osmar R. Zaïane, Privacy preserving frequent itemset mining, Proceedings of the IEEE international conference on Privacy, security and data mining, p.43-54, December 01, 2002, Maebashi City, Japan
	Jaideep Vaidya , Chris Clifton, Privacy preserving association rule mining in vertically partitioned data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
	Jaideep Vaidya , Chris Clifton , Murat Kantarcioglu , A. Scott Patterson, Privacy-preserving decision trees over vertically partitioned data, ACM Transactions on Knowledge Discovery from Data (TKDD), v.2 n.3, p.1-27, October 2008
	Stanley R. M. Oliveira , Osmar R. Zaiane, A unified framework for protecting sensitive association rules in business collaboration, International Journal of Business Intelligence and Data Mining, v.1 n.3, p.247-287, March 2006
	Mohamed F. Mokbel , Chi-Yin Chow , Walid G. Aref, The new Casper: query processing for location services without compromising privacy, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Ling Qiu , Yingjiu Li , Xintao Wu, Preserving privacy in association rule mining with bloom filters, Journal of Intelligent Information Systems, v.29 n.3, p.253-278, December 2007
	Stanley R. M. Oliveira , Osmar R. Zaïane, Foundations for an access control model for privacy preservation in multi-relational association rule mining, Proceedings of the IEEE international conference on Privacy, security and data mining, p.19-26, December 01, 2002, Maebashi City, Japan
	Janak J. Parekh , Ke Wang , Salvatore J. Stolfo, Privacy-preserving payload-based correlation for accurate malicious traffic detection, Proceedings of the 2006 SIGCOMM workshop on Large-scale attack defense, p.99-106, September 11-15, 2006, Pisa, Italy
	Wenliang Du , Zhijun Zhan, A practical approach to solve Secure Multi-party Computation problems, Proceedings of the 2002 workshop on New security paradigms, September 23-26, 2002, Virginia Beach, Virginia
	Shibnath Mukherjee , Madhushri Banerjee , Zhiyuan Chen , Aryya Gangopadhyay, A privacy preserving technique for distance-based classification with worst case privacy guarantees, Data & Knowledge Engineering, v.66 n.2, p.264-288, August, 2008
	Maurizio Atzori , Francesco Bonchi , Fosca Giannotti , Dino Pedreschi, Anonymity preserving pattern discovery, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.4, p.703-727, July 2008
	Kirsten Wahlstrom , Gerald Quirchmayr, The motivation and proposition of a privacy-enhancing architecture for operational databases, Proceedings of the fifth Australasian symposium on ACSW frontiers, January 30-February 02, 2007, Ballarat, Australia