安全多方计算：混淆电路与秘密共享

密码学 2026-08-25 · 阅读约 24 分钟

安全多方计算（MPC）研究的是这样一个问题：多个互不信任的参与方，能不能在不泄露各自私有输入的前提下，共同算出一个约定函数的结果？经典表述是百万富翁问题：两个富豪想知道谁更有钱，却谁也不愿说出自己的资产。这个问题不是思想实验——联合风控、跨机构医疗统计、隐私求交、阈值签名、密封拍卖，本质都是同一类计算。本文聚焦 MPC 的两条主干技术：秘密共享把数据拆成『单独看毫无意义』的份额，混淆电路把任意布尔电路改造成『只能得到输出、看不到输入』的加密电路，并用一段可运行实验把三条关键性质跑出来。

一、MPC 的安全目标：不只保密，还要可控

MPC 的最低目标是隐私性：各方除了函数输出和自身输入外，学不到任何额外信息。更强的工程目标还包括：

  • 正确性：输出必须等于在明文集上直接计算的结果；
  • 输入独立性：任何一方不能先看到别人的输入再决定自己的输入；
  • 公平性与保证输出：理想情况下要么大家都拿到结果，要么谁都拿不到；
  • 抗恶意行为：基础模型常假设半诚实（按协议执行但好奇记录中间值），生产系统往往还要防恶意方篡改消息。

这解释了为什么 MPC 协议看起来『绕』：它保护的不仅是数据内容，还包括计算过程、参与者的行为，以及结果发布方式。

二、秘密共享：把秘密拆成『份额』

1. Shamir 门限共享

Shamir (t,n) 门限共享把秘密 s 藏进一个 t-1 次随机多项式的常数项：任选随机系数构造 f(x)，令 f(0)=s，再分别计算 f(1)…f(n) 分发给 n 个参与方。任意 t 份可用拉格朗日插值重构 f(0)，少于 t 份则在信息论意义上得不到 s 的任何信息。本文实验用 2-of-3：任意两份都能恢复秘密 20260825，而单独一份配合任意猜测都可以『解释』成任意秘密，所以单份零泄露。

2. 加法共享与联合求值

如果目标是加法型统计，更轻量的方案是加法秘密共享：每方把私有输入 w 拆成三份随机数 r1、r2、r3，使 w = r1 + r2 + r3 (mod P)，把份额分给三方；随后每方只公开自己收到的份额之和。由于和的份额等于份额的和，三方公开局部和后再相加，就得到总和与平均值，而任何原始工资都没有离开过本人手里。

三、混淆电路：把函数本身加密

姚氏混淆电路（Yao's Garbled Circuits）适合两方通用计算。以 AND 门为例：

  1. 生成方为两条输入线的 0/1 各生成随机标签 A0/A1、B0/B1；
  2. 对真值表四行分别用『两个输入标签』加密对应输出，得到四行密文并打乱顺序；
  3. 求值方拿到自己输入对应的标签，再通过不经意传输（OT）拿到对方输入对应的标签；关键是自己不知道标签对应 0 还是 1，对方也不知道求值方选了哪个标签；
  4. 求值方用两个标签逐行尝试解密，只有匹配真实输入组合的那一行能解开，得到输出比特；其余三行仍是乱码。

把每个门都这样做，再按电路拓扑级联，就得到整个函数的混淆电路。它的强项是通用：任何能写成布尔电路的函数都能算；弱项是通信与电路规模——AES 这类函数会展开成数万门，OT 与密文传输成本迅速上升。因此现代通用 MPC 常把『算术电路用秘密共享、比较/选择等布尔部分用混淆电路』混合使用。

四、动手实验：三条性质一次跑通

实验在您服务器上以 Python 3 直接运行，覆盖三部分：Shamir 2-of-3 门限共享、加法共享联合求平均工资、混淆电路 AND 门求值。核心片段：

# Shamir: f(0)=secret, 任意两份拉格朗日插值重构
secret = 20260825
shares = shamir_split(secret, n=3, t=2)
assert shamir_recover([shares[0], shares[1]]) == secret
assert shamir_recover([shares[1], shares[2]]) == secret

# 加法共享: w = r1+r2+r3 (mod P), 只公开每方收到的份额之和
salaries = [30000, 50000, 70000]
shares_out = []
for w in salaries:
    r1, r2 = random.randrange(P), random.randrange(P)
    r3 = (w - r1 - r2) % P
    shares_out.append((r1, r2, r3))
total = sum(sum(s[k] for s in shares_out) % P for k in range(3)) % P
assert total == sum(salaries)

# 混淆电路: 求值方持 A1、B1 标签, 只能解开 AND(1,1)=1 那一行
k = sha256((A1 + B1).encode()).hexdigest()[:16]
opened = []
for row in garbled:
    plain = xor(row, k)
    if plain[1:] == plain[0] * 15:
        opened.append(plain[0])
assert opened == ['1']

真实运行输出：

== Shamir 2-of-3 秘密共享 ==
  秘密: 20260825
  份额 x=1: y=66...1
  份额 x=2: y=307...52
  份额 x=3: y=548...6
  份额(1,2)重构: 20260825 OK
  份额(1,3)重构: 20260825 OK
  份额(2,3)重构: 20260825 OK
  单份+猜测可"重构"出任意值(如 164697078437745750805658675357478089067), 说明单份零泄露

== 加法秘密共享: 三方联合求平均工资 ==
  各方份额之和(公开): 73483..., 87621..., 350...
  联合计算平均工资: 50000 (真实均值 50000)
  -> 全程没有任何一方的原始工资离开过自己手里

== 混淆电路: AND 门(姚氏) ==
  求值方持标签 (A?, B?), 逐行尝试解密
  成功解开的行输出: ['1'] (AND(1,1)=1)
  其余 3 行解密为乱码, 求值方无法得知对方的实际输入比特

PASS: 门限共享可重构且单份零泄露; 加法共享完成联合均值; 混淆电路只暴露输出

五、结果解读

  • 门限共享的核心不是『拆开』，而是『少于阈值无任何信息』。实验中任意两份都能恢复同一个秘密，而单份加上任意猜测可以重构出一个完全不同的值——这不是数据损坏，而是信息论安全的直观体现：单份份额对所有候选秘密都等可能。
  • 加法共享把『计算』变成了『公开局部和』。三方平均工资正确等于 50000，但公开的只是三个份额局部和；从局部和反推个人工资在模意义下有无数解。它适合求和、计数、均值这类线性统计；一旦进入乘法、比较、分支，就需要 Beaver 三元组、混淆电路或更重的协议。
  • 混淆电路的关键是『标签不可辨』。求值方拿着 A1、B1 两个标签，却不知道它们代表 0 还是 1；四行密文里只有对应真实输入组合的一行可解。实验里输出恰好是 ['1']，其余行乱码，说明电路只暴露最终输出，不暴露输入路径。
  • 一次有教学价值的修复：初版混淆电路演示把输出行用空格补齐长度，却又要求整行都是同一字符，导致求值方一行也解不开；更严重的是异常被过宽的捕获吞掉，末尾仍打印通过。修正后让加密行用输出字符自身填充，并让断言失败直接暴露。MPC 实现尤其要遵守『失败必须响亮』：协议错一个字节，结果就可能从安全变成看似安全的错误。

六、工程应用

  • 阈值密钥管理：把签名私钥做 t-of-n 分片，配合阈值签名或多签托管，避免单点私钥泄露；
  • 隐私求交（PSI）：银行与平台找出共同客户，却不交换完整客户名单；
  • 联合统计与联邦分析：多家机构在不出原始数据的情况下计算均值、分布、风险指标；
  • 安全机器学习：秘密共享负责线性层，混淆电路负责比较/激活/选择，典型框架有 ABY、MP-SPDZ、CrypTen；
  • 密封拍卖与链上治理：各方提交加密出价，合约只公开最高价或胜出者，不公开全部报价。

七、常见误区

  1. 把秘密共享当成加密算法：份额本身不是密文，没有重构阈值就得不到秘密；但份额分发、存储、重构过程仍需要认证信道，否则会被替换份额攻击。
  2. 只看功能正确，不看安全模型：半诚实协议能防好奇但守规矩的参与方，防不了篡改消息的恶意方；生产场景要明确是否需要 malicious security。
  3. 低估 OT 与电路规模成本：混淆电路通用但重，AES/比较器/排序都会迅速放大通信量；能算术化的部分尽量交给秘密共享。
  4. 忽略元数据泄露：即使输入保密，计算耗时、通信量、访问模式也可能泄露分支走向；高敏场景需要恒定时间电路与流量整形。
  5. 把输出发布当成协议终点：输出本身可能反推输入（例如『平均工资+已知两人工资』泄露第三人）。MPC 只保证过程不泄露，不保证结果不携带推断风险，必要时叠加差分隐私。

八、参考文献

  • Shamir, A. How to Share a Secret. Communications of the ACM 22(11), 1979.
  • Yao, A. C. How to Generate and Exchange Secrets. FOCS 1986（混淆电路奠基）.
  • Goldreich, O., Micali, S., Wigderson, A. How to Play any Mental Game. STOC 1987.
  • Beaver, D. Efficient Multiparty Protocols Using Circuit Randomization. CRYPTO 1991（Beaver 三元组）.
  • Demmler, D., Schneider, T., Zohner, M. ABY: A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. NDSS 2015.