密码学中有一类问题格外引人入胜：若干互不信任的参与方，各自持有私密输入，希望联合计算某个函数并获得结果，但任何一方都不愿向他人暴露自己的原始数据。这就是安全多方计算（Secure Multi-Party Computation，MPC）所要解决的核心难题。自姚期智（Andrew Yao）在 1982 年提出”百万富翁问题”以来，MPC 经历了从纯理论探索到工业级部署的完整演化路径。本文将从基本定义出发，逐步深入混淆电路、GMW、BGW、SPDZ 等经典协议，并讨论 MPC 在隐私保护计算和数字资产托管领域的实际落地。

先看一张图，把这一节的关键关系串起来。

graph TD
    A[私有输入] --> B[秘密共享]
    B --> C[本地计算]
    C --> D[交互协议]
    D --> E[输出结果]

1.1 理想世界与现实世界范式

MPC 的安全性定义采用经典的理想世界/现实世界范式（ideal/real paradigm）。在理想世界中，存在一个完全可信的第三方（trusted third party）：所有参与方将自己的输入发送给该第三方，由其完成计算后将结果分发给各方——没有任何信息泄露，因为第三方除了输出之外不会透露任何中间结果。在现实世界中，参与方之间通过密码学协议直接交互，不存在可信第三方。MPC 的安全性要求是：现实世界中协议的执行效果”不可区分”于理想世界——换言之，敌手在现实世界中能获取的信息，不会超过它在理想世界中仅凭输入和输出所能推断的内容。

形式化地，设参与方集合为 \(P_1, P_2, \ldots, P_n\)，各自持有输入 \(x_1, x_2, \ldots, x_n\)，需要计算函数 \(f(x_1, x_2, \ldots, x_n) = (y_1, y_2, \ldots, y_n)\)。协议 \(\pi\) 被称为安全地计算 \(f\)，当且仅当存在一个模拟器（simulator）\(\mathcal{S}\)，使得敌手在现实世界中观察到的全部信息（称为视图，view）与模拟器仅根据敌手的输入和输出所生成的模拟视图在计算上不可区分（computationally indistinguishable）或统计上不可区分（statistically indistinguishable）。

1.2 半诚实模型与恶意模型

根据敌手的行为假设，MPC 安全模型通常分为两类：

• 半诚实模型（semi-honest / honest-but-curious）：敌手会忠实地执行协议规定的每一步操作，但会试图从协议执行过程中获取的所有消息中推导出其他参与方的输入。这是最基础的安全模型，许多协议首先在此模型下设计，再通过编译技术（compilation technique）提升到恶意安全。
• 恶意模型（malicious / active）：敌手可以任意偏离协议规定的行为——发送伪造消息、提前终止、替换输入——以期获取额外信息或影响计算结果。恶意模型下的协议通常需要零知识证明（zero-knowledge proof）或切割选择（cut-and-choose）等手段来保证正确性。

此外还有隐蔽模型（covert model），由 Aumann 和 Lindell 提出，允许敌手作弊，但保证以一定概率被检测到。该模型在实际场景中具有吸引力，因为参与方出于声誉考虑往往不愿冒被发现作弊的风险。

下表从敌手行为、性能开销、典型技术和实际部署等维度对三种安全模型进行对比：

个人思考。 半诚实模型与恶意模型之间的鸿沟，远不止性能报表上多出来的几个数量级。它反映的是一个根本性的信任假设差异：你是否愿意相信你的对手会老老实实地执行协议？在组织内部的数据分析场景中，半诚实模型往往够用——因为各部门没有主动攻击的动机，被发现作弊的后果远大于收益。但在跨组织甚至对抗性场景中，假设对手「诚实但好奇」就像假设小偷只会看你家的门锁型号但不会撬锁一样不切实际。隐蔽模型提供了一个务实的中间地带：它不保证安全，但保证作弊有代价——这在商业合作中往往已经足够，因为没有哪家企业愿意冒被公开发现欺诈的声誉风险。在我看来，选择安全模型的本质不是一个技术问题，而是一个风险评估问题：你愿意为「防止最坏情况」付出多大的性能代价？

1.3 腐败模型与通信假设

腐败模型还区分静态腐败（static corruption）和自适应腐败（adaptive corruption）：前者要求敌手在协议开始前就确定被腐败的参与方集合，后者允许敌手在协议执行过程中动态地选择腐败对象。自适应安全通常更难实现，所需开销也更大。

通信方面，MPC 协议通常假设参与方之间存在安全的点对点信道（secure point-to-point channel），以及（视协议需要）一个广播信道（broadcast channel）。部分信息论安全的协议还要求诚实多数（honest majority），即被腐败的参与方不超过总数的三分之一或二分之一。

二、不经意传输

不经意传输（Oblivious Transfer，OT）是 MPC 协议的基本构建模块之一，其重要性甚至可以与公钥加密相提并论。Kilian 在 1988 年证明了一个深刻的结论：OT 足以安全地计算任意函数。

2.1 1-out-of-2 OT

