完全安全的多方计算与最小信任

### 完全安全的多方计算与最小信任 #### 1. 协议执行与正确性分析 在多方计算协议 $\Pi$ 中，如果部分参与方 $P_i$（$i \in S'$）在协议执行过程中不调用可信第三方（TP），那么 TP 只会从其他参与方 $P_i$（$i \notin S'$）接收输入 $\{in_i\}$，并将 $S'$ 中参与方的输入设为 $\perp$。TP 计算输出时，对于 $S'$ 中的参与方 $P_i$ 使用默认输入 $x^*_i$，对于 $i \notin S'$ 的参与方 $P_i$ 使用其实际输入 $x_i$。 由于 $S'$ 被定义为 $\{2, \ldots, n\}$ 的子集且不包含索引 1，这意味着参与方 $P_1$ 是诚实的，它以输入 $x_1$ 诚实地参与协议并以 $in'_1 = in_1$ 调用 TP。基于此，我们可以依赖 $postTP_1$ 计算输出的正确性，进而推断出解码过程中计算的 $2^{n - 1}$ 位确实对应于每个子集 $S'$ 下函数 $f$ 的输出集合，即 $(b_1, b_2, \ldots, b_{2^{n - 1}})$。 需要注意的是，即使协议 $\Pi$ 满足容忍故障停止腐败（参与方不向 TP 发送消息）的完全安全性，上述论证仍然成立。此外，仅协议 $\Pi$ 满足公平性并不足以保证 $(E, D)$ 具有（统计上的）正确性，因为解码过程 $D$ 可能无法始终恢复出 $(b_1, \ldots, b_{2^{n - 1}})$。 根据 [DTT10] 的不可压缩性论证，必然有 $|\overline{st}'_1| + |in_1| + \ldots + |in_n| + |out_1| + |postTP_1| \geq 2^{n - 1}$。由此可以推断，至少有一项 $\geq \frac{2^{n - 1}}{n + 3}$。由于我们假设输出解码器较小，$|\overline{st}'_1|$ 和 $|postTP_1|$ 的大小被限制为 $poly(n, \kappa)$，所以必然是 $in_1, \ldots, in_n, out_1$ 中的某一项大小 $\geq \frac{2^{n - 1}}{n + 3}$。但这与我们假设的 TP 大小为 $poly(n, \kappa)$ 相矛盾，因为 $in_1, \ldots, in_n$ 是 TP 的输入，$out_1$ 是 TP 为计算对 $P_1$ 的响应而运行的算法。至此，我们得出矛盾，完成了证明。 #### 2. 无关联随机性模型下的不可能性 在无关联随机性的普通模型中，即使参与方仅存在半诚实腐败的情况，设计具有非勾结安全性的统计安全多方计算协议也是不可能的。具体来说，当非勾结 TP 模型中的敌手可以（a）半诚实地腐败多数参与方 $\{P_1, \ldots, P_n\}$ 或（b）半诚实地控制 TP 时，这样的协议无法实现。以下是正式定理： **定理 7**：在普通的非勾结 TP 模型（见定义 3）中，即使参与方 $P$ 的恶意腐败被限制为半诚实腐败，通用的统计安全多方计算协议也是不可能的。在该模型中，参与方只能对大小为 $poly(n, \kappa)$ 的小型 TP 进行单次调用。 **证明**：为了推出矛盾，假设存在一个统计安全的两方协议 $\Pi$，它能在非勾结 TP 模型中针对半诚实敌手安全地计算函数 $f$。设 $f$ 为计算 $(k + 1)$ 个不经意传输（OT）实例的功能，即： \[f(x_1 = (m^0_i, m^1_i)_{i \in [k + 1]}, x_2 = (b_1, \ldots, b_k, b_{k + 1})) = (m^{b_1}_1, m^{b_2}_2, \ldots, m^{b_{k + 1}}_{k + 1})\] 其中，$P_1$（发送方）的输入由 $(k + 1)$ 对位组成，$P_2$（接收方）的输入由 $(k + 1)$ 位组成。 假设 $C_{TP}$ 表示描述 TP 在协议 $\Pi$ 中计算的函数 $\{TP\}_{i \in [n]}$ 的电路。由于我们假设 TP 是“小型”的，必然有 $|C_{TP}| \leq poly(n, \kappa)$，且该大小与所计算的函数 $f$ 无关。具体而言，这意味着 TP 进行的计算必须严格少于计算 $(k + 1)$ 个 OTs。 我们声称，计算 $f$ 的协议 $\Pi$ 可以用于构建一个半诚实的 OT 扩展协议 $\Pi'$。在半诚实的环境下，参与方被给定 $k$ 个 OT 相关性作为 OT 扩展协议 $\Pi'$ 的基础 OTs。$\Pi'$ 的执行步骤如下： 1. 参与方执行协议 $\Pi$ 在调用 TP 之前的计算阶段的步