1. 秘密共享简介

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

秘密共享定义如下：秘密持有者$S$需要将原始秘密$m$在参与者集合中 P 1 , P 2 , . . . , P n P_1,P_2,...,P_n P1​,P2​,...,Pn​分享，$S$分发给 P 1 P_1 P1​子秘密 m p i m_{p_i} mpi​​，使得只有特定参与者的集合才能够从他们的子秘密中恢复秘密$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 ≤ i ≤ n ) P_i(1 leq i leq n) Pi​(1≤i≤n) 分配共享的过程如下:

(1) 秘密分发

可信中心随机选取多项式 f ( x ) = a t − 1 x t − 1 + … + a 2 x 2 + a 1 x + a 0 ∈ f(x)=a_{t-1} x^{t-1}+ldots+a_2 x^2+a_1 x+a_0 in f(x)=at−1​xt−1+…+a2​x2+a1​x+a0​∈ $GF(q)[x]$, 常数 a 0 = k a_0=k a0​=k 为要分享的秘密。

可信中心在 $GF(q)$ 中选择 $n$ 个非零的互不相同的 元素 x 1 , x 2 , … , x n x_1, x_2, ldots, x_n x1​,x2​,…,xn​, 计算 y i = f ( x i ) , 1 ≤ i ≤ n y_i=fleft(x_iright), 1 leq i leq n yi​=f(xi​),1≤i≤n, 将子密钥 ( x i , y i ) left(x_i, y_iright) (xi​,yi​) 分配给共享者 P i ( x i P_ileft(x_iright. Pi​(xi​ 是公开的, y i y_i yi​ 为 P i P_i Pi​ 的秘密共享)。

（2） 秘密重构

给定 $t$ 个共享 y i s ( 1 ≤ s ≤ t ) y_{i_s}(1 leq s leq t) yis​​(1≤s≤t), 从Lagrange多项式重构的

f ( x ) = ∑ s = 1 t y i s ∏ j = 1 , j ≠ s t x − x j x i s − x i j , k = a 0 = f ( 0 ) = ∑ s = 1 t y i s ∏ j = 1 , j ≠ s t − x j x i s − x i j = ∑ s = 1 t b s y i s , begin{aligned} & f(x)=sum_{s=1}^t y_{i_s} prod_{j=1, j neq 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 neq s}^t frac{-x_j}{x_{i_s}-x_{i_j}}=sum_{s=1}^t b_s y_{i_s}, end{aligned} ​f(x)=s=1∑t​yis​​j=1,j=s∏t​xis​​−xij​​x−xj​​,k=a0​=f(0)=s=1∑t​yis​​j=1,j=s∏t​xis​​−xij​​−xj​​=s=1∑t​bs​yis​​,​其中, b s = Π j = 1 , j ≠ s t − x j x i s − x i j b_s=Pi_{j=1, j neq s}^t frac{-x_j}{x_{i_s}-x_{i_j}} bs​=Πj=1,j=st​xis​​−xij​​−xj​​ (Lagrange插值系数), 运算都是$GF(q)$上的运算。

Eg 设 $t=3,n=5,q=9,k=11$, 随机选取 a 1 = 2 , a 2 = 7 a_1=2, a_2=7 a1​=2,a2​=7, 得多项式为 h ( x ) = ( 7 x 2 + 2 x + 71 )   m o d   19 h(x)=left(7 x^2+2 x+71right) bmod 19 h(x)=(7x2+2x+71)mod19选择 x i = i x_i=i xi​=i, 则由 y i = h ( x i ) , 1 ≤ i ≤ 5 y_i=hleft(x_iright), quad 1 leq i leq 5 yi​=h(xi​),1≤i≤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$ { 4 a 2 + 2 a 1 + a 0 = 5 9 a 2 + 3 a 1 + a 0 = 4 25 a 2 + 5 a 1 + a 0 = 6 begin{cases} 4 a_2+2 a_1+a_0=5 \ 9 a_2+3 a_1+a_0=4 \ 25 a_2+5 a_1+a_0=6end{cases} ⎩ ⎨ ⎧​4a2​+2a1​+a0​=59a2​+3a1​+a0​=425a2​+5a1​+a0​=6​从而解得 k = a 0 = 11 k=a_0=11 k=a0​=11。

3. Asmuth-Bloom方案

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

令 p , d 1 , d 2 , … , d n p, d_1, d_2, ldots, d_n p,d1​,d2​,…,dn​ 是满足下列条件的一组正整数: p > k ; d 1 < d 2 < … < d n p>k ; quad d_1<d_2<ldots<d_n p>k;d1​<d2​<…<dn​对所有的 i , gcd ⁡ ( p , d i ) = 1 ; i, operatorname{gcd}left(p, d_iright)=1 ; i,gcd(p,di​)=1;

对 i ≠ j , gcd ⁡ ( d i , d j ) = 1 ; d 1 d 2 ⋯ d t > i neq j, operatorname{gcd}left(d_i, d_jright)=1 ; d_1 d_2 cdots d_t> i=j,gcd(di​,dj​)=1;d1​d2​⋯dt​> p d n − t + 2 d n − t + 3 ⋯ d n p d_{n-t+2} d_{n-t+3} cdots d_n pdn−t+2​dn−t+3​⋯dn​

令 N = d 1 d 2 ⋯ d t N=d_1 d_2 cdots d_t N=d1​d2​⋯dt​ 是 $t$ 个最小整数之积，则 $N/p$ 大于任意 $t-1$ 个 d i d_i di​ 。令 $r$ 是区间 $[0,\lfloor N/p\rfloor -1]$ 中的一个随机整数, 并公布 $p,r$ 。

(1) 秘密分发

将 $k$ 划分为 $n$ 个共享, 计算 k ′ = k + r p k^{prime}=k+r p k′=k+rp, 则 k ′ ∈ [ 0 , N − 1 ] 。 n k^{prime} in[0, N-1] 。 n k′∈[0,N−1]。n 个共享 为 k i = k ′ modd ⁡ i , i = 1 , 2 , … , n k_i=k^{prime} operatorname{modd}_i, i=1,2, ldots, n ki​=k′moddi​,i=1,2,…,n, 将子密钥 ( d i , k i ) left(d_i, k_iright) (di​,ki​) 分配给共享者 P i ( d i P_ileft(d_iright. Pi​(di​ 是公开的, k i k_i ki​ 为 P i P_i Pi​

(2) 秘密重构

若给定 $t$ 个共享 k i 1 , … , … , k i t k_{i_1}, ldots, ldots, k_{i_t} ki1​​,…,…,kit​​, 则由中国剩余定理可知, 同余方程组 { x ′ ≡ k i 1 mod ⁡ d i 1 x ′ ≡ k i 2 mod ⁡ d i 2 ⋯ x ′ ≡ k i t mod ⁡ d i t begin{cases} x^{prime} equiv k_{i_1} operatorname{mod} d_{i_1} \ x^{prime} equiv k_{i_2} operatorname{mod} d_{i_2} \ cdots \ x^{prime} equiv k_{i_t} operatorname{mod} d_{i_t} end{cases} ⎩ ⎨ ⎧​x′≡ki1​​moddi1​​x′≡ki2​​moddi2​​⋯x′≡kit​​moddit​​​关于模 N 1 = d i 1 d i 2 ⋯ d i t N_1=d_{i_1} d_{i_2} cdots d_{i_t} N1​=di1​​di2​​⋯dit​​ 在 [ 0 , N 1 − 1 ] left[0, N_1-1right] [0,N1​−1] 内有唯一解 $x$, 因为 N 1 ≥ N ≥ k ′ N_1 geq N geq k^{prime} N1​≥N≥k′, 推出 k ′ = x k^{prime}=x k′=x 。 最后计算出 k = k ′ − r p k=k^{prime}-r p k=k′−rp, 即 k = k ′   m o d   p k=k^{prime} bmod p k=k′modp 。

Eg 设 t = 2 , n = 3 , p = 7 , k = 4 , d 1 = 9 , d 2 = 11 , d 3 = 13 t=2, n=3, p=7, k=4, d_1=9, d_2=11, d_3=13 t=2,n=3,p=7,k=4,d1​=9,d2​=11,d3​=13, 则 N = d 1 d 2 = 99 > 91 = 7 ⋅ 13 = p ⋅ d 3 . N=d_1 d_2=99>91=7 cdot 13=p cdot d_3 . N=d1​d2​=99>91=7⋅13=p⋅d3​.在 $[0,[99/7]-1]=[0,13]$ 之间随机取 r = 10 , k ′ = k + r p = 4 + 10 × 7 = 74 r=10, k^{prime}=k+r p=4+10 times 7=74 r=10,k′=k+rp=4+10×7=74, k 1 ≡ k ′  modd  d 1 ≡ 74   m o d   9 ≡ 2 k 2 ≡ k ′   m o d   d 2 ≡ 74   m o d   11 ≡ 8 k 3 ≡ k ′   m o d   d 3 ≡ 74   m o d   13 ≡ 9 begin{aligned} & k_1 equiv k^{prime} text { modd } d_1 equiv 74 bmod 9 equiv 2 \ & k_2 equiv k^{prime} bmod d_2 equiv 74 bmod 11 equiv 8 \ & k_3 equiv k^{prime} bmod d_3 equiv 74 bmod 13 equiv 9end{aligned} ​k1​≡k′ modd d1​≡74mod9≡2k2​≡k′modd2​≡74mod11≡8k3​≡k′modd3​≡74mod13≡9​3 个子密钥为 $\{(9,2),(11,8),(13,9)\}$。

若知道 $\{(9,2),(11,8)\}$, 可建立方程组: { k ′ ≡ 2 mod ⁡ 9 k ′ ≡ 8 mod ⁡ 11 begin{cases} k^{prime} equiv 2 operatorname{mod} 9 \ k^{prime} equiv 8 operatorname{mod} 11 \end{cases} {k′≡2mod9k′≡8mod11​根据中国剩余定理，解得： k ′ ≡ ( 11 × 5 × 2 + 9 × 5 × 8 )   m o d   ≡ 74 k^{prime} equiv(11 times 5 times 2+9 times 5 times 8) bmod equiv 74 k′≡(11×5×2+9×5×8)mod≡74因此 k ′ ≡ k   m o d   p = 4 k^{prime} equiv k bmod p=4 k′≡kmodp=4

4. 可验证的秘密共享

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

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

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

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

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

4.1 Feldman的VSS方案

（1）秘密分发

可信中心选取阶随机多项式： f ( x ) = a t − 1 x t − 1 + … + a 2 x 2 + a 1 x + a 0 ∈ G F ( q ) [ x ] f(x)=a_{t-1} x^{t-1}+ldots+a_{2} x^{2}+a_{1} x+a_{0} in G F(q)[x] f(x)=at−1​xt−1+…+a2​x2+a1​x+a0​∈GF(q)[x]常数 a 0 = s a_{0}=s a0​=s为要分发的秘密;

可信中心选择$n$个非零的互不相同的元素 x 1 , x 2 , … , x n ∈ G F ( q ) x_{1}, x_{2}, ldots, x_{n} in G F(q) x1​,x2​,…,xn​∈GF(q)，计算 y i = f ( x i ) , 1 ≤ i ≤ n y_{i}=fleft(x_{i}right), 1 leq i leq n yi​=f(xi​),1≤i≤n , 将子密钥 ( x i , y i ) left(x_{i}, y_{i}right) (xi​,yi​) 分配给共享者 P i P_{i} Pi​( ( x i ) left(x_{i}right) (xi​)是公开的, y i y_{i} yi​为 P i P_{i} Pi​的秘密共享)，可信中心计算并广播承诺 B j = g a j , 0 ≤ j < t B_{j}=g^{a_{j}}, 0 leq j<t Bj​=gaj​,0≤j<t。

参与者 P i P_{i} Pi​收到自己的碎片 y i y_{i} yi​后, 判断 g y i = Π j = 0 t − 1 B j x i j g^{y_{i}}=Pi_{j=0}^{t-1} B_{j}^{x_{i}^{j}} gyi​=Πj=0t−1​Bjxij​​是否成立, 如果成立, 则接受该 碎片为有效; 否则, P i P_{i} Pi​ 请求可信中心重新发送正确的碎片。

若可信中心向 P i P_{i} Pi​ 传送了正确的碎片 y i y_{i} yi​, 则有 g y i = g f ( x i ) = g a t − 1 r i t − 1 + … + a 2 x i 2 + a 1 x i + a 0 = g a t − 1 x i t − 1 … g a 2 x i 2 g a 1 x i g a 0 = B t − 1 x i t − 1 … B 2 x i 2 B 7 x i B 0 = Π j = 0 t − 1 B j x i j begin{aligned} g^{y_{i}=g^{fleft(x_{i}right)}} & =g^{a_{t-1} r_{i}^{t-1}+ldots+a_{2} x_{i}^{2}+a_{1} x_{i}+a_{0}} \ & =g^{a_{t-1} x_{i}^{t-1}} ldots g^{a_{2} x_{i}^{2}} g^{a_{1} x_{i}} g^{a_{0}} \ & =B_{t-1}^{x_{i}^{t-1}} ldots B_{2}^{x_{i}^{2}} B_{7}^{x_{i}} B_{0} \ & =Pi_{j=0}^{t-1} B_{j}^{x_{i}^{j}} end{aligned} gyi​=gf(xi​)​=gat−1​rit−1​+…+a2​xi2​+a1​xi​+a0​=gat−1​xit−1​…ga2​xi2​ga1​xi​ga0​=Bt−1xit−1​​…B2xi2​​B7xi​​B0​=Πj=0t−1​Bjxij​​​（2）秘密重构

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

Feldman的VSS方案中, 由于可信中心在广播承诺时将 B 0 = g a 0 = g s B_{0}=g^{a_{0}}=g^{s} B0​=ga0​=gs也作为一个承诺发出, 因此方案仅是计算安全的。

4.2 Pedersen的VSS方案

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

（1）秘密分发

可信中心选取两个$t$阶随机多项式： a ( x ) = a t − 1 x t − 1 + … + a 2 x 2 + a 7 x + a 0 ∈ G F ( q ) [ x ] b ( x ) = b t − 1 x t − 1 + … + b 2 x 2 + b 1 x + b 0 ∈ G F ( q ) [ x ] begin{array}{l} a(x)=a_{t-1} x^{t-1}+ldots+a_{2} x^{2}+a_{7} x+a_{0} in G F(q)[x] \ b(x)=b_{t-1} x^{t-1}+ldots+b_{2} x^{2}+b_{1} x+b_{0} in G F(q)[x] end{array} a(x)=at−1​xt−1+…+a2​x2+a7​x+a0​∈GF(q)[x]b(x)=bt−1​xt−1+…+b2​x2+b1​x+b0​∈GF(q)[x]​常数 a 0 = s a_{0}=s a0​=s为要分发的秘密。

可信中心选择$n$个非零的互不相同的元素 x 1 , x 2 , … , x n ∈ G F ( q ) x_{1}, x_{2}, ldots, x_{n} in G F(q) x1​,x2​,…,xn​∈GF(q) ,计算 y i = ( s i , s i 2 ) = ( a ( x i ) , b ( x i ) ) , 1 ≤ i ≤ n y_{i}=left(s_{i}, s_{i 2}right)=left(aleft(x_{i}right), bleft(x_{i}right)right), 1 leq i leq n yi​=(si​,si2​)=(a(xi​),b(xi​)),1≤i≤n 将子密钥 ( x i , y i ) left(x_{i}, y_{i}right) (xi​,yi​)分配给共享者 P i P_{i} Pi​( x i x_{i} xi​是公开的, y i y_{i} yi​为 P i P_{i} Pi​的秘密共享)。可信中心计算并广播承诺 C j = g a j h b j , 0 ≤ j < t C_{j}=g^{a_{j}} h^{b_{j}}, 0 leq j<t Cj​=gaj​hbj​,0≤j<t 。

参与者 P i P_{i} Pi​ 收到自己的碎片 y i y_{i} yi​ 后, 判断 g s i ⌝ h s i 2 = ∏ j = 0 t − 1 C j x i j g^{s_{iurcorner}} h^{s_{i 2}}=prod_{j=0}^{t-1} C_{j}^{x_{i}^{j}} gsi┐​hsi2​=∏j=0t−1​Cjxij​​ 是否成立。如果成立, 则接受 该碎片为有效; 否则, P i P_{i} Pi​ 请求可信中心重新发送正确的碎片。

若可信中心向 P i P_{i} Pi​传送了正确的碎片 y i y_{i} yi​, 则有 g s i ⌝ h s i 2 = g a ( x i ) h b ( x i ) = ( g a t − 1 x i t − 1 + … + a 2 x i 2 + a 1 x i + a 0 ) ( h b t − 1 x i t − 1 + … + b 2 x i 2 + b 1 x i + b 0 ) = ( g a t − 1 h b t − 1 ) x i t − 1 … ( g a 2 h b 2 ) x i 2 ( g a a h b 1 ) x i g a 0 h b 0 = C t − 1 x i t − 1 … C 2 x i 2 C 1 x i C 0 = ∏ j = 0 t − 1 C j x i j begin{aligned} g^{s_{iurcorner}} h^{s_{i 2}}= & g^{aleft(x_{i}right)} h^{bleft(x_{i}right)}=left(g^{a_{t-1} x_{i}^{t-1}+ldots+a_{2} x_{i}^{2}+a_{1} x_{i}+a_{0}}right)left(h^{b_{t-1} x_{i}^{t-1}+ldots+b_{2} x_{i}^{2}+b_{1} x_{i}+b_{0}}right) \ & =left(g^{a} t-1 h^{b_{t-1}}right)^{x_{i}^{t-1}} ldotsleft(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}} ldots C_{2}^{x_{i}^{2}} C_{1}^{x_{i}} C_{0} \ & =prod_{j=0}^{t-1} C_{j}^{x_{i}^{j}} end{aligned} gsi┐​hsi2​=​ga(xi​)hb(xi​)=(gat−1​xit−1​+…+a2​xi2​+a1​xi​+a0​)(hbt−1​xit−1​+…+b2​xi2​+b1​xi​+b0​)=(gat−1hbt−1​)xit−1​…(ga2​hb2​)xi2​(gaahb1​)xi​ga0​hb0​=Ct−1xit−1​​…C2xi2​​C1xi​​C0​=j=0∏t−1​Cjxij​​​（2）秘密重构

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

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

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

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

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

(1) 每个参与者 P i P_i Pi​ 选择一个 $t-1$ 次随机多项式 f i ( x ) = a i , t − 1 x t − 1 + … + a i 2 x 2 + a i 1 x + a i 0 ∈ G F ( q ) [ x ] f_i(x)=a_{i, t-1} x^{t-1}+ldots+a_{i 2} x^2+a_{i1} x+a_{i0} in G F(q)[x] fi​(x)=ai,t−1​xt−1+…+ai2​x2+ai1​x+ai0​∈GF(q)[x], 以 a i 0 = f i ( 0 ) a_{i 0}=f_i(0) ai0​=fi​(0) 作为自己要让 P 1 , P 2 , … , P n P_1, P_2, ldots, P_n P1​,P2​,…,Pn​ 分享的秘密。

(2) P i P_i Pi​ 计算 s i j = f i ( x j ) s_{ij}=f_ileft(x_jright) sij​=fi​(xj​), 发送给 P j , j = 1 , 2 , … , n P_j, j=1,2, ldots, n Pj​,j=1,2,…,n, 如下所示: P 1 P 2 P j P n P 1 f 1 ( x 1 ) f 7 ( x 2 ) f 7 ( x j ) f 1 ( x n ) P 2 f 2 ( x 1 ) f 2 ( x 2 ) f 2 ( x j ) f 2 ( x n ) P i f i ( x 1 ) f i ( x 2 ) f i ( x j ) f i ( x n ) P n f n ( x 1 ) f n ( x 2 ) f n ( x j ) f n ( x n ) begin{array}{llllll} & P_1 & P_2 & P_j & P_n \ P_1 & f_1left(x_1right) & f_7left(x_2right) & f_7left(x_jright) & f_1left(x_nright) \ P_2 & f_2left(x_1right) & f_2left(x_2right) & f_2left(x_jright) & f_2left(x_nright) \ P_i & f_ileft(x_1right) & f_ileft(x_2right) & f_ileft(x_jright) & f_ileft(x_nright) \ P_n & f_nleft(x_1right) & f_nleft(x_2right) & f_nleft(x_jright) & f_nleft(x_nright) end{array} P1​P2​Pi​Pn​​P1​f1​(x1​)f2​(x1​)fi​(x1​)fn​(x1​)​P2​f7​(x2​)f2​(x2​)fi​(x2​)fn​(x2​)​Pj​f7​(xj​)f2​(xj​)fi​(xj​)fn​(xj​)​Pn​f1​(xn​)f2​(xn​)fi​(xn​)fn​(xn​)​(3) P j P_j Pj​ 收到其他参与者的值 s i j = f i ( x j ) , i = 1 , 2 , … , n s_{i j}=f_ileft(x_jright), i=1,2, ldots, n sij​=fi​(xj​),i=1,2,…,n, 计算 s j = ∑ i = 1 n f i ( x j ) s_j=sum_{i=1}^n f_ileft(x_jright) sj​=∑i=1n​fi​(xj​) 作为 自己最终分享秘密的碎片。

从协议中可以看出, 若令 f ( x ) = ∑ i = 1 n f i ( x ) f(x)=sum_{i=1}^n f_i(x) f(x)=∑i=1n​fi​(x), 则 f ( x j ) = ∑ i = 1 n f i ( x j ) fleft(x_jright)=sum_{i=1}^n f_ileft(x_jright) f(xj​)=∑i=1n​fi​(xj​) 。

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