← Back to Blog Cryptography

FN-DSA (Falcon): The Most Compact Post-Quantum Signatures

14 min read

What is FN-DSA?

Every time you install an app on your phone, your device checks a digital signature to make sure the software actually came from the developer and was not tampered with by a hacker. Every time your browser connects to a website over HTTPS, it verifies a chain of digital signatures to confirm the site is who it claims to be. Digital signatures are the invisible trust infrastructure behind almost everything you do online.

The digital signature algorithms in widespread use today (RSA, ECDSA) will be broken by quantum computers running Shor's algorithm. NIST has been standardizing replacement algorithms that are resistant to quantum attacks. Their primary recommendation is ML-DSA (FIPS 204), a lattice-based algorithm. But NIST also selected a second lattice-based signature algorithm with a unique advantage: FN-DSA, which produces the smallest signatures of any post-quantum scheme.

FN-DSA stands for FFT (Fast Fourier Transform) over NTRU-Lattice-Based Digital Signature Algorithm. You may also see it referred to by its competition name, Falcon, which is what it was called throughout NIST's eight-year evaluation process. NIST is standardizing it as FIPS 206 (draft), currently in draft form.

The key fact about FN-DSA is this: at NIST Level 1 security, an FN-DSA signature is about 666 bytes. An ML-DSA signature at a comparable security level is 2,420 bytes. That is roughly 3.6 times larger. At higher security levels, the gap persists. FN-DSA-1024 at NIST Level 5 produces signatures of about 1,280 bytes, which is still smaller than ML-DSA-44 at Level 2. For applications where every byte of signature data costs real money or real latency, this difference is significant.

Why Signature Size Matters

You might wonder why anyone would care about the difference between a 666-byte signature and a 2,420-byte signature. On a modern computer with gigabytes of storage and high-speed internet, an extra 1,754 bytes per signature seems trivial. But consider scale.

A busy web server might handle 10,000 TLS connections per second. Each TLS handshake involves multiple signatures in the certificate chain. If you add 1,754 extra bytes per signature, and there are 2-3 signatures per handshake, that is an additional 35-53 megabytes of data per second, just from signature overhead. Over a day, that adds up to 3-4.5 terabytes of additional network traffic.

For embedded devices and IoT sensors with limited bandwidth (a smart meter on a cellular connection, a satellite uplink, a Bluetooth medical device), every byte matters even more. These devices may have connection speeds measured in kilobits per second. A 17 KB SLH-DSA signature could take noticeable time to transmit, while a 666-byte FN-DSA signature fits comfortably in a single packet.

Blockchain and distributed ledger systems store every transaction permanently. Smaller signatures mean less chain bloat, lower storage costs, and faster synchronization for new nodes joining the network.

FN-DSA was selected by NIST specifically because of this size advantage. NIST's Round 3 status report (NIST IR 8413) explicitly notes that Falcon (now FN-DSA) "has the most compact signatures and public keys" among the post-quantum signature candidates.

How FN-DSA Works: NTRU Lattices Explained Simply

Both FN-DSA and ML-DSA are "lattice-based" algorithms, but they use different types of lattices. Understanding the difference helps explain why FN-DSA produces smaller signatures.

A lattice is a regular, repeating grid of points in space. In two dimensions, think of graph paper: an infinite grid of evenly spaced dots. In three dimensions, think of the atoms in a crystal. Now imagine extending that grid into 512 or 1,024 dimensions. You cannot visualize it, but the math works the same way. The grid has a regular structure, and there are hard problems associated with finding specific points in it.

ML-DSA uses "module lattices" and the Module Learning With Errors (MLWE) problem. The idea is that you take a lattice, add small random errors to it, and the resulting noisy data is hard to distinguish from truly random data. Signing involves proving you know the secret structure behind the noise, without revealing it.

