PDF Run this chapter's code LaTeX source Comments

Chapter 18FN-DSA (Falcon): Draft-Oriented Walkthrough

18.1Learning objectives#

This chapter is a draft-oriented walkthrough of FN-DSA, NIST’s planned standardization of Falcon [1, 2]. It is not a claim of conformance to a final FIPS: readers must consult the exact draft version and date used by an implementation. Unlike ML-KEM, ML-DSA, and SLH-DSA, FIPS 206 remains under standardization at this book’s standards snapshot. Where ML-DSA uses Fiat–Shamir with aborts, Falcon takes a different route on the same lattice foundation: hash-and-sign over NTRU lattices, using a Gaussian trapdoor sampler. The result is the most compact signatures and keys of the three signature standards, at the cost of the most delicate implementation.

After finishing this chapter, you should be able to:

1. contrast hash-and-sign with the Fiat–Shamir approach of ML-DSA, and state the GPV framework and its security requirement;

2. describe the NTRU lattice and why a short secret basis is a trapdoor;

3. explain how signing is a nearest-lattice-point problem solved with a Gaussian sampler;

4. connect the sampler back to discrete Gaussians, good vs. bad bases, and CVP from Part II;

5. understand why Falcon’s floating-point arithmetic makes constant-time implementation hard.

18.2Two routes from a lattice to a signature#

A signature scheme needs a public key that anyone can check against, a secret that only the signer holds, and a way to bind the two to a message. On lattices there are two standard ways to arrange this, and the two lattice signature standards take one each. ML-DSA (Chapter 17) is built from an identification protocol collapsed by a hash: the signer commits, hashes the commitment together with the message to obtain a challenge, and answers the challenge with a response whose distribution must be made independent of the secret by rejection sampling. Falcon takes the other route, hash-and-sign, and this section sets the two side by side before the chapter follows Falcon’s route in detail.

18.2.1Hash-and-sign#

Hash-and-sign is the older paradigm and has the same shape as textbook RSA signatures. A public function \(f_{\mathrm{pk}}\) is easy to compute but hard to invert; the signer holds a trapdoor that makes inversion easy. To sign, the signer hashes the message to a point in the range of \(f_{\mathrm{pk}}\) and uses the trapdoor to produce a preimage:

1. hash the message to a target point \(c = H(M)\);

2. use the secret trapdoor to find a preimage \(s\) with \(f_{\mathrm{pk}}(s) = c\);

3. the verifier recomputes \(c\) and checks that \(f_{\mathrm{pk}}(s) = c\).

The signature is the preimage \(s\) itself, together with any salt used in the hash. Nothing interactive is happening, and no challenge is drawn: the message determines the target, and the trapdoor answers it.

On a lattice, the public function is a short-integer-solution map. With a public matrix \(\mathbf{A}\), the function \(f_{\mathbf{A}}(\mathbf{s}) = \mathbf{A}\mathbf{s} \bmod q\) restricted to short inputs is easy to evaluate, and inverting it (finding a short \(\mathbf{s}\) with \(\mathbf{A}\mathbf{s} = c\)) is an inhomogeneous SIS instance, hard without extra information (Section 11.7). The trapdoor is a short basis of the lattice \(\Lambda^{\perp}_q(\mathbf{A}) = \{\mathbf{z} : \mathbf{A}\mathbf{z} = \mathbf{0} \bmod q\}\): given any solution \(\mathbf{s}_0\) of \(\mathbf{A}\mathbf{s}_0 = c\), a good basis lets the signer find a lattice point close to \(\mathbf{s}_0\), and the difference is a short solution. In lattice terms, signing is a closest-vector problem, and the trapdoor is exactly the good basis that Chapters 7–9 identified as the thing that makes CVP tractable.

18.2.2Fiat–Shamir#

Fiat–Shamir starts from the other end. There is no trapdoor function to invert; instead the secret is used to answer a random challenge in a way that a party without the secret could not. Section 17.9 gave the three-move identification protocol (commitment \(w\), challenge \(c\), response \(z\)) and the transform \(c = H(w \,\|\, M)\) that removes the verifier. In ML-DSA the commitment is \(\mathbf{w} = \mathbf{A}\mathbf{y}\) for a fresh masking vector \(\mathbf{y}\), and the response is \(\mathbf{z} = \mathbf{y} + c\,\mathbf{s}_1\). Correctness follows from linearity. Security needs \(\mathbf{z}\) to reveal nothing about \(\mathbf{s}_1\), and since \(\mathbf{y}\) is bounded rather than Gaussian, the sum \(\mathbf{y} + c\,\mathbf{s}_1\) is not automatically independent of \(\mathbf{s}_1\); the abort loop of Section 17.9 discards the responses that would leak.

