The DOI matches its Crossref record; 63 of the 63 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 \kappa-anonymity has gained popularity. In a \kappa-anonymized dataset, each record is indistinguishable from at least k—1 other records with respect to certain "identifying" attributes. In this paper we show with two simple attacks that a \kappa-anonymized dataset has some subtle, but severe privacy problems. First, we show that an attacker can discover the values of sensitive attributes when there is little diversity in those sensitive attributes. Second, attackers often have background knowledge, and we show that \kappa-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 definition called \ell-diversity. In addition to building a formal foundation for \ell-diversity, we show in an experimental evaluation that \ell-diversity is practical and can be implemented efficiently.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Fast Algorithms for Mining Association Rules in Large Databases
Agrawal, R., & Srikant, R. (1994) · Very Large Data Bases · Cited by 9,419
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
L -diversity: Privacy beyond k -anonymity
Machanavajjhala, A., Kifer, D., Gehrke, J., & Venkitasubramaniam, M. (2007) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1217299.1217302 · Cited by 3,617
Self-citationGoldreich, 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,255
Privacy-preserving data mining
Agrawal, R., & Srikant, R. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335438 · Cited by 2,961
Completeness theorems for non-cryptographic fault-tolerant distributed computation
Ben-Or, M., & Wigderson, A. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62213 · Cited by 2,524
Protecting respondents identities in microdata release
Samarati, P. (2001) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.971193 · Cited by 2,324
Multiparty unconditionally secure protocols
Chaum, D., Crépeau, C., & Damgard, I. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62214 · Cited by 1,544
Samarati, P., & Sweeney, L. (2018) · doi:10.1184/r1/6625469 · Cited by 1,326
Data Privacy through Optimal k-Anonymization
Bayardo, R. J., & Agrawal, R. (2005) · 21st International Conference on Data Engineering (ICDE'05) · doi:10.1109/icde.2005.42 · Cited by 1,131
Incognito: efficient full-domain K-anonymity
LeFevre, K., DeWitt, D. J., & Ramakrishnan, R. (2005) · Proceedings of the 2005 ACM SIGMOD international conference on Management of data · doi:10.1145/1066157.1066164 · Cited by 1,070
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., & Nissim, K. (2003) · Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/773153.773173 · Cited by 980
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 969
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
On the complexity of optimal K-anonymity
Meyerson, A., & Williams, R. (2004) · Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1055558.1055591 · Cited by 821
Limiting privacy breaches in privacy preserving data mining
Evfimievski, A., Gehrke, J., & Srikant, R. (2003) · Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/773153.773174 · Cited by 815
Self-citationPractical privacy: the SuLQ framework
Blum, A., Dwork, C., McSherry, F., & Nissim, K. (2005) · Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1065167.1065184 · Cited by 797
Agrawal, R., Kiernan, J., Srikant, R., & Xu, Y. (2002) · VLDB '02: Proceedings of the 28th International Conference on Very Large Databases · doi:10.1016/b978-155860869-6/50021-4 · Cited by 723
The platform for privacy preferences
Reagle, J., & Cranor, L. F. (1999) · Communications of the ACM · doi:10.1145/293411.293455 · Cited by 716
Information sharing across private databases
Agrawal, R., Evfimievski, A., & Srikant, R. (2003) · Proceedings of the 2003 ACM SIGMOD international conference on Management of data · doi:10.1145/872757.872771 · Cited by 634
On the privacy preserving properties of random data perturbation techniques
Kargupta, H., Datta, S., Wang, Q., & Sivakumar, K. (2004) · Third IEEE International Conference on Data Mining · doi:10.1109/icdm.2003.1250908 · Cited by 618
Algebraic algorithms for sampling from conditional distributions
Diaconis, P., & Sturmfels, B. (1998) · The Annals of Statistics · doi:10.1214/aos/1030563990 · Cited by 616
Deriving private information from randomized data
Huang, Z., Du, W., & Chen, B. (2005) · Proceedings of the 2005 ACM SIGMOD international conference on Management of data · doi:10.1145/1066157.1066163 · Cited by 404
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 364
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. (2003) · Proceedings 2003 VLDB Conference · doi:10.1016/b978-012722442-8/50084-7 · Cited by 289
Suppression Methodology and Statistical Disclosure Control
Cox, L. H. (1980) · Journal of the American Statistical Association · doi:10.1080/01621459.1980.10477481 · Cited by 271
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 264
Limiting Disclosure in Hippocratic Databases
LeFevre, K., Agrawal, R., Ercegovac, V., Ramakrishnan, R., Xu, Y., & DeWitt, D. (2004) · Proceedings 2004 VLDB Conference · doi:10.1016/b978-012088469-8.50013-9 · Cited by 242
Agrawal, R., Srikant, R., & Thomas, D. (2005) · Proceedings of the 2005 ACM SIGMOD international conference on Management of data · doi:10.1145/1066157.1066187 · Cited by 242
From statistical knowledge bases to degrees of belief
Bacchus, F., Grove, A. J., Halpern, J. Y., & Koller, D. (1996) · Artificial Intelligence · doi:10.1016/s0004-3702(96)00003-3 · Cited by 217
The tracker: a threat to statistical database security
Denning, D. E., & Denning, P. J. (1979) · ACM Transactions on Database Systems · doi:10.1145/320064.320069 · Cited by 209
Secure statistical databases with random sample queries
Denning, D. E. (1980) · ACM Transactions on Database Systems · doi:10.1145/320613.320616 · Cited by 204
Secure databases: protection against user influence
Dobkin, D., Jones, A. K., & Lipton, R. J. (1979) · ACM Transactions on Database Systems · doi:10.1145/320064.320068 · Cited by 203
The Linear Randomized Response Model
Warner, S. L. (1971) · Journal of the American Statistical Association · doi:10.1080/01621459.1971.10482364 · Cited by 190
On the Question of Statistical Confidentiality
Fellegi, I. P. (1972) · Journal of the American Statistical Association · doi:10.1080/01621459.1972.10481199 · Cited by 180
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
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
Privacy-preserving distributed mining of association rules on horizontally partitioned data
Kantarcıoğlu, M., & Clifton, C. (2004) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2004.45 · Cited by 149
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 148
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 137
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
Commodity-based cryptography (extended abstract)
Beaver, D. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258637 · Cited by 123
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
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
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
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 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
Cited by
L -diversity: Privacy beyond k -anonymity
Machanavajjhala, A., Kifer, D., Gehrke, J., & Venkitasubramaniam, M. (2007) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1217299.1217302 · Cited by 3,617
Self-citationDifferential 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
Robust De-anonymization of Large Sparse Datasets
Narayanan, A., & Shmatikov, V. (2008) · 2008 IEEE Symposium on Security and Privacy (sp 2008) · doi:10.1109/sp.2008.33 · Cited by 2,372
Privacy-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., Gehrke, J., Kifer, D., & Venkitasubramaniam, M.
- Venue
- 22nd International Conference on Data Engineering (ICDE'06)
- Publisher
- IEEE
- Published
- 2006
- Pages
- 24-24
- ISSN
- 1084-4627 (ISSN-L)
- OpenAlex
- W2134479759
- Cited by
- 2,362
- References
- 63
- FWCI
- 100.13
- Type
- conference paper
- Language
- en
- Open access
- closed
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