FN-DSA uses "NTRU lattices," which have a different algebraic structure. NTRU stands for "N-th degree Truncated polynomial Ring Units." The core idea comes from a 1996 proposal by Hoffstein, Pipher, and Silverman. In an NTRU lattice, the signer holds a "short" secret basis, a compact way of describing the lattice structure that allows efficient navigation. The public key is derived from this secret basis, but computing the short basis from the public key alone is computationally intractable.

The signing process uses a technique called trapdoor sampling. When you want to sign a message, you hash the message to get a target point, then use your secret short basis to find a short lattice vector near that target. "Short" is the key word here; anyone can find some lattice vector near the target, but finding a short one requires knowledge of the secret basis. The signature is this short vector.

The "FFT" in FN-DSA's name refers to the Fast Fourier Transform, which is used to make the trapdoor sampling process efficient. Specifically, FN-DSA uses a sampler over the Fourier domain of the NTRU lattice, which allows it to produce signatures that are both short (compact) and correctly distributed (secure). This mathematical trick is what gives FN-DSA its size advantage over ML-DSA.

Verification is straightforward: given the public key, the message, and the signature (a short vector), anyone can check that the vector is indeed short and corresponds to the message hash. This check is fast and does not require the secret key.

The Size Comparison in Detail

Algorithm	NIST Level	Public Key	Signature	Combined (PK + Sig)
FN-DSA-512	Level 1	897 bytes	~666 bytes	~1,563 bytes
FN-DSA-1024	Level 5	1,793 bytes	~1,280 bytes	~3,073 bytes
ML-DSA-44	Level 2	1,312 bytes	2,420 bytes	3,732 bytes
ML-DSA-65	Level 3	1,952 bytes	3,309 bytes	5,261 bytes
ML-DSA-87	Level 5	2,592 bytes	4,627 bytes	7,219 bytes
SLH-DSA-128f	Level 1	32 bytes	17,088 bytes	17,120 bytes
RSA-2048 (quantum-broken)	N/A	256 bytes	256 bytes	512 bytes

The "Combined" column matters because in many protocols (TLS, certificate chains, signed firmware), both the public key and signature are transmitted together. FN-DSA-1024 at NIST Level 5 has a combined size of about 3 KB, while ML-DSA-87 at the same security level requires over 7 KB. That is a 2.3x difference that compounds across every connection and every signature verification.

Note on RSA-2048: RSA produces the smallest combined size in this table, but it provides zero protection against quantum computers. Shor's algorithm breaks RSA entirely. RSA is included here only as a size reference for the pre-quantum era.

The Tradeoff: Implementation Complexity

FN-DSA's small signatures come with a cost, and that cost is implementation difficulty. This is the main reason NIST recommends ML-DSA as the default and positions FN-DSA as a secondary option for specific use cases.

The trapdoor sampling process at the heart of FN-DSA signing requires high-precision floating-point arithmetic. The sampler must generate random values from a specific probability distribution (a discrete Gaussian over the NTRU lattice), and getting this distribution wrong, even slightly, can leak information about the secret key through statistical analysis of the produced signatures. This kind of vulnerability is called a side-channel attack.

Think of it this way: imagine you are a locksmith who can open any lock, but every time you open one, nearby observers can hear subtle differences in the clicking sounds. If an attacker records enough of these sounds, they might be able to reconstruct how your master key is shaped. FN-DSA has a similar problem with floating-point arithmetic. If the computations are not done with exact precision and constant timing, the slight variations in computation can reveal information about the secret key.

Implementations must either use constant-time floating-point operations (which not all hardware supports consistently) or emulate floating-point using integer arithmetic (which is slower but more predictable). Both approaches require careful engineering and thorough testing.

ML-DSA, by contrast, uses only simple integer arithmetic. Its signing process is based on rejection sampling: generate a candidate signature, check if it meets certain criteria, and if not, try again. This is much simpler to implement securely. There are fewer opportunities for subtle bugs that leak secret information.

