Signature schemes

ML-DSA-87 explained mathematically

How ML-DSA-87 (FIPS 204) signs a McGesund review — from module-LWE through rejection sampling to verification in the browser.

Last updated: 2026-09-07

1. What this is about

When someone submits a review on McGesund, more happens in the background than the text suggests. The review is signed digitally on submission. Every visitor can recompute that signature later in their own browser — without trusting us and without asking us.

For customers from the Pro plan upwards this is done with ML-DSA-87, among others. This article explains what happens mathematically.

One thing up front:

ML-DSA is not encryption. The review text stays publicly readable — that is the point of a review. ML-DSA does not prove secrecy, it proves origin and integrity.

ML-DSA was developed from CRYSTALS-Dilithium and is standardised as FIPS 204. The number 87 denotes the parameter level. There are three:

  • ML-DSA-44
  • ML-DSA-65
  • ML-DSA-87

ML-DSA-87 is the highest and sits in NIST security category 5.

2. What exactly gets signed?

It is not the review text itself that goes into the signature but a compact data object that pins the text down unambiguously. At McGesund it looks essentially like this:

{
  "v":   1,
  "typ": "rev-comment",
  "f":   "<company ID>",
  "c":   "<review ID>",
  "h":   "<SHA-256 of the review text>",
  "rh":  "<SHA-256 of the entire submission record>",
  "rv":  1,
  "qh":  "<SHA-256 of the QR envelope, QR reviews only>",
  "iat": 1757203200
}

This object is our message mm. It ties six statements together:

  1. Which company the review belongs to (f)
  2. Which review is meant (c)
  3. What text was behind it — as a hash value (h)
  4. What record as a whole was submitted (rh): text, hearts, geo status and occasion details, canonically serialised and hashed — in schema version rv
  5. Which QR code the review came from (qh); without a QR the field is omitted
  6. When it was signed (iat)

If someone later changes a single character of the review text, h no longer fits — and neither does rh. Anyone who instead only moves the hearts leaves h untouched but breaks rh. And if someone changes one of those hash values, the signature no longer fits. That chain is precisely the point.

3. What the signature has to achieve

A visitor reading the review should be able to check three things for themselves:

  1. The review really was issued by McGesund.
  2. The text has not been changed since submission.
  3. Nobody can invent a new, valid-looking review.

That is what the key pair is for:

  • a private key — held exclusively by the signing service
  • a public key — anyone may have it; it is addressed via the key ID (kid) in the envelope

Signing uses the private key. Verifying uses the public one — in the reader's browser, not on our server.

4. Why a post-quantum scheme at all?

Many signature schemes in common use today rest on factoring large numbers or on discrete logarithms. A sufficiently powerful quantum computer could solve exactly those problems considerably faster with known algorithms.

For a review this is not an academic question. A review should still be verifiable in ten years. Whoever signs today signs for the entire lifetime of the entry.

ML-DSA therefore uses a different foundation:

lattice problems\boxed{\text{lattice problems}}

More precisely: module-LWE and module-SIS.

5. What is a lattice?

At first, just points in space. Take two vectors:

b1=(2,0),b2=(1,2).b_1=(2,0), \qquad b_2=(1,2).

All integer combinations

a b1+b b2,a,b∈Za\,b_1+b\,b_2, \qquad a,b\in\mathbb{Z}

form the lattice. For example:

2b1+b2=(4,0)+(1,2)=(5,2).2b_1+b_2 = (4,0)+(1,2) = (5,2).
b₁ = (2,0)b₂ = (1,2)(5,2)0
Two vectors, all integer combinations of them: a lattice. The marked point arises from two times b₁ and one times b₂.

The decisive part:

In small dimensions lattice problems are easy. In very high dimensions certain tasks become extremely difficult.

6. Polynomials instead of single numbers

ML-DSA does not compute with 2D vectors but with polynomials and vectors of polynomials.

A polynomial such as

a(x)=1+2x+x3a(x)=1+2x+x^3

can be written as a list of coefficients:

a=(1,2,0,1).a=(1,2,0,1).

The arithmetic happens in a ring:

Rq=Zq[x]/(xn+1).R_q=\mathbb{Z}_q[x]/(x^n+1).

That means two things:

  • Zq\mathbb{Z}_q: arithmetic modulo qq
  • xn=−1x^n=-1: an extra rule that fixes the polynomial length

