How does the Bennett & Brassard protocol work?

Question

I’m studying a matter of quantum cryptography and I’m not understanding the workings of the Bennett & Brassard protocol, it all seems random and meaningless... Even reading other things on the Internet I still can’t understand how a person guesses 50% etc... Can someone explain to me how this protocol works?

Answer 1

Firstly, this protocol takes two things:

• A quantum channel, capable of sending qubits (for example, polarized photons sent by a fiber optic cable) state carries a information (for example, a classic bit, 0 or 1). That channel is public (i.e., it is not safe), so that it can be intercepted or passively (Eavesdropping) or actively (tampering).
• A second channel, classic, where one participant can send messages (bits) to another. For example, a radio broadcast or the Internet itself. Similarly, this channel is public (not secure).
  • Note: I may be mistaken, but by my understanding this protocol suffers from the same problem of protocol Diffie-Hellman, that is, it does not prevent Mitm by itself (i.e. he does not authentic Alice with Bob and vice versa). So in my opinion it would be safer using a channel more resistant to active attacks (e.g., radio transmission) than a more vulnerable one (e.g., internet, or any other channel that might suffer tampering).

For starters, Alice generates a random sequence of bits, sometimes larger than the key size she wants to trade. I can’t tell you the exact number, but let’s assume they want a 256-bit key to use with AES, and Alice started with a 4-bit sequence - 1024 bits. (if the idea is to use a One-Time Pad, then the key would have to be so big or bigger than the message to be sent).

Alice                     Eve                       Bob
k=0010101101110101

To encode these bits into qubits, Alice randomly chooses between two bases, for example a rectilinear (e.g.: 0° for 0 and 90° for 1) and a diagonal (e.g.: 45° for 0 and 135° for 1). If the rectilinear base has been chosen and the bit to be sent is 0, the resulting qubit will be →. If the diagonal base has been chosen and the bit to be sent is 0, the resulting qubit will be ↗. Idem for rectilinear and 1 (↑) and diagonal and 1 (↖). The sequence of qubits is then sent to Bob.

Alice                     Eve                       Bob
k=0010 1011  0111 0101
a=+xx+ xx+x  xx++ x++x
q=→↗↖→ ↖↗↑↖ ↗↖↑↑ ↗↑→↖    q=→↗↖→ ↖↗↑↖ ↗↖↑↑ ↗↑→↖    q=→↗↖→ ↖↗↑↖ ↗↖↑↑ ↗↑→↖

Note that although both Eve and Bob have received the qubits, they still don’t know what their value is - or even what basis they are on - because they haven’t yet measured. Note also that Eve cannot make a "copy" of these qubits (by the "non-ccloning") to measure them later - either she makes a measurement at the time the qubits went through it, or she loses the chance to get any information about them.

If Eve didn’t interfere...

Bob received the qubits, but he doesn’t know which bases are coded. So he tries to "guess" the base, hitting on average 50% of the time:

Alice                     Eve                       Bob
k=0010 1011  0111 0101                              k= ?0?0 1??? 01?1 ??0?
a=+xx+ xx+x  xx++ x++x                              b= xx++ x+x+ xxx+ +x++
q=→↗↖→ ↖↗↑↖ ↗↖↑↑ ↗↑→↖    q=???? ???? ???? ????     q=→↗↖→ ↖↗↑↖ ↗↖↑↑ ↗↑→↖

Every time Bob hits the plate, he gets the same bit that Alice knows. When it misses, it can get the same or opposite bit, with a 50% probability of occurring one or another scenario. For example, the first → read when measured on a basis x can turn into a ↗ (0) or a ↖ (1). In the example above, of the original 16 bases Bob hit 7 and missed 9. If it were 1024 bits, Bob would hit around 512.

(note that the bits that Bob got right may be more than 7, because whenever he has a ? He may have been wrong or wrong; but that doesn’t matter, for they can never be sure whether the bits are right or not, so that they are no longer useful for protocol)

Alice and Bob then reveal to each other which bases they chose, and compare the two sequences to know which qubits were successfully interpreted and which became "junk". The fact that this information is revealed now does not help Eve at all, because the qubits are gone and there is no more way to measure them (and remembering: there is no way to make copies of them for future use).

Alice                     Eve                       Bob
k=-0-0 1---  01-1 --0-                              k= -0-0 1--- 01-1 --0-
a=+xx+ xx+x  xx++ x++x    a=+xx+ xx+x xx++ x++x     a= +xx+ xx+x  xx++ x++x
b= xx++ x+x+ xxx+ +x++    b=xx++ x+x+ xxx+ +x++     b= xx++ x+x+ xxx+ +x++

Eventually Alice randomly picks a few bits to "throw away". This is important to help detect any interceptions, but I’ll let the explanation go. For now, just know that the revealed bits are no longer part of the common key.

Alice                     Eve                       Bob
k=-0-- 1---  -1-- --0-    k=???0 ???? 0??1 ????     k= -0-- 1--- -1-- --0-

The final key - 0110 - is known to both Alice and Bob but unknown to Eve (who only knows the bits that were thrown away and no longer serve any purpose). Of the 7 bits that Bob hit, 4 were used, 1/4 of the initial 16 amount. If they were 1024, the final key would have the desired 256 bits.

