秘密共享（Secret Sharing）是密码学中的一项重要技术，它提供了一种在多个实体之间分发秘密信息的方法，从而实现对秘密的控制。

既能实现 t of n 模式，也能实现减少签名结果的大小，属于阈值签名的范畴。

把密钥分成共 n 份密钥片段，由 n 个成员分别保存。只要凑够其中 t 份秘密片段，就能恢复出完整的密钥，从而完成签名。


什么是秘密共享

简单来说，秘密共享就是将一个秘密分割成多个 “ 份额 ” ，然后分发给不同的实体持有。只有收集到足够数目的 “ 份额 ” 才能重构这个秘密。举例来说，我可以将一个密码分成 5 份，分别给 A 、B 、C 、D 、E 5 人持有。其中规定只有同时收集到至少 3 个人所持有的份额，才能重构这个密码。那么即使用其中 1 人或 2 人的份额是无法推导出原始密码的。这可以防止信息在单一实体的泄露。

秘密共享可以：

  • 提高秘密的安全性。通过分割和分发防止单点泄露。

  • 实现对秘密的访问控制。通过指定重构秘密所需的最少份额数，实现访问策略控制。

  • 提高秘密的可用性。即使部分份额丢失，也可以重构秘密份额，重置密钥片段。


应用场景

秘密共享技术在许多场景中有广泛应用，比如：

  • 密钥管理：可以将加密证书或密钥分成多份分发给多个证书授权机构或密钥管理节点，从而避免单点故障。

  • 区块链中的多签账户：要求交易需由一定数目的节点签名认可后才生效。

  • 敏感数据存储：将关键数据分成多份储存在不同云服务商处，防止单一提供商的数据泄露。

  • 投票系统：将投票密钥根据门限策略分成多份，只有收集足够的投票节点才能打开计票。

  • 军事领域的权限控制：不同级别的指挥需要收集对应数目的密钥份额才能启动武器系统。

实际应用中，可以根据需要选择不同的秘密共享算法，确定分发的份额数目、所需的最少重构份额数等，从而实现自定义的访问结构。


秘密共享作为密码学的重要分支之一，能够在保证安全的前提下实现对秘密访问的灵活控制，在当前和未来都将有广阔的应用前景。理解秘密共享的基本原理和算法思想，对于从事安全和密码学相关工作都大有裨益。


秘密共享算法

要实现秘密共享，需要相关的数学算法。最初的秘密共享算法是在 1979 年由 G. R. Blakley 和 A. Shamir 分别独立提出的。常见的秘密共享算法包括：

  • Shamir 秘密共享：基于多项式插值的算法，是最常用的一种。

  • Asmuth-Bloom 秘密共享：使用中国余数定理实现的共享。

  • Blakley 圆几何秘密共享：基于超平面交点几何的算法。

这些算法通常依赖一些数学原理（比如多项式、向量空间等）将秘密分割成多份，并只有收集足够数目的份额才能重建这个秘密。考虑到篇幅，这里不展开讲解后 2 种算法的细节，我们重点介绍 Shamir 秘密共享。


Shamir 秘密共享

Shamir 秘密共享是基于多项式插值的一种秘密共享算法，由 Adi Shamir 在 1979 年提出。

这里主要包括两个过程：拆分秘密和恢复秘密。


拆分秘密

选择一个 \(p\) 质数，在整数环 \(Zp\) 上构造一个 \(t-1\) 次随机多项式：

$$ f(x)\ =\ a_{0}+a_{1}x+a_{2}x^{2}+ \ ...\ +a_{t-1}x^{t-1} mod(p) $$

\(p\) 是一个大素数，其中代 \(f(0)=a_{0}=s\) （ \(s\) 是秘密），且 \( s<p \) 。

再随机生成 \(t-1\) 个小于 \(p\) 的随机数 \(a_{1}，a_{2}，… ，a_{t-1}\) ，并随机选取 \(n\) 个互不相同的整数 \(x_{1}, x_{2}, ..., x_{n}\) 。

将 \(n\) 个整数代入多项式函数，计算得到 \(n\) 个值 \(s_{1}=f(x_{1}),\ s_{2}=f(x_{2}),\ ...,\ s_{n}=f(x_{n})\) 。

将计算得到的 \(n\) 个值分别分发给 \(n\) 个参与方，即第 \(i\) 个参与方获得 \((x_{i},\ s_{i})\) （作为该参与方需要严格保守的秘密）。

