Contact Discovery

Algorithm: Rounding by Oblivious Transfer (Route B)

11 min read

Lattice encryption is noisy, so the raw output of the oblivious inner product is a fuzzy field element, not the crisp value a pseudorandom function needs. Turning that fuzz into a clean, agreed-upon, unforgeable answer — without the server learning it — is the last mile of the OPRF, and it is subtler than "just round." This article is that last mile.

Prerequisites: the noisy OLE output from OLE from Ring-LWE, and oblivious transfer from PQ Oblivious Transfer.

1. Three problems hiding inside "round the number"

After round one of the OPRF, the client can decrypt the noisy inner product v = ⟨a_x, s⟩ + noise. For a PRF we want a deterministic, clean value — the top bits of ⟨a_x, s⟩, with the noise stripped off. That is rounding: keep the high part, discard the low. Trivial on paper. Three things make it a protocol.

Agreement across the boundary. The server also holds a share of the true value (via the mask R it added in article 06). The clean output is a function of both shares. If the value sits right at a rounding boundary, the client's noise could push it to round one way while the honest value rounds the other, and then Alice and Bob would disagree on presence_id for the same number — discovery silently fails. The rounding has to be engineered so this essentially never happens.
The server must not learn the result. The rounded value is (a piece of) the PRF output. If the server learned it, obliviousness is gone. So we cannot simply have the server compute the rounding and tell the client.
Neither party can cheat the rounding. A malicious server could try to bias the output by lying about its share, and a malicious client could try to claim a rounding inconsistent with the committed values. The rounding has to be bound to what was actually committed, or it becomes a new hole exactly where the proof thought it was airtight.

Problems 1 and 2 are solved with oblivious transfer. Problem 3 is solved by folding the rounding into the zero-knowledge proof — the clause the implementation calls Route B.

2. Rounding as a secret-shared choice

Here is the reframing that lets OT do the work. The value to be rounded is additively shared: the client holds one share (what it decrypted) and the server holds the other (the mask R it injected). Their sum is the true ⟨a_x, s⟩. Rounding the sum while it lives in two halves is the classic secure-computation task, and near a boundary it comes down to a single carry bit: does the low parts of the two shares add up to something that carries into the high part?

Neither party may reveal its share, and the client must end up with the correct high bits. This is exactly the shape oblivious transfer was made for (see article 07, §5):

The server (sender) builds, for each rounded coefficient, a tiny table enumerating the possible outcomes as a function of the client's low bits — "if your low part is in this range, the correct rounded high bits are this; otherwise that." It masks each table entry so only the right one is usable.
The client (receiver) uses its own low bits as the OT choice, obliviously pulling the one correct entry.

The server never learns which entry the client took (OT receiver privacy), so it never learns the rounded value — solving problem 2. The table is constructed so the carry is resolved correctly regardless of small noise, and because we only round PRESENCE_TRUNC = 32 coefficients, this is 32 small OTs, not thousands — solving problem 1 cheaply. This is why the OPRF is two rounds: round one is the OLE plus the server publishing these rounding tables; round two is the client redeeming the 32 oblivious transfers.

3. Route B: binding the rounding parameters into the proof

Problems 1 and 2 are handled. Problem 3 — cheating the rounding — is where it gets interesting, and it is the reason this article exists as more than "we used OT."

Recall the whole point of the Verifiable OPRF: the server proves, in zero knowledge, that its reply used the committed key s. But the proof in article 09 certifies the linear evaluation (the convolution ⟨a_x, s⟩). If the rounding is a separate, unproven step layered on top, a malicious server has a fresh place to cheat: it can evaluate s honestly (passing the proof) but hand the client rounding tables built from a different value, steering the output. The proof would be perfectly valid and the output still corrupted. Closing one hole opened another one right next to it.

So the rounding has to be tied to the committed reply too. The implementation calls this the Route B clause, and the trick is to express the rounding in a way the same linear proof machinery can certify. For each of the 32 rounded coefficients, the server's folded mask value r_i is decomposed into a byte-split plus a carry:

r_i  =  256 · h_r  +  l_r        (h_r = high byte, l_r = low byte),
       with a fold-carry accounting for the negacyclic wrap of the mask.

The high byte h_r, low byte l_r, and the carry become additional witness values in the proof, tied by a linear constraint to the committed mask R. The equation 256·h_r + l_r + (carry term) = fold(R)_i is exactly the shape the article-09 proof already knows how to certify — a linear relation over committed short values. So proving the rounding parameters came from the real committed mask costs a few extra linear constraints, not a whole new proof system. In the project's internal language, the linear evaluation was "cheat #1" and the rounding is "cheat #2."

There is a machine-checked theorem behind this. The clause is an identity over the integers, and 256 divides the modulus the carry is measured in, so reducing it modulo 256 forces l_r — the threshold a cheating server would want to move — with no range assumption on any witness at all. Two witnesses that both satisfy the clause against the same committed mask therefore produce client outputs that differ by a constant, never by something that depends on the client's own secret byte. That is the property that matters: a server cannot make your output a function of your input.

4. Pinning a number is not pinning a message

Now the part that is easy to get wrong, and that the first version of this article got wrong.

The clause pins (h_r, l_r) — the numbers the table is supposed to be built from. It does not, by itself, pin the table. The table is a different message, and it arrives in round two: after you have already sent your oblivious-transfer choices, which is to say after you have already committed to which entry you want. Nothing in round one mentioned it.

So the attack from section 3 survives in a narrower form: prove honestly about (h_r, l_r), then serve a table built from something else. The proof is valid. The output is wrong. And this is not hypothetical — it was reproduced end to end at production parameters before it was closed.

