Contact Discovery

The Verifiable OPRF: Trust, but Verify

10 min read

The oblivious OPRF from the last article stops a curious server from reading your input. It does nothing to stop a lying server from using the wrong key. This article is about the second adversary — the one who follows the protocol perfectly while secretly running it with a different secret for you than for everyone else — and the zero-knowledge machinery we built to shut that attack down without ever revealing the key.

Prerequisites: The Lattice OPRF, and the SIS-means-binding idea from Lattice Foundations.

1. The attack obliviousness misses

Recall the setup: presence_id = Hash(F_s(phone)), and s is a single everlasting key that must be the same for everyone, forever, or discovery breaks (article 02, §5).

Now put on the hat of a malicious operator who wants to de-anonymize one specific user, Alice. You cannot read Alice's inputs — the OLE is oblivious, that part is airtight. But nothing so far forces you to use the real s when you answer Alice. So you do this:

For everyone in the world, answer honestly with the real key s.
For Alice, answer with a special key s_Alice that only you know, chosen so that the presence_ids Alice computes fall into buckets you control.

What did that buy the attacker? Alice's computed IDs now depend on s_Alice, which the attacker chose. By crafting s_Alice and watching which lookups Alice subsequently makes (and, combined with the PIR layer, how the directory responds), the attacker can probe Alice's contact set — a selective-failure / key-tagging attack. The obliviousness of the OLE is perfect and completely beside the point, because the leak came from the server using an inconsistent key, not from reading the input.

This is a general and easy-to-underestimate lesson: privacy against a passive server is not privacy against an active one. A protocol can be flawlessly oblivious and still be broken by a server that deviates from the honest computation. To be safe against a malicious server, the client needs a way to check that the server behaved — specifically, that it used the one true, publicly committed key.

2. The fix, in one sentence

The server publishes a one-time, tamper-evident commitment Com(s) to its key, bakes it into the app, and then proves — in zero knowledge, on every single reply — that the key it just used is the key behind Com(s). The client checks the proof before it reveals anything further, and aborts if it fails.

"Zero knowledge" is the crucial adjective. The server must convince the client of a statement about s ("my reply is consistent with the committed s") while revealing nothing else about s — because s is the master secret whose exposure would let anyone compute everyone's presence_id. That is exactly what a zero-knowledge proof is for: prove a statement is true without revealing why it is true.

This upgrades our OPRF into a Verifiable OPRF (VOPRF). The classical world has a famously slick VOPRF — attach a Chaum–Pedersen DLEQ proof that the same scalar s was used, three group elements and done. But that proof, like the OPRF it accompanies, is built on discrete log and dies to Shor. We needed a post-quantum zero-knowledge proof about a lattice computation, and that is a different order of difficulty entirely.

3. The commitment: sealing the key once

Com(s) is a Module-SIS commitment. Recall from article 01 that if you fix a random matrix A and define Com(s) = A · s for a short s, then binding — the impossibility of finding a second short s' ≠ s with A·s' = A·s — reduces directly to the hardness of SIS. So Com(s) behaves like a sealed fingerprint of the key: the operator computes it once at setup, publishes it, and it gets hard-coded into every client build (a "pinned" 32-byte hash SHAKE-256(Com(s))).

Two properties matter:

It reveals nothing. Com(s) hides s (Module-LWE / the hiding of the commitment), so publishing it does not help anyone compute presence_ids.
It is un-equivocable. The operator cannot later claim a different key matches the same commitment, because that would mean solving SIS.

Because Com(s) is pinned in the app and identical for all users, the per-victim-key attack now has nowhere to hide: if the operator answers Alice with s_Alice ≠ s, it cannot produce a valid proof that s_Alice matches the pinned Com(s), and Alice's client rejects the reply. The attacker is forced to either behave or be caught.

4. What exactly has to be proven

Zoom into a single OLE reply. The public facts are: the client's query ciphertext, the server's reply ciphertext, and the pinned commitment Com(s). The server's claim is:

"There exists a short secret s and short noise/mask R such that (a) my reply ciphertext is the correct homomorphic evaluation of s on the query, and (b) this s is the one committed in Com(s)."

Both halves are linear relations over the evaluation ring — the reply is a convolution of the query with s plus a masking term, and the commitment is A·s. Two subtleties make proving them exactly harder than it looks, and each becomes its own article:

