Existing protocols for private nearest neighbor search re- quire heavy cryptographic tools, resulting in poor practical performance or large client overheads. In this paper, we present the first lightweight protocol for private nearest neighbor search. Our protocol is instantiated using two non-colluding servers, each holding a replica of the database. The protocol supports an arbitrary number of clients simultaneously querying the database via these servers. Each query is only a single round of communication for the client and does not require any communication between servers.
If at least one of the servers is non-colluding, we ensure that (1) no information is revealed on the client’s query, (2) the total communication between the client and the servers is sublinear in the database size, and (3) each query answer only leaks a small and precisely quantified amount of information about the database to the client, even when the client is acting maliciously.
We implement our protocol and report its performance on real-world data. Our construction requires between 10 and 30 seconds of query latency over large databases of 10M feature vectors. Client overhead remained under 10μs of processing time per query and typically less than 4 MB of communication, depending on parameters.