The Tension between Anonymity and Privacy

Abstract

Privacy in the context of information and data is often defined in terms of anonymity, particularly in regulations such as the GDPR. Operationally, it is appealing to define privacy in terms of computable data properties as this makes it possible to verify compliance. A well known example of privacy defined as such is k-anonymity. At the same time, uncertainty regarding real-world privacy is increasing with the amount of data collected about us all. We present arguments for why focusing on anonymity or computable properties of data is not very helpful in this regard. In particular, we count exploitable failures of privacy defined in terms of computable properties of n-bit data and conclude that these counterexamples to protection cannot be rare.