The impact of unlinkability on adversarial community detection

effects and countermeasures

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

3 Citations (Scopus)

Abstract

We consider the threat model of a mobile-adversary drawn from contemporary computer security literature, and explore the dynamics of community detection and hiding in this setting. Using a real-world social network, we examine the extent of network topology information an adversary is required to gather in order to accurately ascertain community membership information. We show that selective surveillance strategies can improve the adversary's efficiency over random wiretapping. We then consider possible privacy preserving defenses; using anonymous communications helps, but not much; however, the use of counter-surveillance techniques can significantly reduce the adversary's ability to learn community membership. Our analysis shows that even when using anonymous communications an adversary placing a selectively chosen 8% of the nodes of this network under surveillance (using key-logger probes) can de-anonymize the community membership of as much as 50% of the network. Uncovering all community information with targeted selection requires probing as much as 75% of the network. Finally, we show that a privacy conscious community can substantially disrupt community detection using only local knowledge even while facing up to the asymmetry of a completely knowledgeable mobile-adversary.

Original languageEnglish
Title of host publicationPrivacy Enhancing Technologies - 10th International Symposium, PETS 2010, Proceedings
Place of PublicationBerlin
PublisherSpringer
Pages253-272
Number of pages20
Volume6205
ISBN (Print)3642145264, 9783642145261
DOIs
Publication statusPublished - 16 Aug 2010
Event10th International Symposium on Privacy Enhancing Technologies, PETS 2010 - Berlin, Germany
Duration: 21 Jul 201023 Jul 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6205 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Symposium on Privacy Enhancing Technologies, PETS 2010
CountryGermany
CityBerlin
Period21/07/1023/07/10

Fingerprint

Community Detection
Countermeasures
Surveillance
Communication
Security of data
Topology
Computer Security
Privacy Preserving
Network Topology
Social Networks
Privacy
Asymmetry
Probe
Community
Vertex of a graph

Keywords

  • social network
  • betweenness centrality
  • community detection
  • threat model
  • community detection algorithm
  • data privacy
  • electric network topology
  • adversarial community detection
  • anonymous communication
  • surveillance techniques

Cite this

Nagaraja, S. (2010). The impact of unlinkability on adversarial community detection: effects and countermeasures. In Privacy Enhancing Technologies - 10th International Symposium, PETS 2010, Proceedings (Vol. 6205 , pp. 253-272). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6205 LNCS). Berlin: Springer. https://doi.org/10.1007/978-3-642-14527-8_15
Nagaraja, Shishir. / The impact of unlinkability on adversarial community detection : effects and countermeasures. Privacy Enhancing Technologies - 10th International Symposium, PETS 2010, Proceedings. Vol. 6205 Berlin : Springer, 2010. pp. 253-272 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{a084d971ac34465490883012dfe70e8e,
title = "The impact of unlinkability on adversarial community detection: effects and countermeasures",
abstract = "We consider the threat model of a mobile-adversary drawn from contemporary computer security literature, and explore the dynamics of community detection and hiding in this setting. Using a real-world social network, we examine the extent of network topology information an adversary is required to gather in order to accurately ascertain community membership information. We show that selective surveillance strategies can improve the adversary's efficiency over random wiretapping. We then consider possible privacy preserving defenses; using anonymous communications helps, but not much; however, the use of counter-surveillance techniques can significantly reduce the adversary's ability to learn community membership. Our analysis shows that even when using anonymous communications an adversary placing a selectively chosen 8{\%} of the nodes of this network under surveillance (using key-logger probes) can de-anonymize the community membership of as much as 50{\%} of the network. Uncovering all community information with targeted selection requires probing as much as 75{\%} of the network. Finally, we show that a privacy conscious community can substantially disrupt community detection using only local knowledge even while facing up to the asymmetry of a completely knowledgeable mobile-adversary.",
keywords = "social network, betweenness centrality, community detection, threat model, community detection algorithm, data privacy, electric network topology, adversarial community detection, anonymous communication, surveillance techniques",
author = "Shishir Nagaraja",
year = "2010",
month = "8",
day = "16",
doi = "10.1007/978-3-642-14527-8_15",
language = "English",
isbn = "3642145264",
volume = "6205",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "253--272",
booktitle = "Privacy Enhancing Technologies - 10th International Symposium, PETS 2010, Proceedings",

}

