本文探讨了以太坊抗量子签名方案 Falcon，介绍了其基于 NTRU 格和快速傅里叶采样（FFT）的技术原理。文章分析了 Falcon 在签名尺寸和验证效率方面的优势，讨论了在 EVM 中实现的挑战，并指出了结合账户抽象实现抗量子迁移的未来路径。
这是探索为以太坊实现后量子签名方案可行性的博客系列的第 2 部分。在 第 1 部分中，我们介绍了以太坊向抗量子未来过渡所涉及的基本挑战和注意事项。在本篇中，我们将深入探讨 Falcon，一种极具前景的后量子签名算法，分析其优缺点，以及将其集成到以太坊交易框架中的实际障碍。
Falcon 签名方案 - 技术概览
Falcon (Fast-Fourier Lattice-based Compact Signatures over NTRU) 基于 Gentry、Peikert 和 Vaikuntanathan (GPV) 的基于格的签名框架。它将该框架应用于 NTRU 格，并采用“快速傅里叶采样”陷门采样器。该方案依赖于 NTRU 格上的短整数解 (SIS) 问题，即使使用量子计算机，该问题在一般情况下也被认为在计算上难以解决，因为目前尚无已知的有效求解算法。
核心组件
Falcon 基于哈希并签名范式，是传统 RSA 签名方案的演进。然而，它不再依赖数论问题，而是利用基于格的问题的硬度。Falcon 的安全性基于在 NTRU 格中寻找短向量的硬度，利用高斯采样技术生成具有缩减范数的陷门基。这确保了高效的密钥生成和签名。
- 密钥生成：
- 给定一个 NTRU 多项式环 $\mathbb{Z}[X] / (X^n + 1)$，私钥由满足 NTRU 方程的两个短多项式 $f, g$ 组成。
- 公钥在环 $\mathbb{Z}_q[X] / (X^n + 1)$ 中导出为 $h = g / f$。
- 签名过程：
- 消息被哈希为格域中的挑战向量。
- 使用快速傅里叶采样采样出一个短解，在保持抗格还原攻击安全性的同时，确保紧凑的签名大小。
- 签名由满足挑战的短格向量组成。
- 验证：
- 验证者检查签名是否满足格环中的公钥关系。
- 验证涉及计算范数并确保模算术下格基的有效性。
Falcon 旨在提供一种稳健的后量子签名解决方案，将基于格的密码学与高效的采样技术相结合。虽然其安全性优势显而易见，但与任何密码系统一样，它在复杂性和实现挑战方面也存在一定的权衡。现在，让我们来分析 Falcon 的亮点、潜在陷阱以及一些更具挑战性的方面。
好的方面
除了 NIST 强调的众所周知的优势，如紧凑的签名 (Compact Signatures)、快速操作 (Fast Operations)（通过 FFT 技术实现高效的密钥生成和验证）以及安全证明 (Security Proofs)（依赖于格还原和最坏情况硬度假设）之外。Falcon 还提供了针对以太坊的特定优势。值得注意的是，它具有明确定义的最坏情况运行时间，这使得它对以太坊虚拟机 (EVM) 特别有用，因为在 EVM 中，可预测的性能和执行时间对于可扩展性和可靠性至关重要。
坏的方面
Falcon 对浮点运算 (floating-point arithmetic) 和专门的数论变换 (NTT/FFT) 的依赖可能会导致实现复杂性 (implementation complexity) 以及在签名 (signing) 过程中对侧信道漏洞的敏感性。然而，这对于以太坊来说不是一个重大顾虑，因为签名发生在链下，那里对性能的要求不那么苛刻。主要的重点是优化发生在链上的验证过程，以确保高效且安全的执行。
棘手的方面
目前一直在进行关于高效聚合 Falcon 签名的研究，例如这篇论文中介绍的工作。假设聚合效率足够高，在共识层使用 Falcon 来取代 BLS 签名（而不是基于哈希多签名的替代提议），将有助于在整个以太坊网络中保持更具同质化的技术栈。
结论
Falcon 是后量子密码学应用的一个强有力候选者，包括像以太坊这样对签名大小和验证效率要求极高的区块链系统。在本系列的第 3 部分中，我们将开始实现第 1 部分中介绍的混合方法，最初将重点放在账户抽象 (Account Abstraction) 和用于 Falcon 验证的 Solidity 合约上，从而弥合后量子安全与以太坊当前基础设施之间的鸿沟。
