|=-----------------------------------------------------------------=|
|=-----=[ D O   N O T   F U C K   W I T H   A   H A C K E R ]=-----=|
|=-----------------------------------------------------------------=|
|=------------------------[ #3 File 0x07 ]-------------------------=|
|=-----------------------------------------------------------------=|
|=-------------------=[Intro to Secret sharing]=-------------------=|
|=-----------------------------------------------------------------=|
|=--------------------=[   By me.ssword   ]=-----------------------=|
|=-----------------------------------------------------------------=|
|=-----------------------=[ Jan 21 2014  ]=------------------------=|
|=-----------------------------------------------------------------=|


# Secret Sharing

假设这样的场景：习大大要交给三胖一份机密文件，派一名大使千里迢迢奔赴他
国，但是大使如果在半路被美帝高价收买，把机密信息泄漏给美帝怎么办？

派十个大使，每人只携带均分的一部分机密文件，好，这一来得不到完整的机密
就没有意义，美帝最多收买一个，总不能收买一窝吧。可是如果半路有一个大使
被美帝干掉怎么办？三胖也得不到完整的机密了。此外，得到一部分机密文件可
以降低猜测其它部分的成本，如果美帝收买了六个人，剩下的机密也可以猜个八
九不离十。

而 Secret Sharing 就是为了解决这个问题。允许习大大将机密文件分成多份密
文，对方得到多数密文才能够还原出机密文件。其中有一两位大使被收买没关系，
他自己手中的密文没有任何意义；一两位大使被干掉也没关系，剩下的大使仍然
可以将还原出完整的机密；部分密文被盗走也没关系，得知部分密文不会降低猜
测剩余密文的成本。

## (n-t) Threshold Scheme

传统的保密方法往往保密性与可靠性不可得兼：机密信息见不得光，为了保密，
机密信息最好隔离在单独的一台机器上；同时，机密信息往往不允许丢失，这又
不可避免地要求将机密信息拷贝备份到多个地方。

上文习大大最后采用的方法，学名叫做 (n-t)-Threshold Scheme： 将机密信息
分散在 n个 share 中，每个单独的 share 没有意义，当集齐至少 t 个 share
时才可以构造出原先的密码。要求得知一份 share 不能减少猜测整体密码的成本；
每份 share 最好至少包含等同于原始密码的信息量，由熵来填充。


## Shamir's Scheme

(n-t) Threshold Scheme 描述了 Secret Sharing 的可行方法，Shamir's
Scheme 则属于它的一个实现。

原理并不难理解：在二维坐标轴上，两个点可以确定一条直线，三个点可以确定
一条抛物线。t 个坐标可以确定一个唯一的 (t-1) 次多项式图像。

以直线为例，方程为 y = a * x 。那么我们可以把机密信息编码为数值 a (如
3)，然后在直线上取三个坐标 (3, 1), (0, 0), (6, 2)。拿到任意两个坐标即可
还原出数值 a。放在 (n-t)-Threshold Scheme 里，这个例子的 t 为 2，n 为
3。

如果需要更大的 t，可以选择更高次的多多项式。比如 y = a * x ^ 2 + b * y
+ c，可以把机密信息编码为 (a, b, c)，至少需要三个坐标才能还原出机密信息。


## Blakley's Scheme

Blakley's Scheme 是另一种实现方法，但是思路差异并不大：(t-1) 维空间中，
t 个不平行的面足以确定唯一的一个点。

那么我们可以把机密信息编码为 (t-1) 维空间中的一个点，将每份 share 拆为
一个面。t个点确定一个面，那么每份 share 的内容就是 t 个 (t-1) 维空间中
的点。每份 share将拥有相对于原密码 t 倍的信息量。


## References

- http://en.wikipedia.org/wiki/Secret_sharing
- http://www.cs.tau.ac.il/~bchor/Shamir.html