Quantum Key Distribution (QKD) and the BB84 Protocol: Securing Communications in the Quantum Era

I often write about the risks quantum computing poses to cryptography and cybersecurity. However, in some ways, quantum mechanics also provides an amazing solution for some of these challenges—a solution that, as of now, we don’t even have the slightest idea if and how it could be broken. Let me illustrate this with Quantum Key Distribution (QKD), exemplified by the BB84 protocol that initiated it.

Quantum Key Distribution (QKD) represents a radical advancement in secure communication, utilizing principles from quantum mechanics to distribute cryptographic keys with guaranteed security. Unlike classical encryption, whose security often relies on the computational difficulty of certain mathematical problems (see “What’s the Deal with Quantum Computing: Simple Introduction” for an introduction), QKD’s security is based on the laws of physics, which are, as far as we know, unbreakable.

Cryptography Background

Knowing my audience, I’ll keep this brief. I want to emphasize one aspect of cryptography, though—our professional lives would have been much simpler if we could have solely relied on symmetric cryptography.

Secret or Symmetric Key Cryptography

In symmetric key cryptography, two parties, typically referred to as Alice and Bob, encrypt and decrypt their messages using the same shared key.

According to the Vernam theorem, a symmetric encryption technique can ensure absolute secrecy if the a random, one-time key is used and if the key is as long as the message itself. The Vernam cipher, developed by Gilbert Vernam in 1917, embodies this principle. He documented it in his patent application. The Vernam theorem underpins the absolute security of this encryption method, stating that if the key is truly random, at least as long as the message, and used only once, the resulting ciphertext will be completely secure and unbreakable. This is because every possible decryption is equally likely, making it impossible to determine which one might be the correct plaintext without knowledge of the key. This has been mathematically proven to be unbreakable when all conditions are met.

Unlike the rest of cryptography, the security of absolutely secret symmetric encryption is not derived from the complexity of the algorithm but from the randomness of the key and its single use.

However, in the real world, the practical application of this method is limited by the difficulty of securely exchanging keys. Whichever method and channel are used for the key exchange, Alice and Bob can never be sure that someone did not intercept the key while sharing it.

Asymmetric or Public-Key Cryptography

The primary reason we developed and rely heavily on the much more complex asymmetric or public-key cryptography was because we couldn’t ensure a reliable sharing of symmetric keys between parties.

In public-key cryptography, the key has two parts: a public and a private component. The fundamental principle here is that data encrypted with the public key can only be decrypted with its corresponding private key, and data encrypted with the private key can only be decrypted with the public key. This dual-key system forms the backbone of secure digital communications, allowing users to exchange information securely over unsecured channels.

The security of public-key cryptography depends on the computational difficulty of problems like integer factorization and the discrete logarithm. These problems are currently infeasible to solve efficiently with classical computers, which provides the security margin necessary to protect data. However, this security is predicated on the assumption that no significant advances in computational methods or computational power will make these problems easy to solve suddenly.

Quantum computers operate on principles fundamentally different from classical computers, using quantum bits (qubits) that can exist in multiple states simultaneously. This capability allows quantum algorithms, such as Shor’s algorithm, to potentially solve integer factorization and discrete logarithm problems in polynomial time, dramatically faster than is possible with classical computers. In seconds vs billions of years on classical computers. If realized at a practical scale, quantum computing could undermine the public-key encryption method. Note that it would not impact the symmetric key cryptography at all.

Imagine how much simpler our life as cybersecurity professionals would be if we didn’t have to deal with all the complexities of asymmetric cryptography. Well, I have good news. That’s exactly what quantum cryptography promises—a return to simple and easy-to-manage symmetric cryptography while ensuring absolute secrecy in key sharing. Even against the advent of quantum decryption that might break the contemporary public-key cryptography over night.

Quantum Theoretical Underpinning

Heisenberg Uncertainty Principle

The Heisenberg Uncertainty Principle is a fundamental concept in quantum mechanics, stating that it’s impossible to simultaneously know both the position and momentum of a particle with absolute certainty. This principle, introduced by Werner Heisenberg in 1927, underscores a fundamental limit on precision measurements at the quantum level. (Original paper in German is available here, and a translation provided by NASA is available here).

