Scientific Paper: Quantum Search for Scaled Hash Function Preimages
Authors: Sergi Ramos-Calderer, Emanuele Bellini, José I. Latorre, Marc Manzano and Victor Mateu
Quantum computers are still in their early infancy, but there is some concern they could break many existing cryptographic algorithms. To address these concerns, researchers have been exploring the mechanics of how quantum cryptographic work in practice. This could lead to the development of more secure algorithms in the wake of improvements in quantum computing.
Researchers at the Technology Innovation Institute in the United Arab Emirates have demonstrated a new approach for simulating cryptographic hacking algorithms on a quantum simulator that run on classical computers. One of the key discoveries was a way to model the complexity of these kinds of computations that could be scaled to a full-sized quantum computer. This allowed them to tease apart the characteristic of more secure cryptographic designs.
Researchers have been exploring this area for a while, since it could have important ramification for security, privacy, finance, and ecommerce. One approach has been to craft a quantum attack on a full-sized cryptography problem by focusing on a small element of the problem and then combining these pieces at the end. Attacking a cryptographic algorithm involves the interplay of many mathematical processes. This approach can struggle with estimating how the interplay between different pieces would scale up.
So, the TII researchers found a way to shrink the cryptographic problem down in such as way as to maintain the appropriate relationship between all the different pieces. Emanuele Bellini, Lead Cryptographer at the TII said, “This was not possible before because quantum simulators consume a lot of power. The one we are using allows us to manage enough simulated qubits to run a meaningful sample.”
The goal of quantum resistance cryptography
The goal of quantum resistant cryptography is to create algorithms that cannot be efficiently attacked by a quantum computer. Quantum cryptography runs algorithms on quantum computers. Post quantum cryptography explores ways of improving the algorithms that run on classical computers that are still resistant to quantum attacks and classical attacks. This specific research focused on post quantum cryptography.
There are different types of cryptographic research exploring ways of attacking asymmetric and symmetric cryptographic schemes. Other research has explored how a technique called Shor’s algorithm could be used to break asymmetric cryptographic schemes such as RSA and Discrete Logarithms.
In this case, the team was looking at how symmetric cryptographic schemes could be modeled and attacked using Grover’s algorithm. This research demonstrated the first implementation of all the components of Grover’s algorithm as a complete ensemble of components. Other researchers have mathematically explored a full implementation but could not run it or have run small pieces of the full algorithm. The TTC researchers resized the problem to a smaller scale which allowed them to run a full implementation of Grover’s algorithm against the problem.
Importance of simulating quantum algorithms
Quantum simulators mimic the operations of a quantum computer in a way that allows researchers to run an algorithm on a classical computer. This allows researchers to explore how the components of the algorithms work together in preparation of more powerful quantum computers in the future. The current simulators can support 35-40 qubits, which is considerable progress from just a few years ago.
In cryptographic research, brute force attacks exhaustively try all possible passwords until the correct one is discovered. It is not very efficient and so cryptographers are looking for shortcuts that can the solution with less effort. However, analyzing the computational requirements of a brute force attack can provide a benchmark for comparing improvements with other algorithms.
Defining toy cryptographic algorithms that scale up to real constructions
One of the key discoveries was how to create several classes of “toy algorithms” that preserve the cryptographic properties of a full-sized cryptographic algorithm yet are small enough to break using brute force methods. This allows researchers to benchmark the speedup of quantum algorithms compared to traditional brute force algorithms running on classical computers. They specifically found that the processing power required to scale brute force algorithms grows at a rate 2n compared to 2n/2 for Grover’s algorithm, which is considered a quadratic improvement.
The researchers made two types of toy algorithms called a Toy Sponge Hash model and a Toy BLAKE Hash model. The Toy Sponge Hash model does not have a real-world counterpart, but it does capture the elements of larger cryptographic algorithms. It would take a quantum computer with about 500 qubits to retrieve the password from a full-sized implementation. The team was able to calculate the complexity in a way that could be extrapolated to larger problems.
The Toy Blake Hash Model is a real function that is used in some cryptographic standards. However, it requires more than 35 qubits to retrieve the password, so the team was not able to simulate it. A full-scale implementation of this algorithm would require about 2000 qubits.
Quantifying quantum gate complexity
One key advancement of these new models was that the researchers were able to calculate the complexity scaling in a way that can be extrapolates to real implementations. Measuring the quantum resources like gates and qubits provides cryptography researchers benchmarks in estimating how many qubits would be required to break a real hash function.
This involves teasing apart how the construction of quantum circuits differs from classical circuits. Quantum computers have qubits and quantum gates that connect the qubits together. This is analogous to the gates in a classical computer that connect bits together. These gates are wired into different kinds of logical function such as NOR, XOR, and OR. In a quantum computer a gate is essentially a matrix operator. Some of the classical gates translate into larger gates in quantum computers, which increases the requirements for qubits.
The researchers found that choosing the right types of logical gates in cryptographic algorithms could provide significant improvement compared to others. Bellini said, “One of the things we realized was that some ciphers are more difficult to attack than others with this kind of quantum attack.”
The team found that the difficulty depends on the types of gates used in the cipher. Including more OR and AND logical gates in the algorithms would significantly increase the amount of quantum processing to search for breaking the hash function aspect of the cryptographic algorithm that could help find the password used for encrypting data.
This difficulty is often measured in the number of quantum bits or qubits that might be required to break a cipher in a reasonable length of time. In this case, they were able to run the quantum cryptographic attack on a 35-qubit simulator. Bellini estimates that a full-scale cryptographic attack might require 2000 qubits. Bellini noted that modern quantum computers are still a long way from this. Furthermore, existing quantum computers are error prone, so most of the qubits are used to correct these errors.
Going forward, the team is exploring how they might construct toy algorithms and simulate quantum cryptographic attacks against symmetric algorithms. This could include exploring alternatives to Shor’s algorithm which is only good at problems involving factorization and discrete logarithms. The team is also exploring how classical attacks could be enhanced by variations in Grover’s algorithm. There may also be better ways to break the problems into smaller problems and look at how each component could be simulated.