Many of the activities in cyberspace, from social networking to the use of mobile apps, leave digital footprints compromising the users’ privacy.  As digital tracking technologies become more sophisticated and pervasive, there is a need to understand and quantify the users’ privacy risk, that is, what is the likelihood that users in cyberspace can be uniquely identified from their activities?

In this talk, we focus on de-anonymization attacks, where publicly and privately available information about users, represented as connectivity graphs, are leveraged to compromise user identities. We model the de-anonymization attack as a graph matching  problem in which  we have two correlated stochastic graphs the first of which has labeled vertices, whereas the second one is unlabeled. The goal is to recover the labels of the second graph by using the correlation structure. We explore how graph matching can be posed as a communications problem, and tools from information theory, communication theory and probability can be used to derive theoretical guarantees and algorithms for graph matching, thereby providing a framework for quantifying the privacy risk of users in the cyberspace.