up:: Classical Cryptography MOC

Public Key Infrastructure (PKI)

Public Key Infrastructure (PKI) is the trust system that lets computers verify who they’re talking to, by binding public keys to real-world identities with digitally signed certificates and organizing those certificates into chains that trace up to a small set of trusted anchors. It’s the machinery behind every HTTPS padlock, every signed software update, and every certificate-authenticated login. PKI is not a single algorithm; it’s an infrastructure of policies, hardware, and credentials that uses RSA and ECDSA signatures with the X.509 certificate format to answer one question at scale, does this public key really belong to who it claims to?

The short version:

• PKI answers a single question: is this public key genuinely the one for this identity? It answers with a signed certificate, where a certificate authority vouches for the binding.
• It’s built from certificate authorities, X.509 certificates, chains of trust, trust stores, and revocation infrastructure, all working together.
• Every secure web connection, signed binary, and certificate-based login depends on PKI to establish who is trustworthy.
• It’s the highest-blast-radius surface in the quantum transition, because one broken CA signing key forges every certificate underneath it at once, the failure known as PKI collapse.
• Migrating a PKI means moving the CA’s own signing keys to ML-DSA or SLH-DSA, planning trust-store distribution across the whole ecosystem, and bridging the gap with composite certificates and cross-certification.

An everyday analogy

Picture a large gathering where you trust a stranger because of a chain of introductions. There’s a host everyone in the room already knows and trusts. The host personally vouches for a handful of lieutenants, and each lieutenant introduces the guests they brought. When you meet a guest you’ve never seen, you trace the introductions back rather than verifying from scratch, this guest was vouched for by a lieutenant, who was vouched for by the host, and since you trust the host, you extend that trust down the chain. The host is a root certificate authority, the lieutenants are intermediate CAs, and the guests are end-entity certificates. Your personal short list of hosts you’ve decided to trust is your trust store. And when word gets around that someone’s vouch is no good, that’s revocation.

What is public key infrastructure?

PKI is the framework that makes public-key cryptography usable between parties who have never met. Public-key crypto lets anyone encrypt to your public key or verify your signatures, but only if they have the right public key. PKI is the system that gets them the right one and proves it. It provides four capabilities:

1. Certification. Binding a public key to an identity by wrapping it in a certificate that a trusted authority digitally signs.
2. Distribution. Publishing and transmitting certificates so relying parties can obtain them, typically served during a connection handshake.
3. Revocation. Telling relying parties that a certificate should stop being trusted, before it naturally expires.
4. Path validation. Checking that a certificate’s signature chain traces cleanly up to a root the validator already trusts.

The certificate format underneath almost all of this is X.509, defined for Internet use by RFC 5280. An X.509 certificate carries the subject’s public key, the subject and issuer names, a validity period, the intended key-usage constraints, and the issuing CA’s signature over all of it. The whole trust model rests on one property: only the CA can produce a valid signature over a certificate, so a certificate can’t be forged without the CA’s private key. That property is exactly what a quantum computer threatens, because the RSA and ECDSA algorithms CAs sign with are both broken by Shor’s algorithm.

Source: IETF, “Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile,” RFC 5280, May 2008, RFC 5280.

How does PKI actually work?

Trust in PKI flows downward through a chain of signatures, and it starts from a deliberately small number of anchors. A root CA signs itself and its public key is baked into operating-system, browser, and runtime trust stores; it’s kept offline and used rarely. The root signs one or more intermediate CAs, which handle the day-to-day work of issuing certificates. Intermediates issue end-entity certificates to specific websites, people, and devices. A relying party believes an end-entity’s identity because it can verify each signature in the chain up to a root it already trusts. Break any signature in that chain and everything below it becomes forgeable, which is why the keys at the top matter most.

The moving parts fit together like this:

Component	Role in the trust system
Root CA	Self-signed trust anchor; kept offline in hardware security modules and embedded directly in trust stores
Intermediate CA	Signed by the root; performs day-to-day issuance and isolates the root so a compromised intermediate doesn’t force an immediate root change
End-entity certificate	Issued to a domain, person, or device; used in TLS, code signing, email, and device authentication
Registration Authority (RA)	Vets the identity behind a certificate request before the CA signs, keeping identity-checking separate from key material
Revocation infrastructure	CRLs and OCSP tell relying parties that a certificate has been withdrawn from trust ahead of its expiry
Trust store	The set of root CAs a system trusts; chain validation succeeds only when the chain roots to an entry here

