加法秘密分享

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

$$ x = a_1 + ... + a_n \bmod p $$

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

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

Shamir门限秘密分享（SSS）

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

拉格朗日插值法

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

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

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

$$ L(x)=\sum_{i=1}^n y_i\Delta_{x_i}(x) $$

其中

$$ \Delta_{x_i}(x)=\prod_{j \not= 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_1i+...+a_{m-1}i^{m-1} $$

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

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

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

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

$$ f(x)=L(x)=\sum_{t \in M} p(t)\Delta_{t}(x) $$

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

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

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