Hacker News Reader

The point is not that all NP hard problems make bad cryptosystems, but rather the NP-hardness guarantee fails to translate into a useful guarantee for a cryptosystem.

It's about the proof, not the computation.

View on HN

Can you explain your usage of NP hard in your comment?

A problem being NP-hard is one of the two requirements of being in NP-complete (the other being that it's NP). If I remember correctly, problems that are NP-hard without being NP are undecidable, so in contexts like "what problems can we base cryptography on?", it's basically the same as saying NP-complete, since we aren't able to base cryptography on undecidable problems.

https://en.wikipedia.org/wiki/NP-hardness

Not undecidable, it's just not possible to verify if an answer is correct in polynomial time. There are problems know to be decidable, known to be NP-hard and outside of NP. (E.g. in NEXPTIME)

Good to know! I guess I didn't recall as well as I thought.

Reply on news.ycombinator.com