# Towards Formalizing the GDPR's Notion of Singling Out

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Apr 2019.

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

- [Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning](https://mlsanity.com/paper/2101.04535/) (2021)
- [SoK: Let the Privacy Games Begin! A Unified Treatment of Data Inference Privacy in Machine Learning](https://mlsanity.com/paper/2212.10986/) (2022)
- [SoK: Privacy-Preserving Data Synthesis](https://mlsanity.com/paper/2307.02106/) (2023)
- [Deletion Inference, Reconstruction, and Compliance in Machine (Un)Learning](https://mlsanity.com/paper/2202.03460/) (2022)
- [Private, fair and accurate: Training large-scale, privacy-preserving AI models in medical imaging](https://mlsanity.com/paper/2302.01622/) (2023)
- [Unifying Re-Identification, Attribute Inference, and Data Reconstruction Risks in Differential Privacy](https://mlsanity.com/paper/2507.06969/) (2025)
- [The Inadequacy of Similarity-based Privacy Metrics: Privacy Attacks against "Truly Anonymous" Synthetic Datasets](https://mlsanity.com/paper/2312.05114/) (2023)
- [Distribution-Invariant Differential Privacy](https://mlsanity.com/paper/2111.05791/) (2021)
- [Measuring Re-identification Risk](https://mlsanity.com/paper/2304.07210/) (2023)
- [Federated Calibration and Evaluation of Binary Classifiers](https://mlsanity.com/paper/2210.12526/) (2022)
- [Approximate, Adapt, Anonymize (3A): a Framework for Privacy Preserving Training Data Release for Machine Learning](https://mlsanity.com/paper/2307.01875/) (2023)
- [TraVaG: Differentially Private Trace Variant Generation Using GANs](https://mlsanity.com/paper/2303.16704/) (2023)
- [When Synthetic Data Met Regulation](https://mlsanity.com/paper/2307.00359/) (2023)
- [From Principle to Practice: Vertical Data Minimization for Machine Learning](https://mlsanity.com/paper/2311.10500/) (2023)
- [Enhancing the Utility of Privacy-Preserving Cancer Classification using Synthetic Data](https://mlsanity.com/paper/2407.12669/) (2024)
- [Enabling PSO-Secure Synthetic Data Sharing Using Diversity-Aware Diffusion Models](https://mlsanity.com/paper/2506.17975/) (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)
- [Universal Semantic Disentangled Privacy-preserving Speech Representation Learning](https://mlsanity.com/paper/2505.13085/) (2025)
- [Rethinking Anonymity Claims in Synthetic Data Generation: A Model-Centric Privacy Attack Perspective](https://mlsanity.com/paper/2601.22434/) (2026)
- [Generating Synthetic Data with Locally Estimated Distributions for Disclosure Control](https://mlsanity.com/paper/2210.00884/) (2022)
- [NFDI4Health workflow and service for synthetic data generation, assessment and risk management](https://mlsanity.com/paper/2408.04478/) (2024)
- [Releasing Differentially Private Event Logs Using Generative Models](https://mlsanity.com/paper/2504.06418/) (2025)
- [Generate-then-Verify: Reconstructing Data from Limited Published Statistics](https://mlsanity.com/paper/2504.21199/) (2025)
- [Efficient Adaptive Data Analysis over Dense Distributions](https://mlsanity.com/paper/2602.07732/) (2026)
- [Plausible Deniability Guarantees for Whistleblowers](https://mlsanity.com/paper/2607.13928/) (2026)

## Abstract (arXiv)

There is a significant conceptual gap between legal and mathematical thinking around data privacy. The effect is uncertainty as to which technical offerings adequately match expectations expressed in legal standards. The uncertainty is exacerbated by a litany of successful privacy attacks, demonstrating that traditional statistical disclosure limitation techniques often fall short of the sort of privacy envisioned by legal standards. We define predicate singling out, a new type of privacy attack intended to capture the concept of singling out appearing in the General Data Protection Regulation (GDPR). Informally, an adversary predicate singles out a dataset X using the output of a data release mechanism M(X) if it manages to find a predicate p matching exactly one row x ∈ X with probability much better than a statistical baseline. A data release mechanism that precludes such attacks is secure against predicate singling out (PSO secure). We argue that PSO security is a mathematical concept with legal consequences. Any data release mechanism that purports to "render anonymous" personal data under the GDPR must be secure against singling out, and hence must be PSO secure. We then analyze PSO security, showing that it fails to self-compose. Namely, a combination of ω(log n) exact counts, each individually PSO secure, enables an attacker to predicate single out. In fact, the composition of just two PSO-secure mechanisms can fail to provide PSO security. Finally, we ask whether differential privacy and k-anonymity are PSO secure. Leveraging a connection to statistical generalization, we show that differential privacy implies PSO security. However, k-anonymity does not: there exists a simple and general predicate singling out attack under mild assumptions on the k-anonymizer and the data distribution.