A linear proximity gap over Galois rings.

Research note. Every number below is an upper bound on one named event, proved from a finite-field theorem by a $2$-adic descent. None is a matching attack, a measured floor, or the security level of a protocol. The panels build intuition; the manuscript carries the proofs.¹

Summary

Things being what they are, the processors of the world count modulo $2^k$. Proof systems that want to speak that arithmetic natively lift it into a Galois ring $R=\mathrm{GR}(2^k,m)$: a finite local ring with residue field $\mathbb F_{2^m}$, containing $\mathbb Z_{2^k}$ when $m=1$ and the binary field when $k=1$. The Reed–Solomon pipeline that fields enjoy carries over almost intact.² Almost. One number resists: how many bad challenges a batched proximity test can tolerate before it stops binding.

Over a field that number is linear in the block length. Over the ring, the published analysis said quadratic. The difference is not a constant; it is a power of $\ell$.

This note proves the linear threshold over the ring, at every radius below unique decoding, with no factor of $k$ and no extra term in $s\delta\ell$. At the ring parameters used in the Ring0 stack, $(s,\ell,m)=(64,2^{21},155)$, the quadratic expression yields $2^{-107}$, the curve bound proved here yields $2^{-128}$, and an affine variant yields $2^{-134}$. Twenty-one bits, then six more.

Interactive · Bad-challenge probability

Three bounds, one geometry.

Upper bounds on the probability that a fresh uniform Teichmüller challenge is bad when the words lack common agreement. Defaults are the parameters used in the manuscript.

Batch width s

64

Block length ℓ

2^21

Residue field size m

𝔽₂^155

• Published bounds·ℓ² / 2ᵐ
  2^-107
• This work, curves·ℓ / 2ᵐ
  2^-128
• This work, affineℓ / 2ᵐ
  2^-134

Curve gains 21 bits over the published expression; affine gains a further 6. Bars are proportional to the security exponent, longer is smaller probability.

1. What a proximity gap promises

Fix $s+1$ words $g_0,\dots,g_s\in R^E$ over an evaluation domain $E$ of size $\ell$. Batch them into one curve, driven by one random challenge:

$$w(\alpha)=\sum_{j=0}^{s}\alpha^{j}g_j .$$

Ask whether $w(\alpha)$ lies within $\delta\ell$ of the Reed–Solomon code $\mathrm{RS}[R,E,\rho]$, the evaluations of polynomials of degree below $\rho\ell$. A proximity gap with correlated agreement answers with a threshold $L$: if more than $L$ challenges pass, then every component agrees with a codeword, and they all agree on the same coordinate set, of size at least $(1-\delta)\ell$. Not each on its own set. One set.

The threshold is the entire economy of the test. A fresh uniform challenge from a set of size $q$ is bad with probability at most $L/q$, and a folding protocol pays that price every round. Halve $L$ and you gain a bit. Divide it by $\ell$ and you gain twenty.

Setting	Object	Challenge set	Radius	Threshold $L$
Finite field (BCIKS)3	curve $\sum\alpha^j g_j$	$\mathbb F_q$	unique decoding	$s\ell$
Galois ring (Wu et al.)4	line $g_0+\alpha g_1$	full ring	Johnson	$O(1)$ in $\ell$; vacuous on $\mathcal T$
Galois ring (JLXYY, CRYPTO 2025)5	curve $\sum\alpha^j g_j$	$\mathcal T$	unique decoding	$s\ell^2$
This work	curve $\sum\alpha^j g_j$	$\mathcal T$	unique decoding	$s\ell$
This work, affine	$g_0+\sum z_j g_j$	$\mathcal T^s$	unique decoding	$\ell q^{s-1}$

Here $\mathcal T\subset R$ is the Teichmüller set, the $2^m$ roots of $X^{2^m}-X$ in $R$. Reduction modulo $2$ maps it onto $\mathbb F_{2^m}$ one to one, and any two of its elements differ by a unit.⁶ Challenges are drawn from $\mathcal T$. The evaluation domain needs only the second property.

The field had its linear gap. The ring was owed one.

2. Why rings are harder than fields

