Post-Quantum Cryptography Has Deadlines. Start With the Inventory.

Bottom line. A large, error-corrected quantum computer would break the public-key cryptography that protects most digital systems today. No such machine exists yet. But the replacement standards are published, Canada has set federal migration dates of 2031 and 2035, and migrations of this kind take years. Organizations holding data that must stay confidential for a decade or more should start now, and the first step is an inventory.

What a quantum computer would break, and what it would not

Public-key cryptography lets two parties who have never met agree on a secret key and verify each other’s identity. Today it rests mainly on two mathematical problems: factoring large numbers (the basis of RSA) and the discrete logarithm problem on elliptic curves (the basis of elliptic-curve cryptography, or ECC). In 1994, Peter Shor showed that a sufficiently large quantum computer could solve both efficiently [1]. A machine able to do this at practical key sizes is often called a cryptographically relevant quantum computer.

Symmetric encryption, such as the Advanced Encryption Standard (AES), and hash functions are far less exposed. The best known quantum attack on them gives at most a quadratic speed-up, which longer keys offset. The migration problem is therefore concentrated in key exchange and digital signatures.

The replacement standards exist

In August 2024, the United States National Institute of Standards and Technology (NIST) published the first three post-quantum cryptography (PQC) standards as Federal Information Processing Standards (FIPS) [2]. These algorithms run on ordinary computers. They are designed to resist attack by both classical and quantum machines.

ML-KEM stands for Module-Lattice-Based Key-Encapsulation Mechanism. ML-DSA and SLH-DSA are the Module-Lattice-Based and Stateless Hash-Based Digital Signature Algorithms. In March 2025, NIST selected a further key-establishment algorithm, Hamming Quasi-Cyclic (HQC), as a backup to ML-KEM built on different mathematics [3]. A signature standard based on the FALCON algorithm is also in development.

The deadlines are set

Two documents set the pace for Canadian organizations and their suppliers:

• Canada. In June 2025, the Canadian Centre for Cyber Security published a roadmap for the Government of Canada’s non-classified systems. Departments are to deliver initial migration plans by April 2026, migrate high-priority systems by the end of 2031 and complete the remaining systems by the end of 2035 [4].
• United States. NIST’s draft transition guidance proposes deprecating quantum-vulnerable algorithms at the 112-bit security level, such as RSA-2048, after 2030, and disallowing quantum-vulnerable public-key algorithms after 2035 [5].

Suppliers to governments should expect these dates to appear in procurement requirements, whether or not they are regulated directly.

How far away is the threat?

Nobody can give a reliable date for a cryptographically relevant quantum computer. What can be measured is how the estimated requirement has moved. In 2019, Craig Gidney and Martin Ekerå estimated that factoring a 2048-bit RSA key would take about 8 hours on a machine with 20 million noisy physical qubits [6]. In 2025, Gidney revised the estimate to fewer than one million noisy qubits running for less than a week [7]. The required machine shrank by a factor of about 20 in six years, through better algorithms and error-correction techniques rather than better hardware.

The hardware is still far from that scale. Google’s Willow processor, announced in December 2024, has 105 physical qubits [8]. The gap is close to four orders of magnitude, and it is closing from both directions.

Why “not yet” is not a reason to wait

Two facts make waiting risky.

First, data can be recorded now and decrypted later. An adversary who stores encrypted traffic today can read it once a capable machine exists. This is known as “harvest now, decrypt later”. For data that must remain confidential for many years, the exposure has already begun.

Second, migration is slow. Cryptography sits inside protocols, software libraries, hardware security modules, embedded devices, certificates and partner integrations. Past transitions show the pace. NIST first deprecated the SHA-1 hash function for digital signatures in 2011, and set the end of 2030 as the date to phase it out completely [9].

Michele Mosca of the University of Waterloo expressed the risk as a simple inequality [10]. Let x be how long data must stay confidential, y how long migration will take, and z the time until a cryptographically relevant quantum computer exists. If x + y is greater than z, the data is at risk. The illustrative values below show why long-lived data comes first.

A practical starting sequence

1. Build a cryptographic inventory. List every place cryptography is used: protocols, libraries, certificates, keys, hardware modules, embedded devices and third-party services. Most organizations do not have this list, and nothing else can be planned without it.
2. Rank systems by the confidentiality life of their data. Use Mosca’s inequality to put long-lived data first.
3. Move key establishment first. Harvest-now attacks target encrypted data, so switching key exchange to ML-KEM protects against recording today. Forged signatures only matter once a quantum computer exists, so most signatures can follow. The exception is long-lived roots of trust, such as firmware signing keys.
4. Use hybrid modes during the transition. Combining a classical and a post-quantum algorithm protects against both quantum attack and undiscovered weaknesses in the newer algorithms.
5. Design for crypto-agility. Make algorithms configurable rather than hard-coded, so the next change takes months rather than years.
6. Ask suppliers for their roadmaps. Most post-quantum capability will arrive through products already in use. Supplier timelines belong in the plan.

Conclusion

Quantum computing timelines are uncertain. Migration timelines are not: the standards are published, the deadlines are set and the work takes years. An organization that starts its inventory this year can migrate on its own schedule. One that waits for a quantum headline will migrate on someone else’s.

References

1. P. W. Shor, “Algorithms for quantum computation: Discrete logarithms and factoring,” in Proc. 35th Annu. Symp. Foundations of Computer Science (FOCS), 1994, pp. 124-134.
2. National Institute of Standards and Technology, FIPS 203, FIPS 204 and FIPS 205, Aug. 2024.
3. National Institute of Standards and Technology, “NIST selects HQC as fifth algorithm for post-quantum encryption,” Mar. 2025.
4. Canadian Centre for Cyber Security, “Roadmap for the migration to post-quantum cryptography for the Government of Canada (ITSM.40.001),” Jun. 2025.
5. D. Moody, R. Perlner, A. Regenscheid, A. Robinson, and D. Cooper, “Transition to post-quantum cryptography standards,” NIST IR 8547 (Initial Public Draft), Nov. 2024.
6. C. Gidney and M. Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,” Quantum, vol. 5, p. 433, 2021 (preprint 2019).
7. C. Gidney, “How to factor 2048 bit RSA integers with less than a million noisy qubits,” arXiv:2505.15917, May 2025.
8. H. Neven, “Meet Willow, our state-of-the-art quantum chip,” Google, Dec. 2024.
9. National Institute of Standards and Technology, “NIST retires SHA-1 cryptographic algorithm,” Dec. 2022.
10. M. Mosca, “Cybersecurity in an era with quantum computers: Will we be ready?,” IEEE Security & Privacy, vol. 16, no. 5, pp. 38-41, 2018.