The oblivious OPRF from The Lattice OPRF (the keyed hash the server evaluates for you without ever seeing your input) stops a curious server from reading that input. It does nothing to stop a lying server from using the wrong key. This article is about that second adversary: the one who follows the protocol perfectly while secretly running it with a different secret for you than for everyone else. It is also about 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. The refresher: SIS (Short Integer Solution) is the lattice problem of finding small numbers that satisfy a given linear system, and its hardness is what stops a commitment from being opened two different ways.
Recall the setup. A presence_id is Hash(F_s(phone)), and s is a single everlasting
key that must be the same for everyone, forever, or discovery breaks
(The Lattice OPRF, §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 (Oblivious Linear Evaluation, the encrypted multiply at the heart of the OPRF) is oblivious, and that part is airtight. But nothing so far forces you to use the real key s when you answer her. So you do this:
s_Alice that only you know, chosen so the
presence_ids she computes fall into buckets you control.What did that buy the attacker?
Alice's computed IDs now depend on s_Alice, a value the attacker picked. Craft
s_Alice carefully, watch which lookups Alice makes next, and you can probe her contact
set one guess at a time. The name for this shape of attack is selective failure, or
key tagging. The blind PIR lookup that follows (PIR is
Private Information Retrieval, a way to fetch a record without the server learning which
one) does not save her, because the tag was planted before the lookup began.
The obliviousness of the OLE is perfect here, and completely beside the point. The leak did not come from reading Alice's input. It came from the server evaluating a different function for her.
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.
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 behindCom(s). The client checks the proof before it reveals anything further, and aborts if it fails.
"Zero knowledge" is the crucial adjective.
The server has to convince the client of one statement about s (my reply is consistent
with the committed key) while revealing nothing else about s. That restriction is
not fussiness. s is the master secret, and anyone who learns it can compute every
presence_id in the system.
Proving that a statement is true without revealing why it is true is exactly what a zero-knowledge proof does.
This upgrades our OPRF into a Verifiable OPRF, or VOPRF. The classical world has a famously slick one. You attach a Chaum–Pedersen DLEQ proof. DLEQ stands for discrete-log equality: a proof that the secret number behind the server's published key is the same one it just multiplied by. Three group elements (three small pieces of curve data), and you are done.
But that proof is built on discrete log, exactly like the OPRF it accompanies, and dies to Shor along with it. What we needed was a post-quantum zero-knowledge proof about a lattice computation, and that is a different order of difficulty.
Com(s) is a Module-SIS commitment, a lattice-based seal on a value: easy to check
against later, impossible to swap out.
Lattice Foundations built this piece. Fix a public random
matrix A and define Com(s) = A·s for a short s, "short" meaning its entries are
small numbers. 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 and publishes it, and a 32-byte hash of it, SHAKE-256(Com(s)), is hard-coded into
every client build.
Two properties matter:
Com(s) hides s, so publishing it does not help anyone compute
presence_ids.Because Com(s) is pinned in the app and identical for every user, the per-victim-key
attack has nowhere left to hide. If the operator answers Alice with some 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.
Zoom into a single OLE reply. Three facts are public: 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 a 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: statements built only from
additions and multiplications by known values. The reply is a convolution of the query with
s (the structured multiply used in polynomial rings) plus a masking term; the
commitment is A·s.
Two subtleties make proving them exactly harder than it looks. Each becomes its own article.
Exact integer arithmetic, with no wraparound. The homomorphic evaluation (the arithmetic done directly on encrypted data) happens inside BFV, the lattice homomorphic-encryption scheme the OLE computes in. Every operation in BFV wraps around at an encryption modulus Q = 242, the way a car odometer rolls over at its limit.
A proof about arithmetic that has already been reduced mod Q (already wrapped) is a proof about a lie. The true relation involves the un-reduced integers plus explicit carry terms, recording how many times each coefficient wrapped around Q.
Proving the reduced version instead would leave a hole. 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 as well. Why that ring has the size it does is The Proof Ring.
The rounding relation. The linear evaluation is not the only place a server can cheat. The rounding step (wrinkle 1 from The Lattice OPRF) also has to be tied to the committed values, or the server could lie there instead of in the multiply. Binding rounding into the proof is the "Route B" clause in Rounding by Oblivious Transfer.
The engine that produces a zero-knowledge proof of these statements is our NIZK: non-interactive zero-knowledge, meaning the whole argument arrives as one message attached to the server's reply, rather than as a back-and-forth challenge game.
It is The NIZK, the largest article in the series, and for good reason.
Here is the uncomfortable truth about post-quantum zero-knowledge proofs of arbitrary computations, as of when we built this.
The honest, textbook way to prove "these lattice equations hold" produces a proof of multiple megabytes that takes tens of seconds to minutes to generate and check, at our parameters: an evaluation ring of dimension M = 4096.
Attach that to every contact lookup and verify it on a phone, and the feature is a non-starter. Nobody keeps a contacts screen that stalls for a minute per name.
So most of the verifiable-OPRF work was a size-and-speed campaign. It stacked three independent ideas, each covered in its own article:
The endpoint of that campaign is 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 at the end of it. That number is not cosmetic. It
is the difference between a feature that ships and one that does not.
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.
Then the packed encoding made the witness tiny (around 200 ring elements), and the client's verification became cheap on its own. The elaborate sublinear machinery was now 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 rather than a hedge, so the mechanism converged on the single packed-and-folded proof.
That convergence is a recurring theme in this series: one path you can fully reason about beats a menu of clever options you cannot.
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 round two of the OPRF: before it redeems any oblivious transfer, before it exposes any choice. A server that cannot prove honest behavior therefore learns nothing at all. It never reaches the step where the client's own actions would leak something.
No unverified fallback, ever. There is exactly one verifiable path. If the proof does not check out, the resolution fails. It does not quietly downgrade to an unverified mode.
That matters because the downgrade is itself an attack. A malicious server could simply claim the verifiable path is "unavailable" and trick the client into the weaker one. Refusing to have a weaker mode removes the lever entirely.
Early designs did carry an unverified fallback, for graceful degradation. We came to see it 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.
Verifiability fences in the server's dishonesty. Three things it does not reach.
It does not address the fact that the VOPRF is deliberately a public service: it turns numbers into IDs, including numbers the caller does not own. That makes it an oracle (a box that answers anyone's questions), and an oracle gets abused by callers using the system exactly as designed, which is precisely what no zero-knowledge proof can prevent. Rate limits, Sybil gates (defenses against one attacker posing as thousands of users), and directory authentication handle that, in Guarding the Directory.
It does not 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 very secret the protocol withholds: a rounding table you can only open one entry of, for instance. That last mile belongs to 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.
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 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.
Next: Bulk Membership: Private Information Retrieval, or descend into Algorithm: The NIZK.