research-article

Anonymization-based attacks in privacy-preserving data publishing

Authors:

Raymond Chi-Wing Wong,

Ada Wai-Chee Fu,

Jian PeiAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 34, Issue 2

Article No.: 8, Pages 1 - 46

https://doi.org/10.1145/1538909.1538910

Published: 02 July 2009 Publication History

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.

Supplementary Material

Wong Appendix (a8-wong-apndx.pdf)

Online appendix to anonymization-based attacks in privacy-preserving data publishing. The appendix supports the information on article 8.

Download
165.50 KB

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.

Digital Library

[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]

]]Agrawal, R. and Srikant, R. 2000. Privacy-preserving data mining. In Proceedings of the ACM SIGMOD Conference on Management of Data. ACM Press, 439--450.

Digital Library

[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]

]]Brumley, D. and Boneh, D. 2003. Remote timing attacks are practical. In Proceedings of the USENIX Security Symposium.

Digital Library

[6]

]]Bu, Y., Fu, A. W.-C., Wong, R. C.-W., Chen, L., and Li, J. 2008. Privacy preserving serial data publishing by role composition. In Proceedigs of the International Conference on Very Large Databases.

Digital Library

[7]

]]Ciriani, V., Vimercati, S. D. C. D., Foresti, S., and Samarati, P. 2007. k-Anonymity. In Security in Decentralized Data Management.

[8]

]]Evfimievski, A., Srikant, R., and Rakesh Agrawal, J. G. 2002. Privacy preserving mining of association rules. In Proceedings of the International SIGKDD Conference on Knowledge Discovery and Data Mining.

Digital Library

[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]

]]Fung, B. C. M., Wang, K., and Yu, P. S. 2005. Top-down specialization for information and privacy preservation. In Proceedings of the International Conference on Data Engineering (ICDE), 205--216.

Digital Library

[11]

]]Garey, M. and Johnson, D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman.

Digital Library

[12]

]]Holyer, I. 1981. The np-completeness of some edge-partition problems. SIAM J. Comput. 10, 4, 713--717.

Digital Library

[13]

]]Kifer, D. and Gehrke, J. 2006. Injecting utility into anonymized datasets. In Proceedings of the ACM SIGMOD International Conference on Management of Data.

Digital Library

[14]

]]Kocher, P. C. 1996. Timing attacks on implementations of Diffe-Hellman RSA, DSS, and other systems. In Proceedings of the International Cryptology Conference (CRYPTO'96), 104--113.

Digital Library

[15]

]]LeFevre, K., DeWitt, D. J., and Ramakrishnan, R. 2005. Incognito: Efficient full-domain k-anonymity. In Proceedings of the ACM SIGMOD International Conference on Management of Data, 49--60.

Digital Library

[16]

]]LeFevre, K., DeWitt, D. J., and Ramakrishnan, R. 2006. Mondrian multidimensional k-anonymity. In Proceedings of the International Conference on Data Engineering (ICDE).

Digital Library

[17]

]]LeFevre, K., Dewitt, D. J., and Ramakrishnan, R. 2008. Workload-aware anonymization techniques for large-scale datasets. ACM Trans. Datab. Syst. 33, 3.

Digital Library

[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]

]]Li, T. and Li, N. 2008. Injector: Mining background knowledge for data anonymization. In Proceedings of the International Conference on Data Engineering (ICDE).

Digital Library

[20]

]]Machanavajjhala, A., Gehrke, J., and Kifer, D. 2006. l-Diversity: Privacy beyond k-anonymity. In Proceedings of the International Conference on Data Engineering (ICDE).

Digital Library

[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]

]]Meyerson, A. and Williams, R. 2004. On the complexity of optimal k-anonymity. In Proceedings of the Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS'04), 223--228.

Digital Library

[23]

]]Samarati, P. 2001. Protecting respondents' identities in micro-data release. Trans. Knowl. Data Eng. 13, 6, 1010--1027.

