完美安全异步多方计算的效率再探

### 完美安全异步多方计算的效率再探 #### 1. 技术概述 在多方计算（MPC）领域，不同的安全协议在通信复杂度上存在差异。以下是不同完美安全MPC协议针对一般对手的每次乘法的摊销通信复杂度： | 设置 | 条件 | 通信复杂度 | | --- | --- | --- | | 同步 | Q(3)(P, Z) | O(\|Z\|² · (n⁵ log \|F\| + n⁶) + \|Z\| · (n⁷ log \|F\| + n⁸)) | | 异步（文献[10]） | Q(4)(P, Z) | O(\|Z\|³ · (n⁷ log \|F\| + n⁹ · (log n + log \|Z\|))) | | 异步（本文工作） | Q(4)(P, Z) | O(\|Z\|² · n⁷ log \|F\| + \|Z\| · n⁹ log n) | 我们的协议是在预处理模型中设计的。在这个模型里，各方首先生成形式为 (a, b, c) 的秘密共享随机乘法三元组，其中 c = ab。这些三元组随后会使用 Beaver 方法来高效评估乘法门。 我们预处理阶段协议的核心是一个高效的异步乘法协议，用于安全地将两个秘密共享的值相乘。该协议紧密遵循文献[19]的同步乘法协议，但在适应异步设置时存在一些挑战。 MPC 协议基于文献[24]中的秘密共享，其共享规范 S 定义为 {P\Z|Z ∈Z}。一个值 s ∈F 相对于 S 进行秘密共享的条件是存在份额 s₁, ..., s\|S\|，使得 s = s₁ + ... + s\|S\|，并且对于每个 q = 1, ..., \|S\|，份额 sq 为 Sq 中的每个（诚实）方所知。s 的共享表示为 [s]，其中 [s]q 表示第 q 个份额。 文献[19]的同步乘法协议假设 Q(3)(P, Z) 条件，以 [a]、[b] 为输入，安全地生成随机共享 [ab]。其主要思想是，由于 Sp ∩Sq ≠ ∅，可以指定一个来自 Sp ∩Sq 的公开已知方对求和项 [a]p[b]q 进行秘密共享。为了提高效率，每个指定的“求和项共享方”可以对分配给它的所有求和项进行求和，并共享该和。如果没有求和项共享方恶意行为，那么所有秘密共享和的总和将导致 ab 的秘密共享。 为了处理作弊问题，文献[19]首先设计了一个乐观乘法协议 ΠOptMult，它接受一个额外参数 Z ∈Z，并在对手 Adv 破坏的方集合 Z⋆⊆Z 时生成 ab 的秘密共享。ΠOptMult 的思想与上述相同，只是求和项共享方现在被“限制”在子集 P \ Z 中。由于 (Sp ∩Sq) \ Z 是非空的，因此可以保证每个求和项 [a]p[b]q 都可以分配给 P \ Z 中的一个指定方。 各方不知道确切的破坏方集合，因此会为每个 Z ∈Z 运行一次 ΠOptMult 实例。这保证了至少有一个实例会生成 ab 的秘密共享。通过比较所有 ΠOptMult 实例生成的输出共享，各方可以检测是否发生了作弊。如果没有检测到作弊，那么任何输出共享都可以作为 ab 的共享。否则，各方会考虑一对冲突的 ΠOptMult 实例，并进入作弊者识别阶段。在这个阶段，各方根据冲突的 ΠOptMult 实例中求和项共享方共享的值，识别出至少一个腐败的求和项共享方。一旦识别出一个腐败的求和项共享方，各方将忽略涉及该方的所有 ΠOptMult 实例的输出共享。这个比较 ΠOptMult 实例输出共享并识别腐败方的过程会一直持续，直到所有剩余的输出共享都是针对同一个值。 #### 2. 异步设置中的挑战 在异步设置中应用上述思想时，存在两个主要挑战： 1. **无限等待问题**：在 ΠOptMult 中，一个潜在的腐败方可能永远不会共享分配给它的求和项的总和，导致无限等待。为了解决这个问题，由于 Z 满足 Q(4)(P, Z) 条件，每个 (Sp ∩Sq) \ Z 中至少包含一个诚实方。因此，不是为求和项 [a]p[b]q 指定一个单一的方，而是 P\Z 中的每个方都共享它“能够”共享的所有求和项的总和，从而保证每个 [a]p[b]q 至少被一个（诚实）方考虑进行共享。但需要确保一个求和项不会被多次共享。 2. **作弊者识别阶段参与问题**：如果存在一对冲突的 ΠOptMult 实例，这些实例中潜在的腐败求和项共享方可能不会进一步参与作弊者识别阶段。为了解决这个问题，乘法协议现在按迭代进行。在每次迭代中，各方为每个 Z ∈Z 运行一次异步 ΠOptMult 实例，并比较每个实例的输出。如果输出不同，他们将进入相应的作弊者识别阶段。然而，前一次迭代中的求和项共享方在参与所有前一次迭代的作弊者识别阶段之前，不允许参与未来的迭代。这可以防止前一次迭代中的腐败求和项共享方在未来的迭代中充当求和项共享方，直到他们完成“待办任务”，在这种情况下，他们会被发现并被丢弃。诚实方最终会被“释放”，可以在未来的迭代中充当求和项共享方。一旦各方到达所有 ΠOptMult 实例的输出都相同的迭代，协议就会停止。 #### 3. 预备知识和现有异步原语 ##### 3.1 基本假设 - 各方通过成对安全通道连接。 - 对手 Adv 是恶意且静态的，在协议执行开始时决定腐败方的集合。未受 Adv 控制的方称为诚实方。 - 给定 P′ ⊆P，如果对于每个 Zi₁, ..., Zik ∈Z，条件 P′ ⊈Zi₁ ∪ ..