基于格的数字签名算法：Falcon 题目描述 Falcon（Fast-Fourier Lattice-based Compact Signatures）是一种基于格理论的 后量子密码学 数字签名算法，其安全性依赖于 NTRU格 上短向量问题的困难性。题目要求：理解Falcon签名的核心步骤，包括密钥生成、签名生成和签名验证，并掌握其利用快速傅里叶变换（FFT）优化多项式运算的原理。 1. 背景知识 （1）NTRU格结构 Falcon使用NTRU格，其定义基于多项式环 \( R = \mathbb{Z}[ x ]/(x^n+1) \)，其中 \( n \) 通常为2的幂（如 \( n=1024 \)）。私钥为一对短多项式 \((f, g)\)，公钥为多项式 \( h = g/f \mod q \)（\( q \) 为模数），对应的格为： \[ \Lambda = \{ (u,v) \in R^2 \mid u + v \cdot h = 0 \mod q \} \] 目标是在格上找到短向量（即签名）。 （2）FFT加速 多项式在环 \( R \) 上的乘法可通过FFT在 \( O(n\log n) \) 时间内计算，这是Falcon高效性的关键。 2. 密钥生成 步骤 生成短多项式 ：随机采样多项式 \( f, g \in R \)，系数取自离散高斯分布，确保 \( f \) 可逆模 \( q \)。 计算公钥 ：计算 \( f \) 的逆 \( f^{-1} \mod q \)，则 \( h = g \cdot f^{-1} \mod q \)。 私钥扩展 ：使用格基分解算法（如LDL分解）将 \((f, g)\) 转化为一组更短的基向量，用于签名时快速找到短向量。 关键点 私钥需满足 \( \| (f,g) \| \) 足够小，以抵御格攻击。 公钥 \( h \) 看似随机，但隐藏了格结构。 3. 签名生成 目标 ：对消息 \( m \) 生成签名 \( s \)，使得 \( (s, c) \) 是NTRU格上的短向量，且 \( c \) 由消息哈希决定。 步骤 哈希消息 ：计算 \( r = \text{Hash}(m) \)，并将其映射到环 \( R \) 上的向量。 采样短向量 ： 使用私钥的短基，通过 Klein抽样算法 （或类似贪心算法）在格上找到接近目标点 \( (0, r) \) 的短向量 \( (s, c) \)。 核心条件：\( s + c \cdot h = r \mod q \)，且 \( \| (s,c) \| \) 极小。 输出签名 ：签名结果为 \( s \)。 细节 Klein抽样通过逐坐标的随机舍入，确保输出向量长度受高斯分布控制。 FFT用于快速计算多项式乘法（如 \( c \cdot h \)）。 4. 签名验证 目标 ：验证 \( (s, c) \) 是否为格上的短向量，且与消息匹配。 步骤 恢复 \( c \) ：由公钥关系 \( c = (r - s) \cdot h^{-1} \mod q \)，其中 \( r = \text{Hash}(m) \)。 检查短性 ：验证 \( \| (s,c) \| \) 是否小于预设阈值（由安全参数决定）。 一致性验证 ：检查 \( s + c \cdot h = r \mod q \)。 关键点 验证仅需公钥 \( h \) 和多项式运算，无需复杂抽样。 短向量条件确保签名无法被伪造。 5. 安全性分析 格攻击 ：已知最好攻击需要解决近似最短向量问题（approx-SVP），当前对 \( n=1024 \) 的格问题在经典和量子计算机下均难解。 侧信道防护 ：采样算法需常数时间实现，避免通过计时攻击泄露私钥。 总结 Falcon通过NTRU格上的短向量问题实现安全签名，并利用FFT提升效率。其核心挑战在于如何高效生成短签名，而验证过程简单快速，适合后量子密码应用。