The BB84 Key Exchange Mechanism

The most commonly cited quantum key exchange mechanism is BB84,^[52] named after Charles Bennet and Gilles Brassard, who devised this scheme and presented it at the International Conference on Computers, Systems and Signal Processing in 1984. Over the years, this mechanism has been shown to be highly secure.^{[53] [54]}

In quantum cryptography, both quantum and classical information is exchanged: a quantum channel carries quantum traffic—the mega-qubit— and a classical channel for non-quantum or classical information.

The underlying quantum effect for the BB84 mechanism is based on ​Back-to-Back H Gates: The First Hint of Taming Randomness​. The first H gate takes the qubits and puts them in a blended state. The second H gate then puts the qubits back to their original states. In quantum cryptography, this concept is divvied up between the sender and receiver: the sender puts the qubit in a blended state by applying a H gate to the qubit. The receiver then applies another H gate on the blended qubits to recover the original states that the sender wants to convey. The complete state of the mega-qubit—the “content,” if you will—isn’t relevant to the security of the channel.

Of course, if eavesdroppers get hold of the blended qubits during their transmission from the sender to the receiver, then they too could simply apply the H gate to reveal the original message. Thus, to thwart any attempt by eavesdroppers to steal the message, the message is transmitted in two phases:

1. Establish trust between the sender and receiver.
2. Only after the security of the channel is assured, create a single-use key to encrypt and decrypt the message.

Notice that in every transmission, a secure channel between the sender and receiver is first assured before a single-use key is generated. Besides the mega-qubit itself being a cagey player, as was hinted at in the previous section and which we’ll explore in depth here, this two-step handshake between the sender and receiver virtually guarantees that the message is fully protected.

Next, we’ll describe the role of quantum computing in these two phases.

Establish Trust

In this phase, the sender and receiver confirm that they’re able to communicate securely without any malicious middlemen snooping around. The actual message to be transmitted isn’t used in this determination. The only publicly known information is that both parties use H gates for their work.

The trust is established by both the sender and receiver taking independent steps and then comparing their results, as follows:

Sender Creates a Random Quantum State

Sender creates a quantum state that’s a long random string of and qubits.

To illustrate the steps, we’ll use the following five-qubit quantum state expressed as a tensor product:

The resulting mega-qubit has a single qubelet combination.

The qubits are created by having a NOT gate operate on a qubit, as shown in the following circuit:

Sender Applies H Gate on Random Qubits

Next, the sender randomly selects some qubits and applies the H gate on them creating a mega-qubit with several qubelet combinations.

For example, if the H gate is applied to just the first, second, and last qubits, the quantum circuit is modified as shown in the following figure:

The quantum state created by this circuit is expressed as the following tensor product:

and are the actions of the H gate on the and qubits, as stated here:

Thus, by expanding the tensor product, the mega-qubit, , is:

This mega-qubit has eight qubelet combinations, with each combination having five qubelets, as shown below:

Mega-Qubit Sent Across Quantum Channel

The sender transmits the mega-qubit over the quantum channel to the receiver.

Picture this mega-qubit as a superposition of its qubelet combinations, drawn using familiar 0/1 bits to emphasize the idea that what’s being transmitted is actually a superposition of several binary strings as opposed to a single string in classical cryptography, as shown in this figure:

The negative qubelet combinations in the mega-qubit are drawn upside-down.

Receiver Applies H Gate on Random Qubits

The receiver gets the mega-qubit from the quantum channel and randomly selects qubits and applies the H gate.

Suppose the receiver selects the first, third, and last qubits and applies the H gate, as shown in the figure below:

By sheer chance, some qubits will have back-to-back H gates applied to them, while others won’t. In fact, if you put the sender’s and receiver’s circuits side by side, you’ll get the overall circuit as shown in the figure.

Only the first and last qubits have back-to-back H gates. Thus, when measured, these qubits will hold the original state set by the sender. Thus, c[0] records a 0 and c[4] logs a 1, matching those of the sender.

There’s no guarantee that the other qubits will match, although some may by chance. (For example, because of the random nature of how the blended quantum state of the third qubit collapses, c[2] will have roughly a 50% chance of matching the original state set by the sender.)

Overall Circuit Is Not a Single Program
	Although we’ve drawn the overall circuit in a single diagram, it doesn’t result in a single quantum program. It’s actually implemented as three separate parts: the sender’s circuit, the receiver’s circuit, and the quantum channel that transmits the qubits from sender to receiver.

