updated: 2026-04-05

Shamir秘密共享协议

基于挂锁的 $(k, n)$ 门限

有这样的一条新闻，某小区业主使用66把锁串联锁住了小区大门，保证只有小区住户才能打开其中一把锁，打开大门。

这种将锁串联的操作实现了一种可以理解为“或”的逻辑。从另一种角度理解，这可以被看作一种 $(1, n)$ 门限方案，即小区的 $n$ 个业主中，只要有一位同意，即可开锁。

进一步的，通过将锁并联，我们可以构造出“与”逻辑，从而实现 $(k, n)$ 门限方案。

例如，当 $k = 2, n = 3$ 时，记参与的三方为 $A, B, C$ ，一个简单的方案如下（假设锁可以复制）：

方案一：
A B
A C
B C

（其中横向表示串联，纵向表示并联）可以看到，该方案需要6把锁，每一方需要1把钥匙。然而，我们还有另一种方案：

方案二：
a
b
c

其中， $A$ 携带钥匙 $bc$ ， $B$ 携带钥匙 $ac$ ， $C$ 携带钥匙 $ab$ 。如此以来，我们只需要使用3把锁，但代价是每一方需要携带2把钥匙。

下面的证明可略过

假设锁不可复制，但是钥匙可以复制。我们接下来研究 $(k, n), k \ge 2$ 门限问题中需要的锁的最小数量以及每个参与者需要携带的钥匙数量。我们需要保证：

必要性：对于任意的 $k - 1$ 个参与者，总是存在至少一把无法打开的锁。
充分性：任意的两组 $k - 1$ 个参与者不能存在共同的无法打开的锁，否则这意味着我们可以找出 $2k - 2 \ge k$ 个无法开门的参与者。

假设锁数量为 $s$ ，这些锁构成了一个集合 $L$ 。将第 $i$ 组 $k - 1$ 个参与者不能打开的锁记为 $u_i$ 。从必要性条件我们有 $|u_i| > 0$ 。从充分性条件知 $U = \{u_1, u_2, ...\}$ 构成 $L$ 的一个划分，且 $|U| = C_{n}^{k - 1}$ 。为了得到最小需要的锁的数量，取 $|u_i| = 1$ ，因此 $s$ 最小为 $C_{n}^{k - 1}$ 。

进一步的，对于一个参与者 $A$ ，我们从剩下的 $n - 1$ 名参与者中挑出一组 $k - 1$ 名参与者，从上述必要性条件知 $A$ 至少拥有一把他们没有的钥匙。同时由充分性条件知任意两组 $k - 1$ 个参与者至少缺少两把钥匙。因此 $A$ 至少要有 $C_{n - 1}^{k - 1}$ 把钥匙。即每一位参与者所需要的最少的钥匙数量为 $C_{n-1}^{k-1}$ 。

在Shamir的论文中，他提到一个 $(6, 11)$ 的门限方案需要至少462把锁，每个参与者需要携带252把钥匙，这是不切实际的。

拉格朗日插值

拉格朗日插值是Shamir秘密共享的核心。对于给定的 $k$ 个点 $(x_1, y_1), (x_2, y_2), ..., (x_k, y_k)$ ，拉格朗日插值法能够计算出通过这些点的多项式。利用该方法给出的 $k$ 阶多项式形式如下：

L(x) = \sum_{i = 1}^k y_i\mathcal{l}_i(x)

直觉上来看，为了让该多项式在 $x = x_i$ 时取值为 $y_i$ ，我们需要保证

\begin{align} \mathcal{l}_i(x) = \left\{ \begin{array}{rcr} 1 &, x = x_i\\0 &, x \ne x_i \end{array} \right. \end{align}

因此我们可以构造 $\mathcal{l}_i(x)$ 如下：

\mathcal{l}_i(x) = \prod_{j = 1, j \ne i}^{k}\frac{x - x_j}{x_i - x_j}

可以看到，当 $x = x_i$ 时，每一项都为 $1$ ，否则总有一项分子为 $0$ ，该构造满足上述要求。我们构造出的多项式 $L(x)$ 被称为拉格朗日多项式。

可以证明，对于 $k$ 个点，我们可以构造出一个唯一的 $k - 1$ 阶拉格朗日多项式。

Shamir协议

协议描述

Shamir对之前提到的 $(k, n)$ 门限方案给出了更严格的限制：假设要共享的秘密为 $D$ ，将 $D$ 分为 $n$ 份 $D_1, D_2, ..., D_n$ ，该方案应当能保证

可以从 $D_1, D_2, ..., D_n$ 中的任意 $k$ 份数据简单的计算出 $D$
即使持有 $D_1, D_2,..., D_n$ 中的任意小于 $k$ 份数据，也无法得知任何关于 $D$ 的信息

通过将上述拉格朗日插值的过程倒转过来，我们很容易得到Shamir秘密共享的基本思想：给定一个 $k-1$ 阶多项式

L(x) = D + a_1x + a_2x^2 + ... + a_{k - 1}x^{k - 1}

其中 $D$ 为要共享的秘密。计算 $D_1 = L(1), ..., D_i = L(i), ..., D_n = L(n)$ ，将 $(i, D_i)$ 分别分发给秘密共享的参与方，那么只要其中 $k$ 方合作，即可唯一确定该拉格朗日多项式 $L(x)$ ，并可以简单地求出 $D = L(0)$ 。

协议安全性证明

在实际应用中，该多项式可以被定义在素域 $F_p$ 上，其中多项式的每一个系数是从素域中随机选取的非零且不等元素。假设一位攻击者拥有 $k - 1$ 部分数据，且

D = L(0) = \sum_{i = 1}^{k}D_i\mathcal{l}_i(0), \text{where } x_i = i

因此

\color{yellow}D_k\color{white}\mathcal{l}_k(0) = \color{yellow}D\color{white} - \sum_{i = 1}^{k - 1}D_i\mathcal{l}_i(0), \text{where } \mathcal{l}_k(0) = \prod_{j = 1}^{k - 1}\frac{0 - x_j}{k - x_j}

注意上式中，只有黄色的部分不是常量。由于我们的操作在素域上进行，上式给出了一个 $D$ 和 $D_k$ 之间的一对一映射关系。因此通过这些数据生成的多项式共有 $p$ 个，且由它们得到秘密 $D$ 的可能性相等，攻击者无法获得任何关于 $D$ 的信息。

参考资料

Shamir1979 - How to share a secret
https://crypto.stackexchange.com/questions/64082/formal-proof-of-shamirs-secret-sharing-scheme-security

∧