The heart of contact discovery is a two-party ritual that turns a phone number into a stable, unlinkable identifier. The client supplies the number and never sees the server's secret. The server supplies the secret and never sees the number. This article is how we built that ritual out of lattices, with none of the classical cryptography a quantum computer would break.
Prerequisites: the problem framing in Contact Discovery and the vocabulary in Lattice Foundations. The short refresher: LWE (Learning With Errors) is the problem of recovering a secret from linear equations that have been deliberately blurred with small random noise. Ring-LWE is its faster variant over polynomials. Both are believed to stay hard even against quantum computers, unlike the elliptic-curve math most of today's internet leans on.
An Oblivious Pseudorandom Function (an OPRF) is a keyed function F_s(x) that two
parties compute together. One party brings the secret key s; the other brings the input
x. It has to satisfy three properties, and they pull in different directions.
F_s evaluated on a thousand inputs tells you nothing about its value on the next one.
This is what defeats the enumeration attack from
the problem statement: no key, no precomputed table from
phone numbers to identifiers.presence_id for Bob's number, or they can never match.Properties 1 and 2 together are just the definition of a pseudorandom function (a PRF): a deterministic, key-controlled scrambler. Property 3 is the "oblivious" adjective, and it is the whole difficulty.
Building a PRF is easy. Building one that two mutually suspicious strangers can jointly evaluate, each keeping their half 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 is SHAKE-256, a quantum-safe member of the SHA-3 family, and it does three jobs at once.
It compresses the PRF output down to a tidy 32 bytes. It destroys any leftover algebraic structure, so none of the lattice arithmetic survives into the identifier. And (the job that matters most for performance) it means the client only ever has to obliviously compute a prefix of the raw PRF output: the first 32 of its 512 numbers, called coefficients. §4 shows what that buys.
It is worth seeing the thing we gave up, because it is so clean.
Classically, you represent the phone number as a point P on an elliptic curve (the
kind of curve whose point arithmetic underpins most of today's public-key cryptography)
and define the PRF as F_s(P) = s·P: the point multiplied by the server's secret
number s, called a scalar.
Obliviousness is one line. The client picks a random blinding scalar r (a
one-time mask that scrambles the point beyond recognition) and sends r·P. The server
multiplies by its secret and returns s·r·P. The client multiplies by the inverse of
r, the blinding cancels, and out comes s·P.
That construction is deterministic, since the same P always gives the same s·P.
It is pseudorandom under the
decisional Diffie–Hellman assumption,
the standard bet that a curve point scrambled by a secret scalar is indistinguishable from
a random one. And it costs about 64 bytes on the wire.
We could have shipped exactly this.
The reason we did not is the post-quantum requirement from
Contact Discovery. The security of s·P rests entirely on
the discrete-logarithm problem being hard: that is, on nobody being able to recover
s from seeing P and s·P. Shor's algorithm solves exactly that problem on a
quantum computer.
Discovery traffic reveals a social graph, and a social graph is a secret with a decades-long shelf life. An adversary who records that traffic today can decrypt it whenever quantum computers arrive: the harvest-now-decrypt-later problem. For a feature whose entire output is long-lived linkage, that was not a risk worth carrying. So we needed both a PRF and an obliviousness mechanism resting on lattices instead.
There is also an in-between option we considered and rejected: constructions that keep the classical shape (a Diffie–Hellman-like blinding) but swap the group for something post-quantum. Isogeny-based OPRFs are the best-known example. (Isogenies are a rival post-quantum family, built on structure-preserving maps between elliptic curves rather than on lattices.)
These fall down in one of three ways. Some turn out to be classical assumptions in disguise. Some are simply immature: isogeny assumptions took serious cryptanalytic hits in 2022 and 2023. And some demand a fully interactive dance with rejection sampling, where a party discards and retries whenever a sampled value lands outside a safe range, which is fiddly to pin to a fixed number of rounds.
We wanted something that reduces to standard Ring-LWE and Ring-SIS, the two workhorse lattice problems from Lattice Foundations, with no exotic assumptions. That pushed us to build the OPRF directly out of homomorphic evaluation: doing arithmetic on encrypted data without ever decrypting it.
Here is the reframing that makes a lattice OPRF possible. Define the PRF as a rounded inner product (multiply matching entries of two vectors, add everything up, then snap the sum to the nearest clean value):
F_s(x) = Round(⟨a_x, s⟩)
a_x is public. It is the phone number x hashed into the ring by a fixed, published
map: a "hash to ring." Anyone can compute a_x from a number; 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 is exactly an LWE-style problem. Each
pair (a_x, F_s(x)) hands an attacker one rounded, noisy linear equation in the unknown
s, and Lattice Foundations established that recovering a
secret from noisy linear equations is a hard lattice problem.
So the outputs are pseudorandom to anyone without s (property 1). They are deterministic,
since a_x and s are both fixed (property 2). That leaves obliviousness.
And obliviousness now has a crisp shape. The client holds a_x. The server holds s. We
need the client to end up with ⟨a_x, s⟩ without either side revealing its
half.
That exact two-party task has a name: Oblivious Linear Evaluation, or OLE, and it is where the real machinery goes. It gets its own deep dive in Oblivious Linear Evaluation from Ring-LWE.
The one-paragraph version: the client encrypts a_x under a freshly generated Ring-LWE key
and sends the ciphertext. The server computes the inner product on the ciphertext, never
decrypting it, and returns an encrypted result that only the client can open. This works
because Ring-LWE encryption is homomorphic: arithmetic done on ciphertexts lands
correctly on the plaintexts sealed inside them.
If the story ended at "encrypt, multiply, decrypt," the OPRF would be a single round trip. Two facts of lattice life make it more interesting.
Ring-LWE encryption is noisy on purpose: the noise is what hides the secret
(Lattice Foundations, §3). So what the client decrypts is not
⟨a_x, s⟩ but ⟨a_x, s⟩ plus a small error term.
A PRF needs a crisp, agreed-upon value, so the noise has to be rounded away. Rounding sounds trivial. It is not, because after the OLE neither side actually holds the value.
What each side holds is an additive share: one of two numbers that mean something
only when combined. The client has u, the server has r, and the two satisfy
u − r ≡ a_x·s (mod q): subtract them, wrapping around at the modulus q, and the
true value appears. Neither number alone means anything.
Rounding a difference of shares is not a local operation. Think of grade-school column subtraction, where whether you borrow from the next column depends on a digit you might not hold. Working from the low bytes of the two shares, everything the client needs is determined except a single borrow bit: whether the server's low byte exceeds its own. The client cannot compute that bit without being told the server's low byte, and the server's low byte is a piece of the key.
That one missing bit creates two requirements at once.
presence_ids for the same number. The protocol must resolve
the bit exactly, not probabilistically.The fix is Oblivious Transfer: a primitive where the client picks one message out of a set the server offers, and the server does not learn which one it picked.
Here the choice is 1-of-256, indexed by the client's own low byte. The client recovers exactly the borrow it needs, and the server learns neither the index nor the result. OT has its own article, Post-Quantum Oblivious Transfer, and the specific way we wire it into rounding is Rounding by Oblivious Transfer (Route B).
This is why the OPRF is a two-round protocol. Round one is the OLE plus the setup of the rounding tables. Round two is the client redeeming the oblivious transfers to finish the rounding.
We could have picked a different PRF that avoids rounding altogether: one built on a lattice assumption whose output comes out naturally clean. Such constructions exist; "even-modulus" and "ternary" tricks are the usual examples.
We rejected them for three reasons. They weakened the pseudorandomness argument, or they blew up the number of rounds, or they made verifiability much harder. The last one decided it. A clean output usually means a more complicated relation (the algebraic statement a proof has to establish), and Trust, but Verify has to prove that relation on a phone. Rounding-via-OT keeps the core relation linear, which paid off enormously when we came to prove it in zero-knowledge: that is, to prove the computation was done correctly without revealing any of the secrets inside it.
The raw PRF output is 512 coefficients. But presence_id consumes only the first 32
(PRESENCE_TRUNC = 32), because 32 coefficients hashed by SHAKE-256 already give a
collision-resistant 32-byte identifier: one where finding two phone numbers that land on
the same identifier is computationally out of reach.
That matters because the expensive part (the oblivious rounding) costs one OT per coefficient. Running it on 32 values instead of 512 cuts the round-two work by 16×, and the saving shows up 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.
A subtle but load-bearing requirement: s is generated once and never changes. We call it the everlasting key.
The reason is discovery's determinism requirement. A presence_id has to stay stable
across device reinstalls, new phones, and years of time. If it changed, everyone who had
ever saved you as a contact would silently lose the ability to find you.
Since the identifier is 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, which The Verifiable OPRF confronts head-on. Because s is a single permanent high-value secret, "rotate the key if it leaks" is not available to us as a safety net. Worse, we have to make sure the server cannot quietly use a different key per victim.
A permanent global secret is a permanent global liability, and a great deal of the verifiability engineering exists precisely to fence it in.
Assembling the pieces, resolving one contact looks like this.
a_x = HashToRing(phone). Generate a fresh Ring-LWE keypair,
used once for this query and then discarded. Encrypt a_x under it.⟨a_x, s⟩ on it and prepares the per-coefficient oblivious-transfer tables
the client will need for its 32 coefficients. It returns the encrypted result, the OT
setup, and, as Trust, but Verify will add, a proof that
it used the committed key.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 the lookup found anything.
We now have an OPRF that is:
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 Verifiable OPRF, and it is where this project spent most of its effort. 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: