Quantum will Break and Fix Cryptography

Anyone who’s investigated quantum computing will already know the technology will eventually render our most robust cryptographic algorithms defunct. There has been an abundance of papers and research on what might replace these algorithms, with National Institute of Standards and Technology (NIST) holding ongoing rounds of competition to find alternative algorithms that leverage quantum architectures. 

Public-key cryptosystems, for example, ones that use Rivest–Shamir–Adleman (RSA), are algorithms that rely on how difficult it is to mathematically factor large composite numbers (or calculate discrete logarithms). These problems remain computationally infeasible for traditional computers to solve in reverse, so they are considered today as strong as we need. However, Peter Shor, an American mathematician and MIT professor, discovered an algorithm that finds the prime factors of a composite number in a reasonable timeframe using a quantum computer. Any data encrypted using the RSA algorithm will be at risk. 

We are still safely using RSA because we lack sufficiently powerful and scalable quantum computers to do the work. Shor’s algorithm requires a quantum computer with a substantial number of qubits and very low error rates to factor these large numbers. If you go back a few years, none of the experimental quantum computers were powerful enough to do this work, so Shor’s algorithm was largely theoretical rather than practical. But the advancements we are seeing in several technology streams that drive us closer to the quantum era means we are inexorably heading into this encryption apocalypse.

Transition to the Quantum Era

Transitioning to post-quantum cryptography will pose some problems as we are still to create widely accepted post-quantum cryptographic algorithms resistant to similar attacks. We would need the Australian government and others worldwide to coordinate with industry and academia to accelerate this development and ensure we create timely standards and guidelines to secure data against quantum threats. There will undoubtedly come a time when much of the world’s encrypted data is vulnerable to governments or large organisations who run unregulated quantum computers, including hostile nation-states who may use such systems to attack our most critical infrastructure. 

There will undoubtedly come a time when much of the world’s encrypted data is vulnerable to governments or large organisations who run unregulated quantum computers, including hostile nation-states who may use such systems to attack our most critical infrastructure. 

This situation begs the question, what can we do to protect our data in the interim? One possible solution is to democratise access to quantum computers, such that all cryptography uses these systems. If this happened, we could move to quantum cryptography even when our systems still run traditional hardware, if the chosen algorithms are sufficiently streamlined to also run on traditional computer systems. Only time will tell as to how this plays out, but we need a concerted effort from many different stakeholders to ensure it doesn’t end in our data being vulnerable to whoever wins the quantum race.

What’s the Upside?

On a positive note, the search for true random number generation has long been a pursuit of mathematicians and computer scientists. Every method of creating random numbers on a traditional computer uses what are called pseudorandom number generators. These may appear random but are deterministic since they are based on how time passes and is linked to the internal clock of the computer architecture it resides on. Now, enter stage left with quantum computing. Quantum systems can generate genuinely random numbers, and this will exponentially improve cryptography.

A Quantum Random Number Generator (QRNG) measures a quantum system’s properties, like electron spin and photon polarisation, using those measurements to generate the random output. Since these properties change randomly and are based on physical natural processes, we obtain genuinely random numbers no matter when the output is requested. This unique feature of quantum systems gives them an advantage over traditional computers and will accelerate our development of software that requires high-quality randomness, such as simulations and, of course, cryptography.

It is a truly interesting time to be alive. Quantum computers are rapidly progressing to the point where they break existing cryptography by efficiently solving complex mathematical problems impossible to solve with traditional computers. At the same time, quantum computers will also fix cryptography by enabling new quantum-resistant algorithms, introducing true randomness and new cryptographic techniques. These quantum-safe approaches are being developed to work even against the computational power of quantum machines, thus ensuring that cryptography can adapt and remain robust in the quantum era.

Tony Campbell

Director of Research & Innovation, Sekuro

Tony has been in information and cyber security for a very long time and delivered projects and services across a bunch of different industries through a variety of different roles. Over the years, Tony has always tried to bridge the growing skills gap through his employment, by mentoring, teaching and working with other disciplines to help them understand the complexities of what we do.

Scroll to Top