A Syndrome--Space Approach to Proximity Gaps and Correlated Agreement for Random Linear Codes and Random Reed--Solomon Codes

Abstract

Proximity gaps and correlated agreement have become central tools in the analysis of interactive oracle proofs of proximity (IOPPs) and code-based SNARKs. Informally, a proximity-gap statement says that for a structured set of words -- such as an affine space, or a curve -- either all points are close to the code, or most are far from it. Such statements are essential in sampling-based proof systems, where a verifier queries only a few random locations on a structured object but must still obtain a global soundness guarantee. In Reed--Solomon-based proof systems, one would ideally like the proximity parameter to approach the information-theoretic limit $1-R$, since this is the largest possible radius for a rate-$R$ code and directly affects protocol efficiency. We establish a direct approach to proximity gaps and correlated agreement for random linear codes in the random parity-check-matrix model, without relying on list decoding of the proof. Our approach is based on a syndrome-space reformulation together with a witness-based reduction argument. It is conceptually different from the existing decoding-driven route for random linear codes, and it also leads to sharper parameters, including the optimal-up-to-$\epsilon$ large-alphabet radius bound $\rho <1-R-\epsilon$ for $q=\Theta (n)$, as well as near-capacity bounds over constant alphabets with improved alphabet-size requirements. We apply the same syndrome-space reductions to random Reed--Solomon codes. This yields correlated agreement for random Reed--Solomon codes over affine spaces and polynomial curves up to radius $\rho \le 1-R-\epsilon$, with field size $q\ge n\cdot 2^{O({\epsilon }^{-3})}$ for affine spaces and $q\ge n\cdot 2^{O_{\ell }({\epsilon }^{-3})}$ for degree-$\ell$ curves.

45 pages