If Eve tried to interfere...

Let’s just say that Eve didn’t just "pass up" the qubits, which she tried to guess a basis and then measure them just like Bob had to. Like Bob, she has a 50% chance of hitting each base. The problem is that measuring it causes the qubit to take over the basis with which it measured. That is to say:

• If it hits (50%), the qubit goes away unchanged*, and Bob gets the same bit when he takes the measurement**;
• If it misses (50%), the qubit will take one of the two forms of the opposite base, so that when Bob measures it has a 50% chance of getting the wrong value although it uses the same base chosen by Alice!

(* "unchanged" in the sense that a measurement on the correct basis has little chance of introducing an error that causes Bob to obtain a different result than he would have had if the measurement had not been made; ** since of course he is also measuring on the right basis)

After all, for every qubit there is a 25% chance that Eve’s actions will introduce an error in Bob’s result, and this error will be significant in any case if Alice and Bob chose the same basis (i.e. in total, 12.5% of the common bits will be different for Alice and Bob).

Alice                     Eve                       Bob
k=0010 1011  0111 0101    k= 0010 1??? 0??1 ??01    k= ?0?0 1??? 0??1 ??0?
a=+xx+ xx+x  xx++ x++x    e= +xx+ x+x+ x+x+ +x+x    b= xx++ x+x+ xxx+ +x++
q=→↗↖→ ↖↗↑↖ ↗↖↑↑ ↗↑→↖    q=→↗↖→ ↖↗↑↖ ↗↖↑↑ ↗↑→↖    q=→↗↖→ ↖??? ↗??↑ ??→↖

In the above example, Eve missed 5 times, so that 5 qubits reached Bob in an undetermined state (equal to or different from its original state). Now see what happens when Alice reveals her bases and she and Bob try to determine which bits were successfully transmitted:

Alice                     Eve                       Bob
k=-0-0 1---  01-1 --0-    k= -0-0 1--- 0?-1 --0-    k= -0-0 1--- 0?-1 --0-
a=+xx+ xx+x  xx++ x++x    e= +xx+ x+x+ x+x+ +x+x    b= xx++ x+x+ xxx+ +x++

Alice and Bob believe they have the same bits. But some of them (in the example above, only one) are not guaranteed to be common, as Bob may or may not have derived the right bit. And anyway, Eve knows that that bit is part of the common key, but she’s also not sure whether or not she’s got the right result - because Alice and Bob chose the same base, while Eve chose the wrong base. At this point, the following things can happen:

1. The uncertain bits were chosen to be dropped. So:
   1. Alice and Bob got the same bit (50%); Eve got away with it...
   2. Alice and Bob got different bits (50%); now they know that someone interfered with the communication, and the protocol is aborted.
2. The uncertain bits remained in the common key. So:
   1. Alice, Bob and Eve have the same bit (25%); Eve has the right key...
   2. Alice and Bob have the same bit, but Eve does not (25%); Eve has the wrong key, and cannot read the later encrypted communication.
   3. Alice and Bob have different bits (50%); when in the future one tries to send an encrypted message to another, it will not be able to read, and they will know that someone interfered with the communication (although the protocol has successfully concluded).

In the above example, the bit entered the final key (scenario 2), so that the protocol successfully concluded despite Eve’s interference. Still, there’s a 25% chance that Eve might have a bit wrong (which would require her extra effort to crack the key) and 50% that Bob might have a bit wrong (which would allow him to discover that the communication was intercepted, although a posteriori).

Alice                     Eve                       Bob
k=-0-- 1---  -1-- --0-    k= -0-- 1--- -?-- --0-    k= -0-- 1--- -?-- --0-

Possibilidades:
Alice Eve  Bob   Resultado
0110  0100 0100  Eve e Bob têm a chave errada
0110  0100 0110  Eve tem a chave errada
0110  0110 0100  Bob tem a chave errada
0110  0110 0110  Eve e Bob têm a chave certa

These scenarios cited (among which some benefit Eve and others benefit Alice and Bob) are worth for every uncertain bit. That is, the more bits the key has, the greater the number of bits that will potentially present problems (1 in the example above that started with 16, 2 being the expected theoretical value; in one that started with 1024, 128 problematic bits would be expected).

Similarly, the more bits are chosen to "throw away", the greater the chance of detecting a discrepancy a priori and terminating the protocol with failure - a scenario preferable to completing it and leaving Eve with a partial knowledge of the shared key.

Bits jogados fora   Chance de algum ser problemático   Chance do problema passar despercebido
  1                 12.5%                              87.5%
  2                 23.4%                              76.6%
  3                 33.0%                              67.0%
  4                 41.4%                              58.6%
  5                 48.7%                              51.3%
 10                 73.7%                              26.3%
 20                 93.1%                               6.9%
 50                 99.9%                               0.1%
256                 99.99999999999986%                  1.4e-13%

Note: this answer assumed to simplify that the quantum channel is error-free, and that any discrepancy is due to an interception attempt. In practice, transmission and detection errors may occur that would cause Alice and Bob to end up with similar but distinct keys, even in Eve’s absence. A final phase would then be necessary, the "enhancing privacy and information reconciliation".