已知两个秘密的碎片,计算秘密的乘积的碎片:
已知两个秘密$\alpha_0,\beta_0$分别实现了门限值为$t$的分享
记$$f_{\alpha}(x)=\alpha_0+\alpha_1x+\cdots+\alpha_{t-1}x^{t-1}$$
$$f_{\beta}(x)=\beta_0+\beta_1x+\cdots+\beta_{t-1}x^{t-1}$$
秘密碎片为$$A_1=f_{\alpha}(1),A_2=f_{\alpha}(2),\cdots,A_n=f_{\alpha}(n)$$
$$B_1=f_{\beta}(1),B_2=f_{\beta}(2),\cdots,B_n=f_{\beta}(n)$$
碎片$(A_1,B_1),(A_2,B_2),\cdots,(A_n,B_n),$分别由成员$P_1,P_2,\cdots,P_n$持有,但是,参与者们并不想分别恢复秘密$\alpha_0,\beta_0$(可能包含有隐私信息),而是想直接恢复秘密的乘积$\alpha_0\cdot\beta_0$,该怎么办?
实际上,各参与者直接计算手中碎片的乘积$C_i=A_i\cdot B_i$,得到的$C_i$就是秘密$\alpha_0\cdot \beta_0$门限值为$2t-1$的碎片.
任意$2t-1$个$C_1,C_2,\cdots,C_{2t-1}$碎片进行Lagrange插值后得到的结果是如下多项式.
$$\begin{aligned}
f_{\alpha}(x)\cdot f_{\beta}(x)&=\alpha_0\beta_0+(\alpha_0\beta_1+\alpha_1\beta_0)x+(\alpha_0\beta_2+\alpha_1\beta_1+\alpha_2\beta_0)x^2+\cdots+\alpha_{t-1}\beta_{t-1}x^{2t-2}
\end{aligned}$$
将$x=0$代入即可得到$\alpha_0\cdot\beta_0$
已知秘密的碎片,计算秘密的逆元的碎片:
已知秘密$k_0$实现了门限值为$t$的分享
$$f(x)=k_0+k_1x+\cdots+k_{t-1}x^{t-1}$$
秘密碎片$$x_1=f(1),x_2=f(2),\cdots,x_n=f(n)$$
分别由成员$$P_1,P_2,\cdots,P_n$$持有
但参与者们并不想分别恢复秘密$k_0$,而是想直接恢复出$k_0$的逆元$k_0^{-1}$,该怎么办?
成员$P_i$做如下工作
- 和其他成员协作,以无分发者的随机秘密分享(Joint-Shamir-RSS,密码协议学习笔记(8.1):秘密分享 - Isakovsky - 博客园 (cnblogs.com))的方式,实现对随机秘密$a$的门限值为$t$的分享,获得碎片$a_i$
- 使用上文所述的协议,计算出$x_ia_i$,此即为秘密$ka$的门限值为$2t-1$的碎片
- 和其他成员协作重构出$ka$的值
- 计算$u_i=(ka)^{-1}a_i$,即得到秘密$k^{-1}$的门限为$t$的碎片.
成员中的任意$t$个,不妨记为$P_1,P_2,\cdots,P_t$可协作恢复$k^{-1}$,只需计算
$$\Sigma_{i=1}^t\lambda_iu_i$$即可.
其中$$\lambda_i=\underset{j=0,1\cdots,i-1,i+1,\cdots,t-1}{\Pi}\frac{j}{j-i}$$为Lagrange插值系数.
$$\begin{aligned}
\Sigma_{i=1}^t\lambda_iu_i=&\Sigma_{i=1}^t\lambda_i(ka)^{-1}a_i\\
=&(ka)^{-1}\Sigma_{i=1}^t\lambda_ia_i\\
=&(ka)^{-1}a\\
=&k
\end{aligned}$$