- 安全多方计算 - Shamir机密分享方案
- 概述
- 门限机密共享
- Shamir机密共享
- Shamir机密共享的特点
- 对加法和乘法运算的支持
- 总结
- 参考
安全多方计算 - Shamir机密分享方案
概述
机密共享 (Secret Sharing) 是一种用于保护敏感数据（如加密密钥）的技术。它将一个机密分成多个部分，并将这些部分分发给多个到场者。只有当各个部分组合到一起时，才能规复原始的机密。它将风险在多方之间分散，从而提高了体系的安全性。
早在秦朝就有秦阳陵虎符：“甲兵之符，右在天子，左在阳陵”。只有"合符"无间才可调拨军队。这可谓古人的一大智慧，也可以看作是一种机密共享的实践。
但这里的机密共享要求所有到场者合作才能规复原始的机密(虎符)，如果任意一个到场方将自己的机密份额丢失或损坏，就再也无法规复原始机密。
本文要先容一种门限机密共享(threshold secret sharing) —— Shamir机密共享1，就能够办理这个问题。同时，因为Shamir机密共享所具有的计算特性，使其在安全多方计算中也发挥重要作用。
门限机密共享
什么是门限机密共享
门限机密共享是一种暗码学技术，将机密 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。
用图形化展示就是以下过程：
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机密共享方案处理加密数据的呆板学习训练和推断任务。
参考
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
