I've recently heard some people claiming that if the fact that P = NP is proven, most (all?) the current cryptographic algorithm considered secure like RSA will be unusable in secure systems.

My question is :

1. If P = NP is proven TODAY, will a RSA key (let say 3072 bits) be still enough to ensure a certain amount of security.

2. If not, what could we do to have at least the same amount of security (take a larger key length? a stronger algorithm?)

  • 5
    $\begingroup$ Besides $P=NP$ there are other possibilities "bad for crypto", see "A Personal View of Average-Case Complexity" by Russell Impagliazzo (available from his webpage as postscript). $\endgroup$
    – j.p.
    Jun 27 '13 at 12:16
  • 2
    $\begingroup$ General statements about complexity classes should not be mixed with actual numbers. Even if breaking RSA was possible in $P$ and expressed in some polynomial in $O$ notion, this does not mean you can derive 1024 is unsafe and 3072 bit is safe. First, P contains any power over $n$. Second: This still does not put a relation to computation power, time required and bitsize. There are constants (or better: coefficients) to required, to get the actual relations. $\endgroup$
    – tylo
    Jan 12 '15 at 14:10

A proof of P = NP would prove that one-way functions do not exist. That in turn would imply, that almost no secure cryptographic primitives can exist according to the accepted definitions of security. (No symmetric encryption, no MACs, no pseudorandom generators, no signature schemes, ...)

However, it would just mean that no scheme can be provably secure. It does not mean that all schemes would be broken in practice. It might even be possible to adapt our definitions of security in a meaningful way.

In particular, it is very much conceivable that a proof of P=NP would be non-constructive. Such a proof would not help in any way. It would just mean that there exists an algorithm to efficiently break RSA (for a theoretical definition of efficiency, i.e. in polynomial time) but that does not mean that we know said algorithm. And even if the algorithm is known, it might not be efficient in practice. An algorithm running in $\mathcal{O}(n^{2^{100}})$ is technically a polynomial time algorithm, but it isn't very helpful.

So in conclusion, the question whether some keysize would still remain "secure" or how we could regain some measure of security cannot be answered in general, as it depends on the exact nature of the proof.

  • $\begingroup$ When you say "almost no secure cryptographic primitives can exist according to the accepted definitions of security", do you have an example of such system that will be less concerned by one-way function problem? $\endgroup$
    – Jaay
    Jun 27 '13 at 10:56
  • $\begingroup$ @Jaay: The one time pad, and Shamir secret sharing, are both information theoretically secure, and wouldn't be affected by P=NP. $\endgroup$ Jun 27 '13 at 11:32
  • $\begingroup$ @HenrickHellström very interesting I will take a look at that :) $\endgroup$
    – Jaay
    Jun 27 '13 at 11:41
  • 1
    $\begingroup$ As Henrick Hellström said, basically everything, where the security stems from information theoretic arguments would remain secure. Everything based on computational hardness should basically fail. The main problem is, that most cryptographic primitives cannot be implemented in a usable way without assuming computational hardness. (Think of symmetric encryption, sure OTP still works, but it isn't very usable in practice.) $\endgroup$
    – Maeher
    Jun 28 '13 at 7:14
  • $\begingroup$ To follow up, there exists a proof of polynomial non-reducibility, that is, there are algorithms of P where P has arbitrarily high power. $\endgroup$
    – Joshua
    Jan 12 '15 at 19:39

I've previously answered this question over at How will security need to be changed if P=NP? (on our sister site, the IT Security Stack Exchange). In addition, see the answers to What would be the scenario if P = NP for RSA algorithm? for still more on the subject.

The short answer is that a proof that P=NP doesn't necessarily mean that all cryptography is insecure in practice -- it does mean we would need to re-evaluate carefully the basis of security of our cryptographic schemes. It's hard to say too much more without knowing the specifics of how we come to know that P=NP.

But read the answer to those questions; they cover it in great depth.


Here is a posting from two decades ago about why P=NP has nothing to do with cryptography:


  • 1
    $\begingroup$ Link-only posts aren't very helpful if the link moves. It's generally recommended that you summarize what the link has to say within the answer. $\endgroup$
    – poncho
    Jan 12 '15 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.