Depending on the algorithm in question, post-quantum cryptography can produce signatures much larger than comparable traditional algorithms. ML-DSA-44, which is a standardized post-quantum signature scheme thought to have security similar to Ed25519 signatures, produces signatures 37 times larger. Naively adopting post-quantum signatures for authentication could cause certificate chains to take up more data than the actual content of the web site in question […]
The solution that the new working group (called “PKI, Logs, and Tree Signatures” or PLANTS) has been discussing inverts the relationship between signatures from certificate authorities and the transparency logs. Currently, a certificate authority first creates a certificate, then logs it in a certificate-transparency log, and then optionally includes the signature from the log in the certificate as a piece of additional information. This is, in some sense, redundant: the information that the certificate is valid is already present in the certificate-transparency log, so why send the client any information other than proof that it appears in the log?
Instead of having a chain of signatures in a certificate to represent some transitive relationship between a certificate authority and a root of trust, the third-party observers would add their signatures to a certificate authority’s log as they validate it. A browser can choose its own criteria for which third-party observers it trusts, and whether it requires a quorum of them before accepting the state of an issuance log.
The certificate seen by the client would therefore no longer be a chain of signatures leading back to a root of trust: it would be a set of signatures from the certificate authority and any relevant observers attesting to the state of the issuance log, plus a proof that the web server’s public key was included in the issuance log. This constitutes what PLANTS calls a “full” certificate. For an individual web site, a full certificate doesn’t decrease the number of needed signatures; but since the issuance logs are append-only, if a browser has already verified the issuance log for a certificate authority up to some checkpoint, it doesn’t need to see the signatures for that checkpoint again. Instead, it can ask the server to just send the proof that the server’s public key appeared in the log prior to that point — a “signatureless” certificate that should be substantially smaller.
To prove that a leaf node belongs to a tree with a given root node, it suffices to provide the hashes of the other nodes that are “adjacent” to the path from the leaf to the root […] The number of additional hashes to provide grows logarithmically with the size of the tree. And, since cryptographic hashes aren’t vulnerable to the same kinds of quantum attacks as public-key cryptography, the size of a Merkle inclusion proof like this doesn’t change when switching to post-quantum cryptography.
To prevent an issuance log from growing without bound, older entries are periodically pruned as they expire. This might seem to be at odds with the append-only nature of an issuance log, but since expired certificates shouldn’t validate correctly anyway, the certificate authority can delete the corresponding leaf nodes and any internal nodes that are therefore no longer usable in actual proofs. The tree maintains the same conceptual size, but the on-disk storage requirements remain proportional to the number of active certificates.