Signature schemes

FALCON explained mathematically

How a McGesund review is signed with FN-DSA (FALCON) — and why a single changed character breaks the signature.

Last updated: 2026-09-07

1. What this is about

A review on McGesund is not a text field in a database that you have to take on trust. It is signed digitally when it is submitted, and every visitor can recompute that signature later in their own browser.

For some of these signatures we use FALCON — more precisely FN-DSA-512 and FN-DSA-1024. This article explains what happens mathematically.

One thing up front:

FALCON is not encryption. The review text is meant to be read. FALCON does not prove secrecy, it proves origin and integrity.

2. What exactly gets signed

What is signed is not the running text but a compact data object that pins the text down unambiguously:

{
  "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 is our message mm. It ties 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 was submitted as a whole (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) — for a review without a QR the field is omitted,
  6. when it was signed (iat).

A single changed character in the review text breaks this chain. That is exactly the purpose — and since rh the same holds for a heart moved afterwards or an altered geo status.

3. The underlying problem

A reader arriving at a company profile faces two questions:

  1. Does this review really come from the McGesund system?
  2. Was it altered afterwards?

That is what the key pair is for:

  • a private key — stays inside the signing service
  • a public key — anyone may have it

Signing uses the private key, verifying the public one. And it happens on the reader's device, not on our server.

4. Why FALCON?

Many of today's signature schemes rest on problems that are hard for classical computers but could become considerably easier for sufficiently large quantum computers.

For a review that matters more than for a fleeting message: a review should still be verifiable in five or ten years. Whoever signs today signs for the entire lifetime of the entry.

FALCON therefore rests on lattice cryptography:

You build a lattice that is easy to describe mathematically and in which one particular search task is extremely hard.

5. What is a mathematical lattice?

Two vectors:

v1=(2,0),v2=(1,2).v_1=(2,0), \qquad v_2=(1,2).

All integer combinations

a v1+b v2,a,b∈Za\,v_1+b\,v_2, \qquad a,b\in\mathbb{Z}

form a lattice of points. For example:

2v1+3v2=(4,0)+(3,6)=(7,6).2v_1+3v_2=(4,0)+(3,6)=(7,6).
v₁ = (2,0)v₂ = (1,2)(7,6)0
Two vectors span a lattice. Every point is an integer combination of the two — the marked one arises from two times v₁ and three times v₂.

The decisive part:

The lattice itself is easy to describe. Finding certain properties inside it is very hard.

6. The secret is short vectors

The classic hard task reads:

min⁡v∈L,  v≠0∥v∥.\min_{v\in L,\;v\neq0}\|v\|.

That is the shortest vector problem. In two dimensions you can simply try everything. FALCON works in dimension 512 or 1024 — there it is hopeless.

long basisnearly parallelshortest vector
The same lattice, two descriptions. The grey vectors generate it as well, but they are long and nearly parallel — a bad basis. The short vector is the thing that is hard to find.

FALCON, however, does not need the shortest vector as such but something related: finding a lattice point close to a given target point. That, too, is hard without the right additional information.

target point from the reviewnearby lattice pointfar away
The target point from the review (hollow circle) is not on the lattice. What is wanted is a lattice point close beside it — the dashed path to a distant point also satisfies the first condition, but it is not a short one.

7. Polynomials instead of numbers

FALCON uses an NTRU lattice and computes with polynomials. So instead of single numbers, with lists of coefficients:

f=(1,0,1,0,0,1)⟷f(x)=1+x2+x5.f=(1,0,1,0,0,1) \quad\longleftrightarrow\quad f(x)=1+x^2+x^5.

The arithmetic happens in the ring

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

That means:

  • Zq\mathbb{Z}_q: arithmetic modulo qq. With q=7q=7, for instance, 10≡310\equiv3, since 10−7=310-7=3.
  • xn=−1x^n=-1: keeps the polynomials at a fixed length.

FALCON specifically uses:

q=12289,n=512  or  1024.q=12289, \qquad n=512 \;\text{or}\; 1024.

8. The central trick

The private key consists of four small polynomials

f,  g,  F,  Gf,\;g,\;F,\;G

satisfying the NTRU equation

fG−gF=q.fG-gF=q.

Together these four form a secret, well-behaved lattice basis — a description of the lattice made of short vectors.

The public key is essentially a single polynomial:

h=gf(modq).h=\frac{g}{f}\pmod q.

From hh you get the same lattice, but in an unwieldy basis of long vectors:

L={(s1,s2)  :  s1+s2 h≡0(modq)}.L=\{(s_1,s_2)\;:\;s_1+s_2\,h\equiv0 \pmod q\}.

That is the whole core of FALCON. Both bases describe the same lattice. It is just that one of them is usable for computing and the other is not.

You can picture it like a street map: public is the complete map. Secret is the knowledge of the shortcuts.

9. The review becomes a point

Before signing, the payload object goes through a hash function. FALCON uses hash-to-point for this: the message does not become a numeric value but directly a point in the ring.

In addition, the signing service draws a random salt rr (320 bits) and hashes it along:

c=HashToPoint(r ∥ m).c=\mathrm{HashToPoint}(r \,\|\, m).

The salt is not decoration. Without it the same review would always produce the same signature, and from many signatures the secret basis could be reconstructed. It therefore travels along inside the signature.

10. What a valid signature is

What is sought is a pair

(s1,s2)(s_1,s_2)

with two properties:

s1+s2 h≡c(modq)and∥(s1,s2)∥  small.s_1+s_2\,h\equiv c \pmod q \qquad\text{and}\qquad \|(s_1,s_2)\|\;\text{small}.

The first condition alone is trivial to satisfy — set s2=0s_2=0 and s1=cs_1=c. The second condition is what makes the task hard.

The shortness is the signature.\boxed{\text{The shortness is the signature.}}

11. A fully worked miniature example

We shrink everything to toy size: polynomials with only one coefficient, so ordinary numbers, and

q=97.q=97.

The secret key. Two small numbers:

f=3,g=5.f=3, \qquad g=5.

The public key. We have 3−1≡65(mod97)3^{-1}\equiv65 \pmod{97}, since 3⋅65=195=2⋅97+13\cdot65=195=2\cdot97+1. So:

h=g⋅f−1=5⋅65=325≡34(mod97).h=g\cdot f^{-1}=5\cdot65=325\equiv \boxed{34} \pmod{97}.

The lattice. L={(s1,s2):s1+34 s2≡0(mod97)}L=\{(s_1,s_2): s_1+34\,s_2\equiv0 \pmod{97}\}.

The public basis follows directly from hh:

(97,0)and(−34,1).(97,0) \quad\text{and}\quad (-34,1).

Both lie in LL — and both are long.

The secret basis is known only to the signing service:

(−g,f)=(−5,3)and(−G,F)=(−9,−14),(-g,f)=(-5,3) \quad\text{and}\quad (-G,F)=(-9,-14),

since −5+34⋅3=97≡0-5+34\cdot3=97\equiv0 and −9+34⋅(−14)=−485=−5⋅97≡0-9+34\cdot(-14)=-485=-5\cdot97\equiv0. The determinant is

(−5)(−14)−(3)(−9)=70+27=97=q,(-5)(-14)-(3)(-9)=70+27=97=q,

so the NTRU equation works out. Both vectors are short.

Step 1: Hash the review

Suppose the review's payload object yields

c=71.c=71.

Step 2: A first, poor solution

(s1,s2)=(71,0)(s_1,s_2)=(71,0)

satisfies 71+34⋅0=71≡c71+34\cdot0=71\equiv c. But its length is 7171 — far too long.

Step 3: Shortening with the secret basis

The signing service expresses the target point in its short basis:

(71,0)=a (−5,3)+b (−9,−14).(71,0)=a\,(-5,3)+b\,(-9,-14).

This leads to a≈−10.25a\approx-10.25 and b≈−2.20b\approx-2.20. Rounded to a=−10a=-10, b=−2b=-2, we get the lattice point

−10 (−5,3)−2 (−9,−14)=(50,−30)+(18,28)=(68,−2).-10\,(-5,3)-2\,(-9,-14)=(50,-30)+(18,28)=(68,-2).

Check: 68+34⋅(−2)=68−68=068+34\cdot(-2)=68-68=0, so it really is in LL. Subtracting:

(71,0)−(68,−2)=(3,2)(71,0)-(68,-2)=\boxed{(3,2)}

Length:

∥(3,2)∥=9+4=13≈3.61.\|(3,2)\|=\sqrt{9+4}=\sqrt{13}\approx3.61.

That is the signature.

Step 4: The same procedure with the public basis

Anyone who knows only h=34h=34 has the basis {(97,0),(−34,1)}\{(97,0),(-34,1)\}. The same rounding computation gives the lattice point (97,0)(97,0) there and therefore

(71,0)−(97,0)=(−26,0),∥(−26,0)∥=26.(71,0)-(97,0)=(-26,0), \qquad \|(-26,0)\|=26.

Also a valid solution of the equation — but seven times longer. If the acceptance bound is set below 26, it is worthless.

Same algorithm, same lattice, same target point.Only the basis differs — and with it the result.\boxed{ \begin{array}{c} \text{Same algorithm, same lattice, same target point.}\\ \text{Only the basis differs — and with it the result.} \end{array}}

That is FALCON's trapdoor in one line.

Step 5: The browser verifies

The browser receives the review, the salt and s2=2s_2=2. It recomputes the hash, obtains c=71c=71, reconstructs

s1=c−s2 h=71−68=3,s_1=c-s_2\,h=71-68=3,

and checks the length:

∥(3,2)∥=13  ≤  β⟹Signature valid\|(3,2)\|=\sqrt{13}\;\leq\;\beta \quad\Longrightarrow\quad \boxed{\text{Signature valid}}

Step 6: Someone changes the review text

If the text is altered afterwards, the content hash changes and with it the point, say

c′=40.c'=40.

The old signature stays (3,2)(3,2), but

3+34⋅2=71≠40⟹Signature invalid3+34\cdot2=71\neq40 \quad\Longrightarrow\quad \boxed{\text{Signature invalid}}

We can delete a review. We cannot alter it without it showing.

An honest note about the example

In two dimensions an attacker can simply try out short solutions — for c′=40c'=40, for instance, (6,1)(6,1). The example is not secure; it only shows the mechanism. With FALCON-1024 the vector has 2048 coefficients, and there trying things out leads nowhere.

12. Why not simply round?

The procedure from step 3 is called Babai rounding. For a textbook example it is enough — for a real signature scheme it is not.

The reason: rounded signatures are not evenly distributed. Their shape depends on the geometry of the secret basis. From enough signatures that geometry could be reconstructed — and with it the private key. Earlier lattice-based signature schemes failed on exactly this.

FALCON therefore draws its short vectors from a discrete Gaussian distribution over the lattice:

P(x)∝e−∥x−c∥2/(2σ2).P(x)\propto e^{-\|x-c\|^2/(2\sigma^2)}.

Values near the target point are more likely, but which one is chosen exactly is random. The result is a distribution that reveals nothing about the basis used — mathematically: it is indistinguishable from a distribution that depends only on the lattice itself.

This sampler is the most demanding part of FALCON. It runs recursively over a tree structure and works with floating-point numbers — which makes the implementation delicate and is the main reason why FALCON is harder to implement correctly than ML-DSA.

13. What is actually transmitted

The signature consists of

σ=(r,  s2).\sigma=(r,\;s_2).

Only s2s_2 — not the pair. The verifier computes s1s_1 itself:

s1=c−s2 h(modq).s_1=c-s_2\,h \pmod q.

Because the coefficients of s2s_2 are small and scatter around zero, they compress very well. That is the reason for FALCON's strikingly compact signatures:

public keysignature
FALCON-512897 B~666 B
FALCON-10241,793 B~1,280 B

For comparison: ML-DSA-87 needs 4,627 bytes. At McGesund, however, none of these signatures sits in the QR code itself — the sticker carries only the Ed25519 envelope; the PQ stamps are attached to the record and are loaded when verifying. So size does not decide printability here but storage and transfer: a FALCON stamp is a good quarter of the size of an ML-DSA stamp.

14. Why FALCON verifies quickly

Naive polynomial multiplication costs

O(n2).O(n^2).

With the fast Fourier transform this drops to roughly

O(nlog⁡n).O(n\log n).

At n=1024n=1024 that is the difference between a million and about ten thousand operations. That is why verification runs in a visitor's browser in milliseconds — and why the F is in the name:

FAst Fourier Lattice-based COmpact signatures over NTRU.

15. The process in one picture

SIGNING SERVICE (MCGESUND)VISITOR'S BROWSERprivate key (f, g, F, G — short basis)payload m = {company, review, h, rh, iat}salt r + HashToPoint(r ‖ m) = cGaussian sampling: short vector (s₁, s₂)signature σ = (r, s₂) + kidreview + σ + public key hrecompute c, s₁ = c − s₂·h‖(s₁, s₂)‖ ≤ β ?validinvalid
From the payload to the tick in the browser. Everything above the dividing line happens once on submission, everything below it happens again for every visitor — on their device, with the public key.

16. Why an attacker fails

They know hh and therefore the entire lattice. They also know the target point cc as soon as the review is public. What they lack is the short basis.

To forge a review they would have to find a short vector for a cc of their own choosing — from the public description alone. That is the task step 4 of the example illustrated: without the good vectors the very same computation ends up at a far too long solution.

In dimension 1024 the best known methods — classical and quantum-based alike — are nowhere near it.

Signing: fastVerifying: fastForging: hard\boxed{\text{Signing: fast}\quad \text{Verifying: fast}\quad \text{Forging: hard}}

17. What McGesund does with it in practice

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

The post-quantum stamps. Alongside it sit one or two quantum-resistant signatures. 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. FALCON rests on NTRU lattices, ML-DSA on module lattices. Should one of the two families 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 establishes 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 computed in the reader's browser, via a WASM module. We supply the data; the check runs on the visitor's device. If we went offline tomorrow, a review once loaded would remain verifiable.

On the names: FALCON is currently being standardised as FN-DSA; the draft is intended as FIPS 206 but is not finished yet. That is why the levels are called FN-DSA-512 and FN-DSA-1024 in the McGesund code, even though people continue to say FALCON in conversation.

18. The most important intuition

The public key is the complete description of a maze. Anyone may look at it.

The signature is the proof: "For exactly this review I found a very short path."

The private key is the knowledge of the shortcuts.

The reader does not need to know the shortcuts. They only measure whether the path presented really is short and really belongs to this review. Both can be done without us.

FALCON turns a review into a point in a latticeand the signature into a short path to it.\boxed{ \begin{array}{c} \text{FALCON turns a review into a point in a lattice}\\ \text{and the signature into a short path to it.} \end{array}}

Change the text and you move the point — and the old path leads nowhere.