Contact Discovery

Algorithm: The NIZK

8 min read

This is the deepest and hardest piece of the whole system: a non-interactive zero-knowledge proof, attached to every OPRF reply, that certifies "I did this lattice computation with the committed key" — without revealing the key, 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, and the convolution relation from OLE from Ring-LWE (what we're proving about).

1. Exactly what is being proven

Strip away the framing and the proof certifies a statement about one OLE reply. Public are: the client's query ciphertext, the server's reply ciphertext, and the pinned commitment Com(s). The server claims to know secret values making all of the following true at once:

The evaluation is correct. The reply ciphertext is the honest homomorphic application of a key s to the query — the negacyclic convolution from article 06, plus the mask R.
The key is the committed one. That same s satisfies Com(s) = A·s, i.e., it is the key behind the app-pinned commitment.
The rounding is consistent (the Route B clause from article 08): the byte-split of the folded mask is tied to the committed R.
Everything is short. The secrets s, R, and the carries are all small — which, as we'll see, is what makes the whole thing bind to a lattice problem.

Every one of these is a linear relation over short values. There are no multiplications of two secrets, no general circuit — a deliberate consequence of the design choices in articles 06 and 08. That linearity is the entire reason a lattice proof is feasible here; general lattice-SNARKs for arbitrary circuits exist but are far heavier.

A proof of "I know secret witnesses satisfying these public linear relations, and they're all short" is exactly what modern lattice proof systems (LaBRADOR, Greyhound) are built to produce.

2. Three properties a proof must have

A zero-knowledge proof is judged on three things, and it helps to hold all three in mind because the engineering trades between them:

Completeness. An honest server always convinces the client. (Easy to get; easy to break by accident with over-aggressive optimizations — the noise/rounding must not cause honest rejections.)
Soundness. A cheating server — one that used the wrong s, or a made-up reply — cannot convince the client except with negligible probability. This is the security property, and for us it reduces to Module-SIS: a server that could forge a proof could be used to solve SIS, which is assumed impossible (article 01, §2).
Zero-knowledge. The proof reveals nothing about the secrets beyond the truth of the statement. Since the secret is the everlasting master key s, this is non-negotiable — a proof that leaked one bit of s per reply would be a slow-motion catastrophe.

The art is achieving all three while the proof stays small (bytes on the wire) and fast (a phone verifies in under a second). Those last two are not properties of "a proof" in the textbook — they are the whole engineering project, and articles 10–12 are how we won them.

3. The skeleton: commit, challenge, respond

Almost every proof of this kind — classical or lattice — has the same three-move skeleton, the Sigma protocol shape:

Commit. The prover commits to its secret witness (here, using the Module-SIS commitment from article 01: t = A·w for the short witness vector w, which includes s, R, and the carries).
Challenge. The verifier sends a random challenge c.
Respond. The prover replies with a value z that combines the witness and the challenge — for a linear relation, z = y + c·w for a random mask y — such that the verifier can check a public equation relating t, c, and z.

Why does this convince anyone? Because of special soundness: if a cheating prover could answer two different challenges c ≠ c' for the same commitment t, then from the two responses z, z' you can algebraically extract the witness w (subtract, 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. Crucially, the extracted w is short and satisfies the relation, so extracting a fake proof's witness would hand you a short SIS solution. Soundness is special-soundness plus SIS-hardness, and that chain is the beating heart of why the proof is trustworthy. (This chain has a real subtlety in the lattice world — dividing by c − c' requires that challenge differences be invertible in the ring — which is one of the reasons the proof ring is chosen the way it is: The Proof Ring.)

From interactive to non-interactive: Fiat–Shamir

The skeleton above is interactive (the verifier sends a live challenge). We need a non-interactive proof — one blob the server attaches to its reply, no back-and-forth. The standard transformation is Fiat–Shamir: replace the verifier's random challenge with a hash of the transcript so far, c = SHAKE-256(everything committed up to this point). Since the prover cannot control the hash, it cannot rig the challenge, so the argument still holds — and now the whole proof is deterministic given the statement, hence non-interactive. We use SHAKE-256 for the hash, so this step is post-quantum too (in the "quantum random oracle model," which the project's formal proofs address explicitly).

