Myco: Unlocking Polylogarithmic Accesses in Metadata-Private Messaging

Myco: Unlocking Polylogarithmic Accesses in Metadata-Private Messaging

Speakers: Darya Kaviani, Deevashwer Rathee, Bhargav Annem, Raluca Ada Popa

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=SU9widjkDzo

Overview

In an era where end-to-end encrypted messaging has become commonplace, the focus of privacy research is increasingly shifting from message content to metadata. This talk, "Myco: Unlocking Polylogarithmic Accesses in Metadata-Private Messaging," presented by Darya Kaviani and her collaborators, addresses the critical yet often overlooked vulnerability of metadata leakage in secure communication systems. While applications like Signal and WhatsApp effectively shield message content from adversaries, the "who, when, and how many" details of communication remain exposed, offering a rich vein of intelligence for sophisticated attackers like the NSA, as highlighted by chilling quotes from former intelligence officials.

Myco proposes a groundbreaking solution to this pervasive problem, aiming to achieve what prior works have struggled with: simultaneous cryptographic privacy for metadata, client asynchrony (offline access), and near-linear server overhead in the number of users (N). This ambitious goal, dubbed the "trillemma" by the researchers, has historically seen systems sacrifice one or more of these crucial properties. Myco claims to resolve this trillemma, offering a practical and highly efficient metadata-private messaging system.

The core innovation of Myco lies in its novel system architecture, which leverages an asymmetric distributed trust setup and a modified Oblivious RAM (ORAM) data structure. By decoupling read and write operations across two non-colluding servers and introducing techniques like unbiasable writes and read-static messaging trees, Myco dramatically reduces server overhead. The result is an impressive throughput improvement of two to three orders of magnitude over existing Private Information Retrieval (PIR) based systems, making truly metadata-private messaging a tangible reality.

Background

▶ Watch: Introduction: The critical need for metadata privacy (0:00)

The concept of metadata privacy stems from the recognition that even with strong end-to-end encryption for message content, the patterns and associations of communication can reveal highly sensitive information. As former NSA general counsel Stuart Baker famously stated, "Metadata absolutely tells you everything about somebody's life. If you have enough metadata, you don't really need content." General Michael Hayden, former NSA and CIA director, went further, asserting, "we kill people based on metadata." Empirical evidence supports these claims, with studies showing that NSA can derive 25,000 people's networks from just one person's call metadata, and tweet metadata alone identifies users with 96.7% accuracy. This underscores the urgent need for solutions that protect not just the "what" but also the "who, when, and how" of digital interactions.

Prior attempts to achieve metadata privacy have generally fallen into a "trillemma," struggling to simultaneously deliver three key properties:

1. Cryptographic Privacy: Ensuring that metadata is indistinguishable to an adversary, even if they compromise servers.
2. Asynchrony: Allowing clients to go offline temporarily without missing messages or compromising privacy.
3. Near-Linear Server Overhead: Maintaining efficiency, meaning server work scales roughly linearly with the number of users (N), avoiding performance bottlenecks.

Various approaches have explored different corners of this trillemma:

• Traditional Mixnets: Offer cryptographic privacy but often lack asynchrony and struggle with efficiency, leading to near-linear server overhead.
• DC-networks: Provide strong cryptographic privacy but typically lack asynchrony and can be inefficient.
• Flexible Mixnets and Trusted Hardware-based Solutions: Offer asynchrony and near-linear server overhead but often compromise on cryptographic privacy, relying on trust in hardware or specific network participants.
• Cryptographic Mixnets: Combine cryptographic privacy and near-linear server overhead but usually without asynchrony.
• Private Information Retrieval (PIR) Based Systems: These systems are a cryptographic primitive where a client can query a database for a specific index I without revealing I to the server. They offer strong cryptographic privacy and asynchrony, as clients can retrieve messages without revealing which ones they're interested in. However, a major drawback of existing PIR-based messaging systems is their quadratic server overhead (O(N^2)) in the number of system users, which severely limits their throughput and scalability. This quadratic overhead typically arises from linear scans over the entire database to hide access patterns.

