HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Contact Discovery

The Lattice OPRF: Deriving presence_id

9 min read

The heart of contact discovery is a two-party ritual that turns a phone number into a stable, unlinkable identifier — while the server, which supplies the secret, never sees the number, and the client, which supplies the number, never sees the secret. This article is how we built that ritual without any of the classical cryptography that a quantum computer would break.

Prerequisites: the problem framing in Contact Discovery and the vocabulary in Lattice Foundations. We assume you know what LWE and Ring-LWE are and why we are avoiding elliptic curves.

1. What an OPRF has to be

An Oblivious Pseudorandom Function is a keyed function F_s(x) computed by two parties, with three properties that pull in different directions:

  1. Pseudorandom. To anyone without the key s, the outputs F_s(x) look like random junk — you cannot predict F_s(x') from other outputs. This is what defeats the enumeration attack from article 00: without s, precomputing a phone-number → ID table is impossible.
  2. Deterministic. The same input always yields the same output. This is what makes discovery work — Alice and Bob must independently arrive at the identical presence_id for Bob's number, or they can never match.
  3. Oblivious. The server (holding s) learns nothing about x; the client (holding x) learns nothing about s beyond the single output value.

Properties 1 and 2 together say F_s is a pseudorandom function — a deterministic, key-controlled scrambler. Property 3 is the "oblivious" adjective, and it is the hard part. Building a PRF is easy; building one two strangers can jointly evaluate while each keeps their input secret is where the cryptography lives.

Our final identifier is

presence_id  =  SHAKE-256( first 32 coefficients of F_s(phone) )

a 32-byte value. The outer hash (SHAKE-256, a quantum-safe hash) does three jobs: it compresses the PRF output to a tidy 32 bytes, it destroys any leftover algebraic structure, and it means the client only has to obliviously compute a prefix of the raw PRF — 32 coefficients out of 512 — which we will see is a big efficiency win.

2. Why the classical construction was off the table

It is worth seeing the thing we gave up, because it is so clean.

Classically you would represent the phone number as a point P on an elliptic curve and define F_s(P) = s·P. Obliviousness is one line: the client sends r·P for random r, the server returns s·r·P, the client multiplies by r⁻¹. It is deterministic (same P → same s·P), pseudorandom (under the decisional Diffie–Hellman assumption), and about 64 bytes on the wire.

We could have shipped exactly this. The reason we did not is the one from article 00: s·P lives or dies by the hardness of discrete log, and Shor's algorithm dismantles discrete log on a quantum computer. Since discovery traffic reveals a social graph — a secret with a decades-long shelf life — an adversary recording it today can decrypt it after quantum computers arrive (harvest-now-decrypt-later). For a feature whose whole output is long-lived linkage, that was an unacceptable risk. So we needed a PRF and an obliviousness mechanism that rest on lattices instead.

There is also an "in-between" option we considered and rejected: lattice-flavored OPRFs that keep the classical shape (a Diffie–Hellman-like blinding) but swap the group for a lattice, e.g., isogeny-based or "shifted-modulus" constructions. These tend to be either still-classical in disguise, immature (isogeny assumptions took serious cryptanalytic hits in 2022–2023), or to require the client and server to do a fully interactive dance with rejection sampling that is fiddly to make constant-round. We wanted something we could reduce to standard Ring-LWE and Ring-SIS with no exotic assumptions, which pushed us to build the OPRF directly out of homomorphic evaluation.

3. The idea: a PRF that is just an inner product

Here is the reframing that makes a lattice OPRF possible. Define the PRF as a rounded inner product:

F_s(x)  =  Round( ⟨a_x, s⟩ )
  • s is the server's secret: a vector of N = 512 small integers, the everlasting key.
  • a_x is a public vector of the same length, produced by hashing the phone number x into the ring (a "hash to ring" — a deterministic public map from a number to a ring element). Anyone can compute a_x; it carries no secret.
  • ⟨a_x, s⟩ is their inner product in the ring, and Round(·) snaps the result to a clean value.

Why is this a good PRF? Because recovering s from input/output pairs (a_x, F_s(x)) is exactly an LWE-style problem — you are seeing (rounded) noisy linear equations in the secret s, and article 01 told us recovering the secret from those is a hard lattice problem. So the outputs are pseudorandom to anyone without s, which is property 1. It is deterministic (fixed a_x, fixed s), which is property 2. That leaves obliviousness.

Obliviousness now has a crisp shape: the client holds a_x, the server holds s, and we need the client to learn ⟨a_x, s⟩ without either party revealing its half. That exact two-party task is a named primitive — Oblivious Linear Evaluation (OLE) — and it is where the real machinery goes. It gets its own deep dive: Algorithm: Oblivious Linear Evaluation from Ring-LWE. The one-paragraph version: the client encrypts a_x under a fresh Ring-LWE key and sends the ciphertext; the server, using the homomorphic property of the encryption, computes ⟨a_x, s⟩ on the ciphertext — never decrypting it — and sends back an encrypted result the client alone can open.

4. The two wrinkles that turn one multiply into a protocol

If the story ended at "encrypt, multiply, decrypt," the OPRF would be a single round. Two facts of lattice life make it more interesting.

Wrinkle 1: the output is noisy, and rounding it is the hard part

Ring-LWE encryption is noisy on purpose — that noise is what hides the secret (article 01, §3). So what the client decrypts is not exactly ⟨a_x, s⟩ but ⟨a_x, s⟩ + (noise). For a PRF we need a crisp, agreed-upon value, so we have to round the noisy result to kill the noise. Rounding sounds trivial, but it hides two problems:

  • Agreement across the noise boundary. If the true value sits right next to a rounding boundary, the client and server can round to different sides because of their independent noise — and then Alice and Bob would compute different presence_ids for the same number. The protocol has to make rounding robust so this essentially never happens.
  • Rounding must not leak. The server helps set up the rounding but must not learn the rounded value (that would break obliviousness). So we cannot just have the server round and tell the client.

The elegant fix is to do the rounding through Oblivious Transfer — a primitive where the client picks one of two secret-server-provided messages per coefficient without the server learning which it picked. That is its own article, Post-Quantum Oblivious Transfer, and the specific way we wire OT into rounding (so the client recovers the correct rounded bits and the server learns nothing) is Rounding by Oblivious Transfer (Route B). This is why the OPRF is a two-round protocol: round one is the OLE and the setup of the rounding tables; round two is the client redeeming the oblivious transfers to finish the rounding.

We could have chosen a different PRF that avoids rounding — for instance one based on a different lattice assumption where the output is naturally clean. Those exist (e.g., "even-modulus" or "ternary" tricks), but they either weakened the pseudorandomness argument, blew up the number of rounds, or made the verifiability story (article 03) far harder, because a clean output usually means a more complicated relation to prove. Rounding-via-OT kept the core relation linear, which paid off enormously when we had to prove it in zero-knowledge.

Wrinkle 2: we only need a prefix

The raw PRF output is 512 coefficients. But presence_id only consumes the first 32 (PRESENCE_TRUNC = 32), because 32 coefficients hashed by SHAKE-256 already give a collision-resistant 32-byte identifier. That means the expensive part — the oblivious rounding, which costs one OT per coefficient — runs on 32 values, not 512. This one design choice cuts the round-two work by 16× and shows up as a speedup in every later article. It is a small reminder that in applied cryptography, deciding how much of the output you actually need is a first-class optimization.

5. Stability: why s never rotates

A subtle but load-bearing requirement: s is the everlasting key. It is generated once and never changes.

The reason is discovery's determinism requirement. A user's presence_id must be stable across device reinstalls, new phones, and years of time — if it changed, everyone who ever saved you as a contact would silently lose the ability to find you. Since presence_id = Hash(F_s(phone)) and the phone number is fixed, stability forces s to be fixed too. Rotating s would re-scramble every identifier in the system at once.

This has a sharp consequence we will confront in The Verifiable OPRF: because s is a single, permanent, high-value secret, we cannot lean on "rotate the key if it leaks" as a safety net, and we have to be extremely careful that the server cannot quietly use a different key per victim. A permanent global secret is a permanent global liability, and a lot of the verifiability engineering exists precisely to fence it in.

6. The end-to-end flow, from number to identifier

Assembling the pieces, resolving one contact looks like this:

  1. Client, local. Compute a_x = HashToRing(phone). Generate a fresh Ring-LWE keypair (used once, for this query only). Encrypt a_x. This encryption is the client's "sealed film."
  2. Round 1 → server. Send the ciphertext. The server homomorphically computes ⟨a_x, s⟩ on it, and prepares the per-coefficient oblivious-transfer tables that will let the client round the 32 needed coefficients. It returns the encrypted result plus the OT setup — and, as article 03 will add, a proof that it used the committed s.
  3. Client, local. Decrypt to get the noisy inner product. It cannot yet round safely on its own — that is what round two is for.
  4. Round 2 ↔ server. The client redeems one oblivious transfer per needed coefficient to obtain the correct rounded bits, learning nothing it should not and revealing nothing about which values it holds.
  5. Client, local. Assemble the 32 rounded coefficients, hash with SHAKE-256, and get a 32-byte presence_id.

Throughout, the server sees only ciphertexts it cannot decrypt and OT choices it cannot read. It never learns the phone number, the output, or even whether this lookup succeeded.

7. What this article set up, and where it goes next

We now have an OPRF that is:

  • post-quantum, resting only on Ring-LWE (hiding) and, once we add proofs, Ring-SIS (binding);
  • oblivious, via homomorphic evaluation for the linear part and oblivious transfer for the rounding;
  • deterministic and stable, via a permanent everlasting key s.

But it is only half a security story. Everything above assumes the server tries to keep your input secret. It does nothing to stop a server that lies about which key it used. Closing that gap is the subject of the next article — and it is where this project spent most of its effort, because proving "I did this lattice computation honestly," in zero-knowledge, fast enough for a phone, is genuinely hard.

The engine-room articles beneath this one:

References

  • M. Freedman, Y. Ishai, B. Pinkas, O. Reingold, "Keyword Search and Oblivious Pseudorandom Functions," TCC 2005 — OPRFs and their use in private matching.
  • A. Boldyreva et al. and the line of work on lattice-based PRFs; see A. Banerjee, C. Peikert, A. Rosen, "Pseudorandom Functions and Lattices," EUROCRYPT 2012 — the "learning with rounding" idea that a rounded inner product is a PRF.
  • S. Jarecki, H. Krawczyk, J. Xu, and RFC 9497 — the classical elliptic-curve OPRF we deliberately did not use.
  • Wikipedia: Oblivious pseudorandom function, Pseudorandom function family, Oblivious transfer.

Next: The Verifiable OPRF: Trust, but Verify.