Algorithm: Rounding by Oblivious Transfer (Route B)

Lattice encryption (encryption built on noisy linear algebra, chosen because it resists quantum computers) is noisy on purpose. So the raw output of the oblivious inner product is a fuzzy field element (a number that lives modulo a fixed prime), not the crisp value a pseudorandom function needs. A pseudorandom function, or PRF, is a keyed function whose outputs look random to anyone who lacks the key. Turning that fuzz into a clean, agreed-upon, unforgeable answer (without the server learning it) is the last mile of the OPRF: an oblivious PRF, one the server evaluates for you without ever seeing your input. It is subtler than "just round." This article is that last mile.

Prerequisites: the noisy OLE output from OLE from Ring-LWE (OLE is oblivious linear evaluation, where the server applies its secret linear function to the client's encrypted input) and oblivious transfer from PQ Oblivious Transfer. Oblivious transfer, or OT, lets a receiver take exactly one item from a sender's list without the sender learning which one, and without the receiver seeing the rest.

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. Here ⟨a_x, s⟩ is the inner product of a vector derived from the client's input with the server's secret key s.

What a PRF wants is 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 holds a share of the true value too, via the random mask R it added in OLE from Ring-LWE. So 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 one way while the honest value goes the other. Alice and Bob would then disagree on presence_id for the same number, and discovery silently fails. The rounding has to be engineered so that 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 do the rounding and tell the client.
Neither party can cheat the rounding. A malicious server could bias the output by lying about its share; a malicious client could claim a rounding inconsistent with the committed values. The rounding has to be bound to what was actually committed, or it becomes a fresh hole right beside the place the proof thought 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: split into two pieces that look random on their own but add up to the real value. The client holds one share, which is what it decrypted; the server holds the other, which is the mask R it injected. Their sum is the true ⟨a_x, s⟩.

Rounding a sum that lives in two halves is the classic secure-computation task. Near a boundary it comes down to a single carry bit: do 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 Post-Quantum Oblivious Transfer, §5):

The server, acting as sender, builds a tiny table for each rounded coefficient. It enumerates 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. Each entry is masked so only the right one is usable.
The client, acting as receiver, uses its own low bits as the OT choice and obliviously pulls the one correct entry.

The server never learns which entry the client took (that is OT receiver privacy), so it never learns the rounded value. Problem 2, solved.

The table is constructed so the carry resolves correctly regardless of small noise. And because we round only PRESENCE_TRUNC = 32 coefficients, this is 32 small OTs rather than thousands. Problem 1, solved cheaply.

This is also why the OPRF is two rounds. Round one carries the OLE reply plus a commitment (a 32-byte hash) to the rounding tables. Round two delivers the tables themselves and the client redeems its transfers. That ordering is deliberate, and §4 is about why it has to be that way round.

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 (convincing the client the claim is true while revealing nothing else) that its reply used the committed key s.

But that proof certifies the linear evaluation (the inner product ⟨a_x, s⟩) and nothing else. If the rounding is a separate, unproven step layered on top, a malicious server gets a fresh place to cheat.

It can evaluate s honestly, passing the proof, and then hand the client rounding tables built from a different value, steering the output. The proof is perfectly valid; the output is still corrupted. Closing one hole opened another right next to it.

So the rounding has to be tied to the committed reply as well. The implementation calls this the Route B clause, and the trick is to express the rounding in a form the same linear proof machinery can already certify.

For each of the 32 rounded coefficients, take the server's folded mask value r_i (the mask R collapsed down onto the single coefficient this rounding step touches) and decompose it into a byte-split:

r_i = 256·h_r + l_r

Here h_r is the high byte and l_r the low byte, with a fold-carry term accounting for the negacyclic wrap of the mask: the sign flip a coefficient picks up when it wraps around the end of this kind of polynomial ring.

Those three values (high byte, low byte, carry) become additional witness values in the proof, more of the secret data the proof is about. They are tied to the committed mask R by a single linear constraint, meaning one equation the prover is forced to satisfy:

256·h_r + l_r + carry = fold(R)_i

That is exactly the shape the NIZK (the non-interactive zero-knowledge proof, a proof delivered as a single message with no back-and-forth) 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 rather than a whole second 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, stated in a proof assistant and verified step by step by the machine, rather than argued on paper.

The clause is an identity over the integers, and 256 divides the modulus the carry is measured in. Reduce the whole equation modulo 256 and the 256·h_r term drops away, which pins l_r (the threshold a cheating server would want to move) with no range assumption on any witness at all.

The consequence is the property that matters. Two witnesses that both satisfy the clause against the same committed mask produce client outputs differing by a constant, never by something that depends on the client's own secret byte. 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 and 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 §3 survives in a narrower form. Prove honestly about h_r and l_r, then serve a table built from something else. The proof is valid; the output is wrong.

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 of the tables (a hash) in round one, inside the statement the proof is about. The client then 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. Repeated across sessions, that adaptive choice could be binary-searched to extract the byte itself.

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 (the random mask whose entire job is to keep a value unreadable) hiding 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 a byte-split?

The constraint has to be linear over small values for the lattice proof to certify it cheaply. A base-256 split gives exactly that: each piece is a single byte (tiny, and easy to range-check as genuinely a byte) while the two together reconstruct 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 would give) and the size of each (small enough to bound tightly).

What makes "reconstructs exactly" true rather than approximately is the exact-integer discipline 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 rather than a mod-Q accident.

Why not round with a fancier gadget?

There are heavier ways to do secure rounding: comparison circuits in generic MPC (secure multi-party computation, the general-purpose machinery for computing any function on inputs neither party will reveal) or "learning with rounding" tricks that avoid an explicit carry.

Generic MPC comparison is far more expensive per coefficient than a small 1-of-256 OT, and it would still need binding 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 §4 completely, and cost is the only 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. That is 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 at the end of round one (fail-closed, meaning any failure aborts the session rather than continuing without the check). That proof included 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 and 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 (a standard cryptographic hash with flexible output length) and outputs the 32-byte presence_id.

Across both rounds, the server provided an honest homomorphic evaluation (computing on the encrypted data without ever decrypting it) and proved it, and committed to its rounding tables before it could learn anything about the client's choices. It learned nothing in return: 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 by the Route B clause: a byte-split 256·h_r + l_r plus a fold-carry, tied to the committed mask R by one linear constraint.
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.