Two pieces of that table deserve their own note. Trust stores are why a certificate that’s valid on one machine can fail on another, since every operating system, browser, and runtime keeps its own independent list of trusted roots, and validation only succeeds if the chain lands on a root in that list. This is the single most important fact for the quantum migration, because getting a new root trusted everywhere means shipping updates to every one of those stores. Revocation is how trust gets pulled back early, through a Certificate Revocation List (a periodically published list of revoked serial numbers, defined in RFC 5280) or the Online Certificate Status Protocol (a real-time status query, RFC 6960), often optimized with OCSP stapling so the server presents a pre-signed status response during the handshake (RFC 6066).

Sources: IETF, “X.509 Internet Public Key Infrastructure Online Certificate Status Protocol - OCSP,” RFC 6960, June 2013, RFC 6960.

IETF, “Transport Layer Security (TLS) Extensions, Extension Definitions,” RFC 6066, January 2011, RFC 6066.

Where is PKI used in real systems?

Almost everywhere trust has to be established between parties who can’t rely on a shared secret. The reach is much wider than the web certificates most people picture:

1. TLS and HTTPS. Every web server presents an X.509 certificate during the TLS handshake to prove its identity. PKI handles the authentication half of TLS; a separate key exchange handles the confidentiality half.
2. Code and firmware signing. Operating-system updates, application packages, drivers, and firmware are signed under code-signing CAs, so a device can confirm an update genuinely came from the vendor.
3. Email security. S/MIME uses X.509 certificates to sign and encrypt email, binding an address to a public key.
4. Client and device authentication. Enterprise VPNs, 802.1X and EAP-TLS Wi-Fi, and zero-trust access use client certificates to authenticate users and machines, usually issued by internal enterprise PKI.
5. Document signing. Legal, financial, and government workflows use certificates for non-repudiable signatures on PDFs and other documents.
6. Identity federation. SAML assertions, JWT access tokens, and OAuth codes are signed with keys managed under PKI constructs, so one login can be trusted across many services.

The theme across all of these is the same: PKI is the authentication and identity layer. It proves who, while confidentiality (keeping the contents secret) is a separate mechanism handled by key establishment, which matters a lot for how the quantum migration splits into two programs.

Why is PKI the highest-blast-radius surface in the quantum transition?

Because a CA signing key is a trust multiplier, and its matching public key is already sitting in the open. A single root or intermediate CA vouches for a huge population of certificates, so the blast radius of breaking one key isn’t one system, it’s everything that key underwrites. Here’s the chain of reasoning:

1. The target is public by design. A CA’s public signing key appears in its certificate, which is published in trust stores, served on handshakes, and logged in Certificate Transparency records (RFC 6962). There’s no traffic to intercept and no vault to breach; the input an attacker needs is already published.
2. Shor’s algorithm turns that public key into the private one. A cryptographically relevant quantum computer running Shor’s algorithm recovers the private signing key from the public key for both RSA and ECDSA. Notably, the CA’s own physical security, HSMs, and access controls are all irrelevant to this step, because the key is computed rather than stolen.
3. One broken CA forges everything beneath it. With the private key, an attacker can mint certificates that are cryptographically valid for any name they choose, and each one passes standard validation because the signature is mathematically correct and chains to a trusted root. The worst case, a broken widely-trusted root, is PKI collapse, where trust for potentially millions of systems fails at once.

This is a trust threat, not a secrecy one, which puts it squarely in the Non-HNDL class of quantum attacks: it targets integrity and authentication in real time and needs a live quantum computer at the moment of attack. It sits opposite harvest-now-decrypt-later, which threatens confidentiality. Grover’s algorithm doesn’t factor into PKI signing at all; this is a public-key break, not a symmetric-key search. For the full mechanics of the catastrophe and the published qubit resource estimates behind it, PKI collapse is the deep-dive.

Source: IETF, “Certificate Transparency,” RFC 6962, June 2013, RFC 6962.

