# Attacks on Deidentification's Defenses

arXiv: https://arxiv.org/abs/2202.13470 · HTML: https://mlsanity.com/paper/2202.13470/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2022.

## Built on by (most cited first, 11 of 11)

- [SoK: Privacy-Preserving Data Synthesis](https://mlsanity.com/paper/2307.02106/) (2023)
- [A Linear Reconstruction Approach for Attribute Inference Attacks against Synthetic Data](https://mlsanity.com/paper/2301.10053/) (2023)
- [Private, fair and accurate: Training large-scale, privacy-preserving AI models in medical imaging](https://mlsanity.com/paper/2302.01622/) (2023)
- [Large-scale online deanonymization with LLMs](https://mlsanity.com/paper/2602.16800/) (2026)
- [Synthetic data generation for a longitudinal cohort study -- Evaluation, method extension and reproduction of published data analysis results](https://mlsanity.com/paper/2305.07685/) (2023)
- [ContextLeak: Auditing Leakage in Private In-Context Learning Methods](https://mlsanity.com/paper/2512.16059/) (2025)
- [A Unified Framework for Adversary-Aware Differential Privacy Bounds](https://mlsanity.com/paper/2507.08158/) (2025)
- [Reconciling AI Performance and Data Reconstruction Resilience for Medical Imaging](https://mlsanity.com/paper/2312.04590/) (2023)
- [Efficient Unlearning with Privacy Guarantees](https://mlsanity.com/paper/2507.04771/) (2025)
- [Rethinking Anonymity Claims in Synthetic Data Generation: A Model-Centric Privacy Attack Perspective](https://mlsanity.com/paper/2601.22434/) (2026)
- [Stereo-LiDAR Fusion by Semi-Global Matching With Discrete Disparity-Matching Cost and Semidensification](https://mlsanity.com/paper/2504.05148/) (2025)

## Abstract (arXiv)

Quasi-identifier-based deidentification techniques (QI-deidentification) are widely used in practice, including k-anonymity, ℓ-diversity, and t-closeness. We present three new attacks on QI-deidentification: two theoretical attacks and one practical attack on a real dataset. In contrast to prior work, our theoretical attacks work even if every attribute is a quasi-identifier. Hence, they apply to k-anonymity, ℓ-diversity, t-closeness, and most other QI-deidentification techniques. First, we introduce a new class of privacy attacks called downcoding attacks, and prove that every QI-deidentification scheme is vulnerable to downcoding attacks if it is minimal and hierarchical. Second, we convert the downcoding attacks into powerful predicate singling-out (PSO) attacks, which were recently proposed as a way to demonstrate that a privacy mechanism fails to legally anonymize under Europe's General Data Protection Regulation. Third, we use LinkedIn.com to reidentify 3 students in a k-anonymized dataset published by EdX (and show thousands are potentially vulnerable), undermining EdX's claimed compliance with the Family Educational Rights and Privacy Act. The significance of this work is both scientific and political. Our theoretical attacks demonstrate that QI-deidentification may offer no protection even if every attribute is treated as a quasi-identifier. Our practical attack demonstrates that even deidentification experts acting in accordance with strict privacy regulations fail to prevent real-world reidentification. Together, they rebut a foundational tenet of QI-deidentification and challenge the actual arguments made to justify the continued use of k-anonymity and other QI-deidentification techniques.