最常用的 OT 变体是 1-out-of-2 OT（二选一不经意传输）。协议中有两个角色：发送方（sender）持有两条消息 \(m_0\) 和 \(m_1\)；接收方（receiver）持有选择比特 \(b \in \{0, 1\}\)。协议结束后，接收方获得 \(m_b\)，但不知道 \(m_{1-b}\)；发送方不知道 \(b\) 的值。

基于公钥密码学的经典 OT 构造利用了类似 Diffie-Hellman 的结构。以 Naor-Pinkas OT 为例：发送方选择群元素 \(C\)，接收方根据 \(b\) 的值在两个公钥位置之一嵌入自己知道离散对数的元素，使得发送方无法区分哪个位置被选中。发送方对两条消息分别用两个公钥加密并发送，接收方仅能解密其中之一。

2.2 OT 扩展与 IKNP 协议

公钥 OT 的计算成本较高，对于大规模电路求值而言，逐门执行公钥 OT 是不可接受的。OT 扩展（OT extension）技术允许我们用少量”种子” OT（seed OT）加上对称密码学操作生成大量 OT 实例，从而将计算瓶颈从公钥运算转移到对称运算。

IKNP 协议（Ishai-Kilian-Nissim-Petrank，2003）是最经典的 OT 扩展方案。其核心思想是角色互换：先执行 \(\kappa\) 次（\(\kappa\) 为安全参数，如 128）“反向”的种子 OT，然后利用伪随机生成器（PRG）和矩阵转置技巧，将这 \(\kappa\) 次种子 OT 扩展为任意 \(m\) 次 OT。整个过程中，除种子 OT 外的计算全部基于对称密码学，效率极高。

后续工作进一步优化了 OT 扩展。KOS15 方案将 IKNP 扩展到恶意安全模型；ALSZ13 引入了更高效的一致性检查；SoftSpokenOT（2022）则利用向量不经意线性评估（VOLE）技术进一步降低了通信量。

2.3 相关不经意传输

相关不经意传输（Correlated OT）和随机不经意传输（Random OT）是 OT 的重要变体。在相关 OT 中，发送方的两条消息满足特定的相关关系（如 \(m_1 = m_0 \oplus \Delta\)），可以进一步降低通信量。随机 OT 则允许消息是随机生成的，而非由应用层指定，这在预处理模型中尤为有用。

三、Yao 的混淆电路

3.1 基本构造

Yao 的混淆电路（Garbled Circuit，GC）是第一个通用的两方安全计算协议，由姚期智在 1986 年提出（尽管完整的安全性证明直到 Lindell 和 Pinkas 在 2009 年才给出）。其核心思想精妙而直观：将待计算的函数表示为布尔电路，然后对电路中的每条线路（wire）和每个门（gate）进行”加密”处理，使得求值方（evaluator）能够正确计算电路的输出，但无法获知任何中间线路的实际比特值。

具体构造如下。设电路有 \(n\) 条线路。对于每条线路 \(w_i\)，混淆方（garbler）随机选择两个密钥 \(k_i^0\) 和 \(k_i^1\)，分别对应比特值 0 和 1——这两个密钥被称为线路标签（wire label）。对于每个门（以 AND 门为例），混淆方构造一张混淆真值表（garbled truth table）：对输入线路标签的每种组合，用双重加密（double encryption）将对应的输出线路标签加密。真值表的四行被随机打乱（permute），使求值方无法从行的位置推断输入比特。

求值方持有每条输入线路上的一个标签（通过 OT 获得自己输入对应的标签，由混淆方直接发送混淆方输入对应的标签），逐门解密混淆真值表，最终得到输出线路上的标签。混淆方提供输出解码表（output decoding table），将输出标签映射回明文比特。

笔者认为，Yao 的混淆电路是 MPC 领域中概念上最令人惊叹的结果。它的核心洞察——可以「加密一个计算过程」，使得某个人能够正确执行这个计算，却对计算的中间状态一无所知——在直觉上几乎和零知识证明一样反直觉。想象一下：你把一个完整的程序交给别人去运行，对方忠实地执行了每一步、得到了正确的输出，但自始至终不知道程序内部发生了什么。混淆电路告诉我们，这不是魔术，而是可以严格构造的密码学对象。从更宏观的视角看，Yao 的这个构造实际上是「计算与知识可以分离」这一深刻命题的第一个完整证明——你可以让某人为你计算，而不赋予他关于计算内容的任何知识。

3.2 优化技术

经过三十余年的发展，混淆电路的效率得到了显著提升。以下逐项展开四种核心优化，重点补充 Free XOR 和 Half Gates 的证明直觉。

点与置换（point-and-permute）：在每个线路标签的最低位附加一个随机置换比特（permute bit），使求值方能够直接定位应解密的行，而无须逐行尝试解密。这将每个门的解密操作从平均 2.5 次降低到恰好 1 次。

