Tassa’s Hierarchical Threshold Secret Sharing

关于 Hierarchical Threshold Secret Sharing 的形式化定义如图 1 所示。

下面通俗地介绍一下 Hierarchical Threshold Secret Sharing 的定义。 \(n\) 个参与者被分为了 \(0,1,\cdots, m\) 等级，共 \(m+1\) 个等级，数字越小等级越高，同一等级 \(i\) 的参与者记为集合 \(\mathcal{U}_i\) ，所有 \(n\) 个参与者组成的集合记为 \(\mathcal{U}\) 。

Hierarchical Threshold Secret Sharing 可用记号 \((\{k_0, k_1, k_2, \cdots, k_m \}, n)\) 表示，其中 \(0 < k_0 < k_1 \cdots, < k_m\) ，它表示要恢复出秘密值 \(S\) ，则至少需要 \(k_0\) 个 \(0\) 等级的参与者， \(k_1\) 个 \(0\) 等级或 \(1\) 等级（即小于等于 \(1\) 等级）的参与者， \(k_2\) 个 \(0\) 等级或 \(1\) 等级或 \(2\) 等级（即小于等于 \(2\) 等级）的参与者， \(k_m\) 个小于等于 \(m\) 等级的参与者。在前面介绍的“银行金库电子钥匙”的例子中，假设部门中有 \(12\) 个人参与秘密分享，其中 \(8\) 个出纳员和 \(4\) 个部门经理。“至少 \(3\) 个员工参与，且其中必须有 \(1\) 个部门经理才能恢复出电子钥匙”的方案可以表示为 \((\{1,3\}, 12)\) 。部门经理属于 \(0\) 等级，出纳员属于 \(1\) 等级， \(k_0=1\) 表示恢复电子钥匙时至少有 \(1\) 个部门经理， \(k_1=3\) 表示恢复电子钥匙时部门经理和出纳员不能小于 \(3\) ，下面是所有可能恢复出电子钥匙的 \(3\) 人组合：

# 可能恢复出电子钥匙的 3 人组合：
“1 个部门经理 + 2 个出纳员” 或：
“2 个部门经理 + 1 个出纳员” 或：
“3 个部门经理 + 0 个出纳员”

Hierarchical Threshold Secret Sharing 有两个要求：

1. Accessibility，表示对于符合门限方案的参与者组合，一定能恢复出秘密值；
   
2. Perfect Security，表示对于不符合门限方案的参与者组合，不能恢复出秘密值。比如上面例子中， \(3\) 个（或更多）出纳员不能恢复出秘密值。
   

我们以前面介绍的“银行金库电子钥匙”为例介绍上面的过程。Dealer 随机选择 \(S_1\) ，通过 \(S_0 = S - S_1\) 计算出 \(S_0\) 。然后， Dealer 把 \(S_0\) 作为秘密值，通过 \((1,4)\) 方案分享给 \(4\) 个部门经理；把 \(S_1\) 作为秘密值，通过 \((3,12)\) 方案分享给 \(4\) 个部门经理和 \(8\) 个出纳员。

要重新恢复出 \(S\) 时，首先，需要至少 \(1\) 个部门经理（记为 \(M_1\) ）恢复出 \(S_0\) ，然后在剩下的 \(3\) 个部门经理和 \(8\) 个出纳员中找 \(2\) 个人，和前面的部门经理 \(M_1\) 一共是 \(3\) 个人恢复出 \(S_1\) ，最后，由 \(S= S_0+S_1\) 计算出秘密值 \(S\) 即可。

这种方案有个缺点：等级越高（即等级数字越小）的参与者需要保存的秘密分片越多。 这种方案中，等级最高的参与者需要保存 \(m+1\) 个秘密分片，所以方案的 Information Rate 为 \(\rho = 1/(m+1)\) 。比如前面例子中，每个部门经理（等级为 \(0\) ）需要保存两个秘密分片，一个秘密分片用于恢复 \(S_0\) ，另一个秘密分片用于恢复 \(S_1\) 。