For all three ML-DSA levels:

n=256,q=8380417.n=256, \qquad q=8380417.

So a polynomial has 256 coefficients, considered modulo 8,380,417. What changes between the levels is not nn or qq but the size of the matrices — more on that later.

As an aside: polynomial multiplication in this ring runs in practice via the NTT, the number-theoretic variant of the fast Fourier transform. ML-DSA therefore by no means does without FFT ideas; they simply sit in the arithmetic rather than in the signature principle.

7. The central trick: module-LWE

The core idea is module learning with errors:

t=As1+s2(modq).\mathbf{t}=\mathbf{A}\mathbf{s}_1+\mathbf{s}_2 \pmod q.

Here:

  • A\mathbf{A} — public, seemingly random matrix of polynomials
  • s1,s2\mathbf{s}_1,\mathbf{s}_2 — small secret vectors
  • t\mathbf{t} — public value

An attacker knows A\mathbf{A} and t\mathbf{t}, but not s1,s2\mathbf{s}_1,\mathbf{s}_2. To them the equation looks like a random equation with noise. They should not be able to compute the small secrets back from it efficiently.

8. A tiny numeric example

We deliberately take a ridiculously small variant — ordinary numbers instead of polynomials, dimension 2 instead of 256, and

q=17.q=17.

Let

A=(3572),s1=(1−1),s2=(10).A=\begin{pmatrix}3&5\\7&2\end{pmatrix}, \qquad \mathbf{s}_1=\begin{pmatrix}1\\-1\end{pmatrix}, \qquad \mathbf{s}_2=\begin{pmatrix}1\\0\end{pmatrix}.

Then:

As1=(3−57−2)=(−25),A\mathbf{s}_1=\begin{pmatrix}3-5\\7-2\end{pmatrix}=\begin{pmatrix}-2\\5\end{pmatrix},
t=As1+s2=(−25)+(10)=(−15)  ≡  (165)(mod17).\mathbf{t}=A\mathbf{s}_1+\mathbf{s}_2=\begin{pmatrix}-2\\5\end{pmatrix}+\begin{pmatrix}1\\0\end{pmatrix}=\begin{pmatrix}-1\\5\end{pmatrix} \;\equiv\; \boxed{\begin{pmatrix}16\\5\end{pmatrix}} \pmod{17}.

At this miniature size you could try out every possibility. With ML-DSA-87, A\mathbf{A} is an 8×78\times 7 matrix of polynomials with 256 coefficients each — that is over 14,000 unknowns in the lattice structure.

9. The signing service's key pair

The private key contains, among other things, the small vectors s1,s2\mathbf{s}_1,\mathbf{s}_2. With ML-DSA-87 their coefficients come from the interval

[−η,η]withη=2,[-\eta,\eta] \quad\text{with}\quad \eta=2,

that is, from {−2,−1,0,1,2}\{-2,-1,0,1,2\}. This smallness is not a detail but the core: only because the secrets are small does a hard lattice problem arise at all.

The public key is, simplified,

(ρ,t1).(\rho,\mathbf{t}_1).

ρ\rho is a seed from which A\mathbf{A} can be reconstructed deterministically — so the matrix does not have to be transmitted. t1\mathbf{t}_1 is the upper bits of t\mathbf{t}; the lower d=13d=13 bits are dropped, which shrinks the key considerably. That omission is the reason for the so-called hints later on.

This produces the asymmetry we want:

verify publicly  ≠  sign secretly\boxed{\text{verify publicly}\;\neq\;\text{sign secretly}}

10. The review becomes a number

The signing service first hashes the payload object from section 2:

μ=H(m).\mu=H(m).

In our toy example we use an artificial mini hash. In the real system μ\mu is 512 bits long and additionally binds in the public key — which means a signature cannot be reinterpreted as belonging to another key.

11. Commitment

The signing service draws a random small vector y\mathbf{y}. In our example:

y=(2−1).\mathbf{y}=\begin{pmatrix}2\\-1\end{pmatrix}.

From it comes an intermediate value, the commitment:

w=Ay=(3⋅2+5⋅(−1)7⋅2+2⋅(−1))=(112).\mathbf{w}=A\mathbf{y} =\begin{pmatrix}3\cdot2+5\cdot(-1)\\7\cdot2+2\cdot(-1)\end{pmatrix} =\begin{pmatrix}1\\12\end{pmatrix}.

