q-Anon: Rethinking Anonymity for Social Networks

This paper proposes that social network data should be assumed public but treated private. Assuming this rather confusing requirement means that anonymity models such as k-anonymity cannot be applied to the most common form of private data release on the internet, social network APIs. An alternative anonymity model, q-Anon, is presented, which measures the probability of an attacker logically deducing previously unknown information from a social network API while assuming the data being protected may already be public information. Finally, the feasibility of such an approach is evaluated suggesting that a social network site such as Facebook could practically implement an anonymous API using q-Anon, providing its users with an anonymous option to the current application model.

I. Introduction

Traditional anonymity research assumes that data is released as a research-style microdata set or statistical data set with well understood data types. Furthermore, it is assumed that the data provider knows a priori the background knowledge of possible attackers and how the data will be used. These models use these assumptions to specify data types as “quasi-identifiable” or “sensitive”. However, it is not so simple to make these assumptions about social networks. It is not easy to predict how applications may use social network data nor can concrete assumptions be made about the background knowledge of those who may attack a social network user's privacy. As such, all social network data must be treated as both sensitive (private) and quasi-identifiable (public) which makes it difficult to apply existing anonymity models to social networks.