Paper 2026/2056

Reed-Solomon Codes Beyond Johnson: Efficient Decoding and Smaller Cryptographic Proofs

Quang Dao, Carnegie Mellon University
Scott Duke Kominers, Harvard University, a16z crypto
Justin Thaler, Georgetown University, a16z crypto
Abstract

List decoding Reed–Solomon codes is a central problem in coding theory and, together with mutual correlated agreement (MCA), underpins the soundness of many succinct cryptographic proofs. In this work, we give precise quantitative bounds on Reed–Solomon list decoding and MCA up to capacity, provide deterministic decoding algorithms that remain efficient over cryptographically large fields, and specialize our bounds to reduce proof sizes in implemented proof systems. Our bounds apply to arbitrary prescribed evaluation domains; beyond Johnson, they require sufficiently large field characteristic. Refining the hidden-derivative method of Brakensiek, Chen, Putterman, Zhang, and Zheng, we obtain an explicit agreement threshold $a_1(\rho)$ strictly below the Johnson bound $\sqrt{\rho}$, using only the first derivative, without requiring its evaluations in the received word. At agreement $a_1(\rho)+\eta_1$, where $\eta_1>0$, our sharper interpolation and candidate counts give list size $O_\rho(n/\eta_1^2)$ and MCA error $O_\rho(n^2/(q\eta_1^4))$ for codes of length $n$ over $\mathbb{F}_q$. Higher derivatives give explicit quantitative bounds up to capacity, uniformly over all rates, sharpening prior MCA results in Zheng's unpublished manuscript and Jeronimo's work, concurrent with ours. At fixed rate, for agreement gap $\eta_0>0$ above Johnson, we improve the MCA error bound of Ben-Sasson et al. (BCHKS) from $O_\rho(n/(q\eta_0^5))$ to $O_\rho(n/(q\eta_0^3))$, in every characteristic. Our decoders determine the values of the message and its derivatives at a point from the agreements with the received word, rather than enumerating them over the field as earlier hidden-derivative decoders do. With fast explicit field arithmetic, at fixed rate and a fixed positive gap above the respective threshold, deterministic decoding takes $\widetilde{O}(n\log q)$ bit operations above Johnson in every characteristic and $\widetilde{O}(n^3\log q)$ above our first-order curve in sufficiently large characteristic. Decoding remains polynomial in $n$ and $\log q$ at every fixed positive gap from capacity, under the same requirement of sufficiently large characteristic. Our first-derivative bounds give the first proof-size reductions in existing proof-system implementations from provable Reed–Solomon proximity-gap bounds beyond the Johnson radius. Relative to the deployed parameters and at unchanged security targets, we save 79.4 KB (11.1%) for ProveKit passport proofs, 13.2 KB (4.63%) for ZisK compressed final proofs, and 59.8 KB (4.85%) for LambdaVM CPU subproofs. We have formally verified the list-decoding and MCA bounds and concrete parameters in ArkLib, a Lean library for verified cryptographic proofs.

Note: This revision (2 Nov 2026) reorganizes and shortens the paper; the list-decoding and MCA bounds and the proof-size savings are unchanged. - The introduction and technical overview are rewritten, and the first-order results and applications now come before the capacity results. - The first-order decoder drops the common-center refinement, so it now runs in Õ(n^3 log q) rather than Õ(n^2 log q). - Several gaps in the proofs and hypotheses are filled, mostly in the decoder analysis. - The Lean statements now point to a newer ArkLib revision.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
reed-solomonlist-decodingproximity-gapcorrelated-agreementbeyond-johnsonsnarks
Contact author(s)
qvd @ andrew cmu edu
skominers @ hbs edu
justin r thaler @ gmail com
History
2026-11-03: last of 2 revisions
2026-09-16: received
See all versions
Short URL
https://ia.cr/2026/2056
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2056,
      author = {Quang Dao and Scott Duke Kominers and Justin Thaler},
      title = {Reed-Solomon Codes Beyond Johnson: Efficient Decoding and Smaller Cryptographic Proofs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2056},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2056}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.