安全多方计算 - Shamir秘密分享方案
概述
秘密共享 (Secret Sharing) 是一种用于保护敏感数据（如加密密钥）的技术。它将一个秘密分成多个部分，并将这些部分分发给多个参与者。只有当各个部分组合到一起时，才能恢复原始的秘密。它将风险在多方之间分散，从而提高了系统的安全性。
早在秦朝就有秦阳陵虎符：“甲兵之符，右在皇帝，左在阳陵”。只有"合符"无间才可调拨军队。这可谓古人的一大智慧，也可以看作是一种秘密共享的实践。
但这里的秘密共享要求所有参与者合作才能恢复原始的秘密(虎符)，如果任意一个参与方将自己的秘密份额丢失或损坏，就再也无法恢复原始秘密。
门限秘密共享
什么是门限秘密共享
门限秘密共享是一种密码学技术，将秘密
SSS 分割为nnn 个部分，并将这些部分分发给nnn 个参与者。所谓门限，是在分割这些秘密的时候，设置一个大小位于 1 和nnn 之间的kkk 值，使得给定任意k−1k - 1k−1 个或更少的秘密份额，都不能够计算得到秘密SSS 的任何信息；当给定任意kkk 个或更多的秘密份额的时候，就能够计算得到秘密SSS。这被称为(k,n)(k, n)(k,n) 门限秘密共享方案。这意味着这nnn 个参与者中最多k−1k - 1k−1 个参与者泄露了他们的秘密份额，秘密SSS 仍然是安全的。
直观理解
想象一下，秘密
SSS 是一个藏宝箱的密码。我们不希望单个参与者独自打开藏宝箱，因此我们可以构造方案将密码分成多个部分分给参与方，只有当至少 2 个参与者合作时，他们才能拼凑出完整的密码并打开藏宝箱。同时即便有个别秘密份额丢失或被盗，剩下的参与方依然可以重构秘密。
为了更具体地说明这一点，我们来看一个例子：
假设我们有一个秘密值
S=2S = 2S=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秘密共享方案基于拉格朗日多项式插值原理。它将秘密
SSS 分成nnn 个部分，每个参与者得到的部分都是秘密SSS 的一个多项式的值。只有当至少kkk 个参与者合作时，才能恢复原始的秘密SSS。
具体来说，多项式上的
kkk 个点能够唯一确定小于或等于k−1k-1k−1 次的多项式。2 个点足以定义一条线，3 个点足以定义一条抛物线，4 个点足以定义一条立方曲线，依此类推。
假设秘密数据
SSS 是一个数字，为了把它分成不同份额SiS_iSi，选择一个随机k−1k-1k−1 次多项式。多项式的一般形式为f(x)=a0+a1x+a2x2+⋅⋅⋅+ak−1xk−1f(x) = a_0 + a_1x + a_2x^2 + ··· + a_{k-1}x^{k-1}f(x)=a0+a1x+a2x2+⋅⋅⋅+ak−1xk−1，其中a0=Sa_0 = Sa0=S 是要保护的秘密。
秘密拥有者随机生成
k−1k-1k−1 个随机数a1,a2,...,ak−1a_1, a_2, ...,a_{k-1}a1,a2,...,ak−1，作为多项式的系数以确定多项式f(x)f(x)f(x)。然后选取nnn 个互不相同的整数x1,x2,...,xnx_1, x_2, ...,x_nx1,x2,...,xn 作为参与方 id，将这些整数带入到f(x)f(x)f(x) 进行计算，得到s1=f(x1),s2=f(x2),...,sn=f(xn)s_1 = f(x_1), s_2 = f(x_2), ..., s_n = f(x_n)s1=f(x1),s2=f(x2),...,sn=f(xn)。将计算得到的nnn 个值分别分配给nnn 个参与方，每个参与方掌握的秘密份额就是(xi,f(xi))(x_i, f(x_i))(xi,f(xi))。
例如，假定一个秘密值
S=45S=45S=45，要求将其分给 10 个参与方，至少 3 方参与计算才能够恢复出原始秘密，即n=10,k=3n = 10, k = 3n=10,k=3。构造对应的多项式f(x)=45+19x+13x2f(x) = 45 + 19x + 13x^2f(x)=45+19x+13x2。在此多项式上选取连续的整数点作为各个子秘密：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)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)。
秘密重建
对于
SiS_iSi 值的任意kkk 个子集，我们可以通过插值找到f(x)f(x)f(x) 的多项式系数，然后计算S=f(0)S = f(0)S=f(0)。另一方面，仅知道子集中的k−1k - 1k−1 个并不足以计算出SSS。
在生成秘密份额的时候，已经确定需要
kkk 个秘密份额来恢复原始秘密。即根据(x1,s1),(x2,s2),...,(xk,sk)(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)=a0S = f(0) = a_0S=f(0)=a0。
Shamir秘密共享的方案使用拉格朗日插值法求解多项式。
f(x)=∑i=0nyili(x)f(x) = \sum_{i=0}^{n}y_il_i(x)f(x)=i=0∑nyili(x)
其中
li(x)=(x−x1)(x−x2)...(x−xn)(xi−x1)(xi−x2)...(xi−xn)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) 为拉格朗日插值基函数。在求解yili(x)y_il_i(x)yili(x) 的求解之后，对其求和，就能够获得目标多项式。
为了重建秘密，任意选取3个参与方的秘密份额作为输入。这里选择 id 为
2，3，62， 3， 62，3，6 的参与方进行秘密重建。(x0,y0)=(2,135);(x1,y1)=(3,219);(x2,y2)=(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)。l0(x)=x−x1x0−x1∗x−x2x0−x2=x−32−3∗x−62−6=14x2−94x+92l_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+29l1(x)=x−x0x1−x0∗x−x2x1−x2=x−23−2∗x−63−6=−13x2+83x−4l_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 - 4l1(x)=x1−x0x−x0∗x1−x2x−x2=3−2x−2∗3−6x−6=−31x2+38x−4l2(x)=x−x0x2−x0∗x−x1x2−x1=x−26−2∗x−36−3=112x2−512x+12l_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+21f(x)=∑i=02yili(x)=y0l0(x)+y1l1(x)+y2l2(x)=135(14x2−94x+92)+219(−13x2+83x−4)+627(112x2−512x+12)=13x2+19x+45f(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 + 45f(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秘密共享方案中，加法运算支持意味着，在不恢复原始秘密的情况下，通过参与方之间的计算，就可以直接得到秘密值之和。这一特性使得在处理多个秘密时，我们能够利用其分享的份额进行加法操作。
示例说明
假设我们有两个秘密值：
S1=45S_1 = 45S1=45 和S2=33S_2 = 33S2=33。对应的多项式为：
对于
S1S_1S1，多项式为f1(x)=45+19x+13x2f_1(x) = 45 + 19x + 13x^2f1(x)=45+19x+13x2；对于S2S_2S2，多项式为f2(x)=33+21x+10x2f_2(x) = 33 + 21x + 10x^2f2(x)=33+21x+10x2。
仍采用前文中
x={2,3,6}x = \{2, 3, 6\}x={2,3,6} 作为甲乙丙三方的ididid。以其在多项式上的值f1({2,3,6})f_1(\{2, 3, 6\})f1({2,3,6}) 和f2({2,3,6})f_2(\{2, 3, 6\})f2({2,3,6}) 作为分配给各方的秘密份额。
三方参与者甲、乙、丙分别持有秘密的拆分份额，表格如下：
参与方idS1份额 (
S1idS1_{id}S1id)S2份额 (S2idS2_{id}S2id)S1idS1_{id}S1id +S2idS2_{id}S2id甲2135115250乙3219186405丙66275191146
如何在不恢复原始秘密的情况加，计算出来
S1+S2S_1 + S_2S1+S2 的结果呢？只需要甲乙丙分别计算各自本地秘密份额的和S1id+S2idS1_{id} + S2_{id}S1id+S2id，然后对其进行插值计算。l0(x)=x−x1x0−x1∗x−x2x0−x2=x−32−3∗x−62−6=14x2−94x+92l_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+29l1(x)=x−x0x1−x0∗x−x2x1−x2=x−23−2∗x−63−6=−13x2+83x−4l_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 - 4l1(x)=x1−x0x−x0∗x1−x2x−x2=3−2x−2∗3−6x−6=−31x2+38x−4l2(x)=x−x0x2−x0∗x−x1x2−x1=x−26−2∗x−36−3=112x2−512x+12l_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=02yili(x)=250(14x2−94x+92)+405(−13x2+83x−4)+1146(112x2−512x+12)=78+ax+bx2f(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^2f(x)=i=0∑2yili(x)=250(41x2−49x+29)+405(−31x2+38x−4)+1146(121x2−125x+21)=78+ax+bx2
直接计算常数项就好了，从计算结果可见，这个多项式的常数项为 78，即原始秘密
S1S_1S1的值加上S2S_2S2的值，验证了Shamir秘密共享方案的同态加法支持。
通过这种方式，我们可以在不恢复原始秘密的情况下，通过参与方持有的份额计算出秘密的和。这证明了Shamir秘密共享对加法计算天然支持。
对乘法运算的支持
在Shamir秘密共享中，为了分享两个秘密
s1s_1s1 和s2s_2s2，分别选取两个多项ppp 和qqq，满足yi=p(i)y_i = p(i)yi=p(i) 和zi=q(i)z_i = q(i)zi=q(i)，且p(0)=s1p(0) = s_1p(0)=s1,q(0)=s2q(0) = s_2q(0)=s2。如果各参与方持有s1s_1s1 的份额(xi,yi)(x_i, y_i)(xi,yi) 和s2s_2s2 的份额(xi,zi)(x_i, z_i)(xi,zi)，他们可以在本地将他们的份额相乘得到秘密份额的乘积s1∗s2s_1*s_2s1∗s2。通过这些新的份额(xi,yi∗zi)(x_i, y_i*z_i)(xi,yi∗zi) 可以计算两个原始秘密的乘积，即yizi=(p∗q)(i)y_iz_i = (p * q)(i)yizi=(p∗q)(i) 并且满足(p∗q)(0)=s1s2(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
版权归原作者 铁锹少年@神州网信 所有， 如有侵权，请联系我们删除。