18.2.3The comparison#

Both routes end at the same requirement, that the object released to the verifier be distributed independently of the secret, but they meet it differently, and the difference drives everything that follows in this chapter.

The size gap in the last row is the reason Falcon exists as a second standard, and the arithmetic row is its price. A Fiat–Shamir response is a sum of a uniformly bounded mask and a small multiple of the secret, so it costs the mask’s full width in bytes; a hash-and-sign preimage is as short as the trapdoor allows, which for a well-conditioned basis is a fraction of that. Sampling such a preimage without leaking the basis, however, requires a discrete Gaussian of controlled width, and that is where floating point enters.

18.2.4The GPV framework#

The lattice version of hash-and-sign was proposed before it was made secure. Goldreich, Goldwasser and Halevi [3] and later NTRUSign [4] signed by rounding the target \(c\) to a nearby lattice point using the secret good basis, exactly Babai’s algorithm from Chapter 8. Each signature is then a point of the parallelepiped spanned by the secret basis, shifted to \(c\), and a collection of signatures traces out that parallelepiped. Nguyen and Regev [5] recovered the secret basis of both schemes from a few hundred signatures by fitting the parallelepiped’s shape. The lesson is the one that Section 17.9 drew for ML-DSA: a deterministic function of the secret, released repeatedly, is a sample from a distribution that depends on the secret.

Gentry, Peikert and Vaikuntanathan [6] gave the framework that repairs this, referred to as GPV after its authors, and the name this chapter uses from here on. It replaces the rounding step by a sampling step. Rather than the nearest lattice point, the signer draws a lattice point from a discrete Gaussian centered at the target, and outputs the short difference. The framework has three components.

1. Trapdoor generation. Output a public matrix \(\mathbf{A}\) (or, for Falcon, a public polynomial \(h\)) together with a short basis \(\mathbf{B}\) of the corresponding lattice, such that \(\mathbf{A}\) alone is indistinguishable from a random matrix.

2. Preimage sampling. Given a target \(c\) and the short basis \(\mathbf{B}\), output \(\mathbf{s}\) with \(\mathbf{A}\mathbf{s} = c\) and \(\mathbf{s}\) distributed as a discrete Gaussian of parameter \(\sigma\) over the solution coset, with \(\sigma\) a small multiple of the largest Gram–Schmidt length of \(\mathbf{B}\).

3. Verification. Accept if \(\mathbf{A}\mathbf{s} = H(M)\) and \(\|\mathbf{s}\| \le \beta\), where \(\beta\) is a fixed multiple of \(\sigma\sqrt{m}\).

Two properties of the sampler carry the security argument, and both are properties of the discrete Gaussian rather than of any particular trapdoor.

This is what the rounding schemes lacked. Babai rounding produces a distribution shaped like the secret parallelepiped; a wide enough Gaussian produces a distribution shaped like the lattice, which is public. The width required is where the Gram–Schmidt lengths of \(\mathbf{B}\) enter: a better basis permits a narrower Gaussian, hence shorter signatures, without violating the condition. That is why key generation in Falcon works to make the secret basis as orthogonal as it can (Section 18.4).

The argument runs as follows. The reduction answers each hash query \(H(M_i)\) by first sampling a short \(\mathbf{s}_i\) from the Gaussian and then defining \(H(M_i) := \mathbf{A}\mathbf{s}_i\); because \(\mathbf{A}\mathbf{s}_i\) is nearly uniform for a wide enough Gaussian, the forger cannot tell these programmed values from random ones, and the reduction can answer signing queries without any trapdoor. When the forger outputs a valid \((M^{*}, \mathbf{s}^{*})\) with \(\mathbf{A}\mathbf{s}^{*} = H(M^{*})\), the reduction already holds its own short preimage \(\mathbf{s}\) of the same target, and with good probability \(\mathbf{s} \neq \mathbf{s}^{*}\), since a Gaussian of parameter above the smoothing parameter has min-entropy: the forger cannot guess which preimage the reduction drew. Then \(\mathbf{s} - \mathbf{s}^{*}\) is a nonzero vector of norm at most \(2\beta\) in \(\Lambda^{\perp}_q(\mathbf{A})\), an SIS solution.

