What Is Public Key Infrastructure — and Why Quantum Computers Break It

Two parties who have never communicated need to know they are genuinely talking to each other, not an impersonator. That is the problem Public Key Infrastructure (PKI) exists to solve. It does so through a chain of delegated trust: a root certificate authority (CA), whose key is embedded in operating systems and browsers by policy, signs an intermediate CA's certificate; the intermediate CA signs an end-entity certificate; the end-entity presents that certificate, and the relying party verifies the chain. RSA or ECDSA is the algorithm doing the signing at every link.

A cryptographically relevant quantum computer (CRQC) breaks those algorithms. Not by brute force. By solving the underlying mathematics efficiently. That distinction matters — it means longer key lengths do not help, and it means the problem is not confined to HTTPS in a browser. It runs through every system that depends on RSA or ECDSA, which is most of enterprise infrastructure.

Where PKI Actually Runs

Most CISOs know that TLS certificates use PKI. The list is longer than that, and the quantum exposure extends to every item on it.

Code signing authenticates software updates, container images, firmware, and executable binaries. Document signing underpins PDF signatures and eIDAS qualified signatures used for regulated filings across the EU. S/MIME secures email at the message layer. SSH uses RSA or ECDSA keys for host authentication and, in certificate-based deployments, client authentication. VPN gateways running IKEv2 over IPsec use certificates for authentication. IoT device identity and hardware attestation in TEE-based environments depend on certificate chains. JSON Web Tokens signed with RS256 or ES256 carry RSA and ECDSA keys into every API-first application stack. Firmware images for routers, PLCs, and HSMs carry signatures that may need to be validated years after the signing event.

Quantum vulnerability in PKI is not a web-browser problem. It is a systemic dependency embedded across every layer of enterprise infrastructure, and it has been there for decades.

Why Shor's Algorithm Breaks It

Peter Shor published his algorithm in 1994. It solves integer factorisation and the discrete logarithm problem in polynomial time on a quantum computer. RSA derives its security from factorisation being computationally hard; ECDSA derives its security from the discrete logarithm on elliptic curves being computationally hard. A CRQC running Shor's algorithm does not brute-force an RSA-2048 key — it solves the factorisation problem directly. The implication is confirmed in the academic record: Roetteler et al. at ASIACRYPT 2017 calculated the quantum resource estimates required to solve the elliptic curve discrete logarithm, establishing that ECDSA key sizes used in production PKI are within reach of a sufficiently capable quantum system.

Doubling the key size does not address this. The quantum speedup applies regardless of key length, within the practical range of deployed keys. The mathematical shortcut exists. Classical key size assumptions become irrelevant once that shortcut is available.

RFC 5280 defines the X.509 certificate structure that carries RSA and ECDSA keys across every PKI deployment. RFC 8446 specifies TLS 1.3. Both documents assume the hardness of integer factorisation and discrete logarithm. That assumption holds against classical adversaries. It does not hold against a CRQC.

Three Things That Do Not Fix the Problem

TLS 1.3 already handles this. It does not. RFC 8446 made significant protocol improvements — removing weak cipher suites, mandating forward secrecy for the key exchange phase, eliminating several downgrade attack vectors. The certificate authentication phase, where RSA or ECDSA is used to verify the server's identity, is unchanged. A TLS 1.3 session authenticated with an ECDSA P-256 certificate is fully quantum-vulnerable at the certificate layer. Upgrading to TLS 1.3 is correct hygiene for other threat models. It is not a quantum defence.

QKD replaces PKI. It does not. Quantum Key Distribution uses quantum optical channels to establish symmetric keys between two directly connected parties. It does not provide authentication — it cannot tell you whether the party at the other end of the fibre is who they claim to be. PKI exists precisely to answer that question. QKD and PKI operate at different layers; they are not substitutes. The NCSC stated this directly in its November 2023 QKD position paper: QKD is not a replacement for post-quantum cryptography. ETSI GR QKD 012 confirms the same architectural constraint — QKD scope is key distribution between fixed, trusted endpoints, not trust hierarchy construction.

