Quantification of de-anonymization risks in social networks

Wei Han Lee, Changchang Liu, Shouling Ji, Prateek Mittal, Ruby Lee

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

2 Scopus citations

Abstract

The risks of publishing privacy-sensitive data have received considerable attention recently. Several deanonymization attacks have been proposed to re-identify individuals even if data anonymization techniques were applied. However, there is no theoretical quantification for relating the data utility that is preserved by the anonymization techniques and the data vulnerability against de-anonymization attacks. In this paper, we theoretically analyze the de-anonymization attacks and provide conditions on the utility of the anonymized data (denoted by anonymized utility) to achieve successful de-anonymization. To the best of our knowledge, this is the first work on quantifying the relationships between anonymized utility and de-anonymization capability. Unlike previous work, our quantification analysis requires no assumptions about the graph model, thus providing a general theoretical guide for developing practical deanonymization/anonymization techniques. Furthermore, we evaluate state-of-the-art de-anonymization attacks on a real-world Facebook dataset to show the limitations of previous work. By comparing these experimental results and the theoretically achievable de-anonymization capability derived in our analysis, we further demonstrate the ineffectiveness of previous de-anonymization attacks and the potential of more powerful de-anonymization attacks in the future.

Original languageEnglish (US)
Title of host publicationICISSP 2017 - Proceedings of the 3rd International Conference on Information Systems Security and Privacy
EditorsPaolo Mori, Steven Furnell, Olivier Camp
PublisherSciTePress
Pages126-135
Number of pages10
ISBN (Electronic)9789897582097
StatePublished - Jan 1 2017
Event3rd International Conference on Information Systems Security and Privacy, ICISSP 2017 - Porto, Portugal
Duration: Feb 19 2017Feb 21 2017

Publication series

NameICISSP 2017 - Proceedings of the 3rd International Conference on Information Systems Security and Privacy
Volume2017-January

Other

Other3rd International Conference on Information Systems Security and Privacy, ICISSP 2017
CountryPortugal
CityPorto
Period2/19/172/21/17

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems
  • Safety, Risk, Reliability and Quality
  • Computer Science Applications

Keywords

  • Anonymization Utility
  • De-anonymization Capability
  • Structure-based De-anonymization Attacks
  • Theoretical Bounds

Cite this