自由异或（Free XOR）：由 Kolesnikov 和 Schneider 在 2008 年提出。混淆方在初始化阶段选择一个全局随机偏移量 \(\Delta \in \{0,1\}^\kappa\)（最低位置 1 以兼容 point-and-permute），并对每条线路 \(i\) 令 \(k_i^1 = k_i^0 \oplus \Delta\)。XOR 门的求值不需要混淆真值表：求值方直接计算 \(k_c = k_a \oplus k_b\) 即可。

正确性证明如下。设求值方持有标签 \(k_a^{v_a}\) 和 \(k_b^{v_b}\)，其中 \(v_a, v_b\) 是实际比特值。由构造：

\[k_a^{v_a} \oplus k_b^{v_b} = (k_a^0 \oplus v_a \Delta) \oplus (k_b^0 \oplus v_b \Delta) = (k_a^0 \oplus k_b^0) \oplus (v_a \oplus v_b)\Delta\]

令 \(k_c^0 = k_a^0 \oplus k_b^0\)，则上式恰好等于 \(k_c^0 \oplus (v_a \oplus v_b)\Delta = k_c^{v_a \oplus v_b}\)——正是输出线路上与 XOR 结果对应的标签。整个过程零密文、零通信、零密码学运算，因此称为”免费”。

安全性方面，由于 \(\Delta\) 贯穿所有线路，敌手看到的多个标签之间存在固定的异或相关。标准的 PRF/随机预言机模型不足以覆盖这种循环依赖，因此 Free XOR 引入了循环相关鲁棒性（circular correlation robustness）假设：哈希函数 \(H\) 在输入与 \(\Delta\) 存在异或相关时仍表现为随机函数。该假设弱于随机预言机假设，且在实践中被广泛接受。

半门（Half Gates）：由 Zahur、Rosulek 和 Evans 在 2015 年提出，将 AND 门的密文从 4 个（朴素方案）压缩到 2 个，并被证明是 Free XOR 兼容方案的理论下界。

核心思想是将 AND 门 \(c = a \cdot b\) 拆分为两个”半门”，每个半门恰有一方知道其中一个输入比特，因此各只需 1 个密文：

• 混淆方半门（generator half-gate）：混淆方知道 \(a\) 的真实值 \(v_a\)。取一个混淆方选定的随机比特 \(r\)，构造一个计算 \(v_a \cdot r\) 的混淆子电路。因为混淆方同时知道 \(v_a\) 和 \(r\)，它可以利用 garbled row reduction 将真值表压缩为 1 行密文。
• 求值方半门（evaluator half-gate）：求值方知道 \(b\) 的真实值 \(v_b\)。令求值方在求值过程中获知 \(v_b \oplus r\)（这不泄露 \(v_b\)，因为 \(r\) 是随机掩码），构造一个计算 \(a \cdot (v_b \oplus r)\) 的混淆子电路。因为求值方知道 \(v_b \oplus r\)，此子电路同样只需 1 行密文。

最终输出通过 Free XOR 合并：\(a \cdot b = a \cdot r \oplus a \cdot (b \oplus r)\)，正确性由 \(a \cdot r \oplus a \cdot (b \oplus r) = a \cdot (r \oplus b \oplus r) = a \cdot b\) 直接可验。每个 AND 门共传输 2 个密文（\(2\kappa\) 比特），相比朴素方案减少 50%，相比 GRR3 减少 33%。

以 \(\kappa = 128\) 为例，一个包含 \(10^6\) 个 AND 门的电路：朴素方案需传输 \(4 \times 16 \times 10^6 = 64\) MB 的密文，Half Gates 仅需 \(2 \times 16 \times 10^6 = 32\) MB。若电路中 XOR 门占比 60%（这在 AES 等对称密码电路中很常见），则 Free XOR 进一步将实际通信量降低至仅覆盖 40% 的 AND 门，最终通信量约 12.8 MB——相比朴素方案的 64 MB 压缩了 80%。这两项优化的叠加效应，是混淆电路从理论构造走向实用系统的关键推动力。

行约减（row reduction）：通过巧妙地选择输出标签，使混淆真值表的某一行变为全零，从而无需传输该行。GRR3（garbled row reduction 3）将每个门的密文从 4 个减少到 3 个。Half Gates 出现后，GRR3 在新设计中已较少使用，但在不兼容 Free XOR 的场景下仍有价值。

下表汇总各优化方案每个 AND 门所需的密文数量：

个人思考。 从朴素方案的 4 个密文到 Half Gates 的 2 个密文，每个 AND 门的通信量减少了一半——这看似不大，但对于包含数十亿门的现代电路（如 AES-128 的标准电路约 6800 个 AND 门，SHA-256 约 22500 个）而言，节省的带宽是以 GB 计的。更深刻的是，Free XOR 改变了电路设计者的思维方式：既然 XOR 门是免费的，那么应该穷尽一切手段将逻辑用 XOR 表达——这催生了大量”XOR 友好”的密码学原语和电路优化研究。Half Gates 的 2 密文下界则意味着，在当前的混淆范式下，AND 门的开销已经不可能再降低了。未来的突破需要全新的范式，例如基于函数秘密共享的方案。

3.3 简化混淆电路的 Python 示例

