Paper 2025/2055

On Proximity Gaps for Reed–Solomon Codes

Abstract

This paper is about the proximity gaps phenomenon for Reed-Solomon codes. Very roughly, the proximity gaps phenomenon for a code $\mathcal C \subseteq \mathbb F_q^n$ says that for two vectors $f,g \in \mathbb F_q^n$, if sufficiently many linear combinations $f + z \cdot g$ (with $z \in \mathbb F_q$) are close to $\mathcal C$ in Hamming distance, then so are both $f$ and $g$, up to a proximity loss of $\varepsilon^*$. Determining the optimal quantitative form of proximity gaps for Reed--Solomon codes has recently become of great interest because of applications to interactive proofs and cryptography, and in particular, to scalable transparent arguments of knowledge (STARKs) and other modern hash based argument systems used on blockchains today. Our main results show improved positive and negative results for proximity gaps for Reed-Solomon codes of constant relative distance $\delta \in (0,1)$. 1. For proximity gaps up to the unique decoding radius $\delta/2$, we show that arbitrarily small proximity loss $\varepsilon^* > 0$ can be achieved with only $O_{\varepsilon^*}(1)$ exceptional $z$'s (improving the previous bound of $O(n)$ exceptions). 2. For proximity gaps up to the Johnson radius $J(\delta)$, we show that proximity loss $\varepsilon^* = 0$ can be achieved with only $O(n)$ exceptional $z$'s (improving the previous bound of $O(n^2)$ exceptions). This significantly reduces the soundness error in the aforementioned arguments systems. 3. In the other direction, we show that for some Reed--Solomon codes and some $\delta$, proximity gaps at or beyond the Johnson radius $J(\delta)$ with arbitrarily small proximity loss $\varepsilon^*$ needs to have at least $\Omega(n^{1.99})$ exceptional $z$'s. 4. More generally, for all constants $\tau$, we show that for some Reed-Solomon codes and some $\delta = \delta(\tau)$, proximity gaps at radius $\delta - \Omega_{\tau}(1)$ with arbitrarily small proximity loss $\varepsilon^*$ needs to have $n^{\tau}$ exceptional $z$'s. 5. Finally, for all Reed-Solomon codes, we show that improved proximity gaps imply improved bounds for their list-decodability. This shows that improved bounds on the list-decoding radius of Reed-Solomon codes is a prerequisite for any new proximity gaps results beyond the Johnson radius.