← Week 2: ML-KEM and ML-DSA

Day 12: ML-DSA Conceptual Walkthrough

Phase 3 · July 19, 2026

← Week 2: ML-KEM and ML-DSA

Agenda (2–3 hours)

  • Read (75 min): NIST FIPS 204 §1–3 (ML-DSA introduction and background, pp. 1–15)
  • Study (45 min): Signature scheme construction, security levels, parameter tradeoffs
  • Challenge (30 min): Compare ML-DSA to ECDSA on every practical dimension
← Week 2: ML-KEM and ML-DSA

ML-DSA in One Sentence

ML-DSA (formerly CRYSTALS-Dilithium) is a digital signature scheme based on
the hardness of the Module Short Integer Solution (MSIS) and MLWE problems.

It provides:

  • EUF-CMA security: existential unforgeability under chosen-message attacks
  • Deterministic or randomized signing (FIPS 204 supports both)
  • Fast verification: cheaper than signing (important for TLS, cert validation)
← Week 2: ML-KEM and ML-DSA

The Signature Construction: Fiat-Shamir with Aborts

ML-DSA uses a "commit → challenge → respond" (sigma protocol) structure:

[Sign(sk, msg)]
  y ← small random polynomial (nonce/commitment randomness)
  w = A·y                     (commitment)
  c ← H(w, msg, pk)           (challenge hash, "Fiat-Shamir")
  z = y + c·s                 (response)
  if z is "too large": ABORT and retry with fresh y
  signature = (c, z, hint)

[Verify(pk, msg, sig)]
  recover w' from (z, hint, c, pk)
  check c == H(w', msg, pk)

The abort step is critical: it prevents leaking information about the secret s
through a large response. This is conceptually similar to why ECDSA needs random k.

← Week 2: ML-KEM and ML-DSA

ML-DSA Parameters

ML-DSA-44 ML-DSA-65 ML-DSA-87
NIST level 2 3 5
Public key 1312 bytes 1952 bytes 2592 bytes
Private key 2528 bytes 4000 bytes 4864 bytes
Signature 2420 bytes 3293 bytes 4595 bytes
Sign ops/s (est.) ~2000 ~1300 ~900

Compare to ECDSA P-256: 64-byte public key, 64-byte signature, ~20,000 sign ops/s.

The signature size is the biggest practical impact on TLS: certificates using
ML-DSA-65 will be ~50× larger than ECDSA P-256 certificates.

← Week 2: ML-KEM and ML-DSA

Signing: Deterministic vs. Randomized

FIPS 204 defines two modes:

  • Deterministic (ML-DSA): y derived from H(sk, msg) — same message always gives same signature
  • Randomized (HashML-DSA): y includes fresh randomness — different signature each time

Deterministic mode risk: if the hash function is broken or the implementation
is incorrect, deterministic signing can leak the secret key. (Contrast with ECDSA
where a bad k is immediately catastrophic — ML-DSA is more robust to bad randomness.)

For provisioning services: deterministic mode is fine. Avoid randomized mode unless
there's a specific reason.

← Week 2: ML-KEM and ML-DSA

ML-DSA vs. ECDSA: Practical Comparison

Dimension ECDSA P-256 ML-DSA-65
Public key 64 bytes 1952 bytes
Signature 64 bytes 3293 bytes
Private key 32 bytes 4000 bytes
Sign time ~50 µs ~750 µs
Verify time ~150 µs ~200 µs
Security vs. quantum Broken (Shor's) Level 3
HSM support (2026) Universal Limited
Standardization 30+ years 2024

Verification is nearly as fast as classical — good for TLS clients who verify cert chains.

← Week 2: ML-KEM and ML-DSA

Challenge Assignment

Write a side-by-side comparison document: ECDSA P-256 vs. ML-DSA-65 for certificate signing

Cover:

  1. Key generation: time, storage cost, HSM support availability
  2. Signing: time and throughput implications for a CA that issues thousands of certs/day
  3. Verification: TLS handshake impact (verify 3 certs per connection)
  4. Certificate size: total chain size for a 3-cert hierarchy, TLS record implications
  5. Migration path: can you have one cert with both signatures during transition? (preview of Day 19)
  6. Overall recommendation: when should your team switch CA signing keys to ML-DSA?
← Week 2: ML-KEM and ML-DSA

Resources

  • NIST FIPS 204: §1 Introduction, §3 Mathematical background
  • CRYSTALS-Dilithium submission: pq-crystals.org/dilithium
  • "The Case for Dilithium": blog post on why Dilithium was selected over Falcon for general use