Cryptology ePrint Archive: Report 2018/579

PIR-PSI: Scaling Private Contact Discovery

Daniel Demmler and Peter Rindal and Mike Rosulek and Ni Trieu

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. Naive 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.

Category / Keywords: cryptographic protocols / private set intersection, pir, contact discovery

Original Publication (with minor differences): PETS 2018

Date: received 5 Jun 2018, last revised 11 Jul 2018

Contact author: rosulekm at eecs oregonstate edu

Available format(s): PDF | BibTeX Citation

Version: 20180711:203603 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]