《A Closer Look at Falcon》精读（一）：核心概念与安全证明入门笔记

前言Falcon 是一种基于格密码学的后量子数字签名方案。它利用 NTRU 格结构和高效的高斯采样技术实现了较短的签名与公钥。但对于刚开始学习密码学的人来说理解 Falcon 并不容易。在阅读论文《A Closer Look at Falcon》的过程中我发现困难不仅在于数学公式更在于许多基础概念彼此关联格、短向量、陷门、高斯采样、随机预言机、安全归约、Rényi 散度等。因此本文尝试从最基本的概念出发整理理解 Falcon 安全证明所需要的知识。全文主要围绕三个问题展开Falcon 的数字签名是怎样生成的Falcon 的安全性与哪些数学难题有关数学家如何利用概率工具证明签名方案的安全性本文是一篇概念性学习笔记旨在理解论文的主要思路并不代替严格的数学证明。一、数字签名的基础概念1. 公钥与私钥数字签名通常涉及两把密钥。私钥Secret Key由签名者秘密保存用于生成数字签名。公钥Public Key可以公开其他人利用它验证签名是否合法。例如Alice 使用私钥为文件生成签名Bob 使用 Alice 的公钥验证文件是否具有有效签名。数字签名的基本目标包括真实性验证签名是否由掌握相应私钥的人生成。完整性判断消息与签名是否匹配防止消息被悄悄修改。不可伪造性没有私钥的攻击者应当难以生成符合要求的新签名。这里需要注意数字签名与加密并不是同一回事。加密主要保护消息内容的机密性而数字签名主要提供真实性和完整性保障。2. 哈希函数Hash Function哈希函数可以把输入消息映射为固定格式的输出。例如消息 → 哈希函数 → 哈希值不同消息可能具有不同的哈希结果。密码学哈希函数通常要求具有一定的抗碰撞性和抗原像攻击能力。在 Falcon 中哈希结果不仅是消息的标识更参与了签名的数学构造。3. 盐值Salt盐值是签名过程中使用的一段随机信息通常用 r 表示。同一条消息使用不同盐值可能产生不同的哈希结果和签名。论文研究的 Falcon 会将消息、盐值以及公钥一起输入哈希函数c H(pk, r, m)其中符号含义pk公钥r随机盐值m消息c哈希结果盐值的引入有助于实现随机化签名。其具体安全作用需要结合签名方案和安全证明分析。盐值是一段随机数据。 它会和消息一起参与哈希计算。盐值不是私钥不需要保密。 Falcon 会将盐值放进最终签名。不同的盐值通常会产生不同的哈希目标。 因而同一条消息可以得到不同的合法签名。Falcon 每次重新采样时都会重新选择盐值。 这有利于作者完成安全证明。4. 普通不可伪造性与强不可伪造性密码学通常使用两种安全性质描述签名算法。普通不可伪造性UF-CMA即使攻击者能够请求合法签名也应当难以为一条此前未请求签名的新消息伪造有效签名。强不可伪造性SUF-CMA要求更严格。即使攻击者已经获得某条消息的合法签名也不能针对该消息生成一份不同但仍然有效的新签名。因此强不可伪造性所限制的攻击行为更多。普通不可伪造性要求攻击者不能伪造“新消息”的签名强不可伪造性进一步要求攻击者不能为“旧消息”伪造一份新的签名。二、格密码学的核心概念1. 什么是格Lattice可以把格想象成空间中按照一定数学规则排列的离散点集。例如在二维平面中整数坐标点构成了一个简单的格。在密码学中研究者通常使用维度更高、结构更复杂的格。这些格能够产生某些计算上困难的问题为密码算法提供安全基础。2. 短向量Short Vector格中的每个点可以看作一个向量。所谓短向量就是长度比较小的向量。例如向量 (3, 4) 的欧几里得长度为 5。向量 (6, 8) 的长度为 10。第一个向量显然更短。在高维格中寻找满足指定条件的短向量可能非常困难。Falcon 的签名机制正是与这种短向量问题密切相关。3. 范数与范数界 β范数Norm用于衡量向量的大小。在 Falcon 的安全分析中β 表示允许的向量长度上界。可以简单理解为向量长度不超过 β满足长度要求。向量长度超过 β不满足长度要求。不过一个向量满足长度要求并不代表它一定是一份有效签名还必须满足相应的代数关系。4. 陷门Trapdoor陷门是密码学中非常重要的概念。可以把它理解成一种特殊的秘密数学信息对于不知道陷门的人完成某项计算很困难。但对于掌握陷门的人同样的任务可以高效完成。在 Falcon 中私钥包含与 NTRU 格有关的陷门信息。签名者利用陷门高效生成满足指定数学关系的短向量。这也是 Falcon 能够完成数字签名的重要原因。5. 高斯采样Gaussian Sampling高斯分布是一种重要的概率分布。在一维情形中人们通常把它画成钟形曲线靠近中心的数值出现概率较高距离中心较远的数值出现概率较低。格密码学中的离散高斯采样则是在离散的格点上按照相应的高斯概率规律进行采样。在 Falcon 中高斯采样帮助签名者生成符合要求的短向量。但是实际采样过程必须兼顾效率、输出分布和向量长度因此实现起来并不简单。6. NTRU 格与 FFO 采样器Falcon 使用具有特殊代数结构的 NTRU 格。这种结构有助于提高计算效率并减小公钥和签名的大小。Falcon 还使用基于FFOFast Fourier Orthogonalization快速傅里叶正交化技术的采样器。它利用 NTRU 结构进行高效计算是 Falcon 实现紧凑签名的重要技术之一。三、Falcon 安全性依赖的数学问题1. SIS 问题SIS 的英文全称是 Short Integer Solution。它要求寻找一个非零、足够短的整数向量使其满足指定的模线性关系。通俗来说在许多数学限制下寻找一个足够短的向量。适当参数下的 SIS 问题被认为具有较高的计算难度因此经常用于格密码学的安全构造与分析。2. ISIS 问题ISIS 是 Inhomogeneous Short Integer Solution即非齐次短整数解问题。与 SIS 相比可以直观理解为它要求短向量满足的等式右侧不再固定为零而是某个给定目标。也就是说我们不仅需要找到短向量还需要让它对应到指定的数学目标。Falcon 的安全归约与这种问题密切相关。3. 多目标问题Multi-target Problem普通的单目标问题只给出一个目标。多目标问题则会给出多个目标只要求攻击者成功解决其中一个。例如给出 100 道困难数学题只需要解出任意一道。论文中的t-R-ISIS就是多目标的环上 ISIS 变体其中 t 表示目标数量。4. 第二原像问题假设已经知道某个数学目标 c以及满足条件的一组短向量。现在要求寻找另一组不同的短向量同样对应目标 c。这就是第二原像问题的基本思想。论文研究的t-R-SPISIS是这类问题的一个特殊版本。它与 Falcon 的强不可伪造性有关。第二原像问题就是已知一个合法的短前像再寻找同一数学目标下另一个不同的合法短前像。前像Preimage就是已知一个计算结果反过来寻找能够产生这个结果的输入。5. 困难性假设困难性假设并不是声称数学家已经证明某个问题永远不可能被快速解决。它的意思是在当前研究和指定参数下我们认为高效攻击者难以解决这个数学问题并据此分析密码系统的安全性。这也是理解密码学安全证明的关键一个证明可以严格成立但它提供的具体安全保证仍然依赖某些数学问题的困难性假设。四、安全证明需要哪些工具1. 安全归约Security Reduction安全归约是现代密码学安全证明的重要方法。它的核心思路是如果存在能够高效攻击密码算法的程序那么我们就能利用这个程序解决一个公认困难的数学问题。例如攻击者 A 能够伪造 Falcon 签名。数学家构造算法 B利用 A 的攻击结果解决 R-ISIS。如果 R-ISIS 确实足够困难那么这种归约就为 Falcon 的不可伪造性提供了数学依据。2. 随机预言机Random Oracle随机预言机是安全证明中常用的理想化哈希模型。对于一个此前没有出现过的输入它返回一个随机结果。对于曾经查询过的输入它必须返回与之前相同的结果。因此模拟随机预言机时通常需要维护一张查询记录表。论文中的 H 就承担了记录输入与输出对应关系的作用。需要强调随机预言机是数学模型不等于现实中的某个具体哈希函数。3. 随机预言机编程在安全证明中数学家构造的模拟器可以按照证明需要为尚未查询过的输入安排哈希输出。例如把一个困难数学问题的目标嵌入哈希结果。当攻击者最终成功伪造签名时模拟器便可能从签名中提取出该数学问题的解。这称为随机预言机编程。随机预言机编程就是安全证明中的模拟器为尚未查询过的输入预先安排哈希输出从而能够模拟签名或嵌入困难数学问题。4. 签名查询与哈希查询论文使用两个重要符号符号含义攻击者最多可以请求多少次合法签名攻击者最多可以进行多少次随机预言机查询二者必须区别签名查询是向签名机器要一个合格答案哈希查询是向随机预言机询问一道数学题的目标值。攻击者请求一次合法签名不等于进行一次哈希查询。在论文的定理 1 中安全归约使用了具有 1 个目标的 R-ISIS 问题。额外的一个目标用于处理最终伪造签名验证过程中可能出现的新哈希查询。5. 攻击优势Advantage攻击优势用于量化攻击者成功的能力。在不可伪造性安全游戏中可以把它理解为攻击者成功赢得游戏的概率。安全证明希望给这个概率建立一个足够小的上界。6. 安全位数Security Bits安全位数用于描述密码方案抵抗攻击的计算强度。例如120 bit 安全性通常意味着相关攻击需要约 () 量级的计算资源具体解释取决于采用的攻击模型和成本估计。不能仅凭算法使用了多长的密钥就直接断言它拥有多少安全位数。也不能把所有安全证明中的概率损失简单等同于实际算法已经遭受的攻击。五、为什么论文大量使用概率论1. 条件概率与条件分布条件概率研究的是在某个条件已经成立时另一个事件发生的概率。例如已知签名向量满足指定数学关系后它的概率分布可能与无条件采样时不同。Falcon 论文中的一些游戏转换就需要比较这种条件下的采样分布。2. 独立性如果一个随机事件的结果不会改变另一个随机事件的概率规律我们就说它们具有独立性。分析连续多次采样时是否独立非常重要。不能因为两次操作都使用随机数就直接认为它们一定独立。3. 生日悖论生日悖论说明当我们随机生成越来越多的结果时出现重复结果的概率可能比直觉预期增长得更快。在密码学中这种思想经常用于分析随机值碰撞问题。Falcon 安全证明也需要处理随机盐值与已有哈希查询产生重复输入的可能性。4. 联合界Union Bound联合界用于限制多个坏事件中至少发生一个的概率。例如如果一次操作存在多种失败方式我们可以分别分析这些失败事件然后给出总体失败概率的上界。这种方法不要求所有事件相互独立。5. 二项分布Binomial Distribution假设每次采样都有一定概率得到合格短向量。现在重复采样若干次希望知道成功了多少次。这类问题可以使用二项分布进行分析。二项分布可以计算多次独立尝试中成功次数的概率而 Falcon 论文借助它分析有限采样次数能否完成签名请求。论文中的游戏 G₁ 就使用这种思路分析有限采样次数内能否完成足够多的签名请求。6. 统计距离与 Rényi 散度这两者都可以用于研究概率分布之间的差异但它们是不同的数学量。统计距离关注两个分布在概率上的差别。可以理解为两种概率分布对同一事件给出的概率最多能相差多少。我们假设两台机器有机器 A 抽中红球的概率50%。机器 B 抽中红球的概率60%。显然二者相差 10 个百分点。抽中蓝球的概率也相差 10 个百分点。因此两台机器的统计距离就是Rényi 散度是一族由阶数参数控制的分布比较工具。统计距离关注的是两个分布给某个事件分配的概率最大能差多少Rényi 散度则通过比较各个结果的相对概率得到另一种衡量分布差异的数学量。继续使用刚才的两台机器作为例子。我们选择二阶 Rényi 散度也就是 a2。按照 Falcon 论文采用的定义计算得到在这篇论文使用的定义下当两个分布完全相同Rényi 散度等于 1。当两个分布存在差异Rényi 散度大于 1。越接近 1通常意味着两个分布越接近。因此1.04 表示两台抽奖机在这种衡量方式下存在一定的差异。要特别注意Rényi 散度不是“概率差 4%”的意思。而且它还带有一个参数 a叫做 Rényi 阶数。改变这个参数就会改变衡量分布差异的方式。论文将 Rényi 散度用于 Falcon 的安全证明重点分析不同采样方式产生的分布变化。作者还可以调整 Rényi 阶数在数学允许的范围内尽量减少证明损失。7. 安全损失与紧归约安全损失Security Loss指的是把攻击签名算法的问题归约到困难数学问题时安全保证会损失多少。紧归约Tight Reduction指的是尽量减少这种损失让数学证明更准确地反映算法的安全性。安全归约虽然能建立密码算法与底层数学难题的联系但转换过程中可能存在损失。例如攻击者成功概率为 10%但归约算法成功解决数学难题的概率可能只有 1%。这种概率变化会影响我们最终能够证明的安全强度。紧归约Tight Reduction希望尽量减少这种损失同时控制归约算法的额外运行时间。Falcon 论文的一项重要工作就是优化 Rényi 散度参数以获得更紧的具体安全界。六、Falcon 论文怎样证明安全——G₀ 到 G₅理解前面的基础知识后我们终于可以讨论论文中最重要的部分安全证明。1. 引理、定理与游戏序列引理Lemma是用于帮助证明其他结论的辅助数学结论。定理Theorem是在明确条件下经过严格证明的数学结论。游戏序列Sequence of Games则是一种安全证明方法。数学家从原始安全游戏出发逐步修改实验规则每一步分析成功概率的变化。最终将复杂的攻击问题转换成更容易分析的数学问题。2. 六个游戏分别做什么论文定理 1 的证明构造了 G₀ 到 G₅ 六个游戏。游戏主要作用G₀原始的 CoreFalcon 不可伪造性游戏G₁限制签名过程中的累计采样次数G₂签名过程中遇到已经查询过的哈希输入就中止G₃改变辅助随机预言机生成哈希结果的方式G₄将前像采样器替换为理想的格上高斯采样G₅直接使用辅助随机预言机提前生成的向量这些修改并不是为了提高真实 Falcon 算法的运行速度而是为了逐步建立数学证明。3. 为什么要限制采样次数 CₛFalcon 在签名过程中可能需要反复采样直到得到符合长度要求的短向量。因此作者在 G₁ 中引入累计采样次数上限 Cₛ。超过上限游戏就中止。这样数学家就可以利用概率工具分析有限次采样能否满足签名请求。4. 为什么 G₂ 要处理重复哈希输入在 G₂ 中作者禁止签名过程使用已被查询过的相同哈希输入。这样做有助于后续模拟随机预言机。但它改变了游戏规则因此作者必须证明这种额外中止事件发生的概率有多大。5. G₃ 和 G₄ 为什么使用 Rényi 散度G₃ 改变了哈希结果的生成方式。G₄ 改变了签名向量的采样方式。这些修改都会涉及概率分布之间的比较。因此作者分别使用两个 Rényi 阶数参数用于分析aᵤG₂ → G₃ 的哈希结果分布变化aₚG₃ → G₄ 的前像采样分布变化两个参数可以分别优化而不必强制相同。6. G₅ 为什么特别重要在 G₅ 中签名机器直接使用辅助随机预言机此前生成的向量。作者证明这种方式与 G₄ 中相应的理想采样具有相同的条件分布。因此G₄ 与 G₅ 的获胜概率相等。最后作者在 Claim 6 中构造算法 B如果攻击者 A 在 G₅ 中成功伪造签名那么 B 就能够从中提取出满足要求的短向量解决相应的 R-ISIS 挑战。这就完成了安全归约的最后一步。7. 将各个游戏的概率关系组合有些游戏转换会引入概率损失有些不会。数学家必须把每一步的关系组合起来才能得到原始游戏 G₀ 的攻击成功概率上界。整个证明可以概括为原始签名伪造攻击 → 游戏序列转换 → 构造求解困难格问题的算法 → 给出攻击成功概率上界这就是定理 1 的主要证明思路。七、论文究竟得出了什么结果《A Closer Look at Falcon》研究的一个关键问题是能否为 Falcon 类型的签名方案建立严格的、具有实际参数意义的安全证明作者指出要获得所需的证明需要对原始 Falcon 做少量修改得到 Falcon。其中包括在签名的重复采样循环内部重新选择随机盐值。将公钥纳入哈希输入。因此必须区分原始 Falcon与论文所分析的 Falcon。论文在随机预言机模型和相应数学困难性假设下得到如下具体安全分析结果方案条件论文给出的可证明安全位数Falcon-512最多 () 次签名查询113 bitFalcon-512最多 () 次签名查询119 bitFalcon-1024论文指定的参数与假设256 bit这些结果表明安全位数不仅与底层格问题的难度有关还受到签名查询次数、概率分布差异和安全归约损失的影响。需要注意这些数字是在明确条件下的安全分析结果不能理解为原始 Falcon 已经被证明绝对安全也不能理解为攻击者已经成功破解了 Falcon。八、总结理解 Falcon 安全证明的知识路线回顾这些概念可以把 Falcon 的学习分成三个层次。第一个层次理解签名算法。需要掌握公钥、私钥、哈希函数、随机盐值、格、短向量、陷门和高斯采样。这一层回答Falcon 是怎样生成和验证数字签名的第二个层次理解安全性来自哪里。需要掌握 SIS、ISIS、多目标问题、第二原像问题、困难性假设和安全归约。这一层回答为什么攻击 Falcon 的能力能够与解决困难格问题联系起来第三个层次理解安全证明怎样完成。需要掌握随机预言机、安全游戏、统计距离、Rényi 散度、概率上界、游戏序列和参数优化。这一层回答为什么数学家能够严格限制攻击者的成功概率并计算具体的安全强度参考文献[1]A Closer Look at Falcon本文主要阅读论文。说明本文以概念理解为主对部分数学问题和概率工具进行了简化。正式研究或引用时应以原论文中的定义、定理及适用条件为准。