Both Parties Compare Which Qubits Have Back-to-Back H Gates

Over an assumed “leaky” classical channel, where eavesdroppers can freely listen in, both the sender and receiver announce which qubits they applied H gates to. Thus, both the sender and receiver, as well as any eavesdroppers, will know which qubits match. Tellingly, though, the actual values of the qubits aren’t shared—just whether they were acted on by back-to-back H gates. So while the sender and receiver would know the values, eavesdroppers wouldn’t.

Given that both the sender and the receiver independently select the qubits to apply the H gate to, statistically we expect that about 50% of the time their choices will match. Thus, in practice, the sender starts by choosing a sufficiently long string of qubits so that the matched qubits are still adequate to make a secret key.

Optional Step for an Enhanced Seal of Trust

If you still need additional evidence that the quantum channel is free from eavesdroppers and middlemen with nefarious intent, the sender selects a subset of the matching qubits and declares their actual original quantum states over the leaky classical channel. Only if these states are identical to those measured by the receiver is the communication deemed safe and private.

Joe asks:

What Makes BB84 Tamper-Proof?

Quantum cryptography not only makes it hard to illegally tap messages but provides incontrovertible proof when tampered. The certificate of tamper-free messages comes directly from the principles of quantum mechanics. In classical cryptography, on the other hand, no one is the wiser when a hacker stealthily listens in.

In quantum cryptography, the odds stack up against evil-doers quickly:

• Firstly, there’s the mega-qubit itself. Even if someone managed to snatch it, they can’t simply read it like a classical string. They have to collapse the qubits. And since at least half of the qubits are in a blended state, the likelihood is tiny that every qubit would collapse to the original state at the same time.

• Secondly, the mega-qubit doesn’t contain the complete information. Even if you had full knowledge of the original quantum states, you still wouldn’t know the secret key. The actions of the receiver have to be factored in.

• If establishing an enhanced level of trust, the presence of an eavesdropper is easily detected. The moment an eavesdropper probes a qubit to inspect its state, the overall quantum state of the system is immediately altered so that there’s a mismatch when the sender and receiver compare their qubits.

Thus, the security of the quantum channel hinges on whether a match occurs when the H gate is applied to roughly half the qubits selected by both the sender and receiver. Remarkably, it’s only the total number that is relevant—not the quantum states of the qubits themselves nor which qubits are selected. In other words, trust is established by sharing minimal information, which in itself makes it more secure, since it reduces the attack surface, or the amount of content that can fall into wrong hands.

Create the Secret Key

Now that the sender and receiver have established a secure quantum channel, they each independently determine the secret key based on the matching qubits. The secret key itself is never sent across any channel, as it would be in classical cryptography.

Specifically, the secret key is derived as follows:

• Discard the qubits used for establishing the enhanced level of trust.

• Consider those qubits to which both the sender and receiver apply H gates:

  • Since sender generates the random string to initiate the negotiation, sender knows the quantum state of the matching qubits.

  • Receiver obtains the quantum state of the matching qubits from the value recorded in the classical register.

• Form the secret key by both sender and receiver concatenating the values of the matching qubits:

  • If the length of the key is shorter than the message to be sent, the key is repeated as many times as necessary.

  • Other schemes, such as reversing the bits in each repetition, could be used if both parties agree to them.

In the example, the sender and receiver apply H gates to the first and last qubits. The secret key is, thus, , assuming that the optional step isn’t needed in this transmission. The sender then encrypts the message using this key. And the receiver decrypts the message using the same key, even though the actual key is never sent across the channel.

The BB84 mechanism’s strength is, thus, multifold:

• Using mega-qubits to establish trust of the communication channel makes it foolproof—virtually impossible for any hacker to operate successfully. Moreover, any attempt to crack it is easily detectable, and no message is communicated till the channel is clear.

• The secret key itself is derived independently by both the sender and receiver and is never actually sent across the channel.

• Each new transmission uses a new secret key—the same key is never used again.

BB84 Using Entangled Qubits
	In the BB84 mechanism, each qubit is first operated on by the sender and then the receiver. Using entangled qubits, however, such as those described in ​Design a Teleporting Circuit​, the sender operates on one and the receiver works on the other entangled qubit.[55] This way, if any entangled qubit is illegitimately intercepted, the sender immediately knows and can stop the communication.