CHAPTER 6

Written by Alexa Ramirez and Elias Lehman

In Partnership with Quantum Computing at Berkeley

Shor’s Algorithm

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

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.

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.

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.

SECTION 4

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.

You have successfully joined our subscriber list.