Static Proactive Secret Sharing
Table of Contents
1. 背景介绍
使用 Shamir's Secret Sharing 方案可以把某个秘密值 \(s\) 分散地保存到 \(n\) 个节点，而只需要 \(t \; (t \le n)\) 个节点同时参与就可以还原出秘密值 \(s\) 。
攻击者需要攻破 \(t\) 个节点才能还原出秘密值 \(s\) ，但是如果节点的秘密值一直是不变的，则存在潜在的不安全：攻击者今天攻破了第 1 个节点，过几天再攻破了第 2 个节点，一个月后共攻破 \(t\) 个节点，这也会造成秘密值 \(s\) 的泄露。 如果有一种方案可以“刷新”每个节点保存的部分秘密，同时保持整体秘密 \(s\) 不变，则系统的安全性将提升。这种方案被称为 Share Renewal Protocol（或者 Share Refresh Protocol）。学术上把节点上的部分秘密可以刷新的 Secret Sharing 称为 Proactive Secret Sharing。 如果刷新后，门限值 \(t\) 维持不变，则称为 Static 方案；如果刷新后，门限值 \(t\) 可以改变，则称为 Dynamic 方案。
注：如果我们有一个可信赖的第三方（“trusted dealer”），则这个事情将很简单：节点把各自的“部分秘密”发送给“trusted dealer”，“trusted dealer”恢复出原始秘密值 \(s\) ，再执行一次 Shamir's Secret Sharing 过程就可以实现各节点“部分秘密”的刷新了。不过，“trusted dealer”是掌握了完整秘密值 \(s\) 的单点，它的存在会降低系统的安全性。所以我们考虑的是刷新过程中不存在“trusted dealer”的情况。
2. Herzberg's Method
1995 年，Herzberg 在论文 Proactive Secret Sharing Or: How to Cope With Perpetual Leakage 提出了 Share Renewal Protocol 和 Share Recovery Protocol，下面将介绍它。
假设，已经通过 Shamir's Secret Sharing 方案，设置门限为 \(t=3\) ，把秘密值 \(s=5\) 分散给了 \(n=4\) 个参与者 Alice/Bob/Carol/Dave，如图 1 所示，原始的多项式 \(f(x) = x^2 - 4x + 5\) ，Alice 分配到的“部分秘密”为 \(f(1) = 2\) ，Bob 分配到的“部分秘密”为 \(f(2) = 1\) ，Carol 分配到的“部分秘密”为 \(f(3) = 2\) ，Dave 分配到的“部分秘密”为 \(f(4) = 5\) 。
f(1) = 2 # Alice's share f(2) = 1 # Bob's share f(3) = 2 # Carol's share f(4) = 5 # Dave's share
而秘密值 \(s = f(0) = 5\) ，由于门限 \(t=3\) （多项式次数是 2），Alice/Bob/Carol/Dave 中任意 3 个人都可以利用拉格朗日插值得到 \(f(x)\) ，从而恢复出秘密值 \(s\) 。
Figure 1: Shamir's Secret Sharing
2.1. Share Renewal Protocol
接着前面的例子，如何实现刷新 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
Figure 2: \(g(x)\) 是随机的 \(t-1\) 次多项式，但要满足 \(g(0)=0\)
第 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'(0) = f(0)+g(0)=f(0)=5\) ，这样维持了整体秘密 \(s\) 不变。Alice/Bob/Carol/Dave 中任意 3 个人都可以利用拉格朗日插值得到 \(f'(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 所示。
Figure 3: Alice 生成 \(g(x)=x^2 - 2x\) ，Bob 生成 \(h(x)=2x^{2} - 4x\)
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.1.1. 形式化描述
图 4 是 Herzberg 在论文中对 Share Renewal Protocol 的描述。
Figure 4: Herzberg's Share Renewal Protocol
2.1.2. 演示代码
在 https://asecuritysite.com/encryption/pro_sss2 中有个 Python 实现的 Proactive Secret Sharing 的演示代码。
2.2. Share Recovery Protocol
接着看节 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 即可。
2.2.1. 形式化描述
图 5 是 Herzberg 在论文中对 Share Recovery Protocol 的描述。
Figure 5: Herzberg's Share Recovery Protocol