02 — NTRU Lattices

ML-DSA's Foundation: Module-LWE

Recall from ML-KEM:

• Module-LWE: Given A (public matrix) and t = A·s + e (public vector), find the secret s (small vector).
• The hardness comes from the noisy linear equations.

FN-DSA's Foundation: NTRU

NTRU uses a different lattice structure:

The NTRU Problem

Given polynomials in the ring R_q = Z_q[X]/(X^n + 1):

$\displaystyle h = g \cdot f^{-1} \pmod q$

Where:

• f and g are small secret polynomials (sparse, few non-zero coefficients)
• h is the public polynomial
• f⁻¹ is the modular inverse of f modulo q

Find f and g given h.

Why It's Hard

The equation $h = g \cdot f^{-1}$ can be rewritten as:

$\displaystyle h \cdot f = g \pmod q$

Or in vector form:

$\displaystyle \begin{pmatrix} H \\ I \end{pmatrix} f = \begin{pmatrix} g \\ f \end{pmatrix}$

Where H is the circulant matrix representing multiplication by h. This is a short vector in a lattice problem:

• The lattice is generated by the columns of the matrix above
• (g, f) is a short vector in this lattice
• Finding it requires solving a hard lattice problem

NTRU vs. Module-LWE

The Trapdoor: Key Generation

The private key in FN-DSA is not just f and g — it's a trapdoor basis for the NTRU lattice:

Good Basis (Private)

The private key contains a short basis for the lattice:

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

Where G and F are computed such that:

• The basis vectors are short (small coefficients)
• The determinant is q^n (correct volume for the lattice)

This is a Gram-Schmidt orthogonalisation problem. The trapdoor allows finding the nearest lattice point efficiently.

Bad Basis (Public)

The public key is the "bad" basis — just the single polynomial h. From h, the lattice is well-defined, but finding short vectors is hard.

Signing = Nearest Lattice Point

To sign a message:

1. Hash the message to a target point t in space
2. Use the trapdoor (good basis) to find the nearest lattice point v to t
3. The difference s = t - v is the signature
4. s is short because v is the nearest lattice point

Message ──> Hash ──> Target point t
                         │
                         │  (trapdoor: good basis)
                         v
                    Nearest lattice point v
                         │
                         v
                    Signature: s = t - v

Why NTRU Enables Small Signatures

The trapdoor sampling produces signatures that are:

• Short: The signature is the difference between target and nearest lattice point
• Compact: Encoded efficiently using the Gaussian distribution
• Provably secure: The distribution of signatures is statistically close to an ideal Gaussian

The signature size depends on:

• The dimension n (higher = larger signatures but more security)
• The Gaussian width σ (wider = larger signatures but easier to compute)
• The modulus q (larger = more room for short vectors)

FN-DSA carefully balances these to achieve 666-byte signatures at Level 1 security.

Historical Context

NTRU was proposed in 1996 by Hoffstein, Pipher, and Silverman — before the term "post-quantum cryptography" existed:

• 1996: NTRU encryption scheme published
• 2001: NTRU Sign (signature scheme, later broken)
• 2012: NTRU modifications improve security
• 2017: FALCON (Fast Fourier lattice-based compact signatures) proposed
• 2022: FALCON selected by NIST as a standard
• 2024: FALCON standardised as FN-DSA (FIPS 206)

NTRU is one of the oldest post-quantum proposals, giving it 25+ years of cryptanalysis.

Resources

• Hoffstein, Pipher, Silverman, "NTRU: A ring-based public key cryptosystem" (1998), ANTS-III
• Ducas et al., "FALCON: Fast-Fourier Lattice-based Compact Signatures over NTRU" (2018), NIST submission
• NIST FIPS 206, Section 3: NTRU Lattice Background