Paper 2018/579
PIR-PSI: Scaling Private Contact Discovery
Daniel Demmler, Peter Rindal, 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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. PETS 2018
- Keywords
- private set intersectionpircontact discovery
- Contact author(s)
- rosulekm @ eecs oregonstate edu
- History
- 2018-07-11: revised
- 2018-06-06: received
- See all versions
- Short URL
- https://ia.cr/2018/579
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/579,
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},
url = {https://eprint.iacr.org/2018/579}
}