Secure similarity joins using fully homomorphic encryption
Mateus S. H. Cruz, Toshiyuki Amagasa, Chiemi Watanabe, Wenjie Lu, Hiroyuki Kitagawa · 2017
Similarity joins are important database operations that can identify pairs of roughly similar records. Due to their many applications (e.g., duplicate elimination and plagiarism detection), a number of algorithms have been created to enhance similarity joins, especially in terms of performance. However, in some cases, the privacy of the data being joined also becomes an important aspect to consider, as leaking sensitive information can result in grave consequences for individuals, enterprises and governmental organizations. We propose a protocol for secure execution of similarity joins that is based on fully homomorphic cryptosystems, which are resistant to a number of attacks and provide flexibility to calculate the similarity between encrypted records. We also consider the adaptation of filter techniques to improve the efficiency of the protocol by reducing the number of record pairs that are compared. In addition, we exploit modern hardware to parallelize the solution and evaluate the performance of the proposal using real datasets.