On profile linkability despite anonymity in social media systems

A number of works have recently shown that the privacy offered by pseudonymous identities on social media systems like Twitter or Reddit is threatened by cross-site identity linking attacks. Such attacks link the identities of the same user across websites. Therefore, assessing linkability, i.e., the risk that identities are linked across different websites, remains an important open problem. In this work, we analyze whether anonymity within a sin- gle social media site can protect a user from being linked across sites. To this end, we first introduce a relative link- ability measure ranking identities within a social media site by their anonymity. We show that anonymity alone is not suffcient to assess linkability risks by evaluating this mea- sure on a data set comprising 15 million comments gathered from the Reddit social media system. Second, we mitigate this insuffciency and present our ab- solute linkability measure, which, in addition, utilizes infor- mation about matching identities. Then, we confirm the validity of this measure on our data set. The measure is able to accurately assess the linkability risk in almost 75% of the cases and, more importantly, is shown to never un- derestimate the linkability risk.