具有可识别中止功能的轮次最优多方计算

### 具有可识别中止功能的轮次最优多方计算 #### 1. 引言 在多方计算（MPC）中，可识别中止的安全性是一个重要的研究方向。传统的方法在某些情况下存在局限性，例如，一方可能无法获取查询混淆电路所需的全部标签。为了解决这个问题，我们提出了一种新的方法，通过对不经意传输（OT）协议的改进，实现了具有可识别中止功能的轮次最优多方计算。 #### 2. 相关工作 - **可识别中止的安全性概念**：最早由Aumann和Lindell提出，随后在多个研究中得到进一步探讨。 - **信息论实现**：Ishai等人展示了在相关随机模型中，可识别中止的MPC可以信息论方式实现。 - **SPDZ协议的应用**：一些后续工作尝试使用SPDZ协议来实现可识别中止的MPC，不同的工作在复杂度和安全性方面有所改进。 - **有界重绕安全**：之前的工作在一些简单原语中考虑了有界重绕安全的概念，但我们的工作需要对任何概率多项式时间的对抗策略都具有安全性，这带来了更多的技术挑战。 #### 3. 预备知识和标准定义 - **符号表示**：用 $\lambda \in N$ 表示安全参数，随机算法 $A$ 在概率多项式时间（PPT）内运行，如果存在多项式 $p(·)$ 使得对于每个输入 $x$，$A(x)$ 的运行时间受 $p(|x|)$ 限制。 - **交互式算法**：用 $\langle A(\alpha), B(\beta) \rangle(\gamma)$ 表示 $B$ 在与 $A$ 交互后的输出分布，$A$ 和 $B$ 分别使用私有输入 $\alpha$ 和 $\beta$，共同输入 $\gamma$。 - **延迟输入协议**：指只在通信的最后一轮需要协议输入的协议。 ##### 3.1 非可塑承诺方案 我们遵循特定文献中的非可塑承诺定义。在实际实验中，中间人（MIM）与承诺者 $C$ 在左会话中交互，与接收者 $R$ 在右会话中交互。同步非可塑承诺方案 $\langle C, R \rangle$ 满足以下条件：对于每个PPT同步对手MIM，存在一个PPT模拟器 $S$，使得以下两个集合在计算上不可区分： $\{MIM_{\langle C,R \rangle}(\tilde{v}, z)\}_{\lambda \in N, v \in \{0,1\}^{\lambda}, z \in \{0,1\}^*}$ 和 $\{SIM_{\langle C,R \rangle}(1^{\lambda}, z)\}_{\lambda \in N, v \in \{0,1\}^{\lambda}, z \in \{0,1\}^*}$ 此外，同步非可塑承诺还需要满足以下性质： 1. **提取的非可塑性**：存在一个提取器 $Ext_{NMCom}$ 能够从MIM生成的格式良好的承诺中提取消息，并且 $Ext_{NMCom}$ 的输出分布与对手接收诚实或模拟承诺无关。 2. **最后消息的伪随机性**：$C$ 生成的最后消息在计算上与随机字符串不可区分。 ##### 3.2 具有有界重绕安全性的陷门生成协议 陷门生成协议 $TDGen = (TDGen1, TDGen2, TDGen3, TDOut, TDValid, TDExt)$ 是一个两方的三轮协议，具体步骤如下： 1. **第一轮**：发送者 $S$ 使用随机字符串 $R_S$ 计算并发送 $td_{S \to R}^1 \leftarrow TDGen1(R_S)$。 2. **第二轮**：接收者 $R$ 使用随机数 $R_R$ 计算并发送 $td_{R \to S}^2 \leftarrow TDGen2(td_{S \to R}^1; R_R)$。 3. **第三轮**：发送者 $S$ 计算并发送 $td_{S \to R}^3 \leftarrow TDGen3(td_{R \to S}^2; R_S)$。 4. **输出**：接收者 $R$ 输出 $0/1 \leftarrow TDOut(td_{S \to R}^1, td_{R \to S}^2, td_{S \to R}^3)$。 5. **陷门验证算法**：$TDValid(·)$ 以 $(trap, td_{S \to R}^1)$ 为输入，输出一个比特位，确定 $trap$ 是否为对应于第一轮消息 $td_1$ 的有效陷门。 该协议还需要存在一个PPT提取器 $TDExt$，在给定一组特定值时能够输出有效陷门。1 - 重绕安全意味着没有作弊的PPT接收者 $R^*$ 能够在查询 $S$ 两次不同的第二轮消息时学习到有效陷门。 #### 4. 重绕安全的OT和MPC ##### 4.1 特殊B - 重绕可安全的OT OT协议 $OT = (OT1, OT2, OT3, OT4)$ 是特殊B - 重绕可安全的，对抗恶意发送者的B次重绕，如果在实验 $E_0^k$ 和 $E_1^k$ 中，对手的输出分布对于任何 $k \in [B]$ 和所有 $\{b_0[j], b_1[j]\}_{j \in [B]}$ 都是计算上不可区分的，其中 $b_{\sigma}[j] \in \{0, 1\}^{\lambda}$ 对于所有 $j \in [B]$ 和 $\sigma \in \{0, 1\}$，且 $b_0[k] = b_1[k]$。 ```mermaid graph LR A(Adversary A) -->|ot1 ← OT1(1λ)| C(Challenger C) C -->|ot1| A A -->|{ot2[j]}j∈[B]| C loop For each j ∈[B] C -->|ot3[j] ← OT3(ot1, ot2[j], bσ[j])| A end A -->|ot4[k]| C ``` ##### 4.2 具有一致中止的有界重绕安全的MPC 一个4 - 轮的MPC协议 $MPC$ 是一个确定性多项式时间算法的元组 $MPC = \{(Next_1^i, Next_2^i, Next_3^i, Next_4^i, output_i)\}_{i \in [n]}$。我们定义了理想计算和实际执行： - **理想计算**：在理想世界中，根据标准的MPC定义，在 $(S, I)$ 下对输入向量 $x$ 进行联合理想执行。 - **实际执行**：在实际世界中，$n$ 方的4 - 轮MPC协议 $\Pi$ 在 $(A, I)$ 下执行，包括四轮的交互过程，最终输出诚实方的输出向量 $y_H$ 和对手的输出 $z$。 安全定义要求对于每个PPT实际世界对手 $A$，存在一个PPT模拟器 $S$，使