How do you migrate a PKI to post-quantum cryptography?

Migrating a PKI means changing the algorithms inside the infrastructure while the infrastructure keeps running, and doing it from the top of the trust chain down. The certificate architecture survives; the signatures within it move to NIST’s standardized post-quantum algorithms. Four realities make this the hardest migration item in the whole transition:

1. The CA’s own signing keys move first. The highest-blast-radius keys are the root and intermediate CA keys, so those are the ones that have to migrate from RSA and ECDSA to a post-quantum signature. Reissuing leaf certificates while the CA key stays classical leaves the real vulnerability in place.
2. Trust-store distribution is the binding constraint. A new post-quantum root only becomes usable once it’s trusted by every relying party, which means shipping it into operating-system trust stores, browser root programs, and language runtimes across the entire fleet. No single organization controls that timeline, and it moves at the speed of update cycles, which is why this is measured in years.
3. The plumbing has to be ready before the certificates are. CA private keys live in hardware security modules that must support the new algorithms, generating new roots requires formal air-gapped key ceremonies, and every certificate parser, TLS library, OCSP responder, and CRL processor has to recognize the new algorithm identifiers before a post-quantum certificate is valid in production.
4. The whole thing runs on a fixed clock. U.S. national-security policy sets 2035 as the outer date for completing the transition, and since re-rooting a large PKI takes years against that fixed deadline, the planning problem is live now even though a capable quantum computer doesn’t exist yet.

The replacement algorithms, and the one adjacent program that’s often confused with PKI migration:

Replace	With	Best for
RSA / ECDSA CA and certificate signatures	ML-DSA	General-purpose certificate and CA signing, the primary choice
RSA / ECDSA long-lived root signatures	SLH-DSA	Conservative hash-based backstop for very long-lived or high-assurance roots
ECDH / RSA key establishment in TLS	ML-KEM	The confidentiality half of the transition, adjacent to PKI but a separate program

Because a PKI ecosystem can’t flip all at once, the transition usually runs through bridging structures rather than a single cutover:

1. Composite certificates carry both a classical and a post-quantum signature in one certificate, so post-quantum-aware verifiers get post-quantum security while older clients still validate the classical part.
2. Dual signatures and parallel trust chains run a classical and a post-quantum hierarchy side by side, so relying parties can upgrade in stages instead of in lockstep.
3. Cross-certification lets an existing CA vouch for a new post-quantum CA before every trust store has been updated, smoothing the root-distribution problem.
4. Crypto-agility first. A PKI that hardcodes its signing algorithm faces the longest and most painful migration, so the ability to change algorithms without rebuilding the infrastructure is the precondition that makes every bridging step above possible.

One more standard is still on the way: FN-DSA, to be published as FIPS 206 for size- and speed-constrained cases, is in draft and not yet finalized.

Sources: NIST, “Module-Lattice-Based Digital Signature Standard,” FIPS 204, August 2024, FIPS 204.

NIST, “Stateless Hash-Based Digital Signature Standard,” FIPS 205, August 2024, FIPS 205.

NIST, “Module-Lattice-Based Key-Encapsulation Mechanism Standard,” FIPS 203, August 2024, FIPS 203.

NSA, “CNSA 2.0 FAQ” (PP-24-4014, December 2024 update), which sets 2035 as the completion date for the National Security Systems transition, CNSA 2.0 FAQ.

NIST, “Post-Quantum Cryptography,” which lists ML-KEM, ML-DSA, and SLH-DSA as finalized in 2024 and FN-DSA (FIPS 206) as forthcoming, NIST PQC project.

What looks like a fix but isn’t?

Several plausible-sounding moves leave the actual vulnerability untouched, and they’re worth naming because teams reach for them first:

