基于定时释放加密和不经意传输的部分公平计算协议解析

### 基于定时释放加密和不经意传输的部分公平计算协议解析 #### 1. 背景与相关概念 在安全计算领域，部分公平性的安全计算在沉寂近十年后再次受到关注。部分公平交换协议旨在让双方交换输入，保证要么双方都获得输出，要么都没有，仅以极小的概率出现例外情况。 #### 2. 预备知识 - **可忽略函数与压倒性概率**：对于正函数 \(f\)，若对任意多项式 \(p\)，存在界限 \(B > 0\)，使得对于任意 \(\lambda \geq B\)，都有 \(f(\lambda) \leq 1/|p(\lambda)|\)，则称 \(f\) 是可忽略的。依赖于 \(\lambda\) 的事件以压倒性概率发生，意味着其概率至少为 \(1 - negl(\lambda)\)，其中 \(negl\) 是可忽略函数。 - **计算不可区分性**：两个分布族 \(X = \{X(a, \lambda)\}_{a \in D_{\lambda}, \lambda \in \mathbb{N}}\) 和 \(Y = \{Y(a, \lambda)\}_{a \in D_{\lambda}, \lambda \in \mathbb{N}}\) 是计算 \(1/p\) - 不可区分的，记为 \(X \stackrel{1/p}{\approx} Y\)，若对于任意非均匀概率多项式时间（PPT）敌手 \(Adv\)，存在函数 \(\mu(\cdot) = negl(\cdot)\)，使得对于任意 \(\lambda \in \mathbb{N}\)，\(a \in D_{\lambda}\)，有 \(|\Pr[Adv(X(a, \lambda)) = 1] - \Pr[Adv(Y(a, \lambda)) = 1]| \leq \frac{1}{p(\lambda)} + \mu(\lambda)\)。若对于每个多项式 \(p\) 都满足上述条件，则称两个分布族是计算不可区分的。 - **双方计算**：双方 \(A\) 和 \(B\) 之间的协议若能在多项式时间内运行，且满足正确性要求，即若 \(A\) 以输入 \(x\) 开始，\(B\) 以输入 \(y\) 开始，协议结束时 \(A\) 输出 \(f_A(x, y)\)，\(B\) 输出 \(f_B(x, y)\)，则称该协议计算功能 \(f : (x, y) \to (f_A(x, y), f_B(x, y))\)。 双方计算的安全性通常在真实/理想范式下定义。给定理想功能 \(F\) 和真实协议 \(\Pi\)，定义随机变量 \(ideal_{F, Adv}(x, y, \lambda)\) 和 \(real_{\Pi, Adv}(x, y, \lambda)\)。若协议 \(\Pi\) 能在 \(1/p\) 的误差范围内模拟理想功能 \(F\)，则称 \(\Pi\) 以 \(1/p\) - 安全的方式计算 \(F\)。 #### 3. 针对隐蔽敌手的双方计算 传统的双方计算定义针对恶意敌手，而隐蔽安全模型是一种较弱但在实际中仍很重要的安全模型。在该模型中，参与方可能会偏离协议规范，但不想被发现作弊。我们关注失败模拟的表述方式，它能自然地融入 \(1/p\) - 安全计算的概念中。 - **检测准确性**：在双方协议 \(\Pi\) 中，若一方 \(P_b\) 输出 \(corrupted_{1 - b}\)，则称其检测到另一方 \(P_{1 - b}\) 作弊。若当 \(P_b\) 未被破坏时，一方输出 \(corrupted_b\) 的概率可忽略不计，则称协议 \(\Pi\) 具有检测准确性。 - **隐蔽 \(1/p\) - 安全性**：设 \(F\) 是理想功能，\(\Pi\) 是计算 \(F\) 的双方协议。若 \(\Pi\) 具有检测准确性，且对于任何破坏 \(P_b\) 的非均匀 PPT 敌手 \(Adv\)，存在非均匀 PPT 理想敌手 \(Sim\)（模拟器），使得对于任意输入 \((x, y)\) 和任意非均匀 PPT 区分器 \(D\)，有 \(\Pr[P_{1 - b} \text{ 输出 } corrupted_b] \geq \varepsilon(\lambda) \cdot (|\Pr[D(ideal_{F, Sim}(x, y, \lambda)) = 1] - \Pr[D(real_{\Pi, Adv}(x, y, \lambda)) = 1]| - 1/p(\lambda)) - negl(\lambda)\)，则称 \(\Pi\) 在隐蔽敌手存在的情况下以 \(1/p\) - 安全的方式计算 \(F\)，其中 \(\varepsilon\) 是威慑因子。 #### 4. 部分公平交换协议的构建模块 - **可撤销陷门承诺**：这是一种计算隐藏、计算绑定的承诺方案，具有可撤销性和弱可提取性。可撤销性意味着使用适当的陷门，任何承诺都可以打开为任意值；弱可提取性表示使用适当的陷门，存在一个提取算法可以从承诺中恢复消息 \(m\)，且没有 PPT 敌手能将该承诺打开为不同的值 \(m'\)。 - **算法定义**：由五个 PPT 算法 \((C.Setup, C.Commit, C.Verify, C.Extract, C.Equivocate)\) 组成。 - \(C.Setup(1^{\lambda})\)：输入安全参数，生成方案的公共参数 \(pp\) 和陷门 \(\tau\)。 - \(C.Commit(pp, m; r)\)：给定消息 \(m \in M\) 和随机硬币 \(r \in R\)，输出承诺 - 打开对 \((c, d)\)。 - \(C.Verify(pp, c, m, d)\)：给定承诺 \(c \in C\)、消息 \(m \in M\) 和打开 \(d \in D\)，输出比特 \(b \in \{0, 1\}\)。 - \(C.Extract(\tau, c)\)：给定陷门 \(\tau\) 和承诺 \(c\)，输出消息 \(m \in M\)。 - \(C.Equivocate(\tau, c, m)\)：给定陷门 \(\tau\)、承诺 \(c\) 和消息 \(m\)，输出打开 \(d \in D\)。 - **正确性**：对于任意 \((pp, \tau) \leftarrow C.Setup(1^{\lambda})\) 和 \((m, r) \in M \times R\)，若 \((c, d) = C.Commit(pp, m; r)\)，则 \(C.Verify(pp, c, m, d) = 1\)。 - **可撤销性**：对于任意 \(m \in M\)，分布 \(\{(pp, \tau) \stackrel{\$}{\leftarrow} C.Setup(1^{\lambda}), (c, d) \stackrel{\$}{\leftarrow} C.Commit(pp, m) : (pp, c, d)\}\) 和 \(\{(pp, \tau) \stackrel{\$}{\leftarrow} C.Setup(1^{\lambda}), c \stackrel{\$}{\leftarrow} C, d \leftarrow C.Equivocate(\tau, c, m) : (pp, c, d)\}\) 是不可区分的。 - **弱可提取