Quantum Key Distribution

If Alice and Bob wish to send secret messages to each other, the only way they can be absolutely sure there is no one eavesdropping on their conversation is to use a one-time pad: Alice and Bob share a private key, which is a random sequence of bits known to both of them, but not to anyone else. Then to send a message, Alice converts it into a string of bits, and performs the XOR between each of her bits and each of a series of key bits, then sends the result to Bob. That is, for each message bit m, Alice sends instead m + k, where k is a key bit (the XOR is addition modulo 2, so if both m and k are 1, Alice sends 0). She only uses each key bit once - if a key bit is used twice, an eavesdropper might be able to deduce some information about the message.

Since Bob also knows the key bits, he can easily decode the message by taking the XOR of the received bit r with the appropriate key bit k:

m = r + k

On the other hand, an eavesdropper Eve knows nothing about k. To her k is just a random bit, so r is also a random bit. Therefore, looking at r tells her nothing about m. Eve learns nothing about the message.

The problem with the one-time pad is that it tends to use up key bits very quickly, since they cannot be reused. Quantum key distribution provides a method to renew the key using just public transmissions plus the transmission of quantum bits.

One of the best-known protocols for quantum key distribution is usually called BB84, since it was proposed by Bennett and Brassard in 1984. In BB84, Alice sends Bob a random sequence of quantum bits (or qubits). These quantum bits are equally likely to be in one of four possible states:

When Bob receives a qubit, he randomly chooses to measure it either in the Z basis or the X basis, and records the results. Bob now has a string of random bits. Then Alice announces which basis the state she sent came from (the "Basis" column in the table), but not what the state actually was, and Bob announces which basis he measured in. If Bob measured in the same basis as Alice used to prepare the state, he should have gotten the result in the "Value" column of the table. Alice and Bob keep the results for which they used the same basis and discard the other bits. In the absence of errors and eavesdropping, they should now have an identical string of bits, which can act as their private key.

Suppose Eve has been watching Alice and Bob perform this protocol. She may have even intercepted some of the qubits being sent from Alice to Bob. However, any measurement she makes on a qubit to attempt to determine what it is will inevitably disturb the quantum state. If she happens to choose the same basis to measure in as Bob, he will not notice - he will get the same result as her, and the same result as if she had not done anything. However, Eve doesn't know what basis Bob will choose to measure in. If Eve measures in the X basis and Bob measures in the Z basis (or vice-versa), Bob's result will now be random - even if the original state was prepared in the Z basis! That means that if Alice and Bob compare notes about the value of this bit, half the time, their bits will be different when they should be the same.

More general strategies Eve might use to learn the key run into the same problem. No matter what she does, she will inevitably introduce some errors into Bob's key compared to Alice. By comparing some randomly chosen subset or combination of the bits in their keys, Alice and Bob can learn if Eve is attempting to listen in. Of course, the communications channel between Alice and Bob is not likely to be perfect, so a number of errors will appear even if Eve is not listening, but if the number of errors is significantly greater than expected, Alice and Bob can be very confident Eve is the cause.

If they determine Eve is probably not present (or at least is not doing anything), Alice and Bob finish with some error correction protocol to eliminate any difference between their keys. The result will be a shared secret key, which they can then use for a one-time pad.

Quantum key distribution is perhaps the best-known example of an application of quantum mechanics to cryptography, but there are many others. For instance, quantum key distribution is closely related to a slightly stronger protocol called uncloneable encryption, which uses quantum states to send an encrypted classical message which cannot be read or even copied by Eve.

Back to Daniel Gottesman's home page

Updated: September 5, 2003