Hacker News Reader

No. Public key cryptography is impossible if P=NP. What we are left with is shared one-time-pads that can be arranged using quantum key distribution.

I am not an expert so I will simply link the Wikipedia article on Computational Complexity Theory as my "source".

https://en.m.wikipedia.org/wiki/Computational_complexity_the...

View on HN

If there is an n^(100^100) algorithm that solves an NP-complete problem, then P=NP, but public-key cryptography is still safe because for any practical n it's still too hard to break. There are also public-key systems that are based on NP-complete problems that are easily broken, because n is chosen too small.

Thank you for schooling me on this. I wasn't considering n^(100^100) problems.

Reply on news.ycombinator.com