Abstract

Entity resolution is the task of disambiguating records that refer to the same entity in the real world. In this work, we explore adapting one of the most efficient and accurate Jaccard-based entity resolution algorithms - PPJoin, to the private domain via end-to-end homomorphic encryption. Towards this, we present our precise adaptation: HE-PPJoin that details certain subtle data structure modifications and algorithmic additions needed for correctness and privacy. We implement HE-PPJoin by extending the PALISADE (now merged with OpenFHE) open-source, homomorphic encryption library and perform experiments to analyze its accuracy and incurred overhead. Furthermore, we directly compare HE-PPJoin against P4Join, an existing privacy-preserving variant of PPJoin, which uses hashing for raw content obfuscation (encryption), by demonstrating a rigorous analysis of the efficiency, accuracy, and privacy …

Date

July 3, 2023

Authors

Tanmay Ghai, Yixiang Yao, Srivatsan Ravi

Conference

2023 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW)

Pages

117-124

Publisher

IEEE