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.
    Commented Jun 27, 2013 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
    Commented Jan 12, 2015 at 14:10

3 Answers 3


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
    Commented Jun 27, 2013 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$ Commented Jun 27, 2013 at 11:32
  • $\begingroup$ @HenrickHellström very interesting I will take a look at that :) $\endgroup$
    – Jaay
    Commented Jun 27, 2013 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
    Commented Jun 28, 2013 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
    Commented Jan 12, 2015 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
    Commented Jan 12, 2015 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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