[honzaik]

afaik the "right kind of code" does a lot of heavy lifting for practical implementations, such as Classical McEliece.

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.

[less_less]

Yeah that's right, there are no known cryptosystems whose security is based on the difficulty of solving an NP-hard problem. It's not known even in theory whether P != NP implies that one-way functions exist: for example, it might be that all NP problems are easy on average, or that there are problems that are hard on average but that you can't sample the problems and their solution at the same time.

(And this is even with the simplification that polytime = practical and not-polytime = infeasible.)

[aleph_minus_one]

> It's not known even in theory whether P != NP implies that one-way functions exist: for example, it might be that all NP problems are easy on average, or that there are problems that are hard on average but that you can't sample the problems and their solution at the same time.

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...