具有最小信任的全安全多方计算探索

### 具有最小信任的全安全多方计算探索 #### 1. 研究背景与相关工作 在多方计算（MPC）领域，存在诸多经典的不可能结果，如在多数方不诚实情况下实现公平MPC的不可能。为了绕过这些限制，研究者们进行了多方面的探索。 相关工作主要分为三大类： - **最小完备原语研究**：旨在研究公平计算所有函数所需的“最小帮助”，将辅助者定义为“完备”原语。例如，[FGMO01] 开启了对安全计算最小完备原语的研究，指出在多数方不诚实情况下，任何完备原语的基数为 n 是必要的，并提出了通用黑盒（UBB）作为一种原语。后续 [GIM+10] 提出了更简单的“公平重建”原语。[IOS12] 首次提出了全安全的无条件完备原语构造，其复杂度不随被评估函数的复杂度增长，但调用次数与电路规模成比例。为改进调用次数，[IOS12] 还提出了其他构造，如调用次数仅取决于参与方数量和电路输出大小的构造，以及将调用次数减少到 1 但以指数级增加完备原语计算复杂度为代价的构造。 - **非标准公平性概念探索**：一些工作通过考虑非标准的公平性概念来绕过 [Cle86] 的不可能性结果。例如，[GK12,BOO15,BLOO20] 考虑部分公平性；[BK14,KB14,ADMM14] 通过施加惩罚来强制公平性；[CGJ+17] 使用公告板；[EGL85,GMPY11,PST17] 探索资源公平性。 - **利用硬件令牌和物理不可克隆函数（PUFs）**：一系列工作研究了使用防篡改硬件令牌的通用可组合（UC）安全性，包括有状态和无状态变体。例如，[BJOV18] 基于单向函数的最小假设，使用硬件令牌提出了一个 UC 安全的非交互式安全计算（NISC）协议。[BFSK11,OSVW13,BKOV17] 探索了在访问 PUFs 的假设下的 UC 安全计算。 #### 2. 安全模型 在 UC 框架下，我们定义了真实世界和理想世界的执行模型。 ##### 2.1 真实世界 一个 n 方协议 Π 由 n 个概率多项式时间（PPT）交互式图灵机（ITMs）组成，每个参与方 Pi 初始化时带有输入 xi 和随机硬币 ri。参与方在同步轮次中交互，通信可以通过广播信道或全连接的点对点（P2P）网络进行，且所有通信都是私密且理想认证的。此外，存在一个特殊的“可信方”（TP），每个参与方 Pi 可以通过私密且认证的点对点信道与 TP 交互。TP 通常不持有输入，协议结束时也不获取输出，并且是无状态的。 恶意腐败的参与方（“主动”方）会从敌手 A 接收任意指令，而诚实方和半诚实腐败方（“被动”方）会忠实地遵循协议指令。敌手 A 是抢先的，即在每一轮中，敌手可以在产生腐败方的消息之前看到诚实方发送的消息。 协议结束时，敌手 A 向环境 Z 提供一个输出，该输出是 A 在整个协议过程中的视图的任意函数。Z 还会获得诚实方的输出，最后 Z 输出一个比特。 ##### 2.2 理想世界 我们描述了具有一致中止（un - abort）、可识别中止（id - abort）、公平性（fairness）和全安全（full）的理想世界执行。 理想计算的过程如下： 1. **参与方发送输入到可信方**：诚实方 Pi 将其输入 xi 发送到可信方。模拟器 S 可以为腐败方发送任意输入。 2. **可信方与模拟器通信**：可信方计算 (y1, ..., yn) = f(x′1, ..., x′n)。如果没有腐败方或 type = full，则进入步骤 4。 - 如果 type ∈ {un - abort, id - abort}，可信方将 {yi}i∈C 发送给 S。 - 如果 type = fairness，可信方发送 ready 给 S。 3. **模拟器 S 响应可信方**： - 如果 type ∈ {un - abort, fairness}，模拟器可以向可信方发送 abort。 - 如果 type = id - abort，若选择中止，模拟器 S 可以选择一个腐败方 i∗∈C 进行指责，并发送 (abort, i∗) 给可信方。 4. **可信方回复参与方**： - 如果可信方收到模拟器 S 的 abort： - 设置中止消息 abortmsg： - 如果 type ∈ {un - abort, fairness}，abortmsg = ⊥。 - 如果 t