5 ms·

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 whet

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 2y ago
> 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 https://ieeexplore.ieee.org/document/514853 Non-paywall links: - https://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf https://www.karlin.mff.cuni.cz/~krajicek/ri5svetu.pdf - https://gwern.net/doc/cs/cryptography/1995-impagliazzo.pdf https://gwern.net/doc/cs/cryptography/1995-impagliazzo.pdf Popular scientific articles on this topic: - https://www.quantamagazine.org/which-computational-universe-do-we-live-in-20220418/ https://www.quantamagazine.org/which-computational-universe-... - https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/ https://cacm.acm.org/research/fifty-years-of-p-vs-np-and-the...