This is not yet a signature.

12. The review turns into a challenge

Message and commitment are hashed together:

c=H(μ,w).c=H(\mu,\mathbf{w}).

With ML-DSA-87, cc is a polynomial with exactly τ=60\tau=60 coefficients from {−1,+1}\{-1,+1\}; the remaining 196 are zero. This structure is intentional: it keeps c⋅s1c\cdot\mathbf{s}_1 small.

In our toy example we simply set

c=2.c=2.

13. The actual signature

z=y+c s1.\mathbf{z}=\mathbf{y}+c\,\mathbf{s}_1.

With our values:

c s1=2(1−1)=(2−2),c\,\mathbf{s}_1=2\begin{pmatrix}1\\-1\end{pmatrix}=\begin{pmatrix}2\\-2\end{pmatrix},
z=(2−1)+(2−2)=(4−3)\mathbf{z}=\begin{pmatrix}2\\-1\end{pmatrix}+\begin{pmatrix}2\\-2\end{pmatrix} =\boxed{\begin{pmatrix}4\\-3\end{pmatrix}}

14. The step that is easily missed: rejection sampling

Here lies the point where ML-DSA differs from a naive construction — and it is not optional.

z=y+c s1\mathbf{z}=\mathbf{y}+c\,\mathbf{s}_1 contains the secret s1\mathbf{s}_1. If you simply always released z\mathbf{z}, then s1\mathbf{s}_1 could be extracted statistically from enough signatures. For a review platform with a great many signatures per day that is not a theoretical risk.

The signing service therefore checks before releasing whether z\mathbf{z} gives away too much, and discards the signature otherwise — then it starts over with a fresh random y\mathbf{y}. This is called Fiat-Shamir with aborts.

The condition is essentially:

∥z∥∞<γ1−β.\|\mathbf{z}\|_\infty < \gamma_1-\beta.
commitment w = Aychallenge c = H(μ, w)response z = y + c · s₁‖z‖∞ < γ₁ − β ?yessignature is releasedno — new y
Three steps and a loop. If z comes out too large, nothing is patched up — the entire pass is discarded and begun again with a fresh random y. That is why signing here is a loop, not a single step.

For ML-DSA-87, γ1=219\gamma_1=2^{19} and β=τ⋅η=60⋅2=120\beta=\tau\cdot\eta=60\cdot2=120. On top of that comes a second bound on the lower bits. In practice several passes are normal — signing is therefore a loop, not a single step.

Important for verification: the browser checks exactly this bound later on. A signature with coefficients that are too large is rejected even if the equation works out.

15. Why the browser can check this

The reader's browser knows:

  • the review and therefore mm
  • the public key (ρ,t1)(\rho,\mathbf{t}_1)
  • the signature (c~,z,h)(\tilde c,\mathbf{z},\mathbf{h})

It does not know s1\mathbf{s}_1. The relationship that gets it further anyway:

z=y+c s1⟹Az=Ay+c As1.\mathbf{z}=\mathbf{y}+c\,\mathbf{s}_1 \quad\Longrightarrow\quad A\mathbf{z}=A\mathbf{y}+c\,A\mathbf{s}_1.

And because

t=As1+s2\mathbf{t}=A\mathbf{s}_1+\mathbf{s}_2

holds, the unknown As1A\mathbf{s}_1 can be replaced by the public value:

Az−c t=Ay−c s2.A\mathbf{z}-c\,\mathbf{t}=A\mathbf{y}-c\,\mathbf{s}_2.

That is the central equation — and it says something important: the browser reconstructs AyA\mathbf{y} not exactly, but only up to the small term c s2c\,\mathbf{s}_2.

16. The miniature example to the end

We had:

A=(3572),t=(−15),c=2,z=(4−3).A=\begin{pmatrix}3&5\\7&2\end{pmatrix},\quad \mathbf{t}=\begin{pmatrix}-1\\5\end{pmatrix},\quad c=2,\quad \mathbf{z}=\begin{pmatrix}4\\-3\end{pmatrix}.

Let us work it through:

