This is the deepest and hardest piece of the whole system: a NIZK, a non-interactive zero-knowledge proof. A zero-knowledge proof convinces you a statement is true while revealing nothing else; non-interactive means it arrives as a single message, no back-and-forth. One is attached to every OPRF reply (the OPRF being the keyed hash the server computes for the client without ever seeing the client's input), certifying "I did this lattice computation with the committed key." It must reveal nothing about the key, and it has to be small enough and fast enough to run on a phone. This article is the map of that proof system; three companion articles fill in the terrain.
Prerequisites: The Verifiable OPRF (why we need this), SIS-binding from Lattice Foundations (SIS is the "short integer solution" lattice problem, and a commitment is SIS-binding when changing the committed value would require solving it) and the convolution relation from OLE from Ring-LWE (what we're proving about; OLE is oblivious linear evaluation, the server applying its secret linear function to the client's encrypted input).
Strip away the framing and the proof certifies a statement about one OLE reply.
Three things are public: the client's query ciphertext (its encrypted query), the server's reply
ciphertext, and the pinned commitment Com(s), a short, unchangeable fingerprint of the
server's key, shipped with the app. The server claims to know secret values making all of the
following true at once.
Com(s) = A·s, so it is the
key behind the commitment pinned in the app.Every one of these is a linear relation over short values. There are no multiplications of two secrets and no general circuit, a deliberate consequence of the design choices in OLE from Ring-LWE and Rounding by Oblivious Transfer.
That linearity is the entire reason a lattice proof is feasible here. General lattice SNARKs do exist (a SNARK, a succinct non-interactive argument of knowledge, is a proof system that handles an arbitrary computation written as a circuit, rather than a fixed set of linear relations), but they are far heavier.
And "I know secret witnesses satisfying these public linear relations, and they are all short" (a witness is simply the bundle of secret values a prover claims to know) is exactly the statement modern lattice proof systems are built to produce. §5 says which one we use.
A zero-knowledge proof is judged on three things, and it helps to hold all three in mind because the engineering trades between them:
The art is achieving all three while the proof stays small (bytes on the wire) and fast, meaning a phone verifies it in under a second.
Those last two are not properties of "a proof" in the textbook. They are the whole engineering project, and the proof ring, packed encoding and succinct folding are how we won them.
Almost every proof of this kind (classical or lattice) has the same three-move skeleton, the Sigma protocol shape, a standard three-message exchange between prover and verifier:
t = A·w, for the short witness
vector w that bundles s, R and the carries.z = y + c·w, with y a random mask, and it lets the
verifier check a public equation relating t, c and z.Why does this convince anyone? Because of special soundness.
Suppose a cheating prover could answer two different challenges c ≠ c′ against the same commitment t. From the two responses z and z′ you could algebraically extract the witness w: subtract one response from the other, divide by c − c′.
So either the prover genuinely knows a valid short w, or it can only answer one challenge in a million, and a random challenge catches it.
The crucial part is what the extraction yields. The extracted w is short and satisfies the relation, so extracting a fake proof's witness would hand you a short SIS solution: the very thing assumed impossible. Soundness is special-soundness plus SIS-hardness, and that chain is the beating heart of why the proof is trustworthy.
The chain has a real subtlety in the lattice world. Dividing by c − c′ requires that challenge differences be invertible in the ring (that dividing by them is even a legal operation), which is one of the reasons the proof ring is chosen the way it is (The Proof Ring).
The skeleton above is interactive: the verifier sends a live challenge. What we need is a non-interactive proof: one blob the server attaches to its reply, with no back-and-forth.
The standard transformation is Fiat–Shamir. Replace the verifier's random challenge with a hash of the transcript so far, the transcript being the running record of every message sent up to that point. The challenge c becomes the SHAKE-256 hash of everything committed so far.
The prover cannot control the hash, so it cannot rig the challenge, and the argument still holds. The whole proof is now deterministic given the statement, which is what makes it non-interactive.
Using SHAKE-256 (a standard cryptographic hash with flexible output length) keeps this step post-quantum as well. The formal setting is the "quantum random oracle model." A random oracle is an idealised hash that behaves like a perfectly random function; the quantum version is the standard way of analysing a hash-derived challenge against an attacker who can evaluate the hash on many inputs at once. The project's formal proofs address it explicitly.
How does z = y + c·w avoid leaking w?
By only sometimes sending it. The prover draws the mask y from a distribution and then rejects and retries whenever z would fall outside a fixed safe region, a region defined independently of w.
This is rejection sampling, Lyubashevsky's technique, and it is the core of the "Fiat–Shamir with aborts" paradigm behind Dilithium, the lattice signature scheme standardized by NIST, the US national standards institute.
The effect is that the distribution of the transmitted z is statistically independent of the secret. The client sees a z that could have come from any valid witness. That is the zero-knowledge.
Run the skeleton directly on our statement and you get a correct proof that is a disaster in practice.
At the evaluation parameters (dimension M = 4096, thousands of witness values), the response z alone is multiple megabytes, and producing and checking it takes tens of seconds to minutes.
A multi-megabyte, minute-long proof on every contact lookup is not a feature anyone keeps.
Getting from there to 52 KB, sub-second on a phone took three independent ideas, each its own article. They attack different costs, and they compose:
| Lever | What it attacks | Rough effect | Article |
|---|---|---|---|
| The proof ring | Correctness of the exact-integer relation | Makes the honest statement provable at all (no wraparound loophole) | Algorithm: The Proof Ring |
| Packed encoding | The prover's speed (witness size) | Witness shrinks ~64×; the biggest single speedup | Algorithm: OLE Packed |
| Succinct folding | The proof's size | Linear → logarithmic; megabytes → ~52 KB | Algorithm: Succinct Proofs by Folding |
The order to read them is the order of dependency: the ring makes the statement sound, packing makes the prover fast, folding makes the proof small.
All three preserve the completeness, soundness and zero-knowledge triple from §2. None of them is a shortcut that trades away security. Each is a change of representation that keeps the exact same relation and the same SIS reduction.
One named building block from the recent lattice-proof literature carries most of the weight.
Greyhound (Nguyen–Seiler, 2024) is a polynomial commitment (a scheme for committing to a long vector of values and later proving facts about it) whose opening proof grows with the square root of the vector length rather than linearly in it. We built it in-tree as an alternative front-end, but it is not what ships today.
What keeps the shipped commitment side from dominating is simpler than Greyhound: the commitment is a fixed number of ring elements regardless of witness length, so it was never the term that grew.
We build on LaBRADOR rather than inventing a proof system from scratch for four reasons. It is recent and peer-reviewed. It is transparent, meaning no trusted setup: no secret parameter generated once at the start that would let whoever kept a copy forge proofs forever. And it rests on plain Module-SIS, matching every constraint we had already set.
And fourth: rolling our own would have meant re-deriving their soundness proofs, and there is no faster way to introduce a subtle, catastrophic bug into a security system than a bespoke proof system.
It is worth being explicit about the trust chain, top to bottom, because it is the payoff of all this machinery:
A malicious server that could make a false OLE reply and a proof the client accepts could be run twice on two challenges to extract a short witness for a false statement. That witness is a short solution to
A·z ≡ 0: a break of Module-SIS, which is to say a short vector in a lattice, which no algorithm, classical or quantum, is believed to find.
So "the server cannot cheat contact discovery" is, at the bottom, "short vectors in high-dimensional lattices are hard."
Everything in this article, and in The Proof Ring, OLE Packed and Succinct Proofs by Folding, exists to make that reduction hold (soundness), reveal nothing (zero-knowledge), and fit on a phone (52 KB, sub-second).
Next, descend further: Algorithm: The Proof Ring.