Submitted Abstract
Over the last decade, online social networks (OSNs) have become one of the most popular online services. The analysis of social network data allows social scientists, market analysts, economists, among others, to understand societal phenomena, detect consumption patterns, assess the effect of policies, etc. Likewise, companies and public agencies can benefit from these studies to improve their decision-making processes and social outreach. In order to enable such studies, it is necessary that OSN owners release the necessary information about the network structure. However, given the personal and sensitive nature of the information contained in the network, it is necessary to sanitise the released information, to ensure that the privacy of the individual users is protected. Adversaries seek to re-identify users and learn sensitive private information about them from the sanitised information releases, such as the existence of relations between users, political affiliation, religious beliefs, etc. To that end, the adversary collects pieces of information that identifies each victim in a unique manner, so when the information is released the victims can be re-identified by matching the adversary knowledge to the released information. So-called active adversaries have the capacity of enrolling sybil nodes in the network, which engage in interactions with the targeted victims in order to create unique structural patterns that can later be used as fingerprints to re-identify the victims and infer private information about them. In this project, we will focus on providing methods for safely releasing structural information about the social network, accounting for, and counteracting, the presence of active adversaries. Given that social networks are inherently dynamic, and numerous analysis tasks require information on the evolution of the social graph over time, we will focus on techniques allowing to release updates on the structural information as the network evolves. We will first study how the dynamic nature of the networks and the release process can be exploited by active adversaries to strengthen their attacks. Then, considering the new vulnerabilities detected, we will define novel ways to quantify privacy in the dynamic scenario. The new privacy properties will be the basis for new models and algorithms allowing OSN owners to safely release information in two manners: (1) periodically publishing anonymised versions of the dynamic social graph, and (2) answering structural queries about the network. The proposed methods will be incremental, in the sense that as the network evolves and new information is released, each new piece of information will integrate with the previously released ones in such a manner that the privacy properties are globally satisfied.Our results will contribute to close the gap between the nature of social network data and the methods available to OSN owners for safely releasing this data to researchers, business partners and competent institutions. At the same time, OSN users will have increased privacy guarantees thanks to the new techniques counteracting the actions of active adversaries.