On the tradeoff between privacy and utility in data publishing

ABSTRACT

In data publishing, anonymization techniques such as generalization and bucketization have been designed to provide privacy protection. In the meanwhile, they reduce the utility of the data. It is important to consider the tradeoff between privacy and utility. In a paper that appeared in KDD 2008, Brickell and Shmatikov proposed an evaluation methodology by comparing privacy gain with utility gain resulted from anonymizing the data, and concluded that "even modest privacy gains require almost complete destruction of the data-mining utility". This conclusion seems to undermine existing work on data anonymization. In this paper, we analyze the fundamental characteristics of privacy and utility, and show that it is inappropriate to directly compare privacy with utility. We then observe that the privacy-utility tradeoff in data publishing is similar to the risk-return tradeoff in financial investment, and propose an integrated framework for considering privacy-utility tradeoff, borrowing concepts from the Modern Portfolio Theory for financial investment. Finally, we evaluate our methodology on the Adult dataset from the UCI machine learning repository. Our results clarify several common misconceptions about data utility and provide data publishers useful guidelines on choosing the right tradeoff between privacy and utility.

REFERENCES

• 1: Charu C. Aggarwal, On k-anonymity and the curse of dimensionality, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 2: A. Asuncion and D. Newman. UCI machine learning repository, 2007.
• 3: M. Barbaro and T. Z. Jr. A face is exposed for aol searcher no. 4417749. New York Times, 2006.
• 4: Roberto J. Bayardo , Rakesh Agrawal, Data Privacy through Optimal k-Anonymization, Proceedings of the 21st International Conference on Data Engineering, p.217-228, April 05-08, 2005 [doi>10.1109/ICDE.2005.42]
• 5: Justin Brickell , Vitaly Shmatikov, The cost of privacy: destruction of data-mining utility in anonymized data publishing, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401904]
• 6: G. T. Duncan and D. Lambert. Disclosure-limited data dissemination. J. Am. Stat. Assoc., pages 10--28, 1986.
• 7: C. Dwork. Differential privacy. In ICALP, pages 1--12, 2006.
• 8: E. Elton and M. Gruber. Modern Portfolio Theory and Investment Analysis. John Wiley&Sons Inc, 1995.
• 9: B. C. M. Fung, K. Wang, R. Chen, and P. S. Yu. Privacy-preserving data publishing: A survey on recent developments. ACM Computing Survey, 2009.
• 10: Benjamin C. M. Fung , Ke Wang , Philip S. Yu, Top-Down Specialization for Information and Privacy Preservation, Proceedings of the 21st International Conference on Data Engineering, p.205-216, April 05-08, 2005 [doi>10.1109/ICDE.2005.143]
• 11: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 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: Daniel Kifer , Johannes Gehrke, Injecting utility into anonymized datasets, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142499]
• 14: N. Koudas, D. Srivastava, T. Yu, and Q. Zhang. Aggregate query answering on anonymized tables. In ICDE, pages 116--125, 2007.
• 15: S. L. Kullback and R. A. Leibler. On information and sufficiency. Ann. Math. Stat., 22:79--86, 1951.
• 16: D. Lambert. Measures of disclosure risk and harm. J. Official Stat., 9:313--331, 1993.
• 17: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Mondrian Multidimensional K-Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.25, April 03-07, 2006 [doi>10.1109/ICDE.2006.101]
• 18: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Workload-aware anonymization, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150435]
• 19: N. Li, T. Li, and S. Venkatasubramanian. t-closeness: Privacy beyond k-anonymity and l-diversity. In ICDE, pages 106--115, 2007.
• 20: Tiancheng Li , Ninghui Li, Injector: Mining Background Knowledge for Data Anonymization, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.446-455, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497453]
• 21: Ashwin Machanavajjhala , Johannes Gehrke , Daniel Kifer , Muthuramakrishnan Venkitasubramaniam, \ell -Diversity: Privacy Beyond \kappa -Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.24, April 03-07, 2006 [doi>10.1109/ICDE.2006.1]
• 22: D. J. Martin, D. Kifer, A. Machanavajjhala, J. Gehrke, and J. Y. Halpern. Worst-case background knowledge for privacy-preserving data publishing. In ICDE, pages 126--135, 2007.
• 23: Mehmet Ercan Nergiz , Maurizio Atzori , Chris Clifton, Hiding the presence of individuals from shared databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247554]
• 24: Vibhor Rastogi , Dan Suciu , Sungho Hong, The boundary between privacy and utility in data publishing, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 25: P. Samarati, Protecting Respondents' Identities in Microdata Release, IEEE Transactions on Knowledge and Data Engineering, v.13 n.6, p.1010-1027, November 2001 [doi>10.1109/69.971193]
• 26: 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]
• 27: Ke Wang , Benjamin C. M. Fung , Philip S. Yu, Template-Based Privacy Preservation in Classification Problems, Proceedings of the Fifth IEEE International Conference on Data Mining, p.466-473, November 27-30, 2005 [doi>10.1109/ICDM.2005.142]
• 28: Ke Wang , Philip S. Yu , Sourav Chakraborty, Bottom-Up Generalization: A Data Mining Solution to Privacy Protection, Proceedings of the Fourth IEEE International Conference on Data Mining, p.249-256, November 01-04, 2004
• 29: Raymond Chi-Wing Wong , Jiuyong Li , Ada Wai-Chee Fu , Ke Wang, (α, k)-anonymity: an enhanced k-anonymity model for privacy preserving data publishing, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150499]
• 30: Xiaokui Xiao , Yufei Tao, Anatomy: simple and effective privacy preservation, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 31: Yabo Xu , Benjamin C. M. Fung , Ke Wang , Ada W. C. Fu , Jian Pei, Publishing Sensitive Transactions for Itemset Utility, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.1109-1114, December 15-19, 2008 [doi>10.1109/ICDM.2008.98]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation, Security, Theory

Keywords:
anonymity, data mining, data publishing, privacy