Is BB84 Quantum Cryptography Secure Against Eavesdropping?

[Chen]

I'm having some doubts about this technique... assuming Alice sends Bob 1,000 polarized photons. Our eavesdropper Eve will be able to measure 500 of them correctly, and she will also measure 250 other correctly by mistake (when using the wrong polarization to measure the photons, there's a 50% chance they will be measured either way). So in total she knows 750 of the bits. But half of all bits will be discarded, because Bob will use the wrong polarization half of the time. So in total, of the 500 bits Alice and Bob are going to work with, Eve would have 375 correct ones (half of 750), just like Bob.

My question is, how can Alice and Bob apply error correction codes when Bob and Eve have the same knowledge regarding the bits? It seems that no matter what Alice and Bob, Eve will know at least as much as Bob does and therefore will be able to know the final corrected key, just like Bob.

In fact, it looks to me like Eve knows even more than Bob! Bob doesn't know which of the photons were incorrectly measured by Eve, so he doesn't which of the bits he knows are correct and which are possibly correct. Eve, on the other hand, knows which polarization Alice used to begin with (since Alice and Bob compare them publicly on an open channel), so she knows exactly which bits are correct for sure and which are not. The random shuffling of the bits by Alice and Bob doesn't really help, either, because it is also done over a public channel so Eve can shuffle her bits accordingly.

So when Alice and Bob start comparing parities, as part of the error correction routine, Eve can also compare the parities of her bits to the parities decalred by Alice and Bob. If the parities of Alice and Bob don't match on one block, that's great for Eve - they will start bisecting the block into smaller blocks and Eve will be able to learn even more about their data. Eve is only in trouble if the parities of Alice and Bob match, but Eve's don't. But even then it's possible that there were an even number of errors on that block, and on the next round of error correction the parities won't match and Eve will become smarter yet again.

This seems like a pretty big flaw, so I'm sure it's been thought of before and dismissed. Could anyone please shed some light?

Thanks,

 

[florianb]

You're basically right

Despite the fact that I'm not an expert, I think that you are basically correct.

In fact, noise and eavesdropping both create bit flips in the final key that Alice and Bob have. If you try to correct errors induced by the noise of your quantum channel, you will also correct errors resulting from eavesdropping...

Eve, by listenning to the quantum channel, will measure 50% of the photons in the right basis, thus not changing anything in the signal (and reading it correctly). When Eve uses the wrong basis, the measurement made by Bob is wrong every two photons. This mean that Eve introduces an error every 4 bit (25%).

In order to have an efficient quantum cryptographic device, you need to have a quantum link which introduces much less noise (lets say 5%) !

When the quantum transmission is done and all the bits that were measured by Bob in the wrong basis are discarded. Bob and Alice can just choose a set of bits (lets say half of the bits) from their respective keys and just publicize them. They are now able to check the percentage of error/noise that occured. If it is anormally high (more than 5% in this case), then eavesdropping has occured, and the whole session is to be discarded.

I hope this helps, and if somebody finds something wrong in my argument, I'd be happy to know !

 

[slyboy]

Your agrument is basically right, apart from the figures you quoted. I think they can tolerate an error rate larger than that. They use techniques called privacy amplification and information reconcilliation to reduce the amount of information Eve has about the key and correct any errors. In practice, this means that a large number of photons have to be sent to generate each bit of secert key. In any case, if the error rate is too high then they can detect Eve's presence and simply abort the protocol.

The most straightforward proof of the security of BB84 can be found in http://xxx.arxiv.org/abs/quant-ph/0003004. It is a rather condensed article, but a much more detailed discussion of this proof can be found in the final chapter of Nielsen and Chuang.

 

[Chen]

Thanks for your replies.

