Skip to main content

​
FNP - Cryptography - Dilithium Post-Quantum Signatures

​
Summary (Explain Like I’m 5)

Imagine you send a handwritten letter and someone asks: “Did you really write this?” Problem: Handwriting can be forged. Digital signatures have the same problem with traditional encryption (RSA). Solution - Dilithium: Uses a different kind of math (lattices) that:
  • Only you can sign with your secret key
  • Anyone can verify with your public key
  • Even quantum computers can’t forge signatures
  • No one can deny they signed (non-repudiation)
In FNP: Every edit is signed by the user who made it. Server verifies: “Is this really from Alice?” without trusting her.

​
Technical Deep Dive

Dilithium (NIST FIPS 204 standard) is a lattice-based digital signature scheme providing post-quantum security for operation authentication and non-repudiation. Design Parameters (Dilithium-4, 256-bit security):
ParameterValuePurpose
k (module rank)6Number of polynomials; larger k = more security
ℓ (weight)5Secret key weight; higher = harder to forge
η (noise bound)7Small noise in secret; η=7 means bounded by 7
τ (challenge weight)60Number of ±1 coefficients in challenge
d (dropped bits)14Bits dropped from low-order in compression
λ (security param)256Bits of security (256 bits = 2^256 work to forge)
Security: 256-bit classical, 256-bit quantum (same hardness vs classical and quantum). Signature Protocol: 
KeyGen() → (vk, sk):
  1. Sample: A ← U(Z_q^{k×ℓ}) [uniform public matrix]
  2. Sample: s₁ ← Bη^ℓ, s₂ ← Bη^k [small secret vectors]
  3. Compute: t = A·s₁ + s₂ mod q
  4. vk = (encode(t), seed_A) [verification key: ~2592 bytes]
  5. sk = (seed, encode(s₁), encode(s₂), ...) [signing key: ~4000 bytes]

Sign(sk, msg) → σ:
  1. Parse: (seed, s₁, s₂, ...) from sk
  2. Compute: μ = CRH(seed, msg) [cryptographic hash]
  3. Sample: y ← B_{γ₁-1}^ℓ [random vector]
  4. Compute: w = A·y mod q [commitment]
  5. Compute: w₁ = HighBits(w, d)
  6. Compute: c = CRH(w₁, μ) [challenge from w₁ and message]
  7. Compute: c̃ = decode(c) [decode as ±1 coefficients]
  8. Compute: z = y + c̃·s₁ mod q
  9. Rejection Test: if ||z - y|| > γ₁ - β: goto step 3
  10. Compute: r = LowBits(A·z - c̃·t, d)
  11. Rejection Test: if r ≠ LowBits(w, d): goto step 3
  12. Output: σ = (c̃, z)

Verify(vk, msg, σ) → accept/reject:
  1. Parse: (c̃, z) from σ
  2. Parse: (t, seed_A) from vk
  3. Reconstruct: A from seed_A
  4. Compute: μ = CRH(seed, msg)
  5. Compute: c = CRH(HighBits(A·z - c̃·t, d), μ)
  6. Check: decoded(c) = c̃ ?
  7. Check: ||z|| ≤ γ₁ - β ?
  8. Accept if both checks pass, reject otherwise
Key Sizes:
  • Verification key (public): 2,592 bytes
  • Signing key (secret): 4,016 bytes
  • Signature: 3,366 bytes
  • Signature (compressed): 2,420 bytes
Signing Time: ~600 microseconds (very fast) Verification Time: ~500 microseconds (very fast) Rejection Sampling: Dilithium uses rejection sampling to prevent timing attacks. If signature fails range checks, resample and retry. Constant-time execution within acceptable bounds.

​
Mermaid Diagrams

​
Key Terms

  • Lattice-Based → Uses Learning With Errors (LWE) hardness; quantum-resistant
  • Rejection Sampling → Resample if signature fails range check; prevents timing leaks
  • Non-Repudiation → Signer can’t deny signing; only they have secret key
  • NIST FIPS 204 → Official US standard for post-quantum signatures
  • Constant-Time → Execution time doesn’t leak secrets through timing channels
  • Signature Malleability → Can’t modify valid signature to produce another valid signature
  • Stateless → No state needed between signatures; deterministic or randomized
  • Module-LWE → Module structure of LWE problem; higher security per operation

​
Q/A

Q: Why Dilithium instead of RSA for signatures? A: RSA signatures are broken by Shor’s algorithm on quantum computers (polynomial-time). Dilithium is built on lattice problems with no known quantum speedup. Same security against classical and quantum attackers. Q: What’s rejection sampling in Dilithium? A: Dilithium signs by computing z = y + c̃·s₁. If ||z|| is too large (might leak secrets), reject and resample y. This makes signature generation non-deterministic but constant-time bounds remain (no timing leaks). Q: Can I forge a Dilithium signature? A: No. Forging requires solving LWE problem (breaking lattice hardness). With 256-bit security, you’d need 2^256 operations (infeasible). Also, signature is binding to specific message via hash μ. Q: How does the server know Alice really signed? A: Server has Alice’s public key (vk_alice). Verify algorithm checks: Does signature correctly satisfy lattice equations for this message and public key? If yes, Alice must have signed (only she has secret key). Q: What if Alice loses her signing key? A: She can no longer sign operations. Previous signatures remain valid (non-repudiation). She should revoke old key, generate new keypair, broadcast new vk. Server stores both old and new keys (rotation). Q: Can signatures be replayed? A: Each operation has unique timestamp + message hash. Replaying old signature with old message gets same hash → server detects replay (Lamport clock check catches it first). Even if Lamport check missed it, Dilithium sig is bound to specific message.

​
Example / Analogy

Notary Public Analogy: Without Dilithium (forging is easy):
  • You sign a contract with pen
  • Anyone can copy your signature
  • No way to prove you really signed it
With Dilithium (unforgeable):
  • Notary gives you special stamp + secret code
  • You stamp document (only you have code)
  • Anyone can verify stamp is legitimate
  • Even you can’t deny you stamped it (non-repudiation)
  • Quantum computers still can’t forge the stamp
Real-world FNP: When Alice types “The project is done”:
  1. Alice’s device creates operation hash
  2. Device signs with Dilithium_sk (only on Alice’s device)
  3. Sends: Operation + Signature to server
  4. Server verifies: “Is Alice’s signature valid?”
  5. Server accepts (Alice authenticated the edit)
  6. Bob receives operation + signature
  7. Bob verifies signature (Alice really signed)
  8. Bob: “Alice owns this edit” (non-repudiation)
Cross-References: System Overview, FNP Protocol Flow, Security & Zero Trust, LSEQ CRDT Category: Cryptography | Post-Quantum | Signatures | Authentication Difficulty: Advanced ⭐⭐⭐⭐ Updated: 2025-11-28