The DOI matches its Crossref record; 73 of the 73 references it cites were found in a registry or an index.
L -diversity: Privacy beyond k -anonymity
Abstract
Publishing data about individuals without revealing sensitive information about them is an important problem. In recent years, a new definition of privacy called k -anonymity has gained popularity. In a k -anonymized dataset, each record is indistinguishable from at least k − 1 other records with respect to certain identifying attributes. In this article, we show using two simple attacks that a k -anonymized dataset has some subtle but severe privacy problems. First, an attacker can discover the values of sensitive attributes when there is little diversity in those sensitive attributes. This is a known problem. Second, attackers often have background knowledge, and we show that k -anonymity does not guarantee privacy against attackers using background knowledge. We give a detailed analysis of these two attacks, and we propose a novel and powerful privacy criterion called ℓ-diversity that can defend against such attacks. In addition to building a formal foundation for ℓ-diversity, we show in an experimental evaluation that ℓ-diversity is practical and can be implemented efficiently.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“To address these shortcomings, Machanavajjhala et al. [162] proposed l-diversity, which ensures that each sensitive attribute of the user should have l distinct values for every equivalence class, which share the same quasi-identifier values.”
From A Deep Dive into Fairness, Bias, Threats, and Privacy in Recommender Systems: Insights and Future Research (2024) · cites this paper as [162]
In the citing paper
“Key approaches (e.g.[194,205,276]) seek to protect speciic individuals and groups from being identiiable, i.e., minimize disclosure risk.”
From Fairness in machine learning: A survey (2024) · cites this paper as [205]
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot the international journal of robotics research and application · doi:10.1108/ir.1999.04926fae.001 · Cited by 39,228
Fast Algorithms for Mining Association Rules in Large Databases
Agrawal, R., & Srikant, R. (1994) · Very Large Data Bases · Cited by 9,454
k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
SWEENEY, L. (2002) · International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems · doi:10.1142/s0218488502001648 · Cited by 8,571
Goldreich, O., Micali, S., & Wigderson, A. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28420 · Cited by 3,590
Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias
Warner, S. L. (1965) · Journal of the American Statistical Association · doi:10.1080/01621459.1965.10480775 · Cited by 3,261
Privacy-preserving data mining
Agrawal, R., & Srikant, R. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335438 · Cited by 3,009
Completeness theorems for non-cryptographic fault-tolerant distributed computation
Ben-Or, M., & Wigderson, A. (1988) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/62212.62213 · Cited by 2,529
L-diversity: privacy beyond k-anonymity
Machanavajjhala, A., Gehrke, J. E., Kifer, D., & Venkitasubramaniam, M. (2006) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2006.1 · Cited by 2,436
Self-citationProtecting respondents identities in microdata release
Samarati, P. (2001) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.971193 · Cited by 2,339
Privacy-preserving data mining
Agrawal, R., & Srikant, R. (2000) · Proceedings of the 2000 ACM SIGMOD international conference on Management of data · doi:10.1145/342009.335438 · Cited by 1,719
Multiparty unconditionally secure protocols
Chaum, D., Crépeau, C., & Damgård, I. (1988) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/62212.62214 · Cited by 1,554
Samarati, P., & Sweeney, L. (2018) · doi:10.1184/r1/6625469.v1 · Cited by 1,344
Samarati, P., & Sweeney, L. (2018) · doi:10.1184/r1/6625469 · Cited by 1,323
Data Privacy through Optimal k-Anonymization
Bayardo, R. J., & Agrawal, R. (2005) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2005.42 · Cited by 1,167
LeFevre, K., DeWitt, D. J., & Ramakrishnan, R. (2005) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1066157.1066164 · Cited by 1,078
On the design and quantification of privacy preserving data mining algorithms
Agrawal, D., & Aggarwal, C. C. (2001) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/375551.375602 · Cited by 1,015
Privacy preserving association rule mining in vertically partitioned data
Vaidya, J., & Clifton, C. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775142 · Cited by 1,001
Revealing information while preserving privacy
Dinur, I., & Kobbi Nissim, B. (2003) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/773153.773173 · Cited by 993
Security-control methods for statistical databases: a comparative study
Adam, N. R., & Worthmann, J. C. (1989) · ACM Computing Surveys · doi:10.1145/76894.76895 · Cited by 975
Tools for privacy preserving distributed data mining
Clifton, C., Kantarcioglu, M., Vaidya, J., Lin, X., & Zhu, M. Y. (2002) · ACM SIGKDD Explorations Newsletter · doi:10.1145/772862.772867 · Cited by 890
Privacy-preserving distributed mining of association rules on horizontally partitioned data
Clifton, C., Kantarcioglu, M., Clifton, C., & Member, S. (2010) · Cited by 888
On the complexity of optimal K-anonymity
Meyerson, A., & Williams, R. (2004) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/1055558.1055591 · Cited by 839
Limiting privacy breaches in privacy preserving data mining
Evfimievski, A., Gehrke, J. E., & Srikant, R. (2003) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/773153.773174 · Cited by 830
Self-citationBlum, A. L., Dwork, C., McSherry, F., & Kobbi Nissim, B. (2005) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/1065167.1065184 · Cited by 812
Privacy preserving mining of association rules
Evfimievski, A., Srikant, R., Agrawal, R., & Gehrke, J. E. (2002) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/775047.775080 · Cited by 772
Self-citationAgrawal, R., Kiernan, J., Srikant, R., & Xu, Y. (2002) · Elsevier eBooks · doi:10.1016/b978-155860869-6/50021-4 · Cited by 729
The platform for privacy preferences
Reagle, J., & Cranor, L. F. (1999) · Communications of the ACM · doi:10.1145/293411.293455 · Cited by 718
Information sharing across private databases
Agrawal, R., Evfimievski, A., & Srikant, R. (2003) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/872757.872771 · Cited by 637
On the privacy preserving properties of random data perturbation techniques
Kargupta, H., Datta, S., Wang, Q., & Sivakumar, K. (2004) · Proceedings · doi:10.1109/icdm.2003.1250908 · Cited by 623
Algebraic algorithms for sampling from conditional distributions
Diaconis, P. W., & Sturmfels, B. (1998) · The Annals of Statistics · doi:10.1214/aos/1030563990 · Cited by 616
The platform for privacy preferences 1.0 (p3p1.0) specification
Cranor, L. F., Langheinrich, M., Massimo Marchiori, B., & Presler-Marshall, M. (2002) · Medical Entomology and Zoology · Cited by 513
Deriving private information from randomized data
Huang, Z., Du, W. K., & Chen, B. (2005) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1066157.1066163 · Cited by 407
A Condensation Approach to Privacy Preserving Data Mining
Aggarwal, C. C., & Yu, P. S. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24741-8_12 · Cited by 367
Data-swapping: A technique for disclosure control
Dalenius, T., & Reiss, S. P. (1982) · Journal of Statistical Planning and Inference · doi:10.1016/0378-3758(82)90058-1 · Cited by 349
Controlling Access to Published Data Using Cryptography
Miklau, G., & Suciu, D. M. (2003) · Elsevier eBooks · doi:10.1016/b978-012722442-8/50084-7 · Cited by 287
Toward Privacy in Public Databases
Chawla, S., Dwork, C., McSherry, F., Smith, A., & Wee, H. (2005) · Lecture notes in computer science · doi:10.1007/978-3-540-30576-7_20 · Cited by 267
Suppression Methodology and Statistical Disclosure Control
Cox, L. H. (1980) · Journal of the American Statistical Association · doi:10.1080/01621459.1980.10477481 · Cited by 260
Agrawal, R., Srikant, R., & Thomas, D. (2005) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1066157.1066187 · Cited by 241
Limiting Disclosure in Hippocratic Databases
LeFevre, K., Agrawal, R., Ercegovac, V., Ramakrishnan, R., Xu, Y., & DeWitt, D. J. (2004) · Elsevier eBooks · doi:10.1016/b978-012088469-8.50013-9 · Cited by 239
From statistical knowledge bases to degrees of belief
Fahiem Bacchus, A., Grove, A. J., Halpern, J. Y., & Koller, D. (1996) · Artificial Intelligence · doi:10.1016/s0004-3702(96)00003-3 · Cited by 217
Denning, D. E., & Denning, P. J. (1979) · ACM Transactions on Database Systems · doi:10.1145/320064.320069 · Cited by 215
Secure statistical databases with random sample queries
Denning, D. E. (1980) · ACM Transactions on Database Systems · doi:10.1145/320613.320616 · Cited by 210
Dobkin, D., Jones, A. K., & Lipton, R. J. (1979) · ACM Transactions on Database Systems · doi:10.1145/320064.320068 · Cited by 203
On the Question of Statistical Confidentiality
Fellegi, I. P. (1972) · Journal of the American Statistical Association · doi:10.1080/01621459.1972.10481199 · Cited by 184
The Linear Randomized Response Model
Warner, S. L. (1971) · Journal of the American Statistical Association · doi:10.1080/01621459.1971.10482364 · Cited by 181
The statistical security of a statistical database
Traub, J. F., Yemini, Y., & Woźniakowski, H. (1984) · ACM Transactions on Database Systems · doi:10.1145/1994.383392 · Cited by 156
Privacy-enhancing k -anonymization of customer data
Zhong, S., Yang, Z., & Wright, R. N. (2005) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/1065167.1065185 · Cited by 150
A formal analysis of information disclosure in data exchange
Miklau, G., & Suciu, D. M. (2004) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1007568.1007633 · Cited by 150
Kenthapadi, K., Mishra, N., & Nissim, K. (2005) · ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/1065167.1065183 · Cited by 138
A practical approach to solve Secure Multi-party Computation problems
Du, W. K., & Zhan, Z. (2002) · New Security Paradigms Workshop · doi:10.1145/844102.844125 · Cited by 136
A security machanism for statistical database
Beck, L. L. (1980) · ACM Transactions on Database Systems · doi:10.1145/320613.320617 · Cited by 135
Tamper Detection in Audit Logs
Snodgrass, R. T., Yao, S. S., & Collberg, C. S. (2004) · Elsevier eBooks · doi:10.1016/b978-012088469-8.50046-2 · Cited by 125
Auditing Compliance with a Hippocratic Database
Agrawal, R., Bayardo, R. J., Faloutsos, C., Kiernan, J., Rantzau, R., & Srikant, R. (2004) · Elsevier eBooks · doi:10.1016/b978-012088469-8.50047-4 · Cited by 121
Commodity-based cryptography (extended abstract)
Beaver, D. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258637 · Cited by 120
A study of several specific secure two-party computation problems
Du, W. K., Atallah, M. J., & Spafford, E. H. (2001) · Cited by 88
Network Models for Complementary Cell Suppression
Cox, L. H. (1995) · Journal of the American Statistical Association · doi:10.1080/01621459.1995.10476652 · Cited by 85
Security problems on inference control for SUM, MAX, and MIN queries
Chin, F. Y. L. (1986) · Journal of the ACM · doi:10.1145/5925.5928 · Cited by 83
Identification and Retrieval of Personal Records from a Statistical Data Bank
Schlörer, J. (1975) · Methods of Information in Medicine · doi:10.1055/s-0038-1635690 · Cited by 77
Kleinberg, J. M., Papadimitriou, C. H., & Raghavan, P. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(02)00036-3 · Cited by 76
Using Boolean reasoning to anonymize databases
Øhrn, A., & Ohno‐Machado, L. (1999) · Artificial Intelligence in Medicine · doi:10.1016/s0933-3657(98)00056-6 · Cited by 71
Secure XML Publishing without Information Leakage in the Presence of Data Inference
Yang, X., & Li, C. (2004) · Elsevier eBooks · doi:10.1016/b978-012088469-8.50012-7 · Cited by 66
Obtaining Information while Preserving Privacy: A Markov Perturbation Method for Tabular Data
Duncan, G. T., & Feinberg, S. E. (2018) · doi:10.1184/r1/6471734 · Cited by 64
Kleinberg, J. M., Papadimitriou, C. H., & Raghavan, P. (2000) · doi:10.1145/335168.335210 · Cited by 64
Worst-Case Background Knowledge in Privacy
MARTIN, D. J., Kifer, D., Machanavajjhala, A., Gehrke, J. E., & Halpern, J. Y. (2006) · eCommons (Cornell University) · Cited by 39
Self-citationBounds for Cell Entries in Two-Way Tables Given Conditional Relative Frequencies
Slavković, A., & Fienberg, S. E. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-25955-8_3 · Cited by 37
Assessing the Risk of Disclosure of Confidential Categorical Data
Dobra, A., Fienberg, S. E., & Trottini, M. (2003) · doi:10.1093/oso/9780198526155.003.0007 · Cited by 36
Statistical tools for disclosure limitation in multi-way contingency tables
Dobra, A. (2002) · Medical Entomology and Zoology · Cited by 35
Ben‐Tal, A., Charnes, A., & Teboulle, M. (1989) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(89)90128-5 · Cited by 31
Bounding Entries in Multi-way Contingency Tables Given a Set of Marginal Totals
Dobra, A., & Fienberg, S. E. (2003) · Contributions to statistics · doi:10.1007/978-3-642-57410-8_1 · Cited by 29
Auditing for secure statistical databases
Chin, F. Y. L., & Özsoyoğlu, G. (1981) · ACM Annual Conference · doi:10.1145/800175.809832 · Cited by 29
Beaver, D. (1998) · New Security Paradigms Workshop · doi:10.1145/310889.310923 · Cited by 27
Admissibility Implications for Different Criteria in Confidence Estimation
Cohen, A., & Strawderman, W. E. (1973) · The Annals of Statistics · doi:10.1214/aos/1176342375 · Cited by 26
Another Look at the Use of Noise Addition for Database Security
Matloff, N. (1986) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.1986.10014 · Cited by 25
Research works printed but not linked: 4
- Cox , L. H. 1982 . Solving confidentiality protection problems in tabulations using network optimization: A network model for cell suppression in the u.s. economic censuses . In Proceedings of the International Seminar on Statistical Confidentiality. Dublin International Statistical Institute , Dublin, Ireland. 229--245. Cox, L. H. 1982. Solving confidentiality protection problems in tabulations using network optimization: A network model for cell suppression in the u.s. economic censuses. In Proceedings of the International Seminar on Statistical Confidentiality. Dublin International Statistical Institute, Dublin, Ireland. 229--245.
- Cox , L. H. 1987 . New results in dislosure avoidance for tabulations . In Proceedings of the International Statistical Institute 46th Session . Tokyo, Japan. 83--84. Cox, L. H. 1987. New results in dislosure avoidance for tabulations. In Proceedings of the International Statistical Institute 46th Session. Tokyo, Japan. 83--84.
- 10.5555/1316689.1316701 · DOI
- Sweeney , L. 2000. Uniqueness of simple demographics in the u.s. population. Tech. rep ., Carnegie Mellon University . Sweeney, L. 2000. Uniqueness of simple demographics in the u.s. population. Tech. rep., Carnegie Mellon University.
Cited by
Sorted by citations
Differential Privacy: A Survey of Results
Dwork, C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-79228-4_1 · Cited by 3,542
t-Closeness: Privacy Beyond k-Anonymity and l-Diversity
Li, N., Li, T., & Venkatasubramanian, S. (2007) · 2007 IEEE 23rd International Conference on Data Engineering · doi:10.1109/icde.2007.367856 · Cited by 3,451
Decentralizing Privacy: Using Blockchain to Protect Personal Data
Zyskind, G., Nathan, O., & Pentland, A. '. (2015) · 2015 IEEE Security and Privacy Workshops · doi:10.1109/spw.2015.27 · Cited by 2,617
L-diversity: privacy beyond k-anonymity
Machanavajjhala, A., Gehrke, J. E., Kifer, D., & Venkitasubramaniam, M. (2006) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2006.1 · Cited by 2,436
Self-citationPrivacy-preserving data publishing: A survey of recent developments
Fung, B. C. M., Wang, K., Chen, R., & Yu, P. S. (2010) · ACM Computing Surveys · doi:10.1145/1749603.1749605 · Cited by 1,704
Metadata
- Authors
- Machanavajjhala, A., Kifer, D., Gehrke, J., & Venkitasubramaniam, M.
- Affiliations
- Cornell University (US)
- Venue
- ACM Transactions on Knowledge Discovery from Data
- Published
- 2007-03
- Volume
- 1
- Issue
- 1
- Pages
- 3
- ISSN
- 1556-4681 (ISSN-L)
- 1556-472X
- OpenAlex
- W2134167315
- Cited by
- 3,617
- References
- 72
- Citations by year
- 2026: 96 · 2025: 180 · 2024: 152 · 2023: 179 · 2022: 179 · 2021: 237 · 2020: 199 · 2019: 183 · 2018: 245 · 2017: 248 · 2016: 232 · 2015: 246 · 2014: 264 · 2013: 219 · 2012: 189
- FWCI
- 155.30
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- ACM Transactions on Knowledge Discovery from Data (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Social Sciences › Sociology and Political Science › Privacy, Security, and Data Protection
- Physical Sciences › Computer Science › Computer Networks and Communications › Access Control and Trust
- Keywords
- l-diversity, k-anonymity, privacy preservation, data anonymization, background knowledge attack, privacy attacks
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
