Preserving data privacy in outsourcing data aggregation services

ABSTRACT

Advances in distributed service-oriented computing and Internet technology have formed a strong technology push for outsourcing and information sharing. There is an increasing need for organizations to share their data across organization boundaries both within the country and with countries that may have lesser privacy and security standards. Ideally, we wish to share certain statistical data and extract the knowledge from the private databases without revealing any additional information of each individual database apart from the aggregate result that is permitted. In this article, we describe two scenarios for outsourcing data aggregation services and present a set of decentralized peer-to-peer protocols for supporting data sharing across multiple private databases while minimizing the data disclosure among individual parties. Our basic protocols include a set of novel probabilistic computation mechanisms for important primitive data aggregation operations across multiple private databases such as max, min, and top k selection. We provide an analytical study of our basic protocols in terms of precision, efficiency, and privacy characteristics. Our advanced protocols implement an efficient algorithm for performing kNN classification across multiple private databases. We provide a set of experiments to evaluate the proposed protocols in terms of their correctness, efficiency, and privacy characteristics.

REFERENCES

• 1: Aggarwal, G., Bawa, M., Ganesan, P., Garcia-Molina, H., Kenthapadi, K., Motwani, R., Srivastava, U., Thomas, D., and Xu, Y. 2005. Two can keep a secret: A distributed architecture for secure database services. Conference on Innovative Data Systems Research (CIDR).
• 2: Aggarwal, G., Mishra, N., and Pinkas, B. 2004. Secure computation of the kth ranked element. IACR Conference on Eurocryption.
• 3: Dakshi Agrawal , Charu C. Aggarwal, On the design and quantification of privacy preserving data mining algorithms, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.247-255, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375602]
• 4: Rakesh Agrawal , Paul Bird , Tyrone Grandison , Jerry Kiernan , Scott Logan , Walid Rjaibi, Extending Relational Database Systems to Automatically Enforce Privacy Policies, Proceedings of the 21st International Conference on Data Engineering, p.1013-1022, April 05-08, 2005 [doi>10.1109/ICDE.2005.64]
• 5: Rakesh Agrawal , Alexandre Evfimievski , Ramakrishnan Srikant, Information sharing across private databases, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872771]
• 6: Rakesh Agrawal , Jerry Kiernan , Ramakrishnan Srikant , Yirong Xu, Hippocratic databases, Proceedings of the 28th international conference on Very Large Data Bases, p.143-154, August 20-23, 2002, Hong Kong, China
• 7: Rakesh Agrawal , Jerry Kiernan , Ramakrishnan Srikant , Yirong Xu, Order preserving encryption for numeric data, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007632]
• 8: Mayank Bawa , Roberto J. Bayardo, Jr. , Rakesh Agrawal, Privacy-preserving indexing of documents on the network, Proceedings of the 29th international conference on Very large data bases, p.922-933, September 09-12, 2003, Berlin, Germany
• 9: Elisa Bertino , Beng Chin Ooi , Yanjiang Yang , Robert H. Deng, Privacy and Ownership Preserving of Outsourced Medical Data, Proceedings of the 21st International Conference on Data Engineering, p.521-532, April 05-08, 2005 [doi>10.1109/ICDE.2005.111]
• 10: Matt Blaze , Joan Feigenbaum , Jack Lacy, Decentralized Trust Management, Proceedings of the 1996 IEEE Symposium on Security and Privacy, p.164, May 06-08, 1996
• 11: Proceedings of the IEEE international conference on Privacy, security and data mining, December 2002
• 12: Clifton, C., Kantarcioglu, M., Lin, X., Vaidya, J., and Zhu, M. 2003. Tools for privacy preserving distributed data mining. SIGKDD Explorations.
• 13: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 14: AnHai Doan , Alon Y. Halevy, Semantic-integration research in the database community, AI Magazine, v.26 n.1, p.83-94, March 2005
• 15: Ahmed Elmagarmid , Marek Rusinkiewicz , Amit Sheth, Management of heterogeneous and autonomous database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 16: Garcia-Molina, H., Ullman, J. D., and Widom, J. D. 2001. Information Integration, Chapter 20. Prentice Hall.
• 17: Goldreich, O. 2001. Secure multi-party computation. Working Draft, version 1.3.
• 18: Hakan Hacigümüş , Bala Iyer , Chen Li , Sharad Mehrotra, Executing SQL over encrypted data in the database-service-provider model, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564717]
• 19: Providing Database as a Service, Proceedings of the 18th International Conference on Data Engineering, p.29, February 26-March 01, 2002
• 20: Alon Y. Halevy , Naveen Ashish , Dina Bitton , Michael Carey , Denise Draper , Jeff Pollock , Arnon Rosenthal , Vishal Sikka, Enterprise information integration: successes, challenges and controversies, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066246]
• 21: Hore, B., Mehrotra, S., and Tsudik, G. 1997. A privacy-preserving index for range queries. ACM Symposium on Principles of Distributed Computing.
• 22: Sushil Jajodia , Ravi Sandhu, Toward a multilevel secure relational data model, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.50-59, May 29-31, 1991, Denver, Colorado, United States
• 23: Murat Kantarcioglu , Chris Clifton, Privacy-Preserving Distributed Mining of Association Rules on Horizontally Partitioned Data, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1026-1037, September 2004 [doi>10.1109/TKDE.2004.45]
• 24: Kantarcioglu, M. and Clifton, C. 2004b. Security issues in querying encrypted data. Tech. rep. TR-04-013, Purdue University.
• 25: Kantarcioglu, M. and Clifton, C. 2005. Privacy preserving k-nn classifier. International Conference on Data Engineering (ICDE).
• 26: Kantarcoglu, M. and Vaidya, J. 2003. Privacy preserving naive Bayes classifier for horizontally partitioned data. IEEE ICDM Workshop on Privacy Preserving Data Mining.
• 27: Lindell, Y. and Pinkas, B. 2002. Privacy preserving data mining. J. Crypto. 15, 3.
• 28: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 29: Markey, E. J. 2005. Outsourcing privacy: Countries processing U.S. social security numbers, health information, tax records lack fundamental privacy safeguards. A staff report prepared at the request of Edward J. Markey, U.S. House of Representatives.
• 30: Michael K. Reiter , Aviel D. Rubin, Crowds: anonymity for Web transactions, ACM Transactions on Information and System Security (TISSEC), v.1 n.1, p.66-92, Nov. 1998 [doi>10.1145/290163.290168]
• 31: Paul F. Syverson , David M. Goldschlag , Michael G. Reed, Anonymous Connections and Onion Routing, Proceedings of the 1997 IEEE Symposium on Security and Privacy, p.44, May 04-07, 1997
• 32: 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 [doi>10.1145/775047.775142]
• 33: 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. [doi>10.1145/956750.956776]
• 34: 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. [doi>10.1145/956750.956776]
• 35: Jaideep Vaidya , Chris Clifton, Privacy-Preserving Top-k Queries, Proceedings of the 21st International Conference on Data Engineering, p.545-546, April 05-08, 2005 [doi>10.1109/ICDE.2005.112]
• 36: Wang, K., Fung, B. C. M., and Dong, G. 2005. Integrating private databases for data analysis. IEEE Intelligence and Security Informatics Conference (ISI).
• 37: Matthew Wright , Micah Adler , Brian N. Levine , Clay Shields, Defending Anonymous Communications Against Passive Logging Attacks, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.28, May 11-14, 2003
• 38: Li Xiao , Zhichen Xu , Xiaodong Zhang, Mutual Anonymity Protocols for Hybrid Peer-to-Peer Systems, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.68, May 19-22, 2003
• 39: Li Xiong , Subramanyam Chitti , Ling Liu, Topk Queries across Multiple Private Databases, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.145-154, June 06-10, 2005 [doi>10.1109/ICDCS.2005.82]
• 40: PeerTrust: Supporting Reputation-Based Trust for Peer-to-Peer Electronic Communities, IEEE Transactions on Knowledge and Data Engineering, v.16 n.7, p.843-857, July 2004 [doi>10.1109/TKDE.2004.1318566]
• 41: Sheng Zhong , Zhiqiang Yang , Rebecca N. Wright, Privacy-enhancing k-anonymization of customer data, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065185]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Algorithms, Design, Experimentation

Keywords:
Privacy, classification, confidentiality, outsourcing