Researchers discover new approach to simulate complexity of quantum cryptographic attacks via classical computers

Quantum computers may still be in their early infancy, but there is already some concern that they could break several existing cryptographic algorithms. To address these concerns, researchers have been exploring the mechanics of how quantum cryptographic algorithms work in practice, with their studies likely to lead to more secure algorithms as a result of improvements in the field of quantum computing.

Researchers at Technology Innovation Institute (TII) in the United Arab Emirates have demonstrated a new approach to simulate cryptographic hacking algorithms on a quantum simulator that runs on classical computers. One of the key discoveries was a way to model the complexity of such computations that could be scaled to a full-sized quantum computer. The research enabled them to create more secure cryptographic designs.

 

Researchers have been exploring this area for some time now, considering that it could have important ramifications for security, privacy, finance, and ecommerce. One approach has been to craft a quantum attack on a full-sized cryptography problem through focusing on a small element of the problem and then combining these pieces in the end. Attacking a cryptographic algorithm involves the interplay of many mathematical processes and this approach could struggle with estimating how the interplay between different pieces would scale up.

 

So, researchers at TII found a way to shrink the cryptographic problem down in such a way as to maintain the appropriate relationship between all the different pieces. Emanuele Bellini, Lead Cryptographer at 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 still resistant to quantum attacks and classical attacks. This specific research focused on post quantum cryptography.

 

There are various types of cryptographic research currently underway that explore ways of attacking asymmetric and symmetric cryptographic schemes.  Other research has examined how the technique of using Shor’s algorithm could 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 only run it with small pieces of the full algorithm. TII researchers resized the problem to a smaller scale, which allowed them to run a full implementation of Grover’s algorithm to address 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 enables researchers to explore how the components of the algorithms work together to prepare for 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 out all possible passwords until the correct one is discovered. It is not very efficient and so cryptographers are looking for shortcuts that can find the solution with less effort. However, analysing 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 the scientists arrived at was how to create several classes of “toy algorithms” that preserve the cryptographic properties of a full-sized cryptographic algorithm and 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 that run on classical computers.  They specifically found that the processing power required to scale brute force algorithms grows at a rate 2ⁿ compared to 2^n/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 2,000 qubits.

 

Quantifying quantum gate complexity

 

One key advancement of these new models was that the researchers were able to calculate the complexity and scale it in a way that enabled it to be extrapolated to real implementations. Measuring the quantum resources like gates and qubits provides cryptography researchers with benchmarks to estimate how many qubits would be required to break a real hash function.

 

This involves understanding 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 a significant improvement over several others. Bellini said: “One of the things we realised was that some ciphers are more difficult to break than others with such quantum attacks.”

 

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 identify how to break 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 period 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 2,000 qubits. Bellini noted that modern quantum computers are still a long way from achieving this capacity. 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 proficient at tackling problems involving factorisation 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.