以下代码演示了单个 AND 门的混淆电路构造与求值过程（仅用于教学说明，不可用于生产环境）：

import os
import hashlib

def H(k1: bytes, k2: bytes, gate_id: int) -> bytes:
    """双重密钥哈希：H(k_a || k_b || gate_id)，输出 16 字节。"""
    data = k1 + k2 + gate_id.to_bytes(4, "big")
    return hashlib.sha256(data).digest()[:16]

def xor(a: bytes, b: bytes) -> bytes:
    return bytes(x ^ y for x, y in zip(a, b))

def garble_and_gate():
    """混淆一个 AND 门并求值。"""
    # 为输入线路 A、B 和输出线路 C 各生成两个 16 字节标签
    kA = [os.urandom(16), os.urandom(16)]   # kA[0], kA[1]
    kB = [os.urandom(16), os.urandom(16)]   # kB[0], kB[1]
    kC = [os.urandom(16), os.urandom(16)]   # kC[0], kC[1]

    gate_id = 0

    # --- 混淆方：构造混淆真值表 ---
    table = []
    for a in (0, 1):
        for b in (0, 1):
            out_bit = a & b                  # AND 逻辑
            mask = H(kA[a], kB[b], gate_id)
            ct = xor(mask, kC[out_bit])
            # 附加置换比特以实现 point-and-permute
            table.append((a, b, ct))

    # 按置换比特随机打乱（此处简化为直接随机排列）
    import random
    random.shuffle(table)

    # --- 求值方：拥有 kA[a_real] 和 kB[b_real]，尝试解密 ---
    a_real, b_real = 1, 1                    # 假设真实输入均为 1
    eval_key_a = kA[a_real]
    eval_key_b = kB[b_real]

    # 逐行尝试解密（简化版本，无 point-and-permute）
    expected_output = kC[a_real & b_real]
    mask = H(eval_key_a, eval_key_b, gate_id)
    for (_, _, ct) in table:
        candidate = xor(mask, ct)
        if candidate == kC[0] or candidate == kC[1]:
            result_label = candidate
            break

    # 输出解码
    result_bit = 0 if result_label == kC[0] else 1
    print(f"输入: A={a_real}, B={b_real}")
    print(f"AND 门输出: {result_bit}")
    assert result_bit == (a_real & b_real), "求值错误！"
    print("混淆电路求值正确")

if __name__ == "__main__":
    garble_and_gate()

四、GMW 协议

4.1 基于秘密共享的多方计算

GMW 协议（Goldreich-Micali-Wigderson，1987）为多方安全计算提供了另一条技术路线——基于秘密共享（secret sharing）而非混淆电路。GMW 协议的核心思想是：每个参与方持有电路中每条线路值的一个加法份额（additive share），通过交互式协议维护这些份额在电路求值过程中的正确性。

对于 \(n\) 个参与方的情形，线路 \(w\) 的值 \(v\) 被拆分为 \(n\) 个随机比特 \(v_1, v_2, \ldots, v_n\)（满足 \(v = v_1 \oplus v_2 \oplus \cdots \oplus v_n\)）。各参与方 \(P_i\) 持有份额 \(v_i\)。

XOR 门的处理是本地的：若两条输入线路的份额分别为 \(a_i\) 和 \(b_i\)，则输出线路的份额为 \(c_i = a_i \oplus b_i\)。正确性显而易见：\(\bigoplus_i c_i = \bigoplus_i (a_i \oplus b_i) = (\bigoplus_i a_i) \oplus (\bigoplus_i b_i)\)。

AND 门的处理需要交互。以两方为例：\(a \cdot b = (a_1 \oplus a_2)(b_1 \oplus b_2) = a_1 b_1 \oplus a_1 b_2 \oplus a_2 b_1 \oplus a_2 b_2\)。项 \(a_1 b_1\) 和 \(a_2 b_2\) 各方可以本地计算，而交叉项 \(a_1 b_2\) 和 \(a_2 b_1\) 涉及两方的私有数据，需要通过 1-out-of-4 OT（或两次 1-out-of-2 OT）来完成。

4.2 GMW 的通信模式

GMW 协议的一个重要特点是其通信复杂度与电路深度成正比——每一层（level）的门可以并行处理，但层与层之间需要同步。这意味着 GMW 在电路深度较浅时（如并行友好的计算）效率较高，但对于深度较大的电路则需要更多轮交互。相比之下，Yao 的混淆电路具有常数轮复杂度（constant round），但通信量更大。

4.3 恶意安全：切割选择

将混淆电路协议从半诚实安全提升到恶意安全的经典方法是切割选择（cut-and-choose）。其基本流程如下：混淆方生成 \(s\) 个独立的混淆电路，求值方随机选择其中一部分（约 60%）进行”打开”验证（检查混淆是否正确），其余部分用于实际求值，通过多数投票确定最终结果。

