0

I know, I know - "If P=NP" is a really large, high-impact assumption.

But this is a hypothetical.

I mean, clearly RSA (and similar methods of obfuscation) would likely become totally irrelevant - or would they? Being solvable in polynomic as opposed to exponential time would be a significant blow to their operation, but could they make use of public/private keys so large (if P=NP, then more efficient prime-number-locators seem likely) that cracking them is still something "difficult?"

Those are mostly just points of discussion. In terms of raw question: What methods of cryptography don't ultimately rely on P!=NP?

Improve this question
1
  • Best not to mention that cryptography is just stylized, extreme improbability obscurity in the presence of fundamentalist "obscurity is not security!" zealots... That said, cryptography is a moving target -- what is "secure" today will be an open book tomorrow, hence the only real security is physical control over your own media.
    – zxq9
    Commented Mar 15, 2014 at 12:49

2 Answers 2

Reset to default
0

Any classical cryptography scheme is algorithmic in nature i.e. any classical cryptography scheme can be broken (in principle). The upcoming field of quantum information I think can one day be able to make communication secure. If you want to read more about quantum key distribution protocols try searching: BB84 protocol, B92 protocol and eckert protocol.

Improve this answer
0

It depends. If P = NP, but the best algorithm to solve a general NP-complete like SAT is say O(N^10) with suitably large constants, then despite being polynomial our conventional cryptography for values of N used today will still hold. If P = NP with solutions for a general NP-complete problem that is say O(N^3) with suitably small constants, then a lot of cryptography will become quite weak.

Checking for primality is already quite efficient (not exponential time), so a reduction of SAT to P wouldn't necessarily speed up searches for prime numbers in any significant way.

Improve this answer

Not the answer you're looking for? Browse other questions tagged .