An information theoretic framework for active de-anonymization in social networks based on group memberships

Farhad Shirani, Siddharth Garg, Elza Erkip

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, a new mathematical formulation for the problem of de-anonymizing social network users by actively querying their membership in social network groups is introduced. In this formulation, the attacker has access to a noisy observation of the group membership of each user in the social network. When an unidentified victim visits a malicious website, the attacker uses browser history sniffing to make queries regarding the victim's social media activity. Particularly, it can make polar queries regarding the victim's group memberships and the victim's identity. The attacker receives noisy responses to her queries. The goal is to de-anonymize the victim with the minimum number of queries. Starting with a rigorous mathematical model for this active de-anonymization problem, an upper bound on the attacker's expected query cost is derived, and new attack algorithms are proposed which achieve this bound. These algorithms vary in computational cost and performance. The results suggest that prior heuristic approaches to this problem provide sub-optimal solutions.

Original languageEnglish (US)
Title of host publication55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages470-477
Number of pages8
ISBN (Electronic)9781538632666
DOIs
StatePublished - Jan 17 2018
Event55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017 - Monticello, United States
Duration: Oct 3 2017Oct 6 2017

Publication series

Name55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
Volume2018-January

Other

Other55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
CountryUnited States
CityMonticello
Period10/3/1710/6/17

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Signal Processing
  • Energy Engineering and Power Technology
  • Control and Optimization

Fingerprint Dive into the research topics of 'An information theoretic framework for active de-anonymization in social networks based on group memberships'. Together they form a unique fingerprint.

  • Cite this

    Shirani, F., Garg, S., & Erkip, E. (2018). An information theoretic framework for active de-anonymization in social networks based on group memberships. In 55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017 (pp. 470-477). (55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017; Vol. 2018-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ALLERTON.2017.8262775