Towards Formalizing the GDPR's Notion of Singling Out

Abstract

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\in 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 $\omega (\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.

References in corpus (4)

• Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
• Towards Formalizing the GDPR's Notion of Singling Out
• On the Generalization Properties of Differential Privacy
• The Limits of Post-Selection Generalization

Cited by in corpus (13)

• Privacy-preserving Artificial Intelligence Techniques in Biomedicine
• Towards Formalizing the GDPR's Notion of Singling Out
• "I need a better description'': An Investigation Into User Expectations For Differential Privacy
• Privacy and Confidentiality in Process Mining -- Threats and Research Challenges
• Private, fair and accurate: Training large-scale, privacy-preserving AI models in medical imaging
• An Overview of Privacy in Machine Learning
• Deletion-Compliance in the Absence of Privacy
• Locally private online change point detection
• Differentially Private Inductive Miner
• Transparency, Compliance, And Contestability When Code Is(n't) Law
• Privacy-Preserving Directly-Follows Graphs: Balancing Risk and Utility in Process Mining
• On Heuristic Models, Assumptions, and Parameters
• Generating Synthetic Data with Locally Estimated Distributions for Disclosure Control