IACR News item: 05 November 2025
Elizabeth Crites, Alistair Stewart
ePrint Report
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.
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.
Additional news items may be found on the IACR news page.