Paper 2018/579

PIR-PSI: Scaling Private Contact Discovery

Daniel Demmler, Peter Rindal, Mike Rosulek, and Ni Trieu


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. PETS 2018
private set intersectionpircontact discovery
Contact author(s)
rosulekm @ eecs oregonstate edu
2018-07-11: revised
2018-06-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Demmler and Peter Rindal and Mike Rosulek and Ni Trieu},
      title = {{PIR}-{PSI}: Scaling Private Contact Discovery},
      howpublished = {Cryptology ePrint Archive, Paper 2018/579},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.