News for hackers. Stuff that matters.
Re:ML-KEM Mythbusting by westurner on Thursday November 27, 2025 @07:14PM (#46074381)
From 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/ :

> 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?

Re:ML-KEM Mythbusting by durumcrustulum on Thursday November 27, 2025 @10:48PM (#46075336)
ML-KEM is a key establishment scheme, not a signature scheme.
Re:ML-KEM Mythbusting by westurner on Friday November 28, 2025 @02:41AM (#46076436)
From 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

"KEM-based Authentication for TLS 1.3" 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-wigg...
Re:ML-KEM Mythbusting by westurner on Friday November 28, 2025 @02:54AM (#46076499)
Is 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.

Re:ML-KEM Mythbusting by durumcrustulum on Friday November 28, 2025 @08:03AM (#46078288)
What "the thing"? AuthKEM isn't being deployed anywhere.
Re:ML-KEM Mythbusting by westurner on Friday November 28, 2025 @01:08PM (#46081119)
How much more complex is the difference than 2.4 KB w/ ML-DSA or ~1 KB w/ ML-KEM?
Re:ML-KEM Mythbusting by durumcrustulum on Monday December 01, 2025 @07:34PM (#46115712)
I'm sorry I don't understand what you're asking
Re:ML-KEM Mythbusting by westurner on Tuesday December 02, 2025 @11:27PM (#46130301)
Though 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.