Shamir秘密共享

Shamir 秘密共享（1979）把秘密 $s$ 分成 $n$ 份，使任意 $k$ 份可恢复秘密、少于 $k$ 份得不到任何信息——即 $(k,n)$ 门限方案。它利用有限域上多项式插值的唯一性：$k$ 个点确定一个 $k-1$ 次多项式。用于密钥托管、多方计算与门限签名。

方案

取素数 $p$ 大于秘密与份数，在 $\mathbb{F}_p$ 上随机选 $a_1,\dots,a_{k-1}$，构造

$$f(x)=s+a_1x+\cdots+a_{k-1}x^{k-1}$$

把份额 $f(i)$（$i=1,\dots,n$）分给 $n$ 个参与者。任取 $k$ 份由拉格朗日插值恢复

$$f(x)=\sum_{j=1}^{k}f(i_j)\prod_{\ell\ne j}\frac{x-i_\ell}{i_j-i_\ell}$$

秘密为 $s=f(0)$。

性质

• 门限性：$k$ 份可恢复，$k-1$ 份以下无法获得关于 $s$ 的任何信息（信息论安全）
• 份额可动态更新；配合多方计算可做加法、乘法

示例

在 $\mathbb{F}_7$ 上共享秘密 $s=4$，取 $k=2$，随机 $a_1=3$：$f(x)=4+3x$。份额

$$f(1)=0,\qquad f(2)=3,\qquad f(3)=6\pmod7$$

由 $(1,0)$ 与 $(2,3)$ 恢复：拉格朗日插值 $f(x)=3(x-1)$，故 $s=f(0)=3\cdot(0-1)\equiv4\pmod7$。

应用

Shamir 方案用于密钥托管（私钥分片保管）、区块链多重签名与门限密码；与中国剩余定理结合可得 CRT 型秘密共享方案。