Quantum computing spells the death knell for conventional encryption. That’s a fact, not speculation, and as the race to build business ready quantum computers hots up, it won’t be long until algorithms like Advanced Encryption Standard (AES) are replaced for a more resilient successor. Even RSA (a public-key cyrtosystem), the basis of many Public Key Infrastructure (PKI) implementations, isn’t safe. RSA relies on it being very difficult to factor large numbers into their prime factors. However, a quantum computer using Shor’s algorithm will factor these numbers significantly faster than classical computers, thus making RSA – and PKI systems – vulnerable to attack. Similarly, AES will be vulnerable to attack using Grover’s algorithm. You’ll find references to both these attack techniques at the end of this blog in case you’re interested.
To address this impending reality, researchers are developing quantum-resistant cryptography that relies on a different set of mathematical problems, ones that are difficult for quantum computers to solve. If these new techniques prove successful, and, importantly, implementation is practicable, they will become the new standard for protecting data confidentiality and integrity. Yet while the dream of quantum-resistant cryptography sounds great, in practice there are many challenges to be overcome, and the question remains: Can we solve these problems in time, since viable commercial quantum computers are drawing ever nearer.
It was way back in 1994 when mathematician, Peter Shor, first figured out the algorithm for attacking RSA using a quantum computer, and so the race to find quantum-resistant encryption began. One leading candidate is called lattice-based cryptography, which uses mathematical structures called lattices to create secure cryptographic systems. This approach is believed to form the basis of one possible option for post-quantum cryptography, and in the USA, the National Institute of Standards and Technology (NIST) has selected several lattice-based algorithms as the finalists in its Post-Quantum Cryptography Standardization Project.
Another approach is multivariate cryptography, which relies on the difficulty of solving systems of multivariate equations. Like most of the other approaches, this has been in development for decades, but is still considered an active area of research. Some of the other methods also under consideration are hash-based cryptography, isogeny-based cryptography, and quantum key distribution (QKD). However, like all new forms of cryptography, each has its own strengths and weaknesses, and viable practical use has yet to be decided. Nevertheless, last year, in 2022, NIST announced several algorithms for widespread community assessment, as the front runners. You can see those selected algorithms here.
One major drawback that needs consideration for any new algorithm is how it interoperates in a legacy technology capacity. Even the most powerful conventional computer using very long keys needed to interoperate with a quantum computer would need to fall back to conventional algorithms. So, until all systems are quantum based, the issues relating to data confidentiality and integrity remains.
As quantum continues to advance at pace, the importance of post-quantum cryptography will only grow, making it a critical area of research for years to come. Lately, we’ve seen a massive push from industry and governments to advance the viability of quantum computers, from research projects to commercial and government capabilities, and it won’t be too long until we are reading about the first quantum desktop hitting the shelves in JB HiFi. When that happens, all bets are off for encrypted data unless we equally focus our research dollars on that arms race.
P.S. If you don’t believe me, take a closer look at what Canberra-based Quantum Brilliance are doing with diamond as the basis for their new technology, which has the potential to shrink what would once have been housed in a large lab down to the size of a desktop.
Shor’s algorithm: Shor’s algorithm – IBM Quantum
Grover’s algorithm: Grover’s algorithm – IBM Quantum
Lattice based cryptography: pqc.dvi (nyu.edu)
The NSA on QKD and Quantum Cryptography: National Security Agency/Central Security Service > Cybersecurity > Quantum Key Distribution (QKD) and Quantum Cryptography QC (nsa.gov)
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.