PKI Workshop

What is PKI?

Public Key Infrastructure (PKI) is a framework of policies, hardware, software, and procedures for creating, managing, distributing, and revoking digital certificates. Defined by ITU-T X.509 and profiled for the internet in RFC 5280, PKI enables entities to establish trust through a hierarchy of Certificate Authorities (CAs) that vouch for the binding between a public key and an identity.

The Certificate Lifecycle

Every X.509 certificate follows a defined lifecycle from key generation through revocation. RFC 5280 Section 3 describes the certificate path processing model, while RFC 6960 (OCSP) and RFC 5280 Section 5 (CRLs) define the revocation checking mechanisms that relying parties use to verify certificate validity in real time.

X.509 Certificate Structure

An X.509v3 certificate (RFC 5280 Section 4.1) contains three main parts: the TBSCertificate (to-be-signed data), the signature algorithm identifier, and the digital signature value. The TBSCertificate holds all the fields that get signed by the CA:

Digital Signatures in PKI

Certificate issuance and verification rely on digital signatures as defined in RFC 5280 Section 4.1.1.2. The CA signs the TBSCertificate using its private key, and any relying party can verify the signature using the CA's public key from a trusted root store.

Classical vs PQC Algorithms in PKI

Traditional PKI relies on RSA and ECDSA signatures, both vulnerable to Shor's algorithm on a cryptographically relevant quantum computer. NIST has standardized post-quantum replacements: ML-DSA (FIPS 204) for lattice-based signatures and SLH-DSA (FIPS 205) for stateless hash-based signatures.

PQC Migration for PKI

Root CA certificates can have lifetimes of 20+ years. While data encryption is vulnerable to "harvest now, decrypt later" attacks, long-lived CAs are vulnerable to "forge later" attacks, where a cryptographically relevant quantum computer could forge signatures and issue rogue certificates. NIST IR 8547 recommends beginning the transition to post-quantum algorithms immediately, with CNSA 2.0 (NSA) requiring exclusive PQC use in national security systems by 2033 for large PKI systems (2030 for software/firmware signing and networking equipment).

Key migration challenges include certificate size growth (ML-DSA-87 public keys are ~2,592 bytes vs ~91 bytes (SPKI) for ECDSA P-256), constrained device support, and maintaining cross-signed trust chains during the transition period. NIST SP 800-131A Rev 2 provides guidance on algorithm deprecation timelines.

Merkle Tree Certificates: Solving PQC Certificate Bloat

Post-quantum signatures are dramatically larger than their classical counterparts: ML-DSA-44 signatures are 2,420 bytes compared to just 64 bytes for ECDSA P-256 — a 37× increase. A typical TLS certificate chain with three PQ signatures, public keys, and Certificate Transparency SCTs can add 18–36 KB to every handshake, breaking constrained clients and degrading performance.

Merkle Tree Certificates (MTCs), proposed in IETF draft-davidben-tls-merkle-tree-certs by Google and Cloudflare, offer an elegant solution: instead of signing each certificate individually, a Merkle Tree CA (MTCA) batches thousands of certificates as leaves in a Merkle tree, signs only the root hash, and distributes compact inclusion proofs (~736 bytes) that let any relying party verify a certificate belongs to the signed batch. This replaces three separate PQ signatures with a single root signature plus a hash-based proof.