21

If we suppose that it is found that P=NP, how will security measures need to be changed?

I'd like to know the major security measures that are affected, and how they would need to be changed. We can suppose that passwords can be hacked in time O(n^4), for the sake of argument.

As an example of what I'm partly looking for, we might have an answer like RSA passwords of 1,024 bits would need to be extended to 5 million bits, or SSH would be rendered insecure. I guess I'm attempting to get a scientific measure of changes that should take place without getting into the realm of speculation. So we would probably have to first determine what level of security is adequate, and then compare the necessary changes. So to have this level as part of the question, we can simply use common security practices in effect today.

I'm somewhat of a novice in the realm of IT security, so I'm hoping that someone can help point out what's important to know in this scenario.

Improve this question
5
  • Where "n" is the number of bits in the password? Number of possible passwords? If the second, then it's already linear time....
    – Billy ONeal
    Commented Mar 16, 2012 at 21:21
  • 1
    @Billy Oneal: "n" is meant to be the number of bits in the password.
    – Matt Groff
    Commented Mar 16, 2012 at 21:42
  • Ah, I see then. Many symmetric algorithms are not NP hard (they are "worse" than that) according to that standard. Unless the attacker can do a known cleartext attack, that is.
    – Billy ONeal
    Commented Mar 16, 2012 at 22:01
  • @BillyONeal: This sounds interesting. Do you mean that even the power to solve SAT wouldn't be enough to break their security? (I'm very interested in algorithms/security measures that have very strong security)
    – Matt Groff
    Commented Mar 17, 2012 at 6:17
  • SAT is in class NP == which requires that verifying a correct solution can be done in polynomial time. For most symmetric ciphers, unless the attacker knows some part of the cleartext, there's no polynomial time way to determine whether you found the correct key. Therefore that's not in any way related to SAT. Of course if the attacker can control some of the cleartext then the verification step is made easy, and things are reduced to NP complexities.
    – Billy ONeal
    Commented Mar 17, 2012 at 7:48

1 Answer 1

Reset to default
25

The answer is: it depends.

  1. Suppose we found a O(n^4)-time algorithm for a NP-complete problem like SAT, where the constant hidden by the big-O notation isn't too large. That would kill pretty much all of modern cryptography, including symmetric-key cryptography and public-key cryptography. The only things left standing would be information-theoretically secure cryptosystems, like the one-time pad and Carter-Wegman-style message authentication.

    In that case, one might be able to respond by designing cryptosystems with a 10 million-bit key or so, but oh boy, life would suck. It would be pretty tough to transfer around keys that large. And it would be awfully hard to trust the resulting cryptosystem for any kind of enduring security. If today someone comes up with an O(n^4) algorithm for SAT, you have to assume that maybe next year someone is going to figure out how to improve that to O(n^3 log n) or something like that. So, in practice, if someone finds a practical O(n^4) time algorithm for SAT, a lot of cryptography rests on a foundation of sand, and we'd have to re-think everything.

  2. Alternatively, suppose someone found an O(n^100)-time algorithm for a NP-complete problem like SAT. In terms of immediate impact, such an algorithm would be totally useless for cracking cryptography. However, in many ways we'd be in the situation of the last paragraph: everyone would wonder if next year some genius will improve this to O(n^10), and then the year after that O(n^4), and so on. This could easily be a blow to folks' confidence in the security of modern cryptography. So this too would be a pretty ground-shattering discovery, even if it has no direct immediate impact.

  3. Or, suppose someone finds a non-constructive proof that there exists a polynomial-time algorithm for some NP-complete problem, but with no indication of how to turn this into a real algorithm and no evidence that the resulting algorithm will be efficient in practice. Then we'd just be in a state of confusion. No one would know whether maybe we are in the world of bullet 1 above, or the world of bullet 2, or something else entirely.

All that said, I don't think any of these scenarios are very likely in the foreseeable future. In fact, I would go so far as to guess that they are very unlikely. We could just as well talk about what the effect on cryptography would be if a massive asteroid struck the earth next year. Well, the impact would be pretty devastating -- but the likelihood is pretty tiny. I think there are much more relevant, likely things to worry about.

So, if you are wondering whether you should take some steps to protect yourself against the possibility that someone proves P=NP: don't bother. That's a waste of time. Spend your energy on more realistic threats.

Improve this answer
14
  • Thanks very much for your answer. It is what I was looking for.
    – Matt Groff
    Commented Mar 16, 2012 at 18:06
  • 1
    What about symmetric key cryptosystems rely on NP-hard problems? Most symmetric algorithms are stronger than that, I thought?
    – Billy ONeal
    Commented Mar 16, 2012 at 20:51
  • The quantum computing guys keep threatening us with infinitely fast computers that will supposedly be able to crack just about anything via brute force. Any comment about that? (I'm personally doubtful that their theories hold water, but if they do it could be bad.)
    – Hot Licks
    Commented Mar 17, 2012 at 0:21
  • @BillyONeal - There are no symmetric-key cryptosystems that rely on anything harder than a NP-complete problem. It is impossible to have a symmetric-key cryptosystem that is harder than NP to break. If P=NP, then all symmetric-key cryptosystems can be broken in polynomial time. This is because breaking a symmetric-key cryptosystem is in NP, no matter what symmetric-key cryptosystem you're talking about. For instance, if you are given a known plaintext-ciphertext pair (P,C), then finding a key K such that E(K,P)=C is a search problem, and thus is "in NP" (it is no harder than SAT).
    – D.W.
    Commented Mar 17, 2012 at 0:45
  • 1
    @HotLicks, quantum cryptography is a different matter, and you should ask about it in a separate question, to avoid mixing things up here. See, e.g., here, here, and here. The short answer: quantum computers, if practical, could break some cryptosystems, but (as far as we know) not all of them.
    – D.W.
    Commented Mar 17, 2012 at 3:07

You must log in to answer this question.

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