Nagaraja, S 2010, The impact of unlinkability on adversarial community detection: effects and countermeasures. in Privacy Enhancing Technologies - 10th International Symposium, PETS 2010, Proceedings. vol. 6205 , Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6205 LNCS, Springer, Berlin, pp. 253-272, 10th International Symposium on Privacy Enhancing Technologies, PETS 2010, Berlin, Germany, 21/07/10. https://doi.org/10.1007/978-3-642-14527-8_15

The impact of unlinkability on adversarial community detection : effects and countermeasures. / Nagaraja, Shishir.

Privacy Enhancing Technologies - 10th International Symposium, PETS 2010, Proceedings. Vol. 6205 Berlin : Springer, 2010. p. 253-272 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6205 LNCS).

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

TY - GEN

T1 - The impact of unlinkability on adversarial community detection

T2 - effects and countermeasures

AU - Nagaraja, Shishir

PY - 2010/8/16

Y1 - 2010/8/16

N2 - We consider the threat model of a mobile-adversary drawn from contemporary computer security literature, and explore the dynamics of community detection and hiding in this setting. Using a real-world social network, we examine the extent of network topology information an adversary is required to gather in order to accurately ascertain community membership information. We show that selective surveillance strategies can improve the adversary's efficiency over random wiretapping. We then consider possible privacy preserving defenses; using anonymous communications helps, but not much; however, the use of counter-surveillance techniques can significantly reduce the adversary's ability to learn community membership. Our analysis shows that even when using anonymous communications an adversary placing a selectively chosen 8% of the nodes of this network under surveillance (using key-logger probes) can de-anonymize the community membership of as much as 50% of the network. Uncovering all community information with targeted selection requires probing as much as 75% of the network. Finally, we show that a privacy conscious community can substantially disrupt community detection using only local knowledge even while facing up to the asymmetry of a completely knowledgeable mobile-adversary.

AB - We consider the threat model of a mobile-adversary drawn from contemporary computer security literature, and explore the dynamics of community detection and hiding in this setting. Using a real-world social network, we examine the extent of network topology information an adversary is required to gather in order to accurately ascertain community membership information. We show that selective surveillance strategies can improve the adversary's efficiency over random wiretapping. We then consider possible privacy preserving defenses; using anonymous communications helps, but not much; however, the use of counter-surveillance techniques can significantly reduce the adversary's ability to learn community membership. Our analysis shows that even when using anonymous communications an adversary placing a selectively chosen 8% of the nodes of this network under surveillance (using key-logger probes) can de-anonymize the community membership of as much as 50% of the network. Uncovering all community information with targeted selection requires probing as much as 75% of the network. Finally, we show that a privacy conscious community can substantially disrupt community detection using only local knowledge even while facing up to the asymmetry of a completely knowledgeable mobile-adversary.

KW - social network

KW - betweenness centrality

KW - community detection

KW - threat model

KW - community detection algorithm

KW - data privacy

KW - electric network topology

KW - adversarial community detection

KW - anonymous communication

KW - surveillance techniques

UR - http://www.scopus.com/inward/record.url?scp=77955446837&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14527-8_15

DO - 10.1007/978-3-642-14527-8_15

M3 - Conference contribution book

SN - 3642145264

SN - 9783642145261

VL - 6205

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 253

EP - 272

BT - Privacy Enhancing Technologies - 10th International Symposium, PETS 2010, Proceedings

PB - Springer

CY - Berlin

ER -

Nagaraja S. The impact of unlinkability on adversarial community detection: effects and countermeasures. In Privacy Enhancing Technologies - 10th International Symposium, PETS 2010, Proceedings. Vol. 6205 . Berlin: Springer. 2010. p. 253-272. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-14527-8_15