最后销毁 \(f(x)\) 。根据多项式函数的性质，少于 \(t\) 个参与方都无法恢复出这个多项式函数。


比如拿 \((3,4)\) 秘密共享举例。 \((t, n)\) ：t 是恢复阈值，n 是秘密分享的总数。

这里假设秘密 \(s=2\) ， \(p=23\) ，构造的 \(f(x)\) 是：

$$ f(x)\ =\ 2+3x+2x^{2} \mod(23) $$

另取 \(x_{1}=1,\ x_{2}=2,\ x_{3}=3,\ x_{4}=4\) ，代入函数得 \(f(1)=7,\ f(2)=16,\ f(3)=6,\ f(4)=0\) 。拆分出 4 个秘密。


恢复秘密

因为我们是 \((3,4)\) 的秘密共享，所以拆分出 4 个秘密，知道其中的 3 个就能恢复出初始秘密。

这里 \(t\) 的取值为 \(3\) ，也就是恢复秘密的阈值为 \(t\) 。

随机选取其中 3 组数据 \((1,7)、(3,6)、(4,0)\) ，并使用拉格朗日插值公式进行恢复。


在 Shamir 秘密共享算法中，秘密 \(s\) 是多项式的常数项。给定了三个点，我们可以使用拉格朗日插值法来找到对应的多项式。

拉格朗日插值多项式的一般形式是： $$ L(x) = \sum_{i=1}^{k} y_i \prod_{j=1, j\neq i}^{k} \frac{x - x_j}{x_i - x_j} \mod p $$ 其中，\((x_{i},\ y_{i})\) 是给定的点。

$$ L(x) = 7 \cdot \frac{(x-3)(x-4)}{(1-3)(1-4)} + 6 \cdot \frac{(x-1)(x-4)}{(3-1)(3-4)} + 0 \cdot \frac{(x-1)(x-3)}{(4-1)(4-3)} \mod 23 $$ 化简后得到：

$$ f(x)\ =\ 2+3x+2x^{2} \mod(23) $$ 这与我们开始时的多项式相匹配。因此，秘密 \(s\) 为多项式的常数项，即 \(s=2\) 。所以，秘密 \(s\) 是 2 。


这就是 Shamir 秘密共享算法的核心思想，它运用了一些抽象代数与多项式插值理论的知识，来提供信息理论安全保证。由此也可见数学理论在密码学算法设计中的重要作用。

这个秘密可以是私钥，也可以扩展成其他任意信息，如加密信息，谜题答案，秘密遗嘱等。

不仅实现了多方管理，也提供了一定的容错机制，允许最多 \(n - t\) 份分片数据丢失。


不过从技术上讲，它属于单签名，因为最后还是要恢复出一个私钥签名，而不是拆分出多个私钥片段直接签名。

而后面衍生出来的阈值签名，就可以使用拆分出的私钥片段签名了。每个成员通过自己的私钥片段生成签名片段，把足够的签名片段聚合，恢复出完整签名。

阈值签名的任何过程都没有暴露完整的私钥，完整的私钥出来没有出现过。每个成员自己也只知道自己的那部分私钥片段，非常安全。


不足之处

但是！

Shamir 原始的密钥分享方案，只能拆分密钥，还存在很多问题。

首先，私钥钥分发者知晓完整的私钥，他是单点控制私钥的。会有作恶的可能，比如对一部分成员发放错误的私钥片段。

另外，私钥片段的持有者也可能提供虚假的私钥片段。

或者只给一部分人发了私钥，根本没达到阈值！

比如一共有 7 个成员，阈值是 5 ，但是只给 4 个成员发了私钥 ~ 根本没法用！所以分发私钥的完整性也需要验证。


基于 Shamir 密钥分享的改进机制：可验证的密钥分享（Verifiable Secret Sharing, VSS）。

关于 VSS ，我们直接讲实用的 Feldman 的 VSS 方案。尽管在 Shamir 提出密钥分享（1979）到 Feldman 的 VSS 方案提出（1987）也存在一些其他方案设计。

VSS 概念由 Benny Chor ，Shafi Goldwasser ，Silvio Micali 等人在 1985 年首次提出 。


Feldman方案 - 可验证密钥分享

Feldman 方案是一种可验证的密钥分享技术，它允许一个密钥的所有者 Alice 把这个密钥分成多个份分发给其他人，而且这些人可以验证自己得到的密钥份是否正确，但无法得到整个原始密钥。

