Myco: Unlocking Polylogarithmic Accesses in Metadata-Private Messaging

Darya Kaviani; Deevashwer Rathee; Bhargav Annem; Raluca Ada Popa

Paper 2025/687

Myco: Unlocking Polylogarithmic Accesses in Metadata-Private Messaging

Darya Kaviani

, University of California, Berkeley

Deevashwer Rathee, University of California, Berkeley

Bhargav Annem

, California Institute of Technology

Raluca Ada Popa

, University of California, Berkeley

Abstract

As billions of people rely on end-to-end encrypted messaging, the exposure of metadata, such as communication timing and participant relationships, continues to deanonymize users. Asynchronous metadata-hiding solutions with strong cryptographic guarantees have historically been bottlenecked by quadratic $O(N^2)$ server computation in the number of users $N$ due to reliance on private information retrieval (PIR). We present Myco, a metadata-private messaging system that preserves strong cryptographic guarantees while achieving $O(N \log^2 N)$ efficiency. To achieve this, we depart from PIR and instead introduce an oblivious data structure through which senders and receivers privately communicate. To unlink reads and writes, we instantiate Myco in an asymmetric two-server distributed-trust model where clients write messages to one server tasked with obliviously transmitting these messages to another server, from which clients read. Myco achieves throughput improvements of up to 302x over multi-server and 2,219x over single-server state-of-the-art systems based on PIR.

Note: Full version

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. Major revision. IEEE Symposium on Security and Privacy 2025
Keywords: Privacy Anonymity Messaging Metadata ORAM
Contact author(s): daryakaviani @ berkeley edu
deevashwer @ berkeley edu
bannem @ caltech edu
raluca popa @ berkeley edu
History: 2025-04-18: revised; 2025-04-15: received; See all versions
Short URL: https://ia.cr/2025/687
License: CC BY

BibTeX

@misc{cryptoeprint:2025/687,
      author = {Darya Kaviani and Deevashwer Rathee and Bhargav Annem and Raluca Ada Popa},
      title = {Myco: Unlocking Polylogarithmic Accesses in Metadata-Private Messaging},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/687},
      year = {2025},
      url = {https://eprint.iacr.org/2025/687}
}