1. 秘密共享简介

秘密共享通过将秘密以适当的方式拆分，拆分后的每一个份额由不同的参与者管理，单个参与者无法恢复秘密信息，只有若干个参与者一同协作才能恢复秘密消息。

秘密共享定义如下：秘密持有者$S$需要将原始秘密$m$在参与者集合中$P_1,P_2,...,P_n$分享，$S$分发给$P_1$子秘密$m_{p_i}$，使得只有特定参与者的集合才能够从他们的子秘密中恢复秘密$m$，而其他参与者不能得到秘密$m$的任何信息。

能够计算出秘密$m$的参与者集合$P$的一个子集$A\subseteq P$，称为一个授权子集。令$\Gamma$为所有授权子集构成的集合，则称$\Gamma$访问结构。

秘密共享方案一般描述如下：将共享的秘密$m$分割成$n$个子秘密，并将其分发至$n$个参与者，使得授权子集$\Gamma$中的参与者可共同恢出复秘密$m$，而非授权子集中的参与者无法得到关于秘密$m$的任何信息。

2. Shamir秘密共享方案

Adi Shamir于1979年提出了基于拉格朗日(Lagrange)插值定理的$(t,n)$-门限方案。该方案利用有限域上的次随机多项式来分享秘密，被分享的秘密为多项式的零次系数，恢复秘密至少需要t个多项式上的点。

方案描述如下：

设 $GF(q)$ 是一个有限域, $q$为公开大素数, 共享的密钥 $k\in GF(q)$, 可信中心给 $n(n<q)$个共享者 $P_i(1\le i\le n)$ 分配共享的过程如下:

(1) 秘密分发

可信中心随机选取多项式 $f(x)=a_{t-1}{x}^{t-1}+\dots +a_2{x}^2+a_{1}x+a_0\in$ $GF(q)[x]$, 常数 $a_0=k$ 为要分享的秘密。

可信中心在 $GF(q)$ 中选择 $n$ 个非零的互不相同的 元素 $x_1,x_2,\dots ,x_n$, 计算 $y_i=f\left(x_i\right),1\le i\le n$, 将子密钥 $\left(x_i,y_i\right)$ 分配给共享者 $P_i(x_i$ 是公开的, $y_i$ 为 $P_i$ 的秘密共享)。

（2） 秘密重构

给定 $t$ 个共享 $y_{i_s}(1\le s\le t)$, 从Lagrange多项式重构的

$$\begin{array}{rl}& f(x)=\sum _{s=1}^t{y}_{i_s}\prod _{j=1,j\ne s}^t\frac{x-x_j}{x_{i_s}-x_{i_j}},\\ & k=a_0=f(0)=\sum _{s=1}^t{y}_{i_s}\prod _{j=1,j\ne s}^t\frac{-x_j}{x_{i_s}-x_{i_j}}=\sum _{s=1}^t{b}_s{y}_{i_s},\end{array}$$其中, $b_s={\Pi }_{j=1,j\ne s}^t\frac{-x_j}{x_{i_s}-x_{i_j}}$ (Lagrange插值系数), 运算都是$GF(q)$上的运算。

