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)=2a_2+6a_{3}x+12a_4{x}^2+20a_5{x}^3+30a_6{x}^4$$ 再经过二次求导，可得 $$P^{(4)}(x)=24a_4+120a_{5}x+360a_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+3x+2x^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{array}{rl}f(x)& =a_0+a_{1}x+a_2{x}^2\\ & =\frac{\det \left(A(E,X,{\phi }_0)\right)}{\det (A(E,X,\phi ))}+\frac{\det \left(A(E,X,{\phi }_1)\right)}{\det (A(E,X,\phi ))}x+\frac{\det \left(A(E,X,{\phi }_2)\right)}{\det (A(E,X,\phi ))}{x}^2\end{array}$$ 所以 $$a_0=\frac{\det \left(A(E,X,{\phi }_0)\right)}{\det (A(E,X,\phi ))}$$ 其中 $A(E,X,\phi )$ 和秘密分片本身无关 $$A(E,X,\phi )=\left(\begin{array}{ccc}1& 2& 2^2\\ 0& 1& 2\times 4\\ 0& 1& 2\times 5\end{array}\right)$$ 而 $A(E,X,{\phi }_0)$ 是把 $A(E,X,\phi )$ 中第 1 列换为 3 个秘密分片而来，即 $$A(E,X,{\phi }_0)=\left(\begin{array}{ccc}18& 2& 2^2\\ 19& 1& 2\times 4\\ 23& 1& 2\times 5\end{array}\right)$$ 所以 $$a_0=\frac{\det \left(A(E,X,{\phi }_0)\right)}{\det (A(E,X,\phi ))}=\frac{8}{2}=4$$