This is a real, practical concern. NIST's Round 3 report specifically flags FN-DSA's implementation complexity as a factor in their decision to make ML-DSA the primary recommendation and FN-DSA the secondary one.

FN-DSA vs ML-DSA: Complete Comparison

Criteria	ML-DSA (FIPS 204)	FN-DSA (FIPS 206 (draft))
NIST role	Primary general-purpose recommendation	Secondary, for bandwidth-constrained scenarios
Standard status	FIPS 204 (final, August 2024)	FIPS 206 (draft)
Signature size (Level 1)	2,420 bytes	~666 bytes
Public key size (Level 1)	1,312 bytes	897 bytes
Security basis	Module-LWE lattices	NTRU lattices
Signing arithmetic	Simple integer math	High-precision floating-point or integer emulation
Implementation difficulty	Moderate	High (side-channel risks in sampler)
Best for	General purpose, high volume	TLS, IoT, blockchain, constrained bandwidth

NIST's guidance: Use ML-DSA as the default signature algorithm. Use FN-DSA when signature size is a critical constraint. The two algorithms are complementary, not competing. They are based on different lattice types (Module-LWE vs NTRU), providing genuine algorithm diversity even within the lattice family.

The NTRU Story: Older Than You Think

The NTRU lattice problem that FN-DSA relies on has an interesting history. It was proposed in 1996 by mathematicians Jeffrey Hoffstein, Jill Pipher, and Joseph Silverman at Brown University, making it one of the oldest lattice-based cryptographic constructions. NTRU was originally designed for encryption (NTRUEncrypt), not signatures, and it predates the modern wave of lattice cryptography that began with Regev's Learning With Errors (LWE) paper in 2005.

The NTRU problem has been studied by mathematicians and cryptographers for nearly 30 years. Despite extensive analysis, no efficient classical or quantum algorithm has been found to solve it. This is a strong track record, comparable to the history of code-based cryptography (McEliece, 1978) and significantly longer than the history of LWE-based cryptography.

NTRU and Module-LWE (the problem underlying ML-DSA) are both lattice problems, but they have different algebraic structures. NTRU lattices have a specific ring structure that enables compact keys and signatures, while Module-LWE uses a more general module structure that is slightly easier to analyze theoretically. This structural difference is what makes FN-DSA and ML-DSA genuinely independent from a security perspective. A mathematical attack that exploits the module structure of MLWE would not automatically apply to NTRU's ring structure, and vice versa.

Real-World Impact: How Much Bandwidth Does FN-DSA Save?

To make the size difference concrete, consider a typical TLS certificate chain with three certificates (root CA, intermediate CA, end-entity). Each certificate contains a signature from the issuing CA. In the post-quantum world, these signatures will be much larger than today's RSA or ECDSA signatures. Here is what the signature-only overhead looks like for a 3-certificate chain:

RSA-2048 (quantum-broken): 3 x 256 bytes = 768 bytes total
FN-DSA-512: 3 x ~666 bytes = ~2,000 bytes total
ML-DSA-44: 3 x 2,420 bytes = 7,260 bytes total
SLH-DSA-128f: 3 x 17,088 bytes = 51,264 bytes total

A web server handling 10,000 TLS handshakes per second would transmit an additional 50 MB/s of signature data with ML-DSA compared to FN-DSA. Over a day, that is an additional 4.3 TB of network traffic. For large content delivery networks handling millions of connections, the aggregate savings from smaller signatures translate directly into lower infrastructure costs and faster page load times for users.

For IoT deployments with thousands of constrained devices reporting sensor data over cellular connections, the per-message overhead of ML-DSA signatures could exceed the payload data itself. FN-DSA keeps the authentication overhead proportional to the actual data being transmitted.

When to Choose FN-DSA

FN-DSA is the right choice in specific scenarios where signature compactness is a hard requirement:

