@article {1638652,
	title = {Towards formalizing the GDPR{\textquoteright}s notion of singling out},
	journal = {The Proceedings of the National Academy of Sciences (PNAS)},
	volume = {117},
	number = {15},
	year = {2020},
	pages = {8344-8352},
	abstract = {
	There is a significant conceptual gap between legal and mathematica\&nbsp;thinking around data privacy. The effect is uncertainty\&nbsp;as to which technical offerings meet legal standards. This uncertainty\&nbsp;is exacerbated by a litany of successful privacy attacks\&nbsp;demonstrating that traditional statistical disclosure limitation\&nbsp;techniques often fall short of the privacy envisioned by regulators.



	We define {\textquotedblleft}predicate singling out,{\textquotedblright} a type of privacy\&nbsp;attack intended to capture the concept of singling out appearing\&nbsp;in the General Data Protection Regulation (GDPR). An adversary\&nbsp;predicate singles out a dataset x using the output of a\&nbsp;data-release mechanism M(x) if it finds a predicate p matching\&nbsp;exactly one row in x with probability much better than a statistical\&nbsp;baseline. A data-release mechanism that precludes suchattacks is {\textquotedblleft}secure against predicate singling out{\textquotedblright} (PSO secure).\&nbsp;We argue that PSO security is a mathematical concept with\&nbsp;legal consequences. Any data-release mechanism that purports\&nbsp;to {\textquotedblleft}render anonymous{\textquotedblright} personal data under the GDPR must prevent\&nbsp;singling out and, hence, must be PSO secure. We analyze\&nbsp;the properties of PSO security, showing that it fails to compose.\&nbsp;Namely, a combination of more than logarithmically many\&nbsp;exact counts, each individually PSO secure, facilitates predicate\&nbsp;singling out. Finally, we ask whether differential privacy and kanonymity



	are PSO secure. Leveraging a connection to statistical\&nbsp;generalization, we show that differential privacy implies PSO\&nbsp;security. However, and in contrast with current legal guidance, kanonymity\&nbsp;does not: There exists a simple predicate singling out\&nbsp;attack under mild assumptions on the k-anonymizer and the data distribution.

},
	author = {Aloni Cohen and Kobbi Nissim}
}
