HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Relay

Reading Without Being Watched: Oblivious Pull

5 min read

You picked up your phone after a few hours away and your messages are there. In between, your phone had to ask the relay "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.

1. The leak in "do I have mail?"

When Bob's phone reconnects, it needs to collect the messages that were re-shipped into its window. The obvious way is to poll: "relay, give me anything waiting on Bob's subject." That single request leaks which subject Bob asked about — and subjects are per-conversation. 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 we spent the whole series erasing. The content stays sealed the entire time; it doesn't matter. The query is the leak.

This is the same trap the discovery path 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?"; here we cannot let Bob ask "is there mail on this subject?" The read itself has to be blind.

2. The tool: ask without saying what you asked

The primitive that lets you retrieve a row from a database while the server learns nothing about which row is 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 the same lattice PIR — FrodoPIR — that the discovery series builds from the ground up. 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 vector the server can compute against but cannot invert. 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.

3. Turning a stream into something you can PIR

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.

  • A short window. The relay keeps recently-published sealed envelopes for about a minute in a rolling pool. That is long enough to cover the reconnect-and-pull window from a push wake, and short enough that the pool is never a mailbox — it is a one-minute conveyor belt, not a warehouse.
  • A content-addressed snapshot. So client and server agree on "which database" they are doing PIR against, the pool is frozen into a snapshot identified by a hash (SHAKE-256) of its contents. Bob first downloads a small hint for the current snapshot, then runs his PIR query against that exact, agreed-upon version — no ambiguity about what row numbers mean.
  • PIR the retrieval. With hint in hand, Bob's phone builds an encrypted query for the rows it could possibly want and gets back the sealed envelopes without the relay learning which it was actually after. The relay computes over the whole snapshot for everyone identically; the query vector is an opaque lattice blob.

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.

4. Hiding how much mail, too

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; a sudden spike is a signal.

So the client pads every poll to a fixed number of queries with random covers. Whether Bob truly had zero messages or five, his phone issues the same fixed count of PIR queries, the surplus being decoys aimed at nothing in particular. The relay sees a constant-shaped poll every time, revealing neither which conversations nor how many. This is the standard "cover traffic" defense: make the honest signal indistinguishable from a fixed template by always sending the template.

5. The honest residual, and the cost

Oblivious pull hides which conversations Bob reads and how many messages he had. What it does not — and cannot — hide:

  • That Bob polled at all. The relay learns Bob's device came online and pulled, and roughly how often. Presence and reconnect cadence are a faint activity signal; they are not a social graph.
  • The bandwidth bill. PIR is not free. To query obliviously, Bob first downloads a hint whose size scales with the pool — on the order of tens of megabytes for a pool of kilobyte-sized records. That is the production knob of the whole mechanism, and the honest tradeoff: perfect query privacy is paid for in hint bandwidth, and sublinear-hint PIR schemes (Spiral and its successors) are the lever if that bill needs to shrink.

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.

References & further reading