FN-DSA (Falcon): Draft-Oriented Walkthrough

Every code listing from this chapter of Applied Post-Quantum Cryptography — 2 in total, 2 runnable here. Edit any cell and press Run.

The book's snippets build on each other down the chapter, but a Sage Cell kernel runs one cell and keeps no state afterwards, so each cell replays the earlier listings with apqc_book. That call is the only thing added to the book's own code.

← the playground

Listing 1 — SageMath 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.

Listing 2 — Solving the NTRU equation.

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