03 — Trapdoor Sampling

The Core Idea

FN-DSA signatures use a trapdoor — a secret mathematical structure that makes an otherwise hard problem easy.

Without trapdoor: Finding the nearest lattice point is hard (like finding a needle in a 512-dimensional haystack).

With trapdoor: Finding the nearest lattice point is fast (like having a magnet that pulls the needle to you).

The Trapdoor: Short Basis

Recall from NTRU lattices: the private key contains a short basis for the lattice:

$\displaystyle B_{good} = \begin{pmatrix} g & G \\ f & F \end{pmatrix}$

Where:

• f, g are the small NTRU secret polynomials
• F, G are computed such that the basis is short and has the correct volume

Computing F and G

Using the extended Euclidean algorithm on the polynomials f and g:

1. Find polynomials a and b such that: a·f + b·g = 1 (Bezout identity)
2. Compute: F = q·b and G = -q·a
3. Reduce: Use lattice reduction (LLL or BKZ) to make F and G as short as possible

This gives a basis where both vectors are short — the "trapdoor."

Nearest Lattice Point Problem

Given a target point t (in the same space as the lattice), find the lattice point v closest to t:

$\displaystyle v = \arg\min_{v \in \text{Lattice}} ||t - v||$

Without Trapdoor (Hard)

Try all lattice points near t. In dimension 512, there are exponentially many candidates.

With Trapdoor (Fast: Babai's Rounding)

1. Express t in the trapdoor basis:

   $\displaystyle t = \alpha_1 \cdot b_1 + \alpha_2 \cdot b_2$

   Where b₁, b₂ are the short basis vectors.

2. Round the coefficients to nearest integers:

   $\displaystyle v = \lfloor \alpha_1 \rceil \cdot b_1 + \lfloor \alpha_2 \rceil \cdot b_2$

3. v is a lattice point close to t.

Why it works: When basis vectors are short and nearly orthogonal, rounding gives the nearest lattice point.

Gaussian Sampling (FALCON's Improvement)

Babai rounding works, but the result is not always the closest point, and the distribution of errors leaks information about the trapdoor.

FALCON improves this with discrete Gaussian sampling:

Discrete Gaussian Distribution

A probability distribution over integers where:

$\displaystyle P(x) \propto e^{-x^2 / (2\sigma^2)}$

• σ is the standard deviation (width of the bell curve)
• Probabilities decrease rapidly as |x| increases
• Most samples are small, a few are moderate, rarely large

Sampling Algorithm

Instead of rounding, sample coefficients from a discrete Gaussian centred at the real coefficients:

1. Compute real coefficients: $\alpha_1, \alpha_2$ (as before)
2. Sample: $c_1 \sim D_{\mathbb{Z}, \sigma, \alpha_1}$ (discrete Gaussian centred at $\alpha_1$)
3. Sample: $c_2 \sim D_{\mathbb{Z}, \sigma, \alpha_2}$ (discrete Gaussian centred at $\alpha_2$)
4. Compute: $v = c_1 \cdot b_1 + c_2 \cdot b_2$

Why Gaussian Sampling Is Better

The GPV Framework

Gentry, Peikert, and Vaikuntanathan (2008) proved:

If signatures are sampled from a discrete Gaussian with the right parameters, the distribution of signatures is statistically close to an ideal Gaussian over the lattice — independent of the trapdoor.

This means:

• An attacker seeing many signatures learns nothing about the trapdoor
• The security proof is rigorous (not heuristic)
• The signature size is minimised (tight Gaussian = short signatures)

Fast Fourier Transform for Speed

The naive Gaussian sampling over a 512-dimensional lattice is slow. FN-DSA uses the Number Theoretic Transform (NTT) — a fast Fourier transform over finite fields:

NTT Speed-Up

How NTT Applies to Sampling

1. Convert the trapdoor basis to NTT domain
2. Sample in NTT domain (coefficients are independent after NTT)
3. Convert back to polynomial domain

Critical insight: In the NTT domain, the covariance matrix of the Gaussian becomes diagonal. Sampling independent Gaussians per coefficient is trivial.

Security Parameters

Resources

• Gentry, Peikert, Vaikuntanathan, "Trapdoors for hard lattices and new cryptographic constructions" (2008), STOC
• Ducas et al., "FALCON: Fast-Fourier Lattice-based Compact Signatures over NTRU" (2018), NIST submission
• Prest, "Gaussian sampling in lattice-based cryptography" (2017), PhD thesis, École Normale Supérieure
• NIST FIPS 206, Section 5: Trapdoor Sampling and FFT