Randomization in privacy preserving data mining

ABSTRACT

Suppose there are many clients, each having some personal information, and one server, which is interested only in aggregate, statistically significant, properties of this information. The clients can protect privacy of their data by perturbing it with a randomization algorithm and then submitting the randomized version. The randomization algorithm is chosen so that aggregate properties of the data can be recovered with sufficient precision, while individual entries are significantly distorted. How much distortion is needed to protect privacy can be determined using a privacy measure. Several possible privacy measures are known; finding the best measure is an open question. This paper presents some methods and results in randomization for numerical and categorical data, and discusses the issue of measuring privacy.

REFERENCES

• 1: 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]
• 2: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 4: 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
• 5: L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. CRC Press, Boca Raton, Florida, USA, 1984.
• 6: Chris Clifton , Murat Kantarcioglu , Jaideep Vaidya , Xiaodong Lin , Michael Y. Zhu, Tools for privacy preserving distributed data mining, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.28-34, December 2002 [doi>10.1145/772862.772867]
• 7: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal statistical Society, Series B, 39:1--38, 1977.
• 8: George Duncan , Ramayya Krishnan , Rema Padman, Cell Suppression to Limit Content-Based Disclosure, Proceedings of the 30th Hawaii International Conference on System Sciences: Information System Track-Organizational Systems and Technology, p.552, January 03-06, 1997
• 9: G. T. Duncan and S. Mukherjee. Optimal disclosure limitation strategy in statistical databases: Deterring tracker attacks through additive noise. Journal of the American Statistical Association, 95(451):720--729, 2000.
• 10: T. Evans, L. Zayatz, and J. Slanta. Using noise for disclosure limitation of establishment tabular data. Journal of Official Statistics, 14(4):537--551, 1998.
• 11: Alexandre Evfimievski , Ramakrishnan Srikant , Rakesh Agrawal , Johannes Gehrke, Privacy preserving mining of association rules, 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.775080]
• 12: S. E. Fienberg, U. E. Makov, and R. J. Steele. Disclosure limitation using perturbation and related methods for categorical data. Journal of Official Statistics, 14(4):485--502, 1998.
• 13: J. M. Gouweleeuw, P. Kooiman, L. C. R. J. Willenborg, and P.-P. de Wolf. Post randomisation for statistical disclosure control: Theory and implementation. Journal of Official Statistics, 14(4):463--478, 1998.
• 14: Vijay S. Iyengar, Transforming data to satisfy privacy constraints, 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.775089]
• 15: J. J. Kim and W. E. Winkler. Masking microdata files, 1995.
• 16: Jon Kleinberg , Christos H. Papadimitriou , Prabhakar Raghavan, On the value of private information, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
• 17: D. Lambert. Measures of disclosure risk and harm. Journal of Official Statistics, 9(2):313--331, 1993.
• 18: R. J. A. Little. Statistical analysis of masked data. Journal of Official Statistics, 9(2):407--426, 1993.
• 19: G. J. McLachlan and T. Krishnan. The EM Algorithm and Extensions. Wiley-Interscience, November 1996. 304 pp.
• 20: Sumitra Mukherjee , George T. Duncan, Disclosure Limitation through Additive Noise Data Masking: Analysis of Skewed Sensitive Data, Proceedings of the 30th Hawaii International Conference on System Sciences: Information System Track-Organizational Systems and Technology, p.581, January 03-06, 1997
• 21: Benny Pinkas, Cryptographic techniques for privacy-preserving data mining, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.12-19, December 2002 [doi>10.1145/772862.772865]
• 22: S. J. Rizvi and J. R. Haritsa. Maintaining data privacy in association rule mining. In Proceedings of the 28th International Conference on Very Large Data Bases, Hong Kong, China, August 2002.
• 23: Pierangela Samarati , Latanya Sweeney, Generalizing data to provide anonymity when disclosing information (abstract), Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.188, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275508]
• 24: P. Samarati and L. Sweeney. Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression. In Proceedings of the IEEE Symposium on Research in Security and Privacy, Oakland, California, USA, May 1998.
• 25: C. E. Shannon. Communication theory of secrecy systems. Bell System Technical Journal, 28--4:656--715, 1949.
• 26: Claude E. Shannon , Warren Weaver, A Mathematical Theory of Communication, University of Illinois Press, Champaign, IL, 1963
• 27: L. Zayatz, R. Moore, and B. T. Evans. New directions in disclosure limitation at the census bureau. In Proceedings of the Government Statistics Section, Joint Statistical Meetings. American Statistical Association, 1996.