Digital Library

[24]

]]Samarati, P. and Sweeney, L. 1998. Generalizing data to provide anonymity when disclosing information (abstract). In Proceedings of the 17th ACM-SIGMOD-SIGACT-SIGART Symposium on the Principles of Database Systems (PODS).

Digital Library

[25]

]]Sweeney, L. 1997. Weaving technology and policy together to maintain confidentiality. J. Law, Med. Ethics 25, 2--3, 98--110.

[26]

]]Sweeney, L. 2002a. Achieving k-anonymity privacy protection using generalization and suppres- sion. Int. J. Uncertainess, Fuzziness Knowl.-based Syst. 10, 5, 571--588.

Digital Library

[27]

]]Sweeney, L. 2002b. k-Anonymity: A model for protecting privacy. Int. J. Uncertainty, Fuzziness Knowl.-based Syst. 10, 5, 557--570.

Digital Library

[28]

]]Wang, K. and Fung, B. 2006. Anonymizing sequential releases. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.

Digital Library

[29]

]]Wang, K., Fung, B. C. M., and Yu, P. S. 2006. Handicapping attacker's confidence: An alternative to k-anonymization. Knowl. Inf. Syst. Int. J.

Digital Library

[30]

]]Wang, K., Yu, P. S., and Chakraborty, S. 2004. Bottom-up generalization: A data mining solution to privacy protection. In Proceedings of the IEEE International Conference on Data Mining (ICDM'04), 249--256.

Digital Library

[31]

]]Wong, R., Fu, A., Wang, K., and Pei, J. 2007. Minimality attack in privacy preserving data publishing. In Proceedings of the International Conference on Very Large Databases (VLDB).

Digital Library

[32]

]]Wong, R., Li, J., Fu, A., and Wang, K. 2006. (Alpha, k)-Anonymity: An enhanced k-anonymity model for privacy-preserving data publishing. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.

Digital Library

[33]

]]Xiao, X. and Tao, Y. 2006a. Anatomy: Simple and effective privacy preservation. In Proceedings of the International Conference on Very Large Databases (VLDB).

Digital Library

[34]

]]Xiao, X. and Tao, Y. 2006b. Personalized privacy preservation. In Proceedings of the ACM SIGMOD International Conference on Management of Data.

Digital Library

[35]

]]Xiao, X. and Tao, Y. 2007. m-Invariance: Towards privacy preserving re-publication of dynamic datasets. In Proceedings of the ACM SIGMOD International Conference on Management of Data.

Digital Library

[36]

]]Xu, J., Wang, W., Pei, J., Wang, X., Shi, B., and Fu, A. 2006. Utility-based anonymization using local recoding. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.

Digital Library

[37]

]]Zhang, L., Jajodia, S., and Brodsky, A. 2007. Information disclosure under realistic assumptions: Privacy versus optimality. In Proceedings of the 14th ACM Conference on Computer and Communications Security.

Digital Library

[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).

Cited By

Gadotti ARocher LHoussiau FCreţu Ade Montjoye Y(2024)Anonymization: The imperfect science of using data while preserving privacyScience Advances10.1126/sciadv.adn705310:29Online publication date: 19-Jul-2024
https://doi.org/10.1126/sciadv.adn7053
Sai ZCheng Y(2023)Difficulties and Countermeasures in Data Asset PricingCloud Computing – CLOUD 202310.1007/978-3-031-51709-9_8(85-94)Online publication date: 17-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-51709-9_8
Podlesny NKayem AMeinel C(2022)A Parallel Quasi-identifier Discovery Scheme for Dependable Data AnonymisationTransactions on Large-Scale Data- and Knowledge-Centered Systems L10.1007/978-3-662-64553-6_1(1-24)Online publication date: 1-Jan-2022
https://doi.org/10.1007/978-3-662-64553-6_1
Show More Cited By

Index Terms

Anonymization-based attacks in privacy-preserving data publishing