代价量化。 安全参数 \(s\) 直接决定作弊检测概率：若混淆方在 \(s\) 个电路中植入至少一个恶意电路，该恶意电路恰好全部落入求值集（而非检查集）的概率不超过 \(2^{-s}\)。例如 \(s = 40\) 对应约 \(10^{-12}\) 的作弊成功率，\(s = 128\) 则达到密码学标准安全级别。通信开销为半诚实方案的 \(s\) 倍——以 \(s = 40\) 计，一个原本 10 MB 的混淆电路膨胀到 400 MB，这在广域网下几乎不可接受。此外还需对每条输入线路执行 \(s\) 次 OT 或 OT 的一致性证明，计算开销同样乘以 \(s\)。

下表直观展示不同安全参数下 cut-and-choose 的代价（基线为半诚实混淆电路 10 MB 通信量）：

近年改进。 学术界在过去十年持续压缩 cut-and-choose 的开销：

• 单次执行（single-execution）方案（Lindell，2013）：利用可提取的承诺（extractable commitment）与零知识证明将多个电路的正确性约束到一次执行上，将通信倍率从 \(s\times\) 降低到 \(3\)–\(5\times\)。
• LEGO（Frederiksen 等人，2013；Nielsen-Orlandi，2009）：将 cut-and-choose 的粒度从”整电路”下沉到”单个门”。先对大量 AND 门做 cut-and-choose 验证，再用同态承诺将验证通过的门”焊接”成完整电路。这一方法的摊销效率更高，尤其适合电路规模很大的场景。
• 认证混淆（authenticated garbling）（Wang-Ranellucci-Katz，2017）：完全放弃 cut-and-choose 范式，转而为每个线路标签附加信息论 MAC。恶意混淆方若篡改任何门的逻辑，将以压倒性概率导致 MAC 校验失败。该方法将恶意安全的开销降低到仅约半诚实方案的 \(2\times\)，是目前两方恶意安全混淆电路的最优实践。

下表汇总各恶意安全提升技术相对于半诚实基线的通信倍率：

从上表可以看出，恶意安全的实际代价已从早期的 \(40\)–\(128\) 倍压缩到 \(2\) 倍左右。这一进展意味着恶意安全不再是”理论上可行但实践中太贵”的选项——在大多数场景中，为获得抵抗主动攻击的安全保证而付出 \(2\times\) 的额外通信，是完全可以接受的工程权衡。

后续工作中，Lindell 还提出了更高效的基于两次执行的恶意安全协议，以及基于全局 cut-and-choose 的方案，持续推动实用恶意安全两方计算的发展。

五、BGW 协议

5.1 信息论安全的 MPC

BGW 协议（Ben-Or-Goldwasser-Wigderson，1988）实现了一个里程碑式的成果：在诚实多数假设下，可以无需任何密码学假设（仅依赖信息论安全性）完成安全多方计算。具体而言，当被腐败的参与方数量 \(t < n/2\)（半诚实模型）或 \(t < n/3\)（恶意模型）时，BGW 协议能够信息论安全地计算任意函数。

BGW 协议基于 Shamir 秘密共享方案。每个输入值 \(x_i\) 被表示为有限域 \(\mathbb{F}_p\) 上的元素，由 \(P_i\) 使用 \(t\) 阶多项式进行 Shamir 秘密共享。线路上的值以 Shamir 份额的形式分布在 \(n\) 个参与方之间。

5.2 加法与乘法

加法门是本地操作：各方将对应份额相加即可，因为 Shamir 秘密共享具有线性同态性——两个 \(t\) 阶多项式之和仍是 \(t\) 阶多项式，其常数项恰好是两个秘密之和。

乘法门更为复杂。若两条输入线路的值分别由 \(t\) 阶多项式 \(f(x)\) 和 \(g(x)\) 共享，则乘积由 \(h(x) = f(x) \cdot g(x)\) 定义，这是一个 \(2t\) 阶多项式。问题在于 \(2t\) 阶的份额不再与后续操作兼容（后续操作要求 \(t\) 阶份额）。因此需要一个度约减（degree reduction）步骤：各方利用线性重组技术，将 \(2t\) 阶多项式的份额转换为同一秘密值的 \(t\) 阶多项式的份额。这要求 \(2t + 1 \leq n\)，即 \(t < n/2\)。

5.3 Beaver 乘法三元组

Beaver 在 1991 年提出了乘法三元组（multiplication triples）技术，将乘法门的在线计算与预处理阶段分离。预处理阶段生成大量形如 \((a, b, c)\) 的随机三元组，其中 \(c = a \cdot b\)，以秘密共享的形式分布给各参与方。

在线阶段，当需要计算 \(x \cdot y\) 时，各方执行以下步骤：

1. 打开（reveal）\(\epsilon = x - a\) 和 \(\delta = y - b\)（这些差值不泄露 \(x\) 和 \(y\) 的信息，因为 \(a\) 和 \(b\) 是随机的）。
2. 本地计算 \(z = c + \epsilon \cdot b + \delta \cdot a + \epsilon \cdot \delta\)。

由于 \(z = ab + (x-a)b + (y-b)a + (x-a)(y-b) = xy\)，正确性得证。这一技术的优美之处在于：预处理阶段与具体的计算任务无关（function-independent），可以提前离线完成，大幅降低了在线阶段的延迟。

