Given a garbled message with a few errors, find the errors, when the code has no visible structure to help you. Very hard, even for quantum computers.
The idea: Error-correcting codes add redundancy so that a few flipped bits can be fixed. For a random code with no structure, fixing those errors is extremely hard: you'd essentially have to guess which bits are wrong, and the number of possibilities explodes. Code-based encryption uses exactly that: add errors on purpose to hide the message, and make sure only the recipient has a code they can decode quickly.
Why it matters: The basis of code-based quantum-safe encryption.
On the map: decode a random linear code best attack: information-set decoding
Decode a random linear error-correcting code: given a noisy codeword, find the small error pattern. The general problem is NP-hard[1], it has been studied since McEliece's 1978 scheme[2], the best attacks (information-set decoding)[3] take exponential time, and quantum computers only give a modest speedup.
It is the basis of code-based cryptography such as Classic McEliece and HQC (KE).
If any of these breaks, this breaks too.
If this breaks, these break with it.