The tension between anonymity and privacy
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.