基于小型可信方的全安全多方计算协议研究

### 基于小型可信方的全安全多方计算协议研究 在多方计算（MPC）中，使用可信方（TP）的计算资源需要支付费用，因此客户自然希望尽量减少这些费用。若通过大规模诚实多数 MPC 协议模拟 TP，情况也是如此。我们将 TP 规模与函数电路规模无关的设置称为小型 TP 模型。 #### 1. 研究问题提出 在这项工作中，除了考虑小型 TP 模型，我们还对设计仅需向 TP 进行单次调用的全安全协议感兴趣。理论上，单次调用是规避 [Cle86] 中公平且全安全 MPC 不可能性的最低要求。它还为类似私有同时消息（PSM）[FKN94] 模型的协议开辟了可能性，在该模型中，给定公共随机性，各方向 TP 发送一次性消息，并在收到 TP 的回复后计算输出。在现实世界中，例如当 TP 被云服务提供商或基于区块链的方法取代时，单次调用相较于多次调用更有可能产生实际可行的解决方案。 我们工作的核心问题是：能否构建一种高效协议，仅向“小型”TP 进行单次调用并实现全安全？ #### 2. 研究结果 我们在使用小型 TP 的全安全 MPC 协议的存在性方面取得了积极和消极两方面的结果。 ##### 2.1 消极结果 - **通用输出解码器的不可能性**：我们证明了先前解决此问题的方法必然需要一个规模与参与方数量呈指数关系的 TP。具体而言，我们考虑一类协议，其中各方可以相互交互（任意轮数），然后向可信方进行单次调用，收到 TP 的回复后，使用通用解码器对该回复及其状态进行计算以得到输出。这里的通用解码器是指其规模与要计算的功能规模无关（考虑单比特输出功能）。我们证明了对于此类协议，TP 的规模必然会随着参与方数量呈指数增长，该结果与协议使用的计算假设无关，即使允许 TP 的规模随函数输出规模增长，结果仍然成立。 - **定理 1（非正式）**：对于任何带有通用输出解码器的全安全 MPC 协议，TP 的规模必须与参与方数量呈指数关系。 - **设置或计算假设的必要性**：上述结果自然引出一个问题，即当放宽使用通用解码器的限制时，是否可以实现小型 TP 辅助的全安全 MPC 协议。我们证明了任何无任何可信设置或相关随机性、仅向小型 TP 进行单次调用的统计安全协议，甚至无法达到半诚实安全。这种不可能性即使对于可能没有通用输出解码器的协议也成立。这表明要实现全安全，必须依靠计算假设或某种设置（如相关随机性）。 - **定理 2（非正式）**：在纯模型中，不存在对半诚实对手实现信息论安全的 MPC 协议，其中 TP 的规模是功能输入规模的固定多项式。 ##### 2.2 积极结果 我们现在关注基于计算假设，使用小型 TP 实现全安全 MPC 协议的问题。我们的主要积极结果由以下定理概括： - **定理 3（非正式）**：假设存在单密钥简洁功能加密（FE）方案，则存在一种全安全高效的 MPC 协议，仅向小型 TP 进行单次调用。 单密钥简洁功能加密是一种 FE 方案，其中加密算法的规模不会随发布秘密密钥的函数规模增长。基于各种假设对这些原语的已知实例化，我们得到以下推论： - **推论 1（非正式）**：假设以下条件成立，则存在一种全安全高效的 MPC 协议，仅向 TP 进行单次调用： 1. 带次指数模噪声比的学习误差（Learning with Errors）[GKP + 13]，如果允许 TP 的规模仅随功能的深度和输出长度增长。 2. 见证加密方案 [GGSW13] 和全同态加密（FHE），如果允许 TP 的规模仅随功能的输出长度增长。 3. 不可区分混淆（iO）[BGI + 01, GGH + 13, JLS21] 和单向函数，其中 TP 的规模与深度和输出长度无关。 我们还给出证据表明，在某些受限设置中，这些假设可能是必要的。具体来说，考虑一种受限的计算模型，其中各方不相互交互，仅向 TP 进行单次调用，并能根据 TP 的回复计算功能输出。这种模型类似于 PSM 设置，不难看出，这种受限模型等同于具有简洁在线阶段的 MPC 协议。目前，已知的具有简洁在线阶段的 MPC 协议的构造都基于简洁功能评估（LFE）[QWW18]，而 LFE 已知蕴含简洁 FE。这表明在上述受限设置中，这些假设可能是必要的。最后，在这个受限模型中，我们通过基于 LFE 构建一个仅向小型 TP 进行单次调用的全安全 MPC 协议，得到了一个积极结果。 ##### 2.3 降低对 TP 信任的可能性 我们还探索了降低对 TP 安全要求的可能性。有趣的是，我们上述的解决方案能够保持对 TP 的隐私性，这是一个额外的理想特性。具体而言，当对手以半诚实方式破坏 TP（但不破坏任何参与方）时，我们的构造是安全的。我们进一步探索了如果允许半诚实的 TP 与其他恶意方勾结会发生什么。我们发现，无论 TP 的规模如何，这种模型都不足以规避 Cleve 公平性的不可能性，即使将恶意方限制为故障停止（fail - stop）情况也是如此。 我们的结果总结在以下表格中： | 安全性 | 调用次数 | 设置 | 调用 TP 前的交互 | 通用输出解码器 | 是否可行 | 参考 | | --- | --- | --- | --- | --- | --- | --- | | 统计安全 | 1 | 纯模型 | 是 | 否 | 否 | 定理 7 | | 计算安全 | 1 | 相关随机性（C.R） | 是 | 是 | 否 | 定理 6 | | 计算安全 | 1 | 公共随机字符串（CRS） | 否 | 否 | 是（基于 LFE） | 定理 4 | | 计算安全 | 1 | 纯模型 | 是 | 否 | 是（基于简洁 FE） | 定理 5 | | 统计安全 | n | 相关随机性（C.R） | 是 | 是 | 是 | [IOS12] | | 计算安全 | n | 纯模型 | 是 | 是 | 是（基于 OT） | [IOS12] | | 统计安全 | 1 | 相关随机性（C.R） | 是 | 否 | 开放问题 | - | #### 3. 技术亮点与讨论 ##### 3.1 积极结果 我们分别基于 LFE [QWW18] 和单密钥简洁 FE [SW05, BSW11] 提出了两种协议，均仅向无状态的“小型”TP 进行单次调用。以下是它们的优缺点： - **基于 LFE 的构造**：LFE 的两轮最小通信模式导致了