FALCON (FN-DSA)

FALCON (Fast-Fourier Lattice-based Compact Signatures over NTRU), now officially named FN-DSA, is a post-quantum digital signature scheme standardized by NIST as FIPS 206. It produces significantly smaller signatures than Dilithium (ML-DSA), making it valuable for bandwidth-constrained applications. The trade-off is implementation complexity: FALCON requires high-precision floating-point arithmetic during signing, which makes constant-time implementation more challenging and increases the risk of side-channel attacks.

NTRU lattices

FALCON’s security is based on the hardness of the Short Integer Solution (SIS) problem over NTRU lattices, a different lattice structure than the Module-LWE lattices used by Kyber and Dilithium. An NTRU lattice is defined by a pair of polynomials $(f, g)$ in the ring $\mathbb{Z}_q[x]/(x^n + 1)$, where the public key is $h = g \cdot f^{-1} \bmod q$. The associated lattice has a special structure that enables compact keys and signatures, but also means that FALCON’s security assumptions are somewhat different from (and potentially less conservative than) those of Dilithium.

How FALCON signing works

FALCON uses the GPV (Gentry-Peikert-Vaikuntanathan) framework for hash-and-sign signatures over lattices:

1. Key generation: Generate a short basis (a “trapdoor”) for an NTRU lattice. This involves finding polynomials $f, g, F, G$ satisfying $fG - gF = q$, which form a short basis of the NTRU lattice.

2. Hashing: Hash the message to a point $\mathbf{c}$ in the lattice.

3. Trapdoor sampling: Using the short basis, sample a lattice vector $\mathbf{v}$ close to $\mathbf{c}$. This is where the “fast Fourier” part comes in: FALCON uses a tree-based sampling algorithm over the FFT (Fast Fourier Transform) representation of the lattice basis, which requires high-precision floating-point arithmetic.

4. Signature output: The signature is the difference $\mathbf{s} = \mathbf{c} - \mathbf{v}$, which is a short vector whose proximity to $\mathbf{c}$ can be verified using only the public key.

The critical step is the trapdoor sampling, which must produce vectors with a specific Gaussian distribution. Deviations from this distribution can leak information about the secret key. This is why constant-time floating-point arithmetic is essential and why FALCON is harder to implement securely than Dilithium.

Parameter sets and comparison with Dilithium

Parameter set	Security level	Public key	Signature	Secret key
FN-DSA-512	NIST Level 1 (~AES-128)	897 bytes	666 bytes	1,281 bytes
FN-DSA-1024	NIST Level 5 (~AES-256)	1,793 bytes	1,280 bytes	2,305 bytes

Compared to Dilithium at similar security levels:

Property	ML-DSA-44 (Level 2)	FN-DSA-512 (Level 1)
Signature size	2,420 bytes	666 bytes
Public key size	1,312 bytes	897 bytes
Signing speed	Fast, simple	Moderate, complex
Verification speed	Very fast	Fast
Implementation difficulty	Moderate	High

FALCON signatures are roughly 3 to 4 times smaller than Dilithium signatures at comparable security levels. This size advantage matters for applications with tight bandwidth budgets, such as certificate chains in constrained IoT devices, blockchain transactions, or embedded systems.

Implementation challenges

The main reason NIST selected Dilithium as the primary signature standard (with FALCON as an additional option) is implementation complexity:

• Floating-point precision: The sampling algorithm requires double-precision or higher floating-point arithmetic. On platforms without hardware floating-point support, this is slow and difficult to implement in constant time.
• Side-channel resistance: The floating-point operations create timing and power side channels that are harder to mitigate than the simple modular arithmetic in Dilithium.
• Key generation cost: Generating the NTRU trapdoor is more computationally expensive than Dilithium key generation.

Why it matters for learners

FALCON illustrates a recurring theme in cryptographic engineering: the trade-off between mathematical elegance and practical deployability. Its compact signatures come from a clever use of lattice geometry and Gaussian sampling, but the implementation complexity is a real barrier. For quantum computing students, FALCON also demonstrates that the lattice-based cryptography landscape is not monolithic. Different lattice structures (Module-LWE for Kyber/Dilithium, NTRU for FALCON) lead to different performance profiles and security assumptions, all unified by the underlying hardness of lattice problems against both classical and quantum attacks.

See also

• Lattice-Based Cryptography
• NIST PQC Standards
• Dilithium (ML-DSA)
• Post-Quantum Cryptography