PQC Explained: Which Cryptographic Algorithms Quantum Breaks

Which cryptographic algorithms quantum computing breaks

Quantum computing breaks public key cryptography, not encryption as a whole. RSA, ECDSA, EdDSA, ECDH and Diffie-Hellman fail outright to Shor's algorithm and must be replaced. Symmetric algorithms such as AES and hash functions such as SHA-2 are weakened by Grover's algorithm and require larger parameters rather than replacement.

How does quantum computing break cryptography?

The distinction between what fails and what survives comes down to which mathematical problem an algorithm relies on for its security.

Public key cryptography derives its strength from structured problems: integer factorisation for RSA, and the discrete logarithm problem for Diffie-Hellman and elliptic curve schemes. Shor's algorithm, published in 1994, solves both in polynomial time on a sufficiently capable quantum computer. This is a complete break. The private key is recovered from the public key, and increasing key length offers no meaningful protection because the required work grows slowly with key size.

Symmetric cryptography and hash functions rely on the absence of structure. The only general attack is search, and Grover's algorithm provides a quadratic speed-up for search. That halves the effective security level of a symmetric key. It is a significant reduction, but it is a predictable one that can be absorbed by using longer keys.

The practical consequence is that the migration is asymmetric in scope. Certificates, key exchange, digital signatures, code signing and authentication are affected. Bulk data encryption largely is not.

Which algorithms quantum computing breaks outright

The following algorithms provide no security against an adversary with a cryptographically relevant quantum computer, regardless of key size.

Every one of these is disallowed under NIST IR 8547 by 2035, and deprecated from 2030. The same set is covered by the NCSC migration timelines, which expect the highest-priority replacements to be complete by 2031.

Which algorithms quantum computing does not break

Symmetric algorithms and hash functions remain usable, with parameter adjustments already reflected in current guidance.

Two qualifications are worth stating precisely. First, Grover's algorithm is inherently sequential and parallelises poorly, so the practical attack cost against AES-128 is considerably higher than the theoretical 64-bit figure suggests. Second, guidance has nonetheless standardised on AES-256 and SHA-384, and compliance is judged against the guidance rather than against the underlying analysis. Under the US CNSA 2.0 suite, AES-256 and SHA-384 or SHA-512 are mandatory for national security systems.

Where quantum-vulnerable algorithms sit in a typical estate

The algorithm list is short. Its footprint is not, which is why the inventory is the difficult part of the work rather than the cryptography.

Public key algorithms appear in TLS termination and every certificate in the chain above it, in SSH host and user keys, in IPsec and VPN key exchange, in S/MIME and PGP email, in code signing and firmware signing, in document signing and long-term validation, in JWT and OpenID Connect token signing, in database and storage key wrapping, in smartcard and derived credential issuance, and in the root and issuing certificate authorities that underpin all of it.

The estate positions that cause most difficulty are the ones with the longest replacement cycles. Hardware roots of trust hold keys that may be embedded for the service life of a device. Firmware verification keys are frequently burned into silicon and cannot be rotated at all. Industrial controllers and airside, rail and medical devices installed today will still be operating past 2035. These are the assets to identify first, because the constraint on them is procurement rather than configuration.

A cryptographic bill of materials is the mechanism for recording this, and it is the prerequisite for any credible migration plan.

What replaces the broken algorithms

NIST published the first post-quantum standards on 13 August 2024, and added a stateful signature standard and a backup key encapsulation mechanism subsequently.

Selection is driven by constraint rather than preference. ML-KEM and ML-DSA are the general-purpose answer and are the algorithms shipping in mainstream libraries and platforms. SLH-DSA is appropriate where signature size can be tolerated and where the conservative security assumptions of a hash-based construction are required. LMS and XMSS are the correct answer for firmware and boot verification, because they were approved earlier and are already supported in hardware, though they impose a state management requirement that makes them unsuitable for general use.

HQC exists because ML-KEM rests on structured lattice assumptions. Holding a backup based on different mathematics is a direct response to the fact that algorithms are broken from time to time, including during standardisation.

Practical consequences of the replacements

The new algorithms are not drop-in substitutes, and the differences show up in operations before they show up in security.

Key and signature sizes increase substantially. An ML-KEM-768 public key is around 1,184 bytes against 32 bytes for X25519. An ML-DSA-65 signature is around 3,309 bytes against 64 bytes for ECDSA P-256. SLH-DSA signatures range from roughly 8 to 30 kilobytes. Certificate chains grow accordingly, which affects TLS handshake size, embedded device storage, smartcard capacity and any protocol with a fixed message limit.

In field terms, the failures encountered first are rarely cryptographic. They are buffer sizes, hardcoded field lengths, MTU and fragmentation behaviour, and appliances that reject certificates above a size the vendor never expected. This is the main argument for a test environment: the interoperability problems are discoverable in advance and are cheap to fix before deployment and expensive afterwards.

Common misconceptions

The first is that quantum computing breaks all encryption. It does not. It breaks the public key layer, which is enough to compromise most systems, but AES-256 encrypted data remains protected.

The second is that longer RSA keys buy time. RSA-4096 offers no meaningful additional resistance to Shor's algorithm, and moving to it consumes migration effort that should be spent on replacement.

The third is that hash functions are finished. Collision resistance is reduced, not eliminated, and SHA-384 remains sound. Hash-based signatures are in fact among the most conservative post-quantum options available.

The fourth is that the work is a straight algorithm swap. It is a change to key sizes, protocol behaviour, hardware capability and supplier dependency, which is why crypto agility is the objective rather than any single algorithm.

How Unsung helps

Unsung is a UK-based, vendor-neutral consultancy specialising exclusively in public key infrastructure and cryptographic systems, working across central government, defence, healthcare, financial services and critical national infrastructure.

We establish which quantum-vulnerable algorithms are in use and where, through our PKI health check and cryptographic bill of materials services, then design the replacement architecture and the certificate lifecycle management capability required to deploy it. Algorithm selection is made against the constraints of the estate, not against a vendor's product set.

For the timing question, see our analysis of the three timelines used in quantum risk assessment.