Beaver 三元组的思想影响深远，它为后续所有预处理模型协议奠定了基础。SPDZ、MASCOT、Overdrive 等现代协议的在线阶段本质上都是对 Beaver 乘法技术的直接应用，区别仅在于三元组的生成方式和认证机制不同。理解 Beaver 三元组，就掌握了理解整个预处理模型 MPC 体系的钥匙。

六、SPDZ 与现代实用协议

6.1 预处理模型

SPDZ（读作”Speedz”）协议由 Damgård 等人在 2012 年提出，是当前最具影响力的实用 MPC 协议之一。SPDZ 采用预处理模型（preprocessing model）：将协议分为离线阶段（offline phase / preprocessing phase）和在线阶段（online phase）。

离线阶段使用较重的密码学工具（如同态加密或 OT）生成大量与具体计算无关的相关随机性（correlated randomness），包括 Beaver 乘法三元组以及用于验证正确性的认证信息。在线阶段仅使用对称密码学和简单的秘密共享操作，效率极高。

6.2 认证份额

SPDZ 最核心的创新是认证份额（authenticated shares）机制。每个秘密值 \(x\) 不仅被加法秘密共享为 \(x_1, x_2, \ldots, x_n\)（满足 \(\sum x_i = x\)），还附带一个全局的消息认证码（MAC）。具体而言，存在一个全局密钥 \(\alpha\)（以秘密共享的形式分布，任何单方都不知道完整的 \(\alpha\)），对每个共享值 \(x\) 存在 \(\gamma = \alpha \cdot x\)（同样以秘密共享形式分布）。

当需要打开一个共享值时，各方不仅发送自己的份额，还发送对应的 MAC 份额。其他参与方可以验证 MAC 的正确性，从而检测到任何恶意行为。这一机制保证了即使在恶意模型下，敌手也无法篡改计算结果——任何偏离协议的行为都会导致 MAC 验证失败。

关键的安全性分析表明：如果敌手试图将打开的值篡改 \(\delta \neq 0\)，它需要相应地篡改 MAC 值 \(\alpha \cdot \delta\)，但由于 \(\alpha\) 对敌手而言是未知的（信息论意义上的隐藏），篡改被检测到的概率为 \(1 - 1/|\mathbb{F}|\)，在足够大的域上这一概率可忽略不计。

6.3 MASCOT 与 Overdrive

SPDZ 的离线阶段最初基于 somewhat homomorphic encryption（SHE），计算和实现复杂度较高。后续工作发展了多种替代方案：

MASCOT（Keller-Orsini-Scholl，2016）使用 OT 扩展替代同态加密来生成乘法三元组，大幅简化了实现并提高了效率。其核心是利用相关 OT 构造认证乘法三元组，结合一致性检查保证恶意安全。

Overdrive（Keller-Pastro-Rotaru，2018）回到基于同态加密的路线，但使用了更高效的 LWE 基同态加密方案，并改进了三元组生成的摊销效率。

SPDZ2k（Cramer 等人，2018）将 SPDZ 框架从素数域扩展到环 \(\mathbb{Z}_{2^k}\)，使其对整数运算更加友好，避免了素数域算术的开销。

6.4 主流协议横向对比

下表从协议模型、安全性、计算表示、通信复杂度等维度对四大经典协议族进行系统对比，以便读者根据应用场景快速选型。表中 \(|C|\) 表示电路门数，\(D\) 表示电路深度，\(n\) 表示参与方数，\(\kappa\) 表示安全参数（如 128）。

以 AES-128 电路（约 6800 AND 门、25000 XOR 门）为参考：Yao GC + Half Gates 的在线通信量约 6800 \(\times\) 32 字节 \(\approx\) 213 KB，一次交互即可完成；GMW 需约 \(D \approx 40\) 轮交互，每轮通信量取决于该层 AND 门数量；SPDZ 在线阶段仅需每乘法门广播两个域元素，但需提前生成等量的 Beaver 三元组。这一对比清楚地展示了”通信量 vs 轮数”的核心权衡。

选型建议。 广域网 + 两方场景优先考虑 Yao GC（常数轮优势突出）；局域网 + 多方场景优先考虑 SPDZ（在线阶段极快，预处理可离线完成）；若参与方间可保证诚实多数，BGW 提供最强的信息论安全保证且无需密码学假设；GMW 在需要布尔电路 + 多方的组合中仍有独特价值，且其 OT-based 设计与现代 OT 扩展技术高度兼容。

值得注意的是，上述四个协议并非互斥关系。现代 MPC 框架（如 ABY、MP-SPDZ）通常支持在同一计算中混合使用多种协议：线性层用算术秘密共享（SPDZ），非线性比较用布尔混淆电路（Yao），二者之间通过高效的份额转换协议（share conversion）衔接。这种混合方案在隐私保护机器学习推理中尤为常见，往往能同时发挥各协议的最优特性。

实际选型时还需考虑工程因素：团队对框架的熟悉程度、已有基础设施对特定网络拓扑的支持、以及是否有现成的经过审计的实现。协议的理论最优不等于工程最优。

