文章总结： 本文介绍了密码学中的抛硬币协议，重点讨论了Blum协议及其安全性证明。文章解释了如何通过承诺方案实现公平的远程抛硬币，分析了协议抵抗恶意对手的能力，并详细展示了如何使用模拟器构造进行安全性证明。文章还探讨了单比特和多比特抛硬币协议的实现方法，以及如何解决选择性中止等安全问题。
综合评分： null
文章分类： 密码学,安全协议,零知识证明,安全证明,安全协议设计
【密码学】抛硬币协议
原创
Litt1eQ
Coder小Q
2025年11月24日 08:30
山东
【密码学】抛硬币协议
接着，上一篇文章，我们来看Alice、Bob和Eve之间，又会发生什么样的问题，这里，我们参考Yehuda Lindell 经典的论文—How To Simulate It – A Tutorial on the Simulation Proof Technique[1]。
再次相聚在咖啡馆
❝
一周后，Bob早早地来到咖啡馆，手里拿着一叠打印出来的笔记，看起来准备充分。
Bob：Alice，Eve，上次你们说要讲抛硬币协议，我这一周可是做了不少功课。
Alice：看来你做足了功课。那我先问你一个问题：你觉得抛硬币最核心的安全要求是什么？
Bob：嗯，应该是公平性吧？就是说，结果应该是真随机的，任何一方都不能控制结果。
Eve：不错。但还有一个更微妙的问题。即使我们无法完全控制结果，我能不能在看到结果对我不利时，就假装”掉线”，让整个协议失败？
Bob：对哦，这就是上次你们说的”选择性中止”问题。那这个问题能解决吗？
Alice：很遗憾，在两方协议中，如果没有诚实多数，我们无法完全阻止选择性中止。这是Cleve在1986年证明的一个不可能性结果[2]。
Bob：那我们还能做什么？
Alice：我们能做到的是可终止安全——恶意方可以在看到自己的输出后选择中止，但除此之外，它无法做任何其他破坏。具体来说：
- 它不能偏置结果（让结果倾向于某个值）
- 它不能学到除了输出以外的任何信息
- 诚实方要么得到正确的输出，要么明确知道协议被中止了
Bob：明白了。那我们怎么设计这样的协议呢？
单比特抛硬币—Blum协议
核心问题
Alice：假设你和Eve要远程抛硬币，决定谁请客吃饭。最朴素的想法是什么？
Bob：嗯，我选一个随机比特 ，你选一个随机比特 ，结果就是 ？
Eve：听起来不错，但有个致命问题：谁先说？
Bob：如果我先说 ，你就可以选择 来控制结果了。
Eve：对。你想让结果是0（你请客），我就选 ；你想让结果是1（我请客），我就选 。先说的人必输。
Bob：那我们同时说呢？
Alice：在密码学模型中，我们没有”同时”这个概念。协议是按轮进行的，每轮只有一方发送消息。
Bob：那怎么办？
承诺方案
Alice：解决方案是使用承诺方案。你还记得承诺方案的两个性质吗？
Bob：记得，隐藏性——看到承诺后猜不出承诺的值；绑定性——承诺后不能改变值。
Alice：非常好。现在看Blum的协议是如何利用这两个性质的：
Blum的单比特抛硬币协议
安全参数：双方都有安全参数 协议流程：
- 选择随机比特 和随机数 ，发送承诺 给
- 收到 后，选择随机比特 ，发送 给
- 收到 后，发送 给 ，并输出
- 收到 后，验证 。如果验证通过，输出 ；否则输出
Bob：嗯嗯，现在我理解了这个协议的流程了，但是，这个协议为什么是公平的呢？
协议的公平性分析
Eve：首先， 不能作弊。当 选择 时，它只看到了承诺 。由于承诺的隐藏性， 无法得知 是什么，所以它选择的 与 是独立的。
Bob：所以 没法根据 来选择 ？
Eve：对。接下来， 也不能作弊。当 看到 后，虽然它知道了 的值，但由于承诺的绑定性，它无法改变之前承诺的 。
Alice：所以， 和 都是在对方不知情的情况下独立选择的，结果 就是均匀分布的。
Bob：这个设计真巧妙。但是，怎么证明它在恶意对手下是安全的呢？
安全性证明—模拟器的构造
Alice：我们需要分别考虑 被腐化和 被腐化两种情况。
被腐化
Bob：如果 是恶意的，模拟器要做什么？
Alice：模拟器 需要：
- 从可信方收到输出比特
- 生成一个与真实执行不可区分的视图
- 使得执行的输出恰好等于
Eve：挑战在于：在真实执行中，输出 是随机的；但在模拟中， 必须让输出等于可信方给定的特定值 。
Alice：接下来，让我们看模拟器是如何工作的：
模拟器 （ 被腐化）
- 发送空输入给可信方，收到输出比特
- 初始化计数器
- 调用对手 ，选择随机 和 ，将 发送给
- 如果 回复 ，则 将 发送给 ，输出 的输出
- 如果 回复 且 ，则 设 ，返回步骤3
- 如果 ，则 输出 fail
Bob：等等，让我理解一下，模拟器需要不断重试，直到 ？
Eve：完全正确。每次迭代中， 选择一个新的随机 ，希望 回复的 恰好满足 。
Bob：但如果 总是故意选择”错误”的 呢？
作弊概率分析
Alice：这就是关键的地方。由于承诺的隐藏性， 看到的 与 的值在计算上是独立的。
Eve：让我们做一个概率分析。 回复的 满足 的概率是多少？
Alice：我们可以展开这个概率：
Bob：这个式子好复杂，能解释一下吗？
Alice：当然。第一行是全概率公式： 和 各占一半概率。第二行的关键是：
其中 是一个可忽略函数。这是由承诺的隐藏性保证的——如果这个差值很大， 就能区分 和 。
Eve：所以，成功的概率接近 ：
Bob：每次成功的概率大约是 ，所以 次全部失败的概率是？
Alice：
这是可忽略的。所以模拟器几乎肯定能在 次内成功。
Bob：太棒了，我理解了模拟器为什么能在多项式时间内完成。但输出分布呢？怎么证明真实和理想的分布相同？
分布的统计规律
Alice：这需要更细致的分析。关键观察是：
在真实执行中： 是均匀分布的。
在理想执行（模拟）中：首先随机选择 ，然后随机选择 ，条件是 。
Eve：定义集合 。这是所有能导致输出 的 对的集合。
Bob：在理想执行中，模拟器均匀地从 中采样？
Alice：对。而且由于隐藏性， 接近 。所以：
每个 在理想执行中出现的概率是 ，这与真实执行中的 统计上接近。
Bob：我大概理解了。那 被腐化的情况呢？
被腐化
Eve：这个情况更有趣，因为我们需要处理选择性中止。
Alice：回想一下，恶意的 可以在看到 后决定是否打开承诺。如果结果对它不利，它可能就”断网”了。
Bob：这不就是上次说的选择性中止攻击吗？
Eve：正是。模拟器必须正确模拟这种行为，而且概率分布要完全匹配。
模拟器 （ 被腐化）
- 发送空输入给可信方，收到输出比特
- 调用 ，收到 发送的承诺
- 分别给 发送 和 ，观察 的回复：
-
发送 给可信方
-
发送 给
-
发送 continue 给可信方
-
发送 给
-
发送 给可信方
-
发送 给
-
发送 continue 给可信方
-
设置 ，将 发送给
-
(a) 如果 对两个 都回复有效的解承诺 ：
-
(b) 如果 对两个 都不回复有效的解承诺：
-
(c) 如果 只对满足 的 回复有效解承诺：
-
(d) 如果 只对满足 的 回复有效解承诺：
- 输出 的输出
Bob：哇，这个模拟器复杂多了。它为什么要给 发送两个不同的 ？
Alice：因为模拟器需要知道 的”策略”——它在什么情况下会中止。通过测试 和 ，模拟器可以完全确定 的行为。
Eve：让我解释每种情况的直觉：
- 情况(a)： 总是诚实地打开承诺。模拟器可以选择 使得结果等于 。
- 情况(b)： 总是中止。诚实方得不到输出。
- 情况(c)： 只有在结果对它有利时才继续。幸运的是， 恰好是它想要的值。
- 情况(d)： 只有在结果对它不利时才继续。不幸的是， 不是它想要的值，所以它会中止。
Bob：情况(c)和(d)看起来很微妙
Alice：确实如此。关键是，模拟器需要确保：
- 如果 会导致输出 ，那就让执行继续，诚实方得到
- 如果 会导致输出 （ 的反），那就中止，因为我们不能让诚实方得到错误的输出
Bob：所以，在情况(d)中，虽然 本来想继续，但因为它想继续的输出是”错误”的，模拟器必须让它中止？
Eve：对。而且这个概率在真实执行和理想执行中是完全相同的——都是 。
分布的分析
Alice：让我们验证情况(c)和(d)的分布。假设 只有在 时才打开承诺（ 是某个固定值）。
在真实执行中：
- 发送随机
- 如果 ， 得到输出
- 如果 ， 输出
在理想执行中：
- 是随机选择的
- 如果 （概率 ）， 发送 ， 得到输出
- 如果 （概率 ）， 发送 ， 输出
Bob：两种情况下， 得到输出或得到 的概率都是 ，而且输出值也相同。分布完全一样。
Alice：正是如此。这完成了 被腐化情况的证明。
多比特抛硬币
Bob：如果我们要抛多个硬币呢？比如抛 个比特？我能想到一个简单的想法是重复 次单比特协议。
Eve：但这需要 轮通信。
Alice：而且更严重的问题是模拟。还记得单比特情况下，模拟器需要重试大约2次吗？
Bob：嗯嗯，我记得。
Alice：如果我们抛 个比特，模拟器需要让 （其中 是可信方给的输出字符串），成功的概率是？
Bob：？这也太多了吧。
Eve：没错。这个方法行不通。
解决方案
Alice：解决方案是使用零知识证明。核心思想是：
- 不再打开承诺
- 直接发送 ，并用零知识证明它确实等于承诺的值
Bob：但这不是一样的吗？
Eve：不一样。在零知识证明中，模拟器可以作弊——它可以证明一个假的陈述。
Alice：让我们看具体协议。但首先，我需要介绍零知识证明功能。
零知识证明的功能
Bob：这是什么意思？
Alice：证明者发送 （陈述和见证），验证者发送 （陈述）。如果两个陈述相同且 是 的有效见证，验证者收到1；否则收到0。
Eve：关键是，在混合模型中，模拟器直接扮演可信方的角色。它可以直接看到证明者发送的 ，也可以直接发送任意输出给验证者。
Bob：所以模拟器不需要运行零知识模拟器或知识提取器？
Alice：对，这就是混合模型的威力。
多比特抛硬币协议
输入：假设要抛 个硬币
混合功能：
- ：证明 是一个有效承诺（）
- ：证明 是对 的承诺（ 满足 ）
协议流程：
- 选择随机 和 ，发送 给
- 发送 给 （证明 是有效承诺）
- 收到 后，发送 给 ，收到验证结果 。如果 ，输出
- 选择随机 ，发送给
- 发送 给 ，并发送 给
- 发送 给 ，收到验证结果 。如果 ，输出 ；否则输出
- 输出
Bob：为什么需要两个零知识证明？第一个证明 是有效承诺，第二个证明 是 承诺的值？
Alice：好问题。第一个证明是为了处理 被腐化的情况——模拟器需要提取 。第二个证明是为了处理 被腐化的情况——模拟器需要”作弊”，发送一个不同于承诺值的 。
Eve：让我更详细地解释：
- 被腐化：模拟器需要知道 承诺的值 ，才能设置 。通过第一个零知识证明， 必须把 明确发送给 ，模拟器可以直接获得。
- 被腐化：模拟器需要让输出等于 。它可以承诺 ，但发送 。在第二个零知识证明中，模拟器直接告诉 “验证通过”，即使 不是承诺的值。
Bob：太巧妙了。模拟器利用了可以”扮演可信方”的能力。
混合模型中的证明
Alice：现在让我们看具体的模拟器构造。先看 被腐化的情况。
模拟器 （ 被腐化）
- 调用 ，收到 和 （发送给 的消息）
- 如果 或 ，发送 ，模拟 中止
- 向可信方发送 ，收到
- 设置 ，发送给
- 收到 和 。如果无效，发送 ；否则发送 continue
Bob：这比单比特的模拟器简单多了，没有重试。
Eve：这就是混合模型的威力。模拟器直接从 发送给 的消息中获得 ，不需要提取。
Alice：而且，这个模拟是完美的——真实和理想分布完全相同。让我解释为什么：
- 第一阶段： 发送 和 ，这在真实和理想执行中完全相同。
- 第二阶段：在真实执行中， 发送随机 ；在理想执行中， 发送 。由于 是随机选择且独立于 ， 也是随机的。
- 第三阶段： 的行为完全由前两阶段决定。如果它发送有效的解承诺， 得到输出 ；否则 输出 。
Bob：那 被腐化呢？
模拟器 （ 被腐化）
- 向可信方发送 ，收到 ，发送 continue
- 选择随机 ，计算
- 调用 ，发送
- 收到 （如果无效则设为 ）
- 设置 ，发送给
- 收到 。如果 ，发送 0 给 ；否则发送 1
- 输出 的输出
Bob：等等， 承诺的是 ，但发送的是 ，这不是在”说谎”吗？
Eve：对。但这正是模拟器能做而真实对手不能做的——它扮演可信方，可以直接告诉 “验证通过”。
Alice：现在的问题是： 能区分承诺 和承诺真实的 吗？
归约到承诺的隐藏性
Bob：根据隐藏性， 不能区分？
Alice：直觉上是这样，但形式化归约有点微妙。问题是： 依赖于 ，而 又依赖于 。所以我们不能直接说”承诺 约等于 承诺 “。
Eve：解决方案是引入一个”中间模拟器” ：
与 相同，但它自己选择随机 （而不是从可信方收到），并输出 。
Alice：显然， 的输出与理想执行的输出分布相同，因为 都是独立均匀选择的。
现在，构造区分器 ：
- 收到承诺 和随机字符串
- 设置 ，
- 运行 的其余部分
如果 ， 的输出与 相同。 如果 ， 的输出与真实执行相同。
由承诺的隐藏性，这两个分布不可区分，所以 （即理想执行）与真实执行不可区分。
Bob：我明白了。这个归约有点绕，但逻辑是清晰的。
本次对话，就这么愉快的结束了，接下来，Alice，Bob，和Eve又会遇到什么故事呢，且听下回分解。快乐的时光过得特别快，又到了说再见的时候了，咱们下次再见~
参考资料
- https://eprint.iacr.org/2016/046.pdf
- R. Cleve. Limits on the Security of Coin Flips when Half the Processors are Faulty. In 18th STOC, pages 364-369, 1986.
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：Coder小Q Litt1eQ《【密码学】抛硬币协议》