Abstract:

Alice and Bob posses sequences x and y respectively and would like to compute the --- distance, namely --- 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-Lindenstrauss embedding into the --- space. Then, it performs secure two-party computation of --- distance 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.