★ FEATURED ARTICLE 研究方向后量子密码学、格密码、数字签名阅读论文A Closer Look at Falcon阅读范围Theorem 1、Theorem 2、Appendix C、Appendix D、Section 5关键词Game Hopping、UF-CMA、SUF-CMA、Rényi 散度、R-ISIS、R-SPISIS前言从理解定理结论到理解证明过程在上一篇博客中我已经梳理了 Falcon 的研究背景、主要算法修改、GPV 安全框架以及 Rényi 散度在密码学证明中的作用。不过当时我对 Theorem 1 和 Theorem 2 的理解主要还停留在结论层面。例如我已经知道Theorem 1 将普通不可伪造性归约到 R-ISIS。Theorem 2 利用 R-SPISIS 进一步分析强不可伪造性。Rényi 散度用于控制安全模拟过程中产生的概率分布差异。但如果进一步追问作者为什么需要构造六个安全游戏每一步游戏跳转究竟改变了什么这些改变如何最终形成安全界当时的我还很难完整回答。因此这次我把阅读重点放在论文 Appendix C 和 Appendix D对 Claim 111 进行了系统梳理并进一步结合 Section 5 的 Table 3理解这些证明在具体安全参数分析中的作用。本文按照原论文的证明逻辑展开同时加入阅读过程中帮助我理解的例子。一、Game Hopping为什么需要游戏跳转证明在密码学中安全归约Security Reduction的基本思想是如果攻击者能够有效攻击某个密码方案那么我们就可以利用这个攻击者解决一个被认为困难的数学问题。对于 Falcon作者希望将签名伪造与格上的困难问题联系起来。但这里存在一个问题正常的 Falcon 签名者拥有私钥陷门可以为哈希目标找到对应的短原像。而归约算法通常只有公钥和数学挑战没有私钥陷门。因此归约算法不能直接照搬真实签名算法来回答攻击者的签名查询。为了解决这个问题作者采用游戏跳转Game Hopping方法G₀ → G₁ → G₂ → G₃ → G₄ → G₅其中G₀ 是原始安全游戏。每一步只修改游戏的一部分。作者通过数学方法控制这次修改对攻击者成功概率的影响。最终的 G₅ 可以用来构造针对底层数学困难问题的归约算法。需要特别注意游戏跳转并不是把原始 Falcon 逐步修改成 Falcon。Falcon 是论文提出的算法改进而 G₀G₅ 是作者为了证明 CoreFalcon 安全性而构造的数学游戏。理解这一点是阅读两个定理证明的基础。1.1 为什么证明 G₅ 的安全性就能证明 CoreFalcon 的安全性刚开始阅读 Game Hopping 时我曾经有一个疑问既然 G₀G₅ 并不是将原始 Falcon 逐步修改为 Falcon那么为什么证明最后的 G₅ 与 R-ISIS 的困难性有关就能够证明 CoreFalcon 的安全性后来我才意识到游戏跳转证明的关键不在于修改算法本身而在于建立不同安全游戏之间的成功概率关系。首先G₀ 就是 CoreFalcon 的真实 UF-CMA 安全实验。因此攻击者在 G₀ 中的成功概率按照定义就是其攻击 CoreFalcon 普通不可伪造性的优势。作者真正需要证明的是攻击者在 G₀ 中成功的概率足够小。但直接分析 G₀ 比较困难因为真实签名模拟涉及私钥陷门而最终求解 R-ISIS 的归约算法并不知道私钥。因此作者构造了 G₁G₅逐步改变签名和哈希的模拟方式。每次游戏发生变化都需要证明攻击者成功概率之间的数学关系。例如先考虑一个简化的游戏跳转Pr[G₀ 成功] ≤ Pr[G₁ 成功] ε其中 ε 表示这一步修改可能引入的概率损失。如果能够证明 ε 非常小那么即使两个游戏不完全相同我们仍然能够利用 G₁ 的成功概率控制 G₀。继续进行类似分析就可以将最初游戏的成功概率与最终游戏联系起来。但这里有一个很重要的问题假设已经证明 G₅ 中的成功概率非常小却没有证明 G₀ 和 G₅ 之间的概率关系那么能够证明 CoreFalcon 安全吗答案是不能。因为我们不知道中间的游戏修改造成了多大的安全损失。即使 G₅ 中成功伪造的概率极低G₀ 中的攻击成功概率仍然可能很高。仅凭 G₅ 的安全性不能推出 G₀ 的安全性。这就是为什么每一次游戏跳转都必须附带严格的数学论证。在本文中作者分别使用二项分布控制采样次数限制带来的失败概率。并集界控制随机盐碰撞概率。Rényi 散度控制哈希目标和原像采样的分布差异。条件分布分析与相关引理控制多次模拟过程中的概率损失。需要注意这些损失并不全部以简单加法形式出现。例如Rényi 散度引入的成功概率关系还包含指数变换。最终作者通过 Claim 15将 G₀ 中的成功概率与 G₅ 联系起来。而 Claim 6 进一步证明如果攻击者能够在 G₅ 中成功伪造签名就可以利用它解决相应的多目标 R-ISIS 问题。因此整条安全归约的逻辑是G₀ 是真实 CoreFalcon 安全实验 → 每次游戏跳转都有可证明的概率关系 → G₅ 可以用于构造 R-ISIS 归约 → 利用 R-ISIS 的困难性与各项归约损失最终控制 G₀ 的攻击成功概率。现在我终于理解了游戏跳转并不是在证明 G₁G₅ 是五个安全的新算法而是通过一系列数学上可控制的辅助实验完成对最初真实算法的安全证明。游戏跳转真正建立的是一座数学桥梁一端连接真实密码方案的安全性另一端连接底层数学困难问题。每一步 Claim 都在保证这座桥梁是可靠的。二、Theorem 1普通不可伪造性的完整证明路线论文 Theorem 1 研究的是 CoreFalcon 的普通不可伪造性UF-CMA。它的核心目标是证明如果攻击者能够为一条此前没有请求过签名的消息构造有效签名那么就可以利用该攻击者解决相应的多目标 R-ISIS 问题。对于 Falcon需要寻找满足以下关系的短原像s₁ h·s₂ c (mod q)同时要求||(s₁,s₂)||₂ ≤ β其中h 是公钥c 是哈希目标β 是原像长度上界。作者在 Appendix C 中通过 Claim 16逐步构造了这一安全归约。2.1 Claim 1限制采样次数对应游戏G₀ → G₁2.1.1 为什么需要限制采样次数Falcon 使用重复采样机制。如果采样得到的短原像不满足长度要求就继续采样直到得到合格结果。例如第一次采样向量过长失败。第二次采样向量过长失败。第三次采样向量长度合格成功。但是数学证明不能直接忽略连续失败的可能性。因此作者在 G₁ 中引入参数 Cs表示签名模拟过程中允许的最大总采样尝试次数。如果采样总次数超过 Cs游戏就会终止。注意这里的 Cs 是回答所有签名查询时允许的总尝试次数而不是每条消息分别允许 Cs 次。2.1.2 为什么需要二项分布假设最多采样 Cs 次。每次采样成功概率为 p。攻击者需要 Qs 次签名查询。令 X 表示固定采样次数内成功的次数。在简化的独立同分布模型中可以写作X ~ Binomial(Cs, p)二项分布的概率公式是P(Xi) C(Cs,i) ××其中C(Cs,i)是组合数。表示 i 次成功对应的概率因子。表示剩余采样失败对应的概率因子。例如最多采样三次要求恰好成功两次。可能的情况是成功、成功、失败。成功、失败、成功。失败、成功、成功。因此C(3,2) 3如果每次成功概率为 0.5那么P(X2) 3 × 0.5² × 0.5 0.375也就是 37.5%。对于实际证明作者使用最小单次成功概率下界进一步给出采样失败事件的概率上界。论文 Claim 1 使用的是P(X ≤ Qs)论文 Claim 1 使用的是但模拟器真正因为合格原像数量不足而失败的事件是。显然因此这是一个保守界因为实际无法完成全部签名查询的事件对应成功次数不足 Qs。2.1.3 我的理解Claim 1 的作用是通过二项分布控制模拟器因采样次数耗尽而终止的风险。Cs 越大允许的采样次数越多采样失败风险通常越小。但 Cs 也不能无限增大因为后面的 Rényi 散度损失可能随之增加。这也是论文需要优化 Cs 的原因。2.2 Claim 2随机盐碰撞与并集界对应游戏G₁ → G₂2.2.1 Falcon 中哈希与签名的关系在理解 Claim 2 之前需要先区分两个容易混淆的符号h小写Falcon 的公钥多项式所有人都可以获得。H大写哈希函数在安全证明中被建模为随机预言机。Falcon 签名时首先生成随机盐 r再根据公钥 h、随机盐 r 和消息 m 计算哈希目标随后签名算法利用私钥陷门寻找满足以下关系的短原像如果原像的长度不满足要求Falcon 就会重新生成随机盐并再次尝试成功后输出签名。因此哈希负责生成数学目标签名算法负责寻找该目标的合格短原像。需要注意一次签名可能经历多次采样每次尝试都需要计算新的哈希目标。这也解释了为什么签名查询次数、采样次数和哈希查询次数不能直接画等号。2.2.2 区分 QH、Qs 和 Cs理解签名过程之后再来看三个容易混淆的参数。参数含义统计对象QH攻击者最多进行的哈希查询次数攻击者直接查询 HQs攻击者最多请求的签名次数攻击者调用 SgnCs签名模拟器允许的总采样尝试次数Sgn 内部调用 PreSmp例如假设攻击者先主动查询随机预言机 100 次然后请求两份签名。签名过程中第一份签名采样 3 次才成功。第二份签名采样 2 次才成功。那么攻击者主动进行的哈希查询为 100 次。攻击者请求的签名数量为 2 次。签名预言机内部实际进行了 5 次原像采样。因此一次签名查询不一定只需要一次哈希计算和一次原像采样。这里尤其需要区分QH 统计攻击者主动向随机预言机发起的查询而签名预言机在生成签名过程中调用哈希函数不直接计入攻击者的 QH。不过在随机预言机的模拟中签名算法内部产生的哈希记录同样需要保存因为相同的哈希输入必须返回相同的输出。2.2.3 为什么 Claim 2 的公式包含 Cs QH现在回到 Claim 2。在 Falcon 的签名过程中每次重新采样都会生成新的随机盐 r然后计算新的哈希目标但是如果新生成的哈希输入此前已经出现模拟器就不能随意为其设置新的哈希结果。因此需要控制发生哈希输入冲突的概率。在论文 Figure 7 的模拟中攻击者最多进行 QH 次哈希查询。签名预言机最多进行 Cs 次内部采样尝试。每次内部尝试至多产生一条新的哈希记录。因此哈希记录表中最多可能出现条记录。由于随机盐长度为 k每次随机生成的盐共有种可能取值。在保守估计下一次内部哈希查询与已有记录发生冲突的概率不超过而签名模拟器最多进行 Cs 次这样的尝试因此根据并集界这个公式可以分成三个部分理解分子中的 QH Cs表示已有哈希记录数量的保守上界。外面的 Cs表示需要考虑的内部哈希尝试次数上限。分母中的表示随机盐的可能取值总数。Claim 2 利用并集界分析哈希输入冲突概率。公式外面的表示最多需要考虑多少次内部哈希尝试括号中的表示每次尝试时可能与新哈希输入发生冲突的已有记录数量的保守上界。将单次冲突概率上界乘以最大尝试次数即得到整个签名模拟过程中发生至少一次冲突的概率上界。至此我才真正理解 Claim 2 的数学意义。作者不是在证明随机盐永远不会重复而是在证明即使签名模拟过程中可能出现哈希输入冲突其发生概率仍然能够通过随机盐长度、哈希查询次数和采样次数进行严格控制。这也解释了为什么 Claim 2 中会同时出现 QH 和 Cs虽然两者统计的是不同操作但这些操作都可能影响随机预言机模拟时需要维护的哈希记录数量。2.2.4 为什么随机盐碰撞会影响证明Falcon 中的哈希目标由以下关系给出c H(h,r,m)其中h公钥。r随机盐。m消息。随机预言机必须遵守一个基本规则相同输入必须返回相同输出。假设攻击者之前已经查询H(h,001,m) 7如果模拟器再次生成盐值 001就不能随意把同一个输入的结果重新设置为 12。否则随机预言机的一致性就被破坏了。因此作者在 G₂ 中增加了一条规则如果签名模拟过程中需要设置的哈希输入已经存在就终止游戏。2.3 Claim 3哈希目标的概率分布替换对应游戏G₂ → G₃这是我在第一轮精读中花费时间最多的一部分也是 Theorem 1 中最值得深入研究的证明步骤之一。在 G₂ 中随机预言机返回均匀随机的哈希目标 c。但在 G₃ 中作者修改为首先从高斯分布采样两个向量s₁, s₂ ← D(R,s)然后计算c s₁ h·s₂ (mod q)这样生成哈希目标的好处是模拟器先拥有合法原像再通过它构造哈希目标因此不需要私钥陷门。但问题是这样生成的 c 未必严格服从均匀分布。所以作者需要利用 Rényi 散度控制 G₂ 和 G₃ 的分布差异。2.3.1 什么是 ru作者定义P环 Rq 上的均匀分布。Qh使用固定公钥 h由高斯短向量计算得到的哈希目标分布。并利用 Rényi 散度衡量两者之间的差异。将所有可能公钥对应的散度取最大值后得到参数 ru。在论文采用的非对数 Rényi 散度定义下两个分布完全相同时散度等于 1。因此ru 越接近 1通常意味着两种分布越接近。2.3.2 为什么要定义 P̄ 和 Q̄作者没有直接分析完整的安全游戏而是先定义两个底层联合分布。P̄首先生成密钥然后依次生成均匀随机的哈希目标c₁,c₂,...,cQQ̄首先生成密钥然后每次通过独立高斯采样计算ci s₁ h·s₂ (mod q)两个分布的关键区别就是哈希目标的生成方式。作者随后使用 Lemma 15也就是数据处理不等式(G₂ || G₃) ≤(P̄ || Q̄)它的直观意义是如果对两个底层随机分布进行相同的后续处理那么可以用底层分布之间的散度控制处理后的游戏分布之间的散度。这一步将复杂的游戏比较转化成了概率分布比较。2.3.3 为什么还需要条件分布论文定义c₀ (B,h)其中 B 是陷门信息h 是公钥。之后才是哈希目标c₁,c₂,...,cQ这里有一个容易混淆的地方每一次生成哈希目标时高斯向量都是独立采样的但所有哈希目标都使用同一个公钥 h。例如c₁ s₁,₁ h·s₂,₁c₂ s₁,₂ h·s₂,₂两次高斯采样相互独立。因此在已经固定公钥 h 的条件下c₂ 的分布不再受到 c₁ 具体取值的影响。但是如果公钥 h 发生变化c₂ 的分布可能发生变化。所以作者使用条件分布来分析在已知公钥以及之前哈希目标的情况下下一个哈希目标服从什么分布进一步地由于不同公钥可能对应不同的散度作者对所有允许的公钥取最大值获得统一上界。2.3.4 Lemma 16多次采样为什么产生指数假设每次生成哈希目标的条件分布散度都不超过 ru。如果只生成一次散度上界是 ru。如果连续生成 Q 次Lemma 16 可以帮助作者得到(P̄ || Q̄) ≤例如ru 1.02如果生成四个哈希目标那么整个序列的散度上界可以表示为这说明单次分布偏差虽然很小但多次操作可能使最终的散度上界明显增大。由于签名模拟过程中的内部哈希查询次数受到 Cs 限制作者最终使用控制这一部分损失。2.3.5 Lemma 14怎样将散度转化为成功概率经过前面的分析作者得到了两个游戏之间的散度界。但是密码学安全证明最终关心的是攻击者成功概率。因此还需要使用 Lemma 14将散度界转化为事件概率之间的关系。记P₂攻击者在 G₂ 中的成功概率。P₃攻击者在 G₃ 中的成功概率。那么 Claim 3 的结果可以写成P₂ ≤ (ru^Cs × P₃)^((au-1)/au)其中 au 是 Rényi 散度阶数。假设 au2并暂时令散度因子为 1。那么P₂ ≤ sqrt(P₃)如果 P₃0.01则只能得到P₂ ≤ 0.1注意这不意味着真实成功概率增加了十倍。它只是说明经过这一步安全归约我们得到的概率上界可能比原来的成功概率宽松。这就是安全归约损失。2.3.6 Claim 3 的完整证明结构现在我们终于能把整个 Claim 3 串起来步骤工具作用1定义 P̄、Q̄构造底层概率分布2Lemma 15利用数据处理不等式控制游戏散度3条件分布分析处理多次采样与固定公钥之间的关系4Lemma 16组合多次采样产生的散度界5Lemma 14将散度界转换为成功概率界这是我阅读 Claim 3 后最大的收获论文中的几个引理不是彼此孤立的而是在逐步完成同一项安全归约任务。2.4 Claim 4实际原像采样器与理想高斯分布对应游戏G₃ → G₄在 G₃ 中签名模拟器使用实际原像采样器PreSmp(B,s,(c,0))在 G₄ 中作者将其替换为对应格陪集上的理想离散高斯分布。这里的理想分布仍然限定在满足目标 c 的原像集合上。也就是说生成的向量仍然必须满足s₁ h·s₂ c (mod q)否则就不是合法原像。为什么使用 rp与 Claim 3 不同Claim 4 比较的是实际 PreSmp 的输出分布。理想格陪集高斯分布。因此这一步使用 rp而不是 ru。Claim 4 的成功概率界可以表示为P₃ ≤ (rp^Cs × P₄)^((ap-1)/ap)其中 ap 是相应的 Rényi 阶数。这与 Claim 3 使用的数学方法类似。事实上论文也明确指出Claim 4 可以按照 G₃ 对应的证明方法得到。所以 Claim 3 和 Claim 4 的区别可以总结为Claim 3哈希目标的分布是否足够均匀Claim 4原像采样器的输出是否足够接近理想高斯分布2.5 Claim 5为什么两个游戏的分布完全相同对应游戏G₄ → G₅Claim 5 与前面的证明不同。Claim 3 和 Claim 4 都在控制概率分布差异而 Claim 5 直接得到Pr[G₄ 成功] Pr[G₅ 成功]为什么这次能够得到等式G₄ 的做法模拟器已经通过高斯采样构造哈希目标 c。当它需要生成签名时再从目标 c 对应的理想格陪集高斯分布中重新采样原像。G₅ 的做法模拟器不再重新采样而是直接使用之前构造哈希目标 c 时的那组向量。因为这组向量本来就满足s₁ h·s₂ c (mod q)为什么两个游戏等价因为在已经知道哈希目标为 c 的条件下原来采样的高斯向量服从相应的条件分布。而这个条件分布正是 G₄ 中使用的理想格陪集高斯分布。所以G₄ 是重新从条件分布中采样。G₅ 是使用之前采样、且已知满足该条件的向量。两种方法得到的相关分布完全相同。因此Claim 5 不会引入新的 Rényi 散度损失。2.6 Claim 6将签名伪造归约到 R-ISIS对应游戏G₅ → R-ISIS经过前面的修改模拟器已经能够在没有私钥陷门的情况下回答签名查询。现在终于可以完成最终归约。2.6.1 归约算法拿到了什么假设归约算法 B 收到了h, ĉ₁, ĉ₂, ..., ĉt其中 h 是公钥ĉj 是 R-ISIS 挑战目标。B 的任务是找到其中任意一个目标对应的合格短原像。2.6.2 怎样嵌入挑战目标B 负责模拟攻击者使用的随机预言机。当攻击者对新的哈希输入进行查询时B 将对应的 R-ISIS 目标作为哈希结果返回。例如H(h,r₁,m₁) ĉ₁H(h,r₂,m₂) ĉ₂依此类推。因为挑战目标具有所需的均匀分布性质因此能够用于模拟普通随机预言机的输出。对于攻击者的签名查询B 则使用 G₅ 中已经建立的无陷门签名模拟方法。2.6.3 怎样从伪造签名中得到短原像假设攻击者提交有效伪造签名σ* (r*,s₂*)B 首先计算c* H(h,r*,m*)然后恢复s₁* c* - h·s₂* (mod q)于是得到完整原像(s₁*,s₂*)如果这个目标恰好对应某个挑战目标 ĉj就有s₁* h·s₂* ĉj (mod q)而有效签名的验证条件还保证原像长度满足要求。因此B 输出(j,s₁*,s₂*)便可以解决 R-ISIS。2.6.4 为什么是 (QH1)-R-ISISQH 表示攻击者最多进行的哈希查询次数。但是当攻击者最终提交伪造签名时它可能尚未查询过该签名对应的哈希输入。归约算法为了验证签名可能需要额外进行一次哈希查询。因此作者需要准备QH 1个挑战目标。这里还有一个重要优点多目标 R-ISIS 只要求解决其中任意一个目标因此 B 不需要提前猜测攻击者最终会针对哪个目标伪造。到这里Theorem 1 的主要证明结构就完整了。2.7 Theorem 1完整安全界的结构将 Claim 16 组合后作者得到 CoreFalcon 的 UF-CMA 安全界。为了便于理解先定义 (×)^((ap-1)/ap)再定义 (×)^((au-1)/au)那么安全界可以整理为≤ Cs(CsQH)/其中是相应多目标困难问题的求解成功概率。是采样次数限制产生的二项分布概率上界。最后一项是随机盐相关的冲突概率上界。这个公式告诉我们签名方案最终能够得到多强的安全保证不仅取决于底层数学问题的困难性还取决于安全归约过程中产生的全部概率损失。三、Theorem 2强不可伪造性与 R-SPISIS 归约Theorem 2 研究 CoreFalcon 的强不可伪造性SUF-CMA。与普通不可伪造性相比强不可伪造性还要防止攻击者为已经签名的消息构造另一份不同的有效签名。3.1 为什么需要 R-SPISIS假设我们已经知道目标 c 的一个合法短原像u h·v c (mod q)普通 R-ISIS 只要求找到目标 c 的一个短原像。但在这里一个合法原像已经给出了。因此要刻画已知一个原像后寻找另一个原像的困难性就需要更合适的问题定义。R-SPISIS 要求寻找s₁ h·s₂ c (mod q)并满足(s₁,s₂) ≠ (u,v)以及相应的范数上界。也就是说攻击者需要寻找同一目标的第二个不同短原像。因此作者将强不可伪造攻击区分为两种情况普通的新消息伪造使用 Theorem 1 的 UF-CMA 安全界。与既有签名相关的第二原像式伪造通过 R-SPISIS 进行归约。这解释了为什么 Theorem 2 的安全界同时包含 UF-CMA 和 R-SPISIS 两部分。3.2 Claim 7处理最终签名对应的哈希查询对应游戏G₁ → G₂Claim 7 研究签名模拟过程中哈希输入的处理方式。它与 Theorem 1 的 Claim 2 有联系但又不完全一样。在这里作者重点考虑的是签名预言机最终实际输出的签名对应哪一次哈希查询例如某条消息连续采样三次第一次失败。第二次失败。第三次成功并输出签名。在这一步修改中作者只对最终输出签名对应的哈希位置进行特殊处理而不是把所有失败重试的哈希位置都作为最终签名对应的位置。为什么因为 Theorem 2 需要研究攻击者是否能够围绕已经提供的合法签名构造第二原像。如果最终签名对应的哈希输入之前已经被查询过那么重新编程可能违反随机预言机一致性。因此作者必须控制这一修改带来的概率差异。需要注意Claim 7 的完整证明并没有在本文重新展开而是引用了已有文献 [BBD23, Thm. 3]。我目前理解了这一步的目的但还没有独立复现其引用文献中的全部概率分析。3.3 Claim 8再次限制采样次数对应游戏G₂ → G₃Claim 8 与 Theorem 1 的 Claim 1 基本相同。作者重新设置采样总次数上限 Cs。如果签名模拟过程中采样次数超过 Cs游戏就会终止。这可能导致某些原本可以完成的签名提前失败。因此作者再次使用二项分布控制由采样次数限制产生的概率损失。这里没有引入新的核心数学工具而是复用了 Claim 1 的分析思路。3.4 Claim 9用理想高斯替换实际原像采样器对应游戏G₃ → G₄Claim 9 与 Theorem 1 的 Claim 4 类似。在 G₃ 中模拟器使用实际原像采样器 PreSmp。在 G₄ 中作者将它替换为对应格陪集上的理想离散高斯分布。由于两种采样分布不一定完全相同因此需要使用 Rényi 散度控制差异。这里使用的是 rp。相应的成功概率上界形式为P₃ ≤ (× P₄)^((ap-1)/ap)论文说明这一步可以按照 Theorem 1 的证明方法完成。需要注意Theorem 2 的第二原像归约部分不需要再次进行 Claim 3 中的哈希目标均匀性替换。因此这条归约路线主要使用 rp而不额外引入 ru 的分布替换。不过完整的 Theorem 2 仍包含 Theorem 1 的 UF-CMA 安全项所以不能说整个 SUF-CMA 分析完全不涉及 ru。3.5 Claim 10撤销采样次数限制对应游戏G₄ → G₅这一步非常特别。论文写道Game G5. This game reverts the changes made in G3.意思是G₅ 撤销了之前在 G₃ 中增加的采样次数限制。假设最多允许采样三次而模拟器需要第四次采样才能成功。那么G₄第三次之后就会终止。G₅可以继续尝试第四次采样。因此两种游戏的运行行为不一定完全相同。作者必须再次控制这一变化带来的概率差异。这一步仍然使用二项分布的分析方法。需要特别注意Claim 10 取消的是采样次数限制而不是撤销 Claim 9 中的理想高斯分布替换。因此Theorem 2 的证明中会出现两次与采样次数限制有关的二项分布误差项。3.6 Claim 11最终归约到 R-SPISIS对应游戏G₅ → R-SPISIS这是 Theorem 2 的最终证明步骤。3.6.1 归约算法已经知道一个原像与 Claim 6 不同Claim 11 中的归约算法 B 一开始就收到(c₁,u₁,v₁), (c₂,u₂,v₂), ...其中每个目标 cj 都有一个已知短原像uj h·vj cj (mod q)因此B 可以直接利用这些已知原像构造合法签名。它不需要私钥陷门。3.6.2 怎样利用攻击者的伪造签名假设攻击者最终提交σ* (r*,s₂*)B 计算c* H(h,r*,m*)随后恢复s₁* c* - h·s₂* (mod q)于是得到完整原像(s₁*,s₂*)然后B 检查是否存在一个目标 cj满足c* cj同时(s₁*,s₂*) ≠ (uj,vj)如果攻击者成功伪造并且前面游戏中的相关条件都得到满足作者证明这样的编号能够被找到。最终 B 输出(j,s₁*,s₂*)从而得到 R-SPISIS 的一个解。这就是 Figure 10 第 78 行的核心作用。3.6.3 为什么必须检查原像不同因为 R-SPISIS 不只是要求找到一个合法短原像。挑战中已经提供了一个短原像。如果 B 最终得到的向量与已知向量相同那么它并没有解决第二原像问题。只有找到同一目标的另一组不同短原像才能完成 R-SPISIS 归约。3.7 Theorem 2完整安全界的逻辑现在我们可以将 Theorem 2 的证明概括为SUF-CMA 攻击成功的概率受到 UF-CMA 安全界、R-SPISIS 困难性以及各项游戏转换误差的共同控制。其中UF-CMA 项控制普通伪造情况。R-SPISIS 项控制第二原像式伪造。其他概率项控制采样失败、哈希输入冲突等游戏转换风险。rp 控制第二原像归约过程中实际采样与理想采样的分布差异。因此Theorem 2 并不是仅仅将 Theorem 1 的结论换了一个安全定义而是针对更强的攻击模型构造了一条额外的数学归约路线。四、Theorem 1 和 Theorem 2 的证明对比完成两个定理的精读之后我们可以把它们放在一起比较。对比项目Theorem 1Theorem 2安全定义UF-CMASUF-CMA核心困难问题R-ISISR-SPISIS结合 UF-CMA归约目标找到一个合格短原像找到与已知原像不同的第二短原像采样失败分析Claim 1Claim 8、Claim 10哈希处理Claim 2、Claim 3Claim 7分布替换ru 与 rp第二原像部分主要使用 rp最终归约Claim 6Claim 11通过这次对比我发现作者的证明具有很强的复用性。例如Claim 8 复用了 Claim 1 的二项分布思想。Claim 9 复用了 Claim 4 的 Rényi 散度分析。Claim 11 在整体归约框架上与 Claim 6 有相似之处但解决的是不同数学问题。这说明密码学中的不同安全性质往往可以通过重新组织安全游戏、复用已有概率工具并引入适当的新困难性假设来证明。此外论文采用第二原像相关的证明路线还避免了传统碰撞式归约中将范数上界从 β 放宽到 2β 的问题。五、Table 3安全归约中的具体 bit 损失完成两个定理的安全证明后作者在 Section 5 中进行具体参数分析。首先需要估计底层 R-ISIS 和 R-SPISIS 问题的困难程度。论文假设这些问题的困难性与相应随机 SIS 实例相当并使用格困难性估计工具计算攻击成本。然后再考虑安全归约产生的各种损失。5.1 Falcon-512为什么是 119 bit 和 113 bitTable 3 给出两组不同的签名查询上限最大签名查询次数R-ISIS 困难性估计rp 损失ru 损失最终安全性120 bit0.5 bit0.5 bit119 bit120 bit3.5 bit3.5 bit113 bit当 Qs时120 - 3.5 - 3.5 113 bit这与我们前面学过的 Claim 3、Claim 4 直接相关。为什么查询次数越多最终安全性估计越低因为签名查询次数增加后通常需要更大的 Cs。而证明中存在以及这两个累积散度因子。因此更多查询可能使 Rényi 散度造成的安全归约损失增加。需要注意最终安全界变弱不代表 R-ISIS 数学问题本身突然变得更容易。它反映的是在不同查询上限下安全归约得到的具体界有所不同。5.2 Falcon-1024为什么 270 bit 最终变成 256 bitFalcon-1024 的参数如下项目安全位数R-ISIS 困难性估计278 bitrp 对应损失4 bitru 对应损失4 bit计算性部分安全界270 bit最终安全性估计256 bit首先278 - 4 - 4 270 bit但为什么最终结果不是 270 bit因为完整安全界除了计算性困难问题之外还包含统计性误差项。例如采样次数不足造成的失败概率。随机盐及哈希输入冲突的概率。即使计算性攻击成功概率极低也不能忽略这些统计性误差。论文 Section 5.4 明确指出Falcon-1024 的计算性部分可达到 270 bit但整体安全级别受到统计性项限制最终为 256 bit。这里不是简单地从 270 中再减去 14而是完整的安全界还受到其他概率项的限制。5.3 为什么还要优化 Cs、au 和 ap通过前面的分析我们已经知道Cs 越大采样失败概率通常越小。但是可能增大。可能增大。随机盐碰撞概率上界也可能增大。因此Cs 需要进行优化。与此同时Rényi 阶数 au、ap 也会影响散度值和概率转换指数。所以作者还需要选择合适的 Rényi 阶数尽量减少安全损失。这就是 Section 5.2 和 Section 5.3 研究的核心问题。5.4 从 Table 3 得到的认识以前我容易认为如果底层数学问题具有很高的困难性那么数字签名方案自然就具有同样高的安全位数。现在我知道这种理解并不严谨。正确的分析过程应该是底层困难问题的计算成本估计↓数学安全归约↓控制采样失败与哈希碰撞风险↓控制 Rényi 散度造成的安全损失↓综合得到最终安全界这也是整篇论文最值得学习的研究方法之一。六、这次精读中最容易混淆的五个问题6.1 R-ISIS 和 R-SPISIS 有什么区别R-ISIS 要求找到某个目标对应的一个合格短原像。R-SPISIS 则在已经知道一个原像的情况下要求找到同一目标对应的另一个不同短原像。区别在于是否已知一个原像以及最终找到的原像是否必须与它不同。6.2 ru 和 rp 有什么区别ru 衡量构造出的哈希目标分布与均匀分布之间的差异。rp 衡量实际原像采样器与理想高斯分布之间的差异。可以简单记忆ru哈希目标均匀不均匀rp原像采样是否接近理想高斯6.3 为什么 Rényi 散度越接近 1 越好论文采用的非对数 Rényi 散度在两个分布完全相同时等于 1。因此散度越接近 1通常越有利于得到较紧的概率界。6.4 为什么 Cs 不能无限增大因为 Cs 增大虽然可以降低采样失败风险但同时也可能增大Rényi 散度累积损失。随机盐碰撞概率上界。因此必须权衡不同因素而不能只关注某一个概率项。6.5 为什么最终安全位数不等于底层困难性估计因为数学安全归约可能产生额外损失。这些损失包括Rényi 散度相关损失。采样失败概率。随机盐碰撞风险。其他安全游戏转换中的统计性误差。因此最终安全位数必须根据完整安全界计算。七、第一轮重点精读总结与反思经过这次阅读我对密码学安全证明的理解比之前具体了很多。一开始面对 Theorem 1 中复杂的概率不等式我几乎不知道应该从哪里入手。特别是 Claim 3其中同时出现底层联合分布。条件概率分布。数据处理不等式。Rényi 散度的多次采样界。成功概率之间的归约关系。这些概念单独学习时似乎并不困难但要理解它们如何共同构成一个证明仍然需要花费很多时间。后来我开始尝试按照三个问题阅读每一个 Claim第一作者在这一步修改了什么第二为什么这次修改可能改变攻击者的成功概率第三作者利用什么数学工具控制这种变化这种阅读方法帮助我逐渐理解了游戏跳转证明的整体结构。7.1 目前已经掌握的内容经过第一轮重点精读我现在基本能够解释Theorem 1 和 Theorem 2 分别证明什么。为什么安全证明需要游戏跳转。Claim 111 的主要目的。Lemma 1416 如何共同用于 Claim 3。ru、rp、Cs 如何影响最终安全界。为什么 Table 3 的安全性估计会低于底层困难问题的初始估计。尤其是两个定理的最终归约我现在已经可以用自己的语言进行解释。7.2 仍然需要进一步研究的问题需要明确的是理解证明主线不等于已经独立完成全部数学推导。接下来仍然有几个值得深入研究的部分Lemma 1416 的完整数学推导尤其是 Rényi 散度的条件分布分析。Claim 7 引用的外部证明以及更精细的随机预言机编程技术。Section 5 中 Cs、au、ap 的具体优化过程。FFO Sampler 的递归分布证明。Table 3 中各项具体参数的独立复现。这些问题可以作为第二轮精读的重点。7.3 对密码学科研方法的新认识这次阅读让我意识到数学证明型密码学论文的难点不仅在于单个引理有多复杂更在于如何把多个引理组织成一条完整的安全归约链。例如作者为了证明普通不可伪造性需要依次处理采样次数限制、哈希输入冲突、哈希目标均匀性、原像采样分布、无陷门签名模拟以及最终的 R-ISIS 归约。每一步都需要相应的数学工具。而在强不可伪造性证明中作者又通过分类攻击情形引入 R-SPISIS并复用前面建立的证明技术。这种从困难问题出发构造安全游戏再逐项控制概率误差的研究方法是我希望在后续密码学学习中继续掌握的内容。结语真正重要的是理解每一步为什么成立在完成《A Closer Look at Falcon》的第一轮重点精读之后我认为这篇论文最重要的启发是一个密码方案的安全性并不能简单地由底层数学问题的困难程度直接推出。要建立严格的安全保证还需要研究真实算法的采样机制、概率分布、随机预言机模拟以及整个归约过程中产生的安全损失。Falcon 的安全证明展示了如何利用游戏跳转、Rényi 散度和适当的困难性假设将真实数字签名方案与抽象数学问题联系起来。而对我来说这次最大的进步不是记住了多少个 Claim而是逐渐开始能够理解作者为什么在这里修改游戏为什么这个引理能够应用为什么最终可以推出那个安全界这也是我从理解密码学概念逐步走向独立阅读密码学证明的一个重要阶段。参考文献与阅读位置A Closer Look at FalconSection 4.2Theorem 1、Theorem 2。同论文 Appendix CClaim 16Figure 7、Figure 8。同论文 Appendix DClaim 711Figure 9、Figure 10。同论文 Section 5.15.4Table 3。Barbosa et al.Fixing and Mechanizing the Security Proof of Fiat-Shamir with Aborts and DilithiumCRYPTO 2023。论文 Claim 7 引用了其中的相关证明。阅读说明本文为第一轮重点精读的学习笔记主要整理安全归约的逻辑、游戏跳转的目的和关键概率界。尚未独立复现的引理和外部证明应以论文原文为准。
阅读完成 · 觉得有帮助？