In a field, every nonzero element divides. Cancel a common factor and nothing is lost. In $\mathrm{GR}(2^k,m)$ with $k\ge2$, the element $2$ is nilpotent, a zero-divisor, and cancelling it is not a step at all. It is a mistake.

The smallest ring already shows it. In $\mathbb Z/4\mathbb Z$, $2\cdot1=2\cdot3$, and $1\ne3$. What survives is weaker, narrower, and exact: multiplication by $2$ is injective as a map between consecutive quotient rings,

$$R/2^{k-t-1}R\;\hookrightarrow\;R/2^{k-t}R ,$$

because the annihilator of $2^t$ is precisely $2^{k-t}R$. So $2a=2b$ in $R/2^kR$ says nothing about $a=b$. It says $a\equiv b$ one ring lower. The descent below performs no other division.

Interactive · Why you cannot cancel 2

Multiplication by 2 in ℤ/8ℤ

Pick a and see every b with 2b = 2a. Cancelling 2 in the ring is illegal; reading the result one ring lower is exact.

Ring length k

ℤ/8ℤ

Element a

1

1. 02·0 = 0
2. 12·1 = 2
3. 22·2 = 4
4. 32·3 = 6
5. 42·4 = 0
6. 52·5 = 2
7. 62·6 = 4
8. 72·7 = 6

Solutions of 2b = 2a

1, 5 — 2 elements, so 2a = 2b does not give a = b.

Read one ring lower

Both solutions equal 1 in ℤ/4ℤ. Multiplication by 2 is injective as a map ℤ/4ℤ ↪ ℤ/8ℤ; that is the only division the descent performs.

The prior ring proof took the field toolkit, Berlekamp–Welch decoding and the Polishchuk–Spielman lemma, and generalised it to the ring. Its displayed sufficient condition has the shape

$$\frac{e+\rho\ell-1}{\ell-e}+\frac{s(e+1)}{|S|-se}<1 ,$$

with $e=\lfloor\delta\ell\rfloor$. At the unique-decoding boundary the first term is $1-\Theta(1/\ell)$. The slack is of order $1/\ell$; to fit inside it, the second term needs a challenge count of order $s\ell^2$. That is where the square enters. It is a property of that inequality, not a floor on the error, and the argument below does not depend on repairing it.⁵

Where the field cancels, the ring divides once, and only downward.

3. The $2$-adic descent

The method is one refusal: do no ring algebra where field algebra suffices. Reduce modulo $2$. Apply the field theorem. Lift the answer, subtract it, divide the residual by $2$. What remains is the same problem, one ring shorter. Repeat $k$ times.

At layer $l$ the words $g_j^{(l)}$ live over $R_{k-l}=R/2^{k-l}R$ on a domain $A_{l-1}\subseteq E$.

1. Project. Reduce modulo $2$. Every good ring challenge becomes a good field challenge, and distinct Teichmüller challenges stay distinct.
2. Agree. The field theorem returns codewords $\bar C_j^{(l)}$ and a common discrepancy support $W_l$: the coordinates where some $\bar g_j^{(l)}$ still disagrees.
3. Lift. Choose any lift of the $<\rho\ell$ coefficients of $\bar C_j^{(l)}$ to $R_{k-l}$, fixed before any challenge is examined.
4. Carry. Off $W_l$, the difference $g_j^{(l)}-C_j^{(l)}$ is divisible by $2$. Divide it. The quotient $g_j^{(l+1)}$ is a word over $R_{k-l-1}$ on $A_l=A_{l-1}\setminus W_l$.

At the last layer the ring is already the field. Find its agreement set and stop. Unrolling the digit relation $g_j^{(l)}=C_j^{(l)}+2g_j^{(l+1)}$ across every layer reconstitutes one ring codeword,

$$C_j=\sum_{l=0}^{k-1}2^{l}C_j^{(l)} ,$$

which agrees with $g_j$ on the final domain. The lifts are not unique. The codeword is: any two candidates lie within $e$ of $g_j$, agree on more than $\rho\ell$ exceptional points, and therefore coincide.

