Written by Alexa Ramirez and Elias Lehman
In Partnership with Quantum Computing at Berkeley
Quantum Key Distribution
Post-Quantum Cryptography
Quantum Networks
SECTION 1
In 1994, mathematician Peter Shor developed Shor’s algorithm focusing on finding the prime factors of a large composite integer. This algorithm works by using quantum mechanical principles — such as superposition and entanglement — to perform a series of operations that can factorize a large integer on a quantum computer.
The main idea of Shor’s algorithm is to use a quantum computer to measure the periodicity of modular exponentiation, which is a mathematical operation that calculates the remainder when an integer is raised to a power and then divided by a positive integer in the modulus. This operation is used to find the period of a function, which is in turn used to determine the prime factors of a composite integer. The algorithm works by computing the period of the smallest positive integer (the “modulo”) that equals one, using a unitary operation that implements the modular multiplication function. In essence, Shor’s algorithm exploits the unique properties of quantum mechanics to quickly solve a problem that is classically difficult.
Although Shor’s algorithm is a powerful factorization method, its
implementation can be challenging due to several limitations. One of these is that the algorithm requires a quantum computer to run, which is currently less reliable and powerful than classical computers when it comes to performing such tasks. Moreover, Shor’s algorithm is probabilistic, which means that it cannot find all the prime factors of a given integer with absolute certainty. Instead, the algorithm provides a probability of finding the prime factors, and it may require multiple runs to obtain the correct results for large composite integers. The probability of success decreases as the size of the integer grows.
Shor’s algorithm is an active research area in quantum computing due to its potential to transform various fields of science and technology, particularly cryptography. However, the widespread implementation of this algorithm would have negative consequences for communication security and data storage. This is because Shor’s algorithm can efficiently factor large numbers, which would render many existing public-key cryptographic systems vulnerable to attacks. As a result, there is a need to develop new cryptographic systems that are resistant to quantum attacks, a field of research known as post-quantum cryptography.
SECTION 2
Quantum key distribution is a method known for secure communication that uses the principles of quantum mechanics to transmit a secret key between shared parties. This key is being used to encrypt and decrypt messages transmitted over the internet having no risk of the key being intercepted by an eavesdropper. These parties share a random sequence of quantum states — typically carried by photons — that are transmitted over a quantum channel, which is known as a communication channel that preserve the quantum state of the particles being used to transmit the key.
In quantum key distribution there’s an exchange of quantum states over a communication channel by the sender and the receiver. These quantum states, which are typically photons, are encoded with the key, to encrypt and decrypt the message. As the key is randomly generated, the sender and the receiver use a series of measurements and communications to verify the key and ensure that it hasn’t been compromised.
For instance, in 1984, Charles Bennett and Gilles Brassard developed a protocol called BB84, also known as the Bennett-Brassard 1984 protocol. This protocol is the original quantum cryptography protocol in which it uses two non-orthogonal states to encode the key and relies on the Heisenberg uncertainty principle to detect the presence of an eavesdropper. In this case, the sender is known as Alice, the receiver as Bob, and the eavesdropper as Eve. The non-orthogonal states that are being employed are states that are not mutually exclusive and cannot be perfectly distinguished from one another. Here, Alice randomly selects one of these states to decode the key, while Bob measures the state to decode the key, which then will disturb the quantum states if an eavesdropper intercepts the key.
This can be detected by error correction which increases privacy techniques. The quantum key distribution differs from the classical communication methods by its increased security and privacy of information because the principles of quantum mechanics make it impossible for an eavesdropper to intercept the key without being detected. Thanks to these principles, this makes the key features extremely secure against adversaries with unlimited resources. Heisenberg’s uncertainty principle, in particular, is responsible for the inability to learn the key without conducting a measurement and being detected.
Quantum cryptography research is focused on developing secure communication protocols over our existing networks. Researchers have developed various protocols that enable the establishment of a shared secret key between parties in a secure and efficient manner. The primary application of these protocols is in contexts where secure communication is critical, such as military and governmental communications. Quantum cryptography represents a promising new direction in the field of secure communication, given its potential to provide security that is nearly impossible to breach without detection.
SECTION 3
Post-quantum cryptography refers to cryptographic algorithms that are designed to be secure against attacks by quantum computers. As exhibited by Shor’s algorithm, quantum computers have the potential to break cryptographic algorithms that are currently widely used to secure communication, such as the RSA cryptography algorithm which is used to secure communication over the internet. Cryptography specialists theorize that attackers can collect encrypted data packets, and in the future may decrypt them using quantum computers – a so-called steal now, hack later approach. In response to this threat, cryptographers in the private sector, academia, and government labs alike have sought new cryptography methods that are resistant to hackers using both classical and quantum computers.
Quantum-resistant cryptographic algorithms rely on mathematical problems that are hard to solve on both classical and quantum computers. Some algorithms employ the learning with errors (LWE) problem and its variant, ring learning with errors (ring-LWE) problem for encryption and decryption. Another example of what is being used is code-based cryptography, based on the difficulty of decoding error-correcting codes.
The sensitivity of government data, and thus the importance of secure transmission of information, prompted the National Institute for Standards and Technology (NIST) to seek the best PQC algorithms for standardizing modern communications. In 2017, NIST launched a competition to select the most secure algorithm. In July 2022, after three filtration rounds, NIST announced their top four finalists, ready for implementation in today’s communication systems. The algorithms were divided into two categories – those for key-establishment, and for digital signatures. NIST recommends two primary algorithms to be implemented for most use cases: CRYSTALS-KYBER (key-establishment) and CRYSTALS-Dilithium (digital signatures). As alternative signature schemes, FALCON and SPHINCS+ were also be standardized.
There are four additional runner-up algorithms currently in a fourth round of evaluation before being considered for standardization. Among these runner-ups was the algorithm SIKE, which in August 2022 was broken by a classical, single core processor and is thus no longer in the competition.
Post-quantum cryptography is an area of research that proposes important factors to these algorithms by preparing information security systems to be able to resist quantum computing attacks. As there is no longer a debate over when we should transition to quantum-secure algorithms – because the risk is evident – there is an ongoing effort to establish which algorithms will replace today’s cryptography protocols.
SECTION 4
An interesting network, still in the theoretical stage, is a quantum oscillator network. A quantum oscillator network is a system of quantum oscillators that are connected and interact with each other through their quantum states. As they can be modeled by different physical systems such as photons in a cavity or atomic states in a solid, these networks invoke the transmission of information using the principles of quantum mechanics. This specific network can leverage widespread entanglement which can support the lifetime of quantum states of the oscillators and the complexity of modeling and simulating similar systems.
Quantum networks transmit and process quantum information, analog to classical computer networks such as the internet. As we have examined before, due to the unique properties of quantum systems, quantum networks can be more secure and faster at certain tasks than classical networks. In a quantum network, particles such as photons or atoms are used to encode and transmit information.
An ideal quantum communication network transmits information securely between two parties. This type of network can use multiple techniques, such as QKD, to establish communication channels that are resistant to eavesdropping. Another type of network involves a quantum computing network, which uses quantum computers as nodes connected over a network, typically optical fibers that transmit photons, to perform distributed quantum computations.
On December 23, 2022, NTT Research, Inc. developed an application involving the quantum oscillator network through the cyber coherent Ising machine (cyber-CIM), a quantum algorithm that can be implemented on a modern digital platform or hybrid quantum-classical machine in the future. This application mainly focused on how the quantum oscillator network can solve combinatorial optimization problems, which were proposed by evaluating the performance of the cyber-CIM algorithm. Researchers are continuously working to develop new strategies for these types of technologies, to create scalable and practical applications.