PIR-PSI: Scaling Private Contact Discovery
Authors: Daniel Demmler (TU Darmstadt), Peter Rindal (Oregon State University), Mike Rosulek (Oregon State University), Ni Trieu (Oregon State University)
Volume: 2018
Issue: 4
Pages: 159–178
DOI: https://doi.org/10.1515/popets-2018-0037
Abstract: An important initialization step in many social-networking applications is contact discovery, which allows a user of the service to identify which of its existing social contacts also use the service. Naïve approaches to contact discovery reveal a user’s entire set of social/professional contacts to the service, presenting a significant tension between functionality and privacy. In this work, we present a system for private contact discovery, in which the client learns only the intersection of its own contact list and a server’s user database, and the server learns only the (approximate) size of the client’s list. The protocol is specifically tailored to the case of a small client set and large user database. Our protocol has provable security guarantees and combines new ideas with state-of-the-art techniques from private information retrieval and private set intersection. We report on a highly optimized prototype implementation of our system, which is practical on real-world set sizes. For example, contact discovery between a client with 1024 contacts and a server with 67 million user entries takes 1.36 sec (when using server multi-threading) and uses only 4.28 MiB of communication.
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
