Estimating and reducing resources for solving cryptography problems using quantum computers

To make quantum computing practical for real-world challenges such as drug discovery and material innovation, it is crucial to understand and reduce its resource requirements. Our work with PsiQuantum focuses on optimising the quantum resources needed to solve cryptographic problems, a key step in advancing quantum computing for broader applications in this field.

Quantum computers are expected to transform a wide range of applications, from chemistry and finance to cryptography—the foundation of digital information security. As threats to information security grow, organisations must begin planning for the transition to quantum-safe cryptosystems. This shift requires a clear understanding of the vulnerabilities in today’s cryptographic methods, including the ability to estimate and reduce the quantum resources required to break them. These insights are crucial not only for making quantum computing practical but also for identifying the most promising early applications of this transformative technology.

What is cryptography and why is it important in the modern world?

Cryptography uses mathematical techniques to protect digital information, systems, and communications from unauthorised access. Through encryption and decryption, it ensures that data remains unreadable without the correct key. Modern cryptography often relies on public-key cryptography, which enables secure communication without the need to share a secret key in advance. Instead, it works by using a public key to encrypt data and a corresponding private key to decrypt it. The security of these systems depends on solving complex mathematical problems that are difficult for classical computers to solve. One widely used method is Elliptic-Curve Cryptography (ECC), which relies on the difficulty of solving the Elliptic Curve Discrete Logarithm Problem (ECDLP). The strength of ECC comes from the fact that it offers robust security while using smaller keys, making it efficient in terms of computation, storage, and bandwidth.

Can Elliptic-Curve Cryptography (ECC) be broken?

While ECC is secure against attacks by classical computers, quantum computers present a potential threat. In 1994, Peter Shor introduced a quantum algorithm capable of solving problems like the ECDLP. In theory, this means a powerful enough quantum computer could break ECC and compromise current cryptographic systems, prompting efforts to develop quantum-safe alternatives.

But does theory translate to reality?

Shor’s algorithm can, in principle, be run on a quantum computer with cryptographically relevant key sizes, but only if the computer is large-scale and fault-tolerant. Fault tolerance is essential for reliable operation because quantum systems are highly prone to errors caused by noise and hardware imperfections. Achieving fault tolerance requires quantum error correction (QEC), which uses algorithms to detect and correct errors without disturbing the underlying quantum information.

What does it take for fault-tolerant quantum computers to break Elliptic-Curve Cryptography?

This is the fundamental question behind our collaborative research with PsiQuantum.

In our study, we estimated the resources required to run Shor’s algorithm for solving elliptic curve discrete logarithms on fault-tolerant quantum computers. Our research focused on elliptic curves over binary fields (a type of number system used in cryptography where values are represented by polynomials with coefficients of 0s and 1s, and the rules for arithmetic differ from standard number systems). This approach is commonly used in securing real-world digital systems.

We examined the qubit and gate requirements (at both logical and physical levels) for running Shor’s algorithm. Our analysis also accounted for the resources needed for quantum error correction (QEC), a crucial factor in ensuring the reliable operation of quantum systems. Additionally, we provided runtime estimates for a variety of hardware platforms, including matter-based systems (such as trapped-ion and superconducting devices) as well as PsiQuantum’s photonic architecture. The key sizes we considered ranged from 163 to 571 bits, which are common in ECC applications today.

Beyond estimating the hardware and runtime requirements, we modified the existing quantum algorithm to handle specific cases in binary elliptic curve cryptography and optimised key parts of the algorithm. Our goal was to reduce runtime by refining the quantum circuits used for elliptic curve group operations, which are both complex and resource-intensive.

Advancing quantum computing for societal impact 

The methods we used to optimise and estimate the resource requirements of quantum algorithms could provide valuable insights for the broader development of quantum computing. These techniques can also be applied to other quantum algorithms to better understand what is needed to run them efficiently, which could benefit applications beyond cryptography. By deepening our understanding of the resources quantum systems require, we can make quantum computing practical across sectors like materials science (see previous work by the Hartree Centre and PsiQuantum), energy, and healthcare, where it could accelerate breakthroughs in clean energy, drug discovery, and complex data analysis, with the potential for significant societal impact.