实现最优轮次和高效通信的多方计算协议

### 实现最优轮次和高效通信的多方计算协议 #### 1. 引言 安全多方计算（MPC）允许不同参与方在私有输入上联合评估任何电路，使得各方仅得知计算输出，而无其他额外信息。近年来，最优轮次MPC的设计备受关注。在半诚实敌手模型下，安全MPC在无额外设置的纯模型中至少需要两轮；而对于恶意敌手，在纯模型中使用黑盒模拟器时，安全MPC至少需要四轮。然而，现有的许多构造存在通信复杂度与被评估电路规模成正比的问题。 #### 2. 研究背景与相关工作 - **功能加密（FE）**：FE是一种可对加密数据进行细粒度访问控制的原语。通过主密钥生成算法，可生成与电路 $f$ 相关的秘密密钥 $sk_f$，使用该密钥解密密文 $ct \leftarrow Enc(msk, x)$ 仅能得到 $f(x)$，保证了除 $f(x)$ 外无其他信息泄露。 - **功能加密组合器**：能将多个FE候选方案组合，只要其中任何一个初始FE候选方案安全，组合后的FE协议就安全。Ananth等人基于学习误差（LWE）假设构造了具有简洁性和可分解性的FE组合器。 - **相关MPC协议**：已有一些关于MPC协议的研究，如Ananth等人提出了在半诚实敌手模型下的最优轮次（两轮）电路可扩展MPC协议，但该协议无法抵御恶意敌手攻击。Cohen等人提出了在相关随机模型下容忍自适应腐败的最优轮次电路可扩展MPC协议。 #### 3. 研究问题与主要贡献 - **研究问题** - 是否存在基于标准复杂度假设、在纯模型中针对不诚实多数恶意敌手安全的最优轮次MPC协议，且具有电路可扩展性，即通信复杂度仅取决于被评估电路的深度及其输入输出长度？ - 是否存在基于标准（多项式）复杂度假设、在纯模型中的最优轮次且与电路无关的恶意安全MPC协议？ - **主要贡献** - **从FE组合器到电路可扩展MPC**：提供了一个保持轮次的黑盒编译器，在存在简洁FE组合器的假设下，可将广泛的MPC协议编译为电路可扩展协议。若LWE假设成立，可得到一个针对恶意敌手安全的最优轮次MPC协议，其通信复杂度仅取决于安全参数、电路深度、输入长度和输出长度。 - **从MFHE到电路无关MPC**：提出一个保持轮次的黑盒编译器，在存在完美正确的紧凑多密钥全同态加密（MFHE）方案的假设下，可将广泛的MPC协议编译为电路无关协议。对于常数数量的参与方，基于LWE假设可得到首个在纯模型中与电路无关的最优轮次恶意MPC协议；对于任意数量的参与方，在Ring - LWE和决策小多项式比率（DSPR）假设下可得到相应协议。 #### 4. 技术概述 ##### 4.1 从FE组合器到电路可扩展MPC - **Ananth等人的编译器**：主要构建模块为一个 $\ell$ 轮半诚实安全的MPC协议和一个简洁可分解的FE组合器。MPC协议计算函数 $g$，该函数接收每个参与方的输入，包括主密钥 $msk_i$、值 $x_i$ 和随机数 $r_i$，使用这些主密钥对 $x_1, \ldots, x_n$ 进行加密。最终协议的通信复杂度为 $poly(\lambda, n, d, L_{in}, L_{out})$。 - **实现恶意安全**：直接将半诚实MPC协议替换为恶意安全协议不可行，因为恶意参与方可能生成格式错误的主密钥或随机数。可通过修改函数 $g$ 来解决随机数问题，但主密钥问题的解决会导致协议轮次增加，且该协议仍不安全，仅能实现带输出知识的隐私（PKO）。 - **保持轮次的构造：PKO安全**：以两轮输入无关的4轮MPC协议为例，参与方先运行两次Blum硬币抛掷协议，生成主密钥和秘密密钥。同时，执行MPC协议评估函数 $g'$，该函数检查承诺的正确性，若检查成功则输出密文。此协议可保证密文诚实计算，但诚实方的输出可能不正确。 - **从PKO到完全安全**：利用Ishai等人的PKO安全到完全安全编译器，将上述协议转换为标准安全协议。此外，还可使用现有编译器使协议支持多输出功能。 ##### 4.2 从MFHE到电路无关MPC - **MFHE概述**：MFHE方案包括设置算法、加密算法、评估算法和解密算法。要求该方案具有紧凑性，即密钥、密文大小和加密解密算法描述仅取决于函数的输入输出大小。 - **编译器工作流程**：以两方情况为例，各方运行设置算法生成公私钥对，加密输入并发送给对方。然后运行评估算法得到密文 $ct'_i$，继续执行MPC协议评估函数 $g$，该函数检查密文和公钥的正确性，若解密值相同则输出结果。协议的通信复杂度为 $poly(\lambda, n, L_{in}, L_{out})$，通过使用伪随机生成器（PRG）可将通信复杂度优化为 $O(L_{in}) + poly(\lambda, n, L_{out})$。 ##### 4.3 k - 延迟输入函数MPC 在编译器的描述中，需要依赖一种MPC协议 $\Pi$，该协议仅在最后两轮（图2构造中为三轮）需要参与方的输入。许多现有MPC协议在前两轮不需要输入，但由于诚实方的输入可能受到敌手影响，无法依赖其标准安全概念。因此，引入了k - 延迟输入函数的概念，即每个参与方的输入包括私有输入 $x$ 和函数 $f$，函数 $f$ 仅在第 $k$ 轮及以后才需要。通过使用标准的2n方 $\ell$ 轮MPC协议和一次