4
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – lPlant
    Jul 14, 2014 at 15:02
  • $\begingroup$ 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. $\endgroup$
    – Ran G.
    Jul 16, 2014 at 2:59

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

BB84 is unconditionally secure under the assumed threat model. This means that no assumption is made on the computational power of your adversary and therefore it is irrelevant whether P=NP or not.

Of course, implementing the protocol on actual hardware brings all sorts of other difficulties and vulnerabilities, but in the idealised mathematical model it is not breakable.

To contrast this with the classical case - classical key distribution can attain at best computational security, which means that your adversary is guaranteed to recover the key, but he may be under a severe computational disadvantage and thus would need a lot of time to do it.

Improve this answer
$\endgroup$

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.