A zero-knowledge proof (a proof that convinces a verifier a statement is true while revealing nothing else) is only as honest as the arithmetic it runs on. This article is about a subtle trap: proving a statement about numbers that have secretly "wrapped around" a modulus, the way 13 o'clock wraps around to 1 on a clock face. It is also about the specific ring of polynomials we chose so that the proof certifies a true integer identity rather than a convenient lie. It is the least glamorous and most load-bearing choice in the proof system.
Prerequisites: rings from Lattice Foundations (a ring is a number system where you can add, subtract and multiply, like the integers or polynomials), the convolution relation from OLE from Ring-LWE, and the special-soundness argument from The NIZK (the argument that a prover able to answer two different challenges must genuinely know the secret witness).
The OLE evaluation (the oblivious linear evaluation, where the server applies its secret linear function to the client's encrypted input) happens modulo a BFV encryption modulus Q = 242. (BFV is the homomorphic encryption scheme in use, named for its authors Brakerski, Fan and Vercauteren.) So for each coefficient i, the true statement the server computed looks like this:
reply_i = ( Σ_j M_ij·s_j + Δ·R_i ) mod Q
The Mij are the signed convolution coefficients from OLE from Ring-LWE. Ri is the random mask the server added there to keep the raw inner product hidden. And Δ is the fixed scaling factor that holds plaintext values clear of the encryption noise.
That little "mod Q" is a landmine. When a coefficient sum exceeds Q it wraps, and a proof about the wrapped value is a proof about a number that is not the real inner product.
Why does that let a cheater in?
Because "x and y agree mod Q" is a weaker statement than "x = y." Two genuinely different secrets can produce the same reply after the wrap, just as 1 o'clock and 13 o'clock land on the same spot on the clock.
A malicious server can exploit exactly that slack to equivocate: to claim later that its
committed key was a different s′ which happens to agree mod Q. The
commitment Com(s) was supposed to pin down one key, and a mod-Q
proof would let it wiggle.
This is not hypothetical. It is the precise hole that sinks naive lattice proofs of modular relations.
The fix is to prove the exact integer identity, with the wrap made explicit:
Σ_j M_ij·s_j + Δ·R_i - Q·k_i = reply_i
That equation holds over the integers, with no modulus anywhere. The new term ki is a fresh witness value (a witness being a secret value the prover claims to know) called the carry, and it is literally how many times this coefficient wrapped around Q.
Now there is no slack to exploit. If the prover knows a short s, a short R, and correct carries k making this hold exactly, it knows the one real key. (Short, throughout, just means the values are small.)
The whole job of the proof ring is to make that exact identity representable: to give us a place to do integer arithmetic where nothing wraps unexpectedly.
To hold the exact identity we need a ring whose modulus is bigger than any value that appears. Then reducing modulo it does nothing to the true values: they never wrap. Let's bound the biggest term.
V_i = Σ_j M_ij·s_j sums 512 products of a value under 242
and a value under 216. Worst case, that is around 242 · 216 · 29, or
about 267.So the honest values live comfortably below about 267, and the carries stay below 225 in absolute value.
If our proof ring's modulus exceeds that, every real value is represented exactly and the ring's own "mod" never touches an honest computation. It fires only on a cheating prover's oversized values, which is precisely when we want it to.
That is why the modulus is chosen to clear roughly 268: the smallest safe ceiling above the honest arithmetic.
The proof ring is
R = ℤ_P[X] / (X^64 + 1)
(polynomials with coefficients modulo P, where X64 counts as −1), with degree D = 64, and a modulus that is the product of three primes:
P = p_1·p_2·p_3 ≈ 2^94.6
Three design pressures fixed these specific numbers, and they pull against each other.
Why the modulus is a product of three primes near 232.
We need P well above the 268 ceiling from §2, with headroom to spare. (The actual bound sits higher once masks and Route B carries are included.)
We also want arithmetic that runs fast on a 64-bit CPU. A single prime near 295 would force slow multi-word "bignum" multiplication (software-simulated arithmetic on numbers too big for the processor's native registers) for every coefficient.
The way out is the Chinese Remainder Theorem (CRT). Represent each big number by its three residues modulo three primes that each fit in a machine word. Arithmetic becomes three independent lanes of fast machine-word operations (a residue number system), and we reassemble the true value only when we need it.
Three primes near 232 multiply to about 294.6: enough ceiling, and every operation stays in a machine word.
The primes are the specific ugly numbers they are (4294966769 is one) because they have to be the largest values below 232 that also satisfy the next constraint.
Why degree 64 and this particular prime shape. The answer is invertible challenge differences.
Recall the special-soundness argument from The NIZK: extracting the witness required dividing by the challenge difference c − c′. Division in a ring is only possible when that difference is invertible: when something you can multiply by to undo it actually exists.
In a polynomial ring ℤ_P[X]/(X^D+1), whether a short element is invertible depends on how the
polynomial X^D+1 factors modulo the primes. That turns out to be delicate.
X^D+1 splits completely (into D linear factors, which happens when
p ≡ 1 mod 2D), multiplication is blazing fast, via a Number-Theoretic Transform: the
finite-field cousin of the FFT, the classic algorithm that makes big multiplications cheap. But
short challenge differences can become zero divisors: nonzero elements
that multiply to give zero, and so have no inverse. Then you cannot divide, exact extraction
breaks, and the equivocation door we just closed swings open again.X^D+1 stays irreducible (it does not factor at all) or splits only a little, every nonzero short element is
invertible and extraction is exact. But multiplication is slower.We chose a partial split: the primes make X^D+1 factor into a few pieces rather than D of
them.
That keeps short challenge differences invertible, so extraction is exact (no slack, and the key is pinned to a single value) while still allowing reasonably fast multiplication.
Degree D = 64 is the sweet spot. Large enough that the challenge space, and so the soundness per round, is big; small enough that a partial-split multiply stays cheap.
This invertibility-versus-speed tension is a real published subtlety in lattice proofs. Lyubashevsky–Seiler and the Attema–Cramer–Xing line study exactly when short elements are invertible, and getting it wrong is a soundness bug rather than a performance one.
Because fully-splitting primes give the fastest multiplication (the NTT), it was tempting to switch to them. We measured it: at degree 64, a fully-split NTT multiply was meaningfully faster than the partial-split multiply. So why didn't we take the speed?
Because it would have broken exact extraction, and with it soundness.
In a fully-split ring, short challenge differences become zero divisors. You can no longer divide z − z′ by c − c′ to recover the witness cleanly. The best available is a relaxed extraction that recovers the witness up to a small slack factor, and a slack factor is exactly the equivocation wiggle-room from §1.
For contact discovery that is disqualifying. The presence identifier is a rounded value, so even
a tiny slack in the recovered witness could flip a rounded bit, letting a cheater produce a
subtly different presence_id while still passing the check.
A 1.8× faster multiply is worth nothing if it lets the server lie about the output.
There is a way to buy the speed back honestly: draw challenges from a larger extension field, a bigger number system built on top of the same primes much as the complex numbers are built on the reals, where every nonzero element is invertible even in a fully-split ring.
That path is further along than "surveyed." The extension arithmetic exists in-tree, with the load-bearing property that every challenge difference inverts. An exact zero-slack extraction from two extension challenges is demonstrated. The faster full-split multiply is built.
What remains is wiring the extension challenges into the fold itself: the extraction step, not just the challenge, has to move into the extension.
So the exact, partial-split ring is still the shipped choice, because it is correct without asterisks today rather than after one more integration. This is the recurring discipline of the whole series: we optimize aggressively, but never past the point where we can still prove the thing is sound.
It is worth restating what the carry witness ki does, because it is the conceptual key to the whole article.
Modular arithmetic forgets how many times a value wrapped. The proof cannot afford to forget, because that forgotten information is exactly the slack a cheater exploits.
So we promote the forgotten wrap-count to a first-class witness, and prove it is correct.
The carries are small (under 225), so they fit the short-witness discipline that binds to SIS, the short-integer-solution lattice problem the commitment's security rests on, and their correctness is one more linear constraint the proof already knows how to handle.
The rounding's Route B clause (Rounding by Oblivious Transfer) uses the same idea: a fold-carry accounting for the negacyclic wrap of the mask, the sign-flipping wrap-around this kind of polynomial ring produces. That is why the two articles rhyme.
The single sentence to remember: prove the exact integer identity, and make the modular wrap-around an explicit, provably-correct, short witness, never an implicit gap.
Next: Algorithm: OLE Packed.