03 — Lattice Signatures

The Building Block: Short Integer Solution (SIS)

Recall from ML-KEM: the Shortest Vector Problem (SVP) asks for the shortest non-zero vector in a lattice.

For signatures, we use a related problem:

Short Integer Solution (SIS): Given a matrix A and a bound β, find a short vector s such that A·s = 0 (mod q) and ||s|| ≤ β.

This is like finding a combination of columns of A that cancels out perfectly — but using only small coefficients.

Why SIS Is Good for Signatures

SIS has a beautiful property for cryptography:

With a trapdoor (good basis): Easy to find short solutions. Without a trapdoor (knowing only A): Hard to find any short solution.

This is exactly what we need for signatures:

• Private key = trapdoor (good basis) → can create short solutions
• Public key = A (bad basis) → can't create short solutions
• Signature = a short solution for a specific challenge

The Identification Protocol

Before we get to signatures, understand the interactive identification protocol:

Three-Party Game

Prover (Signer)                 Verifier
  |                               |
  |-- Commitment: w = A·y         |
  |   (y = random short vector)   |
  |                               |
  |========= w ==================>|
  |                               |
  |          Challenge: c          |
  |          (random small poly)  |
  |<======== c ==================|
  |                               |
  |-- Response: z = y + c·s       |
  |   (s = secret short vector)   |
  |                               |
  |========= z ==================>|
  |                               |
  |          Verify:              |
  |          A·z ?= w + c·t       |
  |          (where t = A·s)      |
  |                               |
  |<==== Accept / Reject =======|

Why It Works

Correctness:

A·z = A·(y + c·s) = A·y + c·A·s = w + c·t

The verifier's check passes because the prover knows s.

Security: A cheating prover who doesn't know s can't create a valid z for an unpredictable challenge c.

From Identification to Signatures: Fiat-Shamir

The brilliant trick (Fiat & Shamir, 1986): replace the verifier's random challenge with a hash of the commitment and message.

Signer:
  1. Pick random y (short vector)
  2. Compute w = A·y
  3. Compute c = Hash(w || message)
  4. Compute z = y + c·s
  5. Output signature: (w, z)

Verifier:
  1. Recompute c = Hash(w || message)
  2. Check: A·z ?= w + c·t
  3. Check: z is short (||z|| ≤ bound)
  4. Accept if both pass

Why it's secure: The hash function acts as a "random oracle" — unpredictable and uncontrollable by the signer. Without knowing s, you can't create a z that passes the check.

The Problem: Signatures Leak Information

Each signature reveals:

z = y + c·s

If you see many signatures, you see many linear combinations of s. With enough equations, you could solve for s.

The solution: Make y MUCH larger than s, so the noise y drowns out the signal c·s.

But then z = y + c·s is also large — and the verifier requires z to be short!

The Solution: Rejection Sampling

Here's the clever trick used in ML-DSA:

1. Pick a random y from a very wide distribution.
2. Compute z = y + c·s.
3. Check: is z "well-shaped" (does it look like it came from the wide distribution, not the narrow secret distribution)?
4. If YES → output z as the signature.
5. If NO → throw it away and try again with a new y.

This is called rejection sampling — the signer keeps trying until the response doesn't leak information about s.

Why It Works

• The distribution of z (after rejection) is statistically close to the distribution of y
• An observer seeing z learns nothing about s
• The expected number of trials is small (2–5 for typical parameters)

See the next article: 04 — Rejection Sampling for the full details.

Lattice vs. Classical Signatures

Resources

• Lyubashevsky, "Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures" (2009), ASIACRYPT.
• Ducas et al., "CRYSTALS-Dilithium: A lattice-based digital signature scheme" (2018), IACR TCHES.
• Fiat & Shamir, "How to prove yourself: Practical solutions to identification and signature problems" (1986), CRYPTO.