后文将介绍 \(\rho = 1\) 的 Hierarchical Threshold Secret Sharing 方案，即每个参与者需要保存的秘密分片和待分享的秘密值 \(S\) 是同样大小的。

上一节只介绍了秘密值的共享方案，但没有介绍如何恢复秘密值 \(S\) （即 \(a_0\) ）。

满足分层门限要求（即至少 \(7\) 个参与者、且其中 \(\mathcal{U}_0 \cup \mathcal{U}_1\) 的参与者至少 \(4\) 个， \(\mathcal{U}_0\) 的参与者至少 \(2\) 个）的参与者组合有很多，比如：

# 情况一：
2 个等级 0 的参与者
2 个等级 1 的参与者
3 个等级 2 的参与者

# 情况二：
2 个等级 0 的参与者
3 个等级 1 的参与者
2 个等级 2 的参与者

对于情况一，这 \(7\) 个参与者要恢复秘密值 \(a_0\) ，下面介绍一下方法。设 \[P(x) = a_0 + a_1 x + \cdots + a_6 x^6\] 二次求导后，可得 \[P''(x) = 2 a_2 + 6a_3 x + 12 a_4 x^2 + 20 a_5 x^3 + 30 a_6 x^4\] 再经过二次求导，可得 \[P^{(4)}(x) = 24 a_4 + 120 a_5 x + 360 a_6 x^2\] 已知 \(3\) 个等级为 \(2\) 的参与者的秘密分片，相当于已知 \(4\) 阶导函数 \(P^{(4)}(x)\) 上的 \(3\) 个点，我们通过拉格朗日插值可以计算出 \(4\) 阶导函数 \(P^{(4)}(x)\) （由于它是 \(2\) 次多项式， \(3\) 个点恰好可唯一确定），从而知道 \(a_4,a_5,a_6\) ；把求得的 \(a_4,a_5,a_6\) 代入到二次导函数 \(P''(x)\) 中，那么 \(P''(x)\) 中只有系数 \(a_2,a_3\) 是未知的了，由于我们还已知二次导函数上的两个点（即 \(2\) 个等级为 \(1\) 的参与者的秘密分片），代入两个点后可得两个方程，这样可以求得两个未知系数 \(a_2,a_3\) 了； \(P(x)\) 只剩下 \(a_0,a_1\) 未知了，使用类似的方法，代入 \(2\) 个等级为 \(0\) 的参与者的秘密分片（即 \(P(x)\) 中的两个点），可以求出 \(a_0,a_1\) 。从而，我们恢复出了秘密值 \(a_0\) 。

对于情况二，我们也能采用类似的方法，即已知 \(7\) 个方程（代入每个秘密分片可得一方程），可求解出 \(7\) 个未知系数 \(a_0,\cdots,a_6\) 。

参与者的秘密分片相当于函数（或某阶导函数）上一个点，每代入一个点，可得一方程， \(k\) 个参与者可得 \(k\) 方程。这里有一个重要问题： 已知 \(k\) 个方程，不一定可确定 \(k\) 个未知数。 因为，方程之间可能线性相关，有效方程可能没有那么多。

其实，上面的问题就是 Birkhoff Interpolation 问题。简单来说 Birkhoff Interpolation 问题就是：已知 \(k\) 个函数值（或者某阶导函数值），求解一个次数小于 \(k\) 的多项式满足给定的点。显然 Birkhoff Interpolation 是拉格朗日插值的一个推广，关于 Birkhoff Interpolation 相关知识点可参考 https://aandds.com/blog/hermite-birkhoff-interpolation.html 。和拉格朗日插值有唯一解不同，对于 Birkhoff Interpolation 来说，它并不一定有唯一解，如果 \(a_0\) 没有唯一解，显然无法满足分层门限方案的第一个要求（即 Accessibility）。

Tassa 证明了在一定条件（节 3.3 将介绍具体条件）下，节 3 中描述的方案一定具备 Accessibility 要求。

下面是不满足分层门限要求的例子：

