To do or not to do: the dilemma of disclosing anonymized data

ABSTRACT

Decision makers of companies often face the dilemma of whether to release data for knowledge discovery, vis a vis the risk of disclosing proprietary or sensitive information. While there are various "sanitization" methods, in this paper we focus on anonymization, given its widespread use in practice. We give due diligence to the question of "just how safe the anonymized data is", in terms of protecting the true identities of the data objects. We consider both the scenarios when the hacker has no information, and more realistically, when the hacker may have partial information about items in the domain. We conduct our analyses in the context of frequent set mining. We propose to capture the prior knowledge of the hacker by means of a belief function, where an educated guess of the frequency of each item is assumed. For various classes of belief functions, which correspond to different degrees of prior knowledge, we derive formulas for computing the expected number of "cracks". While obtaining the exact values for the more general situations is computationally hard, we propose a heuristic called the O-estimate. It is easy to compute, and is shown to be accurate empirically with real benchmark datasets. Finally, based on the O-estimates, we propose a recipe for the decision makers to resolve their dilemma.

REFERENCES

• 1: Nabil R. Adam , John C. Worthmann, Security-control methods for statistical databases: a comparative study, ACM Computing Surveys (CSUR), v.21 n.4, p.515-556, Dec. 1989 [doi>10.1145/76894.76895]
• 2: Aggarwal C. C and Yu P. S. A Condensation Approach to Privacy Preserving Data Mining. EDBT, 2004.
• 3: Aggarwal. G et. al. Anonymizing Tables. ICDT Conference, 2005.
• 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: 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]
• 6: 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
• 7: Chris Clifton, Using sample size to limit exposure to data mining, Journal of Computer Security, v.8 n.4, p.281-307, Dec. 2000
• 8: Irit Dinur , Kobbi Nissim, Revealing information while preserving privacy, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.202-210, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773173]
• 9: Josep Domingo-Ferrer , Anna Oganian , Vicenç Torra, Information-Theoretic Disclosure Risk Measures in Statistical Disclosure Control of Tabular Data, Proceedings of the 14th International Conference on Scientific and Statistical Database Management, p.227-231, July 24-26, 2002 [doi>10.1109/SSDM.2002.1029724]
• 10: Alexandre Evfimievski , Ramakrishnan Srikant , Rakesh Agarwal , Johannes Gehrke, Privacy preserving mining of association rules, Information Systems, v.29 n.4, p.343-364, June 2004 [doi>10.1016/j.is.2003.09.001]
• 11: Fienberg S. E. et. al. Disclosure Limitation using perturbation and related methods for Categorical Data. Journal of Office Statistics, 14, 1998.
• 12: 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]
• 13: Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.712-721, July 2001, Hersonissos, Greece [doi>10.1145/380752.380877]
• 14: M. Jerrum and U. Vazirani. A mildly exponential approximation algorithm for the permanent. Algorithmica 16, 1996.
• 15: 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]
• 16: 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
• 17: Moore Jr. R. A. Controlled Data-Swapping Techniques for Masking Public Use Microdata Sets. Statistical Research Division Report Series, RR 96-04, US Bureau of Census, Washington D. C., 1996.
• 18: Krishnamurty Muralidhar , Rathindra Sarathy, Security of random data perturbation methods, ACM Transactions on Database Systems (TODS), v.24 n.4, p.487-493, Dec. 1999 [doi>10.1145/331983.331986]
• 19: Adam Meyerson , Ryan Williams, On the complexity of optimal K-anonymity, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055591]
• 20: 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]
• 21: Rasmussen L. E. Approximating the permanent: A simple approach. Random Structures and Algorithms, 5, 1994.
• 22: Samarati P. and Sweeney L. Protecting Privacy when Disclosing Information: k-anonymity and its Enforcement through Generalization and Suppression. IEEE Symposium on Research in Security and Privacy, 1998.
• 23: Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]
• 24: J. F. Traub , Y. Yemini , H. Woźniakowski, The statistical security of a statistical database, ACM Transactions on Database Systems (TODS), v.9 n.4, p.672-679, Dec. 1984 [doi>10.1145/1994.383392]
• 25: Valiant L. G. The Complexity of Computing the Permanent. Theoretical Computer Science, 8, 1979.
• 26: Vassilios S. Verykios , Ahmed K. Elmagarmid , Elisa Bertino , Yucel Saygin , Elena Dasseni, Association Rule Hiding, IEEE Transactions on Knowledge and Data Engineering, v.16 n.4, p.434-447, April 2004 [doi>10.1109/TKDE.2004.1269668]
• 27: Yang X. and Li C. Secure XML Publishing without Information Leakage in the Presence of Data Inference. VLDB Conference, 2004.