@article {1624228,
	title = {Towards formalizing the GDPR{\textquoteright}s notion of singling out},
	journal = {Proceedings of the National Academy of Sciences},
	year = {2020},
	abstract = {There is a significant conceptual gap between legal and mathematical thinking around data privacy. The effect is uncertainty as to which technical offerings meet legal standards. This uncertainty is exacerbated by a litany of successful privacy attacks demonstrating that traditional statistical disclosure limitation techniques often fall short of the privacy envisioned by regulators. We define {\textquotedblleft}predicate singling out,{\textquotedblright} a type of privacy attack intended to capture the concept of singling out appearing in the General Data Protection Regulation (GDPR). An adversary predicate singles out a dataset x using the output of a data-release mechanism M(x)\&nbsp;if it finds a predicate p matching exactly one row in x with probability much better than a statistical baseline. A data-release mechanism that precludes such attacks is {\textquotedblleft}secure against predicate singling out{\textquotedblright} (PSO secure). We argue that PSO security is a mathematical concept with legal consequences. Any data-release mechanism that purports to {\textquotedblleft}render anonymous{\textquotedblright} personal data under the GDPR must prevent singling out and, hence, must be PSO secure. We analyze the properties of PSO security, showing that it fails to compose. Namely, a combination of more than logarithmically many exact counts, each individually PSO secure, facilitates predicate singling out. 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, and in contrast with current legal guidance, k-anonymity does not: There exists a simple predicate singling out attack under mild assumptions on the k-anonymizer and the data distribution.},
	url = {https://doi.org/10.1073/pnas.1914598117},
	author = {Aloni Cohen and Kobbi Nissim}
}
