4 ms·

Does 'quantum-resistant' also imply 'P=NP' resistant?

• blendergeek 4y ago
  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_theory https://en.m.wikipedia.org/wiki/Computational_complexity_the...
  • bwesterb 4y ago
    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.
    • blendergeek 4y ago
      Thank you for schooling me on this. I wasn't considering n^(100^100) problems.
• a1369209993 4y ago
  You're thinking of P=BQP (which still falls into the seems-to-not-be-true-but-we-can't-prove-it category, but physics runs BQP already, so we don't need P=BQP for BQP attacks like Shor and Grover to be issue).