FALCON 签名算法：NTRU 格密码的代表作
概述
FALCON（Fast Fourier Lattice Contracts）是由 Jean-Christophe Deneuville、Paulo Mouris、Thomas Prest 等学者设计，基于 NTRU 格结构的一个高效后量子数字签名方案。该方案由法国 INRIA 和法国国家信息安全局（ANSSI）联合开发，在 NIST 后量子密码标准化项目的第三轮竞赛中入围最终名单，并于 2024 年 8 月 13 日正式发布为 FIPS 205 标准。
FALCON 的核心创新在于将三角化 NTRU 格（Triangular NTRU Lattice）与快速傅里叶变换（FFT）结合，实现了签名尺寸的极致压缩。其安全声称与关键性能数据如下表所示：
| 安全级别 | 密钥尺寸 | 签名尺寸 | 加密操作次数（估算） |
|---|---|---|---|
| Category 1 | 1664 字节 | 855 字节 | 约 2×10⁶ 次浮点运算 |
| Category 3 | 3328 字节 | 1793 字节 | 约 8×10⁶ 次浮点运算 |
| Category 5 | 6656 字节 | 3467 字节 | 约 3×10⁷ 次浮点运算 |
性能数据来源说明：上述数据基于参考实现 FALCON v1.2（GitHub: https://falcon-sign.info/falcon/）在 Intel Core i7-8550U @ 1.8GHz 处理器上的基准测试结果。实际生产环境的性能可能因硬件架构、优化程度和随机数生成质量而异。与 Dilithium（FIPS 204）相比，FALCON 的签名尺寸更小，但密钥生成和签名操作的计算开销更高。这种设计权衡使其特别适合带宽受限但计算资源充足的应用场景，如区块链签名、物联网设备认证等。
数学基础
三角化 NTRU 格
FALCON 的安全性基于三角化 NTRU 格（Triangular NTRU Lattice）上的最短向量问题（SVP）。与传统的 lattice-based cryptography 使用的理想格（Ideal Lattice）不同，三角化 NTRU 格具有特殊的代数结构，允许使用 FFT 进行高效的算术运算。
#### 多项式环结构
FALCON 在多项式环 $R_q = \mathbb{Z}_q[x] / (x^n + 1)$ 上操作，其中：
- $n$ 是 2 的幂次（通常取 512 或 1024）
- $q$ 是满足特定条件的素数（FALCON-512 取 $q = 12289$，FALCON-1024 取 $q = 40961$）
- $x^n + 1$ 在 $\mathbb{Z}_q[x]$ 上可分解为 $n$ 个一次因子的乘积
#### 高斯采样与短向量
FALCON 的核心操作是在三角化 NTRU 格上采样服从离散高斯分布的短向量。给定一个格 $\Lambda$ 和参数 $s$，离散高斯分布 $D_{\Lambda, s}$ 定义为：
$$D_{\Lambda, s}(\mathbf{x}) = \frac{\rho_s(\mathbf{x})}{\rho_s(\Lambda)}, \quad \rho_s(\mathbf{x}) = e^{-\pi \|\mathbf{x}\|^2 / s^2}$$
其中 $s$ 是高斯宽度参数，控制采样向量的长度分布。FALCON 要求采样得到的向量范数满足特定界限，以确保签名的安全性。
CVP 求解与签名生成
FALCON 签名方案依赖于最近向量问题（Closest Vector Problem, CVP）的高效求解。给定格 $\Lambda$ 和目标向量 $\mathbf{t}$，CVP 要求找到格点 $\mathbf{v} \in \Lambda$ 使得 $\|\mathbf{v} - \mathbf{t}\|$ 最小。
FALCON 使用三角分解（Triangular Decomposition）将 CVP 问题转化为一系列一维子问题，通过 Babai 最近平面算法（Babai's Nearest Plane Algorithm）的改进版本高效求解。该算法的关键步骤是：
- 对格基矩阵进行 LLL 约减或高斯消元，得到三角基
- 逐维度投影目标向量到子空间
- 在每个维度上进行最近格点舍入
算法结构
密钥生成（Key Generation）
FALCON 的密钥生成过程如下：
KeyGen():
1. 生成随机多项式 f, g ∈ R_q，满足特定范式约束
2. 计算 h = g / f mod q（在多项式环中求逆）
3. 私钥 sk = (f, g)，公钥 pk = h其中 $(f, g)$ 必须满足以下条件：
- $\|f\|^2$ 和 $\|g\|^2$ 均小于某个上界（由安全级别决定）
- $f$ 在 $R_q$ 中可逆（即 $\gcd(f, x^n + 1) = 1$）
签名（Signing）
签名是 FALCON 的核心操作，涉及 CVP 求解和高斯采样：
Sign(sk, μ):
1. 计算消息哈希：e = Hash(μ) ∈ R_q
2. 通过 CVP 求解找到短向量 s ∈ R_q，使得 ||s|| < β
3. 计算签名 σ = s + e·f mod q
4. 返回签名 σ签名过程的关键在于第 2 步的 CVP 求解。FALCON 使用二分树结构（Binary Tree Structure）来组织签名过程中的计算，将高维 CVP 问题递归分解为低维子问题。这种结构使得：
- 签名操作可以并行化
- 内存访问模式具有良好的局部性
- 签名尺寸的方差较小（有利于常数时间实现）
验证（Verification）
签名验证是一个确定性过程：
Verify(pk, μ, σ):
1. 计算 e = Hash(μ)
2. 计算 r = σ - e·h mod q
3. 检查 ||r|| < β 是否成立
4. 如果成立返回 1，否则返回 0验证过程只需要一次多项式乘法和范数计算，时间复杂度为 $O(n \log n)$。
参数体系与安全分析
三个安全级别
FALCON 定义了三个安全级别，对应 NIST PQC 标准的安全类别：
| FALCON 级别 | NIST 类别 | 格维度 $n$ | 模数 $q$ | 签名尺寸 | 密钥尺寸 |
|---|---|---|---|---|---|
| FALCON-512 | Category 1 | 512 | 12289 | 855 字节 | 1664 字节 |
| FALCON-1024 | Category 3 | 1024 | 40961 | 1793 字节 | 3328 字节 |
| FALCON-2048 | Category 5 | 2048 | 163841 | 3467 字节 | 6656 字节 |
- 格基选择：三角化 NTRU 格的参数确保了对称格约减攻击（如 BKZ）的复杂度足够高
- 高斯宽度：签名过程的采样参数保证了攻击者无法从签名中恢复私钥
- 哈希函数：使用 SHAKE128/SHAKE256 作为消息哈希，确保安全级别不被哈希碰撞打破
安全性证明
FALCON 的安全性基于以下困难问题：
- NTRU 格上的 SVP/CVP：即使拥有量子计算机，求解这些问题的复杂度仍然是指数级的
- 模块学习误差（MLWE）：当 $n$ 足够大时，从公钥恢复私钥在计算上不可行
工程实现要点
浮点运算与精度
FALCON 的核心算法依赖浮点运算（特别是 FFT 和浮点高斯采样），这对实现提出了特殊要求：
- 精度要求：CVP 求解过程中的浮点误差必须严格控制在 2⁻⁵³（double precision）以内，否则可能导致签名失败或信息泄露
- 常数时间实现：为了防御侧信道攻击，所有分支和内存访问必须与私钥无关
- 舍入模式：必须使用 IEEE 754 默认的"向最近偶数舍入"（round to nearest, ties to even）
优化策略
在实际工程中，FALCON 有以下几种常见的优化策略：
FFT 优化：
- 使用 Cooley-Tukey FFT 算法将多项式乘法从 $O(n^2)$ 优化到 $O(n \log n)$
- 利用 NTRU 多项式的特殊结构（所有系数在 $\{-1, 0, 1\}$ 中）减少乘法次数
- 使用 SIMD 指令（AVX2/AVX-512）并行处理多个系数
- 将签名操作分解为二叉树上的节点计算
- 允许在线程间分配不同的子树
- 减小中间结果的存储需求
- 使用截断表示法（Truncated Representation）进一步压缩签名尺寸
- FALCON 的签名可以额外压缩约 10-15% 而不影响安全性
已知攻击与防御
| 攻击类型 | 适用范围 | FALCON 防御 |
|---|---|---|
| 格约减攻击（LLL/BKZ） | 低安全级别 | 提高格维度和参数 $q$ |
| 噪声注入攻击 | 签名生成阶段 | 使用确定性随机比特生成器（DRBG） |
| 侧信道攻击（SPA/DPA） | 实现层面 | 常数时间实现、掩码技术 |
| 相关密钥攻击 | 多签名场景 | 使用不同的随机Nonce |
与其他 PQC 方案的对比
FALCON vs Dilithium（ML-DSA）
| 特性 | FALCON | Dilithium（ML-DSA） |
|---|---|---|
| 数学基础 | NTRU 格 | 模块格（Module Lattice） |
| 签名尺寸 | 最小（855~3467 字节） | 中等（1610~3300 字节） |
| 密钥尺寸 | 较大（1664~6656 字节） | 中等（1312~4832 字节） |
| 签名速度 | 较慢（浮点运算多） | 较快（整数运算） |
| 验证速度 | 快 | 快 |
| 实现复杂度 | 高（需要 FFT 和浮点库） | 中（纯整数运算） |
| 常数时间实现 | 困难 | 相对容易 |
FALCON vs SPHINCS+（SLH-DSA）
SPHINCS+ 是 FIPS 205 之外另一种后量子签名方案（FIPS 205 仅包含 FALCON，SPHINCS+ 定义于 FIPS 205 的附录）。两者对比：
| 特性 | FALCON | SPHINCS+ |
|---|---|---|
| 数学基础 | 格密码 | 哈希签名 |
| 签名尺寸 | 中等（855~3467 字节） | 较大（8-64 KB） |
| 密钥尺寸 | 中等 | 较小 |
| 安全性假设 | 格困难问题 | 仅哈希函数安全 |
| 量子安全性 | 强（格问题） | 强（仅依赖哈希） |
| 实现复杂度 | 高 | 低 |
国密对照与应用场景
国密标准的对应关系
目前国密标准中尚无与 FALCON 直接对应的后量子签名标准。但可以从以下角度进行对照：
- GM/T 0034-2014《证书认证系统密码及其相关安全技术规范》：规定了数字签名算法的要求，FALCON 可作为替代 SM2 签名的后量子方案
- GM/T 0024-2023《SSL VPN 技术规范》：规定了传输层安全协议，FALCON 可用于 TLS 1.3 的后量子密钥交换
- GB/T 39786-2021《信息安全技术 密码应用基本要求》：要求系统支持抗量子攻击的密码算法，FALCON 符合这一要求
适用场景
FALCON 特别适用于以下场景：
- 区块链签名：区块链交易需要紧凑的签名以节省存储空间，FALCON 的最小签名尺寸（855 字节）优于 Dilithium
- 物联网设备认证：IoT 设备通常带宽受限但计算资源充足，FALCON 适合此类场景
- 数字证书签发：CA 机构签发后量子证书时，FALCON 可在签名尺寸和安全性之间取得良好平衡
- 长期数据保护：对于需要保护数十年的数据，FALCON 提供比 SM2 更强的长期安全性
迁移建议
从 SM2 迁移到 FALCON 时需注意：
- 密钥长度变化：FALCON-512 公钥为 1664 字节，约为 SM2 公钥（68 字节）的 24 倍
- 签名尺寸变化：FALCON-512 签名为 855 字节，约为 SM2 签名（64 字节）的 13 倍
- 性能差异：FALCON 签名速度约为 SM2 的 1/10~1/5（取决于实现）
- 兼容性：需要更新 TLS 握手协议以支持 FALCON 密钥交换
总结
FALCON 作为 NIST FIPS 205 标准定义的后量子签名方案，代表了格密码领域中签名尺寸优化的前沿成果。其独特的三角化 NTRU 格结构和 FFT 加速技术，使得签名尺寸达到当前 PQC 方案的最低水平。尽管实现复杂度和运行开销较高，FALCON 在带宽敏感场景（如区块链、物联网）中具有不可替代的优势。
对于密码工程实践者而言，理解和掌握 FALCON 的算法原理，不仅有助于选择合适的后量子签名方案，也为研究其他格密码方案（如 Kyber、Dilithium）提供了重要的理论基础。随着 NIST PQC 标准化的深入推进，FALCON 必将在未来的密码基础设施中扮演重要角色。
参考
- FIPS 205: Module-Lattice-Based Digital Signature Standard, NIST, 2024.
- FALCON: Fast-Fourier Lattice-Based Compact Signatures over NTRU, Deneuville et al., EUROCRYPT 2019.
- NIST Special Publication 800-207: Zero Trust Architecture, 2020.
- 国密标准 GM/T 0034-2014《证书认证系统密码及其相关安全技术规范》.
- FALCON 官方参考实现：https://falcon-sign.info/（注意：原链接 falcon-sign.info/falcon/ 已重定向）