Myth-busters: solutions for the quantum threats to encryption

There's lots of confusion about what the right solutions should be...

Image generated by ChatGPT

Quantum computing is an emerging technology that is currently at an early stage of development. It won’t automatically speed up all calculations but may enable specific new algorithms to solve particular problems that are not tractable with existing classical computers. One such algorithm (Shor’s algorithm) would allow a sufficiently capable quantum computer to break some widely used forms of public key encryption - which is why quantum computing has potential impacts on cyber security.

There are plenty of myths about what the risks actually are and what organisations need to worry about, but even once you get past these, there is often confusion about the solutions. There is no shortage of products in the market, and that has created a wave of misconceptions that can lead to poor decisions. In this article I’ll try to dispel some of the most common ones I have heard recently. They come from a variety of sources, but hopefully this will help you to identify which sources you can trust, and which ones don’t really understand the subject (or are maybe trying to sell you something you don’t need).

Myth 1 - Quantum random number generators will make you quantum safe

Quantum random number generators (QRNGs) are technology based on some cool physics. They use the inherent randomness of quantum mechanics to generate truly random numbers from observations of quantum phenomena. As any cryptographer will tell you, good randomness matters when generating encryption keys and other cryptographic values - to reduce the risk of an attacker being able to guess them. This means that we need to find ways around the problem that digital computers, being deterministic, only generate pseudo-random numbers. It’s possible that QRNGs could provide a way to do this, although we already have other solutions in place today.

Quantum random numbers? (generated using Google Gemini)

However, the real problem is that when considering the risks to encryption, it doesn’t matter how perfectly random your private/public key pair generation is; if you are using a quantum-vulnerable public key encryption scheme, Shor’s algorithm will still allow a sufficiently good quantum computer to calculate any single private key from any single public key. Therefore, although QRNGs can be useful for general security hygiene, they provide exactly zero protection against quantum threats to encryption.

Myth 2 - Quantum key distribution is a 100% guaranteed secure solution to solve quantum risks

Quantum key distribution (QKD) is another technology based on some really cool physics - this time, the fact that observing a quantum system irreversibly changes it. This provides a way to send a message to someone and be able to detect if anyone else has read the message en route. In theory, this provides a 100% guaranteed method to set up a secret encryption key between two parties without anyone else having a copy of the key.

Take note, however, of the first two words in the last sentence - “in theory”. In practice, implementing QKD as part of a real encryption system requires many other components - such as authenticated endpoints, key management etc - that can create security vulnerabilities. After all, any cyber security specialist will tell you no system is guaranteed 100% secure. And that’s before considering the limitations of current quantum hardware for such communication, which limits the range to no more than around 100km over fibre, and introduces further potential errors.

Some advocates of QKD will suggest there is a genuine debate about whether it is better than classical solutions such as post-quantum cryptography (which we’ll discuss further on). However, for QKD the official advice from the Australian Signals Directorate is that

practical limitations of QKD … mean that ASD does not support its use for secure communications

This is not an isolated view - other organisations such as the UK’s NCSC and European cyber security agencies have provided similar guidance.

Myth 3 - We need quantum to fight quantum

Image created using ChatGPT

The development of quantum technologies is the whole reason why we are concerned about potential impacts of encryption - so do we need the quantum scientists and technologists to fix it? The only two substantial ideas they have come up with to help encryption are quantum random number generators and quantum key distribution - which we have already shown above are not going to help. Meanwhile, the vague concept of “quantum cryptography” doesn’t actually exist.

It turns out that the best approach is to replace current classical public-key encryption schemes that might be vulnerable to a quantum computer attack with other classical encryption schemes that are expected to be resistant to known quantum attacks. Asymmetric (public-key) cryptography relies on “one way” functions that are easy to compute in one direction (derive public key from a private key) but very difficult to reverse (derive private key from the public key). While Shor’s algorithm breaks the number theory problems used by the current mainstream methods (i.e. RSA, DH and ECC), researchers have developed a whole field of mathematical ideas of other functions for which no efficient quantum attack is known.

This field is called “post-quantum cryptography” (PQC) or “quantum-resistant cryptography” (QRC), but it’s important to note that there is actually nothing quantum about these - they are just different types of maths that can be run on current classical computers.

Myth 4 - We don’t really know what the right solutions are

A discussed above, the best solution is PQC/QRC. It is true that when the quantum risk to cryptography was first identified, mathematicians had lots of different ideas to solve this. However, in 2017 the US NIST organisation started a public competition to find the best solutions. This allowed anyone around the world to propose ideas - and to try to find the weaknesses in them. This process led to the selection of certain algorithms, mainly based on something called “lattice-based cryptography”. These have been formalised in NIST standards that are openly available and are now being incorporated into other standards and being implemented.

It is true that we can’t formally prove that lattice-based cryptography is secure, any more than we can prove that current public-key cryptography methods (which we know are susceptible to a quantum computer attack) are secure against a classical computer. However, these approaches have been studied for many years and no widely accepted practical vulnerabilities have been published - while other proposals in the NIST competition were found vulnerable and eliminated.

It’s also true that PQC algorithms can come with trade-offs. Performance varies by algorithm and platform, but recent benchmarking suggests the computation effort may not be that different from current algorithms. However, public kets, ciphertexts and digital signatures can be much bigger (typically 10x or more). For most systems a few extra hundred or even thousand bytes won’t be significant. However some embedded systems with limited memory and/or limited network bandwidth may require specialised solutions. In most cases we know what to do, it’s “just” a matter of practical implementation and deployment.

Where do we go from here?

Previously, I have broken down various myths and highlighted that the main concern should be data sent across a network protected by public key encryption. A number of vendors are touting different solutions to address this, but having dispelled the common myths the way forward is clear - you should start planning to upgrade existing quantum vulnerable encryption to use PQC.

PQC isn’t quantum technology - it’s new maths that runs on existing hardware. However, upgrading all your potentially vulnerable systems will be a long and complex program of work. I joked that it’s “just about implementation”, but anyone with IT project management experience knows this is often the biggest challenge, not the actual technology.

In the next article in this series, I’ll move from these high level principles to practical guidance on how to get started on this process.

MDR Quantum helps organisations to understand and assess their quantum risk and to respond accordingly. Our services include executive briefings, policy development, risk assessment and PQC migration strategy and planning - please reach out if you’d like to learn more about how we may be able to help.