Recommendations

Can the Utility of Anonymized Data be Used for Privacy Breaches?

Group based anonymization is the most widely studied approach for privacy-preserving data publishing. Privacy models/definitions using group based anonymization includes k-anonymity, l-diversity, and t-closeness, to name a few. The goal of this article ...
Background knowledge attacks in privacy-preserving data publishing models
Abstract
Massive volumes of data are being generated at every moment through various sources in the cyber-physical world. While storing as well as facilitating these data for business or individual requirements, data disclosure, sensitive data ...
An effective value swapping method for privacy preserving data publishing

Privacy is an important concern in the society, and it has been a fundamental issue when to analyze and publish data involving human individual's sensitive information. Recently, the slicing method has been popularly used for privacy preservation in ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 34, Issue 2

June 2009

210 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/1538909

Issue’s Table of Contents

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 July 2009

Accepted: 01 November 2008

Revised: 01 October 2008

Received: 01 March 2008

Published in TODS Volume 34, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Research Grants Council, University Grants Committee, Hong Kong

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
938
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)2

Reflects downloads up to 06 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gadotti ARocher LHoussiau FCreţu Ade Montjoye Y(2024)Anonymization: The imperfect science of using data while preserving privacyScience Advances10.1126/sciadv.adn705310:29Online publication date: 19-Jul-2024
https://doi.org/10.1126/sciadv.adn7053
Sai ZCheng Y(2023)Difficulties and Countermeasures in Data Asset PricingCloud Computing – CLOUD 202310.1007/978-3-031-51709-9_8(85-94)Online publication date: 17-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-51709-9_8
Podlesny NKayem AMeinel C(2022)A Parallel Quasi-identifier Discovery Scheme for Dependable Data AnonymisationTransactions on Large-Scale Data- and Knowledge-Centered Systems L10.1007/978-3-662-64553-6_1(1-24)Online publication date: 1-Jan-2022
https://doi.org/10.1007/978-3-662-64553-6_1
Podlesny NKayem AMeinel C(2022)CoK: A Survey of Privacy Challenges in Relation to Data MeshesDatabase and Expert Systems Applications10.1007/978-3-031-12423-5_7(85-102)Online publication date: 22-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-12423-5_7
Chen RMohammed NFung BDesai BXiong L(2020)Publishing set-valued data via differential privacyProceedings of the VLDB Endowment10.14778/3402707.34027444:11(1087-1098)Online publication date: 3-Jun-2020
https://dl.acm.org/doi/10.14778/3402707.3402744
Zhao XLi YYuan YBi XWang G(2019)LDPart: Effective Location-Record Data Publication via Local Differential PrivayIEEE Access10.1109/ACCESS.2019.2899099(1-1)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2899099
Li DDong XLi M(2019)Differential privacy for publishing enterprise-scale WLAN tracesSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-018-3223-923:14(5667-5682)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s00500-018-3223-9
Eslami SMeinel CVon Schorlemer S(2018) P 2 AM: An Anti-Profiling Framework for Online Healthcare Applications 2018 IEEE 9th International Conference on Software Engineering and Service Science (ICSESS)10.1109/ICSESS.2018.8663804(351-356)Online publication date: Nov-2018
https://doi.org/10.1109/ICSESS.2018.8663804
Jiadi Yu Xin Dong Yuan Luo Minglu Li (2015)Differentially Private Wireless Data Publication in Large-Scale WLAN NetworksProceedings of the 2015 IEEE 21st International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS.2015.44(290-297)Online publication date: 14-Dec-2015
https://dl.acm.org/doi/10.1109/ICPADS.2015.44
Thakkar ABhatti AVasa J(2015)Correlation Based Anonymization Using Generalization and Suppression for Disclosure ProblemsAdvances in Intelligent Informatics10.1007/978-3-319-11218-3_52(581-592)Online publication date: 2015
https://doi.org/10.1007/978-3-319-11218-3_52
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents