Falcon / FN-DSA: Hash-and-Sign Signatures over NTRU Lattices

ML-DSA proves knowledge of a secret with a masked response and rejection sampling. Falcon takes the other classic route to lattice signatures: it uses a secret trapdoor to solve a lattice problem that is hard for everyone else. The message is hashed to a target point, and the signature is a short vector showing that the signer could find a lattice point close to it. This is the idea of the closest vector problem, turned into a signature.

Intuition

Imagine a city grid that has been drawn twice. The public map uses long, slanted streets: every intersection is on it, but finding the intersection nearest your house takes a lifetime. The private map uses short, square blocks, so you can walk to the nearest corner in seconds.

To sign, the message is turned into a random “house” location. Only the holder of the private map can quickly name a nearby intersection. Anyone can check with the public map that the named corner really is an intersection and really is close.

The subtle part is that how you choose the corner must not reveal the shape of your private map. Falcon adds carefully shaped randomness so that the answers look the same whichever map produced them.

Hash-and-sign with a trapdoor

The template comes from Gentry, Peikert and Vaikuntanathan (GPV, 2008). Let $\Lambda$ be a lattice with a public, “bad” description and a secret short basis. To sign a message:

Hash the message (with a fresh random salt) to a target $t$ in the ambient space.
Use the short basis to sample a lattice point $v \in \Lambda$ close to $t$ .
Output $s = t - v$ , which is short.

Verification only checks that $t - s \in \Lambda$ and that $s$ is short. Forging means finding a short vector in a given coset of the lattice without the trapdoor, which is an instance of the SIS problem on the NTRU lattice.

Why the sampler must be Gaussian

Earlier schemes (GGH, NTRUSign) found $v$ by deterministic rounding with the secret basis (Babai’s method). Then $s$ is uniform over the fundamental parallelepiped of that basis, and every signature is a sample from a shape that is the secret. Nguyen and Regev (2006) showed how to recover the parallelepiped from a few hundred signatures.

GPV replaces rounding with a randomized nearest-plane algorithm that outputs $v$ from a discrete Gaussian over the lattice, centered at $t$ . When the Gaussian width $\sigma$ exceeds the Gram–Schmidt norms of the secret basis (times a smoothing factor), the output distribution depends only on the lattice and $t$ , not on which basis did the sampling. The signature leaks nothing.

The NTRU trapdoor

Falcon works in the ring $R = \mathbb{Z}[x]/(x^n + 1)$ with $n = 512$ or $n = 1024$ and modulus $q = 12289$ . That prime satisfies $q \equiv 1 \pmod{2n}$ , so polynomial multiplication mod $q$ can use the NTT. The structure is the same one that powers NTRU encryption.

Definition — Falcon key pair

Sample small polynomials $f, g \in R$ with $f$ invertible mod $q$ , then solve the NTRU equation for polynomials $F, G$ :

$fG - gF = q \pmod{x^n + 1}$
The public key is $h = g f^{-1} \bmod q$ . The public lattice is

$\Lambda_h = \{ (u, v) \in R^2 : u + v h \equiv 0 \pmod q \}$
It has the obvious long basis built from $h$ and $q$ , and the secret short basis

$B = \begin{pmatrix} g & -f \\ G & -F \end{pmatrix}$
whose rows lie in $\Lambda_h$ . The NTRU equation is exactly the condition that $\det B = q$ (as ring elements), so $B$ generates all of $\Lambda_h$ rather than a sublattice.

Solving the NTRU equation (the NTRUSolve step of key generation) uses a recursive field-norm trick that halves the degree at every level. It is the reason Falcon key generation takes milliseconds rather than microseconds, and why keys are rarely generated on the fly.

Signing and verifying

Signing

Pick a random 40-byte salt $r$ and hash to a polynomial $c = H(r \,\|\, m) \in \mathbb{Z}_q[x]/(x^n+1)$ . Use $B$ to sample a short $(s_1, s_2)$ with

$s_1 + s_2 h \equiv c \pmod q$
Restart if the vector is too long. The signature is $r$ plus a compressed encoding of $s_2$ .

Verifying

Recompute $c$ from $r$ and the message, then $s_1 = c - s_2 h \bmod q$ , centered in $(-q/2, q/2]$ . Accept if

$\|(s_1, s_2)\|^2 \le \lfloor \beta^2 \rfloor$
Verification is one NTT-based polynomial multiplication and a norm check, all in integers. It is fast and easy to implement safely.

Only $s_2$ is transmitted because the verifier can recompute $s_1$ . Its coefficients are small and Gaussian-shaped, so a Golomb–Rice-style compression packs them into about 9–10 bits each on average. That is how a 512-coefficient vector fits in 666 bytes.

Fast Fourier sampling