1. Reissuing leaf certificates without migrating the CA key. Rotating all the end-entity certificates feels like progress, but if the CA’s own signing key is still classical, an attacker forges from the CA and every fresh leaf is just as forgeable. The vulnerable key is the one at the top of the chain.
2. Bumping RSA to 4096 bits. A larger RSA key raises the quantum cost only slightly, because Shor’s algorithm scales polynomially in key length rather than hitting the exponential wall that stops classical attacks. It adds classical overhead and buys almost nothing against a CRQC.
3. Certificate pinning. Pinning a certificate or public key hardens against a rogue-issuance attack, but it pins a still-classical, still-forgeable key. Once the underlying signature is breakable, pinning the breakable thing doesn’t help.
4. Assuming vendors will handle all of it. Operating-system trust stores, public-CA root programs, and appliance firmware are vendor-controlled surfaces, and waiting on them is reasonable for the parts they own. It’s a genuine plan only for those parts; private enterprise PKI, code signing, and device identity that an organization runs itself still have to be migrated by that organization.

Common misconceptions

1. “PKI is just an algorithm you swap out.” PKI is an infrastructure of CAs, certificates, trust stores, and revocation, and the algorithms live inside it. The migration keeps the architecture and changes the signatures within it, which is precisely what makes it slow.
2. “Migrating my TLS certificates is the migration.” Public TLS leaf certificates are the easy, fast part. The long pole is migrating the CA signing keys and getting new roots trusted across every trust store, which is a multi-year, ecosystem-wide effort.
3. “Only the public web PKI matters.” Internal enterprise PKI, code signing, firmware, device identity, and machine certificates are usually a larger and more fragile trust surface than the public certificates people picture, and all of them belong in a CBOM.
4. “PKI protects the secrecy of my data.” PKI establishes identity and trust, which is authentication and integrity. Confidentiality of the data in transit is handled separately by the key exchange, and it’s threatened by a different quantum attack, HNDL.
5. “An attacker has to break into the CA.” For the quantum threat, the private key is computed from the published public key, so the CA is never touched. Its HSMs and physical security are irrelevant to that break.
6. “We can wait, since a quantum computer doesn’t exist yet.” The forgery waits for the machine, but the defense is a multi-year re-rooting against a fixed 2035 deadline, so the planning problem is present-day.

Questions people ask

What’s the difference between PKI and a certificate authority? A certificate authority is one component of PKI, the entity that issues and signs certificates. PKI is the whole system around it: the CAs, the X.509 certificate format, the chains of trust, the trust stores, and the revocation infrastructure that together make certificates usable at scale.

What is X.509? X.509 is the standard certificate format used in essentially all modern PKI, profiled for Internet use by RFC 5280. An X.509 certificate carries a public key, the subject and issuer identities, a validity period, key-usage constraints, and the issuing CA’s signature over all of it.

Is PKI affected by quantum computing? Yes, and severely. The RSA and ECDSA signatures that CAs use are broken by Shor’s algorithm on a sufficiently large quantum computer, which lets an attacker forge certificates under any CA whose key they break. Because one CA key underwrites many certificates, PKI carries the highest blast radius of any cryptographic system.

Which key has to be replaced first in a PKI migration? The CA signing keys, especially roots and intermediates, because they sit at the top of the trust chain and vouch for everything beneath them. Migrating leaf certificates while a CA key stays classical leaves the real exposure in place.

Why does migrating a PKI take years? The binding constraint is trust-store distribution. A new post-quantum root only works once it’s trusted everywhere, which means shipping it into operating-system, browser, and runtime trust stores across a global fleet, on update cycles no single organization controls. HSM readiness, key ceremonies, and validator updates add to it.

Do composite certificates replace the need to migrate? No, they’re a bridge during the migration. Composite certificates carry both a classical and a post-quantum signature so new and old clients both validate during the transition period, but the endpoint is still a fully post-quantum PKI.

Do I need to understand PKI to start a post-quantum migration? Yes, because PKI is where the highest-blast-radius signing keys live, and its trust-store distribution timeline is the longest lead time in the transition. Understanding the CA hierarchy is what tells you which keys to move first and why the schedule is measured in years.

Is this the same problem as harvest-now-decrypt-later? No. HNDL is a confidentiality threat closed by moving key establishment to ML-KEM. The PKI problem is a trust threat closed by moving signatures to ML-DSA and SLH-DSA. A complete migration handles both halves.

---

Everything here is the map, given freely. When your team needs its own certificate hierarchy found, sized, and sequenced onto a post-quantum path before the machine arrives, that’s the work I do. Request an alignment briefing.

Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.