On Proximity Gaps of Reed-Solomon Codes

This paper is about the proximity gaps phenomenon for Reed–Solomon codes. Very roughly, the proximity gaps phenomenon for a code C ⊆ Fqn says that for two vectors f,g ∈ Fqn, if sufficiently many linear combinations f + z · g (with z ∈ Fq) are close to C in Hamming distance, then so are both f and g, up to a proximity loss of ε*. 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 δ ∈ (0,1). (1) For proximity gaps up to the unique decoding radius δ/2, we show that arbitrarily small proximity loss ε* > 0 can be achieved with only Oε*(1) exceptional z’s (improving the previous bound of O(n) exceptions). (2) For proximity gaps up to the Johnson radius J(δ), we show that proximity loss ε* = 0 can be achieved with only O(n) exceptional z’s (improving the previous bound of O(n2) exceptions). This significantly reduces the soundness error in the aforementioned arguments systems. In the other direction, we show: (1) for some Reed–Solomon codes and some δ, proximity gaps at or beyond the Johnson radius J(δ) with arbitrarily small proximity loss ε* needs to have at least Ω(n1.99) exceptional z’s. (2) More generally, for all constants τ, we show that for some Reed–Solomon codes and some δ = δ(τ), proximity gaps at radius δ − Ωτ(1) with arbitrarily small proximity loss ε* needs to have nτ exceptional z’s. (3)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.