The principle essentially indicates that the more precisely one property (such as position) is measured, the less precisely the other property (such as momentum) can be known. This is not due to technological limitations but is a fundamental property of the universe at the quantum scale. Therefore any attempt to measure or clone a quantum state would disturb it due to the uncertainty principle.

This principle has profound implications for quantum mechanics and quantum computing. For example, it supports the no-cloning theorem.

No-Cloning Theorem

The no-cloning theorem provides a theoretical foundation for the security of quantum key distribution (QKD) protocols. In QKD, the no-cloning theorem ensures that any attempt by an eavesdropper to intercept and measure the quantum keys will inevitably introduce detectable errors in the system, alerting the legitimate users to the presence of an eavesdropper.

The no-cloning theorem was initially introduced in 1970 by James Park in his paper “The Concept of Transition in Quantum Mechanics.” He introduced the idea that quantum information encoded in an unknown state cannot be perfectly copied or cloned. The concept was later formalized and became widely recognized through the works of William Wootters, Wojciech Zurek and their 1982 paper “A single quantum cannot be cloned“, and independently Dennis Dieks’s paper “Communication by EPR devices“ published the same year.

The formal theorem states that it is impossible to create an identical copy of an arbitrary unknown quantum state. This arises from the linearity of quantum mechanics and the preservation of quantum information. The concepts state:

• Quantum operations are unitary, meaning they preserve the length of the state vectors in the system. This unitarity, coupled with the superposition principle, implies that a general quantum state cannot be exactly copied without affecting the original state.
• The no-cloning theorem also highlights the impossibility of measuring quantum states without disturbing them (due to the Heisenberg Uncertainty Principle among other factors), reinforcing the idea that quantum information is fundamentally different from classical information.

This difference from classical information is the key. The state of a classical system can always be read by making appropriate measurements. No classical equivalent to the quantum no-cloning theorem exists. If the information be read without disturbing it, then classical information can also always be copied.

Implications of No-Cloning Theorem for Quantum Key Distribution (QKD)

The significance of the no-cloning theorem for Quantum Key Distribution (QKD) is profound:

1. Security of Quantum Communication: The no-cloning theorem ensures the security of quantum communication channels. In QKD systems the key information is encoded in the quantum states of particles (often photons). Because these states cannot be perfectly copied without detection due to the no-cloning theorem, any attempt by an eavesdropper to intercept and measure these states will inevitably introduce errors that can be detected by the communicating parties. This disturbance alerts the legitimate users to the presence of the eavesdropper.
2. Ensuring Eavesdropper Detection: In the BB84 protocol, for example, the security of the key distribution process is maintained by randomly selecting polarization bases to encode and decode the transmitted photons. An eavesdropper, not knowing the polarization basis, will likely choose the wrong basis to measure the photons, thereby altering their quantum state. This alteration, due to the no-cloning theorem, can be detected by comparing measurement results over a public channel for a subset of the key.
3. Development of Secure Communication Systems: The theoretical underpinning provided by the no-cloning theorem has encouraged the development of various secure communication systems based on quantum mechanics principles. It assures that the fundamental approach of QKD using quantum mechanics is secure against any future advancements in technology or computational power that might undermine classical cryptographic systems.

The integration of the no-cloning theorem into the design and analysis of quantum cryptographic systems gives us a whole new approach to cryptography, one that we couldn’t have even conceived in classical systems. This makes practical protocols like BB84 not only fascinating from a scientific standpoint but also critically important for future-proofing secure communications.

The Concept of QKD

At its core, QKD involves two parties, Alice and Bob, sharing a secret key generated through the exchange of quantum states, typically photons. These quantum states are susceptible to observation, but any attempt to eavesdrop or measure these quantum states causes detectable disturbances due to the Heisenberg Uncertainty Principle and No-Cloning theorem. This ensures that any interception attempt will alter the state of the qubits, alerting Alice and Bob to the presence of an eavesdropper.

BB84: The First Quantum Key Distribution Protocol

