全安全单态多方计算的轮复杂度分析

### 全安全单态多方计算的轮复杂度分析 在多方计算（MPC）领域，单态多方计算（Solitary MPC）是一个重要的研究方向，它涉及到在存在恶意参与者的情况下，安全地计算函数输出。本文将探讨全安全单态多方计算的轮复杂度，特别是在有广播信道且无公钥基础设施（PKI）的网络环境下的相关结论。 #### 1. 预备知识 在深入研究单态MPC之前，我们需要了解一些基本的符号和设置，以及所使用的密码学原语。 - **符号和设置** - **安全参数**：用 $\lambda$ 表示安全参数，$poly(\lambda)$ 表示关于 $\lambda$ 的多项式函数，$negl(\lambda)$ 表示可忽略函数，即对于任意多项式 $p(\cdot)$ 和足够大的 $\lambda$，有 $f(\lambda) < 1/p(\lambda)$。 - **加密表示**：用 $[[x]]$ 表示对 $x$ 的加密。 - **参与方模型**：考虑一组参与方 $\{P_1 \ldots, P_n\}$，每个参与方被建模为概率多项式时间（PPT）图灵机。存在一个PPT敌手，最多可以破坏 $t$ 个参与方，其中 $n/3 \leq t < n/2$。参与方通过成对安全且认证的信道连接，并可以访问公共参考字符串（CRS）。 - **密码学原语** - **去中心化阈值全同态加密（dTFHE）**：定义了一个 $t$ - 出 - $n$ 的去中心化阈值全同态加密方案，其语法包括以下算法： - $(pki, ski) \leftarrow dTFHE.DistGen(1^{\lambda}, 1^d, i; r_i)$：分布式设置算法，输出参与方 $P_i$ 的公钥 - 私钥对 $(pki, ski)$。 - $[[m]] \leftarrow dTFHE.Enc(pk, m)$：加密算法，输入公钥 $pk$ 和明文 $m$，输出密文 $[[m]]$。 - $[[y]] \leftarrow dTFHE.Eval(pk, C, [[m_1]], \ldots, [[m_k]])$：评估算法，输入公钥 $pk$、深度最多为 $d$ 的电路 $C$ 和一组密文 $[[m_1]], \ldots, [[m_k]]$，输出密文 $[[y]]$。 - $[[m : ski]] \leftarrow dTFHE.PartialDec(ski, [[m]])$：部分解密算法，输入私钥份额 $ski$ 和密文 $[[m]]$，输出部分解密结果 $[[m : ski]]$。 - $m/\bot \leftarrow dTFHE.Combine(pk, \{[[m : ski]]\}_{i \in S})$：组合算法，输入公钥 $pk$ 和一组部分解密结果 $\{[[m : ski]]\}_{i \in S}$，输出明文 $m$ 或符号 $\bot$。 - **非交互式零知识（NIZK）语言**：在单态MPC协议中，考虑两个NP语言 $L_1$ 和 $L_2$。 - **NP语言 $L_1$**： - 声明 $st = ([[x]], pk)$ - 见证 $wit = (x, \rho)$ - $R_1(st, wit) = 1$ 当且仅当 $[[x]] = dTFHE.Enc(pk, x; \rho)$。 - **NP语言 $L_2$**： - 声明 $st = ([[x : sk]], [[x]], pk, i)$ - 见证 $wit = (sk, r)$ - $R_2(st, wit) = 1$ 当且仅当 $[[x : sk]] = dTFHE.PartialDec(sk, [[x]])$ 且 $(pk, sk) = dTFHE.DistGen(1^{\lambda}, 1^d, i; r)$。 #### 2. 有广播无PKI的情况 在假设参与方除了成对私有信道外还可以访问广播信道，并且所有参与方都可以访问公共参考字符串（CRS）的网络环境下，我们进行以下研究： - **三轮的必要性** - **定理1**：假设参与方可以访问CRS、成对私有信道和广播信道。对于正整数 $n$ 和 $t$，满足 $n \geq 3$ 且 $n/3 \leq t < n/2$，存在一个单态功能 $f$，使得没有两轮的 $n$ 方单态MPC协议能够在容忍 $t$ 个破坏的情况下，即使敌手是非抢占式的，也无法安全地计算 $f$。 - **证明思路**：为了简化，考虑 $n = 3$ 和 $t = 1$ 的情况。定义单态函数 $f(x_1 = (m_0, m_1), x_2 = b, x_3 = \bot) := m_b$，其中 $x_3 = \bot$ 表示参与方 $Q = P_3$ 没有输入。分析协议 $\Pi$ 的三种不同执行场景： - **场景1**：敌手主动破坏 $P_2$，$P_2$ 在第一轮对 $P_1$ 诚实，但不与 $Q$ 进行私有通信，第二轮中止。 - **场景2**：敌手被动破坏 $Q$，$Q$ 诚实地学习输出 $f(x_1, x_2, x_3)$，并通过模拟场景1重新计算输出。 - **场景3**：敌手被动破坏 $P_1$，$P_1$ 诚实地进行本地计算，模拟 $Q$ 在场景1中的视图。 - **各方视图**： | 场景 | View1 | View2 | View3 | | --- | --- | --- | --- | | 场景1 | $(x_1, r_1, crs)$，$pc_{2\rightarrow1}, pc_{3\rightarrow1}$，$b_2^1\rightarrow$ | $(x_2, r_2, crs)$，$pc_{1\rightarrow2}, pc_{3\rightarrow2}, pc_{1\rightarrow3}$ | $(x_3, r_3, crs)$，$pc_{1\rightarrow3}, pc_{2\rightarrow3}$，$b_1^1\rightarrow, b_3^1\rightarrow$ | | 场景2 & 3 | $(x_1, r_1, crs)$，$pc_{2\rightarrow1}, pc_{3\rightarrow1}$，$b_2^1\rightarrow$ | $(x_2, r_2, crs)$，$pc_{1\rightarrow2}, pc_{3\rightarrow2}, pc_{1\rightarrow3}$ | $(x_3, r_3, crs)$，$pc_{1\rightarrow3}, pc_{2\rightarrow3}$，$b_1^1\rightarrow, b_2^1\rightarrow$ | | 场景1 | - | $b_1^2\rightarrow$ | $b_1^2\rightarrow$ | | 场景2 & 3 | $b_2^2\rightarrow$ | $b_1^2\rightarrow$ | $b_1^2\rightarrow, b_2^2\rightarrow$ | 首先声称如果场景1发生，$Q$ 必须以压倒性的概率获得 $f(x_1, x_2, x_3)$。否则，协议 $\Pi$ 容易受到半诚实 $Q$ 的潜在攻击，违反安全性。基于此，说明敌手被动破坏 $P_1$ 时可以计算 $f(\tilde{x}_1, x_2, \tilde{x}_3)$，这是最终的矛盾。 - **第一轮广播的必要性** - **定理2**：假设参与方可以访问CRS和成对私有信道。对于正整数 $n$ 和 $t$，满足 $n \geq 3$ 且 $n/3 \leq t < n/2$，存在一个单态功能 $f$，使得没有三轮的 $n$ 方单态MPC协议能够在容忍 $t$ 个破坏的情况下，仅在第二轮和第三