Myco specifically targets the limitations of PIR-based systems, aiming to retain their cryptographic privacy and asynchrony while dramatically improving server efficiency to an asymptotically better O(N log^2 N), thereby solving the trillemma.

Key Findings

▶ Watch: Myco's breakthrough: Achieving N log^2 N server overhead (2:35)

The Myco project presents several pivotal findings and contributions that collectively resolve the long-standing trillemma in metadata-private messaging:

1. Polylogarithmic Server Overhead: Myco achieves a server overhead of O(N log^2 N), a significant improvement over the quadratic (O(N^2)) overhead of prior PIR-based systems. This asymptotic improvement translates into concrete performance gains, making metadata-private messaging practical for large user bases.
2. Unprecedented Throughput: Through its optimized architecture, Myco demonstrates a 11x to 302x throughput improvement over state-of-the-art two-server PIR systems (like TLC++) and a 106x to 2,219x improvement over single-server PIR systems (like PUNG++). This marks Myco as the first practical system to achieve all three properties of the trillemma.
3. Novel Asymmetric Distributed Trust Model: Myco introduces an asymmetric distributed trust setup with two non-colluding servers. This design allows for the unlinkability of reads and writes by leveraging the servers differently, with one server handling writes and the other handling reads, while ensuring messages are transferred obliviously between them.
4. Read-Static Messaging Tree: A key innovation is the adaptation of Path ORAM into a read-static messaging tree. Unlike traditional ORAM, which requires write-backs to re-randomize message locations after each read, Myco's design leverages the one-time read nature of messages to eliminate the need for client-initiated write-backs, simplifying the protocol and enhancing privacy.
5. Unbiasable Writes and Oblivious Batch Evictions: Myco employs techniques like unbiasable writes using a server-side pseudo-random function (PRF) to prevent malicious clients from distorting message distributions and overflowing buckets. Furthermore, oblivious batch evictions allow Server 1 to write to Server 2's tree without revealing sensitive location information, crucial for maintaining privacy in the distributed setup.
6. Hybrid Notification and Messaging System: To optimize for both cross-epoch obliviousness and efficient message retrieval, Myco proposes a hybrid system. A Matrix Myco component handles lightweight, lambda-bit notifications, allowing clients to efficiently discover which conversations have new messages across epochs. Once a notification is found, a Tree Myco component is used for the heavy lifting of obliviously retrieving the actual message content.

These findings collectively demonstrate that it is indeed possible to build a metadata-private messaging system that is cryptographically secure, asynchronous, and performs with near-linear server overhead, thus solving the "trillemma."

Technical Deep Dive

▶ Watch: Core insight: Asymmetric distributed trust for unlinking (4:10)

Myco's technical ingenuity lies in its multi-layered approach to overcoming the inherent challenges of metadata privacy in a distributed, asynchronous environment. The system operates with two non-colluding servers and N clients, where each conversation between Alice (sender) and Bob (receiver) uses a shared symmetric key K. Clients send cover traffic in discrete time intervals called epochs to resist traffic analysis.

1. Asymmetric Distributed Trust:

Traditional PIR-based systems often use a symmetric distributed trust model where Alice writes her message to a location L (derived from K) on both servers, and Bob symmetrically reads from L on both. This approach, however, necessitates a linear scan over the entire database to hide access patterns, leading to quadratic server overhead (O(N^2)).

Myco's core insight is to leverage the distributed trust asymmetrically. Alice writes her message to Server 1. Messages are then obliviously transferred from Server 1 to Server 2. Bob then reads from Server 2. This design ensures that if Server 1 is compromised, Eve (the adversary) only sees who wrote, not who read. If Server 2 is compromised, Eve sees who read, but not who wrote. Critically, if both servers are non-colluding, neither can link a sender to a receiver. This asymmetric approach is foundational to achieving better efficiency.

2. Independent Bucket Assignment and Unbiasable Writes:

A challenge with asymmetric trust is managing message placement. Prior work like Tollic used dependent bucket assignment, where if a bucket L was full, Alice would write to a backup L' or evict an existing message. While acceptable in PIR (where linear scans hide access patterns), this approach leaks honest user behavior in Myco's more efficient setup. If an adversary wrote an evicted message and then read it from L'', they could infer that an honest user wrote to L'.

