CRYSTALS-Dilithium & Falcon Signatures

RSA and ECDSA signatures are broken by Shor's algorithm. Post-quantum signatures must replace them for: TLS certificates, code signing, email signing (S/MIME, PGP), and software update authentication. NIST standardized two lattice-based schemes: ML-DSA and FN-DSA.

Dilithium is based on the hardness of Module-LWE and Module-SIS (Short Integer Solution). Security proof in the QROM (Quantum Random Oracle Model). Three variants: Dilithium2 (~128-bit), Dilithium3 (~192-bit), Dilithium5 (~256-bit). Simple, rejection-sampling-free sign path.

Private key: secret matrices s1, s2. Public key: t = As1 + s2. Sign: sample random y; compute w = Ay; compute challenge c = H(mu || w1) where w1 = HighBits(w); compute z = y + cs1; if ||z|| or ||r0|| is too large, reject and retry. Output (z, c, hint).

Verify (z, c, hint): check ||z|| is small; compute w' = Az - ct; use hint to recover w1; verify c == H(mu || w1). The hint is a small number of bits from MakeHint(). Rejection ensures z does not leak s1 — the security argument is a "aborts-then-uniform" argument.

ML-DSA-65 (Dilithium3, 192-bit security): public key 1952 bytes, private key 4000 bytes, signature 3293 bytes. Compare: ECDSA-P256: 64-byte public key, 64-byte signature. Dilithium is ~40-50x larger in signatures but quantum-safe.

Falcon is based on NTRU lattices and uses a Gaussian sampler over the NTRU lattice. Signatures are significantly smaller than Dilithium but signing requires a floating-point Gaussian sampler — harder to implement in constant time and more complex to code securely.

Falcon-512 (128-bit security): public key 897 bytes, signature 666 bytes — much smaller than Dilithium. Trade-off: Falcon is harder to implement securely (Gaussian sampling susceptible to timing attacks). Suitable for constrained bandwidth but requires careful implementation.

SPHINCS+ is a hash-based signature scheme — conservative choice with no structural algebraic assumptions. Security relies only on hash function security. Signature size: ~8-50 KB (large). Slow signing. Used where long-term trust is critical and performance is secondary.

ML-DSA (Dilithium): general purpose, simple implementation, good for TLS certificates and code signing. FN-DSA (Falcon): bandwidth-constrained environments (IoT, LPWAN). SLH-DSA (SPHINCS+): ultra-conservative, long-lived roots (CA offline keys, software root of trust).

Dilithium: rejection sampling may leak branch timing — use constant-time comparison. Falcon: Gaussian sampler uses floating-point — ensure FP determinism. Both: avoid side-channels in polynomial arithmetic. Use reference implementations from NIST submission packages.

NIST FIPS 204: ML-DSA (Dilithium). NIST FIPS 205: SLH-DSA (SPHINCS+). NIST FIPS 206: FN-DSA (Falcon). All published August 2024. Libraries: OpenSSL 3.x, BoringSSL, liboqs (Open Quantum Safe project) implement all three.

What is the main advantage of Falcon over Dilithium?

ML-DSA (Dilithium): lattice-based, simple, ~3 KB signatures. FN-DSA (Falcon): NTRU-based, ~700-byte signatures, complex implementation. SLH-DSA (SPHINCS+): hash-based, conservative, large. All standardized in FIPS 204/205/206. Next: migrating to PQC with hybrid approaches.