You picked up your phone after a few hours away and your messages are there. In between, your phone had to ask the relay (the server that carries sealed messages between phones) "did I miss anything?" And the naive way of asking tells the relay exactly which conversations lit up while you were gone.
The ephemeral relay drops messages that arrive while you are offline; the sender's outbox re-ships them when you return. This article is about the return: how a phone catches up on what it missed without the act of catching up becoming a new leak.
When Bob's phone reconnects, it needs to collect the messages that were re-shipped for it into a short holding pool on the relay, its "window" (section 3 describes how it works). The obvious way is to poll: "relay, give me anything waiting on Bob's subject." A subject is the named channel a conversation's messages are published on, and there is one per conversation. So that single request leaks which subject (which conversation) Bob asked about. Over a week of reconnections, the relay watches which of Bob's conversation channels have traffic and when, and quietly rebuilds the very who-talks-to-whom pattern this whole series works to erase. The content stays sealed the entire time; it doesn't matter. The query is the leak.
This is the same trap contact discovery (the machinery that finds which of your contacts
are on Pixie) hit at lookup time, and it has the same name: a database query reveals the
query. In discovery we could not let Alice ask "is this presence_id
registered?" (a presence_id being the
blinded stand-in a phone number gets in the directory).
Here we cannot let Bob ask "is there mail on this subject?"
The read itself has to be blind.
There is a cryptographic primitive (a basic building block) that lets you retrieve a row from a database while the server learns nothing about which row you took. It is called Private Information Retrieval (PIR). The mental model is a library where you walk out with the exact book you wanted and the librarian, watching the whole time, cannot tell which shelf you touched.
We use FrodoPIR, the same lattice-based PIR that the discovery series builds from the ground up. ("Lattice-based" means it rests on a family of math problems believed to stay hard even for quantum computers; that is also what "post-quantum" means below.) Rather than re-derive it here, this article points at that treatment: Bulk Membership: Private Information Retrieval explains how a single-server, post-quantum PIR turns a query into an encrypted list of numbers that the server can do arithmetic on, but cannot decode to see which row was requested.
What matters for the relay is how we apply it to a live, churning pool of messages, because a message pool is a very different beast from the static directory PIR was built for.
PIR wants a fixed database with numbered rows and a shared understanding of what's in it. A relay's undelivered traffic is the opposite: a churning stream, different every second. Three design choices bridge the gap.
The relay, running this, sees "Bob's device pulled from the current snapshot." It does not see which conversation had mail, because answering the query required touching the entire window the same way regardless of the answer.
There is a second-order leak PIR alone doesn't close: volume. If Bob issues three PIR queries, the relay learns he had roughly three conversations' worth of mail: a count, even if not a list. Counts are metadata (facts about the traffic rather than its content), and a sudden spike is a signal.
So the shape of a poll is decoupled from how much mail arrived. The phone queries one bucket per live conversation, whether or not that conversation had anything waiting. A conversation with no mail is queried exactly as a conversation with five messages is. The phone then pads the poll with random cover queries up to a minimum floor, so that a user with very few conversations is not distinguishable from one with none.
Whether Bob truly had zero messages or five, the poll looks the same, because nothing about its shape was ever a function of the mail. This is the standard "cover traffic" defense (sending decoy requests so the real ones don't stand out), with the honest signal removed at the source rather than buried.
Oblivious pull hides which conversations Bob reads and how many messages he had. What it does not (and cannot) hide:
We accept the cost for the same reason as everywhere else in this series: the read pattern is the social graph, and paying in bandwidth to blind it is cheaper than the alternative of handing it to the relay. And because the pool is a one-minute window rather than a durable store, even the thing being PIR'd is ephemeral: the obliviousness protects a conveyor belt, not an archive.