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

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

  

Abu Dhabi-UAE:– 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 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 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.

-Ends-

About Technology Innovation Institute (TII)

Technology Innovation Institute (TII) is the dedicated ‘applied research’ pillar of Advanced Technology Research Council (ATRC). TII is a pioneering global research and development centre that focuses on applied research and new-age technology capabilities. The Institute has seven initial dedicated research centres in quantum, autonomous robotics, cryptography, advanced materials, digital security, directed energy and secure systems. By working with exceptional talent, universities, research institutions and industry partners from all over the world, the Institute connects an intellectual community and contributes to building an R&D ecosystem reinforcing Abu Dhabi and the UAE’s status as a global hub for innovation.

For more information, visit www.tii.ae 

About Cryptography Research Centre (CRC)

Cryptography Research Centre – one of the seven research centres at Technology Innovation Institute in Abu Dhabi (TII) – designs the building blocks of advanced cryptographic algorithms that enable data confidentiality, integrity, privacy, and non-repudiation. The Centre works in partnership with leading research advisors and institutions to research new cryptographic primitives covering design, analysis, implementation and implementation hardness, and the development of security protocols. 

For more information, visit https://cryptography.tii.ae      

Connect with us on social media:
LinkedIn: https://www.linkedin.com/company/tiiuae/
Twitter: https://twitter.com/TIIuae
Instagram: https://www.instagram.com/tiiuae/ 

Send us your press releases to pressrelease.zawya@refinitiv.com

© Press Release 2021

Disclaimer: The contents of this press release was provided from an external third party provider. This website is not responsible for, and does not control, such external content. This content is provided on an “as is” and “as available” basis and has not been edited in any way. Neither this website nor our affiliates guarantee the accuracy of or endorse the views or opinions expressed in this press release.

The press release is provided for informational purposes only. The content does not provide tax, legal or investment advice or opinion regarding the suitability, value or profitability of any particular security, portfolio or investment strategy. Neither this website nor our affiliates shall be liable for any errors or inaccuracies in the content, or for any actions taken by you in reliance thereon. You expressly agree that your use of the information within this article is at your sole risk.

To the fullest extent permitted by applicable law, this website, its parent company, its subsidiaries, its affiliates and the respective shareholders, directors, officers, employees, agents, advertisers, content providers and licensors will not be liable (jointly or severally) to you for any direct, indirect, consequential, special, incidental, punitive or exemplary damages, including without limitation, lost profits, lost savings and lost revenues, whether in negligence, tort, contract or any other theory of liability, even if the parties have been advised of the possibility or could have foreseen any such damages.


More From Press Releases