One fact holds the carry together. The residual $c_\alpha^{(l)}-\sum_j\alpha^jC_j^{(l)}$, between the decoded codeword and the lifted combination, must itself be divisible by $2$ as a polynomial. It is, because both terms reduce to field codewords of degree below $\rho\ell$ within $e_l$ of the same word, and at unique decoding the list has one entry. The proof uses that reduction is a ring homomorphism, and nothing else.

Reduce, agree, lift, carry. Then again, one ring down.

4. Where the factor $k$ would have come from

Done carelessly, the descent costs a factor of $k$ and a third of the radius. Let each layer spend the full budget $e=\lfloor\delta\ell\rfloor$ on new discrepancies. The punctured domain at layer $l$ has length $\ell-b_l$, and the instance must still sit inside unique decoding of the punctured code. That demands $2e+b_l\le(1-\rho)\ell$, and as $b_l$ climbs toward $e$ it forces $\delta\le(1-\rho)/3$. The radius is gone before the last layer.

Three lemmas prevent it.

Budget reduction. Count only the new discrepancies $W_l$ carved at layer $l$, and lower the budget by exactly that: $e_{l+1}=e_l-|W_l|$. The radius condition becomes $2e<(1-\rho)\ell+b_l$. It holds at layer zero, and it gains slack at every layer after. The full radius $(1-\rho)/2$ survives to the end.

Cancellation challenges. A challenge can cancel at a discrepancy $x\in W_l$: the curve's component errors may sum to zero there and hide it. For fixed $x$, that condition is a nonzero polynomial of degree at most $s$ over $\mathbb F_{2^m}$. At most $s$ roots per point; at most $s|W_l|$ challenges per layer. Discard them.

A threshold that shrinks with the domain. The field theorem on a domain of length $\ell-b_l$ asks for more than $s(\ell-b_l)$ challenges. Start above $s\ell$, discard at most $sb_l$, and precisely that many remain. Each carved coordinate lowers the demand by the same amount the cancellations cost.

Both totals telescope, and neither carries $k$:

$$\sum_{l=0}^{k-1}|W_l|\le\delta\ell, \qquad \sum_{l=0}^{k-1}s|W_l|\le s\delta\ell .$$

Interactive · Layer accounting

Walk the descent, layer by layer.

Batch width fixed at s = 4. Each layer carves a random slice of the total budget e = ⌊δℓ⌋. Toggle the accounting to see why the naive version loses the radius.

Ring length k

GR(2^4, m)

Block length ℓ

2^8

Rate ρ

0.50

Radius δ

0.220 < 0.250

Tight: eₗ = e − bₗNaive: eₗ = e every layerReshuffle carve

1. Layer 0 · R/2^4inside unique decoding

   Domain ℓ−bₗ

   256

   Budget eₗ

   56

   Carved |Wₗ|

   22

   Field threshold

   1024

   Challenges left

   1025

   Discarded ≤ s|Wₗ|

   88

2. Layer 1 · R/2^3inside unique decoding

   Domain ℓ−bₗ

   234

   Budget eₗ

   34

   Carved |Wₗ|

   15

   Field threshold

   936

   Challenges left

   937

   Discarded ≤ s|Wₗ|

   60

3. Layer 2 · R/2^2inside unique decoding

   Domain ℓ−bₗ

   219

   Budget eₗ

   19

   Carved |Wₗ|

   15

   Field threshold

   876

   Challenges left

   877

   Discarded ≤ s|Wₗ|

   60

4. Layer 3 · 𝔽inside unique decoding

   Domain ℓ−bₗ

   204

   Budget eₗ

   4

   Carved |Wₗ|

   4

   Field threshold

   816

   Challenges left

   817

   Discarded ≤ s|Wₗ|

   0

Telescoped totals

Σ|Wₗ| = 56 ≤ e = 56; discarded challenges Σ s|Wₗ| = 208 ≤ s·e = 224. Neither carries a factor of k.

Final agreement set

|A| = 200 ≥ ℓ − e = 200. Challenges stay above the shrinking field threshold at every layer because s·ℓ − s·bₗ = s(ℓ − bₗ).

Radius

Tight accounting needs 2e < (1−ρ)ℓ + bₗ, which only gains slack as bₗ grows. Every layer stays at the full radius (1−ρ)/2 = 0.250.

