Communication-efficient private distance calculation based on oblivious transfer extensions

摘要

We propose a general framework for computing privacy-preserving distance metrics (PPDM) in the two-party setting in order to improve communication complexity by benefiting from 1-out-of-n oblivious transfers. We implement privacy-preserving Euclidean distance, Cosine similarity and Edit distance protocols while the PPDM framework is easily extendable to address other distance measures. These protocols have direct applications in privacy-preserving one-to-many biometric identification in which two parties known as the client and the server want to find the best match between their inputs. The client's input is compared to all the records in the server's database. We use the semi-honest adversary threat model. We extensively evaluate our PPDM framework. And, we theoretically show the improvement of PPDM over related work.