Falcon / FN-DSA (FIPS 206, forthcoming)
Falcon is a lattice-based signature scheme being standardized by NIST as FN-DSA (selected; FIPS 206 forthcoming, not yet finalized — follow NIST's official release for the final details). Built on NTRU lattices with a GPV trapdoor and fast-Fourier lattice sampling, among NIST-selected mainstream post-quantum signature schemes, Falcon/FN-DSA offers very compact signatures and public keys; but FN-DSA has not yet been published as a final FIPS standard — at the cost of delicate floating-point sampling.
How it works
Falcon is a hash-and-sign signature over NTRU lattices. The public key defines a lattice; the secret key is a short "trapdoor" basis. To sign, the message is hashed to a point and the signer uses the GPV framework to find a nearby lattice vector — a short signature — that only the trapdoor holder can produce. Verification simply checks the signature is short and maps to the hashed point.
The hard part is sampling that short vector without leaking the trapdoor. Falcon uses fast-Fourier lattice sampling with discrete Gaussian distributions implemented in floating-point arithmetic. This is what makes Falcon so compact, but it is also its principal hazard: the Gaussian sampler must run in constant time and produce bit-identical results across platforms, which is difficult to guarantee with floating point.
Parameter sets
Two sets target NIST categories 1 and 5. Sizes are approximate (in bytes); Falcon signatures are variable-length and compressed.
| Parameter set | Security level | Public key (approx.) | Signature (approx.) |
|---|---|---|---|
| Falcon-512 | Category 1 | 897 | variable, ~650 (≤ 752) |
| Falcon-1024 | Category 5 | 1793 | variable, ~1270 (≤ 1462) |
Falcon signatures are variable-length: a Falcon-512 signature is typically around 650 bytes and never exceeds 752. The separate Falcon-padded-512 / Falcon-padded-1024 variants pad to a fixed 666 / 1280 bytes when constant-size encoding matters. Even at the upper bound these are dramatically smaller than ML-DSA — a Falcon-512 signature is roughly a quarter the size of ML-DSA-44 (~2420 bytes).
Strengths & tradeoffs
- Compact. Very compact among NIST-selected PQC signatures in total public key + signature footprint, ideal where total bytes on the wire are at a premium.
- Fast verification. Verifying is quick and simple.
- Tradeoff — floating point. The Gaussian sampler is a side-channel and portability hazard. Non-constant-time floating-point operations can leak the secret key, and reproducing exact behavior on diverse hardware (and in formally verified code) is hard. This is the main reason ML-DSA is preferred as the general-purpose default.
When to use it
Choose Falcon when signature and public-key size are the dominant constraint — for example, bandwidth-limited links, dense certificate chains, or systems storing huge numbers of signatures — and you can deploy a vetted, constant-time implementation on controlled hardware. For most other purposes, prefer ML-DSA, which avoids the floating-point hazard entirely.
Code example
Using liboqs-python (algorithm name as exposed by the library):
import oqs
alg = "Falcon-512"
message = b"compact certificate signature"
with oqs.Signature(alg) as signer:
public_key = signer.generate_keypair() # ~897 bytes
signature = signer.sign(message) # variable length, ~650 bytes (≤ 752)
print("pk:", len(public_key), "sig:", len(signature))
with oqs.Signature(alg) as verifier:
print("valid:", verifier.verify(message, signature, public_key))Related
FN-DSA (FIPS 206) →
The forthcoming Falcon standard (FIPS 206, not yet published).
ML-DSA →
The recommended default signature scheme.
Lattice cryptography →
NTRU lattices and GPV trapdoors.
Side channels →
Why constant-time sampling matters.
Standards & references
- Falcon project — official specification, reference code, and parameter details.
- NIST PQC project — Falcon is being standardized as FN-DSA (FIPS 206, forthcoming).
- FIPS 204 (ML-DSA) — the lattice signature default to compare Falcon against.
- Resources — full standards register
Falcon FN-DSA FIPS 206 制定中
Falcon 是一种基于格的签名方案，NIST 正以 FN-DSA（已入选；FIPS 206 制定中，尚未最终发布，以 NIST 正式发布为准）名义将其标准化。它建立在 NTRU 格、GPV 陷门与快速傅里叶格采样之上，在 NIST 已选中的主流后量子签名方案中，Falcon/FN-DSA 提供非常紧凑的签名与公钥；但 FN-DSA 尚未发布为最终 FIPS 标准——代价是浮点采样十分微妙。
工作原理
Falcon 是一种基于 NTRU 格的哈希后签名（hash-and-sign）方案。公钥定义一个格，私钥则是一组短“陷门”基。签名时，消息被哈希为一个点，签名者借助 GPV 框架找到一个邻近的格向量——即一段短签名——而只有持有陷门者才能生成。验证只需检查签名足够短且映射到该哈希点。
难点在于采样该短向量而不泄露陷门。Falcon 采用快速傅里叶格采样，离散高斯分布以浮点运算实现。这正是 Falcon 如此紧凑的原因，却也是其首要隐患：高斯采样器必须恒定时间运行，并在各平台产生逐比特一致的结果，而这在浮点环境下难以保证。
参数集
两组参数对应 NIST 等级 1 与 5。尺寸为近似值（字节）；Falcon 签名为变长压缩格式。
| 参数集 | 安全等级 | 公钥（约） | 签名（约） |
|---|---|---|---|
| Falcon-512 | 等级 1 | 897 | 变长，约 650（≤ 752） |
| Falcon-1024 | 等级 5 | 1793 | 变长，约 1270（≤ 1462） |
Falcon 签名为变长，Falcon-512 签名通常约 650 字节，上限 752 字节。需要定长编码时，可用单独的 Falcon-padded-512 / Falcon-padded-1024 变体，它们填充到固定的 666 / 1280 字节。即便取上限，这仍远小于 ML-DSA——Falcon-512 签名约为 ML-DSA-44（约 2420 字节）的四分之一。
优势与取舍
- 紧凑。公钥加签名的总占用在 NIST 已选中的主流后量子签名方案中非常紧凑，适合对线上字节数极为敏感的场景。
- 验证快。验证过程迅速而简单。
- 取舍——浮点。高斯采样器是侧信道与可移植性隐患。非恒定时间的浮点运算可能泄露私钥，且在各类硬件（乃至形式化验证代码）上复现完全一致的行为相当困难。这正是 ML-DSA 被推为通用默认方案的主因。
适用场景
当签名与公钥尺寸是首要约束时选用 Falcon——例如带宽受限链路、密集证书链、或需存储海量签名的系统——并且你能在受控硬件上部署经过审计的恒定时间实现。其余多数情况应优先选用 ML-DSA，它完全规避了浮点隐患。
代码示例
使用 liboqs-python（算法名以库中暴露的为准）：
import oqs
alg = "Falcon-512"
message = b"compact certificate signature"
with oqs.Signature(alg) as signer:
public_key = signer.generate_keypair() # 约 897 字节
signature = signer.sign(message) # 变长 约 650 字节（≤ 752）
print("公钥:", len(public_key), "签名:", len(signature))
with oqs.Signature(alg) as verifier:
print("有效:", verifier.verify(message, signature, public_key))相关页面
FN-DSA FIPS 206 →
Falcon 标准（FIPS 206 制定中，尚未发布）。
ML-DSA →
推荐的默认签名方案。
格密码 →
NTRU 格与 GPV 陷门。
侧信道 →
恒定时间采样为何重要。
标准与参考
- Falcon 项目 — 官方规范、参考代码与参数细节。
- NIST PQC 项目 — Falcon 正以 FN-DSA FIPS 206 名义标准化（尚未最终发布，以 NIST 正式发布为准）。
- FIPS 204 ML-DSA — 用于与 Falcon 对比的格签名默认方案。
- 资源链接 — 完整标准登记册