"Reverse" Reed-Solomon error correction, given prefix of input

Question

I have a string $S$ of length (say) 34, that I know the first (say) 24 bytes of, but not the last 10. I also have the 10-byte error correcting code $RS_{44,34}(S)$ in full. Do I have any hope of recovering $S$?

The amount of information of $S$ that I'm missing far exceeds the theoretical guarantee of Reed-Solomon (which I think in this case is 3 bytes), but at the same time, there's $2^{80}$ possible values for the unknown portion of $S$, and also $2^{80}$ possible outputs for the error correction. If we were to iterate over all possible values for the unknown portion of $S$, I would naively expect approximately 1 of them to match the error correction. But $2^{80}$ is too much to brute force.

Are there any techniques that could recover (or at least reduce the state space for) an input, given its Reed-Solomon EC? Is there any reason to think one way or the other that RS is cryptographically secure in this sense?

For background, the "real world" application here is that I have a QR code (version 2, L-level EC) where I don't have the main data bits, but I do have the EC bits. I know that the data is a URL on a particular domain, thus the prefix.

Answer 1

Are there any techniques that could recover (or at least reduce the state space for) an input, given its Reed-Solomon EC?

You are in luck - Reed-Solomon is a linear code, that is, the error correcting section is a linear function of the input, and in fact, by fixing all but 10 bytes of the input, it is a bijection.

What this means is that you can efficiently reconstruct the missing 10 bytes of the input; Gaussian elimination would work, and while there are likely to be more efficient algorithms available, Gaussian elimination would take approximately $10^3$ operations, and so that could be efficient enough.

Answer 2

Not all codes have the nice property that RS codes have, which is that every $k$ symbols are an information set which can be used to reconstruct the original codeword.

There are efficient erasure decoders out there. Erasure means that some symbols are unknown, not just errored.

For example, this recent paper presents an efficient decoding algorithm for RS codes over the finite field with $q$ elements, $\mathbb{F}_q$ with $q=2^m,$ in $O(q \log_q q^2)$ time. It uses walsh transforms to do Lagrange interpolation.