Zero-knowledge: the rejection-sampling trick

How does z = y + c·w avoid leaking w? By choosing the mask y from a distribution and only sometimes sending z — specifically, the prover rejects and retries whenever z would fall outside a fixed "safe" region that is independent of w. This rejection sampling (Lyubashevsky's technique, the core of the "Fiat–Shamir with aborts" paradigm behind Dilithium) makes the distribution of the transmitted z statistically independent of the secret. The client sees a z that could have come from any valid witness. That is the zero-knowledge.

4. Why the naive version is unusable, and the three levers

Run the skeleton directly on our statement and you get a correct proof that is a disaster in practice: at the evaluation parameters (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)	10
Packed encoding	The prover's speed (witness size)	Witness shrinks ~64×; the biggest single speedup	11
Succinct folding	The proof's size	Linear → logarithmic; megabytes → ~52 KB	12

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 / zero-knowledge triple from §2 — none of them is a shortcut that trades away security; each is a representation change that keeps the exact same relation and the same SIS reduction.

5. The commitment scheme underneath: LaBRADOR and Greyhound

Two named building blocks from the recent lattice-proof literature carry most of the weight, and it is worth knowing which does what.

LaBRADOR (Beullens–Seiler, 2023) is the recursive proof machinery: it proves knowledge of a short witness satisfying a system of (dot-product) constraints over a module lattice, and it is the framework whose Sigma-protocol-plus-folding shape our proof follows. Its soundness is the special-soundness-to-Module-SIS chain from §3.
Greyhound (Nguyen–Seiler, 2024) is a fast polynomial commitment: it lets the prover commit to a long vector and later open an evaluation of it with a proof of size only about the square root of the vector length — a √N opening rather than a linear one. This is a key ingredient in keeping the commitment side of the proof from dominating.

We build on these rather than inventing a proof system from scratch because they are recent, peer-reviewed, transparent (no trusted setup), and rest on plain Module-SIS — matching every constraint we set. 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.

6. Where the security ultimately rests

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 — which is a short solution to A·z ≡ 0, i.e., a break of Module-SIS, i.e., 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 the next three exists to make that reduction hold (soundness), reveal nothing (zero-knowledge), and fit on a phone (52 KB, sub-second).

7. Summary

The NIZK proves, per OLE reply, a bundle of linear relations over short secrets: correct evaluation, committed key, consistent rounding, all short.
It follows the commit–challenge–respond skeleton, made non-interactive by Fiat–Shamir (SHAKE-256) and zero-knowledge by rejection sampling.
Its soundness is special-soundness reduced to Module-SIS: forging a proof would solve a hard lattice problem.
The naive proof is megabytes and minutes; three levers — the proof ring, packed encoding, and succinct folding — bring it to 52 KB, sub-second on a phone, without weakening any of the three properties.
We build on LaBRADOR and Greyhound rather than a bespoke system, for transparency, standard assumptions, and peer-reviewed soundness.

References

A. Fiat, A. Shamir, "How to Prove Yourself: Practical Solutions to Identification and Signature Problems," CRYPTO 1986 — the interactive-to-non-interactive transform.
V. Lyubashevsky, "Fiat–Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures," ASIACRYPT 2009 — the rejection-sampling zero-knowledge technique.
W. Beullens, G. Seiler, "LaBRADOR: Compact Proofs for R1CS from Module-SIS," CRYPTO 2023.
N. Nguyen, G. Seiler, "Greyhound: Fast Polynomial Commitments from Lattices," CRYPTO 2024.
Wikipedia: Zero-knowledge proof, Proof of knowledge, Fiat–Shamir heuristic, Sigma protocol.

Next, descend further: Algorithm: The Proof Ring.