TransWikia.com

Can Eve randomly guess the correct bases in the BB84 exchange of a one-time pad?

Quantum Computing Asked by jet457 on December 18, 2020

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.

One Answer

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=8times (1024)^3approx 9times 10^9$. Put that in your exponential!

Answered by DaftWullie on December 18, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP