FNP Dilithium Post-Quantum Signatures

ELI5

A digital signature is a mathematical proof that only you could have created it. Think of it like your handwriting — everyone can verify it’s your style, but only you know how to write it. Dilithium uses lattice math (not RSA) to create unforgeable signatures that quantum computers can’t break.

Technical Deep Dive

Digital Signature Properties

A secure signature scheme has three properties:

1. Completeness — Valid signatures verify correctly
2. Soundness — Only the signer can forge valid signatures (2^-256 probability)
3. Non-repudiation — Signer can’t deny having signed (no plausible deniability)

Dilithium Algorithm (FIPS 204)

Key Generation:

1. Sample random matrix A ∈ Z_q^{k×ℓ}
2. Sample secret matrix s from small distribution
3. Compute t = As mod q
4. Public key: (A, t)
5. Secret key: s

Signing:

Input: message M, secret key s
1. y ← 2^β · r (random challenge)
2. w ← [[A·y]] (high-order bits of A·y)
3. c ← Hash(M || w)  (challenge)
4. z ← y + c·s (signature)

Rejection sampling: if ||z|| is too large, restart from step 1
Output: (z, c)

The rejection sampling step prevents timing attacks: the signer rejects too-large signatures and re-tries, ensuring signature generation time is independent of the secret key.

Verification:

Input: message M, signature (z, c), public key (A, t)
1. w' ← [[A·z - c·t]]
2. c' ← Hash(M || w')
3. Accept if c = c' AND ||z|| ≤ β

Lattice-Based Security

Hardness assumption: Module-LWE (Module-Learning With Errors)

Classical attack: Solving LWE requires ~2^256 operations (exponential in key size)

Quantum attack: Grover’s algorithm reduces to ~2^128 operations (still infeasible)

Key sizes:

• Public key: 1,312 bytes
• Secret key: 2,544 bytes
• Signature: 2,420 bytes
• Security: 128-bit quantum-resistant

Rejection Sampling (Timing Leak Prevention)

Without rejection sampling:

z = y + c·s
If s is large, z is computed in different time
Attacker measures timing → learns about s

With rejection sampling:

if ||z|| > threshold:
    restart computation
else:
    output z

All signatures take ~same time to generate, regardless of secret key magnitude.

Key Terms

• Rejection sampling → Re-attempt computation if output is “bad”; ensures constant-time generation
• Non-repudiation → Cryptographic guarantee that signer can’t deny signing
• Hash-and-sign → Sign the hash of the message, not the message itself (prevents length-based attacks)
• Module-LWE → Lattice hardness assumption; quantum-resistant

Q&A

Q: How does verification work if the verifier never sees the secret key? A: The public key t = As contains the secret s in an “hidden” form. Verification uses matrix arithmetic: w’ = A·z - c·t reconstructs high-order bits. If z was correctly generated with s, this reconstruction succeeds.

Q: Could an attacker forge a signature? A: To forge, the attacker must find z, c satisfying the verification equation. This requires solving Module-LWE, estimated at 2^256 classical work or 2^128 quantum work. No known polynomial-time algorithm.

Q: Why is the signature so large (2,420 bytes)? A: Lattice-based signatures are ~10x larger than RSA-2048 (256 bytes). This is the trade-off for quantum resistance. FNP tolerates this for document operations.

Examples

Dilithium is like an unforgeable seal: only you know the secret wax formula. Anyone can verify the seal is genuine (using public recipe), but only you can produce it. Quantum computers don’t know a faster way to forge the seal than trying 2^128 recipes randomly.