Az=(12−1528−6)=(−322),c t=2(−15)=(−210),A\mathbf{z}=\begin{pmatrix}12-15\\28-6\end{pmatrix}=\begin{pmatrix}-3\\22\end{pmatrix}, \qquad c\,\mathbf{t}=2\begin{pmatrix}-1\\5\end{pmatrix}=\begin{pmatrix}-2\\10\end{pmatrix},
Az−c t=(−112).A\mathbf{z}-c\,\mathbf{t}=\begin{pmatrix}-1\\12\end{pmatrix}.

The original commitment was

w=(112).\mathbf{w}=\begin{pmatrix}1\\12\end{pmatrix}.

The difference is

(−112)−(112)=(−20)=−c s2.\begin{pmatrix}-1\\12\end{pmatrix}-\begin{pmatrix}1\\12\end{pmatrix} =\begin{pmatrix}-2\\0\end{pmatrix} =-c\,\mathbf{s}_2.

Exactly the small error term predicted. The verifier does not get w\mathbf{w} but something that lies close to w\mathbf{w}.

That is precisely why ML-DSA does not compare the values themselves but their upper bits. And that is precisely why the signature additionally contains a hint vector h\mathbf{h}: it states compactly at which positions the rounding tipped over a boundary because of the small error term. With ML-DSA-87 at most ω=75\omega=75 such hints are allowed. They do not give away the secret — they only repair the rounding.

Finally the browser recomputes the challenge. If it matches,

cnew=c,c_{\text{new}}=c,

and all norms lie within the bounds, the signature is valid.

17. What happens if someone changes the review?

Suppose someone with database access — including someone at our company — changes the review text or one of the hearts. Then at least one of the two hash values in the payload changes (h for the text, rh for any field of the record):

