安全多方计算中Shamir秘密共享方案的阈值重建与信息论安全

Shamir秘密共享方案是密码学中的一个基础工具，其核心思想是将一个秘密（比如一个密钥）拆分成多个“份额”，分发给不同的参与者。只有收集到足够数量（达到或超过一个设定的阈值 t）的份额，才能重构出原始秘密；少于 t 个份额则无法获得关于秘密的任何信息。这一特性使其成为安全多方计算（MPC）中保障数据安全和隐私的关键组件。

第一步：理解方案的初始化与分发

在开始重建之前，你需要先有一个秘密和参与者。假设秘密是一个数字 s（例如，一个256位的私钥），总共有 n 个参与者。

1. 设定参数：确定 参与者总数 n 和恢复秘密所需的最小阈值 t。t 必须满足 1 <= t <= n。
2. 构造多项式：生成 一个 t-1 次的随机多项式 f(x)。设定 其常数项为秘密 s，即 f(0) = s。多项式系数从有限域（例如模一个大素数 p）中随机选取。
   • 例如，对于 t=3，多项式形如：f(x) = a_0 + a_1*x + a_2*x^2，其中 a_0 = s。
3. 计算并分发份额：为 每个参与者 i （i 从 1 到 n）计算 一个点 (i, f(i))。将 这个点 (i, f(i)) 作为份额，安全地发送 给第 i 个参与者。现在，秘密 s 被巧妙地“隐藏”在这些份额中。

第二步：执行阈值重建

这是从份额恢复秘密的核心过程。假设有至少 t 个诚实参与者，他们愿意贡献自己的份额来重建 s。

1. 收集份额：汇聚 来自 k 个（k >= t）参与者的有效份额。每个份额是一对坐标 (x_j, y_j)，其中 x_j 是参与者的公开标识，y_j = f(x_j)。
2. 执行拉格朗日插值：使用 数学上的拉格朗日插值公式。其目标是根据已知的 t 个点，唯一确定那个 t-1 次多项式 f(x)，然后计算 f(0)。
   • 计算拉格朗日基：对于每一个贡献了份额的参与者 j，计算 其对应的拉格朗日基多项式 L_j(0)。其公式为：
     $$L_j(0) = \prod_{\substack{m=1 \\ m \neq j}}^{t} \frac{0 - x_m}{x_j - x_m} = \prod_{\substack{m=1 \\ m \neq j}}^{t} \frac{-x_m}{x_j - x_m}$$
   • 加权求和：将 秘密 s 计算为 所有份额值 y_j 与对应基 L_j(0) 乘积的和，即：
     $$s = f(0) = \sum_{j=1}^{t} y_j \cdot L_j(0)$$
   • 所有运算都在同一个有限域（模 p）下进行。
3. 恢复秘密：得到 上述计算的结果，这个结果就是原始秘密 s。

举例说明：假设 t=3， n=5，秘密 s=7，模数 p=11。多项式为 f(x) = 7 + 2x + 3x^2 (mod 11)。我们分发份额：f(1)=1， f(2)=5， f(4)=3。现在，用这三个点 (1,1), (2,5), (4,3) 重建：

• 计算 L_1(0) = \frac{(0-2)*(0-4)}{(1-2)*(1-4)} = \frac{8}{3} = 8 * 3^{-1} = 8*4 = 32 ≡ 10 (mod 11)
• 计算 L_2(0) = \frac{(0-1)*(0-4)}{(2-1)*(2-4)} = \frac{4}{-2} = -2 ≡ 9 (mod 11)
• 计算 L_3(0) = \frac{(0-1)*(0-2)}{(4-1)*(4-2)} = \frac{2}{6} = 2 * 6^{-1} = 2*2 = 4 (mod 11)
• 计算 s = 1*10 + 5*9 + 3*4 = 10 + 45 + 12 = 67 ≡ 1 (mod 11)。结果为 1？我们检查一下：f(0)=7，但计算得 1。这揭示了重建过程的精确性：份额必须正确。用正确的份额 (1, f(1)=7+2+3=12≡1), (2, f(2)=7+4+12=23≡1), (4, f(4)=7+8+48=63≡8) 重新计算，L_j(0) 值不变，s = 1*10 + 1*9 + 8*4 = 10+9+32=51 ≡ 7 (mod 11)。成功恢复了秘密 s=7。

第三步：分析其信息论安全特性

Shamir方案提供的不是计算上的安全性，而是更强的信息论安全（也称为完美保密）。这意味着，即使攻击者拥有无限的计算能力，也无法从不足 t 个份额中获得关于秘密 s 的任何信息（一比特信息都没有）。

1. 理解核心原因：其安全性根植于 多项式的代数性质。对于一个 t-1 次多项式，需要 t 个点才能唯一确定它。少于 t 个点，存在无数个（模 p 下）多项式可以通过这些点。
2. 模拟攻击者视角：假设攻击者截获了 t-1 个份额，即 t-1 个点 (x_j, y_j)。攻击者想知道秘密 s = f(0) 是什么。
   • 攻击者可以构造一个新多项式 g(x)，使其通过这 t-1 个点。
   • 对于任何一个可能的秘密值 s'（从 0 到 p-1），攻击者都能找到 一个唯一的 t-1 次多项式 g_{s'}(x)，满足 g_{s'}(0) = s' 并且 g_{s'}(x_j) = y_j。
   • 这意味着，给定 t-1 个份额，每一个 可能的秘密值 s' 出现的概率是完全相同的，都等于 1/p。
3. 得出安全结论：由于所有可能的秘密值对于不足 t 个份额的持有者来说都是等可能的，因此他们无法排除 任何一种可能性。从信息论的角度看，这些份额没有泄露 关于真实秘密 s 的任何信息。这就是“信息论安全”的含义——安全性不依赖于攻击者的计算能力，而依赖于信息本身的缺失。

第四步：认识其在安全多方计算中的作用

Shamir方案为安全多方计算提供了理想的秘密分发和重构工具。

1. 作为基础构件：在MPC协议中，参与者需要协同计算一个函数 f(x_1, ..., x_n)，其中每个 x_i 是参与者 i 的私有输入。为了保护输入隐私，每个参与者 i 可以使用 Shamir方案将自己的输入 x_i 共享给其他所有参与者。
2. 支持分布式计算：共享后的份额可以在参与者之间进行 安全的算术运算（加法和常数乘法）。例如，两个秘密 a 和 b 的份额，可以直接相加 得到 a+b 的份额；一个秘密 a 的份额可以乘以 一个公开常数 c 得到 c*a 的份额。这得益于多项式的线性性质。
3. 保障阈值隐私：在计算的最后一步，参与者可以联合 使用重建步骤，从结果函数值的份额中恢复出最终计算结果。只要参与重建的人数达到阈值 t，就能成功。同时，少于 t 个参与者无法知晓 计算过程中任何中间值或最终结果，保护了 所有参与方的输入和输出隐私。