Paper 2025/2046

On Reed–Solomon Proximity Gaps Conjectures

Alistair Stewart, Web3 Foundation

Abstract

We disprove a range of conjectures for Reed-Solomon codes underpinning the security and efficiency of many modern proof systems, including SNARKs based on FRI (Ben-Sasson-Bentov-Horesh-Riabzev, ICALP’18), DEEP-FRI (Ben-Sasson-Goldberg-Kopparty-Saraf, ITCS’20), STIR (Arnon-Chiesa-Fenzi-Yogev, CRYPTO’24), and WHIR (Arnon-Chiesa-Fenzi-Yogev, preprint). Concretely, we prove that the following conjectures are false: 1. The correlated agreement up-to-capacity conjecture of Ben-Sasson-Carmon-Ishai-Kopparty-Saraf (J. ACM’23), 2. The mutual correlated agreement up-to-capacity conjecture of WHIR, 3. The list-decodability up-to-capacity conjecture of DEEP-FRI, which follows from existing results in the literature. We then propose minimal modifications to these conjectures up to the list-decoding capacity bound. Our second main contribution is a proof that correlated agreement with small enough error probability implies list decoding of Reed-Solomon codes. Thus, any future results on our correlated agreement conjectures with small enough error probability would imply similar results in classical list decoding. A reduction from proximity gaps to list-decodability was heretofore a natural open problem.

BibTeX

@misc{cryptoeprint:2025/2046,
author = {Elizabeth Crites and Alistair Stewart},
title = {On Reed–Solomon Proximity Gaps Conjectures},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/2046},
year = {2025},
url = {https://eprint.iacr.org/2025/2046}
}