Privacy-preserving approximation of L1 distance for multimedia applications

Alice and Bob possess sequences x and y respectively and would like to compute the ℓ₁ distance, namely || x - y ||₁ under privacy and communication constraints. The privacy constraint requires that Alice and Bob do not reveal their data to each other. The communication constraint requires that they accomplish the secure distance calculation with a small number of protocol transmissions and key exchanges. This paper describes and analyzes a privacy-preserving approximation protocol for the ℓ₁ distance that keeps the communication overhead manageable by performing a Johnson-Lindethe ℓ₁ distance that keeps the communication overhead manageable by performing a Johnson-Lindenstrauss embedding into the ℓ₂ space. Then, it performs secure two-party computation of ℓ₂ distances using Paillier homomorphic encryption. The protocol is implemented for private querying of face images, while maintaining a low communication overhead between the queryingnstrauss embedding into the ℓ₂ space. Then, it performs secure two-party computation of ℓ₂ distances using Paillier homomorphic encryption. The protocol is implemented for private querying of face images, while maintaining a low communication overhead between the querying party and a remote database of face feature vectors.

1. INTRODUCTION

Consider a private querying system in which a user wants to check if his query image matches one or more images in a database of images. The querying device (Alice), can extract features from the user's image and match these against a feature vector database (Bob). A common distance metric for matching image features is the Manhattan distance, or distance. Suppose that the matching criterion is that the distance between Alice's feature vector and one of Bob's feature vectors is below a certain threshold. However, private querying imposes some constraints on how this matching is performed. Firstly, for the user's privacy, Bob must not know anything about Alice's feature vector. Secondly, for security of images in the database, Alice must not find out anything about Bob's feature vectors. Thirdly, for practical usage, the communication protocol employed by Alice and Bob should not incur a large transmission overhead. We propose a secure approximation protocol to address privacy and communication constraints in problems of this kind.