Lattice Digital Signatures

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.

Beginner's Intuition 💡

Imagine receiving a sealed physical letter. A Digital Signature is like a magically unbreakable wax seal on that letter. It mathematically guarantees two things: first, that the letter was definitely sent by the person whose stamp is on the seal, and second, that nobody has opened or tampered with the letter since it was sealed.

In the quantum-resistant lattice world, there are two main ways to create this "wax seal". You can either take a complex mathematical puzzle and squish it into a single step (Fiat-Shamir), or you can prove your identity by finding a highly specific point in a massive grid (Hash-and-Sign).

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.

Hash-and-Sign: The GPV Paradigm

The hash-and-sign paradigm, formalized by Gentry, Peikert, and Vaikuntanathan (GPV) in 2008, is the lattice analogue of RSA signatures. In RSA, signing a message means computing a modular root — the trapdoor makes this easy; without the trapdoor it's infeasible. In the GPV paradigm, signing means finding a short preimage of the hash of the message under a lattice trapdoor.

Construction — GPV Hash-and-Sign

Setup: Generate a random matrix $A \in \mathbb{Z}_q^{n \times m}$ together with a trapdoor — a short basis $$T$$ for the lattice $\Lambda_q^\perp(A)$ . The public key is $$A$$ ; the private key is $$T$$ .

Sign message $\mu$ :
1. Hash the message to a syndrome: $u = H(\mu) \in \mathbb{Z}_q^n$ where $$H$$ is modeled as a random oracle.
2. Use the trapdoor $$T$$ to sample a short vector $\sigma \in \mathbb{Z}^m$ satisfying $A\sigma = u \pmod{q}$ . This is CVP in the coset $\Lambda_q^\perp(A) + t_u$ where $$t_u$$ is any integer lift of $$u$$ , solved efficiently using the short basis $$T$$ .
3. Output $\sigma$ as the signature.

Verify: Check that $A\sigma = H(\mu) \pmod{q}$ and that $\|\sigma\| \leq \beta$ for the scheme's bound.

Security: Forging requires finding a short $\sigma^\prime$ with $A\sigma^\prime = H(\mu^\prime) \pmod{q}$ for a new message — an SIS instance. By Ajtai's theorem, this is as hard as worst-case SVP.

Critical requirement — Gaussian sampling: The sampling of $\sigma$ must follow a discrete Gaussian distribution over the coset, not just any short vector. Non-Gaussian sampling leaks information about the trapdoor $$T$$ across multiple signatures. GPV proved that Gaussian sampling is information-theoretically secure — each signature reveals nothing about the private key regardless of how many are collected.

The GPV paradigm is what Falcon implements, using the NTRU lattice structure to make the trapdoor generation and Gaussian sampling efficient via the fast Fourier nearest plane (ffNP) algorithm.

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]$ ).

Fiat-Shamir with Aborts — The Lyubashevsky Technique

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. Vadim Lyubashevsky (2009, 2012) solved this with rejection sampling.

Definition 32 — Fiat-Shamir with Aborts (Lyubashevsky 2012)

After computing $$z = y + cs$$ , the signer applies a rejection sampling step:

Rejection test: Accept the response $$z$$ with probability proportional to $\min\left(1,\; \frac{D_{\mathbb{Z}^m}(z)}{M \cdot D_{\mathbb{Z}^m, cs}(z)}\right)$ where $D_{\mathbb{Z}^m}$ is the target distribution (uniform over a range) and $$M$$ is a fixed constant. If rejected, abort and restart with a fresh mask $$y$$ .

Effect: Conditioned on acceptance, the distribution of $$z$$ is statistically independent of $$s$$ — it looks exactly like a uniform sample. Rejection sampling removes the statistical correlation between the output signature and the secret key.

In Dilithium's concrete instantiation, the rejection test checks $\|z\|_\infty \geq \gamma_1 - \beta$ — abort if any coefficient of $$z$$ is too close to the boundary. Expected restarts: about $e \approx 2.7$ per signature.

Security proof: In the random oracle model, the resulting signature scheme is EUF-CMA secure assuming Module-SIS is hard. A forger producing two valid signatures for the same commitment $$w$$ with different challenges $c, c^\prime$ yields $z - z^\prime = (c - c^\prime)s$ — solving SIS.

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.

Signature Size Comparison — Dilithium vs FALCON vs SPHINCS+

Signature size is a critical practical concern. Smaller signatures mean less bandwidth, faster transmission, and lower storage costs. The three NIST signature standards represent very different points in the size-security-simplicity tradeoff space.

NIST PQC Signature Size Comparison (128-bit security)

ML-DSA-44 (Dilithium):
Public key: 1,312 bytes | Signature: 2,420 bytes | Security: ~128 bits classical / quantum
Based on Module-LWE/SIS. Fiat-Shamir with aborts. Simple to implement in constant time. No floating-point arithmetic. Best choice for general use.

FN-DSA / Falcon-512:
Public key: 897 bytes | Signature: 666 bytes | Security: ~128 bits classical / quantum
Based on NTRU / Ring-SIS. Hash-and-sign with Gaussian sampling. Smallest signatures of any lattice scheme — competitive with pre-quantum ECDSA in raw bytes. Requires 53-bit floating-point precision; significantly harder to implement without timing side channels.

SLH-DSA / SPHINCS+-128s (hash-based, not lattice):
Public key: 32 bytes | Signature: 7,856 bytes | Security: ~128 bits classical, ~64 bits quantum
Based only on hash function security. Stateless. Largest signatures by far. Security relies on SHA-256 or SHAKE collision resistance — the most conservative possible assumption. Included as a backup in case lattice assumptions fail.

Key takeaway: Falcon gives signatures 3.6× smaller than Dilithium at the same security level, at the cost of significantly more complex implementation. SPHINCS+ is the most conservative choice but pays a 10–12× signature size penalty compared to lattice schemes. For TLS and code signing, ML-DSA is expected to dominate. For bandwidth-constrained applications, FN-DSA is compelling. For maximum conservatism, SLH-DSA provides insurance against lattice breaks.

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 ↗