Improved LCL equivalence gives exponentially smaller alphabets for curve decoding
The claim
The authors assert that their new LCL equivalence reduces alphabet-size requirements exponentially while preserving the best known (a,b) parameters
Published as: “Improved LCL Equivalences and Curve Decoding Alphabet Sizes”
So what
These tighter alphabet-size guarantees make curve decoding-and thus proximity gaps, correlated agreement, and mutual correlated agreement-practically achievable for cryptographic protocols using Reed-Solomon or related codes.
The five-minute version
The paper shows that random Reed-Solomon codes (RRS) share the same LCL threshold as random linear codes, and that this equivalence can be extended to every known subspace-design code construction, yielding exponentially smaller alphabet size requirements for curve decoding. Using the improved non-containment bound for RRS (Theorem 1.2) and a black-box conversion from low-rate non-containment to high-rate containment for nested codes, the authors obtain curve-decoding guarantees with field size q ≥ n·exp(O(l/η2 + l·log(l+1)/η)) for RRS and q ≥ exp(O(log(1/η)+l)/η) for random linear codes. The evidence is theoretical, based on asymptotic analysis of random code ensembles, and matches the best known alphabet-size dependence for list decoding when the curve degree l is constant. The results are conditioned on sufficiently large block length n and constant-rate regimes.
What they found 2
- Random Reed-Solomon codes are (l,δ,a,b)-curve-decodable with field size q ≥ n·exp(O(l/η2 + l·log(l+1)/η)).
“q ≥n exp O l η2 + llog(l+ 1) η .”
- Improved non-containment bound for RRS: P(C contains F) ≤ |F|^r (2e r k / (η(q-n)))^{η n/2}.
“P(C contains F) ≤|F| r 2erk η(q -n) ηn/2 .”
What undercuts it the paper’s own results
- The containment direction (2) in Theorem 1.2 gives the same quantitative result as in [LMS25] and does not improve over prior work.
Stated limits 3
- for all sufficiently large n
- The formal statements use R ≤1-δ-2η.
- The containment direction (2) in Theorem 1.2 gives the same quantitative result as in [LMS25].
What’s new here 4
- Improved quantitative non-containment probability for random Reed-Solomon codes (exponential in ηn rather than ηn/r).
- A generic black-box reduction that turns low-rate non-containment into high-rate containment for any nested subspace-design code family.
- Compressed counting of curve-decoding failure profiles, leading to tighter union bounds.
- Resulting alphabet-size bounds for curve decoding that improve over prior work for both large and constant curve degrees.
Artifacts & methods 5
- Improved low-rate analysis for random Reed-Solomon codes
- Black-box conversion from non-containment to containment for nested codes
- Compressed profile counting for curve decoding
- Random Reed-Solomon codessystem
- Subspace-design codes (including folded Reed-Solomon)system