七、MPC 编译器与框架

7.1 从高级语言到电路

MPC 协议的理论基础建立在布尔电路或算术电路之上，但直接手工编写电路是不切实际的。MPC 编译器和框架的作用是将高级语言编写的计算任务自动转换为适合 MPC 协议执行的电路表示，并处理所有底层的密码学操作。

电路表示通常有两种形式：布尔电路（Boolean circuit），由 AND、XOR、NOT 门组成，适用于混淆电路类协议；算术电路（arithmetic circuit），由加法门和乘法门组成，适用于秘密共享类协议。某些框架还支持混合电路（mixed circuit），在同一计算中灵活切换布尔和算术表示。

7.2 主流框架

MP-SPDZ（由 Marcel Keller 开发维护）是当前功能最全面的 MPC 框架，支持超过 30 种协议变体，包括 SPDZ、MASCOT、semi-honest Yao、BMR、Shamir-based BGW 等。用户使用类 Python 的领域特定语言编写计算逻辑，框架自动处理编译、秘密共享和协议执行。

EMP-toolkit（Efficient Multi-Party computation toolkit）由王潇然等人开发，专注于两方计算场景，提供了高效的混淆电路和 OT 实现。其设计强调灵活性和可组合性，允许研究者快速原型化新的协议优化。

ABY（Arithmetic-Boolean-Yao）框架支持三种共享类型之间的高效转换，用户可以为计算的不同部分选择最合适的表示方式。例如，比较操作适合用布尔电路表示，而大整数乘法适合用算术电路表示。

Obliv-C 是 C 语言的扩展，通过引入 obliv 关键字标记需要安全计算的变量，编译器自动将对应代码转换为混淆电路协议。这种方法对 C 程序员非常友好，降低了 MPC 编程的门槛。

7.3 电路优化

电路优化对 MPC 性能有决定性影响。常用技术包括：将乘法门数量最小化（在算术电路中，乘法门需要通信，加法门不需要）；利用 Free XOR 优化将逻辑尽量用 XOR 门表达；使用查找表（lookup table，LUT）替代深度较大的子电路以减少交互轮数。Bristol Fashion 是一种广泛使用的布尔电路描述格式，许多框架都支持该格式的电路导入。

八、隐私保护应用

8.1 隐私集合求交

隐私集合求交（Private Set Intersection，PSI）是 MPC 最成功的应用之一。两方各持有一个元素集合，希望计算两个集合的交集，但不泄露交集以外的任何元素。PSI 在联系人发现（如 Apple 和 Google 的隐私联系人匹配）、广告转化率衡量、以及数据库连接等场景中有广泛应用。

现代 PSI 协议通常基于 OT 扩展和布谷鸟哈希（cuckoo hashing）构建，可在百万级集合上在数秒内完成。KKRT16（Kolesnikov-Kumaresan-Rosulek-Trieu）协议利用 OT 扩展实现了接近线性的通信复杂度和极高的计算效率。后续的 PSI 协议进一步支持了更丰富的功能，如基于阈值的 PSI（threshold PSI）、PSI-Cardinality（仅返回交集大小）以及 Circuit-PSI（在交集上执行任意函数）。

8.2 隐私保护机器学习

隐私保护机器学习（Privacy-Preserving Machine Learning，PPML）是 MPC 当前最活跃的研究方向之一。典型场景包括：多个医疗机构希望在不共享原始患者数据的前提下联合训练疾病预测模型；云服务提供商希望为用户提供模型推理服务，但不暴露模型参数（模型是商业秘密），用户也不希望暴露自己的查询数据。

在推理阶段，混淆电路和秘密共享可以高效地实现神经网络中的关键操作：线性层（矩阵乘法）适合用算术秘密共享处理，非线性激活函数（如 ReLU 的比较操作）适合用混淆电路或布尔秘密共享处理。CrypTFlow2、MOTION、SecFloat 等框架针对机器学习工作负载进行了深度优化。

训练阶段的 MPC 仍然面临巨大的效率挑战，因为训练涉及大量的迭代计算和梯度更新。当前的实践通常将 MPC 与联邦学习（federated learning）、差分隐私（differential privacy）等技术结合使用。

8.3 经典小规模应用

MPC 的教科书级应用包括：百万富翁问题（比较两个数的大小而不泄露具体值）、薪资比较（一组员工计算平均薪资而不透露个人薪资）、密封拍卖（投标者提交密封出价，协议确定最高出价及赢家而不泄露其他出价）。这些场景虽然简单，却清楚地展示了 MPC 的核心价值。

丹麦的甜菜拍卖（Danish Sugar Beet Auction）是 MPC 最早的实际部署案例之一：2008 年，丹麦的甜菜种植者使用基于 Shamir 秘密共享的 MPC 协议进行了甜菜合同的双重拍卖，各方的出价在整个过程中保持私密。

九、MPC 的性能与部署

9.1 通信与计算复杂度

MPC 协议的效率主要受两个因素制约：通信复杂度（communication complexity）和交互轮数（round complexity）。

