Shamir秘密分享

牛顿：我站在巨人的肩膀上！ 而我：我站在牛顿的肩膀上！

门限密码

Shamir秘密分享方案(SS)

在 \(\operatorname{Shamir}(t, n)\) 门限秘密分享方案中, 可信中心把秘密 \(d\) 拆分成 \(n\) 份, 分发给 \(n\) 个参与者 \(U_1, U_2, \cdots, U_n\). 任意 \(t+1\) 个或 \(t+1\) 个以上的参与者一起可恢复秘密 \(d\), 任意 \(t\) 个参与者一起不能得到秘密 \(d\) 的任何信息. 详细方案如下:

1. 可信中心秘密构造 \(t\) 阶多项式 \(f(x)=\sum_{i=0}^t a_i x^i\), 其中秘密 \(d=f(0)=a_0\);

2. 可信中心计算 \(d_i=f(i)\), 并秘密地把 \(d_i\) 分别发送给参与者 \(U_i其中 1 \leqslant i \leqslant n\);

3. \(U_i\) 将 \(d_i\) 作为份额保存.

上述过程称为 \(t\) 阶 \(\mathrm{SS}\), 并称多项式 \(f(x)\) 为分享多项式. 此时, 任意 \(t+1\) 个参与者集合 \(Q\) 可通过拉格朗日插值公式 ：

\[P_n(x)=\sum_{i=1}^n y_i\left(\prod_{j \neq i}^{1 \leq j \leq n} \frac{\left(x-x_j\right)}{\left(x_i-x_j\right)}\right)\]

恢复出秘密。

📑 解释一下： - \(y_i\) 就是对应函数值。 - 后面那一驼就是除去选定的第\(i\)个值的横坐标，其余横坐标相乘。

举个🌰：

以 \((3,4)\) 门限为例, 假设秘密 \(s=2, p=23\), 构造的 \(f(x)\) 如下:

\[ f(x)=2 x^2+3 x+2 \bmod (23) \]

根据函数可知此处 \(t=3\), 另取 \(x_1=1, x_2=2, x_3=3, x_4=4\), 代 入函数得 \(f(1)=7, f(2)=16, f(3)=6, f(4)=0\) 。

随机选取其中 3 组数据 \((1,7) 、(3,6) 、(3,0)\), 并使用拉格朗日插值公式进行恢复：

\[ s=7 \times \frac{(0-3) \times(0-4)}{(1-3) \times(1-4)}+6 \times \frac{(0-1) \times(0-4)}{(3-1) \times(3-4)}+0 \times \frac{(0-1) \times(0-3)}{(4-1) \times(4-3)} \bmod (23)=2 \]

经过上述计算成功恢复出秘密 \(s=2\)。

如果要用这三个点恢复出原多项式，只需分母不带入\(x\)的值即可：

\[ \begin{align*} f(x) &= 7 \times \frac{(x-3) \times(x-4)}{(1-3) \times(1-4)} + 6 \times \frac{(x-1) \times(x-4)}{(3-1) \times(3-4)} + 0 \times \frac{(x-1) \times(x-3)}{(4-1) \times(4-3)} \bmod 23\\ f(x) &= \frac{7}{6} \times (x^2 - 7x + 12) - 3 \times (x^2 - 5x + 4) \bmod 23 \\ f(x) &= 28 \times (x^2 - 7x + 12) - 3 \times (x^2 - 5x + 4) \bmod 23 \\ f(x) &= 5 x^2 - 12x + 14 - 3 x^2 + 15x - 12 \bmod 23 \\ f(x) &= 2x^2 + 3x + 2 \bmod 23 \end{align*} \]

恢复出原多项式，运算过程中需要注意模乘运算，其中\(28 \bmod 23 = 5，且6^{-1} \bmod 23 = 4\)。

Lagrange插值定理在节点上给出节点基函数，然后做基函数的线性组合，组合系数为节点函数值的一种插值多项式。不止运用与数论，在代数学中也广泛被应用，适合做数据的拟合处理，并运用在已知几个点的情况下求出函数表达式。

比如：已知\(f(1)=1,f(2)=2,f(3)=3,f(4)=4,f(5)=?\)，根据插值公式，这里的\(f(5)\)可以是任何值，并且在每个值下，我们运用插值定理都能找到对应的多项式方程。