论文阅读------How to Share a Secret
论文阅读------How to Share a Secret
-
-
- 门限机制
- 多项式插值
-
- 一般描述
-
模运算描述
-
计算效率
-
大数运算
- 方法特点
- 应用
-
- 密钥管理
-
签名管理
-
门限机制
现有一数据D，将其分为n份D_1,D_2,...D_n，其满足（k<n）：
- 其中任意m (m\ge k)个数据D_i，可以计算出D。
- 其中任意w (w< k)个数据D_i，都无法计算出D。
对应将这一机制称为(k,m)门限机制。
多项式插值
一般描述
平面中的K个点\{(x_i,y_i)\}，可以通过一个k-1次的多项式q(x_i)=y_i (对所有的(x_i,y_i)都成立)来表示。
选择一个K-1次多项式q(x):
q(x)=a_0+a_1x+........a_{k-1}x^{k-1}
按其函数取值，我们构造出n个值，分别为D_1,D_2,...D_n有：
D_i=q(i)，D_0=a_0
于是任意给出K个数偶(i,D_i)，我们可以构造出一个K元一次方程组，并且包含K个式子，通过高数消元很容易得到D_0的解。
模运算描述
选择一个比数据D与n都大的素数P，通过对该素数取模，我们得到一个域，并在该域上进行定义。
多项式的确定是通过在[0,P)均匀分布上，选择K-1整数作为a_i。而D_1,D_2,...D_n的计算不变，只是最后的结果对P取模，使得所有D_i落到域上(D仍为a_0)。
计算效率
现有得多项式插值算法其复杂度可以达到O(nlog^2n)，相对于密钥管理方案中得计算量，已经足够快了。
大数运算
如果对应的D为一个很大的数，可以将其分为多个小比特段，以降低运算精度，但是其分解的长度不能任意短，其中P的最小可用值为n+1(保证生成n个D_i)。
方法特点
- 每部分的信息大小不会大于原数据。
- K固定时，D_i可以动态删减，不会影响到其他信息片的使用。
- 可以在不改变秘密数据D的情况下动态的更换信息片D_i，只需要选择一个新的多项式q(x)即可。
- 在应用中可以根据权重的不同，分发不同数量的信息片D_i，以实现不同权限人员的管理。
应用
一组有矛盾的、相互怀疑的个体必须合作。给予任何足够多的多数人采取一些行动的权力，同时给予任何足够多的少数人阻止它的权力。
密钥管理
该特性可以用于密钥管理，假设密钥使用了(k,n),(n=2k-1)门限机制，那么该系统就具有很强的鲁棒性（容错性）。即使其中的k-1份数据被毁或者泄露，也无法影响到这一密钥的安全性。
签名管理
比如公司中的管理者之间，使用(k,n)门限机制，在决策的时候，当超过k个人同意后(即规定的多数人)就能生成签名，产生决策。如果多数人不同意，则无法产生相应决策。