对于混淆电路类协议，通信量与电路中 AND 门的数量成正比（XOR 门免费），但轮数为常数（通常 2-3 轮）。对于秘密共享类协议，通信量通常更低（每个乘法门仅需要传输几个域元素），但轮数与电路深度成正比。在广域网（WAN）环境下，轮数往往是性能瓶颈；在局域网（LAN）环境下，通信带宽和计算速度更为关键。

SPDZ 类协议的一大优势是在线阶段极为高效：每个乘法门仅需每方广播两个域元素，加法门完全本地计算。预处理阶段的通信量较大，但可以提前离线完成。

一个经常被忽视的观点是：MPC 在实际部署中的真正瓶颈不是计算，而是通信。从工程实践来看，现代 CPU 执行对称密码运算的速度极快（AES-NI 可以达到每秒数十亿次），但跨广域网的一次往返延迟就是 50-200 毫秒。对于一个深度为 d 的电路，秘密共享类协议需要 O(d) 轮交互——如果电路深度为 100 且每轮需要一次网络往返，那么仅通信延迟就需要 5-20 秒，而实际的密码学计算可能只需要几毫秒。这就是为什么 MPC 的优化研究中，「减少交互轮数」的优先级远高于「减少门数量」。Yao 的混淆电路之所以在广域网场景中表现优异，不是因为它的通信量更小（恰恰相反，混淆电路的通信量通常比秘密共享方案大得多），而是因为它只需要常数轮交互。这一观察对工程选型有直接的指导意义：在局域网环境中，选择通信量小的秘密共享方案；在广域网环境中，选择轮数少的混淆电路方案。

9.2 真实世界部署

近年来，MPC 从学术研究走向了大规模商业部署，以下是几个标志性案例：

Fireblocks：这家数字资产基础设施公司使用基于 MPC 的阈值签名（threshold signature）方案来保护加密货币私钥。传统方案中，私钥存储在单一设备上，一旦该设备被攻破则私钥完全泄露。MPC 方案将私钥拆分为多个份额（key shares），分布在不同的设备或组织中，签名过程通过 MPC 协议完成，完整的私钥在任何时刻都不会在任何单一位置出现。Fireblocks 的 MPC-CMP 协议支持任意的 \(t\)-of-\(n\) 阈值签名，已保护超过数万亿美元的数字资产转账。

Unbound Tech（现为 Coinbase 收购）：提供基于 MPC 的密钥管理和密码学操作服务，将密钥份额分布在客户端和服务端之间，确保任何单点被攻破都不足以获取完整密钥。

瑞士邮政（Swiss Post）：在电子投票系统中使用 MPC 技术进行选票的安全计票。选票被加密并分发给多个独立的计票服务器，这些服务器通过 MPC 协议联合计算选举结果，确保没有任何单个服务器能够获知个别选民的投票内容。这一应用对 MPC 的正确性和可验证性提出了极高的要求。

波士顿妇女工资差异研究：Boston Women’s Workforce Council 使用 MPC 技术收集和分析波士顿各企业的员工薪资数据，在不泄露任何企业具体薪资信息的前提下计算出按性别和种族划分的薪资差距统计数据。这是 MPC 在社会公益领域的典范应用。

9.3 挑战与展望

尽管 MPC 已经取得了巨大的进展，但在走向更广泛部署的道路上仍面临若干挑战：

效率瓶颈：对于大规模机器学习训练等计算密集型任务，MPC 的开销仍然比明文计算高出数个数量级。硬件加速（如 GPU、FPGA 上的 MPC 加速器）和协议层面的创新是缩小差距的关键方向。

可组合安全性：现实应用中的协议往往需要与其他密码学原语或子协议组合使用。通用可组合性（Universal Composability，UC）框架提供了严格的安全保证，但 UC 安全的协议通常效率更低。如何在安全性和效率之间取得平衡仍是活跃的研究课题。

部署工程挑战：将 MPC 协议集成到现有的软件基础设施中需要解决大量工程问题，包括网络配置、密钥管理、故障恢复和审计日志。MPC 即服务（MPC-as-a-Service）的模式正在兴起，旨在降低部署门槛。

后量子安全：随着量子计算的发展，基于 Diffie-Hellman 或 RSA 假设的 OT 构造将不再安全。基于格（lattice）的 OT 方案已有初步研究成果，但其效率仍需提升。值得注意的是，信息论安全的 MPC 协议（如 BGW）天然不受量子计算威胁，但它们要求诚实多数假设，适用场景有限。

从理论可行性到工业级部署，安全多方计算走过了四十余年的旅程。从姚期智的百万富翁问题到 Fireblocks 的数万亿美元数字资产守护，MPC 正在证明：即使在互不信任的参与方之间，协作计算也可以是安全的、私密的、可验证的。随着隐私法规的日趋严格和数据协作需求的不断增长，MPC 的应用前景将更加广阔。

密码学百科系列 · 第 41 篇

← 上一篇：秘密共享 | 系列目录 | 下一篇：同态加密 →