In 1984, at the International Conference on Computers, Systems & Signal Processing in Bangalore, India, Charles Bennett and Gilles Brassard introduced a protocol based on Heisenberg’s uncertainty principle and no-cloning theorem. Their original paper is “Quantum cryptography: Public key distribution and coin tossing.” The protocol is named BB84 after the authors’ names and the year it was published. BB84 was the first QKD protocol and remains one of the most widely studied and implemented. It laid the foundational framework for how secure communication could be achieved using quantum mechanics. While this is just the tip of the iceberg in the field of secure communication using quantum networks, understanding this protocol gives us a peek at the power of quantum cryptography and quantum networks.

Breakdown of the BB84 Protocol

At the beginning of the BB84 protocol, Alice and Bob set up two distinct communication paths: a quantum channel, through which Alice sends polarized photons, and a classical channel, used by Bob to relay specific details of his received messages back to Alice for verification.

To prepare, Alice configures her apparatus to isolate individual photons from a polarized light source, while Bob equips his end with a device capable of detecting single photons. Once everything is in place, Alice creates two random sequences of bits. One sequence is used to generate the secret key, and the other determines the polarization bases—either rectilinear or diagonal—used for each photon she sends. She then transmit these photons to Bob one at a time.

As Bob receives the photons, he generates his own random sequence of bases to measure each incoming photon. If his chosen measuring basis aligns with the photon’s original polarization basis set by Alice, Bob can accurately determine the encoded bit. However, if Bob’s chosen basis doesn’t match the photon’s polarization, the act of measurement forces the photon to realign itself randomly according to Bob’s basis. This misalignment effectively erases the original information.

In the next stage of the BB84 protocol, after receiving enough photons, Bob selects a random subset of this shared information to compare with Alice. Original BB84 protocol recommends to use a subset of one third. Bob communicates over a public classical channel which bases he used to measure each photon, but not the results of the measurements.

Alice then compares these bases with the ones she used to encode the photons. If Alice confirms these, then the bits used for the comparison are removed from the shared code and the remaining shared bits become Alice and Bob’s secret key. They will then use this key as a one-time pad to send an encrypted message between the parties.

The process is then repeated for every message that Alice sends to Bob.

And now we are getting to the no-cloning theorem. As this process keeps repeating, Alice and Bob keep measuring the error rate between compared bits. Everything else being the same, the error rate should stay consistent.

If they start receiving a significantly higher error rate in the shared subset of bits, this could indicate a presence of an eavesdropper, commonly referred to as Eve. In a scenario where Eve intercepts and measures the photons before they reach Bob (known as an intercept-resend attack), she would inadvertently introduces errors. 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. Every time Eve would randomly chose an incorrect basis to measure a photon, it would alter the photon’s state, due to the principles mentioned above, and it would reach Bob in a randomized polarization. Now Bob would start receiving a much higher error rate than before Eve’s eavesdropping. The probability that Bob detects an alteration by Eve accumulates through multiple layers of chance: there’s a 50% chance that Eve’s intervention changes the photon’s state, and another 50% chance that Bob uses the matching basis to measure such a photon, leading to an overall 25% chance that any single bit altered by Eve is detected during their verification process. This layered probability is critical for maintaining the integrity and security of their quantum communication.

Security and Practical Implementation

BB84 continues to being improved upon by numerous researchers.

Theoretically, QKD offers perfect secrecy under the laws of quantum mechanics. However, practical implementations of QKD systems must contend with technical imperfections and potential side-channel attacks. The security of a real QKD system, thus, relies heavily on how well these issues are managed.

Current challenges in QKD include extending the distance over which keys can be securely distributed and improving the rate at which keys can be generated. Recent advancements include the development of satellite-based QKD to overcome distance limitations and various technological improvements to increase throughput and reliability.

Conclusion

Quantum Key Distribution, exemplified by the BB84 protocol, offers a promising solution to secure communications against the potential threats posed by quantum computing. As quantum technology continues to evolve, so too will the strategies to exploit its properties, pushing the boundaries of secure communication further into the quantum realm. The ongoing development and refinement of QKD technologies will be critical in maintaining the confidentiality and integrity of global communications.