29 ms·

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 cryptos

by cobbal 2y ago

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.

ethanwillis 2y ago
Can you explain your usage of NP hard in your comment?
- saghm 2y ago
  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 https://en.wikipedia.org/wiki/NP-hardness
  - gpm 2y ago
    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)
    - saghm 2y ago
      Good to know! I guess I didn't recall as well as I thought.