Explore the compact side of post-quantum cryptography: how FALCON achieves blazing-fast, bandwidth-friendly signatures for the next generation internet.
1. Introduction: The 1,220-Byte Speed Limit
Previously, we explored CRYSTALS-Dilithium (ML-DSA), the internet’s new primary standard for Post-Quantum Digital Signatures. Dilithium is incredibly fast, highly secure, and relatively easy for developers to implement. It is a fantastic cryptographic broadsword.
But what happens when a broadsword is too big for the job?
Consider DNSSEC (Domain Name System Security Extensions). This is the protocol that prevents hackers from secretly redirecting your web traffic when you type google.com. Because DNS acts as the ultra-fast "phonebook" of the internet, its data packets have strict, ancient size limits. Specifically, if a DNSSEC signature exceeds 1,220 bytes , it triggers massive network fragmentation, causing severe slowdowns and connection drops across the internet.
A standard Dilithium (ML-DSA) signature is about 2,420 bytes. If we force the internet to use Dilithium for DNSSEC, the phonebook of the internet will fracture. We needed a scalpel. We needed a quantum-proof signature that was drastically smaller, without sacrificing security.
Enter FALCON.
Standardized by NIST under the official name FN-DSA (Fast-Fourier Lattice-based Compact Signatures over NTRU), FALCON is Dilithium’s little brother. Today, we will explore how FALCON produces miraculously tiny signatures, why it uses a completely different approach called “Hash-and-Sign,” and why it comes with a dangerous engineering catch.
2. Two Schools of Thought: How to Sign a Document
To understand FALCON, we have to look at the two fundamentally different ways cryptographers build digital signatures using lattices.
1. The “Fiat-Shamir” Approach (Dilithium) As we saw previously, Dilithium relies on a game of zero-knowledge Hide-and-Seek. The signer proves they know the Private Key by navigating a noisy maze and answering a challenge. It is robust and uses simple whole-number math, but the resulting “transcript” of that game (the signature) is very bulky.
2. The “Hash-and-Sign” Approach (FALCON) FALCON uses a much older, more direct approach. Instead of playing a game, the algorithm directly connects the hash of the document to a specific point on the multidimensional lattice grid.
To understand how this works, we need an analogy. Let’s play a game of Multidimensional Darts.
3. The Math of FALCON: The Dartboard Analogy
Imagine our Lattice as an infinitely massive, multidimensional pegboard (a grid of valid dots).
Step 1: Throwing the Dart (Hashing) Alice wants to sign a PDF contract. Her computer runs the PDF through a cryptographic hash function (like SHA-256). The resulting hash translates to a totally random set of coordinates floating in space. Imagine Alice throwing a dart at the pegboard. Because the dart is random, it almost never lands perfectly on one of the valid grid dots. It lands somewhere in the empty space between the dots.
Step 2: Finding the Closest Dot (The Private Key) Alice’s job as the signer is to find the absolute closest valid grid dot to where her dart landed.
- As we read in the earlier articles, finding the closest point in a 1,000-dimensional grid is the Shortest Vector Problem. It is mathematically impossible.
- However, Alice has the Private Key (the “Good Map” with short, perpendicular arrows). Because her map is clean, she can easily and instantly calculate exactly which grid dot is closest to her dart.
- The Signature: Alice draws a line (a vector) from the dart to that closest dot. That short little line is her digital signature.
Step 3: Verifying the Throw (The Public Key) Bob receives the PDF and Alice’s signature (the short line). He needs to verify it using Alice’s Public Key (the “Bad Map” with long, skewed arrows). Bob does two simple checks:
- He hashes the PDF himself (throwing his own dart). He follows Alice’s signature line from the dart to see where it lands.
- He uses his “Bad Map” to verify: Is this landing spot actually a valid dot on the grid? And is the line incredibly short? If both are true, the signature is valid. Only someone with the “Good Map” could have found a valid dot that perfectly close to a random dart throw.
FALCON uses the Hash-and-Sign method. The signature is simply the shortest mathematical path from a hashed document to a valid point on the lattice.
4. Why is FALCON So “Compact”? (NTRU Lattices)
If both Dilithium and FALCON use Lattices, why are FALCON’s signatures less than half the size? (A FALCON signature is roughly 666 bytes , compared to Dilithium’s 2,420 bytes).
It comes down to the specific type of lattice used.
Dilithium uses standard “Module Lattices.” They are incredibly secure but somewhat spacious and bulky.
FALCON uses NTRU Lattices (pronounced en-true). Without diving into heavy algebra, you can think of an NTRU lattice as mathematically “origami.” The equations in an NTRU lattice are designed to fold in on themselves, creating a much tighter, denser mathematical structure.
- The Analogy: If Dilithium is a standard grid of square boxes, FALCON is a honeycomb of perfectly packed hexagons. There is less wasted space. Because the math is denser, the Public Keys and the Signatures required to describe it are significantly smaller.
Furthermore, FALCON utilizes Fast Fourier Transforms (FFT) — a brilliant mathematical algorithm often used in audio engineering to process sound waves. By using FFT, FALCON can navigate this dense honeycomb lattice at blazing-fast speeds.
FALCON uses a specialized mathematical structure called an NTRU lattice, which packs the cryptographic puzzle into a much smaller digital footprint.
5. The Engineering Catch: Why Isn’t FALCON the Only Standard?
If FALCON (FN-DSA) creates signatures that are half the size and just as fast, why didn’t NIST just crown FALCON the undisputed champion and throw Dilithium away?
Because FALCON comes with a massive engineering headache: Floating-Point Mathematics.
When Alice uses her Private Key to find the closest dot on the dartboard, she has to be very careful. If she simply picks the absolute closest dot every single time, a clever hacker can study thousands of her signatures, reverse-engineer her pattern, and figure out her Private Key.
To prevent this, FALCON requires Alice to add a highly specific, bell-shaped curve of randomness (Gaussian sampling) when she picks the dot.
Calculating this specific randomness requires using decimals (floating-point numbers, like 3.14159 ).
- Dilithium only uses integers (whole numbers, like 3 or 4 ).
The Developer Danger: In computer science, processors handle floating-point decimals in varying, unpredictable ways. Some processors calculate decimals a fraction of a millisecond slower than others. Hackers can use a Timing Attack (a type of side-channel attack) to measure exactly how many milliseconds it takes a server to create a FALCON signature. By analyzing those microscopic time differences, they can extract the Private Key without ever breaking the math!
Writing FALCON code that executes in the exact same amount of time, every single time, regardless of the decimal (known as “Constant-Time Implementation”), is brutally difficult for software engineers.
Therefore, NIST decided:
- Use Dilithium (ML-DSA) by default. It uses whole numbers and is much safer and easier for average developers to implement securely.
- Use FALCON (FN-DSA) only when absolutely necessary. It should be reserved for strict bandwidth scenarios (like DNSSEC) and implemented only by highly specialized cryptographic engineers.
Summary: The Developer’s Choice
What’s Next? Entering Month 5
As you now possess a comprehensive, expert-level understanding of Lattice-based cryptography - the true foundation of the post-quantum internet.
But what if, twenty years from now, a genius mathematician discovers a fatal flaw in Lattices?
Inthe upcoming articles , we will step out of the multidimensional grids and look at the backup plans. We will explore the algorithm NIST standardized purely as an insurance policy. We will discover how to build an unbreakable digital signature using nothing but a gigantic family tree of one-way hash functions.
Top comments (0)