correct me if I am wrong as I havent spent much time looking into it, but the security analysis essentially says "we assume the Goppa code is indistinguishable from a random code so the best attack is to do generic decoding for a random code (NP-hard problem)". but there is no reduction to some NP-hard problem that Goppa code (the specific code used in Classical McEliece) is indistinguishable.
the assumption is reasonable as nobody has been able to find a distinguisher for decades. also, if a distinguisher exists, it also doesn't translate into a direct attack against the system, it just means you cannot rule out "structural attacks" and jump to NP-hard problem.
(And this is even with the simplification that polytime = practical and not-polytime = infeasible.)
Relevant paper:
Impagliazzo, R. A personal view of average-case complexity theory. In Proceedings of the 10th Annual Conference on Structure in Complexity Theory. IEEE Computer Society Press (1995), 134–147.
https://ieeexplore.ieee.org/document/514853
Non-paywall links:
- https://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf
- https://gwern.net/doc/cs/cryptography/1995-impagliazzo.pdf
Popular scientific articles on this topic:
- https://www.quantamagazine.org/which-computational-universe-...
- https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the...