Efficient privacy-preserving link discovery

Xiaoyun He, Jaideep Vaidya, Basit Shafiq, Nabil Adam, Evimaria Terzi, Tyrone Grandison

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

2 Citations (Scopus)

Abstract

Link discovery is a process of identifying association(s) among different entities included in a complex network structure. These association(s) may represent any interaction among entities, for example between people or even bank accounts. The need for link discovery arises in many applications including law enforcement, counter-terrorism, social network analysis, intrusion detection, and fraud detection. Given the sensitive nature of information that can be revealedfrom link discovery, privacy is a major concern from the perspective of both individuals and organizations. For example, in the context of financial fraud detection, linking transactions may reveal sensitive information about other individuals not involved in any fraud. It is known that link discovery can be done in a privacy-preserving manner by securely finding the transitive closure of a graph.We propose two very efficient techniques to find the transitive closure securely. The two protocols have varying levels of security and performance We analyze the performance and usability of the proposed approach in terms of both analytical and experimental results.

Original languageEnglish (US)
Title of host publication13th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2009
Pages16-27
Number of pages12
DOIs
StatePublished - Jul 23 2009
Event13th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2009 - Bangkok, Thailand
Duration: Apr 27 2009Apr 30 2009

Publication series

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

Other

Other13th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2009
CountryThailand
CityBangkok
Period4/27/094/30/09

Fingerprint

Fraud Detection
Transitive Closure
Terrorism
Privacy Preserving
Complex networks
Law enforcement
Intrusion detection
Electric network analysis
Network protocols
Law Enforcement
Social Network Analysis
Intrusion Detection
Complex Structure
Network Structure
Complex Networks
Usability
Linking
Privacy
Transactions
Experimental Results

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Efficiency
  • Link discovery
  • Privacy

Cite this

He, X., Vaidya, J., Shafiq, B., Adam, N., Terzi, E., & Grandison, T. (2009). Efficient privacy-preserving link discovery. In 13th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2009 (pp. 16-27). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5476 LNAI). https://doi.org/10.1007/978-3-642-01307-2_5
He, Xiaoyun ; Vaidya, Jaideep ; Shafiq, Basit ; Adam, Nabil ; Terzi, Evimaria ; Grandison, Tyrone. / Efficient privacy-preserving link discovery. 13th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2009. 2009. pp. 16-27 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{80313de3e12742c08b4fc7b620ff1b6d,
title = "Efficient privacy-preserving link discovery",
abstract = "Link discovery is a process of identifying association(s) among different entities included in a complex network structure. These association(s) may represent any interaction among entities, for example between people or even bank accounts. The need for link discovery arises in many applications including law enforcement, counter-terrorism, social network analysis, intrusion detection, and fraud detection. Given the sensitive nature of information that can be revealedfrom link discovery, privacy is a major concern from the perspective of both individuals and organizations. For example, in the context of financial fraud detection, linking transactions may reveal sensitive information about other individuals not involved in any fraud. It is known that link discovery can be done in a privacy-preserving manner by securely finding the transitive closure of a graph.We propose two very efficient techniques to find the transitive closure securely. The two protocols have varying levels of security and performance We analyze the performance and usability of the proposed approach in terms of both analytical and experimental results.",
keywords = "Efficiency, Link discovery, Privacy",
author = "Xiaoyun He and Jaideep Vaidya and Basit Shafiq and Nabil Adam and Evimaria Terzi and Tyrone Grandison",
year = "2009",
month = "7",
day = "23",
doi = "10.1007/978-3-642-01307-2_5",
language = "English (US)",
isbn = "3642013066",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "16--27",
booktitle = "13th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2009",

}

He, X, Vaidya, J, Shafiq, B, Adam, N, Terzi, E & Grandison, T 2009, Efficient privacy-preserving link discovery. in 13th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2009. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5476 LNAI, pp. 16-27, 13th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2009, Bangkok, Thailand, 4/27/09. https://doi.org/10.1007/978-3-642-01307-2_5

Efficient privacy-preserving link discovery. / He, Xiaoyun; Vaidya, Jaideep; Shafiq, Basit; Adam, Nabil; Terzi, Evimaria; Grandison, Tyrone.

13th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2009. 2009. p. 16-27 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5476 LNAI).

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

TY - GEN

T1 - Efficient privacy-preserving link discovery

AU - He, Xiaoyun

AU - Vaidya, Jaideep

AU - Shafiq, Basit

AU - Adam, Nabil

AU - Terzi, Evimaria

AU - Grandison, Tyrone

PY - 2009/7/23

Y1 - 2009/7/23

N2 - Link discovery is a process of identifying association(s) among different entities included in a complex network structure. These association(s) may represent any interaction among entities, for example between people or even bank accounts. The need for link discovery arises in many applications including law enforcement, counter-terrorism, social network analysis, intrusion detection, and fraud detection. Given the sensitive nature of information that can be revealedfrom link discovery, privacy is a major concern from the perspective of both individuals and organizations. For example, in the context of financial fraud detection, linking transactions may reveal sensitive information about other individuals not involved in any fraud. It is known that link discovery can be done in a privacy-preserving manner by securely finding the transitive closure of a graph.We propose two very efficient techniques to find the transitive closure securely. The two protocols have varying levels of security and performance We analyze the performance and usability of the proposed approach in terms of both analytical and experimental results.

AB - Link discovery is a process of identifying association(s) among different entities included in a complex network structure. These association(s) may represent any interaction among entities, for example between people or even bank accounts. The need for link discovery arises in many applications including law enforcement, counter-terrorism, social network analysis, intrusion detection, and fraud detection. Given the sensitive nature of information that can be revealedfrom link discovery, privacy is a major concern from the perspective of both individuals and organizations. For example, in the context of financial fraud detection, linking transactions may reveal sensitive information about other individuals not involved in any fraud. It is known that link discovery can be done in a privacy-preserving manner by securely finding the transitive closure of a graph.We propose two very efficient techniques to find the transitive closure securely. The two protocols have varying levels of security and performance We analyze the performance and usability of the proposed approach in terms of both analytical and experimental results.

KW - Efficiency

KW - Link discovery

KW - Privacy

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

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

U2 - 10.1007/978-3-642-01307-2_5

DO - 10.1007/978-3-642-01307-2_5

M3 - Conference contribution

AN - SCOPUS:67650702537

SN - 3642013066

SN - 9783642013065

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

SP - 16

EP - 27

BT - 13th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2009

ER -

He X, Vaidya J, Shafiq B, Adam N, Terzi E, Grandison T. Efficient privacy-preserving link discovery. In 13th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2009. 2009. p. 16-27. (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-01307-2_5