H(m)≠H(m′).H(m)\neq H(m').

That changes the challenge:

c≠c′.c\neq c'.

But the existing signature was produced for the old challenge. The browser recomputes and finds:

cnew≠csignature⟹Signature invalidc_{\text{new}}\neq c_{\text{signature}} \quad\Longrightarrow\quad \boxed{\text{Signature invalid}}

The decisive sentence: we can delete a review, but we cannot alter it unnoticed. At McGesund the same check additionally runs nightly on the server across the whole stock — a review that fails it no longer counts towards the company's average.

18. Why can nobody invent a signature?

An attacker knows A\mathbf{A} and t\mathbf{t}, but not s1,s2\mathbf{s}_1,\mathbf{s}_2. To build a valid signature they would have to find a triple (c~,z,h)(\tilde c,\mathbf{z},\mathbf{h}) that

  • satisfies the verification equation and
  • keeps within the norm bounds and
  • matches the challenge that arises from exactly those values themselves.

At its core this amounts to a hard lattice problem — specifically module-SIS: finding short solutions of a homogeneous equation modulo qq. The smallness condition is not decoration here but the actual difficulty. Without it a solution would be trivial.

public data  →  hard lattice problem\boxed{\text{public data}\;\rightarrow\;\text{hard lattice problem}}

19. Why "module"?

The word describes the structure between simple vectors and general lattices. Instead of computing with single numbers, ML-DSA works with vectors of polynomials:

a=(a1(x),a2(x),…,ak(x)),\mathbf{a}=(a_1(x),a_2(x),\ldots,a_k(x)),

and with matrices of those:

A=(a1,1(x)a1,2(x)⋯a2,1(x)a2,2(x)⋯⋮⋮⋱).\mathbf{A}= \begin{pmatrix} a_{1,1}(x)&a_{1,2}(x)&\cdots\\ a_{2,1}(x)&a_{2,2}(x)&\cdots\\ \vdots&\vdots&\ddots \end{pmatrix}.

The advantage: you get the high dimension of a lattice while keeping a compact, efficiently computable representation. Security can be tuned via the matrix size without changing the ring.

20. Why 87 of all numbers?

The three levels differ not in the ring but in the dimensions:

ParameterML-DSA-44ML-DSA-65ML-DSA-87
Matrix size (k,ℓ)(k,\ell)4×44\times46×56\times58×78\times7
Secret range η\eta242
Challenge weight τ\tau394960
Public key1,312 B1,952 B2,592 B
Signature2,420 B3,309 B4,627 B
NIST category235

Worth noting: ML-DSA-87 is not simply "ML-DSA-65, only bigger". The secret range η\eta goes back down from 4 to 2; the security here comes from the larger matrix, not from larger coefficients. It is an independent, standardised choice of parameters.

larger mathematical structure→higher security margin\boxed{\text{larger mathematical structure}\rightarrow\text{higher security margin}}

The price: 4,627 bytes per signature — per stamp that is stored and delivered to the browser when verifying. That is why FALCON, which manages with 1,280 bytes, is available at McGesund alongside ML-DSA-87.

21. Fiat-Shamir: why it works without a counterpart

An interactive proof would run like this:

  1. The signing service sends a commitment.
  2. The verifier sends a random challenge.
  3. The signing service responds.
  4. The verifier checks.

With a review there is no such dialogue — the reader arrives months later. The solution is the Fiat-Shamir transformation: the challenge is not rolled but hashed from the data itself:

c=H(public key,  message,  commitment).c=H(\text{public key},\;\text{message},\;\text{commitment}).

That turns a dialogue into a document. The signing service cannot pick its challenge, because doing so would mean controlling the hash.

22. The whole process

SIGNING SERVICE (MCGESUND)VISITOR'S BROWSERprivate key s₁, s₂payload m = {company, review, h, rh, iat}hash μrandom vector ycommitment w = Aychallenge c = H(μ, w)z = y + c · s₁signature (c, z, hints) + kidreview + signature + public keyAz − c·t → upper bits + hintsrecompute challengerecomputed challenge = supplied one?validinvaliddiscard if z is too large(rejection sampling)
The full path of a review. The dashed return is the rejection sampling — it is taken as often as needed until z is small enough to give nothing away about the secret key.

23. What McGesund does with it in practice

Three layers interlock:

The envelope. Every signed review carries an Ed25519 signature. That is the mandatory variant — classical, tiny, natively verifiable in every browser.

The post-quantum stamps. In addition, one or two quantum-resistant signatures can be placed alongside. Which ones depends on the plan:

Planavailable signature levels
BasisEd25519, FN-DSA-512
KlassikEd25519, FN-DSA-512, FN-DSA-1024
ProEd25519, FN-DSA-1024, ML-DSA-87
PremiumEd25519, FN-DSA-1024, ML-DSA-87, both in parallel

The parallel variant is deliberately redundant. Should one of the two mathematical families — NTRU lattices for FALCON, module lattices for ML-DSA — turn out weaker than assumed today, the other carries on.

The time anchor. The fingerprint of the signing key is anchored in a Bitcoin block via OpenTimestamps. That makes it possible to show not only that the signature is genuine but also that it already existed at a particular point in time — without anyone having to believe our timestamp.

All of this is verified in the reader's browser, via a WASM module. We supply the data; the arithmetic is done on the visitor's device. If we went offline tomorrow, a review once downloaded would remain verifiable.

24. ML-DSA and FALCON side by side

PropertyFALCON (FN-DSA)ML-DSA
Typedigital signaturedigital signature
Lattice familyNTRUmodule-LWE / module-SIS
RingZq[x]/(xn+1)\mathbb{Z}_q[x]/(x^n+1), q=12289q=12289Zq[x]/(x256+1)\mathbb{Z}_q[x]/(x^{256}+1), q=8380417q=8380417
Core mechanismshort vector via Gaussian samplingchallenge-response with aborts
FFT / NTTfloating-point FFT, security-criticalNTT, arithmetic only
Signature size (highest level)1,280 B4,627 B
Implementationdemanding (floating point)comparatively straightforward
Standardisationintended as FIPS 206 (FN-DSA), not yet finishedFIPS 204, finished

In short: ML-DSA is easier to implement and verify correctly, FALCON delivers considerably more compact signatures. Neither of them sits in the QR code — there is only the Ed25519 envelope. Signature size therefore counts for storage and delivery, robustness for implementation. That is why we offer both.

25. One sentence to take away

ML-DSA turns a short secret vector into an answer to a challengehashed from the review itself — verifiableby anyone holding the public key.\boxed{ \begin{array}{c} \text{ML-DSA turns a short secret vector into an answer to a challenge}\\ \text{hashed from the review itself — verifiable}\\ \text{by anyone holding the public key.} \end{array}}

Whoever holds the secret vector signs in milliseconds. Whoever does not would have to solve a lattice problem in over 14,000 dimensions — even with a quantum computer.

For the reader of a review this simply means: they do not have to believe us. They can do the arithmetic.