The proof isolates the requirement that governs Falcon’s implementation, and it is stated here because it recurs in Section 18.8.1 in an implementation setting: the signer must never release two distinct short preimages of the same target. If it did, their difference would be exactly the SIS solution the reduction extracts, handed over for free. In the framework this is guaranteed by the salt, which makes each target fresh, and by the sampler itself, which is randomized so that even a repeated target does not produce a correlated pair. Any implementation detail that breaks either guarantee, a reused salt or a sampler whose output on the same input differs across platforms, breaks the scheme with no side channel involved.

Falcon is the GPV framework instantiated on the NTRU lattice: the trapdoor is the short NTRU basis, the preimage sampler is the fast Fourier sampler over that basis, and the hash is HashToPoint with a salt. The rest of the chapter follows those three components in order.

18.3The NTRU lattice and its trapdoor#

Falcon rests on the NTRU assumption introduced in Section 12.15. It works in the by-now-familiar ring \(R_q = \mathbb{Z}_q[x]/(x^n+1)\) with \(n \in \{512, 1024\}\) and \(q = 12289\). Key generation picks two short secret polynomials \(f, g \in R_q\) and publishes \[h = g \cdot f^{-1} \pmod q.\] The public key is just the single polynomial \(h\). It defines the NTRU lattice \[\Lambda = \{ (u, v) \in R_q^2 : u + v\,h = 0 \pmod q \},\] a \(2n\)-dimensional lattice exactly of the kind studied in Part II. From \(h\) alone you can write down a basis for \(\Lambda\), but it is a bad basis – long and skewed – so finding short vectors in it is hard.

The secret is a good basis for the very same lattice. Key generation completes \((f,g)\) into a full short basis by solving the NTRU equation \[f\,G - g\,F = q\] for two more short polynomials \(F, G\). The pair of rows \((g, -f)\) and \((G, -F)\) is a short, nearly orthogonal basis of \(\Lambda\) – precisely the “good basis” that Chapters 7–9 told us is the key to solving lattice problems.

18.4Phase 1: key generation#

The secret basis and the public \(h\) describe the same lattice; they differ only in quality. That is the entire trapdoor.

18.5Phase 2: hash the message to a point#

Signing begins by mapping the message to a random-looking target in the ring. A fresh salt \(r\) is prepended so that signing the same message twice gives independent targets: \[c = \text{H}{\small\text{ASH}}\text{T}{\small\text{O}}\text{P}{\small\text{OINT}}(r \,\|\, M) \in R_q.\]

18.6Phase 3: sample a short solution (the trapdoor sampler)#

The signer must find a short pair \((s_1, s_2)\) satisfying \[s_1 + s_2\,h = c \pmod q,\] which is the same as finding a lattice point of \(\Lambda\) close to \((c, 0)\). Using the good basis, the signer runs fast Fourier sampling: a discrete Gaussian sampler over the lattice coset, implemented efficiently over the FFT representation of the basis (organized as an “LDL tree”). Two properties matter:

• the result is short, because the good basis makes nearby lattice points reachable;

• its distribution is a discrete Gaussian centered at the target, which – crucially – is independent of which good basis produced it. This is what stops each signature from leaking the secret.

This is where the whole book converges: the discrete Gaussian of Chapter 10, the good-versus-bad-basis geometry of Chapters 7–8, and the closest-vector view of the LWE chapter all appear at once, in service of one signature.

18.7Phase 4: compress and output#

Only \(s_2\) needs to be sent: the verifier can recover \(s_1 = c - s_2 h \bmod q\). Because \(s_2\) has small Gaussian coefficients, it compresses well, giving Falcon its signature-size advantage. The signature is \(\sigma = (r, \text{compress}(s_2))\).

Verification is cheap: one multiplication to recover \(s_1\), then a norm check. A forger without the good basis would have to solve the closest-vector problem in the NTRU lattice using only \(h\) – exactly the hardness Part II established.

