Protecting Privacy Against Structural
De-anonymization Attacks in Social Networks


Gábor György Gulyás

Ph.D Thesis


Research Supervisor:
Sándor Imre, DSc.

Budapest University of Technology and Economics
Department of Networked Systems and Services
CrySyS and MCL Labs




Privacy is a core concern of online social networks. Probably the corner stone challenge is the amount of identifiable information contained in social network meta-data: the underlying graph structure. Sanitized social network information is occasionally shared with third parties, such as business partners and researchers. Previous research developed de-anonymization attacks that can re-identify social network users in such datasets by using public data sources, e.g., obtained by crawling other networks. A strong class of such attacks considered in this dissertation solely consider structural information of the social graph, and achieve large-scale re-identification.

This yields the need for solutions protecting user privacy in social networks. In this thesis, I consider client-side solutions that involve users only, and can be adopted gradually within existing services. Specifically, I investigate the use of an identity management technique called identity separation as a tool for tackling de-anonymization attacks, and analyze several settings of the technique. Initially, my experiments focus on measuring the effectiveness of basic, non-cooperative identity separation mechanisms. Then, I experimentally check if multiple cooperation models can improve overall protection. Finally, I evaluate several strategies where the focus is on protecting the individual privacy of participants. Some of these strategies provide feasible protection in case of the state-of-the-art attack, while others have theoretical guarantees.

Besides, I also contribute to the analysis of attack algorithms: I propose methods for measuring anonymity, and characterize how the initialization of these algorithms can affect the overall performance of the attack.