技术突破 | 抗量子攻击能力再提升，筑牢PQC密码算法防线

摘要：当前，量子计算机的快速发展对经典公钥密码体系构成了前所未有的威胁，其核心在于量子算法对传统数学难题的指数级加速破解能力。以Shor算法为代表的量子计算突破，能够在多项式时间内高效解决大整数分解（RSA密码体系的基础）和离散对数问题（ECC椭圆曲线密码与Diff

当前，量子计算机的快速发展对经典公钥密码体系构成了前所未有的威胁，其核心在于量子算法对传统数学难题的指数级加速破解能力。以Shor算法为代表的量子计算突破，能够在多项式时间内高效解决大整数分解（RSA密码体系的基础）和离散对数问题（ECC椭圆曲线密码与Diffie-Hellman密钥交换的基石），而这两类问题正是当前主流公钥密码学的安全核心。

在这一时代背景的挑战下，一大批后量子密码算法踊跃出现。此类算法往往通过一些巧妙的数学难题进行构造，从而能够较好地规避量子计算的攻击，旨在设计能够抵抗量子计算攻击的密码算法。在此类算法中，Falcon（Fast-Fourier Lattice-based Compact Signatures over NTRU）作为一种基于格的数字签名方案，以其高效性和安全性成为后量子密码学领域的重要代表。Falcon算法不仅能从理论上抵御量子计算攻击的能力，还具备签名长度短、计算效率高等特点，为构建量子时代的安全密码系统提供了可靠的技术支撑。

Falcon算法是不是足够安全？

在回答这个问题之前，我们先来快速回顾一下Falcon算法，这是一种基于格密码学的后量子数字签名算法，由Pierre-Alain Fouque等密码学家团队设计，于2017年提交给NIST后量子密码标准化项目。

Falcon算法建立在三个核心理论之上，用公式表示，Falcon的技术路线可以被抽象地描述为：Falcon=GPV框架+NTRU格+快速傅里叶采样。

三大理论的角色分工明确：

GPV框架：由Gentry、Peikert和Vaikuntanathan提出的基于格密码的hash-and-sign签名方案框架，为Falcon算法提供“签名架构骨架”——需依赖两类核心元素，即特定格结构与陷门采样器。

NTRU格：源于NTRU加密系统的特殊格结构，是Falcon算法的“数学难题基础与实体载体”，签名生成、验证的全流程均需通过NTRU格完成实例化操作。

快速傅里叶采样：一种高效的陷门采样技术，相当于Falcon算法的“性能加速器”，能快速生成满足安全要求的短向量，保障签名过程的实时性。

需特别注意：由于Falcon的全流程依赖NTRU格，其安全性与性能表现直接与NTRU密码的特性挂钩——这也为后续的安全挑战埋下伏笔。

Falcon算法作为当前NIST后量子密码算法的“四大标准之一”，具有广阔的实用价值及应用前景。然而，其当前主要面临以下两个问题：首先，当前NIST给出的Falcon算法的安全性不足，Falcon的安全性基于NTRU格问题的困难性，但其为平衡效率而选择的参数在近年研究中暴露出安全冗余不足，导致其在level 1情况下实际的安全性比特位大约在120比特位；其次，Falcon的离散高斯采样需要生成符合特定统计分布的随机数，但其实现常依赖拒绝采样法，这一方法在采样过程中可能因随机值的接受/拒绝而产生可观测的时间差异，攻击者通过分析签名生成的时间侧信道，可推断出采样值的范围或分布特征，进而逆向推导私钥相关的格基信息。

Falcon算法安全问题如何解决？

为了解决上述问题，中国电信量子研究院联合上海交通大学郁昱教授团队以及东南大学孙超老师团队展开技术攻关。其中，郁昱教授是密码学领域国际权威学者，科研成果发表于Crypto、IEEE S&P、EuroCrypt、USENIX等国际密码学领域的顶级会议；孙超老师长期深耕后量子密码与密码学中的数学领域，论文见于AsiaCrypt、CHES等国际密码学领域的顶级会议，其设计的格密码数字签名算法已入选NIST后量子密码全球征集名单。

如前所述，Falcon算法的安全性与NTRU格直接挂钩。这是因为Falcon算法的安全性很大程度上决定于其所使用的密钥质量，而该密钥则取自于NTRU格的密钥生成算法。在NTRU密钥生成算法中，给出生成该密钥的细节，当生成密钥的参数限制越强时，所生成的密钥质量越高，Falcon算法的安全性就越强。然而，我们并不能频繁地通过限制参数来提高算法的安全性，这是因为这将导致算法整体的性能显著下降。在这种情况，联合团队给出了一种优化的NTRU密钥生成算法，结合一种更匹配的采样算法以及动态参数调整机制，对NTRU密钥生成算法进行优化，进而能够在保证算法安全性提升的同时保障算法的运行性能，达到两者的兼容平衡。

Falcon算法优化后实现了什么关键成果？

针对Falcon算法在安全性和实现效率上的挑战，联合团队通过优化NTRU密钥生成算法取得了显著成果。

实验表明，改进后的Falcon算法能够有效抵御潜在的量子计算攻击，同时降低了侧信道攻击（如时序攻击和故障攻击）的风险。如下表所示，当质量参数越低时，所对应的算法安全性等级就越高。因此，联合团队所提出的优化算法在512位情况下，能够使得Falcon算法的安全性提升8比特位。这使得Falcon算法在实际应用中更加可靠，为后量子密码学的落地提供了更强的安全保障。

这一关键成果标志着我国在后量子密码学领域迈出了重要一步，为构建未来量子安全通信体系奠定了坚实基础。

在量子计算技术迅猛发展的背景下，传统密码体系面临前所未有的挑战。Falcon算法作为后量子密码学的重要代表，尽管具备高效性和抗量子攻击潜力，但其安全性和实现效率仍存在改进空间。中国电信量子研究院联合上海交通大学郁昱教授团队与东南大学孙超老师团队，通过优化NTRU密钥生成算法，成功提升了Falcon算法的安全性和实用性。实验数据表明，改进后的算法在512位情况下，安全性分别提升了8比特位。