为了使得分发的秘密碎片的数据可验证，分发私钥片段的人除了给出私钥片段外，还要提供对应的承诺 \((c_0, c_1,... )\) 。


这个方案的基本思路是：

Alice 作为私钥分发人，选择一个大素数 \(p\) 和一个生成元 \(g\) ， \(g\) 属于 \(Z_{p}^{*}\) 且为 \(q\) 阶元素。实际中，使用的密钥分享都是有限域上的循环群的运算，使用公共 \(g\) 作为生成元。

\(q\) 是 \(p -1\) 的一个大素数因子。公开 \(p,\ q,\ g\) 。

\(s\) 为随机生成的原始密钥，\(t\) 是阈值，\(n\) 是成员总数。

生成多项式： $$ f(x)\ =\ a_{0}+a_{1}x+a_{2}x^{2}+ \ ...\ +a_{t-1}x^{t-1} mod(p) $$ \(a_0\) 代表私钥，即多项式的秘密。

计算承诺（commitment）：\(c_0=g^{a_0}, \ c_1=g^{a_1}, \ c_2=g^{a_2}, \ ..., \ c_{t-1}=g^{a_{t-1}}\) 。

Alice 把承诺 \((c_0,\ c_1,\ ,\ c_2...\ ,\ c_{t-1})\) 公开给所有成员。

接下来 Alice 要把私钥 \(s\) 分成 \(n\) 份 \(s_i\) ，分发给 \(n\) 个成员。

收到 \(s_i\) 的成员可以用承诺验证私钥片段：计算 \( g^{s_{i}} = {\textstyle \prod_{j=0}^{k-1}} (C_j)^{i_{j}} \mod{p} \) 。

如果结果等式成立，就说明这一份私钥片段是正确的。由于承诺绑定了系数，如果 Alice 给出承诺不是用多项式方程真实系数，就会验证失败。

所有人都可以验证自己的私钥片段，但没人可以得到 \(s\) ，除非所有 \(n\) 个人一起合作。


这样 Feldman 方案实现了可验证的密钥分享，既保证了密钥的安全，也使得每个人都能验证自己得到的是正确的密钥片段。这在很多密码系统和区块链技术中都有应用。


更新秘密 - 动态秘密共享

Feldman 方案在原始 Shamir 方案基础上添加了验证环节，解决了传统秘密共享中，秘密分发者不诚实的问题。


不过这个方案假设的是，攻击者不能在系统的整个生命周期内，获取到足够的私钥片段。

但一个更实际的场景是，攻击者可以在不同时间段内，慢慢渗透不同的成员，逐个击破。

在秘密本身的生命周期较长时，就很容易被逐个击破，例如节点受到病毒攻击，或者泄露、遗忘私钥片段等，如果面对长时间的破坏性攻击，可验证秘密共享方案并没有一直较好的安全性。

当然可以通过变换原始私钥（秘密）缓解这个问题，但是总有一些情况需要长期保持私钥不变的（比如商业、军事机密）。


而动态秘密共享方案可以在不改变秘密的情况下，解决秘密共享方案在长期保存的安全性问题。

通过周期性地更换私钥片段，每次更换私钥片段后，攻击者在上一个周期获得的私钥都会失效。

这样就可以根据密钥可能受攻击的程度决定私钥片段保留周期的长短，例如如果私钥（秘密）保密级别很高，更换私钥片段的周期就要相应的时间很短，频率高。反之，更换周期就会变长。

保证在每一个周期内私钥的安全性。而且过期的私钥片段不会对最新的私钥片段产生影响。即消除上一周期内，攻击者的获取的秘密，不随着时间增加，产生累加效应。

这样，即使攻击者获取了某节点前一个时间段的私钥，它也无法在下一个时间段伪造这个节点的身份。因为该节点已经更新了自己的私钥。而攻击者已经无法获取新的私钥来进行签名。

需要注意的是，如果攻击者不仅获取了旧的私钥，并且在下一个时间段依然控制这个节点，那么它可以伪造一个新的公私钥对并广播。但由于真实节点也会广播真实的新公钥，因此网络中会出现两个冲突的公钥。这就会被其他节点检测到，并判定这个节点被入侵。此时就需要重置这个节点，并安装一个全新的操作系统与私钥。


有关动态秘密共享的方案已有不少，Amir Herzberg 在 1995 年提出的方案是很经典的一个，方案是对 Shamir 的秘密共享方案实现动态化。

感兴趣可以看这篇论文。