后量子密码算法之FALCON算法解读

1994年，Peter Shor设计了一个算法，在量子计算机上运行该算法可以在多项式时间内解决大整数因子分解问题和离散对数问题。这对诸如RSA和ECC等基于这两类困难问题的经典公钥密码系统来说是一个巨大的威胁。所幸当时量子计算机尚未问世；然而，随着量子技术的发展，这个威胁正日益逼近。为了应对量子威胁，在2016年，NIST发起了后量子密码（PQC）标准的提案征集。FALCON是提交到NIST PQC征集的一个签名算法。2022年，NIST宣布了四个候选提案入选标准化方案，其中之一就是FALCON。NIST称，FALCON入选的原因是Dilithium（PQC签名方案，已被NIST标准化）的签名比较长，在需要较短签名的场合FALCON可以派上用场。NIST称，FALCON标准草案将在2024年底发布，最终草案版本将在2025年发布。

什么是FALCON?

FLACON代表“基于NTRU格和快速傅里叶的紧致签名”。它是一种可以抵抗量子攻击的数字签名算法。它可以用来检测数据所受到的非授权修改，验证签名者的身份。FALCON生成的签名可作为证据，证明签名确由声称的签名者签署。这种特性被称为“抗抵赖性”，即签名者无法事后否认签名行为。

FALCON算法的工作原理

FALCON是由Gentry、PeiKert和Vaikuntanathan（GPV）描述的理论框架的一个实例化，这个理论框架描述了一种构造基于格的hash-and-sign范式的签名方案。这个框架需要有两个元素：一类格密码和一个陷门采样器。FALCON选择了NTRU格和快速傅里叶采样。简言之，FALCON签名方案可以描述如下：

FALCON = GPV框架 + NTRU格 + 快速傅里叶采样

FALCON有哪些优势

与其他的抗量子签名算法相比，FALCON的特点是紧致，灵活，验签速度快。

首先，FALCON的主要设计原则是紧致，使得公钥长度和签名长度之和达到最小。在安全级别“I级”中，FALCON的公钥长度是897字节，比Dilithium的公钥长度短415字节。而在签名长度方面，FALCON算法的签名长度为666字节，比Dilithium算法的签名长度短1754字节。其次, FALCON算法很灵活。一方面，它可以转换为IBE（Identity-Based Encryption）方案，这个方案在性能上比基于双线性对的IBE方案要快几个数量级。另一方面，FALCON也可转换为环签名方案。另外，FALCON在验签方面的性能比Dilithium表现得更优秀。

FALCON的参数

FALCON指定了两个参数集，分别对应于NIST规定的安全级别I和安全级别V。具体参数见下表：

FALCON可以用在哪些场景

FALCON已经被集成到很多软件密码库中，比如OQS（Open Quantum Safe）。OQS是一个以支持密码算法抗量子化为目标的工程，已经被集成到广泛使用的OpenSSL库。得益于FALCON算法的灵活性，它可以用在下列等场景：

关于握奇

巧合的是，当Peter shor提出shor算法的同年，1994年，握奇公司成立，开始基于公开密钥密码体系开发信息安全解决方案。凭借在密码算法、数字安全和安全芯片操作系统领域的深厚积累，握奇的产品方案为全球数十亿用户提供身份认证和交易安全的保障。我们紧跟后量子密码算法的发展，积极布局，密切关注标准研究发展趋势，确保未来的产品设计能够应对量子计算时代的安全挑战，为客户提供前沿的抗量子算法支持，以构建强大的数字安全防护体系。