企业官网建设流程全解析

研究方向：后量子密码学、格密码、数字签名
阅读论文：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 1～11 进行了系统梳理，并进一步结合 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 1～5，将 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 1～6，逐步构造了这一安全归约。

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(X=i) = C(Cs,i) ××

其中：

• C(Cs,i)是组合数。

• 表示 i 次成功对应的概率因子。

• 表示剩余采样失败对应的概率因子。

例如，最多采样三次，要求恰好成功两次。

可能的情况是：

1. 成功、成功、失败。

2. 成功、失败、成功。

3. 失败、成功、成功。

因此：

C(3,2) = 3

如果每次成功概率为 0.5，那么：

P(X=2) = 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

理解签名过程之后，再来看三个容易混淆的参数。

例如，假设攻击者先主动查询随机预言机 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₂,...,cQ

Q̄：

首先生成密钥，然后每次通过独立高斯采样计算：

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 散度阶数。

假设 au=2，并暂时令散度因子为 1。

那么：

P₂ ≤ sqrt(P₃)

如果 P₃=0.01，则只能得到：

P₂ ≤ 0.1

注意，这不意味着真实成功概率增加了十倍。

它只是说明：

经过这一步安全归约，我们得到的概率上界可能比原来的成功概率宽松。

这就是安全归约损失。

2.3.6 Claim 3 的完整证明结构

现在我们终于能把整个 Claim 3 串起来：

这是我阅读 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 为什么是 (QH+1)-R-ISIS？

QH 表示攻击者最多进行的哈希查询次数。

但是，当攻击者最终提交伪造签名时，它可能尚未查询过该签名对应的哈希输入。

归约算法为了验证签名，可能需要额外进行一次哈希查询。

因此，作者需要准备：

QH + 1

个挑战目标。

这里还有一个重要优点：

多目标 R-ISIS 只要求解决其中任意一个目标，因此 B 不需要提前猜测攻击者最终会针对哪个目标伪造。

到这里，Theorem 1 的主要证明结构就完整了。

2.7 Theorem 1：完整安全界的结构

将 Claim 1～6 组合后，作者得到 CoreFalcon+ 的 UF-CMA 安全界。

为了便于理解，先定义：

= (×)^((ap-1)/ap)

再定义：

= (×)^((au-1)/au)

那么安全界可以整理为：

≤++ Cs(Cs+QH)/

其中：

• 是相应多目标困难问题的求解成功概率。

• 是采样次数限制产生的二项分布概率上界。

• 最后一项是随机盐相关的冲突概率上界。

这个公式告诉我们：

签名方案最终能够得到多强的安全保证，不仅取决于底层数学问题的困难性，还取决于安全归约过程中产生的全部概率损失。

三、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 的完整证明并没有在本文重新展开，而是引用了已有文献 [BBD+23, 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 第 7～8 行的核心作用。

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 的证明对比

完成两个定理的精读之后，我们可以把它们放在一起比较。

通过这次对比，我发现作者的证明具有很强的复用性。

例如：

• 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 bit？

Table 3 给出两组不同的签名查询上限：

最大签名查询次数	R-ISIS 困难性估计	rp 损失	ru 损失	最终安全性
	120 bit	0.5 bit	0.5 bit	119 bit
	120 bit	3.5 bit	3.5 bit	113 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 bit？

Falcon+-1024 的参数如下：

首先：

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 1～11 的主要目的。

• Lemma 14～16 如何共同用于 Claim 3。

• ru、rp、Cs 如何影响最终安全界。

• 为什么 Table 3 的安全性估计会低于底层困难问题的初始估计。

尤其是两个定理的最终归约，我现在已经可以用自己的语言进行解释。

7.2 仍然需要进一步研究的问题

需要明确的是：

理解证明主线，不等于已经独立完成全部数学推导。

接下来仍然有几个值得深入研究的部分：

1. Lemma 14～16 的完整数学推导，尤其是 Rényi 散度的条件分布分析。

2. Claim 7 引用的外部证明，以及更精细的随机预言机编程技术。

3. Section 5 中 Cs、au、ap 的具体优化过程。

4. FFO Sampler 的递归分布证明。

5. Table 3 中各项具体参数的独立复现。

这些问题可以作为第二轮精读的重点。

7.3 对密码学科研方法的新认识

这次阅读让我意识到：

数学证明型密码学论文的难点，不仅在于单个引理有多复杂，更在于如何把多个引理组织成一条完整的安全归约链。

例如，作者为了证明普通不可伪造性，需要依次处理：

采样次数限制、哈希输入冲突、哈希目标均匀性、原像采样分布、无陷门签名模拟，以及最终的 R-ISIS 归约。

每一步都需要相应的数学工具。

而在强不可伪造性证明中，作者又通过分类攻击情形，引入 R-SPISIS，并复用前面建立的证明技术。

这种从困难问题出发，构造安全游戏，再逐项控制概率误差的研究方法，是我希望在后续密码学学习中继续掌握的内容。

结语：真正重要的是理解每一步为什么成立

在完成《A Closer Look at Falcon》的第一轮重点精读之后，我认为这篇论文最重要的启发是：

一个密码方案的安全性，并不能简单地由底层数学问题的困难程度直接推出。

要建立严格的安全保证，还需要研究真实算法的采样机制、概率分布、随机预言机模拟以及整个归约过程中产生的安全损失。

Falcon+ 的安全证明展示了如何利用游戏跳转、Rényi 散度和适当的困难性假设，将真实数字签名方案与抽象数学问题联系起来。

而对我来说，这次最大的进步不是记住了多少个 Claim，而是逐渐开始能够理解：

作者为什么在这里修改游戏？为什么这个引理能够应用？为什么最终可以推出那个安全界？

这也是我从理解密码学概念，逐步走向独立阅读密码学证明的一个重要阶段。

参考文献与阅读位置

1. A Closer Look at Falcon，Section 4.2，Theorem 1、Theorem 2。

2. 同论文 Appendix C，Claim 1～6，Figure 7、Figure 8。

3. 同论文 Appendix D，Claim 7～11，Figure 9、Figure 10。

4. 同论文 Section 5.1～5.4，Table 3。

5. Barbosa et al.，Fixing and Mechanizing the Security Proof of Fiat-Shamir with Aborts and Dilithium，CRYPTO 2023。论文 Claim 7 引用了其中的相关证明。

阅读说明：本文为第一轮重点精读的学习笔记，主要整理安全归约的逻辑、游戏跳转的目的和关键概率界。尚未独立复现的引理和外部证明，应以论文原文为准。