Analysis of De-anonymization Attacks on Social Networks with Identity Separation

Most of today's online social networking services have a flat structure, i.e., these services only al low a single choice of connection type (usually called "friends") for t heir users, and lack the functionality of identity separation. Howe ver, identity partitioning allows users to group their contacts, to share different or even diverse information, and therefor e offer privacy protection against third parties looking to re-iden tify users in sanitized social graph data. In this paper, we anal yze the protective strength of identity separation against these types of structural de-anonymization attacks by introducing a statistical user behavior model and defining attack failure pro bability formally. It turns out from simulations and the par ameter analysis of the model that in case of even a relati vely small number of users applying identity separation, an at tacker is likely to fail.