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 Scopus citations

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 - 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

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Efficiency
  • Link discovery
  • Privacy

Fingerprint Dive into the research topics of 'Efficient privacy-preserving link discovery'. Together they form a unique fingerprint.

  • 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