Paper 2023/1218

Arke: Scalable and Byzantine Fault Tolerant Privacy-Preserving Contact Discovery

Nicolas Mohnblatt, Geometry
Alberto Sonnino, Mysten Labs, University College London
Kobi Gurkan, Geometry
Philipp Jovanovic, University College London

Contact discovery is a crucial component of social applications, facilitating interactions between registered contacts. This work introduces Arke, a novel approach to contact discovery that addresses the limitations of existing solutions in terms of privacy, scalability, and reliance on trusted third parties. Arke ensures the unlinkability of user interactions, mitigates enumeration attacks, and operates without single points of failure or trust. Notably, Arke is the first contact discovery system whose performance is independent of the total number of users and the first that can operate in a Byzantine setting. It achieves its privacy goals through an unlinkable handshake mechanism built on top of an identity-based non-interactive key exchange. By leveraging a custom distributed architecture, Arke forgoes the expense of consensus to achieve scalability while maintaining consistency in a Byzantine fault tolerant environment. Performance evaluations demonstrate that Arke can support enough throughput to operate at a planetary scale while maintaining sub-second latencies in a large geo-distributed setting.

Note: This update describes the process of verifying user private keys and includes a more complete related works section.

Available format(s)
Cryptographic protocols
Publication info
contact discoveryprivacy-preserving technologybyzantine fault tolerantdistributed
Contact author(s)
nico @ geometry xyz
alberto sonnino @ ucl ac uk
kobi @ geometry xyz
p jovanovic @ ucl ac uk
2023-12-01: last of 2 revisions
2023-08-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nicolas Mohnblatt and Alberto Sonnino and Kobi Gurkan and Philipp Jovanovic},
      title = {Arke: Scalable and Byzantine Fault Tolerant Privacy-Preserving Contact Discovery},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1218},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.