基于最小信任的全安全多方计算

### 基于最小信任的全安全多方计算 #### 1. 相关定义 - **全模拟安全性**：对于任意安全参数 $\kappa \in N$，若存在概率多项式时间（PPT）模拟器 $S$，使得对于每个非均匀 PPT 敌手 $A = (A_1, A_2)$，真实实验和理想实验的结果在计算上不可区分，即 $Expt_{FE,A}^{real}(1^{\kappa}) \approx_c Expt_{FE,A,S}^{ideal}(1^{\kappa})$，则称函数加密（FE）方案 $FE$ 满足（单密钥）全模拟安全性。 - **简洁性**：设 $FE = (FE.Setup, FE.KeyGen, FE.Enc, FE.Dec)$ 是针对函数类 $H = \{H_m\}_{m \in N}$ 的单密钥 FE 方案。若对于任意 $m = poly(\kappa)$，所有 $h \in H_m$ 以及所有 $x \in \{0, 1\}^m$，令 $(mpk, msk) \leftarrow FE.Setup(1^{\kappa})$，$ct \leftarrow FE.Enc(mpk, x)$，密文 $ct$ 的大小（即 $|ct|$）不随 $h$ 的电路规模增长，而仅随其深度增长，则称 $FE$ 是简洁的。 #### 2. 基于简洁函数加密（LFE）的全安全多方计算 ##### 2.1 构造概述 该构造遵循三阶段结构，分两步进行： 1. 假设存在诚实的可信第三方（TP），允许各方将输入明文交给 TP。 2. 通过函数隐藏的 LFE 实现对 TP 的输入隐私保护。假设 LFE 具有公共随机字符串（CRS）。 ##### 2.2 详细协议步骤 - **阶段 1（TP 调用前）**： - 各方 $P_i$ 执行以下操作： 1. 设置 $LFE.crs := r$，其中 $r$ 来自公共随机数。 2. 利用公共随机数 $r$ 导出 $n$ 个随机填充 $\{r_j\}_{j \in [n]}$，其中 $|r_j| = |x_j|$。 3. 计算 $(digest_g, r_g) \leftarrow LFE.Compress(g, LFE.crs)$，其中函数 $g$ 硬编码 $n$ 个填充 $\{r_j\}_{j \in [n]}$，接受 $n$ 个输入 $z_1, \ldots, z_n$，并对输入 $\{z_j \oplus r_j\}_{j \in [n]}$ 执行 $f$ 计算。将 $(LFE.crs, digest_g, z_i = x_i \oplus r_i)$ 发送给 TP。 - **阶段 2（TP 调用）**： - TP 执行以下计算： 1. 初始化集合 $Z = \varnothing$。若未从 $P_j$ 收到消息或收到语法错误的消息，则将 $P_j$ 添加到 $Z$ 中。 2. 根据收到的 $(LFE.crs, digest_g)$ 值将集合 $P \setminus Z$ 划分为子集 $S_1, S_2, \ldots, S$。 3. 对于每个子集 $S_{\alpha}$： - 令 $LFE.crs_{\alpha}, digest_{g_{\alpha}}$ 表示 $S_{\alpha}$ 中各方提交的公共值。 - 对于每个 $j \in \{1, \ldots, n\}$，若 $j \in S_{\alpha}$，则设置 $\overline{z}_j = z_j$；否则设置 $\overline{z}_j = z_j$（其中 $z_j$ 是从 $P_j$ 收到的，$\{z_j\}_{j \in \{1, \ldots, n\}}$ 是 TP 随机采样的默认（掩码）输入）。 - 计算 $ct_{\alpha} \leftarrow LFE.Enc(digest_{g_{\alpha}}, \overline{z}_1, \ldots, \overline{z}_n)$，并将 $ct_{\alpha}, S_{\alpha}$ 发送给 $S_{\alpha}$ 中的每个方。 - **阶段 3（TP 调用后）**： - 方 $P_i$ 收到 $ct$ 后，使用阶段 1 中的 $LFE.crs$ 和 $r_g$ 计算输出 $y \leftarrow LFE.Dec(LFE.crs, ct, r_g)$。 ##### 2.3 定理总结 假设存在满足正确性、模拟安全性和函数隐藏安全性的简洁函数评估（LFE）方案，则存在一个针对任意功能 $f$ 的 TP 辅助多方计算协议 $\Pi_{LFE}$，该协议： - 对大小为 $poly(n, \kappa, m, \alpha, \beta)$ 的无状态 TP 进行单次调用（其中 $n$ 是参与方数量，$\kappa$ 是安全参数，$m$ 是各方输入 $f$ 的大小，$\alpha$ 和 $\beta$ 分别表示 LFE 方案中单个摘要和单个密文的大小）。 - 在非勾结模型中，针对多达 $(n - 1)$ 个恶意腐败方和半诚实腐败的 TP 实现全安全性。 #### 3. 基于单密钥简洁 FE 的全安全多方计算 ##### 3.1 构造概述 同样遵循三阶段结构，分两步进行： 1. 假设存在诚实的 TP，允许各方将输入交给 TP。 2. 通过对称密钥加密（SKE）实现输入隐私保护。 ##### 3.2 详细协议步骤 - **阶段 1（TP 调用前）**： - 各方 $P_i$ 调用 $\Pi_{idua}$ 实例，输入 $x_i$，计算以下内容： 1. 为每个 $P_i$ 生成默认输入 $x_i$。 2. 为每个方 $P_i$ 生成秘密密钥 $k_i \leftarrow SKE.Gen(1^{\kappa})$。 3. 生成 $(msk, mpk) \leftarrow FE.Setup(1^{\kappa})$。 4. 为每个 $P_i$ 计算 $e_i \leftarrow SKE.Enc(k_i, x_i)$。 5. 生成 $sk_g = FE.KeyGen(msk, g)$，其中函数 $g$ 嵌入输入的密文 $\{e_j\}_{j \in [n]}$ 和默认输入 $\{x_j\}_{j \in [n]}$，接受 $n$ 个密钥 $\{k_j\}_{j \in [n]}$ 和一个 $n$ 位向量 $\{b_j\}_{j \in [n]}$ 作为输入，输出 $f(\overline{x}_1, \ldots, \overline{x}_n)$（其中对于每个 $j \in [n]$，若 $b_i = 1$，则 $\overline{x}_j = SKE.Dec(k_i, e_j)$；否则 $\overline{x}_j = x_j$）。 6. 为数字签名方案生成 $(sk, vk)$。 7. 对于每个 $i \in [n]$，将 $(vk, mpk, k_i, \sigma_i, sk_g)$ 输出给 $P_i$，其中 $\sigma_i = Sign(sk, (i, mpk, k_i))$。若 $\Pi_{idua}$ 输出 $(\perp, C)$，则在集合 $P \setminus C$ 中重新运行阶段 1；否则进入下一阶段。各方 $P_i$ 以 $in_i = (vk, mpk, k_i, \sigma_i)$ 调用 TP。 - **阶段 2（TP 调用）**： - TP 执行以下计算： 1. 初始化 $Z = \varnothing$。若未收到来自 $P_j$ 的消息或 $Vrfy(vk, (