Just rotate the certs. Certificate rotation generates a new key pair using the same algorithm. A rotated RSA-2048 certificate is still an RSA-2048 certificate. The vulnerability is in the algorithm, not the key value. Rotation is correct practice for other operational reasons; stating that clearly is not dismissing it. But it does not address algorithm-level quantum exposure. It also does not address retroactive exposure: the CISA/NSA/NIST Joint Advisory on Post-Quantum Cryptography (August 2023) explicitly frames harvest-now-decrypt-later (HNDL) attacks as a present-tense risk — encrypted traffic recorded before certificate rotation still carries the original key exchange data, and that data is at risk once a CRQC exists.

What Replaces It

NIST published three post-quantum standards in August 2024 that address the PKI failure mode directly.

FIPS 203 specifies ML-KEM (Module-Lattice-Based Key Encapsulation Mechanism), derived from the CRYSTALS-Kyber submission. ML-KEM replaces RSA and ECDH in key exchange contexts — TLS key agreement, IPsec IKEv2, SSH key negotiation. It generates and encapsulates a shared secret that is decapsulated by the recipient; the secret never traverses the network in a form that Shor's algorithm can attack.

FIPS 204 specifies ML-DSA (Module-Lattice-Based Digital Signature Algorithm), derived from CRYSTALS-Dilithium. ML-DSA is the migration target for RSA-PSS and ECDSA wherever signing is required: CA signing keys, TLS certificate chains, code signing, document signing, and email authentication. This is the algorithm that rebuilds the trust chains PKI depends on.

FIPS 205 specifies SLH-DSA (Stateless Hash-Based Digital Signature Algorithm), derived from SPHINCS+. SLH-DSA provides a conservative security basis for long-lived signing use cases — root CA keys and firmware signing where algorithm diversity beyond the MLWE assumption is operationally valuable. Its security rests solely on hash function assumptions, not lattice mathematics.

The IETF is standardising how these algorithms integrate into the existing protocol infrastructure. For TLS, two active Internet-Drafts define the migration path: draft-ietf-tls-ecdhe-mlkem-04 specifies a hybrid ECDHE-MLKEM mechanism for the transition period (both classical and post-quantum in parallel, so security holds while either remains unbroken); draft-ietf-tls-mlkem-07 specifies pure ML-KEM for full migration. For X.509 certificates, the LAMPS Working Group's draft-ietf-lamps-pq-composite-sigs-19 — currently in the RFC Editor Queue as of May 2026 — defines composite ML-DSA signatures for use in certificate chains. None of these documents is yet a published RFC; all are on the IETF standards track. NIST SP 1800-38A (Initial Public Draft) (NCCoE PQC Migration guidance) describes the PKI migration workstreams these drafts support.

One factual note on commercial CA vendors: they are migrating their certificate issuance capabilities. They are not responsible for the application-layer cryptography that consumes those certificates, or for the embedded legacy PKI hierarchies outside their issuance scope. The scope of a certificate management vendor's PQC roadmap and the scope of an organisation's actual quantum PKI exposure are two different things. Organisations that size their migration programme to match the former will find the latter is larger.

What the Timeline Looks Like

Root CA certificates issued today with RSA-4096 or ECDSA P-384 keys commonly carry validity periods of 20 to 25 years. Code-signing certificates have shorter validity periods, but the artefacts they sign — firmware, software packages — persist far longer in production environments. NIST IR 8547 (Initial Public Draft, November 2024) sets out the transition timeline for classical algorithms. NCSC guidance recommends that organisations identify PKI migration targets and begin hybrid deployments in the 2025–2028 window.

The migration order for PKI infrastructure is root CA first, intermediate CAs second, subscriber certificates third. Root CA migration requires co-ordination across every system trusting that root. It is the longest-lead item in any PKI migration programme, and it is the item most often deferred when organisations start with leaf certificates and work backwards.

For data with a confidentiality requirement longer than the expected CRQC arrival window, HNDL exposure means the migration deadline is already behind you, not ahead. That applies directly to long-lived regulated data — health records, financial audit trails, classified communications — where the sensitivity horizon exceeds the plausible quantum timeline.

Start with the inventory. The natural next step after understanding why PKI is vulnerable is identifying every location where your organisation runs it. Our coverage of cryptographic inventory and why it is the prerequisite for any migration programme covers the approach in detail. For a directional score of your organisation's quantum cryptographic exposure, including the weight of your PKI and trust infrastructure, QSECDEF's Post-Quantum Risk Assessment runs seven questions in your browser with no account required.