Secret Sharing

秘密共享的思想是将秘密以适当的方式拆分，拆分后的每一个份额由不同的参与者管理，单个参与者无法恢复秘密信息，只有若干个参与者一同协作才能恢复秘密消息。更重要的是，当其中任何相应范围内参与者出问题时，秘密仍可以完整恢复。

秘密共享是一种将秘密分割存储的密码技术，目的是阻止秘密过于集中，以达到分散风险和容忍入侵的目的，是信息安全和数据保密中的重要手段。

More about Threshold Cryptography: https://webencrypt.org/thresholdcryptography/

$(k, n)$ 秘密分割门限方案

已知秘密 $S$ ，将其分割成 $n$ 个元素 $S_{1}, S_{2}, ... S_{n}$
1. 拥有大于等于 $k$ 个不同的 $S_{i}$ ，可以重构秘密 $S$ ；
2. 拥有小于 $k$ 个不同的 $S_{i}$ ，不能重构秘密 $S$ 。

$k$ 称为门限值， $S_{i}$ 称为子密钥或影子。

秘密分割方案由 Adi Shamir 和 George Blakley 在 1979 分别提出。

Asmuth-Bloom(基于中国剩余定理)。

依据：
2 个点可以构建直线，3 个点可以构建抛物线，4 个点可以构建 3 次曲线…， $k$ 个点可以构建 $k-1$ 次多项式。
假设要构建 $(k, n)$ 门限方案，其中共享秘密为 $S$ ，假设 $S\in{\mathbb{Z}_{p}}$

$0<k\leq{}n<p$ $S<p$ , $p$ 为素数。

随机选择 $k-1$ 个正整数 $a_{1}, ..., a_{k-1}\in{}\mathbb{Z}_{p}$ , 令 $a_{0}=S$ 。由此构建多项式：

$f(x) = a_{0} + a_{1}x + a_{2}x^{2} + ... + a_{k-1}x^{k-1}$

秘密的分割：
每个参与者分配一个点 $(x_i , f(x_i))$

$\begin{cases} a_{0} + a_{1}(x_{1}) + \cdots + a_{k-1}(x_{1})^{k-1} = f(x_{1})\\ \vdots \\ a_{0} + a_{1}(x_{k}) + \cdots + a_{k-1}(x_{k})^{k-1} = f(x_{k}) \end{cases}$

Lagrange插值公式：

设 $\{(x_{1}, y_{1}), ..., (x_{k}, y_{k})\}$ 是平面上 $k$ 个点构成的点集， $k$ 个点构成的点集，其中 $x_{i}(i = 1, ..., k)$ 各不相同，那么在平面上存在唯一的 $k$ 各不相同，那么在平面上存在唯一的 $k-1$ 次多项式 $f(x)$ 通过这 $k$ 个点.若把秘密 $S$ 取做 $f(0)$ ， $n$ 个子密钥取做 $f(x_{i}) (i = 1, ..., n)$ ,那么利用其中任意 $k$ 那么利用其中任意 $k$ 个子密钥可以重构 $f(x)$ ，从而可以得到秘密 $S$ 。

Lagrange插值公式构造多项式：

$f(x)=\sum_{j=1}^{k}f(x_{j})\prod_{i=1, i\neq{}j}^{k}\frac{x-x_{i}}{x_{j}-x_{i}} (\bmod p)$

$\begin{aligned} S&=\sum_{j=1}^{k}f(x_{j})\prod_{i=1, i\neq{}j}^{k}\frac{0-x_{i}}{x_{j}-x_{i}} (\bmod p)\\ &=(-1)^{k-1}\sum_{j=1}^{k}f(x_{j})\prod_{i=1, i\neq{}j}^{k}\frac{x_{i}}{x_{j}-x_{i}} (\bmod p)\\ &=\sum_{j=1}^{k}f(x_{j})\prod_{i=1, i\neq{}j}^{k}\frac{x_{i}}{x_{i}-x_{j}} (\bmod p) \end{aligned}$

Shamir门限方案的举例：

例 $k=3$ , $n=5$ , $p=19$ , $S=11$

随机选 $a_{1}=2$ , $a_{2}=7$ ，则有 $f(x)=11 + 2x + 7x^{2} \bmod 19$

计算 $f(1)=1$ , $f(2)=5$ , $f(3)=4$ , $f(4)=17$ , $f(5)=6$

已知 $f(2)$ , $f(3)$ , $f(5)$ ，重构：

$\begin{aligned}f(x)&=5\frac{(x-3)(x-5)}{(2-3)(2-5)}+4\frac{(x-2)(x-5)}{(3-2)(3-5)}+6\frac{(x-2)(x-3)}{(5-2)(5-3)}\\ &=11+2x+7x^{2}\end{aligned}$

Asmuth-Bloom门限方案(参数选取) ：

令 $p$ 是一个大素数， $m_{1}, m_{2}, ..., m_{n}$ 是 $n$ 个严格递增的数，且满足下列条件：

$p > S$
$(m_{i}, m_{j})=1 (\forall{}i, j, i\neq{}j)$
$(p, m_{i})=1 (i = 1, 2, ..., n)$
$N=\prod_{i=1}^{t}m_{i}>p\prod_{j=1}^{t-1}m_{n-j+1}$

Asmuth-Bloom门限方案(秘密分割) ：

随机选取整数 $A$ 满足 $0\leq{}A\leq{}\lfloor{}N/p\rfloor{}-1$ ，并公布 $p$ 和 $A$
$y=S+Ap$ ，则有 $y<p+Ap=(A+1)p\leq{}\lfloor{}N/p\rfloor{}\cdot{}p\leq{}N$
计算 $y_{i}\equiv{}y(\bmod m_{i}) (i=1,2,...,n)$ ， $(m_{i},y_{i})$ 即为一个子共享，将其分别传送给 $n$ 个用户

集合 $\{(m_{i},y_{i})\mid{}i=1,2,...,n\}$ 即构成了一个 $(t, n)$ 门限方案。

Asmuth-Bloom门限方案(秘密恢复)：

当 $t$ 个参与者 $i_{1},i_{2},...,i_{t}$ 提供出自己的子份额，由 $\{(m_{i_{j}},y_{i_{j}})\mid{}i=1,2,...,t\}$ 建立方程组：

$\begin{cases}y\equiv{}y_{i_{1}} (\bmod M_{i_{1}})\\y\equiv{}y_{i_{2}} (\bmod M_{i_{2}})\\\cdot{}\cdot{}\cdot{}\\y\equiv{}y_{i_{k}} (\bmod M_{i_{k}})\end{cases}$

根据中国剩余定理可求得：

$y\equiv{}y' (\bmod N')$

其中， $N'=\prod_{j=1}^{t}m_{i_{j}}\geq{}N$ ，由 $y'-Ap$ 即得到秘密 $S$ 。

Introduce

Shamir

Blakley

Asmuth-Bloom

Reference