How do you let your friends find you on a new app, without telling the app who your friends are, without letting anyone build a map of who knows whom, and in a way that stays private even against a computer that hasn't been invented yet?
This is the story of one hard feature, told from the top. It is the entry point to a series; each hard sub-problem gets its own deep dive, and this article links out to them as we go. If you have taken a data structures and algorithms course and remember what "one-way function," "hash table," and "polynomial time" mean, you have everything you need to follow along. We will meet the specialized cryptography as we need it, and never before.
You install a messaging app. It asks for permission to read your contacts, you tap "Allow," and within a second the app knows which of your 800 phone contacts are already users. That instant "People you may know" moment is contact discovery, and almost every social app does it. It is also one of the most quietly dangerous things an app can do, because the naive way to build it hands the server a perfect social graph.
Let us be precise about what we want. A user Alice has a phone number and a set of phone numbers in her address book. We want:
Requirement 2 is the interesting one. A phone number is not secret: there are only about ten billion of them, which sounds like a lot until you remember that a computer can hash all ten billion in seconds. So "just hash the number" protects nothing.
The obvious first design: the client hashes each contact's number with SHA-256 (a standard one-way hash function, easy to compute forward and infeasible to run backward) and sends the hashes. The server hashes its user numbers the same way and returns the intersection.
This fails, for a reason worth internalizing. The space of phone numbers is small and
structured: you can simply list all of it. So an attacker, or the server itself, can
compute SHA-256(number) for every number that exists and store the results in a reverse
lookup table.
Once that table exists, every hash Alice uploads is de-anonymized the moment it arrives. The server has her address book. Hashing gave her the illusion of hiding, not the substance.
The classic defence against a lookup table is a salt: a random extra value mixed into every hash, which is why password systems salt passwords. Wikipedia calls the underlying attack a dictionary attack. But salting is exactly what we cannot do here. Alice and the server have to arrive at the same value or a match is undetectable, and a salt is what makes two parties arrive at different ones.
There is a well-trodden alternative we did not take. Signal's production system runs contact discovery inside a secure enclave: a region of a CPU that the operating system, and therefore the server operator, physically cannot read into. It is real, deployed, and we respect it.
Two things kept us away from it. It makes your privacy contingent on one CPU vendor's enclave not having a side-channel bug, and enclaves have had many. And it does nothing for the "private forever" property, which we are about to argue is the requirement that matters most here.
What we wanted was a guarantee that comes from mathematics we publish rather than hardware we trust. So we went the long way around.
The trick that breaks the enumeration problem is to introduce a secret that only the server holds, and to compute the matchable identifier as a keyed function of the phone number:
presence_id = Hash( F_s(phone number) )
Fs is a pseudorandom function, or PRF: a function with a key built in. Feed it the same input twice and you get the same output twice. But show that output to anyone who does not hold the key s, and they cannot tell it apart from random noise.
That is what breaks the enumeration attack. An attacker can still write down every phone
number in the country. But a list of phone numbers is no longer a list of presence_ids,
because turning one into the other means evaluating Fs, and only the server, which holds the key, can do
that.
Which leaves a new problem, and it is the one this series is really about. If only the server can evaluate Fs, then Alice has to hand her contacts' numbers to the server to have them evaluated. We have walked straight back into requirement 2.
So we need something stranger than a keyed function: a way for the server to apply its key to an input it never sees.
The mental model is a photo lab that develops your film without ever seeing the pictures. You hand over a sealed, scrambled roll; they apply their secret chemical process; they hand back the still-scrambled result; you unscramble it at home. They contributed their secret, you kept your photo private, and the output is deterministic: the same film always develops to the same print, which is exactly what we need for two people to match on the same number.
That protocol has a name: an Oblivious Pseudorandom Function, or OPRF: "oblivious" because the server applies its keyed function while staying oblivious to the input. Three things are true at the end of it. The client holds Fs(x), the PRF applied to her input x. The server has learned nothing about x. The client has learned nothing about s.
One assumption is doing quiet work under all of this. The server has to keep s secret, and not only from outsiders, because an attacker who breached the server would walk away able to de-anonymize every lookup anyone had ever made. Making that assumption true is its own design problem, and it is the subject of Guarding the Directory.
So the top-level architecture is:
presence_id
she can look up, without the server seeing the number.presence_id → inbox mapping (the ID plus where to reach them) in a directory.presence_ids appear in the directory.Five sub-problems fall out of this, and each one turned out to be a small research project.
| Sub-problem | Why it's hard | Deep dive |
|---|---|---|
| Build an OPRF that resists quantum computers | The classic OPRF constructions all rest on elliptic curves, which a quantum computer breaks | The Lattice OPRF |
| Make sure the server can't cheat | A malicious server can use a different secret per victim to de-anonymize a single target | The Verifiable OPRF |
| Check membership without leaking which IDs you checked | Even asking "is presence_id X in the directory?" leaks X |
Bulk Membership: PIR |
| Stop abuse of an oracle that turns numbers into IDs | The OPRF is, by design, a machine for computing presence_ids, including for numbers you don't own |
Guarding the Directory |
| Stop the directory handing you the wrong key | A lookup answer is only as good as the directory serving it, and a substituted key is invisible without a proof | The Transparency Log |
Everything else in this series is the machinery underneath those five. But first we have to confront the requirement that dictated the whole design.
The textbook OPRF is a beautiful one-liner, and it is worth seeing before we throw it away.
It lives on an elliptic curve, the classical workhorse under most of today's public-key cryptography: the kind of encryption where anyone can lock a message with your public key, but only you can unlock it. For our purposes a curve is just a set of points you can add together. Adding a point to itself over and over is therefore a kind of multiplication, so "multiply this point by a whole number" is a thing you can do.
The protocol is four moves. Represent the phone number as a point P on the curve. The
client picks a random blinding scalar r (a plain number used as a one-time scramble
that only the client can undo) and sends r·P. The server multiplies by
its secret s and returns s·(r·P). The client multiplies by r−1,
the number that undoes multiplying by r,
which cancels its own blinding and leaves s·P.
Now check what each side came away with. The server never saw P, because r hid it. The
client never saw s. And s·P is deterministic, so Alice and Bob starting from the
same phone number arrive at the same value, which is the whole point. This is
2HashDH, and it is what most privacy-preserving systems
use today, including Signal-style designs and the RFC-9497 standard.
It rests entirely on one assumption: that given P and s·P, you cannot recover
s.
That is the discrete logarithm problem,
and in 1994 Peter Shor showed that a sufficiently large quantum computer solves it
efficiently. The same result breaks RSA, Diffie–Hellman, and every elliptic-curve scheme
in wide use.
Here is why that matters for us specifically, even though large quantum computers do not exist yet. Contact-discovery traffic reveals a social graph, and a social graph does not expire. An adversary can record the blinded traffic today and simply wait. The day a quantum computer arrives, they decrypt fifteen years of recordings and reconstruct who knew whom, retroactively. Cryptographers call this harvest-now, decrypt-later, and it turns "quantum computers don't exist yet" from a comfort into a countdown.
So we imposed a hard rule: no elliptic curves, no RSA, no Diffie–Hellman anywhere in the discovery path. (RSA and Diffie–Hellman are the other classical public-key workhorses; Shor's result breaks all three.) Every primitive (every basic cryptographic building block we use) must rest on a problem believed hard even for quantum computers. In practice that means one family of problems, lattice problems (questions about finding a short, well-hidden vector inside a regular grid of points in a few hundred dimensions), which currently give us the best-understood, standardized post-quantum assumptions. The foundations are their own article, because every later piece leans on them: Lattice Foundations.
This rule is expensive. The elliptic-curve OPRF is two scalar multiplications and about 64 bytes on the wire. Its lattice replacement, as we will see, is a multi-round protocol. It moves tens of kilobytes and does its arithmetic in polynomial rings: number systems whose elements are whole polynomials with thousands of coefficients. A large part of this series is the story of clawing that cost back down to something that runs in well under a second.
We want to be honest about the tradeoff we accepted. We could have shipped the fast, classical, curve-based OPRF and told ourselves that quantum computers were a decade away. Many production systems make exactly that call, and it is defensible. We decided that a social graph is precisely the kind of long-lived secret that harvest-now-decrypt-later is designed to steal, and that "we'll fix it before the quantum computer arrives" is not a plan you can execute retroactively on traffic already recorded. So we paid the cost up front.
If we cannot multiply a point by a secret scalar, how do we evaluate a keyed function obliviously? The answer reframes the whole thing as linear algebra over a ring: vectors and inner products, but with arithmetic that wraps around a modulus.
Our PRF is built out of an inner product:
F_s(x) = round( ⟨a_x, s⟩ )
Here ⟨a_x, s⟩ is the inner product of two vectors: multiply them entry by entry, then
add everything up. The vector ax is public (you get it by hashing the phone
number x), and s is the
server's secret vector. (Ignore the rounding for a moment; it is the first of the two
wrinkles below.)
Now notice who holds which half. The client can compute ax entirely on its own, because
it is just a hash of a number the client already has. The server holds s. So evaluating
the PRF obliviously collapses into one very specific question: can two parties compute
⟨a_x, s⟩ when one of them holds the vector and the other holds the secret,
with neither revealing their piece?
That task has a name: Oblivious Linear Evaluation, or OLE. It is the workhorse of the entire system. We build it out of lattice encryption in Algorithm: Oblivious Linear Evaluation from Ring-LWE.
Two wrinkles turn one clean inner product into a real protocol:
The output has to be rounded. A pseudorandom function needs to output crisp bits, but the OLE gives us a noisy field element: a number in a fixed modular range with a little random error still riding on it, because lattice encryption is noisy by nature. Both parties must agree on the same rounded value without the server learning it and without the noise causing them to disagree. We handle the rounding through a second primitive, Oblivious Transfer, in which the server offers two values, the client takes exactly one, and neither side learns the other's half: not which one was taken, not what the other one was. It is described in Post-Quantum Oblivious Transfer and applied to rounding in Rounding by Oblivious Transfer.
Only a prefix of the output matters. The full PRF output is 512 coefficients, but
the presence_id only needs 32 of them (PRESENCE_TRUNC = 32) hashed down to 32 bytes.
That lets us do the expensive rounding on 32 values instead of 512, a small design
choice that pays off everywhere downstream.
Put together, one contact resolves in two network round-trips: the client sends a lattice
encryption of ax; the server applies s homomorphically (arithmetic done straight on
the ciphertext, so an encrypted answer comes out without anything being decrypted along the
way) and sets up the rounding; the
client finishes the rounding and hashes the result into a presence_id. The server, the
whole time, sees only ciphertexts it cannot decrypt.
Obliviousness protects Alice from a curious server. But it is a guarantee about what the server learns, not about what it does, and nothing so far obliges the server to run the protocol it agreed to.
The server is supposed to use one secret key s for everyone. What if it doesn't? A malicious operator can mint a per-victim key sAlice, use it only when Alice is connected, and use the honest key for everyone else.
Now Alice's presence_ids are computed under a key nobody else uses, so they will never match
the real directory. But something more insidious is possible: the operator can choose sAlice to sort Alice's
contacts into buckets, then learn things about them by watching which lookups she performs next.
The obliviousness held perfectly; the consistency of the key was the hole.
The fix is to make the server prove, on every single response, that it used the one key it is supposed to use, without revealing that key.
It works in two parts. Once, up front, the server publishes a commitment
Com(s): a sealed, tamper-evident fingerprint of s, which is baked into the app.
Then every OLE reply arrives with a zero-knowledge proof (a proof that convinces you a
statement is true while revealing nothing else) saying "the s I just used is the s
behind Com(s)."
The client checks that proof before it reveals anything further, and aborts if it fails. A server using a per-victim key cannot produce one.
This upgrade, from OPRF to Verifiable OPRF, is the subject of The Verifiable OPRF. The proof system that makes it possible is a NIZK (a non-interactive zero-knowledge proof, one the server can attach as a single message with no back-and-forth), and it is the deepest rabbit hole in the series: Algorithm: The NIZK.
The proof is where most of the engineering went, because a zero-knowledge proof that some linear algebra over a lattice was done correctly is, naively, enormous and slow: think multiple megabytes and minutes. Getting it to a 52-kilobyte proof that verifies in well under a second required three nested ideas, each its own article:
And for the corner a proof cannot reach (where checking the answer would need the very secret the protocol withholds), Known-Answer Testing catches a cheating server by hiding questions with published answers among the real ones.
Now Alice can compute her contacts' presence_ids privately and correctly. She still has
to look them up. And here is the twist that catches people: the moment she asks the
server "is presence_id X registered?", she has told the server about X.
We could have accepted this. The whole point of the keyed OPRF was that presence_id is
not linkable back to a phone number without the server's key, so leaking the set of IDs
Alice checks leaks a set of pseudonyms, not phone numbers. For many threat models that is
enough. But those pseudonyms are exactly the social graph we swore to protect: the set
of people Alice looks up is her contact list, phone numbers or not, and the server
watching those lookups over time reconstructs her connections.
So the lookup itself must be blind. The tool is Private Information Retrieval (PIR): a protocol that lets Alice query a database and get the answer for her row without the server learning which row she asked about. We use a single-server, lattice-based PIR (FrodoPIR) so that even the query is an encrypted blob the server cannot invert. That is Bulk Membership: PIR.
Step back and notice what we have built: a public service that, given a phone number,
returns its presence_id. That is by design: Alice needs it for numbers she doesn't
"own" (her contacts'). But it is also an oracle, a black box anyone can put questions
to: an attacker can feed it numbers it
does not own and harvest presence_ids, or hammer it to enumerate the whole number space
under the server's key, or register poisoned directory entries to see who looks them up.
None of the fancy cryptography helps here, because the attacker is using the system exactly as intended. The defenses are more classical: rate limiting, requiring proof you control a number before you can be listed (a Sybil gate: the check that stops one attacker from spinning up thousands of fake identities), and authenticating the people who publish directory entries so nobody can poison them. These belong to Guarding the Directory, and they are a reminder that a system is only as private as its most boring interface.
After a lot of exploration, the discovery path settled into a single, uniform flow. There is exactly one way to resolve a contact, and it is post-quantum end to end:
a_x = Hash(phone) under a fresh lattice key and posts
it. The server homomorphically evaluates its secret s, sets up the oblivious rounding,
and returns the reply together with a 52 KB zero-knowledge proof that it used the
committed key.Com(s), the client aborts and reveals nothing further. There is no
"unverified fallback": a server that cannot prove it behaved learns nothing.presence_id.We arrived here by deliberately collapsing several parallel designs into one. Early on we carried multiple proof formats (a flat one; a "sublinear-verifier" one, meaning checking it takes less time than reading the whole statement; and a batched one) and even a classical curve-based path as a bridge. Each existed for a good reason at the time, but a security system with four ways to do the same thing has four times the attack surface and four times the code that can rot.
Once the packed, folded proof became strictly better than every alternative (smaller and faster to produce and fast to check), keeping the others was pure risk. A single, well-audited path you can reason about beats a menu of options you cannot. So the mechanism is deliberately singular.
Read top-down for the story, bottom-up for the mechanisms:
A recurring theme, which is really the moral of the whole project: the expensive part of privacy is not hiding data: it is proving that the hidden computation was done honestly, and doing it fast enough that nobody turns the feature off.
Next: Lattice Foundations: SIS, LWE, and Post-Quantum Trust.