Paper 2023/758

Scaling Mobile Private Contact Discovery to Billions of Users

Laura Hetz, TU Darmstadt
Thomas Schneider, TU Darmstadt
Christian Weinert, Royal Holloway University of London

Mobile contact discovery is a convenience feature of messengers such as WhatsApp or Telegram that helps users to identify which of their existing contacts are registered with the service. Unfortunately, the contact discovery implementation of many popular messengers massively violates the users' privacy as demonstrated by Hagen et al. (NDSS '21, ACM TOPS '23). Unbalanced private set intersection (PSI) protocols are a promising cryptographic solution to realize mobile private contact discovery, however, state-of-the-art protocols do not scale to real-world database sizes with billions of registered users in terms of communication and/or computation overhead. In our work, we make significant steps towards truly practical large-scale mobile private contact discovery. For this, we combine and substantially optimize the unbalanced PSI protocol of Kales et al. (USENIX Security '19) and the private information retrieval (PIR) protocol of Kogan and Corrigan-Gibbs (USENIX Security '21). Our resulting protocol has a total communication overhead that is sublinear in the size of the server's user database and also has sublinear online runtimes. We optimize our protocol by introducing database partitioning and efficient scheduling of user queries. To handle realistic change rates of databases and contact lists, we propose and evaluate different possibilities for efficient updates. We implement our protocol on smartphones and measure online runtimes of less than 2s to query up to 1024 contacts from a database with more than two billion entries. Furthermore, we achieve a reduction in setup communication up to factor 32x compared to state-of-the-art mobile private contact discovery protocols.

Available format(s)
Publication info
Published elsewhere. Minor revision. ESORICS 2023
Mobile Contact DiscoveryPrivate Set IntersectionPrivate Information Retrieval
Contact author(s)
laura hetz @ encrypto cs tu-darmstadt de
schneider @ encrypto cs tu-darmstadt de
christian weinert @ rhul ac uk
2023-10-11: revised
2023-05-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Laura Hetz and Thomas Schneider and Christian Weinert},
      title = {Scaling Mobile Private Contact Discovery to Billions of Users},
      howpublished = {Cryptology ePrint Archive, Paper 2023/758},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.