cronokirby

(2026-05) Interleaving Stability for Mutual Correlated Agreement and Curve Decodability

2026-05-06

Abstract

We prove that row-wise interleaving does not impose a linear loss on two coding-theoretic soundness properties used in recent IOP/SNARK analyses: generator mutual correlated agreement and curve decodability.

For generator-MCA, let G:Ω→FqℓG:\Omega\to\mathbb{F}_q^\ell be a coefficient generator over a finite seed set and let CC be an Fq\mathbb{F}_q-additive code. For every interleaving width ss and distance parameter δ\delta, we show

εG(C,δ)≤εG(C≡s,δ)≤(1+1q+⋯+1qs−1)εG(C,δ). \varepsilon_G(C,\delta) \le \varepsilon_G(C^{\equiv s},\delta) \le \left(1+\frac1q+\cdots+\frac1{q^{s-1}}\right)\varepsilon_G(C,\delta).

Moreover, if ∣Ω∣≤q|\Omega|\le q, then the transfer is exact:

εG(C≡s,δ)=εG(C,δ). \varepsilon_G(C^{\equiv s},\delta)=\varepsilon_G(C,\delta).

In particular, affine-line MCA is invariant under row-wise interleaving. This answers the known interleaving-loss question and removes the linear interleaving factor from the affine-line MCA bound. It also implies that polynomial-generator MCA bounds transfer to interleaved codes without an additional interleaving-width factor.

We further establish interleaving stability for curve decodability. We introduce a marked formulation, prove its equivalence to the standard definition for Fq\mathbb{F}_q-additive codes and 1≤b≤a≤q1\le b\le a\le q, and use it to transfer curve decodability to row-wise interleavings. If CC is (ℓ,δ,a,b)(\ell,\delta,a,b)-curve-decodable and (ab)≤q\binom{a}{b}\le q, then C≡sC^{\equiv s} is also (ℓ,δ,a,b)(\ell,\delta,a,b)-curve-decodable for every ss. We also give a field-size-weighted variant that transfers larger base-code witness parameters to smaller interleaved-code witness parameters.