HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Contact Discovery

Contact Discovery

15 min read

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.

1. The problem

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:

  1. Discovery works. If Bob is a registered user and Bob's number is in Alice's address book, Alice's app learns that Bob is reachable.
  2. The server never learns Alice's address book. Not the numbers she looked up, not which ones matched, not even how the numbers hash.
  3. The server never learns a social graph. Even a server that logs everything and colludes with itself over time cannot reconstruct "who is connected to whom."
  4. It is fast enough to feel instant for a real address book (hundreds of contacts).
  5. It stays private forever — including against an adversary who records the traffic today and decrypts it in fifteen years with a quantum computer. (This last one is the requirement that reshaped almost every decision. More on it soon.)

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 strawman, and why it fails

The obvious first design: the client hashes each contact's number with SHA-256 and sends the hashes; the server hashes its user numbers the same way and returns the intersection.

This is bad for a reason worth internalizing. The phone-number space is small and structured — it is enumerable. An attacker (or the server itself) can precompute SHA-256(number) for every possible number and build a reverse lookup table. Now every hash the client uploads is de-anonymized instantly, and the server has learned Alice's entire address book. Hashing gives you the illusion of hiding, not the substance. Wikipedia calls this a dictionary attack; it is the same reason you salt passwords, except here you cannot salt, because Alice and the server must arrive at the same value for a match to be detectable.

We could have leaned on trusted hardware here — Signal's production system runs contact discovery inside a secure enclave (SGX), where the server physically cannot read the data it is processing. That is a real, deployed solution and we respect it. But it makes your privacy contingent on a specific CPU vendor's enclave not having a side-channel bug (and enclaves have had many), and it does not by itself give you the "private forever against quantum" property we insisted on. We wanted the guarantee to come from mathematics we publish, not from hardware we trust, so we went a different way.

2. The shape of the solution

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) )

Here F_s is a pseudorandom function keyed by a server secret s. Because the attacker does not know s, they cannot precompute the table — enumerating phone numbers tells them nothing without also evaluating F_s, and only the server can do that. (This quietly assumes the server can keep s secret — even from an attacker who breaches the server itself; making that assumption true is its own design problem, taken up in Guarding the Directory.) This is the standard modern answer, and the primitive that makes it work while also hiding the input from the server is called an Oblivious Pseudorandom Function, or OPRF: a two-party protocol where the client learns F_s(x) and the server learns nothing about x, and the client learns nothing about s.

If you have never seen an OPRF, 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.

So the top-level architecture is:

  • Alice runs the OPRF with the server on each contact's number to get a presence_id she can look up, without the server seeing the number.
  • Registered users have published their own presence_id → mailbox in a directory.
  • Alice checks which of her computed presence_ids appear in the directory.

Four 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

Everything else in this series is the machinery underneath those four. But first we have to confront the requirement that dictated the whole design.

3. The requirement that changed everything: post-quantum

The textbook OPRF is a beautiful one-liner. Represent the phone number as a point P on an elliptic curve. The client picks a random blinding scalar r and sends r·P. The server multiplies by its secret s and returns s·(r·P). The client multiplies by r⁻¹ and gets s·P. The server never saw P (it was blinded by r), the client never saw s, and s·P is deterministic. This is the 2HashDH OPRF, and it is what most privacy-preserving systems use today, including in 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. Every primitive must rest on a problem believed hard even for quantum computers. In practice that means one family of problems — lattice problems — 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 moving tens of kilobytes and doing arithmetic over polynomial rings 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.

4. From a curve multiply to a lattice evaluation

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.

Our PRF is F_s(x) = (a rounding of) ⟨a_x, s⟩, where a_x is a public vector derived by hashing the phone number x, and s is the server's secret vector. Evaluating the PRF is just an inner product. The obliviousness problem becomes: let the client compute ⟨a_x, s⟩ where the client holds a_x and the server holds s, with neither party revealing their piece. That specific two-party task has a name — Oblivious Linear Evaluation (OLE) — and 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 (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, 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 a_x; the server homomorphically applies s 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.

5. The second adversary: a lying server

Obliviousness protects Alice from a curious server. But there is a nastier attack that obliviousness alone does not stop, and it is subtle enough that it is easy to miss.

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 s_Alice, 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 more insidiously, the operator can choose s_Alice to sort Alice's contacts into buckets and 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 force the server to prove, on every response, that it used the one committed key — without revealing the key. The server publishes a one-time commitment Com(s) (think of it as a sealed, tamper-evident fingerprint of s), bakes it into the app, and then every OLE reply comes with a zero-knowledge proof that "the s I just used is the s behind Com(s)." The client checks the proof before it reveals anything further, and aborts if it fails. This upgrade — from OPRF to Verifiable OPRF — is the subject of The Verifiable OPRF, and the proof system that makes it possible 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:

  • doing all the proof arithmetic in a carefully chosen Proof Ring so exact integer identities never "wrap around";
  • a Packed encoding that stuffs 64 numbers into each ring element, shrinking the secret being proven about by 64×;
  • and a Succinct folding technique that compresses the proof from linear size down to logarithmic.

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.

6. Membership without a question

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.

7. The oracle problem

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: 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), 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.

8. The shape we converged on

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:

  1. Round 1. The client encrypts 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.
  2. Client checks the proof, fail-closed. If the proof does not verify against the baked-in commitment Com(s), the client aborts and reveals nothing further. There is no "unverified fallback" — a server that cannot prove it behaved learns nothing.
  3. Round 2. The client finishes the oblivious rounding, obtaining the 32-coefficient PRF prefix, and hashes it into a 32-byte presence_id.
  4. Blind lookup. The client checks membership by PIR, learning which of its contacts are reachable without revealing which IDs it asked about.

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, 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.

9. How to read the rest of the series

Read top-down for the story, bottom-up for the mechanisms:

  • Start here, then read Lattice Foundations once — it is the vocabulary for everything else.
  • The two "trust" articles, The Lattice OPRF and The Verifiable OPRF, are the heart of the design.
  • The Algorithm articles (06–12) are the engine room. They are self-contained enough to read in any order, but 09→10→11→12 form a natural staircase down into the proof system.
  • PIR and Guarding the Directory close the loop from "compute an ID" to "safely use it."

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.

References

Next: Lattice Foundations: SIS, LWE, and Post-Quantum Trust.