Static Proactive Secret Sharing

接着前面的例子，如何实现刷新 Alice/Bob/Carol/Dave 的“部分秘密”，但同时保持秘密值 $s=5$ 不变呢？

第 1 步、随便某个人（比如 Alice），随机地生成一个 满足条件 $g(0)=0$ 的 2 次多项式 $g(x)$ ，假设为 $g(x)=x^2-2x$ ，计算出 $g(1),g(2),g(3),g(4)$ ，如图 2 所示，分别给 Alice/Bob/Carol/Dave：

g(1) = -1     # Alice 自己留着
g(2) = 0      # 发送给 Bob
g(3) = 3      # 发送给 Carol
g(4) = 8      # 发送给 Dave

第 2 步、Alice/Bob/Carol/Dave 分别把各自保存的部分秘密 $f(1),f(2),f(3),f(4)$ 加上 $g(1),g(2),g(3),g(4)$ ，作为新的部分秘密：

f'(1) = f(1) + g(1) = 1      # Alice's new share
f'(2) = f(2) + g(2) = 1      # Bob's new share
f'(3) = f(3) + g(3) = 5      # Carol's new share
f'(4) = f(4) + g(4) = 13     # Dave's new share

由于生成 $g(x)$ 时满足了条件 $g(0)=0$ ，所以这个变换后， $f^{\prime }(0)=f(0)+g(0)=f(0)=5$ ，这样维持了整体秘密 $s$ 不变。Alice/Bob/Carol/Dave 中任意 3 个人都可以利用拉格朗日插值得到 $f^{\prime }(x)=f(x)+g(x)=2x^2-6x+5$ ，从而恢复出秘密值 $s$ 。

上面的步骤中，只有一个参与者（Alice）随机生成了一个 2 次多项式 $g(x)$ ，这样就可以完成了部分秘密的刷新。

当然，Alice 不应该被特殊化，也就是其他参与者都可以随机生成的一个 2 次多项式（但也要满足 $x=0$ 处的值为 0），再计算 $x=1,2,3,4$ 几个点的值，然后发送给其它人。比如，Bob 随机生成 $h(x)=2x^2-4x$ ，如图 3 所示。

h(1) = -2     # 发送给 Alice
h(2) = 0      # Bob 自己留着
h(3) = 6      # 发送给 Carol
h(4) = 16     # 发送给 Dave

每个节点收到 Bob 发送来的数据后，更新自己的部分秘密：

f'(1) = f(1) + g(1) + h(1) = -1      # Alice's new share
f'(2) = f(2) + g(2) + h(2) = 1       # Bob's new share
f'(3) = f(3) + g(3) + h(3) = 11      # Carol's new share
f'(4) = f(4) + g(4) + h(4) = 29      # Dave's new share

同样地，由于 $h(0)=0$ ，所以各自的部分秘密在刷新后并不会影响到整体秘密 $s$ 。

类似地，Carol/Dave 也可以各自随机生成的一个 2 次多项式（但也要满足 $x=0$ 处的值为 0），计算 $x=1,2,3,4$ 几个点的值，然后发送给其它人。

接着看节 2 中的例子：

f(1) = 2      # Alice's share, but missing
f(2) = 1      # Bob's share
f(3) = 2      # Carol's share
f(4) = 5      # Dave's share

假设 Alice 保存的“部分秘密”丢失了（比如它的电脑磁盘坏了）。Bob/Carol/Dave 可以帮助 Alice 恢复出他丢失的“部分秘密”（即数字 2）吗？解决这个问题的协议被称为 Share Recovery Protocol。

有一种简单的办法，就是 Bob/Carol/Dave 直接把他们掌握的秘密发送给 Alice，Alice 可以通过拉格朗日插值还原出 $f(x)=x^2-4x+5$ ，从而恢复出 $f(1)=2$ 。但这显然有个安全问题：Alice 同时也知道了秘密值 $s=5$ ，这是不允许的。

其实，我们可以采用节 2.1 类似的思路来解决这个问题。

第 1 步，Bob 随机地生成一个 $t-1$ （即 2）次多项式 $r(x)$ ，这个 随机多项式要满足条件 $r(i)=0$ ，这里 $i$ 为 Alice 的对应编号，即 $i=1$ 。假设随机生成的多项式为 $r(x)=(x-1)(x+3)$ ，计算出 $r(2),r(3),r(4)$ ，分别发送给 Bob/Carol/Dave：

r(2) = 5       # Bob 自己留着
r(3) = 12      # 发送给 Carol
r(4) = 21      # 发送给 Dave

第 2 步，Bob/Carol/Dave 分别把各自保存的部分秘密 $f(2),f(3),f(4)$ 再加上 $r(2),r(3),r(4)$ ，并把结果发送给 Alice：

f(2) + r(2) = 6         # Bob 把这个值发送给 Alice
f(3) + r(3) = 14        # Carol把这个值发送给 Alice
f(4) + r(4) = 26        # Dave 把这个值发送给 Alice

第 3 步，Alice 收到 Bob/Carol/Dave 发来的 3 个值，通过拉格朗日插值，可由 3 个点 $(2,6),(3,14),(4,26)$ 还原出一个 2 次多项式 $s(x)=2x^2-2x+2$ ，然后 Alice 自己的部分秘密就是 $x=1$ 时的值 $s(1)=2$ 。从而 Alice 顺利恢复出了丢失的部分秘密，这个过程中 Alice 并不知道整体秘密 $s=5$ 。

注：和节 2.1 类似，除了 Bob 随机生成一个 2 次多项式外，Carol/Dave 也可以各自随机生成的一个 2 次多项式，满足 $x=1$ （1 是 Alice 的编号）时多项式值为 0 即可。