Eg 设 $t=3,n=5,q=19,k=11$, 随机选取 $a_1=2,a_2=7$, 得多项式为$$h(x)=\left(7x^2+2x+11\right)\mathrm{mod}19$$选择 $x_i=i$, 则由 $y_i=h\left(x_i\right),1\le i\le 5$, 很容易得到$5$个子密钥$$h(1)=1,h(2)=5,h(3)=4,h(4)=17,h(5)=6$$如果知道其中 3 个子密钥 $h(2)=5,h(3)=4,h(5)=6$$$\{\begin{array}{l}4a_2+2a_1+a_0=5\\ 9a_2+3a_1+a_0=4\\ 25a_2+5a_1+a_0=6\end{array}$$从而解得 $k=a_0=11$。

3. Asmuth-Bloom方案

Asmuth和Bloom于1980年提出了一个基于中国剩余定理的$(t,n)$-门限方案。该方案中，成员的共享是由秘密 $S$ 得出的数 $y$ 对于不同模数 $m_1,m_2,\dots ,m_n$ 的剩余。

令 $p,d_1,d_2,\dots ,d_n$ 是满足下列条件的一组正整数:$$p>k;d_1<d_2<\dots <d_n$$对所有的 $i,\gcd \left(p,d_i\right)=1;$

对 $i\ne j,\gcd \left(d_i,d_j\right)=1;d_1{d}_2\cdots d_t>$ $p{d}_{n-t+2}{d}_{n-t+3}\cdots d_n$

令 $N=d_1{d}_2\cdots d_t$ 是 $t$ 个最小整数之积，则 $N/p$ 大于任意 $t-1$ 个 $d_i$ 。令 $r$ 是区间 $[0,\lfloor N/p\rfloor -1]$ 中的一个随机整数, 并公布 $p,r$ 。

(1) 秘密分发

将 $k$ 划分为 $n$ 个共享, 计算 $k^{\prime }=k+rp$, 则 $k^{\prime }\in [0,N-1]。n$ 个共享 为 $k_i=k^{\prime }{\mathrm{modd}}_i,i=1,2,\dots ,n$, 将子密钥 $\left(d_i,k_i\right)$ 分配给共享者 $P_i(d_i$ 是公开的, $k_i$ 为 $P_i$

(2) 秘密重构

若给定 $t$ 个共享 $k_{i_1},\dots ,\dots ,k_{i_t}$, 则由中国剩余定理可知, 同余方程组$$\{\begin{array}{l}{x}^{\prime }\equiv k_{i_1}\mathrm{mod}{d}_{i_1}\\ x^{\prime }\equiv k_{i_2}\mathrm{mod}{d}_{i_2}\\ \cdots \\ x^{\prime }\equiv k_{i_t}\mathrm{mod}{d}_{i_t}\end{array}$$关于模 $N_1=d_{i_1}{d}_{i_2}\cdots d_{i_t}$ 在 $\left[0,N_1-1\right]$ 内有唯一解 $x$, 因为 $N_1\ge N\ge k^{\prime }$, 推出 $k^{\prime }=x$ 。 最后计算出 $k=k^{\prime }-rp$, 即 $k=k^{\prime }\mathrm{mod}p$ 。

Eg 设 $t=2,n=3,p=7,k=4,d_1=9,d_2=11,d_3=13$, 则$$N=d_1{d}_2=99>91=7\cdot 13=p\cdot d_3.$$在 $[0,[99/7]-1]=[0,13]$ 之间随机取 $r=10,k^{\prime }=k+rp=4+10\times 7=74$,$$\begin{array}{rl}& k_1\equiv k^{\prime }\text{ modd }{d}_1\equiv 74\mathrm{mod}9\equiv 2\\ & k_2\equiv k^{\prime }\mathrm{mod}{d}_2\equiv 74\mathrm{mod}11\equiv 8\\ & k_3\equiv k^{\prime }\mathrm{mod}{d}_3\equiv 74\mathrm{mod}13\equiv 9\end{array}$$3 个子密钥为 $\{(9,2),(11,8),(13,9)\}$。

若知道 $\{(9,2),(11,8)\}$, 可建立方程组:$$\{\begin{array}{l}{k}^{\prime }\equiv 2\mathrm{mod}9\\ k^{\prime }\equiv 8\mathrm{mod}11\end{array}$$根据中国剩余定理，解得：$$k^{\prime }\equiv (11\times 5\times 2+9\times 5\times 8)\mathrm{mod}\equiv 74$$因此 $k^{\prime }\equiv k\mathrm{mod}p=4$

4. 可验证的秘密共享

可验证的秘密共享VSS方案是对传统秘密共享方案的修正，在通常的秘密分享方案基础上附加验证操作构成，主要用于解决不诚实的分发中心问题。

在VSS方案中，分发者不但分发秘密的碎片，而且广播对秘密碎片的承诺，当个成员收到其碎片时，要验证其碎片是否正确；在秘密重构阶段，每个参与者也采用同样方法验证其他成员秘密碎片的正确性。

VSS主要抵抗以下两种主动攻击：

• 分发者在秘密分发协议中发送错误碎片给部分或全部参与者。
• 协议参与者在秘密重构协议中提交错误碎片。

常见的可验证的秘密共享方案包括Feldman的VSS方案以及Pedersen方案。

4.1 Feldman的VSS方案

（1）秘密分发

可信中心选取阶随机多项式：$$f(x)=a_{t-1}{x}^{t-1}+\dots +a_2{x}^2+a_{1}x+a_0\in GF(q)[x]$$常数$a_0=s$为要分发的秘密;

可信中心选择$n$个非零的互不相同的元素$x_1,x_2,\dots ,x_n\in GF(q)$，计算$y_i=f\left(x_i\right),1\le i\le n$ , 将子密钥 $\left(x_i,y_i\right)$ 分配给共享者 $P_i$($\left(x_i\right)$是公开的,$y_i$为$P_i$的秘密共享)，可信中心计算并广播承诺$B_j=g^{a_j},0\le j<t$。

参与者$P_i$收到自己的碎片$y_i$后, 判断$g^{y_i}={\Pi }_{j=0}^{t-1}{B}_j^{x_i^j}$是否成立, 如果成立, 则接受该 碎片为有效; 否则,$P_i$ 请求可信中心重新发送正确的碎片。

若可信中心向 $P_i$ 传送了正确的碎片 $y_i$, 则有$$\begin{array}{rl}{g}^{y_i=g^{f\left(x_i\right)}}& =g^{a_{t-1}{r}_i^{t-1}+\dots +a_2{x}_i^2+a_1{x}_i+a_0}\\ & =g^{a_{t-1}{x}_i^{t-1}}\dots g^{a_2{x}_i^2}{g}^{a_1{x}_i}{g}^{a_0}\\ & =B_{t-1}^{x_i^{t-1}}\dots B_2^{x_i^2}{B}_7^{x_i}{B}_0\\ & ={\Pi }_{j=0}^{t-1}{B}_j^{x_i^j}\end{array}$$（2）秘密重构

假设每个参与者都接受到正确的碎片, 他们中的任意$t$个可执行 Shamir门限秘密分享方案中的重构算法恢复出院时秘密, 即$P_i$向参与重构的其他人广播自己的碎片，这样每个参与重构的成员均可验证所接收到的碎片的有效性，然后使用Lagrange揷值公式计算出秘密$S$。

Feldman的VSS方案中, 由于可信中心在广播承诺时将$B_0=g^{a_0}=g^s$也作为一个承诺发出, 因此方案仅是计算安全的。

4.2 Pedersen的VSS方案

Pedersen扩展了Feldman的方案，将Shamir秘密共享方案与承诺方案相结合，构造出了一个高效、安全的非交互式可验证秘密共享方案，且验证信息不会直接泄露秘密$k$，因此是信息论安全的。

（1）秘密分发

可信中心选取两个$t$阶随机多项式：$$\begin{array}{l}a(x)=a_{t-1}{x}^{t-1}+\dots +a_2{x}^2+a_{7}x+a_0\in GF(q)[x]\\ b(x)=b_{t-1}{x}^{t-1}+\dots +b_2{x}^2+b_{1}x+b_0\in GF(q)[x]\end{array}$$常数$a_0=s$为要分发的秘密。

可信中心选择$n$个非零的互不相同的元素 $x_1,x_2,\dots ,x_n\in GF(q)$ ,计算 $y_i=\left(s_i,s_{i2}\right)=\left(a\left(x_i\right),b\left(x_i\right)\right),1\le i\le n$ 将子密钥$\left(x_i,y_i\right)$分配给共享者 $P_i$($x_i$是公开的,$y_i$为$P_i$的秘密共享)。可信中心计算并广播承诺$C_j=g^{a_j}{h}^{b_j},0\le j<t$ 。

参与者$P_i$ 收到自己的碎片 $y_i$ 后, 判断 $g^{s_{i┐}}{h}^{s_{i2}}={\prod }_{j=0}^{t-1}{C}_j^{x_i^j}$ 是否成立。如果成立, 则接受 该碎片为有效; 否则, $P_i$ 请求可信中心重新发送正确的碎片。

若可信中心向$P_i$传送了正确的碎片$y_i$, 则有$$\begin{array}{rl}{g}^{s_{i┐}}{h}^{s_{i2}}=& g^{a\left(x_i\right)}{h}^{b\left(x_i\right)}=\left(g^{a_{t-1}{x}_i^{t-1}+\dots +a_2{x}_i^2+a_1{x}_i+a_0}\right)\left(h^{b_{t-1}{x}_i^{t-1}+\dots +b_2{x}_i^2+b_1{x}_i+b_0}\right)\\ & ={\left(g^{a}t-1h^{b_{t-1}}\right)}^{x_i^{t-1}}\dots {\left(g^{a_2}{h}^{b_2}\right)}^{x_i^2}{\left(g^{a^a}{h}^{b_1}\right)}^{x_i}{g}^{a_0}{h}^{b_0}\\ & =C_{t-1}^{x_i^{t-1}}\dots C_2^{x_i^2}{C}_1^{x_i}{C}_0\\ & =\prod _{j=0}^{t-1}{C}_j^{x_i^j}\end{array}$$（2）秘密重构

假设每个参与者都接受到正确的碎片, 他们中的任意$t$个可执行 Shamir门限秘密分享方案中的重构算法恢复出院时秘密, 即$P_i$向参与重构的其他人广播自己的碎片, 这样每个参与重构的成员均可验证所接收到的碎片的有效性, 然后使用Lagrange揷值公式计算出秘密$s$ 。

Pedersen的VSS方案中，可信中心在广播承诺时与秘密$s$相关的信息仅为$C_0=g^s{h}^{b_0}$，没有泄露关于$s$的任何信息，因此方案是信息论安全的。

5. 无分发者的随机秘密共享

在该秘密体制中不存在秘密分发者，仅有参与者$P_1,P_2,...,P_n$，他们以交互的方式协商出一个随机秘密$s$，并各自得到该秘密的一个碎片$s_i$，但每个参与者都不知道这个随机秘密的具体值，除非他们公布自己的碎片并重构该秘密。

基于Shamir的秘密分享体制的一个无秘密分发者的$(t,n)$秘密分享体制，称为Joint-Shamir-RSS方案（Joint Shamir Random Secret Sharing）。

(1) 每个参与者 $P_i$ 选择一个 $t-1$ 次随机多项式 $f_i(x)=a_{i,t-1}{x}^{t-1}+\dots +a_{i2}{x}^2+a_{i1}x+a_{i0}\in GF(q)[x]$, 以 $a_{i0}=f_i(0)$ 作为自己要让 $P_1,P_2,\dots ,P_n$ 分享的秘密。

(2) $P_i$ 计算 $s_{ij}=f_i\left(x_j\right)$, 发送给 $P_j,j=1,2,\dots ,n$, 如下所示:$$\begin{array}{lllll}& P_1& P_2& P_j& P_n\\ P_1& f_1\left(x_1\right)& f_7\left(x_2\right)& f_7\left(x_j\right)& f_1\left(x_n\right)\\ P_2& f_2\left(x_1\right)& f_2\left(x_2\right)& f_2\left(x_j\right)& f_2\left(x_n\right)\\ P_i& f_i\left(x_1\right)& f_i\left(x_2\right)& f_i\left(x_j\right)& f_i\left(x_n\right)\\ P_n& f_n\left(x_1\right)& f_n\left(x_2\right)& f_n\left(x_j\right)& f_n\left(x_n\right)\end{array}$$(3) $P_j$ 收到其他参与者的值 $s_{ij}=f_i\left(x_j\right),i=1,2,\dots ,n$, 计算 $s_j={\sum }_{i=1}^n{f}_i\left(x_j\right)$ 作为 自己最终分享秘密的碎片。

从协议中可以看出, 若令 $f(x)={\sum }_{i=1}^n{f}_i(x)$, 则 $f\left(x_j\right)={\sum }_{i=1}^n{f}_i\left(x_j\right)$ 。

秘密重构阶段，只需任意$t$个参与者使用自己拥有的秘密碎片$s_i$执行Shamir秘密分享体制的秘密重构即可。