20 August 2002 9:00-13:00
Target Audience ·
Data mining technology has emerged as a means of identifying patterns and trends from large quantities of data. One of the key requirements of a data mining project is access to the relevant data. Privacy and Security concerns can constrain such access, threatening to derail data mining projects. This tutorial discusses constraints imposed by privacy and security, and presents technical solutions that enable data mining projects to proceed without violating these constraints.
Privacy and security have been a concern since early in the age of automated data processing, and these issues were raised early in the data mining community [CM96]. There has recently been a surge in solutions to these issues [AS00, LP00, AA01, KC02, VC02]. The combination of growing use of data mining (leading to more conflict with privacy and security concerns), along with the growing number of technical solutions, makes the time ripe for a tutorial on the subject.
There are many data mining situations where these privacy and security issues arise. A few examples are:
Identifying public health problem outbreaks (e.g., epidemics, biological warfare instances). There are many data collectors (insurance companies, HMOs, public health agencies). Individual privacy concerns limit the willingness of the data custodians to share data, even with government agencies such as the U.S. Centers for Disease Control. Can we accomplish the desired results while still preserving privacy of individual entities?
Collaborative corporations or entities. Ford and Firestone shared a problem with a jointly produced product: Ford Explorers with Firestone tires. Ford and Firestone may have been able to use association rule techniques to detect problems earlier. This would have required extensive data sharing. Factors such as trade secrets and agreements with other manufacturers stand in the way of the necessary sharing. Could we obtain the same results, while still preserving the secrecy of each side's data? Government entities face similar problems, such as limitations on sharing between law enforcement, intelligence agencies, and tax collection.
Multi-national corporations. An individual country's legal system may prevent sharing of customer data between a subsidiary and its parent.
These examples each define a different problem, or set of problems. The problems can be characterized by the following three parameters:
What is the desired data mining result? Do we want to cluster the data, as in the disease outbreak example? Are we looking for association rules identifying relationships among the attributes? There are several such data mining tasks, and each poses a new set of challenges.
Control of Data
Who controls the data? Is each entity found only at a single site (as with medical insurance records)? Or do different sites contain different types of data (Ford on vehicles, Firestone on tires)?
What are the privacy requirements? If the concern is solely that values associated with an individual entity not be released (e.g., "personally identifiable information") we can develop techniques that provably protect such information. In other cases, the notion of "sensitive" may not be known in advance. This would lead to human vetting of the intermediate results.
Sometimes it may be difficult (or impossible) to develop an exact solution that meets the privacy constraints. In data mining an approximate solution is often sufficient. The goal, then, is to obtain a solution with bounded error.
The first half of this tutorial will discuss privacy and security constraints that are likely to affect data mining projects. The second half will introduce technical solutions to these problems: How to obtain data mining results without violating privacy, where "normal" data mining approaches would require a level of data access that violates privacy and security constraints.
This tutorial meets the needs of two audiences. Practitioners will learn to recognize when privacy and security concerns threaten to derail a data mining project. They will become able to develop alternative approaches that enable project completion while meeting privacy constraints. They will learn of technical solutions that enable those approaches, and of contacts within the research community who can develop new solutions where existing ones do not meet their needs.
Researchers will become familiar with the current state of research in this relatively new area. They will learn the constraints that lead to privacy and security problems with data mining, enabling them to identify new challenges and develop new solutions in this rapidly developing field.
Participants will need a general knowledge of data mining methods and techniques.
Examples of conflict between data mining and privacy, example of simple solution to one example (distributed association rules in horizontally partitioned distributed data where global access to individual values restricted).
Privacy and security
Individual privacy, Collection privacy, Limitations on use of results.
Sources of privacy and security
Regulatory, Contractual, Secrecy.
Classes of solutions:
Data obfuscation. Example: United States
Census Bureau Public Use Microdata [RAM96].
Summarization. Example: Statistical Queries [Den80].
Data separation. Horizontal vs. vertical partitioning of data. Example: Hospital records.
Part 1 summary and break:
When privacy concerns should be addressed, in terms of the CRoss Industry Standard Process for Data Mining (CRISP-DM). Articulating that data mining results rarely violate these concerns. The problem is for the data miners to obtain access to the data.
Setup for Part 2:
technical solutions to obtain data mining results in spite of limited data access.
Data obfuscation based
Developing reliable classifiers from unreliable data through reconstructing distributions. Method of [AS00].
Data separation based techniques:
Computing results without sharing data.
Overview of secure multiparty computation.
Definition of secure, semi-honest and malicious model. Brief overview
of the general two-party protocol [Yao86].
Secure decision tree construction. [LP00].
Secure association rules. Horizontally partitioned data [KC02], Vertically partitioned data [VC02].
Clifton, Associate Professor
Department of Computer Sciences
West Lafayette, Indiana 47907-1398 USA
+1 765-494-6005, Fax: +1 765 494-0739
Chris Clifton is an Associate Professor of Computer Science at Purdue University. He has a Ph.D. from Princeton University, and Bachelor's and Master's degrees from the Massachusetts Institute of Technology. Prior to joining Purdue in 2001, Chris had served as a Principal Scientist at The MITRE Corporation and as an Assistant Professor of Computer Science at Northwestern University. His research interests include data mining, data security, database support for text, and heterogeneous databases.
Dakshi Agrawal and Charu C. Aggarwal. On the design and quantification of privacy preserving data mining algorithms. In Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Santa Barbara, California, USA, May 21-23 2001. ACM.
Rakesh Agrawal and Ramakrishnan Srikant. Privacy-preserving data mining. In Proceedings of the 2000 ACM SIGMOD Conference on Management of Data, Dallas, TX, May 14-19 2000. ACM.
Chris Clifton and Don Marks. Security and privacy implications of data mining. In Workshop on Data Mining and Knowledge Discovery, pages 15-19, Montreal, Canada, June 2 1996. ACM SIGMOD.
Dorothy E. Denning. Secure statistical databases with random sample queries. ACM Transactions on Database Systems, 5(3):291-315, September 1980.
Murat Kantarcioglu and Chris Clifton. Distributed association rule mining without sharing. Submitted to Workshop on Research Issues on Data Mining and Knowledge Discovery (DMKD'02). ACM SIGMOD, June 2 2002.
Yehuda Lindell and Benny Pinkas. Privacy preserving data mining. In Advances in Cryptology - CRYPTO 2000, pages 36-54. Springer-Verlag, August 20-24 2000.
Jr. Richard A. Moore. Controlled data-swapping techniques for masking public use microdata sets. Statistical Research Division Report Series RR 96-04, U.S. Bureau of the Census, Washington, DC., 1996.
Jaideep Shrikant Vaidya and Chris Clifton. Privacy preserving association rule mining in vertically partitioned data. Submitted to The Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, July 23-26 2002.
Andrew C. Yao. How to generate and exchange secrets. In Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pages 162-167. IEEE, 1986.