# 例子 1（不满足分层门限要求，因为没有等级 0 参与者）：
0 个等级 0 的参与者
4 个等级 1 的参与者
3 个等级 2 的参与者

# 例子 2（不满足分层门限要求，因为等级 0 参与者太少，分层门限要求至少 2 个等级 0 参与者）：
1 个等级 0 的参与者
3 个等级 1 的参与者
3 个等级 2 的参与者

为什么这些组合不能恢复出秘密值 \(a_0\) 呢？对于例子 1 来说，比较好理解，因为对 \(P(x)\) 求导函数时， \(a_0\) 作为常数项，不会出现在大于等于 \(1\) 阶的导函数中，联立方程组时，要把 \(a_0\) 包含在某个方程中，则必须代入 \(P(x)\) 上的点（只有等级 0 的参与者才对应 \(P(x)\) 上的点，其它等级的参与者对应的是某阶导函数上的点）。在例子 1 中，根本没有等级 0 的参与者，所以不可能求解出 \(a_0\) 。

上面说明了在例子 1 的情况下不能恢复出秘密值 \(a_0\) ，并不能说明其它不满足分层门限要求的组合不能恢复出秘密值。即无法说明它具备 Perfect Security 要求。

Tassa 证明了在一定条件（节 3.3 将介绍具体条件）下，节 3 中描述的方案一定具备 Perfect Security 要求。

在什么条件下，节 3 中介绍的分层门限秘密共享才具备 Accessibility 和 Perfect Security 这两个要求呢？

Tassa 在论文的 3.3 节给出两种形式的条件。这两种形式都要求参与者的编号（即求参与者秘密分片时所使用的 \(x\) 值）满足 Monotonic Principle。

所谓 Monotonic Principle 就是： \[u \in \mathcal{U}_i, v \in \mathcal{U}_j, i < j \Rightarrow u < v\] 也就是说 参与者等级数字越小，则计算他们秘密分片所采用的 \(x\) 值越小。 即计算 \(\mathcal{U}_0\) 中参与者秘密分片时所使用的 \(x\) 值，一定要小于计算 \(\mathcal{U}_1\) 中参与者秘密分片时所使用的 \(x\) 值；而计算 \(\mathcal{U}_1\) 中参与者秘密分片时所使用的 \(x\) 值，一定要小于计算 \(\mathcal{U}_2\) 中参与者分片时所使用的 \(x\) 值；依次类推。举例来说，假设 \((k_0,k_1,k_2) = (2,4,7)\) 方案中 \(\mathcal{U}_0\) 有三个成员，它们的秘密分片分别由 \(F(1), F(4), F(6)\) 计算而来，那么计算 \(\mathcal{U}_1\) 的成员的秘密分片时所采用的 \(x\) 值必须大于 \(6\) ，可以采用 \(F''(7),F''(10)\) 等，但不能采用 \(F''(2),F''(4)\) 等。

记 \(N= \max \mathcal{U}\) ，即 \(N\) 是参与者最大编号值。记 \(k=k_m\) ，即 \(k\) 是恢复秘密值的最少参与者个数。记 \(q\) 为计算所在有限域 \(\mathbb{F}\) 的 Order。

条件 29（论文中相关公式编号为 29）： 如果参与者的编号满足 Monotonic Principle，并且有 \[2^{-k} \cdot (k+1)^{(k+1)/2} \cdot N^{(k-1)k/2} < q = |\mathbb{F}_q|\] 那么节 3 中介绍的分层门限秘密共享一定满足 Accessibility 和 Perfect Security。

条件 35（论文中相关公式编号为 35）： 如果参与者的编号满足 Monotonic Principle，并且有 \[2^{-k+2} \cdot (k-1)^{(k-1)/2} \cdot (k-1)! \cdot N^{(k-1)(k-2)/2} < q = |\mathbb{F}_q|\] 那么节 3 中介绍的分层门限秘密共享一定满足 Accessibility 和 Perfect Security。

