Shamir秘密分享的基本形式（同态加、同态乘）

Shamir秘密分享，指的是Shamir在1979年的文章《How to share a secret》[1] 中提出的门限秘密分享方案。该方案利用多项式求值和多项式插值，在有限域 Z p \mathbb{Z}_p Zp​中构造门限方案分享秘密值。该方案是信息论安全的，并且可以抵抗半诚实的合谋攻击。

假设 p p p是一个素数， Z p = { 0 , 1 , 2 , ⋯   , p − 1 } \mathbb{Z}_p=\{0, 1,2, \cdots ,p-1\} Zp​={0,1,2,⋯,p−1}是一个由整数构成的有限域，即 Z p \mathbb{Z}_p Zp​中的元素对于模 p p p加法构成一个交换群， Z p ∗ = { 1 , 2 , ⋯   , p − 1 } \mathbb{Z}_p^*=\{1,2,\cdots,p-1\} Zp∗​={1,2,⋯,p−1}中的元素对于模 p p p乘法构成一个交换群，乘法对加法具有分配律。下面的运算都是有限域 Z p \mathbb{Z}_p Zp​中的运算，也就是模 p p p运算。

定义一个系数模 p p p的 t − 1 t-1 t−1次多项式 f ( x ) = s + c 1 x + c 2 x 2 + ⋯ + c t − 1 x t − 1 f(x)=s+c_1x+c_2x^2+\cdots+c_{t-1}x^{t-1} f(x)=s+c1​x+c2​x2+⋯+ct−1​xt−1是关于秘密 s s s的秘密多项式。其中 c 1 , ⋯   , c t − 1 c_1,\cdots,c_{t-1} c1​,⋯,ct−1​是 Z p \mathbb{Z}_p Zp​中均匀随机选取的随机数。(有 1 p \frac{1}{p} p1​的概率使得 c t − 1 c_{t-1} ct−1​为0，也就是 f ( x ) f(x) f(x)的次数小于 t − 1 t-1 t−1，但是由于 c t − 1 c_{t-1} ct−1​也是秘密的，所以，其他人并不知道秘密多项式的次数，并不影响安全性)

在 Z p \mathbb{Z}_p Zp​中选取 n ( n ≥ t ) n(n\ge t) n(n≥t)个不同的数 { x 1 , x 2 , ⋯   , x n } \{x_1,x_2,\cdots,x_n\} {x1​,x2​,⋯,xn​}（ x i x_i xi​不为0），并计算 y 1 = f ( x 1 ) , y 2 = f ( x 2 ) , ⋯   , y n = f ( x n ) y_1=f(x_1),y_2=f(x_2),\cdots,y_n=f(x_n) y1​=f(x1​),y2​=f(x2​),⋯,yn​=f(xn​).每个用户 P i P_i Pi​获得 ( x i , y i ) (x_i,y_i) (xi​,yi​)。这样就构成了一个 ( t , n ) (t,n) (t,n)门限秘密分享方案。只有至少 t t t个用户才能恢复出秘密的多项式，从而知道秘密 s s s 。根据代数学基本定理， t t t个用户可以插值得到唯一的多项式。而 t − 1 t-1 t−1个多项式只能得到最多 t − 2 t-2 t−2次多项式。由系数的随机性， t − 1 t-1 t−1个用户得不到任何 s s s的信息。

秘密的恢复或者重建是简单的，通过多项式的插值就可以完成。最常见的就是通过拉格朗日插值法，求秘密多项式 f ( x ) f(x) f(x)。

定义拉格朗日基函数 l i ( x ) = ( ∏ i ≠ j ( x − x j ) ) ÷ ( ∏ i ≠ j ( x i − x j ) ) l_i(x)=(\prod_{i \neq j}(x-x_j))\div (\prod_{i \neq j}(x_i-x_j)) li​(x)=(∏i=j​(x−xj​))÷(∏i=j​(xi​−xj​))。容易验证 l i ( x ) l_i(x) li​(x)在 x i x_i xi​处的值为1，而在 x j ( j ≠ i ) x_j(j\neq i) xj​(j=i)处的值为0.

