Welcome to the resource topic for 2025/2046
Title:
On Reed–Solomon Proximity Gaps Conjectures
Authors: Elizabeth Crites, Alistair Stewart
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:
- The correlated agreement up-to-capacity conjecture of Ben-Sasson-Carmon-Ishai-Kopparty-Saraf (J. ACM’23),
- The mutual correlated agreement up-to-capacity conjecture of WHIR,
- 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.
ePrint: https://eprint.iacr.org/2025/2046
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .