HomeTechnical ArchitecturePhilosophyContactRequest access
All articles

Contact Discovery

Algorithm: The Proof Ring

8 min read

A zero-knowledge proof 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 — and 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, the convolution relation from OLE from Ring-LWE, and the special-soundness argument from The NIZK.

1. The trap: proving arithmetic that wrapped around

The OLE evaluation happens modulo a BFV encryption modulus Q = 2⁴². So the true statement the server computed looks like:

reply_i  =  ( Σ_j M[i][j] · s_j  +  Δ · R_i )   mod Q

for each coefficient i, where the M[i][j] are the signed convolution coefficients from article 06. 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 mod Q = y mod Q" is a weaker statement than "x = y." Two genuinely different secrets can produce the same reply after the wrap, and a malicious server could exploit exactly that slack to equivocate — to later claim its committed key was a different s' that happens to agree mod Q. The commitment Com(s) was supposed to pin down one key; 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[i][j] · s_j  +  Δ · R_i  −  Q · k_i  =  reply_i      (over the integers, no mod)

Here k_i is a new witness value — the carry, literally how many times this coefficient wrapped around Q. Now the statement is a true equation in the integers. There is no slack to exploit: if the prover knows short s, R, and correct carries k making this hold exactly, it knows the one real key. The whole job of the proof ring is to make this exact identity representable — to give us a place to do integer arithmetic where nothing wraps unexpectedly.

2. How big do the numbers get?

To hold the exact identity we need a ring whose modulus is bigger than any value that appears, so that reducing modulo it is a no-op on the true values (they never wrap). Let's bound the biggest term.

  • The key s has N = 512 coefficients, each a small integer below 2¹⁶ (the BFV plaintext modulus bound).
  • The convolution coefficients M[i][j] come from the ciphertext, each below Q = 2⁴².
  • Each output term V_i = Σ_j M[i][j]·s_j sums up to 512 products of a < 2⁴² value and a < 2¹⁶ value: worst case around 2⁴² · 2¹⁶ · 2⁹ ≈ 2⁶⁷.

So the honest values live comfortably below about 2⁶⁷, and the carries satisfy |k| < 2²⁵. If our proof ring's modulus exceeds this, every real value is represented exactly, and the "mod" in the ring never touches an honest computation — it only ever fires on a cheating prover's oversized values, which is exactly when we want it to. This is why the ring's modulus is chosen to clear roughly 2⁶⁸: it is the smallest safe ceiling above the honest arithmetic.

3. The ring we chose, and the three ugly primes

The proof ring is

R  =  ℤ_P[X] / (X⁶⁴ + 1),      degree D = 64,
P  =  p₁ · p₂ · p₃  ≈  2⁹⁴·⁶,   three ~2³² primes.

Three design pressures fixed these specific numbers, and they pull against each other.

Why the modulus is a product of three ~2³² primes (≈ 2⁹⁴·⁶). We need P well above the 2⁶⁸ ceiling from §2 (with headroom to spare — the actual bound, once masks and Route B carries are included, sits higher). We also want arithmetic that runs fast on a 64-bit CPU. A single ~2⁹⁵ prime would force slow multi-word "bignum" multiplication for every coefficient. Instead we use 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 32-bit-ish operations (Residue Number System), and we reassemble the true value only when needed. Three primes near 2³² multiply to about 2⁹⁴·⁶ — enough ceiling, all machine-word arithmetic. The primes are the specific ugly numbers they are (e.g., 4294966769) because they must be the largest values below 2³² that also satisfy the next constraint.

Why degree 64 and this particular prime shape: invertible challenge differences. Recall the special-soundness argument from article 09: extracting the witness required dividing by the challenge difference c − c'. Division in a ring is only possible when c − c' is invertible. In a polynomial ring ℤ_P[X]/(Xᴰ+1), whether a short element is invertible depends on how the polynomial Xᴰ+1 factors modulo the primes. This is delicate:

  • If Xᴰ+1 splits completely (into D linear factors, which happens when p ≡ 1 mod 2D), multiplication is blazing fast (a Number-Theoretic Transform, the finite-field FFT) — but short challenge differences can become zero divisors, and then you cannot divide, and the clean exact extraction breaks. That reopens the equivocation door we just closed.
  • If Xᴰ+1 stays irreducible 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ᴰ+1 factor into a few pieces, not D of them), which keeps short challenge differences invertible so extraction is exact — no slack, 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 thus soundness per round) is big, small enough that a partial-split multiply is cheap. This "invertibility vs. 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, not a performance one.

4. A speed idea we investigated and rejected

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 thus soundness. With a fully-split ring, short challenge differences become zero divisors, so you can no longer divide z − z' by c − c' to recover the witness cleanly. The best you can do 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 this is disqualifying: the presence identifier is a rounded value, and 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 where every nonzero element is invertible even in a fully-split ring — and that path is real and we scoped it. But it adds machinery and its own care (the extraction step, not just the challenge, has to move into the extension), so we kept the exact, partial-split ring as the shipped choice: it is correct without asterisks. 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.

5. The carries, one more time

It is worth restating what the carry witness k_i 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 (< 2²⁵), so they fit the "short witness" discipline that binds to SIS, and their correctness is one more linear constraint the proof already knows how to handle. The rounding's Route B clause (article 08) uses the same idea — a fold-carry that accounts for the negacyclic wrap of the mask — which 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.

6. Summary

  • Proving a mod-Q relation is a trap: it is weaker than the true integer relation and leaves a cheating server room to equivocate on the committed key.
  • The fix is to prove the exact integer identity with an explicit carry witness k_i ("how many times this coefficient wrapped Q"), which removes the slack entirely.
  • Holding the exact identity needs a big enough modulus (honest values reach ~2⁶⁷), realized as a product of three ~2³² primes (≈ 2⁹⁴·⁶) via CRT/RNS so all arithmetic stays in machine words.
  • Degree 64 and a partial-split factorization keep short challenge differences invertible, so witness extraction (hence soundness) is exact — no slack.
  • We measured that fully-splitting primes multiply faster but break exact extraction, so we declined the speedup rather than accept a relaxed, potentially-forgeable proof.

References

  • V. Lyubashevsky, G. Seiler, "Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to Lattice-Based Zero-Knowledge Proofs," EUROCRYPT 2018 — the invertibility / splitting tradeoff at the center of this article.
  • T. Attema, R. Cramer, C. Xing, "A Note on Short Invertible Ring Elements and Applications to Cyclotomic and Trinomial Number Fields," 2019 — bounds on when short elements are invertible.
  • W. Beullens, G. Seiler, "LaBRADOR," CRYPTO 2023 — the exact-lift and short-witness discipline in context.
  • Wikipedia: Chinese remainder theorem, Residue number system, Cyclotomic polynomial, Number-theoretic transform.

Next: Algorithm: OLE Packed.