"Exact integer" arithmetic (no wraparound). The homomorphic evaluation happens modulo a BFV encryption modulus Q = 2⁴². But a proof about arithmetic that has been reduced mod Q is a proof about a lie — the true relation involves the un-reduced integers plus explicit "carry" terms saying how many times each coefficient wrapped around Q. If we proved the mod-Q version, a cheating server could exploit the wrap to open the same commitment two ways (an equivocation). So the proof works over a ring big enough to hold the exact integers, and proves the carries are correct. Why the proof ring is a specific size, and how the carries pin down the exact relation, is The Proof Ring.
The rounding relation (Route B). Beyond the linear evaluation, the rounding step (article 02's wrinkle 1) also has to be tied to the committed values, or a server could cheat on the rounding instead of the multiply. Binding the rounding into the proof is the "Route B" clause described in Rounding by Oblivious Transfer.

The engine that actually produces a zero-knowledge proof of these linear-algebra statements is Algorithm: The NIZK. It is the largest article in the series, and for good reason.

5. Why the proof was the hard part: size and speed

Here is the uncomfortable truth about post-quantum zero-knowledge proofs of arbitrary computations, circa the time we built this: the honest, textbook way to prove "these lattice equations hold" produces a proof that is multiple megabytes and takes tens of seconds to minutes to generate and check, at our parameters (a M = 4096-dimensional evaluation ring). A multi-megabyte proof attached to every contact lookup, verified on a phone, is a non-starter — nobody will keep a feature that stalls for a minute per contact.

So most of the verifiable-OPRF work was a size-and-speed campaign, and it stacked three independent ideas, each covered in its own article:

A packed encoding (OLE Packed). The naive proof treats each of the ~16,000 witness numbers as its own ring element, wasting 63 of every 64 coefficient slots. Packing 64 integers into each ring element shrinks the secret being proven about by 64×, which is the single biggest lever on prover speed.
Succinct folding (Succinct Proofs by Folding). A proof whose size is linear in the witness is compressed to logarithmic by a recursive "fold," the lattice analog of the inner-product argument that makes Bulletproofs short. This is what takes the proof from megabytes to ~52 kilobytes.
The right proof ring (The Proof Ring), so the exact integer relation is provable at all without the wraparound loophole.

The endpoint of that campaign: a 52 KB proof the server produces in a couple of seconds and the client verifies in well under a second on a phone. We validated the full path on a device — a real client, a real server, the proof checked fail-closed, and the correct presence_id came out. That number, 52 KB, is not cosmetic; it is the difference between a feature that ships and one that does not.

A road we explored and left behind

For a while we carried a second fast-proof design in parallel — a "sublinear-verifier" scheme where the client's checking time grew like the square root of the witness rather than linearly. It was clever and it worked. But once the packed encoding made the witness tiny (~200 ring elements), the client's verification was already cheap, so the elaborate sublinear-verify machinery was solving a problem we no longer had. Two proof systems that do the same job are not a feature; they are twice the code to audit and twice the surface for a bug. We could have kept both "just in case," but in security, unused complexity is a liability, not a hedge — so the mechanism converged on the single packed-and-folded proof. That convergence is the subject of the whole series' recurring theme: a singular way you can fully reason about beats a menu of clever options you cannot.

6. Fail-closed: the discipline that makes it real

A proof system is only as good as what the client does when the proof fails. Two principles govern the client here, and both are the paranoid choice on purpose:

Verify before you reveal. The client checks the proof before it does round two of the OPRF (before it redeems any oblivious transfer, before it exposes any choice). So a server that cannot prove honest behavior learns nothing — it never gets to the step where the client's behavior would leak anything.
No unverified fallback, ever. There is exactly one verifiable path. If the proof does not check out, the resolution fails; it does not silently downgrade to an unverified mode. This matters because a downgrade is itself an attack: a malicious server could pretend the verifiable path is "unavailable" to trick the client into the weaker mode. By refusing to have a weaker mode at all, we remove the lever. (Early designs did carry an unverified fallback for graceful degradation; we came to see that as an attacker-triggerable downgrade and removed it in favor of failing hard.)

The engineering phrase for this is fail-closed: when in doubt, deny. It is the opposite of the more common "fail-open" instinct (when in doubt, allow, so the feature keeps working), and for a privacy-critical path it is the only defensible default.

7. Where the master key still isn't the whole story

Verifiability fences in the server's dishonesty. It does not, by itself, address the fact that the VOPRF is deliberately a public service that turns numbers into IDs — including for numbers the caller does not own. That is an oracle, and oracles get abused in ways no zero-knowledge proof prevents (you are using the system exactly as designed). Rate limits, Sybil gates, and directory authentication handle that, and they are Guarding the Directory.

It also does not, by itself, hide which IDs the client looks up — that is the PIR layer, Bulk Membership.

And it does not reach the corners where a check would need the secret the protocol withholds — a rounding table you can only open one entry of, for instance. That last mile is covered by Known-Answer Testing, which catches a server using the wrong key by hiding questions with published answers among the real ones.

Verifiability is one leg of a tripod: honest computation (this article), blind lookup (PIR), and abuse resistance (directory guarding). Remove any leg and the privacy story falls over.

8. Summary

A perfectly oblivious OPRF is still broken by a server that uses an inconsistent key per victim — an active attack that obliviousness does not see.
The defense is a commitment Com(s) pinned in the app, plus a zero-knowledge proof on every reply that the key used matches the commitment — a Verifiable OPRF.
The classical VOPRF proof (Chaum–Pedersen DLEQ) is post-quantum-broken, so we built a lattice zero-knowledge proof of the linear evaluation and its exact-integer carries.
The proof was the hard part: naive versions are megabytes and minutes. Packing, folding, and the right proof ring got it to 52 KB and sub-second on a phone.
The client is fail-closed: it verifies before revealing anything and has no unverified fallback to be downgraded into.

The rest of the descent — The NIZK, The Proof Ring, OLE Packed, Succinct Folding — is how that 52 KB is actually built, and Known-Answer Testing is what guards the part a proof cannot reach.

References

S. Goldwasser, S. Micali, C. Rackoff, "The Knowledge Complexity of Interactive Proof Systems," STOC 1985 — the definition of zero-knowledge.
D. Chaum, T. Pedersen, "Wallet Databases with Observers," CRYPTO 1992 — the DLEQ proof, the classical VOPRF technique we could not use post-quantum.
W. Beullens, G. Seiler, "LaBRADOR: Compact Proofs for R1CS from Module-SIS," CRYPTO 2023 — the lattice proof recursion underneath our NIZK.
N. Nguyen, G. Seiler, "Greyhound: Fast Polynomial Commitments from Lattices," CRYPTO 2024 — the square-root-size commitment opening we build on.
Wikipedia: Zero-knowledge proof, Commitment scheme, Non-interactive zero-knowledge proof.

Next: Bulk Membership: Private Information Retrieval, or descend into Algorithm: The NIZK.