iLunch Talk (Nov 20) A Concentration of Measure Approach to Social Network Deanonymization

What: A Concentration of Measure Approach to Social Network Deanonymization 

When: Friday November 20, 12 noon – 1:00 pm

Where: Zoom Meeting ID:  860 2707 4223      Password: 198846

Who: Farhad Shirani
Affiliation: Assistant Professor at the Electrical and Computer Engineering Department at North Dakota State University

Abstract: As web tracking technologies become more sophisticated and pervasive, there is a critical need to understand and quantify web users’ privacy risks, that is, what is the likelihood that users on the internet can be uniquely identified from their online activities? In this talk, we develop an information theoretic framework to study the fundamental limits of web privacy and investigate the design and analysis of practical deanonymization attacks in social networks and database systems. This framework puts forth a systematic technique for deriving theoretical guarantees for web privacy in several attack scenarios of interest such as online fingerprinting, social network deanonymization, and database deanonymization. In the first part of the talk, we study online fingerprinting attacks, which occur when a victim visits a malicious website, and the attacker queries the victim’s device for deanonymization purposes. Through an analogy with the well-studied problem of data transmission over channels with feedback, we propose an attack algorithm and derive sufficient conditions for its success. We further derive necessary conditions for successful deanonymization by providing an information theoretic converse. We show that the optimal expected number of queries needed for deanonymization, which determines the time it takes for the attacker to identify the victim, grows logarithmically in the number of users in the network. We characterize the logarithmic coefficient as a function of the network statistics. In the second part of the talk, we study social network deanonymization, which is modeled mathematically as a graph matching problem. We expand the notion of typicality of sequences, which is widely used in information theory, to typicality of graphs. Building upon this, we propose a typicality-based graph matching algorithm and derive necessary and sufficient conditions under which social network deanonymization is possible.

Bio: Farhad Shirani Chaharsooghi is currently an Assistant Professor at the Electrical and Computer Engineering Department at North Dakota State University. Previously, he was a research Assistant Professor at the New York University from 2017 to 2020. He has served as Lecturer and Postdoctoral Research Fellow at the University of Michigan in 2017. His Ph.D. in Electrical Engineering was completed at the University of Michigan in 2017.  He also received his M.Sc. in Electrical Engineering and M.Sc. in Applied Mathematics at the University of Michigan in 2012 and 2016, respectively. His research interests are in the areas of privacy and security, wireless communications, information theory, and machine learning

Host: School of Computing and Information Science, University of Maine

For questions: