秘密共享
1. 秘密共享简介
秘密共享通过将秘密以适当的方式拆分，拆分后的每一个份额由不同的参与者管理，单个参与者无法恢复秘密信息，只有若干个参与者一同协作才能恢复秘密消息。
秘密共享定义如下：秘密持有者
S
S
S需要将原始秘密
m
m
m在参与者集合中
P
1
,
P
2
,
.
.
.
,
P
n
P_1,P_2,...,P_n
P1,P2,...,Pn分享，
S
S
S分发给
P
1
P_1
P1子秘密
m
p
i
m_{p_i}
mpi，使得只有特定参与者的集合才能够从他们的子秘密中恢复秘密
m
m
m，而其他参与者不能得到秘密
m
m
m的任何信息。
能够计算出秘密
m
m
m的参与者集合
P
P
P的一个子集
A
⊆
P
A \subseteq P
A⊆P，称为一个授权子集。令
Γ
\Gamma
Γ为所有授权子集构成的集合，则称
Γ
\Gamma
Γ访问结构。
秘密共享方案一般描述如下：将共享的秘密
m
m
m分割成
n
n
n个子秘密，并将其分发至
n
n
n个参与者，使得授权子集
Γ
\Gamma
Γ中的参与者可共同恢出复秘密
m
m
m，而非授权子集中的参与者无法得到关于秘密
m
m
m的任何信息。
2. Shamir秘密共享方案
Adi Shamir于1979年提出了基于拉格朗日(Lagrange)插值定理的
(
t
,
n
)
(t,n)
(t,n)-门限方案。该方案利用有限域上的次随机多项式来分享秘密，被分享的秘密为多项式的零次系数，恢复秘密至少需要t个多项式上的点。
方案描述如下：
设
G
F
(
q
)
G F(q)
GF(q) 是一个有限域,
q
q
q为公开大素数, 共享的密钥
k
∈
G
F
(
q
)
k \in G F(q)
k∈GF(q), 可信中心给
n
(
n
<
q
)
n(n< 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−1xt−1+…+a2x2+a1x+a0∈
G
F
(
q
)
[
x
]
G F(q)[x]
GF(q)[x], 常数
a
0
=
k
a_0=k
a0=k 为要分享的秘密。
可信中心在
G
F
(
q
)
G F(q)
GF(q) 中选择
n
n
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=f\left(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
(
x
i
P_i\left(x_i\right.
Pi(xi 是公开的,
y
i
y_i
yi 为
P
i
P_i
Pi 的秘密共享)。
（2） 秘密重构
给定
t
t
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∑tyisj=1,j=s∏txis−xijx−xj,k=a0=f(0)=s=1∑tyisj=1,j=s∏txis−xij−xj=s=1∑tbsyis,其中,
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=stxis−xij−xj (Lagrange插值系数), 运算都是
G
F
(
q
)
G F(q)
GF(q)上的运算。
Eg 设
t
=
3
,
n
=
5
,
q
=
9
,
k
=
11
t=3, n=5, q=9, k=11
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+71\right) \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=h\left(x_i\right), \quad 1 \leq i \leq 5
yi=h(xi),1≤i≤5, 很容易得到
5
5
5个子密钥
h
(
1
)
=
1
,
h
(
2
)
=
5
,
h
(
3
)
=
4
,
h
(
4
)
=
17
,
h
(
5
)
=
6
h(1)=1, h(2)=5, h(3)=4, h(4)=17, h(5)=6
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
h(2)=5, h(3)=4, h(5)=6
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=6\end{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
)
(t,n)
(t,n)-门限方案。该方案中，成员的共享是由秘密
S
S
S 得出的数
y
y
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_i\right)=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_j\right)=1 ; d_1 d_2 \cdots d_t>
i=j,gcd(di,dj)=1;d1d2⋯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+2dn−t+3⋯dn
令
N
=
d
1
d
2
⋯
d
t
N=d_1 d_2 \cdots d_t
N=d1d2⋯dt 是
t
t
t 个最小整数之积，则
N
/
p
N / p
N/p 大于任意
t
−
1
t-1
t−1 个
d
i
d_i
di 。令
r
r
r 是区间
[
0
,
⌊
N
/
p
⌋
−
1
]
[0,\lfloor N / p\rfloor-1]
[0,⌊N/p⌋−1] 中的一个随机整数, 并公布
p
,
r
p, r
p,r 。
(1) 秘密分发
将
k
k
k 划分为
n
n
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_i\right)
(di,ki) 分配给共享者
P
i
(
d
i
P_i\left(d_i\right.
Pi(di 是公开的,
k
i
k_i
ki 为
P
i
P_i
Pi
(2) 秘密重构
若给定
t
t
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′≡ki1moddi1x′≡ki2moddi2⋯x′≡kitmoddit关于模
N
1
=
d
i
1
d
i
2
⋯
d
i
t
N_1=d_{i_1} d_{i_2} \cdots d_{i_t}
N1=di1di2⋯dit 在
[
0
,
N
1
−
1
]
\left[0, N_1-1\right]
[0,N1−1] 内有唯一解
x
x
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=d1d2=99>91=7⋅13=p⋅d3.在
[
0
,
[
99
/
7
]
−
1
]
=
[
0
,
13
]
[0,[99 / 7]-1]=[0,13]
[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 9\end{aligned}
k1≡k′ modd d1≡74mod9≡2k2≡k′modd2≡74mod11≡8k3≡k′modd3≡74mod13≡93 个子密钥为
{
(
9
,
2
)
,
(
11
,
8
)
,
(
13
,
9
)
}
\{(9,2),(11,8),(13,9)\}
{(9,2),(11,8),(13,9)}。
若知道
{
(
9
,
2
)
,
(
11
,
8
)
}
\{(9,2),(11,8)\}
{(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−1xt−1+…+a2x2+a1x+a0∈GF(q)[x]常数
a
0
=
s
a_{0}=s
a0=s为要分发的秘密;
可信中心选择
n
n
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}=f\left(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−1Bjxij是否成立, 如果成立, 则接受该 碎片为有效; 否则,
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^{f\left(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−1rit−1+…+a2xi2+a1xi+a0=gat−1xit−1…ga2xi2ga1xiga0=Bt−1xit−1…B2xi2B7xiB0=Πj=0t−1Bjxij**（2）秘密重构**
假设每个参与者都接受到正确的碎片, 他们中的任意
t
t
t个可执行 Shamir门限秘密分享方案中的重构算法恢复出院时秘密, 即
P
i
P_{i}
Pi向参与重构的其他人广播自己的碎片，这样每个参与重构的成员均可验证所接收到的碎片的有效性，然后使用Lagrange揷值公式计算出秘密
S
S
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
k
k，因此是信息论安全的。
（1）秘密分发
可信中心选取两个
t
t
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−1xt−1+…+a2x2+a7x+a0∈GF(q)[x]b(x)=bt−1xt−1+…+b2x2+b1x+b0∈GF(q)[x]常数
a
0
=
s
a_{0}=s
a0=s为要分发的秘密。
可信中心选择
n
n
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(a\left(x_{i}\right), b\left(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=gajhbj,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_{i\urcorner}} h^{s_{i 2}}=\prod_{j=0}^{t-1} C_{j}^{x_{i}^{j}}
gsi┐hsi2=∏j=0t−1Cjxij 是否成立。如果成立, 则接受 该碎片为有效; 否则,
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_{i\urcorner}} h^{s_{i 2}}= & g^{a\left(x_{i}\right)} h^{b\left(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}} \ldots\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}} \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−1xit−1+…+a2xi2+a1xi+a0)(hbt−1xit−1+…+b2xi2+b1xi+b0)=(gat−1hbt−1)xit−1…(ga2hb2)xi2(gaahb1)xiga0hb0=Ct−1xit−1…C2xi2C1xiC0=j=0∏t−1Cjxij**（2）秘密重构**
假设每个参与者都接受到正确的碎片, 他们中的任意
t
t
t个可执行 Shamir门限秘密分享方案中的重构算法恢复出院时秘密, 即
P
i
P_{i}
Pi向参与重构的其他人广播自己的碎片, 这样每个参与重构的成员均可验证所接收到的碎片的有效性, 然后使用Lagrange揷值公式计算出秘密
s
s
s 。
Pedersen的VSS方案中，可信中心在广播承诺时与秘密
s
s
s相关的信息仅为
C
0
=
g
s
h
b
0
C_{0}=g^{s} h^{b_{0}}
C0=gshb0，没有泄露关于
s
s
s的任何信息，因此方案是信息论安全的。
5. 无分发者的随机秘密共享
在该秘密体制中不存在秘密分发者，仅有参与者
P
1
,
P
2
,
.
.
.
,
P
n
P_1,P_2,...,P_n
P1,P2,...,Pn，他们以交互的方式协商出一个随机秘密
s
s
s，并各自得到该秘密的一个碎片
s
i
s_i
si，但每个参与者都不知道这个随机秘密的具体值，除非他们公布自己的碎片并重构该秘密。
基于Shamir的秘密分享体制的一个无秘密分发者的
(
t
,
n
)
(t,n)
(t,n)秘密分享体制，称为**Joint-Shamir-RSS方案**（Joint Shamir Random Secret Sharing）。
(1) 每个参与者
P
i
P_i
Pi 选择一个
t
−
1
t-1
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−1xt−1+…+ai2x2+ai1x+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_i\left(x_j\right)
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_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}
P1P2PiPnP1f1(x1)f2(x1)fi(x1)fn(x1)P2f7(x2)f2(x2)fi(x2)fn(x2)Pjf7(xj)f2(xj)fi(xj)fn(xj)Pnf1(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_i\left(x_j\right), 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_i\left(x_j\right)
sj=∑i=1nfi(xj) 作为 自己最终分享秘密的碎片。
从协议中可以看出, 若令
f
(
x
)
=
∑
i
=
1
n
f
i
(
x
)
f(x)=\sum_{i=1}^n f_i(x)
f(x)=∑i=1nfi(x), 则
f
(
x
j
)
=
∑
i
=
1
n
f
i
(
x
j
)
f\left(x_j\right)=\sum_{i=1}^n f_i\left(x_j\right)
f(xj)=∑i=1nfi(xj) 。
秘密重构阶段，只需任意
t
t
t个参与者使用自己拥有的秘密碎片
s
i
s_i
si执行Shamir秘密分享体制的秘密重构即可。
本文转载自: https://blog.csdn.net/apr15/article/details/128889028
版权归原作者 机器学习Zero 所有， 如有侵权，请联系我们删除。
版权归原作者 机器学习Zero 所有， 如有侵权，请联系我们删除。