编辑推荐：
对称性（Symmetry）在格密码学中至关重要，其中安全签名依赖于多项式环上的结构不变量。本文对轻量级签名方案（lightweight signature scheme）Falcon-M进行了严格的安全性和正确性分析。研究人员首先通过该方案的一个明确实验实例化
对称性（Symmetry）在格密码学中至关重要，其中安全签名依赖于多项式环上的结构不变量。本文对轻量级签名方案（lightweight signature scheme）Falcon-M进行了严格的安全性和正确性分析。研究人员首先通过该方案的一个明确实验实例化（experimental instantiation）展示了一个基本的正确性失败：由于签名算法在代数上与私钥（private key）解耦，在研究人员的测试实验中，没有诚实生成的签名被接受。此外，研究人员揭示出移除NTRU陷门（NTRU trapdoor）打破了基本的计算不对称性，导致验证方程（verification equation）退化为一个可公开求解的线性系统（linear system）。因此，对于可逆公钥（public key），攻击者可以通过频域（frequency domain）中的逐点代数逆（pointwise algebraic inversion）以O(n log n)时间复杂度仅从公开数据执行直接通用伪造攻击（universal forgery attack）。对于不可逆密钥，研究人员进一步识别出一种利用局部盐搜索（localized salt-search）的实用存在性伪造（existential forgery）。最终，这些实际的密码分析结果从数学上否定了在被分析实例化（instantiation）下的声称安全性。
**论文解读：Falcon-M签名方案的密码分析**
**1. 研究背景与问题**
格密码学（lattice cryptography）中，对称性（Symmetry）是安全签名的基础，依赖于多项式环上的结构不变量。Falcon方案基于NTRU陷门（NTRU trapdoor）和快速傅里叶变换（FFT）实现紧凑密钥与签名，但在物联网（IoT）等资源受限环境中部署困难。为此，Kerimbayeva等人提出轻量级变体Falcon-M，通过移除NTRU陷门，直接使用随机多项式与线性代数操作完成签名生成与验证，以降低内存和计算开销。然而，这种设计破坏了签名与验证之间的代数对称性，可能危及系统安全。研究人员开展严格分析，发现Falcon-M存在根本性正确性失败和结构缺陷，导致攻击者可在多项式时间（polynomial time）内伪造签名。论文发表在《Symmetry》上。
**2. 主要技术方法**
研究人员采用离散高斯采样（discrete Gaussian sampling）生成签名中的随机向量，并利用快速傅里叶变换（FFT）/数论变换（NTT）在频域实现多项式乘法与求逆。针对可逆公钥，通过频域逐点代数逆（pointwise algebraic inversion）执行通用伪造攻击；针对不可逆公钥，采用盐搜索（salt-search）技术实现存在性伪造。实验基于Intel Xeon Gold 6271C CPU（2.60 GHz）、2GB RAM，操作系统Debian 9.9，数学软件SageMath 7.4，进行百万次独立随机试验（样本来源为计算机模拟，无真实队列）。
**3. 研究结果**
**1. Introduction（引言）：** 通过分析Falcon-M的设计，指出移除NTRU陷门破坏了验证方程的非线性绑定，为后续攻击奠定基础。
**2. Description of the Falcon-M Signature Scheme（Falcon-M签名方案描述）：** 严格复现原方案算法，揭示签名生成与私钥完全解耦，仅依赖随机采样和频域运算。
**2.1 Algorithm Formalization（算法形式化）：** 形式化描述密钥生成、签名生成和验证算法，并指出原方案中符号不一致和分布定义不完整。
**2.2 Comparison of Core Components and Computational Overhead（核心组件与计算开销比较）：** 比较Falcon与Falcon-M，发现轻量化设计（移除陷门）导致验证方程退化为线性系统。
**3. Security Analysis of the Falcon-M Signature Scheme（Falcon-M签名方案的安全分析）：** 通过理论推导，证明私钥解耦使得验证方程可公开求解，攻击者可在频域直接求逆。
**3.1 Threat Model and Practical Attack Assumptions（威胁模型与实际攻击假设）：** 定义攻击者仅需公钥和目标消息，假设公钥在频域可逆（或通过盐搜索处理）。
**3.2 Description of the Forgery Attack on Falcon-M（Falcon-M伪造攻击描述）：** 提出通用伪造攻击：对于可逆公钥，通过频域逐点除法计算签名，时间复杂度O(n log n)。
**3.3 Correctness Analysis of the Forgery Attack（伪造攻击的正确性分析）：** 证明引理1（频域均匀分布）和定理1（不可逆公钥的盐搜索存在性伪造），严格推导可逆概率约91.99%，单次盐搜索成功概率为1/q^z。
**3.4 Discussion and Experimental Analysis（讨论与实验分析）：** 通过100万次实验验证：诚实签名接受率为0%（95%置信上限为3/百万）；可逆公钥比例92.03%，攻击残差为0；盐搜索在z=1时预期迭代q次，z=2时q^2次，实验成功率达到92.63%（1000次盐重试）。
**4. 总结讨论与结论翻译**
**讨论部分总结：** 实验数据与理论高度一致，确认可逆公钥下通用攻击100%成功，不可逆公钥下盐搜索攻击在z≤2时可行，且残差严格为零。该攻击完全依赖代数逆，不依赖连续域近似，彻底否定了Falcon-M的EUF-CMA安全声明。
**结论部分翻译：** 本文对无陷门格签名方案Falcon-M进行了正式密码分析。基于具体实验实例化（experimental instantiation）的评估强烈表明，移除NTRU陷门导致私钥与签名过程在结构上完全解耦，在研究人员的大规模测试中，诚实签名的接受率为0%。此外，研究人员揭示了验证方程退化为线性可逆系统的结构缺陷。通过展示理论复杂度为O(n log n)的直接通用伪造攻击（universal forgery attack）以及利用局部盐搜索（localized salt-search）的存在性伪造（existential forgery），研究人员得出了一个实际结果，从根本上否定了该方案的EUF-CMA安全声明。这些发现强调，在格密码学中，结构对称性（structural symmetry）和非线性代数绑定（non-linear algebraic binding）不能为了轻量级性能而牺牲。
