Hello everyone! Welcome to a new blog post. In this one, we will discuss the notion of quantum key distribution and its first kind scheme: the BB84 protocol.
Key Exchange
What is it and why is it important?
Key exchange is the process of securely sharing cryptographic keys between parties who wish to communicate securely over an insecure channel, such as the internet. These keys are used to encrypt and decrypt messages, ensuring that only the intended recipients can read the information.
Key exchange is important because it forms the foundation of secure communication in various contexts, including online banking, e-commerce transactions, secure messaging applications, and more. Without a secure method of exchanging keys, sensitive information could be intercepted and read by unauthorized parties, leading to privacy breaches, financial losses, and other serious consequences.
By securely exchanging keys, parties can establish a shared secret that enables them to communicate confidentially and authenticate each other's identities. This ensures the confidentiality, integrity, and authenticity of the transmitted data, safeguarding it from eavesdroppers and malicious attackers.
Diffie-Hellman Key Exchange Algorithm
Diffie-Hellman (DH) key exchange is a mathematical method of securely exchanging cryptographic keys over a public channel and named after Whitfield Diffie and Martin Hellman.
Traditionally, secure encrypted communication required that they first exchange keys by some secure physical ways like papers. The Diffie-Hellman key exchange method allows two parties with no prior knowledge of each other to establish a shared secret key over an insecure channel.
How it works?
The original implementation uses a multiplicative group structure over integers modulo $p$, where $p$ is a prime and $g$ is a primitive root modulo $p$.
Alice and Bob publicly agree to use a modulus $p$ and base $g$.
Alice chooses a private integer $a$, then sends Bob \(A = g^a \ mod \ p\).
Bob chooses a private integer $b$, then sends Alice \(B = g^b \ mod \ p\).
Alice computes \(s = B^a \ mod \ p\).
Bob computes \(s = A^b \ mod \ p\).
Alice and Bob now share a secret, the number $s$.
Example
Let \(p = 23\) and \(g = 5\).
Alice chooses a secret \(a = 4\) and sends Bob \(A = 5^4 \ mod \ 23 = 4\).
Bob chooses a secret \(b = 3\) and sends Alice \(B = 5^3 \ mod \ 23 = 10\).
Alice computes \(s = 10^4 \ mod \ 23 = 18.\)
Bob computes \(s = 4^3 \ mod \ 23 = 18\).
Alice and Bob have the same secret: $18$.
What's wrong with DH?
The security of traditional Diffie-Hellman key exchange relies on the difficulty of computing discrete logarithms, which is the process of finding the exponent in the equation \(g^x = y \ mod \ p\). However, quantum computers have the potential to efficiently solve the discrete logarithm problem using algorithms like Shor's algorithm. So traditional Diffie-Hellman key exchange is not quantum-resistant.
Introduction to Quantum Mechanics
What is it?
Quantum mechanics is a branch of physics that dealing with the behavior of matter and light on the atomic and subatomic scale. It aims to explain and understand the characteristics of molecules and atoms, as well as their components—electrons, protons, neutrons, and other particles like quarks and gluons. These characteristics encompass how these particles interact with each other and with electromagnetic radiation, such as light, X-rays, and gamma rays.
Postulates of Quantum Mechanics
The state of a quantum system is completely described by a wave function, denoted as \(\psi(x, t)\), which encodes all the probabilistic information about the system's properties.
The evolution over time of the wave function of a quantum system is determined by the Schrödinger equation, a linear partial differential equation:
$$i \hbar \frac{\partial \psi}{\partial t} = \left[ - \frac{\hbar^2}{2m} \frac{\partial^2}{\partial x^2} + V(x) \right] \psi.$$
- Physical quantities, or observables, such as energy, position, and momentum, are represented by operators in quantum mechanics. These operators act on the wave function to extract physical information:
$$\hat{H} \psi = E\psi.$$
- The act of measurement affects the system being measured. The only possible outcome of measuring a quantifiable property (observable) of a quantum system is one of the eigenvalues of the corresponding operator. Upon measurement, the wave function of the system collapses to an eigenstate associated with the eigenvalue.
Heisenberg's Uncertainty Principle
One of the most famous aspects of quantum mechanics is the Heisenberg Uncertainty Principle. Formulated by Werner Heisenberg in 1927, this principle states that certain pairs of physical properties, like position and momentum, cannot both be precisely measured or known simultaneously. The more precisely one property is measured, the less precisely the other can be controlled or known. This is not due to faults in measurement instruments, but rather a fundamental property of quantum systems.
Mathematically, the principle is expressed as:
$$\Delta x \Delta p \geq \frac{\hbar}{2}$$
where \(\Delta x\) and \(\Delta p\) are the standard deviations of position and momentum, respectively, and \(\hbar\) (h-bar) is the reduced Planck constant.
This principle has very significant implications for the nature of reality and our understanding of the universe, indicating a fundamental limit to what we can know about the properties of particles.
These concepts of quantum mechanics are not just theoretical curiosities but have practical applications, particularly in the field of quantum computing and quantum cryptography, where they enable technologies that would be impossible under classical physics.
Quantum Key Distribution
What is it?
Quantum Key Distribution (QKD) is an unusual approach in secure communication, utilizing principles of quantum mechanics to generate and share cryptographic keys between parties with guaranteed security. The underlying strength of QKD lies in the fundamental aspects of quantum mechanics, such as the Heisenberg Uncertainty Principle and the no-cloning theorem..
QKD allows two parties to produce a shared random secret key known only to them, which can then be used to encrypt and decrypt messages. What makes QKD unique from traditional cryptographic systems is its ability to alert both parties to the presence of any third party trying to gain knowledge of the key. This security feature stems from the principle that measuring quantum data invariably alters it. Thus, an eavesdropper trying to intercept the key would cause detectable disturbances in the system, alerting the legitimate parties to the breach.
It is worth noting that quantum key distribution is used to generate and distribute only a key, not to send / receive any message data. But such a key can be used within any chosen encryption scheme.
The BB84 Protocol
The BB84 protocol, proposed in 1984 by Charles Bennett and Gilles Brassard, is the first and most well-known Quantum Key Distribution scheme. Its security relies on two fundamental principles of quantum mechanics:
The impossibility of measuring a quantum state without disturbing it (Heisenberg Uncertainty Principle).
The no-cloning theorem, which states that it is impossible to create an identical copy of an unknown quantum state.
The protocol allows two parties, commonly called Alice and Bob, to generate a shared random key in a way that any eavesdropping attempt by an adversary (Eve) is detectable.
Step 1: Preparation and Transmission
Alice prepares a sequence of quantum bits (qubits), each encoded using one of two bases:
$$|+⟩ = \frac{|0⟩ + |1⟩}{\sqrt{2}}, \quad |−⟩ = \frac{|0⟩ - |1⟩}{\sqrt{2}}.$$
For each bit in a randomly generated string, Alice chooses (a) a random bit value (0 or 1), and (b) a random basis (rectilinear or diagonal). She then sends the corresponding qubits to Bob through a quantum channel.
Step 2: Measurement
For each received qubit, Bob also chooses a random basis (rectilinear or diagonal) to measure it. Because his choice might not match Alice’s, some measurements will be “wrong” (i.e., produce random results). Importantly, Bob does not inform Alice of his measurement results yet—only the bases he used.
Step 3: Basis Reconciliation
After the quantum transmission is complete, Alice and Bob communicate over a classical public channel (which can be eavesdropped on, but not modified).
They then discard all bits where their bases were different. The remaining bits (where both chose the same basis) form the raw key.
Step 4: Eavesdropping Detection
To check for eavesdropping, Alice and Bob publicly compare a randomly chosen subset of their raw key. If the error rate is above a certain threshold, they assume Eve has intercepted the qubits (since her measurements would have disturbed the states) and abort the protocol.
If the error rate is below the threshold, they proceed, discarding the revealed bits and keeping the rest.
Step 5: Error Correction and Privacy Amplification
The raw key may still contain a small number of errors due to noise in the quantum channel. Alice and Bob use classical error correction protocols to reconcile their keys. Finally, they apply privacy amplification techniques to reduce Eve’s possible knowledge to an arbitrarily small amount, yielding the final secret key.
This final key can then be used in any symmetric encryption scheme (e.g., One-Time Pad or AES), with the guarantee that any eavesdropping attempt would have been noticed during the protocol.
Conclusion
Quantum Key Distribution represents a fundamental shift in how we think about secure communication. Rather than relying on computational assumptions like the hardness of discrete logarithms or factoring, QKD leverages the laws of physics to guarantee security. It is also worth noting that it is more of a complementary method instead of a replacement.
The BB84 protocol is a particularly elegant demonstration of this idea: even if an adversary has infinite computational power, they cannot extract information about the key without introducing detectable disturbances. While real-world implementation still faces technical challenges—such as channel noise, distance limitations, and cost—QKD systems are already being deployed in some specialized networks around the world.
As quantum computers advance and threaten traditional public-key cryptosystems, QKD provides a complementary path forward.