18.7.1Where the signature bytes go#

The sizes in the parameter table (Section 18.12) are not rounded estimates but sums of fixed fields, and each field follows from something already on the page. A Falcon signature is \[\underbrace{1}_{\text{header}} \;+\; \underbrace{40}_{\text{salt }r} \;+\; \underbrace{\ell_n}_{\text{C}{\small\text{OMPRESS}}(s_2)} \quad\text{bytes}, \qquad \ell_{512}=625,\quad \ell_{1024}=1239,\] giving \(666\) and \(1280\) bytes. The header byte records the encoding and \(\log_2 n\); the salt is the 320-bit value hashed with the message. Everything that varies with the security level is in \(\ell_n\), and \(\ell_n\) is set by two facts: how wide the sampler’s Gaussian is, and how the coefficients are coded.

The width.#

The fast Fourier sampler outputs \((s_1,s_2)\) with each coefficient a discrete Gaussian of standard deviation \[\sigma \;=\; 1.17\,\sqrt{q}\;\eta_\varepsilon(\mathbb{Z}^{2n}),\] where \(\eta_\varepsilon\) is the smoothing parameter of Section 18.2.4 at the \(\varepsilon\) the specification fixes; the specification tabulates \(\eta_\varepsilon \approx 1.278\) for \(n=512\) and \(1.298\) for \(n=1024\), so \(\sigma \approx 165.7\) and \(168.4\). The factor \(1.17\sqrt{q}\) is the Gram–Schmidt quality that key generation guarantees for the secret basis (Section 18.4); a coefficient of \(s_2\) is thus an integer of typical magnitude a hundred or two, out of a range of \(q=12289\).

The code.#

A coefficient stored as a raw residue costs \(\lceil\log_2 q\rceil = 14\) bits, which would put \(s_2\) alone at \(896\) bytes for \(n=512\). Compress instead writes each coefficient \(c\) as one sign bit, the low seven bits of \(|c|\) verbatim, and the remaining high part \(\lfloor |c|/128\rfloor\) in unary (\(k\) zero bits followed by a one). With \(\sigma\approx166\), \(|c|<128\) for about \(56\%\) of coefficients and \(|c|<256\) for about \(88\%\), so the unary part averages roughly \(0.6\) bits, and the expected cost is \[1 + 7 + (0.6 + 1) \;\approx\; 9.6\ \text{bits per coefficient},\] about \(613\) bytes for \(n=512\). The information-theoretic floor for a Gaussian of this width, \(\log_2\bigl(\sigma\sqrt{2\pi e}\bigr)\approx 9.4\) bits, shows the code is within a few percent of optimal.

The fixed length.#

A variable-length signature would leak the size of \(s_2\) and complicate every parser downstream, so the specification fixes \(\ell_n\) slightly above the mean: \(625\) bytes for \(n=512\) is \(9.77\) bits per coefficient, \(1239\) for \(n=1024\) is \(9.68\). An encoding that comes up short is padded with zero bits; the rare draw whose encoding would exceed \(\ell_n\) is discarded and the signer samples again. That resampling is why the table’s figures can be exact rather than typical.

The public key has no such structure to exploit. Its single polynomial \(h\) has coefficients uniform modulo \(q\), so it costs the full \(14n/8\) bytes plus a header byte: \(897\) for \(n=512\) and \(1793\) for \(n=1024\). The asymmetry is the whole design in one line: the key is a random-looking ring element and must be stored as one, while the signature is a short Gaussian vector and is stored as one.

18.8Why Falcon is the hardest to implement#

The Gaussian sampler needs high-precision floating-point arithmetic (FFT over the reals) to get the output distribution exactly right. Floating-point operations are notoriously variable-time and platform-dependent, which makes a constant-time implementation – one that leaks nothing through timing – genuinely difficult. If the sampler’s timing or rounding depends on the secret basis, an attacker can gradually reconstruct it. This is the direct motivation for the final chapter on side-channel security, and it is the main reason Falcon, despite its elegance and compactness, is the most demanding of the three standards to deploy safely.

18.8.1Non-determinism is a second, separate problem#

Timing is the familiar hazard, and it is not the only one. The same floating-point operation can give slightly different results on a different processor, compiler, or optimization level, and that alone can break the scheme — with no side channel involved at all.

