Lattices.io — Mathematical Lattices & Post-Quantum Cryptography

A digital signature proves that a specific message was authorized by a specific party — and that the message hasn't been altered since. The signer uses a private key to produce a short proof attached to the message; anyone can verify the proof using only the public key. Classical signatures (RSA, ECDSA) are broken by Shor's algorithm. Lattice signatures are not.

Two fundamentally different paradigms exist for lattice signatures: Fiat-Shamir with Aborts (Dilithium / ML-DSA) and Hash-and-Sign (Falcon / FN-DSA). Both are NIST standards; each has distinct advantages that make it appropriate for different contexts.

What a Signature Scheme Must Guarantee

Correctness

A valid signature on a message should always verify. The signer and verifier must agree: if the signing algorithm runs honestly, the verification algorithm accepts. This is the easy part.

Unforgeability (EUF-CMA)

An adversary who sees many message-signature pairs — and can even choose the messages to be signed (chosen-message attack) — cannot produce a valid signature on any new message. This is the standard security notion: Existential Unforgeability under Chosen-Message Attack.

From SIS/LWE to unforgeability

In lattice signatures, unforgeability reduces to the hardness of SIS or Module-SIS. Forging a signature means finding a short vector satisfying the verification equation — directly an SIS problem. By Ajtai's theorem, this is as hard as worst-case SVP.

Approach 1: Fiat-Shamir with Aborts (Dilithium / ML-DSA)

The Fiat-Shamir transformation converts an interactive proof protocol into a non-interactive signature by replacing the verifier's random challenge with a hash of the message and the prover's commitment. Dilithium applies this idea to lattice commitments — but with a critical twist called rejection sampling, which prevents signature leakage.

The Basic Idea: A Zero-Knowledge Proof

Dilithium starts from a simple interactive proof that the signer knows a short vector $$s$$ satisfying $As = t \pmod{q}$ :

The Underlying Interactive Protocol

Prover (Signer) → Verifier:
1. Sample a random mask vector $$y$$ with coefficients in $[-\gamma_1, \gamma_1]$ . Compute commitment $w = Ay \pmod{q}$ . Send $$w$$ (or its high bits).

Verifier → Prover:
2. Send a random challenge $$c$$ — a polynomial with $\tau$ nonzero $\pm 1$ coefficients (a sparse challenge).

Prover → Verifier:
3. Compute response $$z = y + cs$$ . Send $$z$$ .

Verifier checks:
4. Verify that $$Az - ct = Ay + cAs - ct = Ay = w$$ and that $$z$$ is short (coefficients in $[-\gamma_1 + \beta, \gamma_1 - \beta]$ ).

The Problem: Signature Leakage

The naive Fiat-Shamir approach has a critical flaw: the response $$z = y + cs$$ has a distribution that depends on the secret $$s$$ . After seeing enough signatures, an attacker could recover $$s$$ by statistical analysis. This is not a theoretical concern — similar leakage was exploited to break early ECDSA implementations.

The Fix: Rejection Sampling

Definition 32 — Rejection Sampling in Dilithium

After computing $$z = y + cs$$ , the signer checks whether $$z$$ is "too close" to the boundary — specifically, whether any coefficient of $$z$$ exceeds $\gamma_1 - \beta$ . If yes: abort. Restart the entire signing process with a fresh $$y$$ .

When a response is accepted, its distribution is statistically independent of $$s$$ — it looks exactly like a uniform sample from the accepted range. Rejection sampling removes the correlation between the signature and the secret key.

Expected number of restarts: about $e \approx 2.7$ per signature (with Dilithium parameters). Signing is non-deterministic but outputs are unlinkable.

Full ML-DSA Signing Protocol

ML-DSA-65 Signing (Simplified)

Keys: Matrix $A \in R_q^{k \times \ell}$ (public), secrets $s_1 \in R_q^\ell, s_2 \in R_q^k$ (small), public key $$t = As_1 + s_2$$ .

Sign message $$M$$ :
1. Hash $$M$$ and public key to get $\mu$ .
2. Sample mask $y \leftarrow D_{\gamma_1}^\ell$ .
3. $$w = Ay$$ . Compute hint bits from high bits of $$w$$ .
4. Challenge: $c = H(\mu, \mathrm{HighBits}(w))$ .
5. Response: $$z = y + cs_1$$ .
6. Rejection test: If $\|z\|_\infty \geq \gamma_1 - \beta$ or hints are inconsistent, abort and restart from step 2.
7. Output signature $$(c, z, h)$$ where $$h$$ are hint bits for recovering the commitment.

