秘密共享协议与安全多方计算

可视化演示

展示秘密S拆分为5份分片（3/5门限），以及利用拉格朗日插值从任意3份分片重构原始秘密的过程。

秘密共享概述

船长的故事里藏着三个朴素事实：单片碎片看不出宝藏位置；凑够三人就能拼出全图；人数再多也不会让拼图变简单。这三个事实对应秘密共享协议的三个核心概念：碎片、门限、重构。把秘密 S（可以是一个数字、一段密钥、一份模型参数）拆成 n 份碎片分给 n 个参与方，任意 t 份都能还原 S，而任意少于 t 份的碎片即使全部公开，也得不到 S 的任何信息——这就是 (t, n) 门限方案。

“得不到任何信息”不是工程近似，而是信息论意义上的绝对零信息：只拿到 t-1 份碎片时，秘密的每一种取值都有同样可能的碎片组合与之对应，攻击者能做的只有瞎猜。这一性质叫完美安全性，它让秘密共享有别于普通加密：密文靠计算复杂度保护，碎片靠信息论分割保护。门限 t 是安全性与可用性的分界：t 越小容错越强，但小团体合谋风险越高；t 越大保密越好，但对参与方在线率要求越高。

于是船长把“三人成行”写进航海条例；在计算机世界，这条条例被翻译成一段精确的数学公式。门限就是那把尺子，碎片总数则像冗余编制：宁可多备几份，也不让一次海难毁掉整张藏宝图。

加法秘密共享

如果宝藏坐标是一串数字，船长还有更轻巧的办法：把数字 15 拆成三个数的和。他告诉大副“记住 3”、二副“记住 5”、三副“记住 7”。三个数字单独看来毫无含义，只有三人把数字相加，15 才会浮现。这就是加法秘密共享：秘密是若干随机碎片在同一模空间上的和。

设模数 p 是大素数，所有运算都在 0 到 p-1 的整数环上进行。分发时先从模空间均匀随机抽取前 n-1 份碎片，最后一份用秘密减去前面所有碎片得到，这样每份碎片都是均匀随机数，单独看与噪声无异。加法秘密共享最迷人的性质是同态加法：甲持有 x 的碎片、乙持有 y 的碎片，那么同一编号的碎片直接相加，得到的就是 x+y 的合法碎片——各方不需要通信，就能在本地“看不见明文地”完成加法。这份性质是后续安全多方计算处理加法门的基础。

三位副手各自记下一个数字，谁也不知道总数；一旦三人在甲板上碰头把数字相加，宝藏总值瞬间见分晓。加法秘密共享把“每人一块拼图”的直觉变成了可严格证明的数学性质，也是所有共享类安全计算方案的第一块砖。

Shamir 门限方案

加法方案有个不体面的弱点：必须集齐全部碎片。船长可不想因为三副落海而永远失去宝藏。他换了一种藏法：不再把数字拆成加法碎片，而是把秘密当作一条抛物线的“起点高度”，让每个水手记住抛物线上一个点的坐标。三个人各抛出一个点，就能唯一画出一条抛物线，读出起点处的秘密；只有两个点时，穿过它们的抛物线有无数条——秘密依然深藏不露。

这就是 Shamir 门限方案，由密码学家 Adi Shamir（RSA 中的 S）在 1979 年提出。方案随机选择一条 t-1 次多项式，把秘密作为常数项放入多项式，然后在 x = 1, 2, ……, n 处取点，每个点 (i, f(i)) 就是一份碎片。为什么任意 t 个点足够、t-1 个点不够？因为一条 t-1 次多项式恰好由 t 个点唯一确定：拿到 t 个点，就能通过拉格朗日插值重建多项式、读出常数项；拿到 t-1 个点，会得到无穷多条候选多项式，秘密的每个取值都有可能，于是信息量为零。Shamir 方案因此实现了真正的 (t, n) 门限，且是信息论安全的。

三位水手在甲板上各报一个坐标，很快画出一条抛物线，起点高度就是宝藏埋藏的深度；若只来了两位，他们只能面对无数条可能的抛物线面面相觑。Shamir 用一条曲线把“三人成行”的规矩装进了数学保险箱——这份优雅的构造，至今仍是秘密共享领域应用最广的方案。

安全多方计算

新的挑战来了：船长想知道归程所需补给总量，但每个水手都私藏了数量不明的私货，谁也不想当着全船的面报数。更妙的是，他们可以先交换一些“打了马赛克的碎片”，再借助一套协作流程算出总补给量——整个过程没人真正看到别人的数字。这就是安全多方计算（MPC）：n 个参与方分别持有私有输入，共同计算一个函数，最终每个人都只得到输出结果，而彼此的输入保持私密。

安全多方计算的鼻祖是姚期智院士的“百万富翁问题”：两个百万富翁想比较谁更有钱，却都不愿透露自己的财富数额。1986 年姚期智提出混淆电路方案：把要计算的函数转化成布尔电路，一个参与方把电路“打乱”成乱码电路，另一个参与方通过不经意传输获得与自己输入对应的钥匙，在不解密的情况下逐步求值，最终只得到比较结果。安全性则用“模拟范式”刻画：协议运行中参与方看到的一切视图，都能由仅知其自身输入和最终输出的模拟器生成——既然模拟器不看别人输入就能造出相同的视图，说明协议没有泄露多余信息。

