Paper 2026/782

Failure of proximity gaps close to capacity

Stepan Kazanin, Stanford University

Ulrich Haböck, StarkWare Industries LTD

Abstract

We give a simple counterexample which shows that, for Reed--Solomon codes over multiplicative subgroups of prime fields, proximity gaps do not hold near capacity, at least not as conjectured by Ben-Sasson, et al., in BCIKS20. For relative distance $\theta = 1-\rho-\eta$, where $\rho$ is the rate of the code, and positive $\eta = \Theta_\rho(1/\log n)$, where $n$ is the length of the code, we construct an affine line that is not entirely $\theta$-close to the code but still contains $2^{\Omega_\rho(1/\eta)}$ such points. The same construction gives a slightly stronger list-decoding lower bound. The proof uses a new additive-combinatorics lemma on sums of roots of unity.

Note: added acknowledgments

@misc{cryptoeprint:2026/782,
      author = {Dmitry Krachun and Stepan Kazanin and Ulrich Haböck},
      title = {Failure of proximity gaps close to capacity},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/782},
      year = {2026},
      url = {https://eprint.iacr.org/2026/782}
}