秘密共享
什么是秘密共享
秘密共享是将秘密以适当的方式拆分，拆分后的每一个份额由不同的参与者管理，使得单个参与者无法恢复出秘密，只有若干个参与者一同协作才能恢复秘密。更重要的是，任何适量范围内的参与者丢失份额时，秘密仍可以完整恢复。秘密共享是一种将秘密分割存储的密码技术，目的是阻止秘密过于集中，以达到分散风险和容忍入侵的目的，是信息安全和数据保密中的重要手段。
秘密共享分为两个阶段，秘密分发阶段和秘密恢复阶段。在密码分发阶段，秘密分发者将一个秘密拆分为 n 份分发给 n 个参与者，每一份被称为一个秘密份额。每个参与者不能根据自己的份额得知到秘密的信息。在秘密恢复阶段，至少 t 个用户合作才能恢复出秘密值。秘密共享的整体过程如下：
秘密共享有什么用
秘密共享方案是存储高度敏感和高度重要信息的理想方案。比如:加密密钥、导弹发射代码、编号重要的银行账户等。这些信息的暴露可能是灾难性的;然而，同样重要的是，这些秘密不应该丢失，否则会导致严重后果。传统的加密方法不适合同时实现高机密性和高可靠性，因为在存储加密密钥时，必须考虑是"在一个位置保存密钥的单个副本"以获得最大的保密性，还是"在不同位置保存密钥的多个副本"以获得更高的可靠性。存储单个密钥副本存在密钥丢失的风险，存储多个副本增加了密钥泄露的可能、副本有更多的机会落入坏人之手。秘密共享方案解决了这个问题，并允许实现任意高级别的机密性和可靠性。
秘密共享还允许秘密的分发者"总体上"信任一个组。传统上，将一个秘密交给一个小组保管需要分发者完全信任小组的所有成员。秘密共享方案允许分发者安全地将秘密存储在组中，即使不是所有成员都可以始终信任。只要叛徒的数量不超过重建秘密所需的临界数量，秘密就是安全的。
秘密共享方案在云计算环境中非常重要。因此，可以通过阈值秘密共享机制将密钥分发到许多服务器上。然后在需要时重建密钥。
秘密共享的安全性
一个安全的秘密共享方案分配份额，这样任何拥有少于 t 份份额的人都不会比拥有0份份额的人拥有更多关于秘密的信息。秘密共享方案应避免类似下述的秘密分发方法：
例如，考虑一个秘密共享方案，其中秘密短语"password"被分成共享"pa"、“ss”、“wo"和"rd”。一个拥有0份份额的人只知道密码由8个字母组成，因此他必须从$2^{68}$ = 2080亿种可能的组合中猜测密码。然而，拥有一份的人只需要从$2^{66}$ = 3.08亿个组合中猜出6个字母，以此类推，随着更多的人串通。因此，这个系统不是一个"安全"的秘密共享方案，因为拥有少于t个秘密份额的玩家能够减少获得内部秘密的问题，而不需要首先获得所有必要的份额。
Shamir秘密共享
Shamir秘密共享方案由Adi Shamir于1979年在论文《How to share a secret》中提出。Shamir秘密共享方案主要基于拉格朗日插值公式，由于平面上的 t 个点可以唯一确定一个 t-1 阶的多项式，因此如果选择了 n > t 个点并分别分发给 n 个人， 那么其中的任意的 t 的人都可以使用拉格朗日插值恢复出这个多项式。 Shamir正是利用这一点，将 t-1 阶多项式的常系数作为秘密值，从而实现了安全的秘密共享。
作者简介
阿迪·沙米尔于1952年7月6日出生于以色列，著名的密码学家、数学家和发明家。他是(RSA)算法的发明者之一(RSA分别是Rivest-Shamir-Adleman )，Fiat-Shamir启发式的发明者之一，差分密码分析的发明者之一，Shamir秘密共享方案的提出者，为密码学和计算机领域做出许多贡献。曾获得图灵奖、沃尔夫数学奖、UAP科学奖、日本奖、以色列国家奖、以色列数学学会奖等等。Shamir是以色列科学院院士；国际密码学研究协会会士；美国国家科学院院士；欧洲科学院院士；法国科学院外籍院士；英国皇家学会外籍院士；美国艺术与科学院院士。(院士这么简单?)
Shamir秘密共享方案
预备知识
拉格朗日插值公式
简介:
在数值分析中，拉格朗日插值法是以法国十八世纪数学家约瑟夫·拉格朗日命名的一种多项式插值方法。许多实际问题中都用函数来表示某种内在联系或规律，而不少函数都只能通过实验和观测来了解。如对实践中的某个物理量进行观测，在若干个不同的地方得到相应的观测值，拉格朗日插值法可以找到一个多项式，其恰好在各个观测的点取到观测到的值。这样的多项式称为拉格朗日（插值）多项式。数学上来说，拉格朗日插值法可以给出一个恰好穿过二维平面上若干个已知点的多项式函数。拉格朗日插值法最早被英国数学家爱德华·华林于1779年发现，不久后（1783年）由莱昂哈德·欧拉再次发现。1795年，拉格朗日在其著作《师范学校数学基础教程》中发表了这个插值方法，从此他的名字就和这个方法联系在一起。
目的:
若 $y=f(x)$ 在互不相同的 n 个点 $x_0,…,x_{n-1}$ 处的函数值分别为 $y_0,…,y_{n-1}$（即该函数过 这 n 个点），拉格朗日插值用于构造一个过这 n 个点的、次数不超过 n 的多项式 $y=L_n(x)$ ,使其满足： $$L_n(x_k)=y_k \ (k=0,1,…,n-1)$$ 拉格朗日证明了满足插值条件的、次数不超过n的多项式是存在而且是唯一的，并且给出了一种构造该函数的方法，我们称之为拉格朗日插值法，通过拉格朗日插值法构造出的多项式 $L_n(x)$ 也被称为拉格朗日多项式。
Lagrange插值法：
假设在平面上有 n 个点 $(x_0,y_0),…,(x_{n-1},y_{n-1})$，我们的目标是作一个函数 $f(x)$ 使得其图像经过这 n 个点。为了便于叙述构造 $f(x)$ 的过程，设集合 $D_n$={ 0,1,..,n-1} 是关于点 (x,y) 的角标的集合，$B_k$ = { $i | i\neq k,i\in D_n$ }，且 $p_k(x)$ 定义如下：
$$p_k(x)=\prod_{i\in B_k} \frac{x-x_i}{x_k-x_i}$$
可以看出 $p_k(x)$ 是 n-1 次多项式，且对于任意的 $m\in B_k$ 有 $p_k(x_m)=0$ 且 $p_k(x_k)=1$ 。我们构造拉格朗日多项式 $L_n(x)$ 如下, 则 $L_n(x)$ 就是满足满足条件的最终函数 $f(x)$ 。 $$L_n(x)=\sum_{j=0}^{n-1}y_j \cdot p_i(x)$$
Shamir秘密共享方案
秘密分发
-
秘密分发者首先随机生成 $ t - 2 $ 个小于 $ p $ 的随机数 $ a_{1}, a_{2},…, a_{t - 1} $ 并构造一个 t-1 阶的多项式 $ f (x) = a_0 + a_{1} x + … + a_{t-1} x^{t-1} \pmod p $ ， 其中 $ f (0) = a_{0} = s $ 是要保护的秘密， $ p $ 是一个大素数，且 s < p 。
-
秘密分发者随机选取 $ n $ 个互不相同的整数 $ x_{1}, x_{2}, … , x_{n} $ 并将 $ n $ 个整数代入多项式函数 $f(x)$得到 $ n $ 个值 $ y_1 = f (x_1)$, $ y_2 = f(x_2)$,…, $y_{n} = f (x_{n}) $ , 然后将计算得到的 $ n $ 个坐标 $(x_i,y_i)$ 分别发给 $ n $ 各参与方并销毁 $ f (x) $，即第 $ i $ 个参与方获得 $ (x_{i}, y_{i}) $ 。
秘密恢复
收集到 t 个参与者的份额、也就是 t 个点的坐标之后，将得到的 t 个点利用拉格朗日插值法计算出拉格朗日插值多项式，也就是 $f(x)$ , 然后计算 $f(0)=s$ 得到秘密值。事实上，恢复秘密除了按照上述方式先求解出Lagrange多项式 $f(x)$ 在求代入 $x = 0$ 求得 $s = f(x)$ 之外，还可以将求多项式和求 $f(0)$ 的过程合并，得到下面一个恢复秘密的公式： $$ s = \sum_{i=0}^{n-1}( y_i \cdot \prod_{i=j}^{n-1} \frac{x_i}{x_i-x_j} )$$
一个简单例子
在秘密分发阶段
以(3, 4)门限为例，假设秘密 $ s = 2 $，$ p = 23 $，构造 $ f (x) = 2x^{2} + 3x + 2 \pmod {23} $ 。根据函数可知此处 $ t = 3 $，另取 $ x_{1} = 1$, $x_{2} = 2$, $x_{3} = 3$, $x_{4} = 4 $，代入函数得 $ f (1) = 7, f (2) = 16, f (3) = 6, f (4) = 0 $。将 $(1,7),(2,16),(3,6),(4,0)$ 作为份额分别分发给四个参与者。
在秘密恢复阶段
任意三个参与者可以恢复出秘密 s 。我们假设取得其中 3 组数据为 $ (1, 7) 、(3, 6)、(3, 0) $，使用拉格朗日插值公式进行恢复：
$$ s = 7 \times \frac{(0 - 3) \times (0 - 4)}{(1 - 3) \times (1 - 4)} + 6 \times \frac{(0 - 1) \times (0 - 4)}{(3 - 1) \times (3 - 4)} + 0 \times \frac{(0 - 1) \times (0 - 3)}{(4 - 1) \times (4 - 3)} \operatorname{mod}(23) $$
经过上述计算成功恢复出秘密 $ s = 2 $
其他秘密共享
Blakley’s Secret Sharing
同一平面上的两条非平行线恰好相交于一点。空间中的三个不平行平面恰好相交于一点。更一般地说，任何n个非平行（n-1）维超平面在特定点相交。秘密可以被编码为交叉点的任何单个坐标。如果秘密是使用所有坐标编码的，即使它们是随机的，那么内部人员（拥有一个或多个（n-1）维超平面的人）就会获得有关秘密的信息，因为他知道秘密一定位于他的平面上。如果内部人员能够比外部人员获得更多关于秘密的知识，那么系统就不再具有信息理论安全性。如果仅使用n个坐标中的一个，那么内部人员只知道局外人（即，对于2维系统来说，秘密必须位于x轴上）。每个玩家都获得了足够的信息来定义超平面;通过计算平面的交叉点，然后获取该交叉点的指定坐标来恢复秘密。
Blakley的方案的空间效率低于Shamir的方案;虽然Shamir的份额仅与原始秘密一样大，但Blakley的份额大t倍，其中t是玩家的阈值数量。布莱克利的计划可以通过增加对哪些飞机可用作股份的限制来收紧。由此产生的方案相当于Shamir的多项系统。
基于CRT的SS
秘密共享的发展
经过多年的发展，后人对秘密共享方案进行了很多扩充，这里对其进行简单的介绍，有兴趣的读者可以自行搜索相关论文进行查看。
当有多个秘密需要共享时，需要为每个秘密都拆分出很多秘密份额，这会导致秘密份额的数量随着秘密的增多而快速增大，为了解决这个问题，有学者提出了多秘密共享方案，该方案可以一次共享多个秘密，并且每个参与者只需要存储一个秘密份额。
虽然一个参与者无法通过自己的份额得知秘密的信息，但是他可以在恢复秘密的时候提供错误的份额，从而导致无法正确的恢复出秘密值。这在有些情况下是不可接收的，比如基于Shamir秘密共享的分布式密钥生成过程中，如果参与者提供错误的份额分布式系统中的其他节点，将导致整个系统无法正确的协商出一个密钥。为了解决这个问题，有学者提出了可验证的秘密共享VSS。在VSS中，任何人可以验证参与者的份额是否合法。
在传统的秘密共享中存在一个秘密分发者，这个人知道整个系统中所有参与者的份额，并且也知道秘密本身。这个人的存在一定程度上违背秘密共享的初衷。为此，有学者提出了无秘密分发者的秘密共享，解决了这个问题。
虽然秘密共享中，敌手必须攻破一定数量的参与者之后才能得到足够的份额恢复秘密。但是密钥的长期存储难免会导致密钥的泄露，威胁秘密的安全。为此，有学者提出了主动式秘密共享的概念，可以动态的更新秘密份额，更好的保护秘密。
拓展阅读
秘密共享的一个重要应用是基于属性的加密(ABE)，基于ABE提出的细粒度访问控制被认为是最有发展前景的细粒度访问控制方法。详细请参考文章《基于属性的加密》