不妨设 P 1 , P 2 , ⋯   , P k ( t ≤ k ≤ n ) P_1,P_2,\cdots,P_k(t\le k\le n) P1​,P2​,⋯,Pk​(t≤k≤n)想要重建秘密。多项式 f ( x ) = ∑ i = 1 k y i l i ( x ) f(x)=\sum_{i=1}^{k} y_il_i(x) f(x)=∑i=1k​yi​li​(x).

假设 s 1 s_1 s1​的秘密多项式为 f 1 ( x ) f_1(x) f1​(x)，其分享值为 ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x n , y n ) (x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n) (x1​,y1​),(x2​,y2​),⋯,(xn​,yn​)， s 2 s_2 s2​的秘密多项式为 f 2 ( x ) f_2(x) f2​(x)，其分享值为 ( x 1 , z 1 ) , ( x 2 , z 2 ) , ⋯   , ( x n , z n ) (x_1,z_1),(x_2,z_2),\cdots,(x_n,z_n) (x1​,z1​),(x2​,z2​),⋯,(xn​,zn​).

则， P 1 , P 2 , ⋯   , P n P_1,P_2,\cdots,P_n P1​,P2​,⋯,Pn​可以在不重建秘密的情况下，计算 s 1 + s 2 s_1+s_2 s1​+s2​的秘密分享值。

每个用户 P i P_i Pi​在本地计算 y i + z i y_i+z_i yi​+zi​，则对于 P i P_i Pi​来说， 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​).

注意到多项式的乘法会导致多项式的次数增加，所以我们需要 n ≥ 2 t + 1 n\ge2t+1 n≥2t+1.

首先，和加法类似，每个用户 P i P_i Pi​在本地计算 y i × z i y_i\times z_i yi​×zi​，则对于 P i P_i Pi​来说， s 1 × s 2 s_1 \times s_2 s1​×s2​的秘密分享值是 ( x i , y i × z i ) (x_i,y_i\times z_i) (xi​,yi​×zi​).

然后我们需要额外的步骤，使得新的秘密多项式的次数也是 t − 1 t-1 t−1.

实际上，根据拉格朗日插值，秘密多项式 f ( x ) = ∑ i = 1 n y i l i ( x ) f(x)=\sum_{i=1}^n y_il_i(x) f(x)=∑i=1n​yi​li​(x)，那么秘密 s = f ( 0 ) = ∑ i = 1 n y i l i ( 0 ) s=f(0)=\sum_{i=1}^ny_il_i(0) s=f(0)=∑i=1n​yi​li​(0). 由于 l i ( x ) l_i(x) li​(x)是可以公开的，所以用户 P i P_i Pi​可以在本地计算 y i l i ( 0 ) y_il_i(0) yi​li​(0).

P i P_i Pi​重新采样随机数，构造一个 t − 1 t-1 t−1次的多项式 q i ( x ) = y i l i ( 0 ) + c 1 , i x + c 2 , i x 2 + ⋯ + c t − 1 , i x t − 1 q_i(x)=y_il_i(0)+c_{1,i}x+c_{2,i}x^2+\cdots+c_{t-1,i}x^{t-1} qi​(x)=yi​li​(0)+c1,i​x+c2,i​x2+⋯+ct−1,i​xt−1. 现在， s 1 × s 2 s_1 \times s_2 s1​×s2​的新的秘密多项式等于 ∑ i = 1 n q i ( x ) \sum_{i=1}^{n}q_i(x) ∑i=1n​qi​(x).

P i P_i Pi​计算 q i ( x 1 ) , q i ( x 2 ) , ⋯   , q i ( x n ) q_i(x_1),q_i(x_2),\cdots,q_i(x_n) qi​(x1​),qi​(x2​),⋯,qi​(xn​)，然后将 q i ( x j ) q_i(x_j) qi​(xj​)发送给 P j P_j Pj​.

在收到其他用户发送来的值后， P i P_i Pi​计算 y i ′ = ∑ j = 1 n q j ( x i ) y_i^\prime=\sum_{j=1}^nq_j(x_i) yi′​=∑j=1n​qj​(xi​)作为 s 1 × s 2 s_1 \times s_2 s1​×s2​在 x i x_i xi​处的分享值。

[1] Shamir, Adi. “How to share a secret.” Communications of the ACM 22.11 (1979): 612-613. [2] Goldwasser, S., M. Ben-Or, and A. Wigderson. “Completeness theorems for non-cryptographic fault-tolerant distributed computing.” Proc. of the 20th STOC. 1988.