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 revealed from 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 transaction may reveal sensitive information about other individuals not involved in any fraud. In this paper, we propose an approach for link discovery in a privacy-preserving manner. We show how the problem can be reduced to finding the transitive closure of a graph. A secure split-matrix multiplication protocol based on secure scalar product computations is proposed to find the transitive closure. We analyze the performance and usability of the proposed approach.