水手们互递涂黑的信封，最终每个人手里都多了一张补给总清单，却始终不知道邻座的私货。安全多方计算让“不说真话也能一起办事”从江湖把戏升级为一门严谨的工程学问。

乘法与电路

加法共享就像水手们排队报数相加，简单直接；可一旦要算“私货数量乘以补给单价”，麻烦立刻出现——直接乘碎片会混入交叉项，等于把私货信息暴露在运算结果里。船队需要一种“打码称重”的妙招：先准备好一组三人共同持份的随机数三元组，用它给两端各加一个随机扰动，再把扰动后的值亮出来相乘，最后剥掉扰动，得到正确乘积。

这个妙招叫 Beaver 三元组。预处理阶段，可信任的经销商或协作过程随机生成三元组 (a, b, c)，满足 c = a × b，并把三份碎片分给参与方。计算乘积 x × y 时，各方先在本地计算掩蔽值 d = x − a、e = y − b，并公开 d、e；随后 x × y = d×e + d×b + e×a + c。由于 d、e 带着随机扰动，公开它们不泄露 x、y。展开上式：x×y = (d+a)(e+b) = de + db + ea + ab，其中 ab = c——一次“秘密乘法”被拆成一次公开乘法和几次局部运算。在布尔电路场景中，XOR 门免费，AND 门每扇消耗一个三元组并引入一轮通信。

打码称重的把戏在水手间传开：先给每袋私货盖上随机重量的“官封”，过秤后揭开官封一折算，总重量分毫不差，私货内容却无人知晓。Beaver 三元组就是那组官封——它让“乘法”这道安全计算里最难啃的骨头，变成了人人可做的加法与公开乘法。

工程实践

理论图纸画好，船队终于要启航。真正的远航不比甲板演练：海图要复制几份、通信要靠旗语与信鸽、风暴可能让某只船失联。工程化的秘密共享系统同样要回答三个问题：协议按什么顺序跑、资源花在哪、拿来解决什么业务。这三个问题分别对应协议流程、性能考量与典型应用。

一个典型的共享型 MPC 协议分为离线和在线两阶段。离线阶段（预处理）生成 Beaver 三元组、随机掩码等“耗材”；在线阶段完成输入分发、逐门计算与结果重构。分离的好处是耗材可以提前批量制造，让在线阶段只保留少量交互，显著降低延迟。协议流程概括为：初始化参数 → 分发碎片 → 电路求值 → 门限重构。性能上，乘法门是主要瓶颈：每扇乘法门消耗一个三元组、需要一轮广播，通信量约为乘法门数乘以单份碎片大小。实践中常用批处理、乱序优化与局部通信拓扑来压缩开销；典型应用包括密钥托管、联合统计与联邦学习安全聚合。

当船队真正驶入大洋，船长发现：航速取决于船队中最慢的通信，载货量取决于预先装好的“耗材”，航线图早已由门限与电路深度刻画完毕。秘密共享与 MPC 的工程化，就是把甲板上的默契变成可度量、可优化、可上线的流水线。

AI 应用场景

Python 演示

import random def modinv(a, p):    # 费马小定理求模逆    return pow(a, p - 2, p) def eval_poly(coeffs, x, p):    # 霍纳法求多项式值    val = 0    for c in reversed(coeffs):        val = (val * x + c) % p    return val def share_secret(secret, t, n, p):    # 秘密放常数项 随机挑 t-1 个系数    coeffs = [secret] + [random.randrange(1, p) for _ in range(t - 1)]    return [(i, eval_poly(coeffs, i, p)) for i in range(1, n + 1)] def reconstruct(shares, p):    # 拉格朗日插值 重构 f(0)    result = 0    for i in range(len(shares)):        xi, yi = shares[i]        num = 1        den = 1        for j in range(len(shares)):            if i == j:                continue            num = num * (-shares[j][0]) % p            den = den * (xi - shares[j][0]) % p        result = (result + yi * num * modinv(den, p)) % p    return result if __name__ == "__main__":    p = 2 ** 127 - 1    s = 20240601    t, n = 3, 5    shares = share_secret(s, t, n, p)    print("shares:", shares)    print("recover with 3:", reconstruct(shares[:3], p))    assert reconstruct(shares[:3], p) == s

1. coeffs = [secret] + [random.randrange(1, p) for _ in range(t - 1)]秘密放进常数项，再随机补 t-1 个系数，拼出 t-1 次多项式。
2. return [(i, eval_poly(coeffs, i, p)) for i in range(1, n + 1)]在 x = 1 到 n 上取点，每个点 (i, f(i)) 就是一块碎片。
3. return pow(a, p - 2, p)利用费马小定理求模逆：p 是素数时 a 的逆为 a^(p-2)。
4. num = num * (-shares[j][0]) % p拉格朗日基多项式在 0 点的分子，逐项累乘 (-x_j)。
5. den = den * (xi - shares[j][0]) % p基多项式分母，保证第 i 个基函数在本点取 1。
6. result = (result + yi * num * modinv(den, p)) % p每份碎片乘以对应权重后累加，权重就是 num/den 的模逆结果。
7. p = 2 ** 127 - 1大素数梅森素数，提供足够大的有限域，也便于模逆运算。

常见误区

面试题