Secret Sharing —— 秘密共享

引言：

秘密分享（英语：Secret sharing），又称秘密拆分（英语：Secret splitting），是将秘密分散到人群的方法，每人得到秘密的一部分，称为份额（英文：Share）。只有集齐份额满足方案的要求，将其结合后，才能还原出秘密；每件份额各自则没有用途。
一种特殊的分享方案里，角色分为一名1荷官及n名玩家。荷官将秘密分配给玩家，但只有满足特定条件时，玩家可以还原出秘密。方案中每个玩家收到一件份额。只要有至少t（阈值，"threshold"）个玩家合作，就可以还原出秘密，但不足t个人则不能。这样的秘密分享方案称为(t, n)—阈值方案（有时亦写成(n, t)—阈值方案）。
本文主要介绍两种秘密共享方案——Shamir秘密共享机制，Asmuth-Bloom门限机制，以及他们各自的数学原理。

1.1 秘密共享规定：

  • 一保险柜内存有秘密文件，相关5人中有3人及以上在场才能打开。
  • 保险柜上安装多把锁，没人拥有部分锁的钥匙
  • 在保险柜上安装10把锁，每把锁配发三把钥匙，每人手中有六把锁的钥匙
    • 任取3列，必有任何锁的钥匙
    • 任取2列， 必缺一把锁的钥匙

1.2 少数与多数：

  • 设相关人共有2n=1个，任意n个组成的少数团体不能打开保险柜，任意n+1个组成的多数团体可以打开保险柜。

  • 两个不同的少数团体联合可成为多数团体。

  • 每个人需拥有他所不属于的所有“少数”团体所打不开的锁的钥匙

每人拥有的钥匙数量： 保险柜至少需要的锁的数量：

1.3 拉格朗日插值定理

  • 某个多项式函数，已知有给定的K+1个取值点：

其中，对应着自变量的位置，而对应着某个函数在这个位置的取值 假设任意两个不同的都互不相同，那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为： 其中，每个为拉格朗日基本多项式（或称之为插值基函数），其表达式为 拉格朗日基本多项式的特点是在上的取值为1，在其他点上的取值为0 。,

1.4 Shamir 秘密共享机制：（基于拉格朗日线性插值）

  • 一保险柜的开启密码为整数X，规定当且仅当相关的n个人中有k个或以上在场方可开启

  • 随机选择K-1个整数 和n个互不相同的整数 。计算

  • 将数ci和bi告知第i个人

  • 由若干与值求X：

    • 若有K人在场，线性方程组有唯一解

    • 其系数矩阵为： 可以看到这个行列式为范德蒙行列式：

  • 若在场人数小于k，系数矩阵行数小于列数，该线性方程组有无穷多解，无法得到X的值。
  • 若k-1次多项式经过点,

  • 其中
  • 计算在有限域中进行 综上所述，若有k个人及以上在场时，该线性非齐次方程组有唯一解。即对应所有()该方程组能求出x的值，否则该线性非齐次方程组有无穷多解。

1.5 中国剩余定理

  • 中国剩余定理即线性同余方程组的求解

其中模数为两两互质的整数，求x的最小非负整数解

若模数不是两两互质的则中国剩余定理失效。

中国剩余定理解题分为以下几个步骤

  • 计算所有模数的乘积
  • 计算第i个方程的
  • 计算在模意义下的逆元
  • 最后求出 例：

  • 因 同理可得

  • 最后根据公式计算出

  • 中国剩余定理的代码实现： 其中mi为模数列表，ai同上述r1，r2，r3列表。fast_pow与fast_mul为快速幂与快速乘。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def CRT(ai, mi, len): #中国剩余定理  
	ans = 0  
	lcm = 1  
	for i in range (len):  
	lcm *= mi[i]  
	for i in range (len):  
	Ci = lcm // mi[i]  
	inv = fast_pow(Ci, mi[i] - 2, mi[i])  
	x = fast_mul(fast_mul(inv, Ci, lcm), ai[i], lcm)  
	ans = (ans + x) % lcm  
	return ans

def fast_pow(a, b, mod):  
	ans = 1  
	a %= mod  
	while b:  
	if b & 1:  
	ans *= a  
	ans %= mod  
	a *= a  
	a %= mod  
	b >>= 1  
	return ans  
    
def fast_mul(a, b, mod):  
	ans = 0  
	a %= mod  
	while b:  
	if b & 1:  
	ans = (ans + a) % mod  
	a = (a + a) % mod  
	b >>= 1 #使用移位来代替乘法  
	return ans

1.6 Asmuth-Bloom门限机制（基于中国剩余定理）

  • 一次同于方程组有唯一小于的非负整数解
  • t-1个人共享秘密份额

该方案中，由秘密S得出的数y对于不同模数的剩余，基于中国剩余定理

在n个人中有t个及以上成员在场时才能解出秘密S

  • 首先令是满足下列条件的一组整数

且对所有的即任意d和p均互质 对 令是t个最小整数之积，则大于任意t-1个.令r是区间z中的一个随机整数，并公布p，r。

  • 秘密分发： 将k划分为n个共享，计算,则n个共享为，将子密钥分配给共享者
  • 秘密重构 若给定t个共享，则由中国剩余定理可知，同余方程组

关于模在内有唯一解x，因为,推出最后计算出即

Eg: 设则 在之间随机取 3个子密钥为 若知道可建立方程组 根据中国剩余定理解得： 因此