加法秘密分享

这是一种十分简单的秘密分享方式，其主要想法就是

$$x=a_1+...+a_{n}modp$$

只要把 x 拆分成 n 个秘密值 $a_i$，只有获得所有的秘密值才能计算出来秘密 $x$。

但是这样的秘密分享方式是严格的秘密分享，因为必须要获得所有的值才能还原秘密。

Shamir 门限秘密分享（SSS）

这种秘密分享的方式在属性加密中被使用到了。
具体思想是基于拉格朗日插值法来形成的 (m,n)- 门限方案。

拉格朗日插值法

假设有一些点 $\{(x_i,y_i){\}}_{i\in \{1,...,n\}}$, 考虑过这些点的多项式：

$$f(x)=a_0+a_{1}x+...+a_{n-1}{x}^{n-1}$$

这样一个多项式可以通过插值法进行构造：

$$L(x)=\sum _{i=1}^n{y}_i{\mathrm{\Delta }}_{x_i}(x)$$

其中

$${\mathrm{\Delta }}_{x_i}(x)=\prod _{j\ne i}^n\frac{x-x_j}{x_i-x_j}$$

并且，根据拉格朗日插值定理，满足插值条件的、次数不超过 n 的多项式是存在并且唯一的，即

$$f(x)=L(x)$$

秘密分享的思想

那么如何使用拉格朗日多项式进行门限秘密分享呢？

首先，假设有 n 个参与者，给他们编号为 $1,...,n$。

而后，如果我们需要 m 个参与者一块才能获取该秘密的话，随机生成 $m-1$ 个数字 $\{a_i{\}}_{i=\{1,..,m-1\}}$，并定义 $a_0=x$，其中 $x$ 为秘密。

对于每个参与者 $i$，计算这么一个多项式：

$$q(i)=a_0+a_{1}i+...+a_{m-1}{i}^{m-1}$$

这个多项式的值就是分配给每个参与者的分享值。

那么相当于我们有以下多项式，并在这个多项式上取了 n 个点 $(1,q(1)),...(n,q(n))$：

$$f(x)=a_0+a_{1}x+...+a_{m-1}{x}^{m-1}$$

根据上面的拉格朗日插值法可以知道，一个 $m-1$ 阶多项式只要获得 $m$ 以上个点就可以进行还原：

$$f(x)=L(x)=\sum _{t\in M}p(t){\mathrm{\Delta }}_t(x)$$

其中 $M$ 为取的 $m$ 个点的集合。

而如果这时候我们再取 $x=0$，那么可以算出 $L(0)=a_0=x$ 即可恢复秘密。

（若是不足 $m$ 个点的话，那么就不能唯一确定那个多项式函数，也就没有办法还原出来结果了。）