# What happens to quantum algorithms such as BB84 if P=NP

Under the hypothesis that P=NP, many cryptographic protocols are no longer secure (i.e. attacks are feasible).

The BB84 algorithm is based on the idea that by observing a quantum state, one has to (in quantum theory) disturb that state. This makes them efficient against eavesdropping.

Are quantum algorithms based on BB84 also subject to the hypothesis that P=NP? Or do they remain unaffected by the hypothesis?

• Which applications are no do you consider no longer secure? The idea that if P=NP then cryptographic protocols are vulnerable is not exactly true. In cryptography,in most current applications, an algorithm that runs in polynomial time may not still be sufficient. Take RSA as an example, lets say that we have figured out a way to factor numbers in $O(n^2)$, that doesn't mean that RSA is broken, in fact for many cryptographic applications the run time of the algorithms used to break them need to be in the area of $O(log(n))$. Since even linear time on a 4000 binary digit number is far to slow. Commented Jul 14, 2014 at 15:02
• BB84 is known to be unconditionally secure, that means it is secure independent of the P=NP question, or any other restriction other than the postulates of quantum mechanics. Commented Jul 16, 2014 at 2:59

BB84 is simply a key exchange procedure. This procedure remains secure unless someone can figure out how to observe a quantum phenomenon without changing it, whether or not $P=NP$ will not change this. If the vulnerability of the algorithm was in key transmission, then it is safe if it uses BB84. If it is however somewhere else in the algorithm, then no matter how the key is transmitted it will be vulnerable. So really it depends on the algorithm and the exposed vulnerability. Most algorithms that could be broken by a drastic reduction in run time however are public key algorithms, private key algorithms are much more secure, however the key exchange is the risky part and usually uses some form of public key based encryption. With BB84 however the key exchange becomes relatively safe. So for the most part, the algorithms that would use BB84 are not vulnerable unless the key can be discovered, which requires breaking BB84 and therefor changing the modern understanding of physics. Unfortunately the infrastructure is not yet in place for BB84 to be realistically implemented.