TLS and certificate chains. Web servers transmitting certificate chains on every connection benefit from smaller signatures. A 3-certificate chain with FN-DSA saves roughly 5-10 KB per handshake compared to ML-DSA.
IoT and embedded devices. Sensors, smart meters, and medical devices with limited bandwidth (cellular, Bluetooth, satellite) need the smallest possible signatures to keep communication overhead low.
Blockchain and distributed systems. Every transaction is stored permanently. Smaller signatures reduce chain bloat and speed up synchronization.
Protocol compatibility. Some existing protocols have hard limits on field sizes that were designed around RSA or ECDSA signatures. FN-DSA's compact signatures are more likely to fit within those limits without protocol modifications.
Algorithm diversity within lattice family. Even if your primary algorithm is ML-DSA, deploying FN-DSA alongside it provides diversity. ML-DSA and FN-DSA rely on different lattice problems (MLWE vs NTRU). A breakthrough against one does not automatically break the other.

Standardization Status

As of early 2026, FN-DSA is specified in a FIPS 206 (draft) Initial Public Draft (IPD) published by NIST. The final standard is expected around 2027. The Falcon algorithm that FN-DSA is based on has been publicly analyzed since its submission to NIST in 2017. It survived all three rounds of NIST's evaluation process and was selected alongside CRYSTALS-Dilithium (now ML-DSA) and SPHINCS+ (now SLH-DSA) in July 2022.

The standardization process is formalizing exact parameter encodings, compliance requirements, and test vectors. The core algorithm, the underlying mathematics, the parameter sets, and the security proofs are well-established and not expected to change. The primary open questions are about encoding formats and implementation guidance, not about the algorithm's security.

Organizations with near-term needs for compact post-quantum signatures can begin deployment now, with the understanding that minor encoding adjustments may be needed when FIPS 206 (draft) is finalized. The security properties of the algorithm are already settled by nearly a decade of public analysis.

How QNSQY Uses FN-DSA

FN-DSA is available in the QNSQY Business tier. It follows the same hybrid pattern used for all post-quantum signatures in QNSQY: the FN-DSA signature is combined with an Ed25519 classical signature, so that an attacker must break both to forge a signature. This hybrid approach provides defense-in-depth during the transition to post-quantum cryptography.

Generate an FN-DSA key pair:

qnsqy keygen-sign -o mykey -n "My Signing Key" --algorithm fn-dsa512

Sign a file:

qnsqy sign -i document.pdf -k mykey

Verify a signature:

qnsqy verify -i document.pdf -k mykey.pub

Both FN-DSA-512 (NIST Level 1) and FN-DSA-1024 (NIST Level 5) parameter sets are supported. QNSQY's implementation uses constant-time operations throughout the signing path to prevent the side-channel leakage discussed above.

Choosing Between the Three PQC Signature Standards

With three post-quantum signature standards (ML-DSA, SLH-DSA, and FN-DSA), the natural question is: which one should I use? The answer depends on your specific requirements:

Default choice: ML-DSA (FIPS 204). Fast, reasonably compact, simple to implement, finalized standard. This is what NIST recommends for general-purpose use.
Bandwidth-critical: FN-DSA (FIPS 206 (draft) draft). If signature size is your binding constraint (TLS, IoT, blockchain), FN-DSA gives you 3.6x smaller signatures than ML-DSA.
Maximum conservatism: SLH-DSA (FIPS 205). If you need the strongest possible security guarantee and signature size is not a concern, SLH-DSA's hash-only security basis provides the ultimate safety net.

Many organizations will deploy more than one. ML-DSA for everyday operations, SLH-DSA or FN-DSA for specific applications where their particular strengths matter. The algorithms are complementary, not competing.

Sources

Algorithm Diversity

QNSQY Business includes FN-DSA alongside ML-DSA for defense in depth.

Try QNSQY

Originally published at quantumsequrity.com/blog/fn-dsa-falcon-explained.