Summary
This paper shows that a certain kind of error correction problem called bounded-distance decoding for Reed-Solomon codes is computationally very hard (NP-complete) when trying to correct a specific number of errors. The authors prove this hardness for decoding just below the limit where these codes can no longer guarantee correction, clarifying the complexity with a stronger gap than previous work. Their proof involves advanced math related to fields, subsets, and polynomial identities, making the problem as difficult as other known challenging problems. This means that finding efficient algorithms for this decoding task in many cases is unlikely.
What this means in practice
- •For coding theory engineers: Avoid assuming efficient polynomial-time algorithms exist for bounded-distance decoding of Reed-Solomon codes near the covering radius.
- •For cryptographers: Use the NP-completeness of this decoding problem to design or analyze cryptographic schemes based on the hardness of decoding Reed-Solomon codes.
A theory result. No direct application yet.
Abstract
For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding radius is $d$ below the covering radius for every $1\le d\le c\log n/\log\log n$, where $c>0$ is an absolute constant. We prove that, for every fixed rational $0<α<1/2$, bounded-distance decoding is NP-complete under deterministic polynomial-time many-one reductions over explicitly represented finite extension fields for the additive gap $d=\lfloor n^α\rfloor$ below the covering radius. The hard codes have odd block length~$n$, dimension $K=(n+1)/2-d$, decoding radius $(n-1)/2$, and rate tending to $1/2$. The alphabet size is subexponential in the evaluation set size: for a fixed $0<η<1$ depending only on $α$, it is $2^{Θ(n^η\log n)}=2^{o(n)}$. The proof passes through moments subset sum on $n-1$ nonzero field elements, with required subset size $(n-1)/2$ and $d$ prescribed moments. The arithmetic ingredient is a uniform positive-completion theorem over prime fields $\mathbb{F}_q$ with $q\ge d^{2+ρ}$, for any fixed $ρ>0$. A sharper form follows from a higher-dimensional point-count estimate based on Deligne's theorem; the weaker form used in our reduction is proved more elementarily using additive-character orthogonality, the one-variable Weil bound, a moment identity of order $2d$, and Newton identities. A universal completion pool, an extension-field quotient construction, and a deterministic linear-size simultaneous power condenser complete the reduction.