News for hackers. Stuff that matters.
Re:Why cryptography is not based on NP-complete problems by cobbal on Wednesday February 12, 2025 @09:40PM (#43032108)
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.

Re:Why cryptography is not based on NP-complete problems by ethanwillis on Wednesday February 12, 2025 @10:04PM (#43032232)
Can you explain your usage of NP hard in your comment?
Re:Why cryptography is not based on NP-complete problems by saghm on Wednesday February 12, 2025 @10:14PM (#43032291)
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

Re:Why cryptography is not based on NP-complete problems by gpm on Thursday February 13, 2025 @12:00AM (#43032820)
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)
Re:Why cryptography is not based on NP-complete problems by saghm on Thursday February 13, 2025 @09:34AM (#43036209)
Good to know! I guess I didn't recall as well as I thought.