SPN2: Single-Sided Privacy Preserving Nearest Neighbor and its Application to Face Recognition

We address the privacy concerns that raise when running a nearest neighbor (NN) search on confidential data in a surveillance system composed of a client and a server.
The proposed privacy preserving NN search uses Boneh-Goh-Nissim encryption to hide both the query data captured by the client and the database records stored in the server.
As opposed to state–of–the–art approaches which rely on a large number of interactions, this encryption enables the client to fully outsource the NN computation to the server;
hence, ensuring a single-sided private computation, and resulting in a one–round protocol between the server and the client. We analyze the practical feasibility of this algorithm
on a face recognition problem. We formally prove and experimentally show that the resulting system maintains the recognition rate while fully preserving the privacy of both
the database and the acquired faces.