安全多方计算 - Shamir秘密分享方案
概述
秘密共享 (Secret Sharing) 是一种用于保护敏感数据（如加密密钥）的技术。它将一个秘密分成多个部分，并将这些部分分发给多个参与者。只有当各个部分组合到一起时，才能恢复原始的秘密。它将风险在多方之间分散，从而提高了系统的安全性。
早在秦朝就有秦阳陵虎符：“甲兵之符，右在皇帝，左在阳陵”。只有"合符"无间才可调拨军队。这可谓古人的一大智慧，也可以看作是一种秘密共享的实践。
但这里的秘密共享要求所有参与者合作才能恢复原始的秘密(虎符)，如果任意一个参与方将自己的秘密份额丢失或损坏，就再也无法恢复原始秘密。
门限秘密共享
什么是门限秘密共享
门限秘密共享是一种密码学技术，将秘密
S
S
S 分割为
n
n
n 个部分，并将这些部分分发给
n
n
n 个参与者。所谓门限，是在分割这些秘密的时候，设置一个大小位于 1 和
n
n
n 之间的
k
k
k 值，使得给定任意
k
−
1
k - 1
k−1 个或更少的秘密份额，都不能够计算得到秘密
S
S
S 的任何信息；当给定任意
k
k
k 个或更多的秘密份额的时候，就能够计算得到秘密
S
S
S。这被称为
(
k
,
n
)
(k, n)
(k,n) 门限秘密共享方案。这意味着这
n
n
n 个参与者中最多
k
−
1
k - 1
k−1 个参与者泄露了他们的秘密份额，秘密
S
S
S 仍然是安全的。
直观理解
想象一下，秘密
S
S
S 是一个藏宝箱的密码。我们不希望单个参与者独自打开藏宝箱，因此我们可以构造方案将密码分成多个部分分给参与方，只有当至少 2 个参与者合作时，他们才能拼凑出完整的密码并打开藏宝箱。同时即便有个别秘密份额丢失或被盗，剩下的参与方依然可以重构秘密。
为了更具体地说明这一点，我们来看一个例子：
假设我们有一个秘密值
S
=
2
S = 2
S=2，我希望将这个秘密值分享给 4 个参与者，并且要求至少 2 个参与者才能恢复出秘密值。现在将这个秘密值作为y轴上的一个点的纵坐标，绘制一条穿过点（0，2）的随机直线。然后随机取4个 x 坐标值 3、5、6、7 作为4名参与者的 id，并计算这些 id 对应的直线上点的纵坐标值，分配给 4 名参与者。例如，参与者 3 得到的秘密份额 s3。每个参与者只知道自己的 id 和对应的秘密份额。
4 个参与者有了秘密份额，接下来就应该考虑使用秘密份额恢复秘密了。任意一个参与者单独都无法恢复出来秘密值，因为单独一份秘密份额相当于只有坐标系上的一个点，无法确定秘密份额生成的时候选择了哪条线。这也意味着不知道这条线与 y 轴相交的位置。
当有两个或更多参与者提供秘密份额时，相当于坐标系中有多个点存在，就能够绘制出这条直线。这条直线与 y 轴的交点，就是原来的秘密值。
以上是对门限秘密共享的基本概念和直观理解的展示。接下来我们会详细讨论 Shamir 秘密共享方法，它是最经典和广泛使用的门限秘密共享技术之一。
Shamir秘密共享
Shamir秘密共享是一种门限秘密共享方案。
秘密分享
Shamir秘密共享方案基于拉格朗日多项式插值原理。它将秘密
S
S
S 分成
n
n
n 个部分，每个参与者得到的部分都是秘密
S
S
S 的一个多项式的值。只有当至少
k
k
k 个参与者合作时，才能恢复原始的秘密
S
S
S。
具体来说，多项式上的
k
k
k 个点能够唯一确定小于或等于
k
−
1
k-1
k−1 次的多项式。2 个点足以定义一条线，3 个点足以定义一条抛物线，4 个点足以定义一条立方曲线，依此类推。
假设秘密数据
S
S
S 是一个数字，为了把它分成不同份额
S
i
S_i
Si，选择一个随机
k
−
1
k-1
k−1 次多项式。多项式的一般形式为
f
(
x
)
=
a
0
+
a
1
x
+
a
2
x
2
+
⋅
⋅
⋅
+
a
k
−
1
x
k
−
1
f(x) = a_0 + a_1x + a_2x^2 + ··· + a_{k-1}x^{k-1}
f(x)=a0+a1x+a2x2+⋅⋅⋅+ak−1xk−1，其中
a
0
=
S
a_0 = S
a0=S 是要保护的秘密。
秘密拥有者随机生成
k
−
1
k-1
k−1 个随机数
a
1
,
a
2
,
.
.
.
,
a
k
−
1
a_1, a_2, ...,a_{k-1}
a1,a2,...,ak−1，作为多项式的系数以确定多项式
f
(
x
)
f(x)
f(x)。然后选取
n
n
n 个互不相同的整数
x
1
,
x
2
,
.
.
.
,
x
n
x_1, x_2, ...,x_n
x1,x2,...,xn 作为参与方 id，将这些整数带入到
f
(
x
)
f(x)
f(x) 进行计算，得到
s
1
=
f
(
x
1
)
,
s
2
=
f
(
x
2
)
,
.
.
.
,
s
n
=
f
(
x
n
)
s_1 = f(x_1), s_2 = f(x_2), ..., s_n = f(x_n)
s1=f(x1),s2=f(x2),...,sn=f(xn)。将计算得到的
n
n
n 个值分别分配给
n
n
n 个参与方，每个参与方掌握的秘密份额就是
(
x
i
,
f
(
x
i
)
)
(x_i, f(x_i))
(xi,f(xi))。
例如，假定一个秘密值
S
=
45
S=45
S=45，要求将其分给 10 个参与方，至少 3 方参与计算才能够恢复出原始秘密，即
n
=
10
,
k
=
3
n = 10, k = 3
n=10,k=3。构造对应的多项式
f
(
x
)
=
45
+
19
x
+
13
x
2
f(x) = 45 + 19x + 13x^2
f(x)=45+19x+13x2。在此多项式上选取连续的整数点作为各个子秘密：
D
0
=
(
1
,
77
)
;
D
1
=
(
2
,
135
)
;
D
2
=
(
3
,
219
)
;
D
3
=
(
4
,
329
)
;
D
4
=
(
5
,
465
)
;
D
5
=
(
6
,
627
)
;
D
6
=
(
7
,
815
)
;
D
7
=
(
8
,
1029
)
;
D
8
=
(
9
,
1269
)
;
D
9
=
(
10
,
1535
)
D_0 = (1, 77); D_1 = (2, 135); D_2 = (3, 219); D_3 = (4, 329); D_4 = (5, 465); D_5 = (6, 627); D_6 = (7, 815); D_7 = (8, 1029); D_8 = (9, 1269); D_9 = (10, 1535)
D0=(1,77);D1=(2,135);D2=(3,219);D3=(4,329);D4=(5,465);D5=(6,627);D6=(7,815);D7=(8,1029);D8=(9,1269);D9=(10,1535)。
秘密重建
对于
S
i
S_i
Si 值的任意
k
k
k 个子集，我们可以通过插值找到
f
(
x
)
f(x)
f(x) 的多项式系数，然后计算
S
=
f
(
0
)
S = f(0)
S=f(0)。另一方面，仅知道子集中的
k
−
1
k - 1
k−1 个并不足以计算出
S
S
S。
在生成秘密份额的时候，已经确定需要
k
k
k 个秘密份额来恢复原始秘密。即根据
(
x
1
,
s
1
)
,
(
x
2
,
s
2
)
,
.
.
.
,
(
x
k
,
s
k
)
(x_1, s_1), (x_2, s_2), ..., (x_k, s_k)
(x1,s1),(x2,s2),...,(xk,sk) 等一系列点构造出原始的多项式
f
(
x
)
f(x)
f(x)，进而求解得到秘密值
S
=
f
(
0
)
=
a
0
S = f(0) = a_0
S=f(0)=a0。
Shamir秘密共享的方案使用拉格朗日插值法求解多项式。
f
(
x
)
=
∑
i
=
0
n
y
i
l
i
(
x
)
f(x) = \sum_{i=0}^{n}y_il_i(x)
f(x)=i=0∑nyili(x)
其中
l
i
(
x
)
=
(
x
−
x
1
)
(
x
−
x
2
)
.
.
.
(
x
−
x
n
)
(
x
i
−
x
1
)
(
x
i
−
x
2
)
.
.
.
(
x
i
−
x
n
)
l_i(x) = \frac{(x-x_1)(x-x_2)...(x-x_n)}{(x_i-x_1)(x_i-x_2)...(x_i-x_n)}
li(x)=(xi−x1)(xi−x2)...(xi−xn)(x−x1)(x−x2)...(x−xn) 为拉格朗日插值基函数。在求解
y
i
l
i
(
x
)
y_il_i(x)
yili(x) 的求解之后，对其求和，就能够获得目标多项式。
为了重建秘密，任意选取3个参与方的秘密份额作为输入。这里选择 id 为
2
，
3
，
6
2， 3， 6
2，3，6 的参与方进行秘密重建。
(
x
0
,
y
0
)
=
(
2
,
135
)
;
(
x
1
,
y
1
)
=
(
3
,
219
)
;
(
x
2
,
y
2
)
=
(
6
,
627
)
(x_0, y_0) = (2, 135); (x_1, y_1) = (3, 219); (x_2, y_2) = (6, 627)
(x0,y0)=(2,135);(x1,y1)=(3,219);(x2,y2)=(6,627)。
l
0
(
x
)
=
x
−
x
1
x
0
−
x
1
∗
x
−
x
2
x
0
−
x
2
=
x
−
3
2
−
3
∗
x
−
6
2
−
6
=
1
4
x
2
−
9
4
x
+
9
2
l_0(x) = \frac{x-x_1}{x_0-x_1}*\frac{x-x_2}{x_0-x_2} = \frac{x-3}{2-3}* \frac{x-6}{2-6} = \frac{1}{4}x^2-\frac{9}{4}x+\frac{9}{2}
l0(x)=x0−x1x−x1∗x0−x2x−x2=2−3x−3∗2−6x−6=41x2−49x+29
l
1
(
x
)
=
x
−
x
0
x
1
−
x
0
∗
x
−
x
2
x
1
−
x
2
=
x
−
2
3
−
2
∗
x
−
6
3
−
6
=
−
1
3
x
2
+
8
3
x
−
4
l_1(x) = \frac{x-x_0}{x_1-x_0}*\frac{x-x_2}{x_1-x_2} = \frac{x-2}{3-2}* \frac{x-6}{3-6} = -\frac{1}{3}x^2+\frac{8}{3}x - 4
l1(x)=x1−x0x−x0∗x1−x2x−x2=3−2x−2∗3−6x−6=−31x2+38x−4
l
2
(
x
)
=
x
−
x
0
x
2
−
x
0
∗
x
−
x
1
x
2
−
x
1
=
x
−
2
6
−
2
∗
x
−
3
6
−
3
=
1
12
x
2
−
5
12
x
+
1
2
l_2(x) = \frac{x-x_0}{x_2-x_0}*\frac{x-x_1}{x_2-x_1} = \frac{x-2}{6-2}* \frac{x-3}{6-3} = \frac{1}{12}x^2-\frac{5}{12}x+\frac{1}{2}
l2(x)=x2−x0x−x0∗x2−x1x−x1=6−2x−2∗6−3x−3=121x2−125x+21
f
(
x
)
=
∑
i
=
0
2
y
i
l
i
(
x
)
=
y
0
l
0
(
x
)
+
y
1
l
1
(
x
)
+
y
2
l
2
(
x
)
=
135
(
1
4
x
2
−
9
4
x
+
9
2
)
+
219
(
−
1
3
x
2
+
8
3
x
−
4
)
+
627
(
1
12
x
2
−
5
12
x
+
1
2
)
=
13
x
2
+
19
x
+
45
f(x) = \sum_{i=0}^{2}y_il_i(x) = y_0l_0(x) + y_1l_1(x) + y_2l_2(x) \\ = 135(\frac{1}{4}x^2-\frac{9}{4}x+\frac{9}{2}) + \\ 219(-\frac{1}{3}x^2+\frac{8}{3}x - 4) + \\ 627(\frac{1}{12}x^2-\frac{5}{12}x+\frac{1}{2}) \\ = 13x^2 + 19x + 45
f(x)=i=0∑2yili(x)=y0l0(x)+y1l1(x)+y2l2(x)=135(41x2−49x+29)+219(−31x2+38x−4)+627(121x2−125x+21)=13x2+19x+45
至此，这个用于秘密分享的多项式重构完成，而秘密是自由系数，也就是45。
用图形化展示就是以下过程：
- 绘制份额
- 绘制相应抛物线
- 秘密就是与y轴交点
Shamir秘密共享的特点
前面提到的Shamir秘密共享方案使用的实数进行操作，虽然这种方法在数值上比较简单，但其安全性并不高。即使两个点不足以完美描述抛物线，它们仍然能够泄露有关秘密的部分信息。为了解决这一问题，Shamir秘密共享方案是在有限域上定义的，这样可以有效地提高安全性。在有限域上，多项式的图形变得不连贯和分散，这使得攻击者无法基于观察到的点对底层函数做出有根据的猜测。有限域的引入有效地防止了从简单点恢复多项式的秘密值。
以下是Shamir秘密共享的一些主要特点：
- 秘密份额的大小与原始数据大小无关：每个秘密份额的大小不会超过原始秘密的大小，这确保了秘密份额在存储和传输过程中的高效性。
- 动态调整秘密份额：当 k k k 值固定，秘密份额 s i s_i si 是可以动态增加或删除的，比如有参与方加入或离开不会影响其他的秘密份额；
- 秘密份额的修改：可以通过生成新的多项式来轻松修改秘密份额，同时保持原始秘密数据不变。这种修改可以提升安全性，因为暴露的秘密份额在更新后变得无效。
- 分级方案的实现：通过多项式的值的组合，可以实现分级方案。例如，可以根据参与方的重要性分配不同数量的秘密份额。比如，给公司的CEO分配3个秘密份额，给两位副总分配2个秘密份额，每位高管分配1个秘密份额。这样，对于 ( 3 , n ) (3, n) (3,n) 门限秘密共享方案，执行与原始秘密相关的活动需要至少3位高管共同参与，或者2位高管（其中包括至少一位副总）参与，或者仅由CEO独自进行操作。
这些特点使得Shamir秘密共享不仅在保密性和灵活性方面表现出色，还在多种实际应用场景中展现了其独特的优势。然而，秘密共享的真正潜力还包括其在加法和乘法操作中的支持。Shamir秘密共享不仅可以用于分割和恢复秘密，还可以在分裂态下进行加法和乘法运算。这意味着在多个参与方合作的情况下，可以对秘密进行复杂的操作，而最终的结果却不会暴露原始(秘密)数据。
接下来的部分将详细介绍Shamir秘密共享如何支持加法和乘法操作，以及这些特性如何提升其在实际应用中的价值。
对加法和乘法运算的支持
对加法运算的支持
在Shamir秘密共享方案中，加法运算支持意味着，在不恢复原始秘密的情况下，通过参与方之间的计算，就可以直接得到秘密值之和。这一特性使得在处理多个秘密时，我们能够利用其分享的份额进行加法操作。
示例说明
假设我们有两个秘密值：
S
1
=
45
S_1 = 45
S1=45 和
S
2
=
33
S_2 = 33
S2=33。对应的多项式为：
对于
S
1
S_1
S1，多项式为
f
1
(
x
)
=
45
+
19
x
+
13
x
2
f_1(x) = 45 + 19x + 13x^2
f1(x)=45+19x+13x2；对于
S
2
S_2
S2，多项式为
f
2
(
x
)
=
33
+
21
x
+
10
x
2
f_2(x) = 33 + 21x + 10x^2
f2(x)=33+21x+10x2。
仍采用前文中
x
=
{
2
,
3
,
6
}
x = \{2, 3, 6\}
x={2,3,6} 作为甲乙丙三方的
i
d
id
id。以其在多项式上的值
f
1
(
{
2
,
3
,
6
}
)
f_1(\{2, 3, 6\})
f1({2,3,6}) 和
f
2
(
{
2
,
3
,
6
}
)
f_2(\{2, 3, 6\})
f2({2,3,6}) 作为分配给各方的秘密份额。
三方参与者甲、乙、丙分别持有秘密的拆分份额，表格如下：
参与方idS1份额 (
S
1
i
d
S1_{id}
S1id)S2份额 (
S
2
i
d
S2_{id}
S2id)
S
1
i
d
S1_{id}
S1id +
S
2
i
d
S2_{id}
S2id甲2135115250乙3219186405丙66275191146
如何在不恢复原始秘密的情况加，计算出来
S
1
+
S
2
S_1 + S_2
S1+S2 的结果呢？只需要甲乙丙分别计算各自本地秘密份额的和
S
1
i
d
+
S
2
i
d
S1_{id} + S2_{id}
S1id+S2id，然后对其进行插值计算。
l
0
(
x
)
=
x
−
x
1
x
0
−
x
1
∗
x
−
x
2
x
0
−
x
2
=
x
−
3
2
−
3
∗
x
−
6
2
−
6
=
1
4
x
2
−
9
4
x
+
9
2
l_0(x) = \frac{x-x_1}{x_0-x_1}*\frac{x-x_2}{x_0-x_2} = \frac{x-3}{2-3}* \frac{x-6}{2-6} = \frac{1}{4}x^2-\frac{9}{4}x+\frac{9}{2}
l0(x)=x0−x1x−x1∗x0−x2x−x2=2−3x−3∗2−6x−6=41x2−49x+29
l
1
(
x
)
=
x
−
x
0
x
1
−
x
0
∗
x
−
x
2
x
1
−
x
2
=
x
−
2
3
−
2
∗
x
−
6
3
−
6
=
−
1
3
x
2
+
8
3
x
−
4
l_1(x) = \frac{x-x_0}{x_1-x_0}*\frac{x-x_2}{x_1-x_2} = \frac{x-2}{3-2}* \frac{x-6}{3-6} = -\frac{1}{3}x^2+\frac{8}{3}x - 4
l1(x)=x1−x0x−x0∗x1−x2x−x2=3−2x−2∗3−6x−6=−31x2+38x−4
l
2
(
x
)
=
x
−
x
0
x
2
−
x
0
∗
x
−
x
1
x
2
−
x
1
=
x
−
2
6
−
2
∗
x
−
3
6
−
3
=
1
12
x
2
−
5
12
x
+
1
2
l_2(x) = \frac{x-x_0}{x_2-x_0}*\frac{x-x_1}{x_2-x_1} = \frac{x-2}{6-2}* \frac{x-3}{6-3} = \frac{1}{12}x^2-\frac{5}{12}x+\frac{1}{2}
l2(x)=x2−x0x−x0∗x2−x1x−x1=6−2x−2∗6−3x−3=121x2−125x+21
通过计算：
f
(
x
)
=
∑
i
=
0
2
y
i
l
i
(
x
)
=
250
(
1
4
x
2
−
9
4
x
+
9
2
)
+
405
(
−
1
3
x
2
+
8
3
x
−
4
)
+
1146
(
1
12
x
2
−
5
12
x
+
1
2
)
=
78
+
a
x
+
b
x
2
f(x) = \sum_{i=0}^{2}y_il_i(x) = 250(\frac{1}{4}x^2-\frac{9}{4}x+\frac{9}{2}) \\ \\+ 405(-\frac{1}{3}x^2+\frac{8}{3}x - 4) \\ \\+ 1146(\frac{1}{12}x^2-\frac{5}{12}x+\frac{1}{2}) \\ \\= 78 + ax + bx^2
f(x)=i=0∑2yili(x)=250(41x2−49x+29)+405(−31x2+38x−4)+1146(121x2−125x+21)=78+ax+bx2
直接计算常数项就好了，从计算结果可见，这个多项式的常数项为 78，即原始秘密
S
1
S_1
S1的值加上
S
2
S_2
S2的值，验证了Shamir秘密共享方案的同态加法支持。
通过这种方式，我们可以在不恢复原始秘密的情况下，通过参与方持有的份额计算出秘密的和。这证明了Shamir秘密共享对加法计算天然支持。
对乘法运算的支持
在Shamir秘密共享中，为了分享两个秘密
s
1
s_1
s1 和
s
2
s_2
s2，分别选取两个多项
p
p
p 和
q
q
q，满足
y
i
=
p
(
i
)
y_i = p(i)
yi=p(i) 和
z
i
=
q
(
i
)
z_i = q(i)
zi=q(i)，且
p
(
0
)
=
s
1
p(0) = s_1
p(0)=s1,
q
(
0
)
=
s
2
q(0) = s_2
q(0)=s2。如果各参与方持有
s
1
s_1
s1 的份额
(
x
i
,
y
i
)
(x_i, y_i)
(xi,yi) 和
s
2
s_2
s2 的份额
(
x
i
,
z
i
)
(x_i, z_i)
(xi,zi)，他们可以在本地将他们的份额相乘得到秘密份额的乘积
s
1
∗
s
2
s_1*s_2
s1∗s2。通过这些新的份额
(
x
i
,
y
i
∗
z
i
)
(x_i, y_i*z_i)
(xi,yi∗zi) 可以计算两个原始秘密的乘积，即
y
i
z
i
=
(
p
∗
q
)
(
i
)
y_iz_i = (p * q)(i)
yizi=(p∗q)(i) 并且满足
(
p
∗
q
)
(
0
)
=
s
1
s
2
(p * q)(0) = s_1s_2
(p∗q)(0)=s1s2。
但这里存在两个问题：
- 多项式 ( p ∗ q ) (p * q) (p∗q) 的系数不是随机值，而是要依赖于各方共同计算；
- 多项式的次数发生了变化。如果 p p p 和 q q q 的次数都是 k − 1 k - 1 k−1 次，也就是各自需要 k k k 个秘密份额来重建秘密，那么 ( p ∗ q ) (p * q) (p∗q) 多项式的次数就变成了 2 k − 2 2k-2 2k−2 次，也就是它将会需要 2 k − 1 2k-1 2k−1 个份额来重建 s 1 s 2 s_1s_2 s1s2。
这些问题在安全多方计算中带来了以下挑战：
性能问题：多项式次数的增加导致计算复杂度显著增加。需要更多的计算资源来处理更高次数的多项式，并且需要更多的参与方来重建秘密，这会影响整个计算过程的效率。
通信开销：为了计算和共享新生成的份额，需要在参与方之间进行更多的通信。这不仅增加了通信的负担，还可能导致更高的延迟，特别是在参与方分布广泛的情况下。
安全性问题：多项式系数不是随机的，可能会导致秘密的部分信息泄露。在实际应用中，需要额外的步骤来确保系数的随机性和保密性，从而增强整体安全性。
为了解决这些问题，后续研究开发了多种基于 Shamir 秘密共享的改进算法协议来更好的支持在秘密之间进行的运算，尤其是乘法运算。
总结
本文从秘密共享和门限秘密共享出发，介绍了Shamir秘密共享方案的原理、计算过程以及其对于多方参与计算的支持，主要贡献如下：
Shamir秘密共享方案的全面介绍：详细描述了Shamir秘密共享方案的基本概念，包括如何将一个秘密分割成多个份额，并介绍了如何使用拉格朗日插值法恢复原始秘密。
图形化直观展示：通过具体的示例和图示，展示了Shamir秘密共享方案的工作原理，包括秘密的分割、秘密份额的分配及其重构过程。
多方参与计算的支持：探讨了Shamir秘密共享方案对多方计算的支持，特别是其在支持加法和乘法运算方面的能力。通过示例详细说明了如何在不恢复原始秘密的情况下进行加法运算，并探讨了其在乘法运算中的挑战。
接下来仍需要研究的内容：
乘法运算的改进：由于Shamir秘密共享在乘法运算上的限制，多项式的系数不是随机的，且多项式次数增加导致计算复杂度提高。因此，后续需要探究新的协议是如何来解决这些问题，以更高效、安全地支持秘密之间的乘法运算。
应用拓展：Shamir秘密共享方案在多方安全计算和机器学习中的应用潜力巨大，后续会探究如何利用Shamir秘密共享方案处理加密数据的机器学习训练和推断任务。
参考
- How to Share a Secret
版权归原作者 铁锹少年@神州网信 所有， 如有侵权，请联系我们删除。