Analyses of Falcon’s floating-point sensitivity make this implementation boundary concrete: compiler, instruction, and rounding differences can perturb the sampled distribution in ways relevant to secret-key security [7].

The reason is the security requirement stated in Section 18.2.4: a signer must never release two distinct short preimages for the same digest. Two short vectors \(s, s'\) with \(As = As' = c\) give their difference \(s - s'\), a short non-zero vector in the lattice \(\Lambda^{\perp}_q(A)\) — which is a solution to the very problem the trapdoor was supposed to keep hard. Ordinary Falcon avoids this by drawing a fresh 320-bit salt for every signature, so no two signatures ever target the same digest.

The danger appears when signing is derandomized: if the salt is derived pseudorandomly from the message and the key, as one would want for reproducible signing, then signing the same message twice must produce the same signature bit-for-bit. Two implementations at different precision — or the same implementation compiled twice — would produce two valid signatures for one digest, and hand an observer a short lattice vector.

The fix is to remove the platform dependence rather than to manage it: replace hardware floating-point with an integer emulation, so that every implementation performs identical arithmetic and produces identical output. The cost is asymmetric in a way that happens to suit a blockchain (Section 28.4.4):

• key generation is about \(2\times\) slower;

• signing is about \(15\times\) slower;

• verification is unaffected, because Falcon verification uses no floating-point arithmetic at all — it is integer arithmetic modulo \(q\) with an NTT, and it is the fastest verification of the three standards.

An output is signed once, by its owner, when it is spent; the signature is then verified by every validating node, forever. Paying \(15\times\) on the operation that happens once to make the operation that happens everywhere both cheap and identical across platforms is the right side of that trade. Even emulated, Falcon signing remains one to two orders of magnitude faster than SLH-DSA at its small-signature parameters.

18.8.2The signer needs memory, too#

One further practical constraint, easy to miss because it appears in neither the key nor the signature size. The sampler is driven by the tree of Section 18.6, and where that tree is kept decides the signer’s memory footprint. Holding it alongside the compact basis makes signing a simple traversal but occupies roughly \(40\) kB at \(n=512\) and \(90\) kB at \(n=1024\). Rebuilding only the branch currently needed cuts this to about \(8\) and \(16\) kB, at roughly double the signing cost.

That matters because the natural place to run a signer is a hardware wallet, and those are microcontrollers with tight RAM budgets. Note also that this cost compounds with the emulation penalty above, and that it is a per-signature cost whenever a key signs only once — which is exactly the recommended practice for a Bitcoin address.

18.9Research directions in compactness and acceleration#

Sections 18.2.4 and 18.7.1 explain how Falcon’s sampler and encoding produce compact signatures. Recent analyses tighten GPV preimage sampling under weaker smoothness conditions and use Rényi divergence to measure the gap between Falcon’s real and ideal samplers more precisely [8, 9]. Other work combines probability coding, sampling geometry, and modulus choices to shorten hash-and-sign lattice signatures [10]. These results can reduce proof slack or transport size, but every saving must be reported together with its security margin and sampler requirements.

MITAKA explores a different engineering point: it retains the NTRU hash-and-sign direction while replacing Falcon’s fast Fourier sampler with a hybrid sampler and a stronger-quality trapdoor, producing a structure intended to be easier to parallelize and mask [11]. The comparison is useful precisely because MITAKA is a research construction rather than FN-DSA: simplifying an implementation may require changing the primitive, not merely optimizing Falcon code.

Acceleration is equally workload-specific. FPGA and ASIC designs expose area, memory-port, power, and energy costs hidden by software benchmarks [12, 13]. GPU implementations can obtain very high Falcon batch throughput; GOLF, for example, reports results on an RTX 4090 using message-level parallelism, FFT kernels, and cache-locality optimization [14]. Such figures do not predict the latency of one interactive signature: batch size, transfer overhead, occupancy, tail latency, and tenant isolation must be measured separately.

18.10SageMath experiment: the public NTRU relation#

Sage can verify the public-key equation underlying the NTRU lattice. The example deliberately stops before the Gaussian trapdoor sampler: finding a correctly distributed short signature is the hard, specification-sensitive part of FN-DSA and is not reproduced by this toy calculation.

from random import Random
from sage.all import GF, PolynomialRing

q = 17
n = 8
rng = Random("fndsa-ntru-relation")
R.<x> = PolynomialRing(GF(q))
Rq = R.quotient(x^n + 1)

def small_poly():
    return Rq([rng.choice([-1, 0, 1]) for _ in range(n)])

def small_unit():
    f = small_poly()
    while not f.is_unit():
        f = small_poly()
    return f

f = small_unit()
g = small_poly()
h = g * f^(-1)                 # public NTRU value
assert f * h == g               # f h = g in Rq

c = Rq([rng.randrange(q) for _ in range(n)])
s2 = small_poly()
s1 = c - s2*h                  # verifier's reconstruction rule
assert s1 + s2*h == c
print("NTRU public relation and verification equation hold")

The last equality is only an algebra check. In a real signature, FFSampling must choose \((s_1,s_2)\) with the required short Gaussian distribution; choosing an arbitrary small \(s_2\) as above is not an FN-DSA signing algorithm.

18.11A complete SageMath implementation#

The experiment above stops exactly where the difficulty starts. The companion file sage/fips206_fndsa.sage goes the rest of the way: all eighteen numbered algorithms of the Falcon specification, at \(n=512\) and \(n=1024\) – the FFT over the complex tower, NTRUGen with the tower-recursive NTRU solver, the LDL^\(\star\) decomposition and the Falcon tree, fast Fourier sampling with the isochronous discrete Gaussian sampler, signing, verification, and the compressed signature and key encodings.

Run it in a browser: the sampler and FFT checks, and signing and verification from a stored key; only NTRUGen is too slow for a sandbox. See appliedpqc.io/playground.html — nothing to install.

Which specification the code follows.#

This matters more here than in the other three chapters. At the book’s standards snapshot NIST lists FIPS 206 as in development: no initial public draft has been published, and consequently no ACVP test vectors exist. The authoritative specification for FN-DSA is therefore still the round-3 Falcon submission, and that is what the file implements, using Falcon’s algorithm numbering. The places most likely to be respecified when the draft appears – the key and signature encodings, and the domain separation of the hashed message – are marked in the source. The lattice machinery below them is not expected to change.

Solving the NTRU equation.#

Key generation’s one genuinely hard step is the line that Algorithm 23 states in five words: solve \(fG - gF = q\) for short \(F,G\). The method is a tower recursion. The field norm \(N\) maps \(\mathbb{Z}[x]/(x^n+1)\) down to \(\mathbb{Z}[x]/(x^{n/2}+1)\); applying it repeatedly reaches \(\mathbb{Z}\), where the equation is an extended gcd; the multiplicativity of the norm then lifts the solution back up, one level at a time.

def NTRUSolve(f, g):
    """Algorithm 6. Find F, G with f*G - g*F = q in Z[x]/(x^n + 1)."""
    n = len(f)
    if n == 1:
        d, u, v = xgcd(ZZ(int(f[0])), ZZ(int(g[0])))
        if d != 1:
            return None, None
        return [int(-FALCON_q*v)], [int(FALCON_q*u)]
    fp, gp = field_norm(f), field_norm(g)
    Fp, Gp = NTRUSolve(fp, gp)              # recurse in the smaller ring
    if Fp is None:
        return None, None
    F = _cyclo_mul(lift(Fp), galois_conjugate(g), n)
    G = _cyclo_mul(lift(Gp), galois_conjugate(f), n)
    return Reduce(f, g, F, G)               # shorten F, G against f, g

Here field_norm is \(N(a) = a(x)a(-x)\) written in \(x^2\), lift is \(a(x)\mapsto a(x^2)\), and galois_conjugate is \(a(x)\mapsto a(-x)\). The lifted \(F,G\) come back with enormous coefficients, which is what Reduce is for: it repeatedly subtracts the multiple of \((f,g)\) nearest to \((F,G)\), rescaling to 53 significant bits each round so that the rounding stays exact enough to converge.

Three kinds of arithmetic, three Sage rings.#

Falcon is unusual in needing exact and inexact arithmetic side by side, and the implementation keeps them in separate, explicitly named Sage domains:

• the NTRU solver runs over ZZ[’x’], so the trapdoor equation \(fG-gF=q\) is established exactly rather than up to floating point – verify_ntru_equation(), at the end of sage/fips206_fndsa.sage, checks it as an identity in \(\mathbb{Z}[x]/(x^n+1)\);

• the public key and the verification relation \(s_1 = c - s_2 h\) are computed in \(\mathbb{F}_{12289}[x]/(x^n+1)\);

• the signing FFT runs over CDF, Sage’s complex double field, which is the IEEE 754 binary64 arithmetic that Falcon prescribes – not a higher-precision stand-in that would silently change the sampler’s output distribution.

The function verify_fft_against_exact_ring(), in the same file, closes the loop between the first and third of these, checking that pointwise multiplication in the FFT domain reproduces the product Sage computes exactly in \(\mathbb{Z}[x]/(x^n+1)\).

Validation without NIST vectors.#

Since FIPS 206 has none, FN-DSA is validated against the Falcon submission’s own known-answer tests [2], in four independent ways:

1. SamplerZ reproduces all sixteen test vectors of the Falcon specification’s sampler table, byte for byte – including the cases where rejection sampling iterates twice or BerExp consumes a second random byte;

2. for each Falcon KAT key, the private key is decoded, \(fG-gF=q\) is verified exactly, and the recomputed \(h=g f^{-1}\) re-encodes to the KAT public key byte for byte;

3. every Falcon KAT signature verifies, and the same signature over a tampered message is rejected;

4. signatures produced by this implementation under a Falcon KAT private key verify under the corresponding KAT public key.

Signing itself cannot be pinned to the KAT byte string, and the reason is instructive: Falcon signing is randomized, and the reference KATs were generated with the reference implementation’s own PRNG chain, so identical signatures would test PRNG replication rather than the scheme. Verification is deterministic, and it is checked byte-exactly. The gap is precisely the Gaussian sampler discussed in the next section – the part that is hardest to specify, hardest to implement, and hardest to test.

18.12Parameter sets#

Why there is no Level 3.#

The gap in that table is structural, not an oversight. The fast Fourier sampler recurses by halving the ring degree at every step down to a scalar leaf, so \(n\) must be a power of two: the admissible degrees are \(\dots, 256, 512, 1024, \dots\) with nothing in between. Concrete estimates place \(n=512\) at roughly \(128\) bits of classical security and \(n=1024\) well above \(250\), and no power-of-two ring lands in the middle. ML-DSA, whose security is tuned by the module dimensions \((k,\ell)\) over a fixed ring, has no such constraint — which is why it offers three levels and Falcon offers two. A deployment wanting a Category 3 margin from a lattice signature must take Falcon-1024 and the size that comes with it, or take ML-DSA instead.

18.13Pitfalls#

Pitfall 1: sampling short vectors deterministically.#

If the signer always returned the single closest lattice point (e.g. via Babai rounding), every signature would trace the shape of the secret basis, and a few signatures would reveal it. The Gaussian randomization of the output is essential, not a mere convenience.

Pitfall 2: treating the floating-point sampler as ordinary code.#

The sampler’s timing, branches, and rounding must not depend on secret data. Naive floating-point code leaks; Falcon implementations go to great lengths (emulated fixed-precision, careful table lookups) to be constant-time.

Pitfall 3: reusing the salt.#

The per-signature salt \(r\) must be fresh. Reusing it across different messages correlates their targets \(c\) and erodes the Gaussian’s hiding property.

18.14Summary#

FN-DSA (Falcon) is lattice hash-and-sign done right:

• the public key \(h\) and the secret short basis \((f,g,F,G)\) describe the same NTRU lattice, differing only in quality – the trapdoor;

• signing hashes the message to a target and uses a Gaussian sampler over the good basis to find a short, secret-hiding solution;

• verification recovers \(s_1=c-s_2 h\) and checks shortness, a closest-vector problem for anyone without the trapdoor;

• the reward is very compact signatures; the cost is delicate floating-point, constant-time engineering.

This completes the lattice-based signatures. ML-DSA and FN-DSA both live on lattices but reach a signature by opposite routes – Fiat–Shamir with aborts versus Gaussian hash-and-sign – and trade off size against implementation delicacy accordingly. The next part leaves lattices entirely for signatures built on a different hard problem: hash functions alone, culminating in the third signature standard, SLH-DSA (FIPS 205).

References