The Quantum Computing Cryptopocalypse – I’ll Know It When I See It

Can quantum computing break cryptography? Can it do it within a person’s lifetime? Will it be a cryptopocalypse, as some experts suggest?

Can quantum computing break cryptography? Sure, it can. Can it do it within a person’s lifetime? Yes. In fact, it will likely achieve this sometime within your career. Will it be a cryptopocalypse, as some experts suggest? Possibly. Advances in quantum computing mean that we don’t necessarily have to wait for a large quantum computer running at supercooled strengths at sufficient qubits to run Shor’s algorithm (the best-known algorithm for factoring large numbers). There are newer, more sophisticated techniques on the table, such as combinations of attacks that can do what one brute force thing can’t. So, it might not be time to panic, but it certainly is time to recognize that the threats and the benefits of quantum computing are here now, and security professionals need to ensure that they and the organization they work for are fully prepared.

These are just some of the thoughts that Johna Till Johnson, CEO at Nemertes Research, and Bob Burns, Chief Product Security Officer at Thales, shared with me on the latest episode of the Security Sessions podcast. Quantum has been discussed and theorized for years, and like the “sudden” rise of AI and generative technology that seemed to happen in early 2023, efficient and cost-effective use of quantum computing may also jump to a critical mass, and sooner than expected, despite its long voyage of research and development.

Bob asks, for example, “What happens if we find that quantum computing actually can be used as a multistage step to break the factoring that doesn’t involve Shor’s algorithm? What if we make incremental improvements or chain multiple results from a quantum computer that’s realizable today?” Those are the types of thoughts that keep him up at night. They are a testament to people’s relentless desire for innovation, as well as their abilities to advance by developing techniques, products, and solutions that weren’t even foreseen when the technology was first introduced.

You can say such things about almost any technology, of course – the personal computer, the internet, and the smartphone – they all became much more versatile than their inventors ever foresaw. But Johna provides an example of how this evolution in breaking cryptography happened just recently: researchers from the KTH Royal Institute of Technology in Stockholm used recursive training AI combined with side-channel attacks to crack one of NIST’s quantum-resistant algorithms. In this case, it measured out-of-band information, specifically temperature changes corresponding to the processing inside the machine.

This has direct and ominous implications on what is known as a Q-Day – that point in time “when quantum computers can render all current encryption methods meaningless,” as PCMagazine succinctly puts it. But as Bob points out, for calculating a Q-Day, “I look at all my data, and I take the biggest amount of data that I want to keep the longest amount of time, and I predict how long it might take me to make that transition. But when my Q-Day ends up being, let’s say, ten years away, my concern will be that someone forces that up to three of four years.”

But both Johna and Bob point out that quantum computing is not all doom and gloom. There are lots of good reasons to deploy quantum computing, and many aren’t what most people think they are. Basically, Johna says they can solve problems for which the answer isn’t the best or the only, but good enough by some consistent definition of good enough, for example, policy hardening. Whether this refers to a technical policy, a cybersecurity policy, or even a geopolitical policy, it’s helpful to know all the answers. In the latter case, a government might need to identify all the possible things it can do that will not result in war with a particular country. That’s the kind of thing that a classical computer with AI can’t answer very well, but a quantum computer can because it effectively computes all the possible scenarios and outcomes at once. It’s not great at telling you which of those scenarios is the absolute best, but it can help decision-makers draw a line to say, anything above this line, we don’t go to war, and that’s good enough.

Essentially, this is about taking on the category of problems that we don’t even try to solve right now because they’re too hard; they require a technique of solving all possible scenarios at once and cherry-picking the ones that come above some definition of good enough. And those are all the problems that quantum can solve. Johna concludes, “Once you let your imagination go with that, policy hardening is just kind of the tip of the iceberg.”

About the author: Steve Prentice

Follow me on Twitter: @securityaffairs and Facebook and Mastodon

Pierluigi Paganini

(SecurityAffairs – hacking, quantum computing)