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