$$$(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$$$个严格递增的数,且满足下列条件:

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


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

  1. 随机选取整数$$$A$$$满足$$$0\leq{}A\leq{}\lfloor{}N/p\rfloor{}-1$$$,并公布$$$p$$$$$$A$$$
  2. $$$y=S+Ap$$$,则有$$$y<p+Ap=(A+1)p\leq{}\lfloor{}N/p\rfloor{}\cdot{}p\leq{}N$$$
  3. 计算$$$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$$$