3
$\begingroup$

I'm learning about Quantum Key Distribution, and just learned about the BB84 exchange. I learned that it can be used to exchange a key for a one-time pad, which would allow for information-theoretically secure communication. As I understand the algorithm:

  1. Bob and Alice decide on 2 different bases to encode quantum states
  2. Alice chooses a basis and a random bit to prepare a qubit and transmits the prepared qubit to Bob.
  3. Bob randomly chooses a basis to measure the received qubit in
  4. Alice and Bob communicate over a classical channel and figure out which bits they measured with the same basis

Eve can try to intercept the qubit Alice sends, but Eve has to randomly guess which basis to measure in because she has no information about which basis Alice prepared the qubit in. This means Eve has a 50% chance of choosing the right basis for any given transmitted qubit and a 75% chance of not introducing a disagreement between Alice and Bob by collapsing the state of the qubit.

Let $n$ be the number of qubits Alice and Bob measure in the same basis. This means that Eve has $0.75^n$ chance of getting lucky and getting the key while going unnoticed. She could then check if Alice and Bob continue to communicate to see if she went unnoticed. Eve can also eavesdrop over the classical channel Alice and Bob use to communicate the bases they used to throw out measurements she made that were not included in the key. Now Eve has constructed the key and knows it's the correct key.

While the probability of Eve measuring the key correctly scales exponentially with respect to $n$, it seems like this algorithm is not safe unless roughly $n > 1000$.

Is there something I'm misunderstanding, or is the above argument valid? Is there any way to guarantee Eve has no chance of guessing the correct key?

This is an answer to a similar question but does not answer my final question.

Improve this question
$\endgroup$
7
  • $\begingroup$ Welcome to QCSE. Why do you think $n$ needs to be $1000$ or more? $0.75^n$ grows very quickly to $0$. $\endgroup$
    – Mark Spinelli
    Jul 22, 2020 at 19:59
  • $\begingroup$ That was just a very rough estimation. 0.75^100 is around 10^-13, and 0.75^1000 is around 10^-125. If n=100, then on average 1 in 10^13 key exchange interception attempts will go undetected. If you imagine roughly 10^10 people sending 10^3 messages and someone trying to intercept every message, then on average 1 person's key will be intercepted. If n=1000, then the number of messages sent before it becomes likely a key is intercepted needs to be around 10^115. That's a ridiculous number of messages, so I figure that's good enough. $\endgroup$
    – jet457
    Jul 22, 2020 at 20:09
  • 2
    $\begingroup$ Eve has a chance of 0.5^N of correctly guessing any secret message right away. $\endgroup$
    – Norbert Schuch
    Jul 22, 2020 at 21:34
  • $\begingroup$ I think you're missing the step of BB84 wherein Alice and Bob sacrifice some of their codeword and Alice publicly announces her chosen basis, along with her chosen bit, to Bob. If $n\gt 100$ Eve will get caught in her lie. The probability of catching Eve grows exponentially close to $1$ as the length of the message increases. $\endgroup$
    – Mark Spinelli
    Jul 22, 2020 at 21:39
  • $\begingroup$ @NorbertSchuch Your N is the length of the encrypted message. The n in the question is the length of the encryption key. Typically n << N $\endgroup$
    – Bruno Rijsman
    Nov 25, 2021 at 13:01

1 Answer 1

Reset to default
3
$\begingroup$

I like Norbert's comment about the chance of Eve guessing the message without any eavesdropping (it points out that the probability of Eve succeeding can never be made 0), but thought I should also point out a very different perspective - that of the context in which you would use quantum key distribution.

In the context of today's communication, 1000 bits is a very small message. For something that small which needs high security, the two parties would probably meet up in person in advance and exchange a secret key. No key distribution protocol required (OK, I know there will always be people who cannot meet up, especially in these crazy times). The setting where key distribution becomes more relevant is when there are unpredictable quantities of data to be sent, e.g. large volumes, or even continuously generated data. Just think what value $n$ has for a gigabyte of data (even ignoring the fact that some proportion of the data needs to be sacrificed for security checks, error correction, privacy amplification etc). $n=8\times (1024)^3\approx 9\times 10^9$. Put that in your exponential!

Improve this answer
$\endgroup$

Your Answer

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

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