🔐 ML-DSA-44 Interactive Visualizer

1. Key Generation

First of all, a 32-byte random seed ξ is generated using a cryptographically secure random source provided by the operating system or hardware. This seed is then given to SHAKE256, which expands it into 128 bytes of deterministic output, split into three parts:

Matrix A is generated from ρ using ExpandA (SHAKE128 with row/column indices). For ML-DSA-44, A is a 4×4 matrix — 16 polynomials, each with 256 coefficients, giving 4096 coefficients total. Every coefficient is taken modulo q = 8,380,417, so values lie in [0, 8,380,416].

The two secret vectors s₁ and s₂ are generated from ρ′ using ExpandS (SHAKE256 + centered binomial distribution). With η = 2 for ML-DSA-44, coefficients are in {−2, −1, 0, 1, 2}. Each vector has 4 polynomials × 256 coefficients = 1024 coefficients.

Alice then calculates t = As₁ + s₂. Since A is 4×4 and s₁ is 4×1, the result is a 4×1 vector — four polynomials with 256 coefficients each (1024 coefficients total).

Storing every t coefficient uncompressed would need 23 bits each (since q < 2²³), giving 1024 × 23 / 8 = 2944 bytes — unnecessarily large. So ML-DSA uses Power2Round to split each coefficient:

t₁ holds the high bits (10 bits encoded per coefficient), t₀ holds the centered low bits (13 bits each). The public key is ρ ∥ t₁:

2. Private Key

The private key stores ρ, K, tr, s₁, s₂, and t₀. After generating the public key, Alice computes tr = H(pk) producing 64 bytes. The sizes break down as:

Component	Size	Encoding
ρ	32 bytes	raw
K	32 bytes	raw
tr = H(pk)	64 bytes	raw
s₁ (η=2, 3 bits/coeff)	384 bytes	1024 × 3 / 8
s₂ (η=2, 3 bits/coeff)	384 bytes	1024 × 3 / 8
t₀ (13 bits/coeff)	1664 bytes	1024 × 13 / 8

3. Signing Process

Alice wants to sign message M. She first computes the message representative μ:

Then she derives signing randomness ρ″ using K, a random 32-byte value rnd, and μ:

Using ρ″, she generates the masking vector y (ExpandMask) — 4 polynomials, 256 coefficients each, with coefficients in [−γ₁+1, γ₁] where γ₁ = 2¹⁷ = 131,072.

She computes w = A·y, then decomposes it into high bits w₁ and low bits w₀. She encodes w₁ and hashes to get the challenge seed:

Then SampleInBall converts c̃ into the challenge polynomial c: 256 coefficients, exactly 39 are ±1 (τ = 39 for ML-DSA-44), the other 217 are zero.

The response vector is computed as: z = y + c·s₁ — the masking y hides s₁ from any observer.

4. Creating the Hint

Alice computes the intermediate values c·s₂ and c·t₀, then forms:

MakeHint checks all 4 × 256 = 1024 coefficient positions. For each position, hᵢ = 1 if the relevant high bits change when the correction is applied, otherwise hᵢ = 0. ML-DSA-44 allows at most ω = 80 hint positions to be 1. The hint is encoded compactly as the positions where hᵢ = 1 plus 4 polynomial boundary values:

5. Final Signature

Alice assembles σ = (c̃ ∥ z ∥ h):

Component	Size
c̃ (challenge seed)	32 bytes
z (response vector)	2304 bytes
h (hint bits)	84 bytes

6. How Bob Verifies the Signature

Bob receives M, pk, and σ = (c̃, z, h). He also has pk = (ρ, t₁). His steps:

1. Recompute μ = H(tr ∥ M) using tr derived from pk.
2. Run c = SampleInBall(c̃) — deterministic, produces the same c as Alice.
3. Compute the approximate commitment: w′ = A·z − c·t₁·2^d (d = 13). Bob does not need s₁, s₂, or t₀ — the public t₁ and the math make the secret terms cancel approximately.
4. Apply the hint: w₁′ = UseHint(h, w′). Each hint bit tells Bob which coefficients need their high-bit value corrected to account for the t₁/t₀ split.
5. Recompute the challenge seed: c̃′ = H(μ ∥ Encode(w₁′)).
6. Compare c̃′ with the c̃ from the signature, and check all norm and validity bounds.

The verifier never needs the secret key. Even a quantum computer cannot forge this signature.