Alice can now compute her contacts' identifiers privately and correctly. She still has to look them up in a directory, and the act of looking something up is itself a leak. This article is about the last mile: checking whether an identifier is registered without telling the server which identifier you asked about.
Prerequisites: Contact Discovery for the framing, and
Lattice Foundations for LWE (Learning With Errors, the
problem of recovering a secret from linear equations that have been deliberately blurred
with small random noise, and the hardness bet this whole series rests on). The
Lattice OPRF produced the presence_ids we are now looking up:
stable, private identifiers derived from phone numbers.
The OPRF (the oblivious pseudorandom function of the previous chapter, a keyed hash the server computes for you without ever seeing your input) was a lot of work to make sure the server never sees a phone number. Here is the deflating part.
If Alice now turns around and asks the server "is presence_id 0x9f3c… in the
directory?", she has just handed the server a presence_id. Do that for all 800 of her
contacts and the server has her entire contact set.
It arrives as a list of pseudonyms rather than names, which sounds better than it is. That list is the social graph the whole system exists to protect. A pseudonymous social graph is still a social graph.
It is worth naming why this is easy to miss. The OPRF protects the derivation of the identifier. Membership checking is a different operation, and its privacy is a different problem: a system can be flawless at the first and wide open at the second.
The general lesson, again: privacy is a property of the whole pipeline, not of its most impressive component.
So the requirement for the lookup is: Alice learns which of her presence_ids are in the
directory, and the server learns nothing about which IDs she asked about: not the IDs,
not which matched, ideally not even how many.
Two designs look like they solve this and do not.
"Just download the whole directory." If Alice downloads every registered presence_id
and checks locally, the server learns nothing at all about her queries. That is perfect
privacy.
It is also unshippable. A directory of millions of users is tens or hundreds of megabytes, it grows forever, and it has to be re-downloaded to stay fresh. On a phone over cellular data, that is a non-starter.
It has a second problem that survives any amount of compression: it leaks the entire member set to every user. Anyone who installs the app can now enumerate who is registered.
A compressed Bloom filter (a compact bit-array sketch of a set that answers "definitely not present" or "probably present") shrinks the download, and Bloom filters are lovely, but they do not fix either objection. The membership set still leaks, it still grows with the user base, and the filter's false positives would make Alice think a stranger is a contact. So "download it all" was out.
"Two non-colluding servers." There is a classic and very efficient family of private information retrieval schemes, going back to Chor–Goldreich–Kushilevitz–Sudan in 1995, that splits the database across two servers assumed not to talk to each other.
What it buys is remarkable: information-theoretic privacy, the kind that holds even against an adversary with unlimited computing power rather than one that merely cannot solve a hard problem. And it costs almost nothing. This is genuinely great when you can arrange it.
We chose not to depend on it, because "two servers that never collude" is an operational assumption rather than a mathematical one. In practice both servers tend to be run by the same organization, or in the same cloud, and the security evaporates the moment they compare notes.
We wanted the privacy to come from a hardness assumption we could point at, not from an org chart.
That leaves single-server, computational PIR, where the math stops one server from learning the query.
Private Information Retrieval is a protocol where a client fetches item i from a server's database and the server does not learn i.
The single-server version sounds impossible. How can the server return row i without knowing i? The resolution is beautifully simple once you see it.
Model the database as a vector of records D = (D_0, D_1, …, D_{m−1}). To fetch
record i, what the client conceptually wants is the selector vector
e_i = (0, …, 0, 1, 0, …, 0): all zeros except a single 1 in position i.
The reason it wants that vector is the dot product: multiply the two vectors entry by
entry, then add everything up. In ⟨e_i, D⟩ = D_i, every record gets multiplied by a zero
except the one in position i, so the sum picks out exactly the row the client is after
and nothing else. If the client could compute that dot product without revealing
e_i, it would get D_i and the server would learn nothing.
And we already know how to compute a dot product on hidden inputs. That is what lattice encryption gives us.
The client encrypts the selector vector and sends the ciphertexts. The server uses the
homomorphic property (adding and scalar-multiplying still work under encryption) to compute
⟨Enc(e_i), D⟩ on the ciphertexts, a big weighted sum over its records, and
returns one encrypted result. The client decrypts it and gets D_i.
The server never sees which row it just handed over. To it, Enc(e_i) is a vector of LWE
ciphertexts, each indistinguishable from random noise. It cannot tell the 1 from the 0s.
That is the whole idea: PIR is a homomorphic dot product against a selector you keep encrypted. It is the same LWE trick as the OLE (the oblivious linear evaluation) from The Lattice OPRF, pointed at a different job.
It is post-quantum for the same reason, too. The query is an LWE ciphertext, and inverting it is a hard lattice problem, so a "harvest-now" adversary who records the query learns nothing from it even after quantum computers exist.
The naive scheme above has the server do a full pass over the entire database for every query, which is expensive if the database is large and queries are frequent. The scheme we use, FrodoPIR (Davidson–Pestana–Celi, 2023), makes this practical with a stateful, preprocessing trick: do the heavy work once, ahead of time, and let the client keep the result. The trick is worth understanding because it shows how PIR gets fast.
The database is thought of as a matrix. Ahead of time, the server publishes a hint: a one-time, query-independent digest of the database (concretely, the database multiplied by a public random matrix). The client downloads this hint once and caches it. Now, at query time:
The name "Frodo" is a nod to the FrodoKEM family of post-quantum key-establishment schemes (a KEM, or key encapsulation mechanism, is a tool two parties use to agree on a shared secret key). It signals the same design instinct: FrodoPIR uses plain, unstructured LWE rather than the structured Ring-LWE elsewhere in this series.
That is deliberate conservatism. Ring structure buys speed and costs a little assurance, because the extra algebra is extra surface for a future attack. For the PIR layer we were willing to pay in speed for the most cautious lattice assumption available, since a membership query leaks less structure to begin with.
We then sized the LWE dimension so the scheme clears the strict quantum core-SVP ≥128 bar under the community lattice estimator, the same tool Lattice Foundations used. Core-SVP is the standard yardstick for lattice parameters: the estimated cost of the cheapest known attack, quoted in bits. Clearing 128 means nothing known breaks it in under 2128 operations, and the quantum figure assumes the attacker already has a quantum computer.
At n = 1728 the estimate is roughly 135.7-bit quantum and 149.5-bit classical. Smaller dimensions cleared only the classical bar: n = 1536 came in around 116-bit quantum, and n = 1024 at about 74. For a system whose promise is "private forever," classical-only was not good enough, so we paid for the larger n.
The cost model, made explicit: PIR moves the expense to a one-time hint download of tens of megabytes, cached and refreshed lazily, in exchange for cheap, private, per-query lookups.
"Refreshed lazily" means a conditional request. The client keeps its cached hint and revalidates against the server's content ETag (the version fingerprint web servers attach to a file), so an unchanged directory answers with a tiny 304 Not Modified and the re-scan pays nothing for the hint. It re-downloads only when the directory has actually changed.
For contact discovery, where a user syncs a big address book occasionally and then does light lookups, that trade is exactly right.
A membership bit ("yes, this presence_id is registered") is only half of what discovery
needs.
Once Alice knows Bob is reachable, she needs Bob's actual discovery inbox, the sealed inbox she will use to start a conversation. And fetching that leaks which member she matched, just as badly as the membership query would have.
So the system runs PIR twice, in two tiers:
presence_id registered?" privately, using a compact
membership structure so the per-query cost stays tiny even for a large directory.Both tiers are the same underlying FrodoPIR machinery aimed at different tables. The result: Alice goes from a phone number all the way to "here is Bob's sealed inbox and how to encrypt to it," and at no point did the server learn the number, the identifier, the match, or the inbox it just handed over.
The second tier does one more thing, which matters for the promise made in §1: it issues record queries for cover indices alongside the real ones and throws the answers away.
That pads the number of record fetches up to a fixed bucket instead of letting it track the number of matches. A run where nobody in your address book is on Pixie looks exactly like a run with a handful of hits, so "not even how many" is a delivered property rather than an aspiration.
PIR hides which row Alice reads. It does not stop her from reading many rows to enumerate the directory, and it does not authenticate who put a row there.
Those are abuse and integrity problems rather than privacy ones, and they are handled by rate limits and directory authentication in Guarding the Directory.
PIR also assumes the presence_ids Alice looks up were computed honestly, which is the job
of the Verifiable OPRF. PIR is the blind-lookup leg of the
tripod, and it is only private in a system where the other two legs hold as well.
Next: Guarding the Directory: Enumeration, Sybils, and Poisoning.