The layers do not each pay. They share one budget, and the budget is $\delta\ell$.

5. Removing the factor $s$

The curve threshold carries $s$ because a single challenge must absorb the whole batch. Combine the same words as an affine space instead, with $s$ independent challenges $z\in\mathcal T^s$:

$$w(z)=g_0+\sum_{j=1}^{s}z_j\,g_j .$$

Now the cancellation condition at a point is an affine equation in $\bar z\in\mathbb F^s$, a hyperplane, with exactly $q^{s-1}$ solutions. The other two lemmas never inspect the coefficients, so the descent runs unchanged. The threshold is $\ell q^{s-1}$ out of $q^s$ vectors, and the bad-challenge probability is $\ell/2^m$: independent of the batch width.

The price is $s$ draws instead of one. Whether the transcript can afford them is the protocol's question. The bound does not answer it.

6. What the bound does and does not cover

Uniform residue suffices. The count sees only residues. Any challenge whose reduction modulo $2$ is uniform in $\mathbb F_{2^m}$ receives the same bound, full-ring draws included; the higher digits may be distributed however one likes. The words must be fixed before the challenge is drawn.

Weights carry through. A weighted form tracks rational coordinate weights of denominator $M$ through the same descent. Composing $r$ layers with weights $M_i=2^i$ on lengths $\ell/2^i$ costs a factor $r$ in the summed bound. A maximum of local transition bounds and a sum of failure probabilities are two different numbers, and a compiler must say which one it needs.

A protocol still owes its own reductions. The theorem bounds one event for fixed component words. A folding protocol must separately prove that a far parent yields components without common agreement for the child code and radius, that its fold identity holds, and that its terminal test, its authentication, and its extractor behave. Only then does the per-round count

$$\Pr\bigl[\Delta(\mathrm{Fold}_\alpha f,C_{i+1})\le\delta\ell_{i+1}\bigr]\le\frac{s\,\ell_{i+1}}{2^m}$$

follow, with $\ell_{i+1}/2^m$ for the affine adapter.

Past unique decoding is open. Extending common agreement beyond $(1-\rho)/2$ over Galois rings needs a different argument. This descent does not supply it.

A bound is a promise about one event. The protocol must keep the rest.

What was proved

A linear threshold $s\ell$ for the batched curve over $\mathrm{GR}(2^k,m)$, at every $\delta<(1-\rho)/2$, independent of $k$, with proximity loss zero. An affine variant with threshold $\ell q^{s-1}$, which removes the batch width from the probability. Weighted and uniform-residue forms of both. The only external input is the finite-field theorem; the only divisions are by units, or through the injection between consecutive quotient rings.

At unique decoding the ring costs nothing. The accounting was the whole difficulty.

References

Footnotes

1. Luis Ángel González. A Linear Proximity Gap for Batched Reed–Solomon Codes over Galois Rings. Zenodo, 23 June 2026. Local copy: PDF. Full statements, proofs, the weighted section, and deferred lemmas. ↩

2. H. Zeilberger, B. Chen, B. Fisch. BaseFold: efficient field-agnostic polynomial commitment schemes from foldable codes. CRYPTO 2024. ↩

3. E. Ben-Sasson, D. Carmon, Y. Ishai, S. Kopparty, S. Saraf. Proximity gaps for Reed–Solomon codes. J. ACM 70(5), 2023. The finite-field base case, Theorems 1.5, 1.6 and 6.1. ↩

4. Z. Wu, X. Zhang, Y. Deng, Y. Wei, Z. Zhang, L. Yang. Polylogarithmic polynomial commitment scheme over Galois rings. 2025. A single-line gap with full-ring challenges at the Johnson radius. ↩

5. Y. Jia, S. Li, C. Xing, Y. Yao, C. Yuan. Polynomial commitments for Galois rings and applications to SNARKs over $\mathbb Z_{2^k}$. CRYPTO 2025. The quadratic threshold sharpened here. ↩ ↩²

6. Z.-X. Wan. Lectures on Finite Fields and Galois Rings. World Scientific, 2003. Teichmüller sets and the chain-ring structure. ↩