Commit, then reveal. The fix is ordering. Those tables are fully determined in round one already — they depend only on the server's own mask and its own randomness, not on anything the client says — so there is no reason to wait until round two to be bound by them. The server now publishes a short fingerprint (a hash) of the tables in round one, inside the statement the proof is about, and the client refuses any round-two message whose tables do not hash to that fingerprint.

That is a commitment scheme doing exactly what commitments are for: forcing a choice to be made before the information that would make cheating profitable is available. The server must fix its tables before it learns which entry you will open. That kills the sharp version of the attack — picking the rounding threshold as a function of your secret byte, which could be binary-searched across sessions to extract it.

What is still open, and why it is hard. A server can still commit, in round one, blind, to a table built from a dishonest threshold. It gets one guess, with no feedback, and it must commit before knowing anything — but it can guess.

Why can't the client just check? Because you open exactly one entry out of 256, and you have nothing to compare it against. Verifying that entry directly would require knowing h_r and l_r — and those are precisely the one-time pad that hides the unrounded product from you. The thing you would need in order to check is the thing you are not allowed to learn. That is a real and slightly beautiful constraint, and it means the last line of defence cannot be verification.

It is detection instead, and that is the canary belt: hide questions you already know the answer to among the real ones, so a server that tampers cannot tell which sessions it is safe to tamper with.

5. Why this shape, and roads not taken

Why byte-split into 256·h + l? Because the constraint has to be linear over small values for the lattice proof to certify it cheaply, and a base-256 split keeps each piece a single byte (tiny, easy to range-check that it really is a byte) while their combination reconstructs the value exactly. We could have used a different radix or a bit-by-bit decomposition; bytes hit the sweet spot between the number of witness values (fewer than bits) and the size of each (small enough to bound tightly). The exact-integer discipline that makes "reconstructs exactly" true rather than approximately is the subject of The Proof Ring — the carry term is precisely what accounts for the ring's negacyclic wrap so the reconstruction is an honest integer identity, not a mod-Q accident.

Why not round with a fancier gadget? There are heavier ways to do secure rounding — comparison circuits in generic MPC, or "learning with rounding" tricks that avoid an explicit carry. Generic MPC comparison is far more expensive per coefficient than a 1-of-2 OT, and it would still need to be bound to the commitment somehow. The learning-with-rounding style would change the PRF's algebraic relation in ways that make the proof harder. As throughout this project, we picked the rounding method that kept the relation linear and provable, because the proof is the expensive part and everything upstream is chosen to make it cheap.

Why not put the table itself inside the proof? That is the obvious way to close section 4 completely, and the cost is the reason it is not done. The tables are masked with a hash before they are sent, so proving a statement about the transmitted bytes means proving a hash inside the proof — hundreds of millions of constraints per session, against the roughly ten thousand the rest of the relation costs. Extrapolating from the best measured proof systems puts it in the gigabytes and minutes per contact. Commitment plus detection is what you do when the direct check is real but unaffordable.

6. The full round-two picture

Putting rounding together with everything before it, the client's round two is:

It already verified the server's proof (fail-closed) at the end of round one — including the Route B clause tying the rounding parameters to the committed mask, and the fingerprint of the round-two tables.
It redeems 32 oblivious transfers (one per needed coefficient), using its decrypted low bits as choices, to obtain the correct rounded high bits — learning nothing else, revealing nothing about its shares.
It checks the tables it was actually served against the fingerprint from round one, and refuses them if they do not match.
It assembles the 32 rounded coefficients, hashes them with SHAKE-256, and outputs the 32-byte presence_id.

The server, across both rounds, provided an honest homomorphic evaluation and proved it, committed to its rounding tables before it could learn anything about the client's choices, and learned nothing — not the input, not the output, not the client's OT choices.

7. Summary

The OLE output is noisy; producing a clean PRF value means rounding an additively-shared quantity across a carry boundary, without the server learning the result and without the two parties disagreeing.
Oblivious transfer solves the disagreement and the secrecy: the server builds per-coefficient rounding tables, the client obliviously pulls the correct branch (32 small OTs, thanks to PRESENCE_TRUNC = 32).
Rounding introduces a new cheating surface beside the main proof, so the rounding parameters are bound into the proof via the Route B clause: a byte-split 256·h_r + l_r plus a fold-carry, tied by a linear constraint to the committed mask R.
Pinning the parameters is not the same as pinning the table, which is a separate, later message. So the server also commits to its tables in round one, before it can learn which entry the client will open — and the client refuses tables that miss the commitment.
The client opens one entry of 256 and cannot check it directly, because checking would require the very value the pad hides. The remaining gap is therefore closed by detection, not verification — see Known-Answer Testing.
Every design choice here — bytes, linear constraints, commit-then-reveal — follows the project's rule: keep the relation linear and provable, because the proof is where the cost and the security both live.

References

A. Banerjee, C. Peikert, A. Rosen, "Pseudorandom Functions and Lattices," EUROCRYPT 2012 — the "learning with rounding" view of a rounded inner product as a PRF, and the noise-vs-boundary tension.
Y. Ishai, J. Kilian, K. Nissim, E. Petrank, "Extending Oblivious Transfers Efficiently," CRYPTO 2003 — the OT machinery the rounding rides on.
Work on secure comparison / secret-shared truncation in MPC (e.g., Catrina–de Hoogh) — the heavier alternatives we did not use.
Wikipedia: Oblivious transfer, Secret sharing, Rounding.

Next: Algorithm: The NIZK — the proof that ties it all together.