Verify: Reconstruct $w' = Az - ct_1 \cdot 2^d$ using hint bits, recompute challenge, check it matches $$c$$ and $$z$$ is short.

Approach 2: Hash-and-Sign (Falcon / FN-DSA)

Falcon takes a completely different approach. Instead of an interactive protocol turned non-interactive, it uses the classical "hash-and-sign" paradigm: hash the message to a point in the lattice coset, then use the trapdoor to find a short preimage. The trapdoor is the NTRU private key.

Falcon Signing Protocol

Key generation: Generate NTRU key pair with public key $$h$$ and trapdoor $$(f, g, F, G)$$ satisfying $$fG - gF = q$$ in $$R$$ .

Sign:
1. Sample random salt $$r$$ . Compute target $c = H(r \| M) \in R_q$ .
2. Use Fast Fourier Nearest Plane (ffNP) algorithm with trapdoor $$(f, g, F, G)$$ to sample a short $(s_1, s_2) \in \mathbb{Z}^{2n}$ satisfying $s_1 + h \cdot s_2 = c \pmod{q}$ . This is CVP in the NTRU lattice, solved efficiently via the trapdoor.
3. Output signature $$(r, s_2)$$ .

Verify: Recompute $$c$$ , check that $$(c - hs_2, s_2)$$ has small norm $\leq \sqrt{\beta_\sigma}$ .

The Challenge: Gaussian Sampling

Falcon's hash-and-sign approach requires sampling from a discrete Gaussian distribution over the NTRU lattice coset. This is not optional — sampling from the wrong distribution leaks the private key. The GPV framework (Gentry-Peikert-Vaikuntanathan 2008) proved that Gaussian sampling ensures information-theoretic security of the signature.

Gaussian sampling over the NTRU lattice is done via the Fast Fourier Nearest Plane(ffNP) algorithm — a recursive algorithm that exploits the ring structure (NTT) to sample efficiently. However, this requires careful floating-point arithmetic, making constant-time implementation significantly harder than for Dilithium.

ML-DSA vs FN-DSA: When to Use Which

Prefer ML-DSA (Dilithium) when:

— Implementation simplicity and auditability are critical.
— Constant-time guarantees are required without floating-point.
— Side-channel resistance is a primary concern.
— Signature size is acceptable (≈2.4 KB at Level 2).

Use cases: TLS certificates, code signing, firmware updates, general software applications.

Prefer FN-DSA (Falcon) when:

— Signature size must be minimized (≈666 bytes at Level 1).
— Bandwidth is severely constrained (IoT, satellite, embedded).
— Your platform can provide the required precision floating-point arithmetic.

Use cases: blockchain transactions, constrained devices, protocols where many signatures are transmitted.

Parameter Tables

ML-DSA (Dilithium) Parameter Sets

ML-DSA-44: $k=4, \ell=4$ . PK: 1,312 B. Sig: 2,420 B. Security: ~128 bits.

ML-DSA-65: $k=6, \ell=5$ . PK: 1,952 B. Sig: 3,293 B. Security: ~192 bits.

ML-DSA-87: $k=8, \ell=7$ . PK: 2,592 B. Sig: 4,595 B. Security: ~256 bits.

All use $$n=256$$ , $$q=8380417$$ (a prime with $q \equiv 1 \pmod{512}$ ).

FN-DSA (Falcon) Parameter Sets

Falcon-512: $$n=512$$ . PK: 897 B. Sig: 666 B. Security: ~128 bits.

Falcon-1024: $$n=1024$$ . PK: 1,793 B. Sig: 1,280 B. Security: ~256 bits.

Both use NTRU over $\mathbb{Z}[x]/(x^n+1)$ with $$q = 12289$$ .

References and Further Reading

Key papers on lattice signatures

Micciancio & Regev, "Lattice-based Cryptography" (2009) — §6 covers lattice identification and signature schemes. PDF ↗

Silverman, "An Introduction to Lattices, Lattice Reduction, and Lattice-Based Cryptography" — includes treatment of signature schemes. IAS PDF ↗

Lattice Reduction papers on Academia.edu ↗