假设我们用分层门限秘密共享方案来保存 128 位的 AES 密钥（即 \(q\) 为 128 比特位），那么条件 29 和条件 35 对 \(k\) 和 \(N\) 的约束关系如表 1 所示。

Table 1: Values of k and N that satisfy conditions (29) and (35)

\(k\)	Condition 29	Confition 35
5	\(N \le 5497\)	\(N \le 1234795\)
6	\(N \le 296\)	\(N \le 3637\)
7	\(N \le 56\)	\(N \le 200\)
8	\(N \le 19\)	\(N \le 38\)

当 \(k=3,4\) 时的情况可以参考原论文的附录，它们对 \(N\) 的限制更加宽松。

假设有 \(5\) 个参与者（A/B/C/D/E），其中两个参与者（A/B）等级为 \(0\) ，另外三个参与者（C/D/E）等级为 \(1\) 。

下面介绍如何实现一个 \((\{1, 3\}, 5)\) 分层门限秘密共享方案，也就是说 \(5\) 个参与者中等级为 \(0\) 的参与者至少 \(1\) 个，等级为 \(0\) 或 \(1\) 的参与者至少 \(3\) 个才能恢复出秘密值。设待分享的秘密值为 \(S=4\) 。

第一步，Dealer 随机选择一个 \(2\) 次多项式（由于至少 \(3\) 个参与者才能恢复秘密值，所以是 \(3-1\) 次多项式） \[P(x)=a_0 + a_1 x + a_2 x^2\] 其中 \(a_0\) 就是待分享的秘密值 \(4\) ，假设随机选择的 \(a_1,a_2\) 分别为 \(3,2\) ，即 Dealer 确定的多项式为 \[P(x)= 4 + 3 x + 2 x^2\]

第二步，Dealer 把 \(P(1)=9, P(2)=18\) 分别分发给等级 \(0\) 的两个参与者 A 和 B。Dealer 把 \(P''(3)=15, P''(4)=18, P''(5)=23\) 分别分发给等级 \(1\) 的三个参与者 C/D/E。

这种分配方式符合节 3.3 中的条件，所以一定满足 Accessibility 和 Perfect Security。

假设现在 B 和 D 和 E 想恢复出秘密值 \(a_0\) ，他们如何操作呢？

利用 Birkhoff 插值公式（下面相关细节可参考 https://aandds.com/blog/hermite-birkhoff-interpolation.html ），有 \[\begin{aligned} f(x) & = a_0 + a_1 x + a_2 x^2 \\ & = \frac{\operatorname{det}\left(A\left(E, X, \varphi_{0}\right)\right)}{\operatorname{det}(A(E, X, \varphi))} + \frac{\operatorname{det}\left(A\left(E, X, \varphi_{1}\right)\right)}{\operatorname{det}(A(E, X, \varphi))}x + \frac{\operatorname{det}\left(A\left(E, X, \varphi_{2}\right)\right)}{\operatorname{det}(A(E, X, \varphi))}x^2 \end{aligned}\] 所以 \[a_0 = \frac{\operatorname{det}\left(A\left(E, X, \varphi_{0}\right)\right)}{\operatorname{det}(A(E, X, \varphi))}\] 其中 \(A(E, X, \varphi)\) 和秘密分片本身无关 \[A(E, X, \varphi) = \begin{pmatrix} 1 & 2 & 2^2 \\ 0 & 1 & 2 \times 4 \\ 0 & 1 & 2 \times 5 \end{pmatrix}\] 而 \(A(E, X, \varphi_0)\) 是把 \(A(E, X, \varphi)\) 中第 1 列换为 3 个秘密分片而来，即 \[A(E, X, \varphi_0) = \begin{pmatrix} 18 & 2 & 2^2 \\ 19 & 1 & 2 \times 4 \\ 23 & 1 & 2 \times 5 \end{pmatrix}\] 所以 \[a_0 = \frac{\operatorname{det}\left(A\left(E, X, \varphi_{0}\right)\right)}{\operatorname{det}(A(E, X, \varphi))} = \frac{8}{2} = 4\]