Myco introduces independent bucket assignment, where messages are written to locations independently of other messages. To achieve this safely and efficiently, Myco uses unbiasable writes. Initially, the concept assumes infinitely sized buckets. Realistically, buckets must be capped. The problem then becomes "biasable writes" – a malicious client could craft a location L and use multiple compromised clients to flood that bucket, causing an overflow. To prevent this, Myco introduces a Pseudo-Random Function (PRF) layer at Server 1.

When Alice sends her message and an intermediary message location F to Server 1, Server 1 uses a server routing key (KSRK) to apply a PRF on F, salted with a unique client username. This generates the final message location L. Even if two malicious clients submit the same F, their unique usernames ensure that the PRF output (L and L') will almost certainly be different, preventing bucket clogging. The paper proves that logarithmically sized buckets (O(log N)) are sufficient with this mechanism.

3. Matrix Myco (Epoch-based System):

The buckets are organized into hash tables within an epoch-based system. Each epoch has a new hash table, and messages expire after a delta number of epochs. Server 1 receives new writes, transfers the current hash table to Server 2, and Server 2 stores a matrix of N * delta buckets (hence "Matrix Myco"). Alice writes to the new hash table, and Bob reads from Server 2.

A significant problem arises if Bob goes offline for delta epochs and is in Q conversations. Upon returning, he would need to download Q * delta buckets to avoid missing messages and remain oblivious. This results in high total work, as constants matter.

4. Tree Myco (Read-Static Messaging Tree with ORAM):

To address the offline client problem, Myco turns to Oblivious RAM (ORAM), specifically Path ORAM, which offers sublinear and oblivious accesses. Path ORAM organizes data in a binary tree, and client accesses involve reading an entire path from the root to a leaf, re-encrypting blocks, and writing them back to a new, random location. This hides access patterns, and paths have logarithmic length (O(log N)).

The challenge is adapting Path ORAM to a multi-server messaging system:

• Who is the ORAM client? If a malicious client is the ORAM client, it could compromise honest client message locations.
• Server 1 as ORAM client? If Server 1 holds the position map (the ORAM client's sensitive data), Alice writes to Server 1, which then writes to Server 2's ORAM tree. Bob reads from Server 2, but then would need to write back through Server 1 (the ORAM client) to re-randomize. This creates a link: Server 1 sees both the write and the read-back, compromising privacy.

Myco's solution is the read-static messaging tree. The insight is that for messaging, a message is typically read only once by the intended recipient. Therefore, the costly write-back operation of Path ORAM, designed for mutable storage, is unnecessary.

Here’s how it works:

• Alice sends F and her message to Server 1.
• Server 1 uses KSRK and F to derive L, the final location. It writes L and the message to its internal position map and then writes obliviously to Server 2's ORAM tree. The KSRK is also transferred to Server 2.
• When Bob wants to read, he downloads KSRK from Server 2. Using F (which he locally computes from K), he derives L. He then downloads the path to L from Server 2's tree and obtains the message.

Crucially, Bob does not write anything back. Reads and writes are completely decoupled.

5. Oblivious Batch Evictions:

The "how Server 1 writes to Path P of Server 2 without disclosing L to Server 2" problem is solved by oblivious batch evictions. Leveraging the high volume of writes in a messaging system, Server 1 processes writes in batches.

• Server 1 samples a path set (e.g., N random paths) from Server 2's tree.
• Alice submits her message and F. Server 1 derives L.
• The message is written to the least common ancestor (LCA) node of the path set and the intended path L. This is a critical departure from standard Path ORAM, where blocks are pushed to the deepest non-full bucket along the old path. Here, it must be exactly the LCA to maintain independent bucket assignment and prevent leakage.
• The updated path set is sent to Server 2.
• Messages "percolate" towards deeper leaves over epochs as new path sets are sampled. This frees up space near the root. Server 1 also deletes expired messages. The paper proves that a bucket size of log(N * delta^3) is sufficient and no stash is needed.

6. Hybrid System with Notifications:

Myco combines the strengths of both Matrix Myco and Tree Myco into a hybrid system:

• Matrix Myco for Notifications: When Alice sends a message, she also sends a small lambda-bit notification (f_notif) to the Matrix Myco system. Server 1 derives l_notif and writes it to the notification matrix. This part has a constant overhead.
• Tree Myco for Messages: The actual message content is written to the Tree Myco system as described above.
• Bob's Retrieval: Bob, after being offline, first downloads Q delta notification buckets from the Matrix Myco. These are small, so the overhead is manageable. He finds the notification, which tells him who* sent a message and in which epoch (t). This information allows him to precisely identify the F and t for the actual message. He then uses this information to download the specific path to L from the Tree Myco, obtaining the message.

This hybrid approach provides the best of both worlds: efficient discovery of new messages across epochs (via Matrix Myco notifications) and oblivious, sublinear retrieval of actual message content (via Tree Myco).

Demo / Proof of Concept

▶ Watch: Problem: Dependent bucket assignment leaks user behavior (5:30)

The Myco team implemented their system in 5,500 lines of Rust and conducted a comprehensive evaluation to demonstrate its practical viability.

Evaluation Setup:

• Baselines: Myco was compared against two state-of-the-art PIR-based messaging systems:
• PUNG++: A single-server system (PUN) enhanced with a state-of-the-art PIR scheme (CLI).
• TLC++: A two-server system (Tollic) enhanced with a state-of-the-art PIR scheme (DPFS).
• Infrastructure: Myco and baseline servers were deployed on Google Cloud Platform (GCP) machines with 64 BCPUs in US West 1. Clients ran on GCP machines with 16 BCPUs in US East 4, ensuring realistic WAN latency by placing them on opposite sides of the US.
• Empirical Capacity Analysis: The researchers empirically determined optimal bucket capacities:
• Matrix Myco: A bucket capacity of 25 devices was found sufficient to prevent overflow.
• Tree Myco: A bucket capacity of 50 devices was found sufficient to prevent overflow.

Core Findings (Throughput):

Myco delivered a dramatic improvement in throughput, directly attributable to its O(N log^2 N) server work compared to the quadratic overhead of PIR-based schemes.

• 11x to 302x higher throughput than TLC++.
• 106x to 2,219x higher throughput than PUNG++.

This significant gap was visually evident in both linear and log-scale graphs, showing Myco's minimal degradation with increasing users compared to the sharp decline of PIR systems.

Single Client Latency:

In an unrealistic scenario where only one client is online, Myco's single-client latency for one epoch was around 50 milliseconds. This is because even with one user, Server 1 must perform a batch write on N paths to ensure the capacity analysis holds and maintain obliviousness. In this specific scenario, TLC++ and PUNG++ showed lower latency.

Worst-Case Latency (All Clients Online):

Under a realistic worst-case scenario where every single client is online, Myco achieved an epoch duration of less than two minutes. In stark contrast, TLC++ required 8 hours per epoch, and PUNG++ needed a staggering 60 hours per epoch. This highlights Myco's superior scalability and practicality for real-world usage.

Bandwidth:

• Server-to-Server Communication: TLC++ has no server-to-server communication, whereas Myco sends 1 to 36 GB of data per epoch between its two servers. However, this translates to only about 100 kilobytes per user when accounting for all users' work.
• Client-to-Server Communication: While TLC++ had lower client-to-server communication, Myco's client-to-server communications grow sublinearly with N. The researchers acknowledge that improving concrete communication costs remains a goal for future work.

The evaluation conclusively demonstrated Myco's ability to provide metadata-private messaging with practical performance, making it the first system to effectively solve the trillemma.

Defensive Implications

▶ Watch: Solution: Independent bucket assignment and unbiasable writes (6:05)

The Myco project offers profound insights and a potential blueprint for the future of secure messaging, with several critical implications for defenders, developers, and users:

1. Metadata is a Primary Attack Vector: The talk reinforces the critical understanding that metadata is not "benign information." It is a potent intelligence source, capable of revealing deep insights into individuals' lives and networks, and can be used for surveillance, targeting, and even physical harm. Defenders must prioritize metadata privacy alongside content encryption.
2. The "Trillemma" is Solvable: Myco's success in achieving cryptographic privacy, asynchrony, and near-linear server overhead proves that the long-standing "trillemma" is not an inherent limitation. This should encourage developers to integrate robust metadata protection into new and existing messaging platforms, rather than dismissing it as an intractable problem.
3. Rethink System Architectures: Myco's innovative use of asymmetric distributed trust and a read-static messaging tree provides a novel architectural paradigm. Developers should explore how these principles can be adapted to other privacy-sensitive distributed systems, moving beyond traditional symmetric trust models where possible.
4. Embrace Advanced Cryptographic Primitives: The reliance on Private Information Retrieval (PIR) and Oblivious RAM (ORAM), specifically Path ORAM, demonstrates the power of advanced cryptographic primitives in building practical privacy solutions. While complex, these tools, when intelligently adapted (as Myco does with its read-static tree), can yield significant security and performance benefits.
5. Importance of Unbiasable Operations: The concept of unbiasable writes (using a PRF) to prevent malicious users from influencing data distribution is crucial. Any system dealing with shared, public-writable data structures in a privacy-preserving context must consider how to prevent such attacks that could degrade performance or leak information.
6. Hybrid Approaches for Optimization: Myco's hybrid notification/messaging system highlights the value of multi-layered design. By using different, optimized mechanisms for different types of data (lightweight notifications vs. heavy messages), overall system efficiency and user experience can be dramatically improved without compromising core privacy.
7. Performance is Key for Adoption: The impressive throughput gains (up to 2,219x) demonstrated by Myco are vital. Even the most cryptographically sound system will fail if it's too slow or resource-intensive to be practical. Myco sets a new benchmark for performance in metadata-private systems, demonstrating that high privacy doesn't have to mean unusable latency.
8. Continued Research in Communication Costs: While Myco makes huge strides in server work, the developers acknowledge that concrete communication costs (especially server-to-server bandwidth) could be improved. This indicates an ongoing area of research for the broader privacy community, aiming to reduce the data footprint of these powerful privacy-preserving techniques.

Myco provides a robust framework for building the next generation of truly private communication tools, offering both a conceptual breakthrough and a practical implementation that sets a new standard for metadata protection.

Key Takeaways

• Metadata is a critical privacy concern: Even with end-to-end encryption, communication metadata (who, when, how often) reveals highly sensitive information, used for surveillance and targeting.
• Myco solves the "trillemma": It is the first practical metadata-private messaging system to achieve cryptographic privacy, client asynchrony, and near-linear (O(N log^2 N)) server overhead simultaneously.
• Asymmetric distributed trust is key: By decoupling read and write operations across two non-colluding servers, Myco prevents either server alone from linking senders to receivers.
• Read-static ORAM enables efficiency: Myco adapts Path ORAM into a "read-static messaging tree," eliminating the need for costly write-back operations and achieving sublinear access patterns for messages.
• Unbiasable writes prevent attacks: Server-side PRFs ensure that malicious clients cannot clog buckets or distort message distribution, guaranteeing independent message placement.
• Hybrid system optimizes retrieval: Myco uses a Matrix Myco for lightweight notifications and a Tree Myco for actual messages, allowing efficient discovery of new messages and oblivious, sublinear retrieval.
• Dramatic performance gains: Myco achieves 11x to 302x throughput over two-server PIR systems and 106x to 2,219x over single-server PIR systems, with worst-case epoch durations under two minutes compared to 8-60 hours for baselines.

About the Speaker(s)

The talk was presented by Darya Kaviani, who introduced the work as a joint effort with Deevashwer Rathee, Bhargav Annem, and Raluca Ada Popa. While specific titles and affiliations beyond their collaborative roles on this research are not detailed in the provided transcript, their work on Myco, presented at the prestigious IEEE S&P conference, highlights their expertise in cryptography, distributed systems, and privacy-preserving technologies. Raluca Ada Popa is notably a prominent researcher in the field of secure systems, often focusing on practical cryptographic solutions for data privacy. The team's collective research demonstrates a strong commitment to advancing the state of the art in secure and private communication.