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

Nicolas Mohnblatt; Alberto Sonnino; Kobi Gurkan; Philipp Jovanovic

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

Abstract

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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: contact discovery privacy-preserving technology byzantine fault tolerant distributed
Contact author(s): nico @ geometry xyz
alberto sonnino @ ucl ac uk
kobi @ geometry xyz
p jovanovic @ ucl ac uk
History: 2023-12-01: last of 2 revisions; 2023-08-10: received; See all versions
Short URL: https://ia.cr/2023/1218
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1218,
      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},
      url = {https://eprint.iacr.org/2023/1218}
}