Anonymization-based attacks in privacy-preserving data publishing

ABSTRACT

Data publishing generates much concern over the protection of individual privacy. Recent studies consider cases where the adversary may possess different kinds of knowledge about the data. In this article, we show that knowledge of the mechanism or algorithm of anonymization for data publication can also lead to extra information that assists the adversary and jeopardizes individual privacy. In particular, all known mechanisms try to minimize information loss and such an attempt provides a loophole for attacks. We call such an attack a minimality attack. In this article, we introduce a model called m-confidentiality which deals with minimality attacks, and propose a feasible solution. Our experiments show that minimality attacks are practical concerns on real datasets and that our algorithm can prevent such attacks with very little overhead and information loss.

REFERENCES

• 1: Aggarwal, G., Feder, T., Kenthapadi, K., Motwani, R., Panigrahy, R., Thomas, D., and Zhu, A. 2005a. Anonymizingtables. In Proceedings of the International Conference on Database Theory (ICDT'05), 246--258.
• 2: Aggarwal, G., Feder, T., Kenthapadi, K., Motwani, R., Panigrahy, R., Thomas, D., and Zhu, A. 2005b. Approximation algorithms for k-anonymity. J. Privacy Technol.
• 3: 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
• 4: Blake, E. K. C. and Merz, C. J. 1998. UCI repository of machine learning databases. http://www.ics.uci.edu/~mlearn/MLRepository.html.
• 5: David Brumley , Dan Boneh, Remote timing attacks are practical, Proceedings of the 12th conference on USENIX Security Symposium, p.1-1, August 04-08, 2003, Washington, DC
• 6: Yingyi Bu , Ada Wai Chee Fu , Raymond Chi Wing Wong , Lei Chen , Jiuyong Li, Privacy preserving serial data publishing by role composition, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453948]
• 7: Ciriani, V., Vimercati, S. D. C. D., Foresti, S., and Samarati, P. 2007. k-Anonymity. In Security in Decentralized Data Management.
• 8: 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]
• 9: Fayyad, U. M. and Irani, K. B. 1993. Multi-Interval discretization of continuous-valued attributes for classification learning. In Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI'93). Morgan Kaufmann.
• 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: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: Holyer, I. 1981. The np-completeness of some edge-partition problems. SIAM J. Comput. 10, 4, 713--717.
• 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: Paul C. Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.104-113, August 18-22, 1996
• 15: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Incognito: efficient full-domain K-anonymity, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066164]
• 16: 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]
• 17: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Workload-aware anonymization techniques for large-scale datasets, ACM Transactions on Database Systems (TODS), v.33 n.3, p.1-47, August 2008 [doi>10.1145/1386118.1386123]
• 18: Li, N. and Li, T. 2007. t-Closeness: Privacy beyond k-anonymity and l-diversity. In Proceedings of the International Conference on Data Engineering (ICDE).
• 19: 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]
• 20: 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]
• 21: Martin, D. J., Kifer, D., Machanavajjhala, A., and Gehrke, J. 2007. Worst-case background knowledge for privacy-preserving data publishing. In Proceedings of the International Conference on Data Engineering (ICDE).
• 22: 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]
• 23: 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]
• 24: 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]
• 25: Sweeney, L. 1997. Weaving technology and policy together to maintain confidentiality. J. Law, Med. Ethics 25, 2--3, 98--110.
• 26: Latanya Sweeney, Achieving k-anonymity privacy protection using generalization and suppression, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.571-588, October 2002 [doi>10.1142/S021848850200165X]
• 27: 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]
• 28: Ke Wang , Benjamin C. M. Fung, Anonymizing sequential releases, 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.1150449]
• 29: Ke Wang , Benjamin C. M. Fung , Philip S. Yu, Handicapping attacker's confidence: an alternative to k-anonymization, Knowledge and Information Systems, v.11 n.3, p.345-368, April 2007 [doi>10.1007/s10115-006-0035-5]
• 30: 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
• 31: Raymond Chi-Wing Wong , Ada Wai-Chee Fu , Ke Wang , Jian Pei, Minimality attack in privacy preserving data publishing, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 32: 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]
• 33: 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
• 34: Xiaokui Xiao , Yufei Tao, Personalized privacy preservation, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142500]
• 35: Xiaokui Xiao , Yufei Tao, M-invariance: towards privacy preserving re-publication of dynamic datasets, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247556]
• 36: Jian Xu , Wei Wang , Jian Pei , Xiaoyuan Wang , Baile Shi , Ada Wai-Chee Fu, Utility-based anonymization using local recoding, 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.1150504]
• 37: Lei Zhang , Sushil Jajodia , Alexander Brodsky, Information disclosure under realistic assumptions: privacy versus optimality, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315316]
• 38: Zhang, Q., Koudas, N., Srivastava, D., and Yu, T. 2007. Aggregate query answering on aononymized tables. In Proceedings of the International Conference on Data Engineering (ICDE'07).

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General

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

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Privacy

General Terms:
Algorithms, Experimentation, Security

Keywords:
k-anonymity, l-diversity, Privacy preservation, data publishing, minimality attack