秘密分享的背景与概念:
密钥丢失是一件很麻烦的事情,例如,保存私钥的硬盘被不小心格式化,或者持有密钥的管理员被车创了,会导致重要文件不能打开等严重后果.避免此类后果的方式之一是创建多个密钥备份,但备份越多意味着密钥泄露的风险越大.
另一个思路是秘密分享,其思想是将秘密分解为多个碎片并分别保存,在秘密丢失时,这些碎片中的某些特定子集可以通过将碎片组合在一起回复整个秘密.
$(t,n)$秘密分享体系的成员包括秘密分发者$Deliver$和参与者$P_1,\cdots,P_n$
该体系包含以下两个协议:
- 秘密分发协议:分发者$Deliver$在$n$个参与者中分享秘密$s$,参与者$P_i$获得一个碎片$s_i$
- 秘密重构协议:任意不少于$t$个参与者以自己的碎片作为输入,重构原秘密$s$
该体系需要满足如下性质:
- 任意$t$个参与者通过提供自己的碎片能够协作恢复原秘密$s$
- 任意少于$t$个参与者即使拥有自己的碎片也无法计算出关于秘密$s$的任何信息
这里的$t$一般称为"门限值"
一个直观但不安全的秘密分享体系:
要在$n$个参与者之间分享秘密,要求门限值也为$n$,那么直接将秘密分割为$n$段($||$为字符串拼接符号)
$s=s_1||s_2||\cdots||s_n$
对上述秘密分享体系的一个攻击示例:
考虑一个RSA密码系统,包含
两个大质数$p,q$(由于常用的RSA体系使用两个位数相同的大质数,因此不妨假定$2p>q>p>3$),
模数为$m=pq$,$\varphi(m)=(p-1)(q-1)$
公钥$e=3$,保证$gcd(e,\varphi(m))=1$,
私钥$d=e^{-1} \mod \varphi(m)$,
要在参与者$P_1$和$P_2$之间分享私钥$d$,
将$d$直接分割为两段$d=d_1||d_2$,分别交给$P_1,P_2$保管.
但实际上,$P_2$只需要计算
$\hat{d}=1+\lfloor \frac{2m-4\sqrt{m}}{3} \rfloor$
然后将$\hat{d}$的后半部分替换为自己掌握的$d_2$即可得到$d$
正确性:
实际上,由于$d=e^{-1} \mod \varphi(m)$,将其改写为扩展欧几里得方程的形式,存在整数$l$使得
$$\begin{aligned}
e\cdot d =&1+l\cdot\varphi(m)\\
&\Downarrow \\
3\cdot d =&1+l\cdot\varphi(m)
\end{aligned}$$
由于$0<d<\varphi(m)$,因此要么$l=1$,要么$l=2$
另一方面,由于$p,q$均为大质数,
$$\begin{aligned}
p \mod 3 \neq 0,&q\mod 3 \neq 0\\
&\Downarrow \\
(p-1) \mod 3 \neq 2,&(q-1)\mod 3 \neq 2 \\
&\Downarrow \\
\varphi(m)\mod &3 \neq 2
\end{aligned}$$
那么,如果$l=1$,则等式$3\cdot d =1+l\cdot\varphi(m)$左端模3余$0$,右端模$3$不余$0$,等式必然不成立,因此必然有$l=2$
将$l=2$代回等式,得到了$d=\frac{1+2\varphi(m)}{3}$
考虑$\hat{d}$与$d$之间的误差
$$\begin{aligned}
|d-\hat{d}|=&|\frac{1+2\varphi(m)}{3} -1-\lfloor \frac{2m-4\sqrt{m}}{3} \rfloor| \\
=&|\lceil\frac{1+2\varphi(m)}{3} -1-\frac{2m-4\sqrt{m}}{3}\rceil| \\
=&|\lceil \frac{2\varphi(m)-2-2m+4\sqrt{m}}{3} \rceil|\\
=&|\lceil \frac{2(m-p-q+1)-2-2m+4\sqrt{m}}{3} \rceil| \qquad (\varphi(m)=(p-1)(q-1)=pq-p-q+1)\\
=&|\lceil \frac{2m-2p-2q+2-2-2m+4\sqrt{m}}{3} \rceil| \\
=&|\lceil \frac{4\sqrt{m}-2p-2q}{3} \rceil| \\
\end{aligned}$$
因为保证了$2p>q>p>3$,因此有$\sqrt{2m}>q>\sqrt{m}>p>\sqrt{\frac{m}{2}}$
$2p\in (\sqrt{2m},2\sqrt{m})$,$2q\in(2\sqrt{m},2\sqrt{2m})$
$(2p+2q) \in ((2+\sqrt{2})\sqrt{m},(2+2\sqrt{2})\sqrt{m})$
$|\lceil \frac{4\sqrt{m}-2p-2q}{3} \rceil| \in [0,\frac{\sqrt{m}}{3})$,因此$\hat{d}$与$d$的前半部分必然相同.
该示例意味着,简单地将秘密按位分割来实现秘密分享是不安全的.
Shamir秘密分享体系:
系统参数:
$n$为参与者的人数,$t$为门限值,
$p>n$为大素数,
设欲分享的秘密为$s\in [1,p-1]$
秘密分发:
- 分发者$Deliver$选择一个$t$阶随机多项式$$a(x)=s+\alpha_1 x+ \alpha_2 x^2 + \cdots +\alpha_{t-1}x^{t-1}$$其中$\alpha_{j}\in [1,p-1]$(为了描述的一致性,记$\alpha_0=s$)
- 对于$i=1,2,\cdots,n$,将$x=i$代入$a(x)$计算出$a(i)$,令$s_i=a(i)$
- 将$s_1,s_2,\cdots,s_n$作为碎片发送给参与者$P_1,P_2,\cdots,P_n$
| $Deliver$ | ||||
|
$s_1$ $\downarrow$ |
$s_2$ $\downarrow$ |
$\cdots$ |
$s_{n-1}$ $\downarrow$ |
$s_n$ $\downarrow$ |
| $P_1$ | $P_2$ | $\cdots$ | $P_{n-1}$ | $P_{n}$ |
秘密重构:
任意$t$个参与者用它们手中的值计算Lagrange插值,恢复$a(x)$的表达式,然后计算出$a(0)$
回顾:Lagrange插值Lagrange插值 - Isakovsky - 博客园 (cnblogs.com)
| $P_1$ | $P_2$ | $P_3$ |
|
$s_1$ $\searrow$ |
$s_2$ $\downarrow$ |
$s_3$ $\swarrow$ |
|
$\nearrow$ $s_4$ |
$\cdots$ |
$\nwarrow$ $s_t$ |
| $P_4$ | $\cdots$ | $P_t$ |
在原有参与者持有的秘密碎片不变的情况下,分发者可以给新的参与者分发新的秘密碎片.
此外,分发者也可以分发数量不等的秘密碎片以体现各分享者的不同重要性.
问题:
该体系只能抵挡被动攻击.
若分发者分发的秘密碎片是虚假的,参与者完全无法察觉.
若在重构过程中,参加的参与者刚好等于门限值,那么,某个参与者提供了虚假的碎片的行为无法被察觉.
若在重构过程中,参加的参与者数量大于门限值,那么如果某个参加者包含不持有秘密碎片,却使用虚假的碎片冒名参与重构,则它可能在重构过程中的会话环节"白嫖"到其他参与者正确的信碎片并恢复出秘密.
可验证的密码分享体系(VSS, Verifiable Secret Sharing):
该体系是传统的秘密分享体系的修正.
该方案要求分发者在分发秘密碎片时同时广播对秘密碎片的承诺,以防止分发虚假的碎片.
也要求在重构阶段时,参与者也要承诺自己提供的碎片,同样是为了防止虚假碎片.
下面介绍两个VSS的示例
Feldman的VSS体系:
该方案是Shamir门限秘密体系的拓展.
系统参数:
设参与者数量为$n$,门限值为$t$
取大素数$p$,$G$为$p$阶循环群,$g$为其一个生成元,
$s\in[0,p-1]$为要分享的秘密
秘密分发:
分发者$Deliver$的工作如下:
- 选择一个$t$阶随机多项式$$a(x)=s+\alpha_1 x+ \alpha_2 x^2 + \cdots +\alpha_{t-1}x^{t-1}$$ 其中$\alpha_{j}\in [1,p-1]$,(为了描述的一致性,记$\alpha_0=s$)
- 对于$i=1,2,\cdots,n$,将$x=i$代入$a(x)$计算出$a(i)$,令$s_i=a(i)$
- 将$s_1,s_2,\cdots,s_n$作为碎片发送给参与者$P_1,P_2,\cdots,P_n$
- 计算并广播承诺$B_0,B_1,\cdots,B_{t-1}$,其中$B_j=g^{\alpha_j}$
| $Deliver$ | ||||
|
$s_1$ $B_0,B_1,\cdots,B_{t-1}$ $\downarrow$ |
$s_2$ $B_0,B_1,\cdots,B_{t-1}$ $\downarrow$ |
$\cdots$ |
$s_{n-1}$ $B_0,B_1,\cdots,B_{t-1}$ $\downarrow$ |
$s_n$ $B_0,B_1,\cdots,B_{t-1}$ $\downarrow$ |
| $P_1$ | $P_2$ | $\cdots$ | $P_{n-1}$ | $P_{n}$ |
参与者$P_i$收到自己的碎片$s_i$后,判断下式是否成立
$g^{s_i}=\Pi^{t-1}_{j=0}(B_j)^{(i^j)}$
若成立则接收碎片有效,否则碎片无效,$P_i$可选择向分发者要求重新发送正确的碎片.
事实上,如果分发者向参与者$P_i$传送了正确碎片$s_i$的话,
$$\begin{aligned}
g^{s_i}=&g^{a(i)}\\
=&g^{s+\alpha_1i+\alpha_2i^2+\cdots+\alpha_{t-1}i^{t-1}}\\
=&g^s\cdot g^{\alpha_1i}\cdot g^{\alpha_2i^2}\cdots g^{\alpha_{t-1}i^{t-1}}\\
=&B_0B_1^iB_2^{i^2}\cdots B_{t-1}^{i^{t-1}}\\
=&\Pi_{j=0}^{t-1}B_{j}^{(i^j)}
\end{aligned}$$
通过此过程,参与者可确定分发者是否诚实.
秘密重构:
在重构开始前,向其他参与重构的参与者秘密发送自己的碎片,然后用$g^{s_i}=\Pi^{t-1}_{j=0}(B_j)^{(i^j)}$检查其他人发来的碎片.
这样,不诚实的参与者也会被检查出来.
随后的步骤同Shamir体系的秘密重构步骤
安全性:
由于离散对数问题是难解的,因此,仅通过$B_{i}$的信息难以求解$s_{i}$
Pedersen的VSS体系:
在Feldman的方案中,秘密分发者要在分发秘密时,将承诺$B_i=g^{s_i}$一并给出,这就导致必须依赖离散对数问题难解性的假设,方案只能是计算安全的,Pedersen将此方案再次拓展,构造出了一个信息论安全的方案
系统参数:
设参与者人数为$n$,门限值为$t$
$p$为大素数,$G$为$p$阶循环群,
$g,h$为$G$上随机的两个生成元,任何人均难以计算离散对数$\log_gh$,
设$s=[0,p-1]$为要分享的秘密
秘密分发:
分发者$Deliver$的工作如下:
- 选择两个$t$阶随机多项式
$a(x)=s+\alpha_1 x+ \alpha_2 x^2 + \cdots +\alpha_{t-1}x^{t-1}$
$b(x)=\beta_0+\beta_1 x+ \beta_2 x^2 + \cdots +\beta_{t-1}x^{t-1}$
其中$\alpha_{j},\beta_j\in [1,p-1]$,(为了描述的一致性,记$\alpha_0=s$) - 对于$i=1,2,\cdots,n$,将$x=i$代入$a(x)$计算出$a(i)$,令$s_i=a(i)$
- 将$s_1,s_2,\cdots,s_n$作为碎片发送给参与者$P_1,P_2,\cdots,P_n$
- 计算并广播承诺值$C_0,C_1,\cdots,C_{t-1}$,其中$C_j=g^{\alpha_j}h^{\beta_j}$
| $Deliver$ | ||||
|
$s_1$ $C_0,C_1,\cdots,C_{t-1}$ $\downarrow$ |
$s_2$ $C_0,C_1,\cdots,C_{t-1}$ $\downarrow$ |
$\cdots$ |
$s_{n-1}$ $C_0,C_1,\cdots,C_{t-1}$ $\downarrow$ |
$s_n$ $C_0,C_1,\cdots,C_{t-1}$ $\downarrow$ |
| $P_1$ | $P_2$ | $\cdots$ | $P_{n-1}$ | $P_{n}$ |
参与者收到碎片时,验证下面的等式是否成立
$g^{s_{i_1}}h^{s_{i_2}}=\Pi^{t-1}_{j=0}(C_j)^{(i^j)}$
若成立则接收碎片有效,否则碎片无效,$P_i$可选择向分发者要求重新发送正确的碎片.
$$\begin{aligned}
g^{s_{i_1}}h^{s_{i_2}}=&g^{a(i)}h^{b(i)}\\
=&g^{\alpha_0+\alpha_1i+\alpha_2i^2+\cdots+\alpha_{t-1}i^{t-1}}\cdot h^{\beta_0+\beta_1i+\beta_2i^2+\cdots+\beta_{t-1}i^{t-1}}\\
=&g^{\alpha_0}h^{\beta_0}\cdot g^{\alpha_1i}h^{\beta_1i}\cdot g^{\alpha_2i^2}h^{\beta_2i^2}\cdots g^{\alpha_{t-1}i^{t-1}}h^{\beta_{t-1}i^{t-1}}\\
=&C_0C_1^iC_2^{i^2}\cdots C_{t-1}^{i^{t-1}}\\
=&\Pi_{j=0}^{t-1}C_{j}^{(i^j)}
\end{aligned}$$
秘密重构:
同Feldman体系中的重构操作.
注意,因为函数$b(x)$始终只被分发者掌握,因此其他人无法从承诺值$C_j$中获取任何有关秘密$s_0$的信息
公开可验证密码分享体系(PVSS, Publicly Verifiable Secret Sharing):
在PVSS体系中,对秘密碎片分发过程的正确性验证不再仅限于参与者,任何人都可执行此操作.
PVSS可用于设计密钥托管系统,可撤销匿名性的电子支付协议等.
Schoenmakers的PVSS方案:
注意,该方案分发的秘密只能是循环群(如椭圆曲线)上的随机元素
初始化:
设参与者数量为$n$,门限值为$t$
设$p$为大素数,$G$为$p$阶循环群,在其上计算离散对数问题是困难的,因此,对于随机选择的两个生成元$g,h$,任何人都难以计算离散对数$\log_gh$
选定哈希函数$H:\{0,1\}^* \to [0,p-1]$
每个参与者$P_i$选择$x_i\in[0,p-1]$,要求$gcd(x_i,\varphi(p))=1$,计算$z_i=x_i^{-1} \mod \varphi(p)$(或者描述为$x_i\cdot z_i=k\varphi(p)+1$,其中$k$为整数),将$(x_i,z_i)$作为自己的私钥秘密保留,将$y_i=h^{x_i}$作为公钥广播出去.
分发者$Deliver$选择随机数$s\in[0,p-1]$,计算$S=h^{s}$,作为要分发的秘密.
| 公开 | ||||
|
$\uparrow$ $y_1$ |
$\uparrow$ $y_2$ |
$\cdots$ |
$\uparrow$ $y_{n-1}$ |
$\uparrow$ $y_n$ |
| $P_1$ | $P_2$ | $\cdots$ | $P_{n-1}$ | $P_{n}$ |
秘密分发:
Deliver的工作:
分发者Deliver执行如下操作以构造,并以加密的秘密碎片的形式分发秘密碎片:
- 选取形如$$p(x)=s+\alpha_1x+\alpha_2x^2+\cdots+\alpha_{t-1}x^{t-1}$$的随机多项式,其中$\alpha_i\in[1,p-1]$(为了描述的一致性,记$\alpha_0=s$)
- 将$x=1,x=2,\cdots,x=n$分别代入$p(x)$计算出$p(1),p(2)\cdots,p(n)$
- 计算$s_1,s_2,\cdots,s_n$,其中$$s_i=h^{p(i)}$$
- 使用参与者的公钥$y_1,y_2,\cdots,y_n$计算并公开加密的秘密碎片$Y_1,Y_2,\cdots,Y_n$,其中$$Y_i=(y_i)^{p(i)}$$
为了达到加密的秘密碎片的公开可验证,Deliver需要进行以下操作:
- 计算并公开多项式$p(x)$的每个系数$\alpha_0(=s),\alpha_1,\cdots,\alpha_{t-1}$分别对应公共承诺$C_0,C_1,\cdots,C_{t-1}$,其中$$C_j=g^{\alpha_j}$$
- 通过公共承诺计算出对每个成员$P_1,P_2,\cdots,P_n$的私人承诺$X_1,X_2,\cdots,X_n$,其中$$\begin{aligned}
X_i=&\Pi_{j=0}^{t-1}(C_j)^{(i^j)}\\
=&\Pi_{j=0}^{t-1}(g^{\alpha_j})^{(i^j)}\\
=&g^{\alpha_0}\cdot g^{\alpha_1\cdot i}\cdot g^{\alpha_2i^2}\cdots g^{\alpha_{t-1}i^{t-1}}\\
=&g^{\alpha_0+\alpha_1i+\alpha_2i^2+\cdots+\alpha_{t-1}i^{t-1}}\\
=&g^{p(i)}
\end{aligned}$$ 但私人承诺可以不必直接公开,实际上,公共承诺与私人承诺是等价的,因为任何人都可以通过公开的公共承诺,计算对某个成员的私人承诺. - 选取随机数$\omega_1,\omega_2,\cdots,\omega_n\in[0,p-1]$
- 计算$a_{1},a_{2},\cdots,a_{n}$,其中$$a_{i}=g^{\omega_i}$$
- 计算$b_{1},b_{2},\cdots,b_{n}$,其中$$b_{i}=y_i^{\omega_i}$$
- 计算公共质询值$$c=H(X_1,X_2,\cdots,X_n,Y_1,Y_2,\cdots,Y_n,a_{1},a_{2},\cdots,a_{n},b_{1},b_{2},\cdots,b_n)$$
- 计算对成员$P_1,P_2,\cdots,P_n$的应答$r_1,r_2,\cdots,r_n$,其中$$r_i=\omega_i-p(i)c$$
- 将$PROOF_D=(c,r_1,r_2,\cdots,r_n)$作为知识证据公开
| 公开 |
|
$\uparrow$ $C_0,C_1,\cdots,C_{t-1}$ $Y_1,Y_2,\cdots,Y_n$ $PROOF_D=(c,r_1,r_2,\cdots,r_n))$ |
| $Deliver$ |
(任何人都可充当的)验证者的工作:
获得Deliver的公开信息后,任何人想验证任意一个加密的秘密碎片$Y_i$的有效性,需要进行以下步骤:
- 使用公共承诺自行计算出所有的私人承诺$$X_i=\Pi_{j=0}^{t-1}(C_j)^{(i^j)}=g^{p(i)}$$
- 观察$X_i=g^{p(i)},Y_i=y_i^{p(i)}$,因为$X_i,Y_i$的底数$g,y_i$均是已知的,只需要比较它们的指数是否相同,但由于离散对数问题的难解性,进行这样的比较需要借助知识证据$PROOF_D$,并且绕几个弯:
- 计算所有的
$$\begin{aligned}
a_i^{'}=&g^{r_i}(X^{'}_i)^c \\
=&g^{r_i}X_i^c \\
=&g^{\omega_i-p(i)c}(g^{p(i)})^c\\
=&g^{\omega_i}\\
=&a_i
\end{aligned}$$$$\begin{aligned}
b_i^{'}=&{y_i}^{r_i}Y_i^c \\
=&{y_i}^{r_i}Y_i^c \\
=&{y_i}^{\omega_i-p(i)c}(y_i^{p(i)})^c\\
=&y_i^{\omega_i}\\
=&b_i
\end{aligned}$$ -
然后计算
$$c'=H(X^{'}_1,X^{'}_2,\cdots,X^{'}_n,Y_1,Y_2,\cdots,Y_n,a^{'}_{1},a^{'}_{2},\cdots,a^{'}_{n},b^{'}_{1},b^{'}_{2},\cdots,b^{'}_n)$$
如果$c'=c$,则接受Deliver的所有输出为有效.
不考虑哈希碰撞,显然$c'=c$当且仅当Deliver正确运行了协议.
- 计算所有的
参与者的工作:
收到加密的秘密碎片后$P_1,P_2,\cdots,P_n$分别需要使用自己的私钥$z_i$计算$$S_i=Y_i^{z_i}$$以还原秘密碎片$S_i$
实际上,
$$\begin{aligned}
S_i=&Y_i^{z_i}\\
=&(y_i^{p(i)})^{z_i}\\
=&((h^{x_i})^{p(i)})^{z_i}\\
=&h^{x_i \cdot z_i\cdot p(i)} \\
=&h^{p(i)} \mod p\qquad (x_i\cdot z_i=k\varphi(p)+1,h^{\varphi(p)}=1)
\end{aligned}$$
秘密重构:
碎片有效性检查:
每个参与者$P_i$除了向其他的参与者提交自己的秘密碎片$S_i$以外,还需要公布一个知识证据$PROOF_{P_i}$,在不透露$x_i$的前提下证明$$y_i=h^{x_i},Y_i=S_i^{x_i}$$的指数均是$x_i$
为此,$P_i$进行如下操作:
- 选取一个随机数$\omega_{P_i}\in[0,p-1]$,
- 计算$a_{P_i}=h^{\omega_{P_i}},b_{P_i}=S_i^{\omega_{P_i}}$
- 计算$c_{P_i}=H(y_i,Y_i,a_{P_i},b_{P_i})$
- 计算$r_{P_i}=\omega_{P_i}-x_ic$
- 将知识证据$PROOF_{P_i}=(c_{P_i},r_{P_i})$和秘密碎片$S_i$一同发送给其他参与秘密重构的成员
其他人收到后,按如下的方式进行验证:
-
计算
$$\begin{aligned}
a_{P_i}^{'}=&h^{r_{P_i}}y_i^{c_{P_i}}\\
=&h^{\omega_{P_i}-x_ic_{P_i}}(h^{x_i})^{c_{P_i}}\\
=&h^{\omega_{P_i}}
\end{aligned}$$$$\begin{aligned}
b_{P_i}^{'}=&S_i^{r_{P_i}}Y_i^{c_{P_i}}\\
=&S_i^{\omega_{P_i}-x_ic_{P_i}}(S_i^{x_i})^{c_{P_i}}\\
=&S_i^{\omega_{P_i}}
\end{aligned}$$ - 计算$$c^{'}_{P_i}=H(y_i,Y_i,a^{'}_{P_i},b^{'}_{P_i})$$
- 判断$c^{'}_{P_i}=c_{P_i}$是否成立,若成立则接受,若不成立,则说明成员$P_i$试图拿着虚假的秘密碎片白嫖别人的秘密碎片,中止此次重构.
秘密重构:
在验证秘密碎片$S_1,S_2,\cdots,S_t$均有效后,使用以下类似Lagrange插值的方法还原秘密:
$$\Pi_{i=1}^{t}S_i^{\lambda_i}$$
其中$\lambda_i=\underset{j=0,1,\cdots,i-1,i+1,\cdots,t-1}{\Pi}(\frac{j}{j-i})$
$$\begin{aligned}
\Pi_{i=1}^{t}S_i^{\lambda_i}=&\Pi_{i=1}^{t}(h^{p(i)})^{\lambda_i}\\
=&h^{\Sigma_{i=1}^{t}p(i)\cdot \lambda_i}
\end{aligned}$$
观察指数部分,$$\begin{aligned}&\Sigma_{i=1}^{t}p(i)\cdot \lambda_i\\=&\Sigma_{i=1}^{t}p(i)\underset{j=0,1,\cdots,i-1,i+1,\cdots,t-1}{\Pi}(\frac{j}{j-i})\end{aligned}$$实际上就是Lagrange插值表达式$$\Sigma_{i=1}^{t}p(x_i)\underset{j=0,1,\cdots,i-1,i+1,\cdots,t-1}{\Pi}(\frac{x-x_j}{x_i-x_j})$$在$x=0$时的值
因此$$\Sigma_{i=1}^{t}p(i)\cdot \lambda_i=p(0)$$
原式:
$$\begin{aligned}
\Pi_{i=1}^{t}S_i^{\lambda_i}=&h^{p(0)}\\
=&h^s
\end{aligned}$$
至此,重构出了秘密$h^{s}$.
动态秘密分享:
前文的秘密分享方案中,攻击者可能用很长时间,一个一个攻击参与者,从而最终得到秘密.
动态秘密分享(proactive secret sharing)的概念的提出就是为了解决此问题.
该方案将秘密的有效期分为若干个阶段,每个阶段的秘密虽然不变,但秘密碎片会更新,这样攻击者在前一阶段获得的碎片,在新的阶段就会失去意义.
原本的秘密:
分发后的秘密:
更新后的秘密:
Herzber的动态秘密分享方案:
系统参数:
$n$为参与者的人数,$t$为门限值,
$p>n$为大素数,
设欲分享的秘密为$s\in [1,p-1]$
秘密分发:
类似于Shamir的方案,分发者$Deliver$
- 选择一个$t$阶随机多项式$$f^{(0)}(x)=s+\alpha^{(0)}_1 x+ \alpha^{(0)}_2 x^2 + \cdots +\alpha^{(0)}_{t-1}x^{t-1}$$其中$\alpha^{(0)}_{j}\in [1,p-1]$,(为了描述的一致性,记$\alpha^{(0)}_0=s$)
- 对于$i=1,2,\cdots,n$,将$x=i$代入$f(x)$计算出$f(i)$,令$s_i^{(0)}=f(i)$
- 将$s^{(0)}_1,s^{(0)}_2,\cdots,s^{(0)}_n$作为碎片发送给参与者$P_1,P_2,\cdots,P_n$
碎片更新:
已经掌握碎片$s_i^{(T-1)}$的参与者$P_i$在$T$时刻开始时,执行如下步骤将自己的碎片更新为$s_i^{(T)}$
- 选择$t-1$个随机数$$\delta^{(T-1)}_{(i,1)},\delta^{(T-1)}_{(i,2)},\cdots,\delta^{(T-1)}_{(i,t-1)}\in [1,p-1]$$构造$t-1$次多项式$$\Delta^{(T-1)}_i(x)=0+\delta^{(T-1)}_{(i,1)}x+\delta^{(T-1)}_{(i,2)}x^2+\cdots+\delta^{(T-1)}_{(i,t-1)}x^{t-1}$$显然有$\Delta^{(T-1)}_i(0)=0$
- 计算$$u^{(T-1)}_{(i,1)},u^{(T-1)}_{(i,2)},\cdots,u^{(T-1)}_{(i,i-1)},u^{(T-1)}_{(i,i+1)},\cdots,u^{(T-1)}_{(i,n)}$$其中$$u^{(T-1)}_{(i,j)}=\Delta^{(T-1)}_i(j)$$发送给$P_1,P_2,\cdots,P_{i-1},P_{i+1},\cdots,P_{n}$
另计算$$u^{(T-1)}_{(i,i)}=\Delta^{(T-1)}_i(i)$$自己保留
- 在收到其他参与者发来的$$u^{(T-1)}_{(1,i)},u^{(T-1)}_{(2,i)},\cdots,u^{(T-1)}_{(i-1,i)},u^{(T-1)}_{(i+1,i)},\cdots,u^{(T-1)}_{(n,i)}$$后,加上自己的$$u^{(T-1)}_{(i,i)}$$其中$$u^{(T-1)}_{(j,i)}=\delta^{(T-1)}_j(i)$$按照如下公式更新自己的碎片$$s_i^{(T)}=s_i^{(T-1)}+\Sigma_{j=1}^nu^{(T-1)}_{(j,i)}$$
- 除保留新碎片$s_i^{(T)}$外,销毁其他数据.
秘密重构:
设当前碎片更新的时间节点为$T'$,$t$个参与者$P_1,P_2,\cdots,P_t$进行如下操作以重构出秘密$s$
- 向其他人发送自己的$s_i^{T'}$
- 计算$\Sigma_{i=1}^{t}\lambda_is_i^{(T')}$,其中$\lambda_i=\underset{j=0,1\cdots,i-1,i+1,\cdots,t-1}{\Pi}\frac{j}{j-i}$为Lagrange插值系数
数学归纳法证明:
$0$时间节点时,有
$$\begin{aligned}
\Sigma_{i=1}^{t}\lambda_is_i^{(0)}=&\Sigma_{i=1}^{t}\lambda_if^{(0)}(i)\\
=&f^{(0)}(0) \qquad (\text{Lagrange插值})\\
=&s
\end{aligned}$$
若$\Sigma_{i=1}^{t}\lambda_is_i^{(T-1)}=s$,则
$$\begin{aligned}
\Sigma_{i=1}^{t}\lambda_is_i^{(T)}=&\Sigma_{i=1}^{t}\lambda_i(s_i^{(T-1)}+\Sigma_{j=1}^nu^{(T-1)}_{(j,i)})\\
=&\Sigma_{i=1}^{t}\lambda_i(s_i^{(T-1)}+\Sigma_{j=1}^n\Delta^{(T-1)}_{j}(i))\\
=&\Sigma_{i=1}^{t}\lambda_is_i^{(T-1)}+\Sigma_{i=1}^{t}\Sigma_{j=1}^{n}(\lambda_i\Delta^{(T-1)}_{j}(i))\\
=&\Sigma_{i=1}^{t}\lambda_is_i^{(T-1)}+\Sigma_{j=1}^{n}\Sigma_{i=1}^{t}(\lambda_i\Delta^{(T-1)}_{j}(i))\qquad(\text{交换求和顺序})\\
=&\Sigma_{i=1}^{t}\lambda_is_i^{(T-1)}+\Sigma_{j=1}^{n}\Delta_j^{(T-1)}(0)\qquad(\text{Lagrange插值})\\
=&\Sigma_{i=1}^{t}\lambda_is_i^{(T-1)}+\Sigma_{j=1}^{n}0 \\
=&\Sigma_{i=1}^{t}\lambda_is_i^{(T-1)}\\
=&s\end{aligned}$$
综上,在任意的$T'$时间节点,总有$$\Sigma_{i=1}^{t}\lambda_is_i^{(T')}=s$$
问题:
由于该方案是基于Shamir的方案设计的,因此也只能抵抗被动攻击者,当分发者Deliver分发虚假的秘密碎片,或者在碎片更新过程中任意一个参与者$P_i$提交虚假的$u_{(i,j)}$,将会导致碎片更新失败.
改进的Herzber的动态秘密分享方案:
该方案在更新过程中引入了检查操作,防止参与者提交虚假信息.
系统参数:
$n$为参与者的人数,$t$为门限值,
$p>n$为大素数,
设欲分享的秘密为$s\in [1,p-1]$
为了碎片更新过程中的检查工作,引入$p$阶循环群$G$
秘密分发:
同Herzber的方案.
碎片更新:
已经掌握碎片$s_i^{(T-1)}$的参与者$P_i$在$T$时刻开始时,执行如下步骤将自己的碎片更新为$s_i^{(T)}$
- 选择$t-1$个随机数$$\delta^{(T-1)}_{(i,1)},\delta^{(T-1)}_{(i,2)},\cdots,\delta^{(T-1)}_{(i,t-1)} \in [1,p-1]$$构造$t-1$次多项式$$\Delta^{(T-1)}_i(x)=0+\delta^{(T-1)}_{(i,1)}x+\delta^{(T-1)}_{(i,2)}x^2+\cdots+\delta^{(T-1)}_{(i,t-1)}x^{t-1}$$显然有$\Delta^{(T-1)}_i(0)=0$
- 计算$$u^{(T-1)}_{(i,1)},u^{(T-1)}_{(i,2)},\cdots,u^{(T-1)}_{(i,i-1)},u^{(T-1)}_{(i,i+1)},\cdots,u^{(T-1)}_{(i,n)}$$其中$$u^{(T-1)}_{(i,j)}=\Delta^{(T-1)}_i(j)$$发送给$P_1,P_2,\cdots,P_{i-1},P_{i+1},\cdots,P_{n}$
另计算$$u^{(T-1)}_{(i,i)}=\Delta^{(T-1)}_i(i)$$自己保留
- 计算并广播$$B^{(T-1)}_{(i,1)},B^{(T-1)}_{(i,2)},\cdots,B^{(T-1)}_{(i,t-1)}$$其中$$B^{(T-1)}_{(i,j)}=g^{\delta^{(T-1)}_{(i,j)}}$$作为对$$\delta^{(T-1)}_{(i,1)},\delta^{(T-1)}_{(i,2)},\cdots,\delta^{(T-1)}_{(i,t-1)}$$的签名
- 在收到其他参与者发来的$$u^{(T-1)}_{(1,i)},u^{(T-1)}_{(2,i)},\cdots,u^{(T-1)}_{(i-1,i)},u^{(T-1)}_{(i+1,i)},\cdots,u^{(T-1)}_{(n,i)}$$以及$$B^{(T-1)}_{(\cdot,\cdot)}$$后,依次判断当$j=1,2,\cdots,i-1,i+1,\cdots,n$时如下等式是否成立($j=i$时$B$就是自己算出来的当然不用验证)$$g^{u^{(T-1)}_{(j,i)}}=\Pi_{k=1}^{t-1}(B^{(T-1)}_{(j,t)})^{i^t}$$
- 若所有人发来的更新信息验证成功,则加上自己的$$u^{(T-1)}_{(i,i)}$$按照如下公式更新自己的碎片$$s_i^{(T)}=s_i^{(T-1)}+\Sigma_{j=1}^nu^{(T-1)}_{(j,i)}$$
- 除保留新碎片$s_i^{(T)}$外,销毁其他数据.
当参与者$P_j$构造的多项式$\Delta^{(T-1)}_j(x)=0$时,有
$$\begin{aligned}
&\Pi_{k=1}^{t-1}(B^{(T-1)}_{(j,t)})^{i^t}\\
=&\Pi_{k=1}^{t-1}g^{\delta^{(T-1)}_{(j,t)}\cdot i^t}\\
=&g^{\Sigma_{k=1}^{t-1}\delta^{(T-1)}_{(j,t)}\cdot i^t}\\
=&g^{\Sigma_{k=0}^{t-1}\delta^{(T-1)}_{(j,t)}\cdot i^t} \qquad (\delta^{(T-1)}_{(j,0)}=0)\\
=&g^{\Delta^{(T-1)}_j(i)}\\
=&g^{u_{(j,i)}^{(T-1)}}
\end{aligned}$$
秘密重构:
同Herzber的方案.
其他特殊的秘密分享体系:
除以上有分发者的方案外,基于不同的需求,还可以构造没有分发者的秘密分享机制.
Joint-Shamir-RSS(一种无分发者的随机秘密分享):
该方案中,不存在秘密分发者,仅有参与者$P_1,P_2,\cdots,P_n$,它们以交互的方式协商出一个随机秘密$s$,并且各自得到一个秘密碎片$s_i$,但在重构秘密之前,没人知道随机产生的秘密是什么.
参与者共$n$个,门限值为$t$
系统参数包括大素数$p$
碎片生成与分发:
每个参与者$P_i$进行如下工作:
- 选择一个$t-1$次随机多项式$$a_i(x)=\alpha_{(i,0)}+\alpha_{(i,1)}x+\alpha_{(i,2)}x^2+\cdots+\alpha_{(i,t-1)}x^{t-1}$$其中$$\alpha_0,\alpha_1,\cdots,\alpha_{t-1}\in[1,p-1]$$令$A_i=\alpha_{(i,0)}$作为自己要分享的秘密
- 计算$$s_{(i,1)},s_{(i,2)},\cdots.s_{(i,i-1)},s_{(i,i+1)},\cdots,s_{(i,n)}$$其中$$s_{(i,j)}=a_i(j)$$并分别秘密发送给$P_1,P_2,\cdots,P_{i-1},P_{i+1},\cdots,P_{n}$
- 收到其他参与者发来的$$s_{(1,i)},s_{(2,i)},\cdots.s_{(i-1,i)},s_{(i-2,i)},\cdots,s_{(n,i)}$$后,加上自己的$$s_{(i,i)}=a_i(i)$$计算$$S_i=\Sigma_{j=1}^{n}s_{(j,i)}$$作为自己的碎片.
秘密重构:
任意$t$个参与者提交它们的$S_1,S_2,\cdots,S_t$,共同计算
$$\Sigma_{k=1}^{t}\lambda_iS_i$$
其中$$\lambda_i=\underset{j=0,1\cdots,i-1,i+1,\cdots,t-1}{\Pi}\frac{j}{j-i}$$为Lagrange插值系数
实际上,最后重构出来的秘密是
$$\begin{aligned}
&\Sigma_{k=1}^{t}\lambda_iS_i\\
=&\Sigma_{k=1}^{t}\lambda_i(\Sigma_{j=1}^{n}s_{(j,i)})\\
=&\Sigma_{j=1}^{n}(\Sigma_{k=1}^{t}\lambda_ia_j(i))\\
=&\Sigma_{j=1}^{n}a_j(0)\\
=&\Sigma_{j=1}^{n}A_j
\end{aligned}$$
问题:
可以看出该方案因为基于朴素的Shamir秘密分享方案,因此无法抵抗不遵守协议的主动攻击者.
Joint-Shamir-ZSS(Zero Secret Sharing)(一种无分发者的随机秘密分享):
该方案和上一个方案类似,区别在于参与者$P_i$分享的秘密$A_i=\alpha_{(i,0)}=0$
标签：8.1,秘密,笔记,碎片,密码,cdots,alpha,Sigma,参与者 From： https://www.cnblogs.com/isakovsky/p/17728451.html