I do understand how the protocol works, and even managed to simulate it successfully in a script (the bits we generated randomly, though; I couldn't find any photons :tongue:). But I do have doubts as to the security of the protocol.

As I said, it seems that not only does Eve possesses the same amount of correct bits as Bob, she actually knows better than him which are correct and which are not. So my concern is that due to the error correction (or information reconciliation as it is sometimes referred to), which reveals even more information to Eve, and despite the privacy amplification process, Alice and Bob will share the same key but it will not be completely private.

As I said, I'm sure I'm not the first one to think along these lines, and I'm also sure these concerns have been debunked before. What I would like to know is why, despite of all of the above, the final key shared by Alice and Bob will not be known to Eve (or at least most of it).

Thanks,

 

[meteor]

But I do have doubts as to the security of the protocol

This paper
http://arxiv.org/abs/quant-ph/9812064
gives an attack strategy for the BB84 protocol. The attack strategy is called "indirect copying attack", and the authors say that using this strategy, the BB84 protocol is at risk

 

[Chen]

Thanks for that meteor, I will print and read that tonight.

slyboy: I've found the following simulation of information reconciliation here:
http://www.crypto.ethz.ch/research/keydemo/InformationReconciliation.html
It works well and everything, but it assumes an initial estimated bit error probability of only 4%. In the case of BB84, assuming the eavesdropper measures the value of every photon, the expected error rate is 25%. If we perform 3 rounds of reconciliation with doubling block sizes starting with 4 (we only expect one error in every 4 bits), we would reveal about 43.75% parity bits. In round 1, we compare blocks of 4 bits so 25% parity bits will be communicated. In round 2 we only check every 8 bits, but that's another 12.5% parity bits. Round 3 only checks every 16 bits, but still 6.25% parities will be exposed. And that's if we ignore the parity bits revealed when actual errors are corrected during the bisect of wrong blocks!

Something is definitely not adding up here. I'm well aware that Alice and Bob can measure the estimated error rate before proceeding to the reconciliation step, and abort the process if it's over 10%, for example. But is that really the answer? Shouldn't the protocol be able to ensure successful key exchange even when we assume worst conditions?

 

[Njorl]

It looks like the eavesdropper must insert herself into the communication channel. This will invariably cause a time delay. The signals can not be tapped, they must be captured and regenerated (though not perfectly). If Bob and Alice arrange for a rigorously timed exchange, they should be able to detect the eavesdropping.

If we assume that the time schedule has been exchanged in an unsecure mode which Eve has obtained, can she pull pull it off?
Njorl

 

[Chen]

Njorl,

Alice and Bob can detect eavesdropping by a number of methods, most of which you already described. My question is, though, what are they going to do when they do detect eavesdropping? Most papers on this subject simply say that they should abort the operation and try again. But what's to stop Eve from eavesdropping again? According to this, without a successful method to overcome eavesdropping, the BB84 protocol is basically useless, isn't it?

 

[slyboy]

If the eavesdropper measures every photon then Alice and Bob will detect the eavesdroppers presence and abort the protocol. They will not be able to distill any secret key. This is completely uncontroversial.

An implicit assumption is that the eavesdropper not only wants to gain some information about the key, but also wants to avoid being detected. Her aim is to be able to decode Alice and Bob's secret messages without them being aware that this is happening. This is pretty much the definition of the term "eavesdropper". It is NOT her aim to prevent them from communicating at all. The latter task would be better achieved by simply cutting all the communication lines between Alice and Bob.

No cryptography protocol is designed to stop an enemy from preventing communication altogether. This is why the military still thinks it is a good idea to attack transmitters in a war situation.

Note that it is not stricly correct to say that " assuming the eavesdropper measures the value of every photon, the expected error rate is 25%". This assumes that the best strategy is for the eavesdropper to measure the photon in one of the bases used in the BB84 protocol. This is not necessarily the case, as she could do a much gentler type of measurement that gives her less information about the state, but also disturbs it to a lesser extent. She could also collect many of Alice's photons together and perform a big quantum computation on all of them together (assuming Bob doesn't notice the time delay). Remarkably, the security proof for BB84 still works for these cases as well.

 

[Chen]

Well, by preventing Alice and Bob from using any means of quantum cryptography, the eavesdropper could force them into using a classic, less secure means. For example, Alice and Bob would see that they can't complete the BB84 protocol, and resort to using traditional PGP, which Eve can easily break assuming she has quantum computational abilities. So in that sense, she has certainly achieved her goal.

But I'm not here to debate the semantics of this subject, and I do understand and accept your point that one of Eve's concerns is not being detected. I'm preparing a lecture on quantum cryptography, and I was just thinking what to answer when someone asks the same question I asked in my first post. I think I have an answer now.

Note that it is not stricly correct to say that " assuming the eavesdropper measures the value of every photon, the expected error rate is 25%". This assumes that the best strategy is for the eavesdropper to measure the photon in one of the bases used in the BB84 protocol. This is not necessarily the case, as she could do a much gentler type of measurement that gives her less information about the state, but also disturbs it to a lesser extent.

Could you please extend on this a little? If the photons are sent with orthogonal and diagonal bases, do you mean that Eve can measure them with a base that is a mixture of the two?

Thanks,

 

[slyboy]

Could you please extend on this a little? If the photons are sent with orthogonal and diagonal bases, do you mean that Eve can measure them with a base that is a mixture of the two?

She can do something even more subtle than that. She could interact the photon with another quantum particle, which might have a much larger Hilbert space, and then perform a measurement on the second particle. The effect on the original photon is to perform a POVM (Positive Operator Valued Measure), which allows a far greater range of possibilities. For example, the measurement might have far more than two possible outcomes.

Nielsen and Chuang's book contains a thorough discussion of POVMs.

 

[Chen]

Has it been proven such a feat was practically possible? In other words, is it possible to interact the photon with another particle without disturbing its original state? I would presume so, otherwise this technique would be pretty useless as well...

