Sacha Servan-Schreiber

February 18, 2021 at 11:00 AM on Zoom / Soda Hall

Private Nearest Neighbor Search with Sublinear Communication

Abstract: Nearest neighbor search is a fundamental building-block for a wide range of applications. A privacy-preserving protocol for nearest neighbor search involves a set of clients who send queries to a remote database. Each client retrieves the nearest neighbor(s) to its query in the database without revealing any information about the query. To ensure database privacy, clients must learn as little as possible beyond the query answer, even if behaving maliciously by deviating from protocol. Existing protocols for private nearest neighbor search require heavy cryptographic tools, resulting in high computational and bandwidth overheads. In this talk, I will 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. Our design supports an arbitrary number of clients simultaneously querying the database through the two servers. Each query consists of a single round of communication between the client and the two servers. No communication is required between the servers to answer queries. If at least one of the servers is non-colluding, our protocol ensures 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 bounded amount of information about the database to the client, even if the client is malicious. Paper ePrint: https://eprint.iacr.org/2021/1157

Bio: Sacha is a third year PhD student at MIT CSAIL, working on privacy-preserving systems and applied cryptography. Sacha is especially interested in building systems that have the potential to improve user anonymity and privacy in online ecosystems. Personal website: http://sachaservanschreiber.com/

Security Lab