Countdown to Q Day: Quantum computers could kill cryptography - can new algorithms stop them?

In the 1990s, two researchers Peter Shor and Lov Grover ran a thought experiment. They wondered: what if you could use quantum states – which enable a bit of data to act as a 0 and 1 at the same time – to do computation? These machines would be able to perform astonishing calculations – so astonishing they could break all the encryption we use to protect digital transactions.

To support their argument, the two scientists designed and published algorithms that could, in theory, do the job.

30 years later, the theory is close to reality. Tech giants such as Google, IBM and Microsoft are making progress in quantum computing. So much so that there is now talk of “Quantum Day” (Q Day) – the date when quantum machines become sufficiently advanced/available to break conventional encryption.

A recent Gartner® report* says “By 2029, advances in quantum computing will make conventional asymmetric cryptography unsafe to use.”

The good news is that technology companies, governments and standards agencies are well aware of the deadline. They are working on defensive strategies to meet the challenge — inventing cryptographic algorithms that run not just on quantum computers but on today’s conventional components.

This technology has a name: post-quantum cryptography.

There have already been notable breakthroughs. In the last few days, Thales launched a quantum-resistant smartcard: MultiApp 5.2 Premium PQC. It is the first smartcard to be certified by ANSSI, France’s national cybersecurity agency.

The product uses new generation cryptographic signatures to protect electronic ID cards, health cards, driving licences and more from attacks by quantum computers.

It’s a small step forward in the fight to come. To get a fuller picture of this battle, let’s review the history of quantum computing, the nature of the threat and the potential solutions…

What is quantum computing?

Conventional computers use semi-conductors to make calculations based on billions of binary switches that can be either one or zero. A quantum computer, on the other hand, takes advantage of the strange properties of sub-atomic particles. Here, a bit of data — a qubit —can be a zero and a one at the same time. Consequently, quantum computers are exponentially faster and more powerful than conventional silicon. Indeed, Google claims its ‘Willow’ quantum chip takes five minutes to solve a problem that would take the world's fastest super computer 10,000,000,000,000,000,000,000,000 years to complete.

Why Quantum changes the game for encryption

Conventional cryptographic algorithms multiply huge prime numbers to scramble data. These sums would take a conventional computer billions of years to solve. Quantum computers could, in theory, crack them in days or even hours. Obviously, post-quantum encryption algorithms must be based on new kinds of mathematical problems. 

How urgent is the Q Day problem?

It’s very urgent. Why? Because of the ‘Harvest Now, Decrypt Later’ challenge. Although quantum computing is progressing fast, it is not yet a scalable and commercial technology. However, cybersecurity experts believe bad actors have already begun hoarding information with the aim of decrypting it when Q Day arrives.

These experts expect quantum technology to become ‘democratic’ very quickly. Xavier Banchelin, at Thales, believes new business models will make this possible: “The first users of quantum computers will probably be nation states,” he says. “But I can see a cloud model developing, where you pay as you go for access to quantum computing. This will take QC to a wide user base pretty fast.”

How are cybersecurity researchers responding to the threat?

To defend against post-quantum attacks, researchers are developing encryption algorithms that conventional and future quantum computers struggle to solve.

Leading this effort is the US-based National Institute of Standards and Technology (NIST). Its Post-Quantum Cryptography (PQC) project started in 2016 and released its first three standards in 2024. The formal name for these algorithms is the Federal Information Processing Standard (FIPS) 203, 204. They are based on a family of math problems called structured lattices.

The algorithms are designed for two main tasks. The first is for general encryption, which protects information such as passwords exchanged over public networks. The second is for digital signatures, which are used for identity authentication in ID cards, driver’s licences, health cards and so on.

“These finalised standards include instructions for incorporating them into products and encryption systems,” says NIST’s PQC standardisation lead Dustin Moody. “We encourage system administrators to start integrating them into their systems immediately, because full integration will take time.”
 

Thales’ breakthrough: the first certified PQC smartcard

NIST’s call for industry integration was quickly taken up by Thales. According to Banchelin, his team spotted the post-quantum cryptography challenge early. "About six years ago, when our engineers first mentioned this emerging threat, we immediately recognised its potential impact. Obviously, for us, cryptography is a key asset.  We saw what NIST was doing around that time and we asked: is this something we can successfully integrate into our smart cards?”

The Thales researchers got to work. They used the FIPS 204 standard to define a digital signature algorithm for a new quantum-resistant smartcard: MultiApp 5.2 Premium PQC.

Of course, experimental products like this must be rigorously tested. So Thales commissioned specialists to assess the card’s Evaluation Assurance Level (EAL), an internationally recognised measure of security in IT products. Thales’ product won EAL6+ certification (the highest is EAL7).

As a result, it was certified by ANSSI, France’s national cybersecurity agency. The award made Thales the world’s first company to receive a high-level PQC product certification.

From an end-user perspective, nothing changes: citizens will continue to use their cards as usual. But the new generation cryptographic signature inside ensures the card will protect sensitive personal data if and when Q day arrives.
 

The roadmap to quantum-safe identity

The countdown to Q-Day has started. PQC looks set to reshape cybersecurity across all critical infrastructures. Products such as Thales’ certified PQC smartcard are proof that quantum-safe identity is no longer theoretical — it’s real, certified and ready.

Governments and industries should start planning their migrations now. Digital trust in the quantum era starts today.

＊Gartner®, Postquantum Cryptography: The Time to Prepare Is Now!, Mark Horvath et al., 1 July 2024
The Gartner content described herein (the “Gartner Content”) represents research opinion or viewpoints published, as part of a syndicated subscription service, by Gartner, Inc. ("Gartner"), and is not a representation of fact. Gartner Content speaks as of its original publication date, and the opinions expressed in the Gartner Content are subject to change without notice.
GARTNER is a registered trademark and service mark of Gartner, Inc. and/or its affiliates in the U.S. and internationally and is used herein with permission. All rights reserved.