Well this is certainly an interesting twist. I was always under the impression (mostly because of books I've read about this subject) that quantum mechanics would allow us to develop such cryptographic system that are absolutely foolproof (as opposed to current modern cryptosystems which rely on our limited computational power). But now you're saying that quantum mechanics provide encryption crackers with even more powerful tools, rendering anything we can possible come up with subject to attacks?

(I don't wish to bother you too much with this, especially now that I basically have the answer I was originally looking for. So feel free to tell me to RTFM. )

 

[Chen]

I think I finally found the missing stage... all papers I read about BB84 forgot to mention the "advantage distillation" phase, which is explained here:
http://www.crypto.ethz.ch/research/keydemo/AdvantageDistillation.html
I've ran some tests myself. If Bob and Eve both start with a 25% error rate (almost worst case scenario, right?), after just one round of distillation Bob's rate drops to around 10% while Eve's rate only drops to 20%. This provides Bob with the inital advantage over Eve (which I was so desperately looking to achieve), and it also lowers the error rate before the reconcilliation phase, which makes it easier.

 

[meteor]

Today seems a good day for quantum cryptography...
http://www.newscientist.com/news/news.jsp?id=ns99995076
"First quantum cryptography network unveiled


18:43 04 June 04

NewScientist.com news service

The first computer network in which communication is secured with quantum cryptography is up and running in Cambridge, Massachusetts.

Chip Elliott, leader of the quantum engineering team at BBN Technologies in Cambridge, sent the first packets of data across the Quantum Net (Qnet) on Thursday. The project is funded by the Pentagon's Defense Advanced Research Projects Agency."

Though i don't know the QKD protocol used in this Qnet, don't know if is the BB84 protocol or other (for example the Ping Pong protocol). But anyway, the news seemed to me interesting

 

[slyboy]

Has it been proven such a feat was practically possible? In other words, is it possible to interact the photon with another particle without disturbing its original state? I would presume so, otherwise this technique would be pretty useless as well...

No, the interaction DOES disturb the state of the system. This is a consequence of the no-cloning theorem. The point is that it makes for a larger number of possible strategies for the eavesdropper and we have to rule them out as well.

I think I finally found the missing stage... all papers I read about BB84 forgot to mention the "advantage distillation" phase, which is explained here:

I thought that "advantage distillation" was the same as what is usually called "privacy amplification" in the quantum cryptography literature. I could be wrong about this.

However, it still won't work if Eve measures every single photon in one of the BB84 bases. In that case, any correlations between Alice and Bob's results are determined by the correlations between Alice and Eve's results. For advantage distillation to work, the errors in Bob's and Eve's results have to be somewhat independent.

 

[Chen]

meteor: Thanks, that's very interesting.

I thought that "advantage distillation" was the same as what is usually called "privacy amplification" in the quantum cryptography literature. I could be wrong about this.

However, it still won't work if Eve measures every single photon in one of the BB84 bases. In that case, any correlations between Alice and Bob's results are determined by the correlations between Alice and Eve's results. For advantage distillation to work, the errors in Bob's and Eve's results have to be somewhat independent.

At least in the papers I read, "privacy amplification" was the application of a random hash function to the bits that remained after the reconcilliation. Basically it went from quantum communication to reconcilliation to amplification.

While Bob and Eve share the same amount of errors, they are not necessarily located at the same place...even if Eve uses the wrong base, and thus have a 50% chance to record an error, Bob has an equal chance to measure a good bit after all. I've just checked in my script and the Eve has 25% wrong bits whether we check hers against Alice's or Bob's. As for whether it works or not... I'm pretty sure it does, unless I made a mistake in my script (and since I do get the expected results, I don't think that's the case).

 

[Njorl]

How about this.

Eve intercepts every photon from alice and Bob. She also sends them random photons that they are expecting at the times they are expecting them. She interacts with each one as if she isthe other.

At they end, she has 2 keys. One to use with alice, one to use with bob. Their keys don't work with each other, but that doesn't matter. They will never talk to each other with those keys. they only talk to eve.

Njorl

 

[Gelsamel Epsilon]

I'm having some doubts about this technique... assuming Alice sends Bob 1,000 polarized photons. Our eavesdropper Eve will be able to measure 500 of them correctly, and she will also measure 250 other correctly by mistake (when using the wrong polarization to measure the photons, there's a 50% chance they will be measured either way). So in total she knows 750 of the bits. But half of all bits will be discarded, because Bob will use the wrong polarization half of the time. So in total, of the 500 bits Alice and Bob are going to work with, Eve would have 375 correct ones (half of 750), just like Bob.
Thanks,

OK i didn't read anything other then what you said, so if somones already said this, forgive me. But eve won't get the Same correct photons as bob, and therefore will get the wrong code, ( you do know that the photons r to make a code to encript with?)

 

[slyboy]

How about this.

Eve intercepts every photon from alice and Bob. She also sends them random photons that they are expecting at the times they are expecting them. She interacts with each one as if she isthe other.

At they end, she has 2 keys. One to use with alice, one to use with bob. Their keys don't work with each other, but that doesn't matter. They will never talk to each other with those keys. they only talk to eve.

You are correct that this is a loophole. Recent discussions of quantum cryptography are careful to point out that Alice and Bob must use an authenticated classical channel (i.e. one where Bob can be sure that the messages are coming from Alice and vice-versa). Fortunately, there are pretty good classical authentication protocols and there are also quantum mechanical authentication schemes.