这两天发现了一个之前查过的概念一直没有总结。这次总结一个密码学中的概念，叫做 Secret Sharing，因为这个东西一开始用来分享密钥的，所以中文名称也有人叫做密钥分享。提到密钥有点 confusing，本文中就叫做秘密共享吧。
需求
Secret Sharing 的核心在于：能否设计一个方案，将一个信息分发给 $n$ 个用户，只有当这 $n$ 个用户在一起的时候才能共同还原出原始数据。
为了更好的理解这个问题，我们先来搞一个虽然不正确，但是能理解 Secret Sharing 的解决方案。假设我有一个秘密，这个秘密是数字 $S=253$，我需要将这个秘密分发给三个人。那么用字符串的拼接就好了，我告诉第一个人2，告诉第二个人5，然后告诉第三个人3。不就解决了这个问题。
这么说好像也没啥不对的，但是有一些小的问题。首先，这个顺序怎么定，这三个人在一起可能是253也可能是523啊。当然为了解决问题的话，我们可以定一个索引，这样就可以唯一确定顺序了。但是给定索引会导致安全性的问题，比如第一个用户和第二个用户在一起，就知道数字是 $S=25x$，只需要进行10次猜测就能猜测出秘密了。当然，这个方案还有着不足，那要是把 $253$ 分给四个人咋分。
问题定义
大概知道了什么是秘密分享之后，我们可以这么定义 Secret Sharing 这个问题：
$(k, n)$-Secret Sharing：将秘密 $S$ 分成 $S_1, S_2, …, S_n$，使得：
1) 知道 $S_i$ 中的 $k$ 份，就可以还原出 $S$。
2) 知道的份数少于 $k$，则无法还原出 $S$。
在刚才的例子中，$S=253, k=n=3$。值得注意的是，这个当中是可以 $n > k$ 的。
Shamir’s Secret Sharing Scheme
在秘密分享中，最经典的算法莫过于 Shamir’s Secret Sharing 了。它最基本的设计原理是：平面上 $k$ 个点可以唯一确定一个 $k-1$ 阶的多项式 $f(x)=a_{0}+a_{1} x+a_{2} x^{2}+\ldots+a_{k-1} x^{k-1}$。如两个点可以唯一确定一条直线。我们把 $a_0$ 作为秘密 $S$。
案例计算
这部分直接采用了wiki上面的计算过程，链接为：Secret Sharing。
假设秘密 $S=1234$，需要分享给 $n=6$ 个人，任意三个人即可还原原始信息 $t=3$。
准备与分发阶段
1）随意选用 $k-1$ 个随机数，如 166 与 94，即确定了一个二次方程：
2）根据构建的多项式构造 $n$ 个点分配给用户：
重建阶段
这样，我们就可以从用户集中任意选取三个用户，即可确定出原始的多项式，进而得到秘密 $S$。一般来说，我们采用拉格朗日差值的方法去计算多项式，比如我们用 $\left(x_{0}, y_{0}\right)=(2,1942) ;\left(x_{1}, y_{1}\right)=(4,3402) ;\left(x_{2}, y_{2}\right)=(5,4414)$ 去恢复多项式。
拉格朗日差值的方法这里具体就不仔细讲了，刚学的时候是在数值分析这门课上。其实不用拉格朗日差值也能去算，就是解一个三次方程而已。
拉格朗日差值中，首先需要拉格朗日算子：
所以，构造的多项式为：
因此，通过三个点构造的秘密为 $S=f(0)=1234$。
总结
本文简单介绍了 Secret Sharing 的基本概念和一种简单的可行方法。因为只是简单了解这个概念，并没有完整地介绍这个方法的安全性问题。
本篇内容到这里就结束了，欢迎关注公众号《差分隐私》，获取更多前沿技术。