The generic GPV sampler (Klein’s algorithm) walks through the Gram–Schmidt vectors of the secret basis one by one. For a $2n$ -dimensional lattice that costs $O(n^2)$ operations and storage. Falcon’s contribution is to exploit the ring structure so the same distribution can be sampled in $O(n \log n)$ .

The ffLDL tree

Compute the Gram matrix $G = BB^*$ and its $LDL^*$ decomposition over the ring. Split each polynomial into its even and odd halves; in the FFT domain this is a cheap linear map, and it turns one $2 \times 2$ problem of degree $n$ into two problems of degree $n/2$ . Recursing gives a binary tree (the Falcon tree) whose leaves hold the standard deviations for one-dimensional samples.

Signing (ffSampling) walks this tree like an FFT, drawing one integer Gaussian sample per leaf with a base sampler of width near $\sigma$ . The tree is computed once from the private key and can be stored with it, which is why expanded Falcon private keys are much larger than their encoded form.

Why floating point is the hard part

The FFT and the tree live in $\mathbb{C}$ , and Falcon’s reference code uses IEEE-754 double precision (53-bit mantissa) for them. The parameters were chosen so that this precision is enough, but it brings three practical problems:

No FPU, or a slow one. Many microcontrollers lack double-precision hardware. Emulating it in integer code works (the reference implementation includes an emulated version) but makes signing many times slower.
Constant time. Floating-point instructions can take data-dependent time on some CPUs (subnormals, division, square roots). The values being processed are derived from the secret key, so any variation is a potential leak.
Side channels in practice. Published power and electromagnetic attacks on Falcon target the floating-point multiplications in the FFT and the Gaussian sampler, and have recovered keys from embedded implementations. Hardening needs masking and careful sampler design, not only constant-time branches.

NIST has said its FIPS 206 draft adjusts the Gaussian sampler in consultation with the Falcon team, allows fixed-point arithmetic as an option, and permits only randomized (salted) signing. Deterministic signing, which would make fault attacks easier, is not included.

Sizes compared with ML-DSA and SLH-DSA

This is Falcon’s selling point. Sizes are in bytes; security categories are NIST levels.

Scheme	NIST level	Public key	Signature
Falcon-512 (FN-DSA)	1	897	666
Falcon-1024 (FN-DSA)	5	1,793	1,280
ML-DSA-44 (FIPS 204)	2	1,312	2,420
ML-DSA-65 (FIPS 204)	3	1,952	3,309
ML-DSA-87 (FIPS 204)	5	2,592	4,627
SLH-DSA-SHA2-128s (FIPS 205)	1	32	7,856
SLH-DSA-SHA2-128f (FIPS 205)	1	32	17,088
ECDSA P-256 (classical)	—	64	64

Falcon signature lengths are for the padded (fixed-length) format; the compressed encoding is variable and slightly shorter on average. A public key plus signature is about 1.6 kB for Falcon-512 against 3.7 kB for ML-DSA-44. In a TLS handshake that carries several certificates and signed timestamps, that difference can decide whether the handshake fits in the initial congestion window.

Standardization status

NIST selected Falcon in 2022 alongside Dilithium and SPHINCS+. ML-DSA (FIPS 204) and SLH-DSA (FIPS 205) were published in August 2024. Falcon took longer because of its implementation complexity: on 28 August 2025, NIST reported that the FN-DSA draft (FIPS 206) was essentially complete and had been submitted for approval for publication. As of September 2026, FIPS 206 is not yet a final standard, so validated FN-DSA modules are not available. Treat FN-DSA as something to prototype and plan for, and check NIST’s PQC project page for the current status before committing to it.

When to choose FN-DSA over ML-DSA

Choose FN-DSA when

Bytes dominate: certificate chains, DNSSEC, constrained radio links, blockchains and anything that stores many signatures. Verification happens far more often than signing, or signing runs on a server-class CPU with a trusted, well-reviewed implementation. Keys are long-lived, so slow key generation does not matter.

Choose ML-DSA when

Signing runs on embedded or physically exposed hardware, you need a FIPS-validated module today, or you want the lowest implementation risk. ML-DSA uses only integer arithmetic and uniform sampling, and it is the scheme NIST expects to be most widely deployed. It is the right default for most systems.

A common split is ML-DSA for signers you control and do not want to audit deeply, and FN-DSA where a size budget forces it, typically verified on many clients but signed in a few hardened places. For how both families compare as lattice problems, see lattice signatures. For the attacks that set the parameters, see Ducas’ work on lattice reduction and parameter selection.

Check Your Understanding

Q1. NTRUSign and GGH also signed by finding a lattice point close to a hashed target. Why were they broken while Falcon is not?
Q2. What does the verifier actually check?
Q3. Why is Falcon considered harder to implement safely than ML-DSA?
Q4. A certificate chain carries five signatures and four public keys. Where does Falcon-512 save the most bytes compared to ML-DSA-44?

3.6 Falcon / FN-DSA