Quantum Key Distribution and BB84 Protocol
Quantum key distribution (QKD), very closely related to quantum cryptography, is a secure communication method that implements a cryptographic protocol involving components of quantum mechanics. Before discussing quantum cryptography, let’s talk about the basics of classical cryptography.
Classical Cryptography
Cryptography is a method of storing and transmitting data in a particular form so that only those for whom it is intended can read and process it. Classical cryptography has two major branches: secret or symmetric key cryptography and public or asymmetric key distribution.
Secret Key Cryptography
Two parties encrypt and decrypt their messages using the same shared key in secret-key cryptography. The two parties must somehow share the key ( physically, by email, or by letter) before using the key for secure communication. The downside is that you never know if someone stole the key while sharing it, which is a significant disadvantage of this cryptographic system.
Public Key Cryptography
In public-key cryptography, the key has two parts: public and secret. The data encrypted with the public key can only be decrypted with the private key, and the data encrypted with the private key can only be solved with the public key. The security of public-key cryptography is based on the unproven assumption about the difficulty of specific problems like integer factorization and the discrete logarithmic problem, which makes the system potentially vulnerable to improvements in computational power or the discovery of efficient algorithms. Indeed, there are algorithms to solve both integer factorization and discrete algorithm problems in polynomial time using quantum computers, like Shor’s algorithm.
Performance of Shor’s algorithm against the best classical factorizing algorithm
Quantum Cryptography
In contrast to classical cryptography, quantum key distribution and other protocols use quantum mechanics principles to provide an unconditionally secured public-key cryptosystem. These protocols can even detect the presence of an eavesdropper in the system who is attempting to learn the key.
The basic model of QKD consists of two parties, referred to as Alice and Bob, having access to both a quantum communication channel (which is private) that involves sharing a secret key by exchanging quantum particles and a classical communication channel (which is public) that involves basis reconciliation, error correction, and privacy amplification protocols. We assume that an eavesdropper, called Eve, can access both channels.
Now, let’s look at the concepts from quantum mechanics that make QKD so useful.
1. Heisenberg’s Uncertainty Principle: This principle states that in a quantum system, only one property of a pair of conjugate properties like position and momentum can be known with certainty (a plausible measurement of a particle’s position will disturb its speed). Quantum cryptography takes advantage of this by using the polarization of photons (as photons can be exchanged over fiber optic links) on different bases as the conjugate properties.
2. No Cloning Theorem: Indirectly following the last principle states that it is impossible to create identical copies of an unknown quantum state. Due to this, it is possible to find out if someone interrupted the quantum channel during the vital transmission.
3. Quantum Entanglement: Regardless of the distance, two quantum particles can entangle. When a particular property is measured in a particle, a correlated state of the property will appear on the other particle. Quantum teleportation uses entanglement for communication via a classical information channel. Entangled states are used as the basis of Eckert’s protocol, which we will talk about later.
The BB84 Protocol
In 1984, Charles Bennett and Gilles Brassard published a protocol based on Heisenberg’s uncertainty principle. The protocol is named BB84 after the authors’ names and the year it was published. It is one of the most prominent quantum protocols. All the other protocols based on HUP are considered variants of BB84.
In the BB84 protocol, Alice can transmit a random secret key to Bob by sending a string of photons with the private key encoded in their polarization. The no-cloning theorem guarantees that Eve cannot measure these photons and transmit them to Bob without disturbing the photon’s state in a detectable way.
The above is true, considering no error on the quantum channel. If the track is prone to error, Alice and Bob will not detect Eve’s presence all the time.
Photons as Qubits
Photons have quantum properties and can be transmitted through fiber optics and, therefore, can be used to encode the secret key. Let’s discuss how photons act as qubits and how we can operate them.
Photons are qubits for their state of polarization. Now, what is polarization? Before that, we must know what a lightwave is? A light wave is an electromagnetic wave where the plane occupied by the electric field is perpendicular to the plane occupied by the magnetic field. And the direction of propagation of the wave is orthogonal to these two planes.
When a light wave is polarized, it oscillates on a single plane. We can use polarizers and wave plates like half-wave plates and quarter-wave plates to polarize light.
There are two types of polarization: linear and elliptical. We don’t need to know about elliptical polarization here. Linear polarization has two states: rectilinear and diagonal. Again Rectilinear polarization is of two types: horizontal and vertical. And Diagonal polarization is also of two kinds: diagonal and anti-diagonal.
It is pretty easy to see that we have a two-level system in photon polarization. Thus, we can use one as |0⟩ and another as |1⟩. The two states of rectilinear polarization, horizontal and vertical, are represented as |H⟩ and |V⟩. The two states of diagonal polarization, diagonal and anti-diagonal, are described as |D⟩ and |A⟩. Now, we can consider |H⟩ and |V⟩ as |0⟩ and |1⟩ on the Z-axis and |D⟩ and |A⟩ as |+⟩ and |-⟩ along the X-axis.
Back to BB84
For the BB84 protocol, we define polarization of 0° on the rectilinear basis or 45° on the diagonal basis as binary 0. Similarly, a binary 1 can be 90° on a rectilinear basis and 135° on a diagonal basis.
In the first step, Alice and Bob communicate over a Quantum Channel. Alice randomly selects a string of bits and a string of bases (rectilinear or diagonal) of equal length. Then she transmits a photon for each bit with the corresponding polarization through an optical fiber (or other channels that allows sending photons) to Bob.
Bob randomly chooses a basis for each photon to measure its polarization. If Bob selects the same basis as Alice for a particular photon, he will correctly find the bit Alice wanted to share as he measured the same polarization. If he doesn’t guess correctly, he will get a random bit.
Alice and Bob communicate over a classical public channel in the second step. Bob tells Alice the bases he used to measure each photon. Alice informs Bob of the bases he guessed correctly to measure the encoded bits. After that, Alice and Bob remove the encoded and measured bits on different bases. Now, Alice and Bob have an identical bit-string, the shifted key.
To check the presence of Eve, Alice and Bob can share a few bits from the shifted key, which are supposed to be the same. Any disagreement in the compared bits will expose the presence of Eve.
Let’s look at an example where Eve managed to intercept some of the photons used in the quantum channel.
Due to the presence of Eve, despite having six identical bases, only one of Alice’s and Bob’s bits match. Which revealed the presence of Eve in the channel. In this case, Alice and Bob will have to transmit the photons again using another Quantum Channel.
Eve’s Escape Probability
Eve has no way to know the bases Alice used to encode the bits before Alice reveals her coding bases in the classical channel. So, Eve needs to guess the bases to measure the photons. If she measures incorrectly, information encoded on the other bases will be lost. Again Eve cannot replicate the states of the intercepted photons before sending them to Bob. Based on probability, if Eve eavesdrops on n bits, she will go undetected (3/4)^n times. In our case of 10 bits, Eve’s escape probability is 0.0563, which is very small.
BB84 Protocol Variants
SSP99 Protocol: The six-state protocol was proposed by Pasquinucci and Gisin in 1999. Instead of two orthogonal bases, it uses six orthogonal bases to encode the bits, which results in a lower escape probability for Eve.
Eckert91 Protocol: Eckert used a single photon source in this protocol that produces entangled photons. One of the photons from each entangled pair goes to Alice and the other one to Bob. Alice and Bob randomly select bases to measure the photons. They will get correlated results for each measurement, where they chose the same basis. After removing the photons measured on different bases, they will have a bit-string binary correlated to each other. Knowing if the entangled states were inversely or directly related, Alice and Bob can convert their key to the shifted key. They can measure a photon (they measured on a different basis) on a third basis, and with that result, they can test Bell’s Inequality to check Eve’s presence. If the inequality contains, someone may have eavesdropped on the quantum channel.
B92 Protocol: In 1992, Charles Bennett developed a simplified version of the BB84 protocol where only two states are used in encoding bits in photons. Binary 0 is encoded as 0° on a rectilinear basis, and binary 1 as 45° on a diagonal basis. Here the bits themselves dictate the bases Alice must choose to encode them. Bob still selects bases randomly to measure the polarized photons. If he chooses the wrong basis, he will not get any measurement this time.
Weaknesses of Quantum Cryptography
Quantum cryptography is unconditionally secured because no assumptions are made about Eve’s inability to compute complex mathematical problems but rather about her failure to violate the principles of quantum mechanics. However, these protocols are vulnerable to a man-in-the-middle attack where Eve pretends to be Bob or Alice. The man-in-the-middle attack cannot prevent such attacks without Alice and Bob authenticating each other first. Moreover, quantum cryptography is not perfectly secured when used with faulty equipment and in a noisy environment (which may lead to bit-flip, phase errors, or measurement errors). In an error-prone quantum channel, information reconciliation and privacy amplification can be used to develop a secured key.
Information reconciliation is carried out in the classical channel to ensure both the shifted keys are identical. It is conducted so Eve cannot intercept much information about each key. The most common protocol used for information reconciliation is the cascade protocol which operates in several rounds. During each round, both the keys are divided into small blocks, and parities of those blocks are compared. If there is any difference in inequality, a binary search is performed to find and correct the error.
If the parity of a former round was correct but had an error, the error can be found in the next round and can be corrected as before. And the whole process is repeated recursively. After one round, Alice and Bob again reorder their key and start another round. After multiple rounds, Alice and Bob get an identical key with high probability.
Privacy amplification is followed by information reconciliation, where the partial information about the key that Eve might have collected from the quantum or the classical channel is reduced. In Privacy amplification, a shorter key is produced using Alice and Bob’s key so that Eve has negligible information about the new key. Privacy amplification uses a publicly known set of functions that take the old key as input and outputs a new key of short length. The shortening of the new key depends on how much information Eve has gained about the old key.
Due to hardware limitations, we cannot implement the protocol perfectly. In a natural system, as we cannot produce and detect single photons properly, we often use a laser to make a small amount of coherent light, which creates the chance of a PNS (Photon Number Splitting) attack where Eve splits off a small number of photons from each bit-transmission for measurement and allows the rest to pass on to Bob. PNS attacks let Eve measure the photons without disturbing Bob’s photon measurement.
To prevent this, we use the decoy-state technique. Here, Alice transmits each qubit using a random intensity. After transmission, Alice announces publicly the intensity level she used to send each qubit. A PNS attack will reduce the power of the qubits at Bob’s end. Bob can detect the PNS attack by monitoring the bit error rate associated with each intensity level.
Though the article described a lot about quantum cryptography, we have barely scratched the surface. Research is still going on to develop advanced protocols and to increase the security of the past ones. But until now, all the protocols developed are variants of the BB84 protocol. Probably (we hope that shortly), more and more protocols will be developed that will provide safer and safer options. But until that time, this is what we have.
Stay tuned with Quantum Untangled for more articles about quantum computing and everything related!
