Quantum Cryptography and Cybersecurity
6.S089 Final Project
Tina Zhang, Maria Santos, and Corina Arimond
We are researching quantum cryptography and cybersecurity. We will discuss the current state of cybersecurity, how quantum computing can threaten current cybersecurity, and how it can improve cybersecurity moving forward. In particular, we will delve into the use of Quantum Key Distribution (QKD) and Quantum Cryptography (QC) to secure National Security Systems (NSS) transmissions as well as requirements for a secure QKD protocol and limitations to overcome. Additionally, we will explore Lattice-Based Cryptography, a post-quantum cryptography field, and discuss the societal implications of quantum computing changing cybersecurity.
Classical Cryptography
Cryptography is a method of storing/transmitting data in a form such that only the intended recipient can read and process it. Classical cryptography has two major branches: secret and public.
With secret cryptography, two parties encrypt and decrypt messages using the same shared key. The key can be shared physically, by email, or by letter. One of the most significant disadvantages is that the key can be stolen during this sharing process.
In public cryptography, the key has two parts — public and secret. Data encrypted with the public key can only be decrypted with the private key and vice versa. Although the key won’t be stolen during sharing as in secret cryptography, the security of public-key cryptography is based on the assumption that problems like integer factorization and the discrete logarithmic problem are incredibly difficult to solve with classical computers. This makes the system vulnerable to improvements in computational power or the discovery of more efficient algorithms.
What is Cryptography Used For?
The first recorded use of correspondence through cryptography was by the Spartans in 400 BC. They used a cipher device called the scytale for secret communication between military commanders.
Cryptography has evolved much since then and is now used primarily online to encrypt bank cards, computer passwords, digital signatures, cryptocurrency, and network communication. It is also behind MIT’s Kerberos system, which uses a variety of cipher algorithms to protect data.
Cryptography also plays a large role in cybersecurity. Many companies use cryptography for “Bring Your Own Device” policies, securing sensitive emails, encrypting databases, and protecting sensitive company data. Agencies in the federal government that handle sensitive personal data use cryptographic modules as well.
Is Quantum Computing a Threat?
Quantum computing is a double-edged sword when it comes to cybersecurity. On the one hand, expanded computing power will create new opportunities to improve cybersecurity; on the other hand, it could create serious exposures.
Public cryptography, for example, is based on difficult mathematical problems, such as factoring large numbers, which can take thousands of years on today’s most powerful supercomputers. Peter Shor at MIT demonstrated the same problem could be solved in mere days or hours on a large-scale quantum computer.
Secret cryptography is also in danger. Grover’s algorithm, which uses quantum concepts to search databases very quickly, will improve brute-force attacks required to break secret encryption.
However, most experts agree that the benefits far outweigh potential risks, and that quantum cybersecurity can provide better opportunities to safeguard critical and personal data.
Quantum Cryptography
Quantum cryptography, also known as quantum encryption, refers to various cybersecurity methods for encrypting and transmitting secure data based on the naturally occurring and immutable laws of quantum mechanics. Although it is still in its early stages, quantum encryption has a potential to be far more secure than previous types of cryptographic algorithms and is even unhackable in theory. In other words, quantum cryptography aims to use the unique properties of quantum mechanics to achieve cryptographic tasks with higher security than classical cryptographic methods.
Introduction to QKD
Quantum Key Distribution (QKD) is a well-known example of quantum cryptography (QC), and it illustrates how quantum principles can be applied to enhance the security of cryptographic key distribution in communication systems. It is an established protocol known for its guaranteed security. QKD allows for the creation of private key bits between two parties over a public channel. Subsequently these key bits are employed in classical private key cryptosystems to secure communication between the parties.
In contrast to classical cryptography, QKD uses quantum mechanics principles to provide an unconditionally secure public-key cryptosystem. These protocols can detect the presence of an eavesdropper in the system who is attempting to learn the key.
The only requirement for the QKD protocol is that qubits can be communicated over the public channel with an error rate lower than a certain threshold. The security of the generated key is guaranteed by the inherent properties of quantum information, which relies solely on the accuracy of fundamental laws of physics.
An Overview of QKD
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.
The idea behind QKD is that Eve cannot gain any information from the qubits transmitted from Alice to Bob without disturbing their state. Firstly, due to the no-cloning theorem, Eve cannot clone Alice’s qubit. Moreover, information gain implies disturbance. Therefore, in any attempt to distinguish between two non-orthogonal quantum states, information gain is only possible at the expense of introducing disturbance to the signal.
Key Ideas from Quantum Mechanics in QKD
As opposed to classical cryptography that is based on mathematics, quantum cryptography is built on the laws of physics. Specifically, quantum cryptography relies on the unique principles of quantum mechanics.
1. Heisenberg’s Uncertainty Principle
This principle states that in a quantum system, it is impossible to know precisely both properties of a conjugate pair, such as position and momentum, simultaneously. This is because attempting to measure one property, like a particle’s position, will disturb its speed. Quantum cryptography takes advantage of this principle by using the polarization of photons (as photons can be exchanged over fiber optic links) on different bases as the conjugate properties.
In other words, quantum cryptography utilizes the way photons are oriented, or polarized, to secure communication. The photons are essentially “messengers”, and their polarization is analogous to the “secret code” they carry. By shifting the direction of polarization in certain ways, it allows us to create a secure language for communication. As a result, even if someone tries to intercept the message, they would disturb the polarization, which would alert us to potential eavesdropping and keeping our communication safe.
2. No Cloning Theorem
The non-cloning theorem states that it is impossible to create identical copies of an unknown quantum state. It arises from fundamental concepts of quantum mechanics, in particular the superposition principle and the collapse of the wave function upon measurement. The no-cloning theorem implies that if you attempt to make an exact copy of an arbitrary quantum state, you would need to know the state precisely, so you have to measure it. However, measurement disturbs the quantum state, and due to the no-cloning theorem, it would be impossible to create an exact duplicate. Due to the no-cloning theorem, 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.
Quantum entanglement suggests that particles are inherently uncertain. This means that on a quantum level, particles can simultaneously exist in more than one place or more than one state of being at the same time, and it is impossible to predict their exact quantum state.
4. Holevo Bound
The Holevo bound is a useful upper bound on the accessible information that plays an important role in many applications of quantum information theory. It sets a limit on the amount of classical information that can be reliably extracted from a quantum system. In the context of quantum cryptography, the bound is often used to quantify the information that can be transmitted securely between two parties who share entangled quantum states.
Implementing QKD
Before exploring the implementation of QKD, let’s examine the fundamental properties of photons and understand why they are excellent candidates for use as qubits.
Photons as Qubits
Photons have quantum properties and can be transmitted through fiber optics and, therefore, can be used to encode the secret key. We will discuss how photons act as qubits and how we can operate them.
Photons are qubits for their state of polarization. To understand polarization, it is essential to first grasp the nature of a light wave. 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. The wave’s direction of propagation is orthogonal to these planes. Polarization occurs when a light wave oscillates on a single plane. We can use polarizers such as half-wave plates and quarter-wave plates to polarize light.
Furthermore, there are two types of polarization: linear and elliptical. Linear polarization plays an essential role in operating photons that act as qubits. Linear polarization has two states: rectilinear, which could have horizontal and vertical types, and diagonal, which could have diagonal and anti-diagonal types.
As a result, we have a two-level system in photon polarization. Therefore, 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.
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 published. The BB84 protocol is one of the most prominent quantum protocols, and all 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. This is true considering there is 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.
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, either 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.
In the second step, Alice and Bob communicate over a classical public channel. Bob tells Alice the bases he used to measure each photon, and 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, which is 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 discrepancy in the compared bits would reveal Eve’s interference. Consider the example below 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 reveals 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. Consequently, Eve needs to guess the bases to measure the photons. Any incorrect measurements would result in the loss of information encoded in other bases. Moreover, 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 example of 10 bits, Eve’s escape probability is 0.0563, which is very small.
BB84 Protocol Variants
1. SSP99 Protocol
The SSP99 protocol is a six-state protocol proposed by Pasquinucci and Gisin in 1999. It uses six orthogonal bases instead of two to encode the bits, which results in a lower escape probability for Eve.
2. Eckert91 Protocol
In this protocol, Eckert used a single photon source to produce 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 and will get correlated results for each measurement when they choose the same basis. After removing the photons measured on different bases, they will obtain a binary bit-string 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 then measure a photon (originally measured on a different basis) using 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.
3. B92 Protocol
Charles Bennett created a simplified version of the BB84 protocol in 1992 where only two states are used in encoding bits in photons. In the B92 protocol, 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 happens to choose the incorrect basis, he won’t obtain any measurement results.
Weaknesses of Quantum Cryptography
Quantum key distribution utilizes the unique properties of quantum mechanical systems to generate and distribute cryptographic keying material using special purpose technology. Quantum cryptography uses the same physics principles and similar technology to communicate over a dedicated communications link. Published theories suggest that physics allows QKD or QC to detect the presence of an eavesdropper, a feature not provided in standard cryptography.
Quantum cryptography is unconditionally secured if no assumptions are made about Eve’s inability to compute complex mathematical problems but rather about her inability to violate the principles of quantum mechanics. However, these protocols are susceptible to a man-in-the-middle attack, in which Eve pretends to be either Bob or Alice. To prevent such attacks, authentication between Alice and Bob is crucial before proceeding. Moreover, quantum cryptography is not perfectly secured when using faulty equipment and in a noisy environment, as it could lead to bit-flip, phase errors, or measurement errors. Consequently, in an error-prone quantum channel, information reconciliation and privacy amplification can be used to develop a secured key.
Information Reconciliation
Information reconciliation is carried out in the classical channel to ensure that both the shifted keys match. This process is implemented to minimize the potential interception of key information by Eve. The most common protocol used for information reconciliation is the cascade protocol, which operates across multiple rounds. In each round, the keys are divided into small blocks, and parities of those blocks are compared. If any difference in inequality is detected, 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 subsequent round and can be corrected following the same procedure. Moreover, the whole process is repeated recursively. After completing one round, Alice and Bob rearrange their key once more and start another round. After multiple rounds, there is a high probability that Alice and Bob will obtain identical keys.
Privacy Amplification
Privacy amplification is followed by information reconciliation. This process reduces any partial information that Eve may have acquired from either the quantum or classical channels. In privacy amplification, a shorter key is produced using Alice and Bob’s key to ensure that Eve has minimal information about the new key. Privacy amplification utilizes a publicly known set of functions that take the old key as an input and outputs a new key with reduced length. The extent of shortening in the new key is dependent on the amount of information Eve may have gained about the old key.
However, due to hardware limitations, we cannot implement the protocol perfectly. In a natural system, since we cannot produce and detect single photons properly, we often use a laser to make a small amount of coherent light. This process introduces the risk of a Photon Number Splitting (PNS) attack, where Eve splits off a small number of photons from each bit-transmission for measurement and allows the remaining photons to pass on to Bob. PNS attacks allow Eve to measure the photons without disturbing Bob’s photon measurement.
To minimize the likelihood of PNS attacks, we can use the decoy-state technique. In this approach, Alice transmits each qubit with a random intensity. Subsequently, after transmission, Alice publicly announces the intensity level she used to send each qubit. If a PNS attack occurs, it will reduce the power of the qubits at Bob’s end. Bob can then detect the PNS attack by monitoring the bit error rate associated with each intensity level.
Limitations of QKD and QC
Quantum key distribution and Quantum cryptography vendors as well as the media sometimes make ambitious claims based on theory, such as the notion that this technology provides “guaranteed” security due to the laws of physics. However, communication needs and security requirements often physically conflict in the use of QKD/QC, and achieving a balance between these fundamental issues requires meticulous engineering with an extremely low tolerance for error. Therefore, the security of QKD and QC is highly dependent on implementation as opposed to being inherently assured by the laws of physics.
Technical limitations
It is important to note that for the sake of simplicity, we specifically refer to QKD. However, similar observations apply to QC.
QKD only serves as a partial solution. It generates keying material for an encryption algorithm that provides confidentiality. The keying material could also be used in symmetric key cryptographic algorithms to offer integrity and authentication if there is cryptographic assurance that the original QKD transmission comes from the desired entity (i.e. entity source authentication).
However, QKD itself doesn’t provide a means to authenticate the source of QKD transmission. Instead, source authentication requires the use of asymmetric cryptography or pre-placed keys. Moreover, the confidentiality services QKD offers can be provided by quantum-resistant cryptography, often at a lower cost and with a more comprehensively understood risk profile.
Another technical limitation of QKD is its dependence on specialized equipment. QKD relies on distinct physical properties, and its security derives from unique physical layer communications. This property of QKD requires users to either lease dedicated fiber connections or physically manage free-space transmitters. It cannot be implemented in software or as a service on a network and cannot be easily integrated into existing network equipment. Furthermore, since QKD is hardware-based, it lacks flexibility for upgrades or security patches.
Additionally, QKD leads to increased infrastructure costs and heightened insider threat risks. QKD networks frequently require the use of trusted relays, entailing additional cost for secure facilities and introducing additional security risk from potential insider threats. This eliminates many use cases from consideration.
Securing and validating quantum key distribution is a significant challenge. While QKD is often associated with theoretical unconditional security derived from the laws of physics, the actual security it offers is limited and depends on hardware and engineering designs. The tolerance for error in cryptographic security is significantly smaller than in most physical engineering scenarios, making it very difficult to validate. Furthermore, the specific hardware used to perform QKD can introduce vulnerabilities, resulting in several well-publicized attacks on commercial QKD systems.
QKD also increases the risk of denial of service. The sensitivity to an eavesdropper as the theoretical basis for QKD security claims also shows that denial of service is a significant risk for QKD.
NSA Recommendation on the Use of QKD and QC
Currently the National Security Agency (NSA) does not recommend the use of QKD and QC unless the above technical limitations are overcome. Implemented on existing platforms, quantum-resistant algorithms rely on mathematical complexity to ensure security. These algorithms are used in cryptographic protocols to provide the means for assuring the confidentiality, integrity, and authentication of a transmission — even against potential future quantum computers. The National Institute of Standards and Technology (NIST) is currently actively conducting a rigorous selection process to identify quantum-resistant (or post-quantum) algorithms for standardization. Once NIST completes its selection process, the NSA will issue updated guidance.
The NSA considers quantum-resistant (or post-quantum) cryptography to be a more cost effective and easily maintained solution compared to QKD. As a result, the NSA does not support the use of QKD or QC to protect communications in National Security Systems (NSS). Furthermore, the NSA does not anticipate certifying or approving any QKD or QC security products for use by NSS customers unless the above limitations are addressed.
Nevertheless, it is important to note that research is still ongoing to develop advanced protocols and to increase the security of the past ones. However, until now, all the protocols developed have been variants of the BB84 protocol. There is a likelihood, and we are optimistic, that more protocols will be developed to offer increasingly secure options.
Lattice-Based Cryptography
There are a few fields of hard math problems which could be used for cryptography that are more secure against quantum computing. One potential such “post-quantum” form of cryptography is lattice-based cryptography.
Lattice Basics
Lattices as a mathematical concept have been studied and explored for at least centuries, notably by Johann Gauß in the 1800s. To form a lattice, sets of vectors are combined to form a new set of vectors, which is called the basis of the lattice. Lattice-based cryptographic systems use difficult problems about lattices that are hard to solve, even for a quantum system.
In the above image, the set of red vectors and the black vector can be combined to create another set of vectors, like the green and blue vectors. The blue vector could be formed by adding two of the black vectors and subtracting one of the red vectors, while the green vector is formed by simply adding one black and one red vector. This new set of vectors, so in this instance, a set consisting of the green and blue vectors, would then form a lattice and be defined as its basis.
While the above example deals with 2-variable or 2-dimensional vectors, lattice-based cryptographic systems would typically make much more complicated lattices using many more (possibly thousands of) variables or dimensions.
Examples of Difficult Lattice Problems
The following are a few examples of the most relevant difficult lattice problems used in lattice-based cryptography.
Shortest vector problem: Given a lattice with long vectors in its basis, find the shortest possible vector from the origin to some other grid point in that lattice.
Shortest basis problem: Given a lattice with a long basis, find a basis for that lattice with the shortest possible vectors.
Closest vector problem: Given a lattice with a long basis, as well as some vector (or end point), find the vector (or end point) in the lattice’s basis that is closest to the given vector (or point).
While seemingly intuitive in lower dimensions, these problems become much more complicated in lattices based on vectors that are long and have thousands of dimensions. It is also worth noting that these problems are often connected; finding the solution to the short basis problem for a lattice would help solve the short vector problem for that lattice.
Applications and Considerations for Lattice-Based Cryptography
Lattice-based cryptographic systems have the potential to not just replace many current classical cryptography and cybersecurity systems, but due to their nature, they could also provide entirely new cryptographic tools. Earlier in this post, the NIST’s mission to determine a standardized post-quantum algorithm was mentioned. In 2022, NIST announced 4 finalists in this search for a reliable post-quantum cryptographic algorithm, one of which uses hash functions while the other 3 are lattice-based.
Moving forward, lattice-based cryptography is a promising field that has the potential to save our cybersecurity systems against quantum’s possible threat.
Works Cited
Boutin, Chad. “NIST Announces First Four Quantum-Resistant Cryptographic Algorithms.” NIST, 5 July 2022, https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms.
“National Security Agency/Central Security Service > Cybersecurity > Quantum Key Distribution (QKD) and Quantum Cryptography QC.” Retrieved from www.nsa.gov/Cybersecurity/Quantum-Key-Distribution-QKD-and-Quantum-Cryptography-QC
Nielsen, Michael A, and Isaac L Chuang. Quantum Computation and Quantum Information. Cambridge Cambridge University Press, 2019.
Relyea, Robert. “Post-quantum cryptography — lattice-based cryptography.” Red Hat Blog, 30 October 2023, https://www.redhat.com/en/blog/post-quantum-cryptography-lattice-based-cryptography.
“Quantum Key Distribution and BB84 Protocol.” Quantum Untangled, 24 June 2021, medium.com/quantum-untangled/quantum-key-distribution-and-bb84-protocol-6f03cc6263c5.
“What is Lattice-Based Cryptography and Why You Should Care.” Wickr, 15 June 2018, https://medium.com/cryptoblog/what-is-lattice-based-cryptography-why-should-you-care-dbf9957ab717.
“What Is Quantum Cryptography? | IBM.” Retrieved from www.ibm.com/topics/quantum-cryptography.
