博弈论公平性的完整刻画：多方硬币抛掷协议解析

### 博弈论公平性的完整刻画：多方硬币抛掷协议解析 #### 1. 相关概念与背景 在多方硬币抛掷协议的研究中，有几个重要的概念和背景需要了解。首先，存在一种与RPD（一种相关理论框架）的联系。RPD框架将协议设计视为一个元游戏，即协议设计者与攻击者之间的Stackelberg博弈。设计者先选择协议Π，攻击者在考察该协议后决定腐蚀哪些联盟以及采用何种策略。他们期望找到一个能在这个元游戏中实现子博弈完美均衡的解决方案，不过采用的是与破坏隐私或正确性相关的经典效用函数。实际上，如果适当调整效用概念，CSP公平性概念可以在RPD框架中得到等价解释。 另外，为了绕过Cleve提出的在多数方被腐蚀情况下实现强公平（即无偏）硬币抛掷的不可能性，有两种方法：引入可信设置或采用非标准的加密假设，如可验证延迟函数。但本文聚焦于无可信设置、无公共参考字符串（CRS）且基于标准加密难度假设的普通模型。 #### 2. 技术概述 - 上界分析 ##### 2.1 希望的曙光 Chung等人的研究持悲观态度，但我们可以从一个简单协议中看到希望。以\(n_0 = n_1 = 2\)的特殊情况为例，这里\(n_b\)（\(b \in \{0, 1\}\)）表示偏好\(b\)的玩家数量（也称为\(b\)支持者）。在这种情况下，有一个简单协议能对最多2个玩家的联盟实现CSP公平性。具体做法是，随机选出一个0支持者和一个1支持者作为代表，让他们使用Blum的硬币抛掷方法进行对决。若\(b\)支持者中止，协议输出\(1 - b\)。以下是该协议满足CSP公平性的原因： - 若联盟只控制1个玩家，无论该玩家是否被选为代表，偏离协议都没有意义。 - 若联盟控制2个偏好相反的玩家，联盟对结果无偏好，没有偏离的动机。 - 若联盟控制2个偏好相同的玩家，其中一个会被选为代表，代表没有偏离的动机，因为非代表玩家的行为对结果无影响。 这个简单协议表明，当不存在\((n - 1)\)规模的联盟时，Chung等人的不可能性证明不成立，同时也说明该概念比加密公平性弱，因为即使没有诚实多数，仍有可能实现公平结果。 ##### 2.2 半恶意联盟的热身协议 上述\(n_0 = n_1 = 2\)的简单协议难以推广到更大的\(n_0\)和\(n_1\)情况。接下来介绍一个更复杂的热身协议，它为最终的上界结果提供了通用范式。由于Chung等人已经给出了\(n_0 = 1\)时针对最多\(n_1\)个玩家联盟的协议，我们的构造仅考虑\(n_0 \geq 2\)的情况。为简化，先从半恶意模型开始，在该模型中，联盟的偏离行为受限： 1. 联盟可以在某一轮查看诚实玩家的消息后中止协议，且一旦玩家中止，就不再参与后续过程。 2. 联盟可以在查看每一轮诚实玩家的消息后选择自己的随机硬币。 除这两种可能的偏离外，联盟会忠实遵循协议。 #### 2.3 HalfToss子协议 考虑名为\(HalfToss_b[k]\)（\(b \in \{0, 1\}\)，\(k\)为阈值参数）的子协议。该子协议为调用它的玩家组选择一个随机硬币。这个协议会执行两次，第一次在0支持者中执行，1支持者作为沉默观察者；第二次在1支持者中执行，0支持者作为沉默观察者。最终硬币结果是两组硬币的异或。 **协议2.1：HalfToss_b[k]子协议（半恶意版本）** - **共享阶段**： 1. 每个\(b\)支持者\(i \in P_b\)选择一个随机比特\(coin_i \stackrel{\$}{\leftarrow} \{0, 1\}\)，然后使用\((k + 1)\)出\(n\)的Shamir秘密共享方法将\(coin_i\)拆分为\(n_b\)份，记为\(\{[coin_i]_j\}_{j \in P_b}\)，并通过私有信道将\([coin_i]_j\)发送给每个玩家\(j \in P_b\)。 2. 若\(b\)支持者未中止，向广播信道发送心跳消息。此时，活跃集\(O_b\)定义为实际向广播信道发送心跳消息的所有\(b\)支持者的集合。每个玩家\(i \in [P_b]\)计算\(s_i := \oplus_{j \in O_b}[coin_j]_i\)，其中\([coin_j]_i\)是玩家\(i\)从玩家\(j\)收到的份额。 - **重建阶段**： 1. 每个\(b\)支持者\(i \in P_b\)向广播信道发送重建消息\((i, s_i)\)。 2. 若至少\(k + 1\)个\(b\)支持者发送了重建消息，使用Shamir秘密共享方法重建最终秘密\(s\)。具体来说，将每个形式为\((j, s_j)\)的重建消息解释为共同定义一个多项式\(f\)，使得\(f(j) = s_j\)，重建的秘密\(s := f(0)\)并输出\(s\)。 3. 若发送重建消息的\(b\)支持者少于\(k + 1\)个，输出\(\perp\)。 **HalfToss子协议的性质**： - **绑定性**：共享阶段唯一确定一个秘密\(s\)，重建阶段要么成功输出\(s\)，要么失败输出\(\perp\)。 - **知识阈值**：若至少\(k + 1\)个\(b\)支持者被腐蚀，联盟可以控制硬币抛掷结果。在共享阶段，联盟会知道每个诚实玩家的\(coin_i\)值，从而可以相应地选择联盟的硬币值来控制结果。若最多\(k\)个\(b\)支持者被腐蚀，共享阶段绑定的硬币值\(s\)是均匀的，且与联盟在共享阶段的视图无关。 - **活性阈值**：若联盟控制至少\(n_b - k\)个\(b\)支持者，它可以导致重建失败并输出\(\perp\)。若联盟控制少于\(n_b - k\)个\(b\)支持者，重建阶段必定成功。 ##### 2.4 热身协议 我们的热身协议使用了两个\(HalfToss_b\)子协议实例，分别在0支持者和1支持者中执行，这两个实例由阈值\(k_0\)和\(k_1\)参数化。以下是协议的具体步骤： **协议2.2：具有半恶意安全性的热身协议** - **共享阶段**： 1. 0支持者参与，1支持者观察，运行\(HalfToss_0[k_0]\)的共享阶段。 2. 1支持者参与，0支持者观察，运行\(HalfToss_1[k_1]\)的共享阶段。 - **重建阶段**： 1. 0支持者参与，1支持者观察，运行\(HalfToss_0[k_0]\)的重建阶段。若重建成功，结果记为\(s_0\)；若重建输出\(\perp\)，则令\(s_0 := 0\)。 2. 1支持者参与，0支持者观察，运行\(HalfToss_1[k_1]\)的重建阶段。若重建输出\(\perp\)，最终硬币值输出0；否则，记重建值为\(s_1\)，最终硬币值输出\(s_0 + s_1\)。 ##### 2.5 选择阈值\(k_0\)和\(k_1\) 假设我们要为最多\(t\)个玩家的联盟设计一个CSP公平协议，设\(t_0\)和\(t_1\)分别表示被腐蚀的0支持者和1支持者的数量。我们的目标是根据\(n_0\)、\(n_1\)和\(t\)选择\(k_0\)和\(k_1\)，满足以下条件（假设\(n_1 \geq n_0\)）： - **(C1)**：联盟不能同时控制\(s_0\)和\(s_1\)。即对于\(b \in \{0, 1\}\)，若联盟控制至少\(k_b + 1\)个\(b\)支持者，由于受腐蚀预算\(t\)的限制，联盟最多控制\(k_{1 - b}\)个\((1 - b)\)支持者，使得\(s_{1 - b}\)在共享阶段结束时与联盟的视图无关且均匀。 - **(C2)**：若联盟能控