5 ms·
From https://news.ycombinator.com/item?id=45743372 https://news.ycombinator.com/item?id=45743372 re: the Cloudflare Merkle Tree draft: > Problem is PQ signatur
by westurner 11mo ago
From https://news.ycombinator.com/item?id=45743372 https://news.ycombinator.com/item?id=45743372 re: the Cloudflare Merkle Tree draft:
> Problem is PQ signatures are large. If certificate chain is small that could be acceptable, but if the chain is large, then it can be expensive in terms of bandwidth and computation during TLS handshake. That is the exchange sends many certificates which embed a signature and a large (PQ) public key.
> Merkle Tree Certificates ensures that an up to date client only needs 1 signature, 1 public key, 1 merkle tree witness.
> Looking at an MTC generated certificate they've replaced the traditional signing algorithm and signature with a witness.
> That means all a client needs is a signed merkle root which comes from an expanding Merkle Tree signed by the MTCA (Merkle Tree CA), which is delivered somehow out of band.
From "Keeping the Internet fast and secure: introducing Merkle Tree Certificates" (2025-10) https://blog.cloudflare.com/bootstrap-mtc/ https://blog.cloudflare.com/bootstrap-mtc/ :
> The central problem is the sheer size of these new algorithms: signatures for ML-DSA-44, one of the most performant PQ algorithms standardized by NIST, are 2,420 bytes long, compared to just 64 bytes for ECDSA-P256, the most popular non-PQ signature in use today; and its public keys are 1,312 bytes long, compared to just 64 bytes for ECDSA. That's a roughly 20-fold increase in size. Worse yet, the average TLS handshake includes a number of public keys and signatures, adding up to 10s of kilobytes of overhead per handshake. This is enough to have a noticeable impact on the performance of TLS.
Are ML-KEM certs impractically large too?
- durumcrustulum 11mo agoML-KEM is a key establishment scheme, not a signature scheme.
- westurner 11mo agoFrom Gemini then: Algorithm Role Public Key Size Signature / Ciphertext Size ECDSA P-256 (Identity / Signing) ~64 bytes ~64 bytes X25519 (Key Exchange) 32 bytes 32 bytes ML-DSA-44 (PQ; Identity / Signing) 1,312 bytes 2,420 bytes ML-KEM-768 (PQ; Key Exchange) 1,184 bytes 1,088 bytes > If you tried to make "ML-KEM Certificates" (using a newer mechanism called AuthKEM where you authenticate by proving you can decrypt a challenge rather than signing), you would replace the ~2.4 KB ML-DSA signature with a ~1 KB ML-KEM ciphertext. This saves about 50% of the bandwidth compared to ML-DSA, but it is still roughly 35x larger than a traditional ECC certificate chain. /? AuthKEM: kemtls/draft-celi-wiggers-tls-authkem: https://github.com/kemtls/draft-celi-wiggers-tls-authkem https://github.com/kemtls/draft-celi-wiggers-tls-authkem "KEM-based Authentication for TLS 1.3" https://kemtls.org/draft-celi-wiggers-tls-authkem/draft-celi-wiggers-tls-authkem.html https://kemtls.org/draft-celi-wiggers-tls-authkem/draft-celi... : > Table 1. Size comparison of public-key cryptography in TLS 1.3 and AuthKEM handshakes. Handshake HS auth algorithm HS Auth bytes Certificate chain bytes Sum ... AuthKEM Kyber-768 2272 6152 (Dilithium-2) 8424 AuthKEM Kyber-768 2272 2229 (Falcon-512) 4564 "KEM-based pre-shared-key handshakes for TLS 1.3" > "2.2. Key Encapsulation Mechanisms", "3. Abbreviated AuthKEM with pre-shared public KEM keys": https://kemtls.org/draft-celi-wiggers-tls-authkem/draft-wiggers-tls-authkem-psk.html#section-2.2 https://kemtls.org/draft-celi-wiggers-tls-authkem/draft-wigg...
- westurner 11mo agoIs this the thing with ML-KEM, then: > [With AuthKEM,] you would replace the ~2.4 KB ML-DSA signature with a ~1 KB ML-KEM ciphertext.
- durumcrustulum 11mo agoWhat "the thing"? AuthKEM isn't being deployed anywhere.
- westurner 11mo agoHow much more complex is the difference than 2.4 KB w/ ML-DSA or ~1 KB w/ ML-KEM?
- durumcrustulum 11mo agoI'm sorry I don't understand what you're asking
- westurner 11mo agoThough there is a difference between a cert signature (ML-DSA) and a challenge (ML-KEM), ultimately and fundamentally, isn't real key size still a relevant metric for comparison. (Everyone dnvoted this like -6/-7. I guess they didn't understand the relevance.) IDK a terse analogy then: MerkleCerts + ML-DSA : ML-DSA :: Challenge (ML-KEM,) : ____ (ML-DSA) Merkle-signing cert trust roots is a security/bytes-transferred efficiency tradeoff. What is the difference in number of bytes seemed usefully relevant to me at least.