CIPT扩展知识-隐私增强技术-秘密分享
鹿鼎记中满清的宝藏地图被分别藏在八部《四十二章经》中,交给了满洲八旗的旗主保管,这是一个很有效的秘密保护手段,单个或多个旗主即使觊觎宝藏,只有部分地图是没用的。但它有一个缺陷,如果满清在中原失败了,撤退过程中个别旗主丢失了经书,从此就再也拼不回地图,宝藏也就无法寻回。
在密码学领域,秘密分享(Secret Sharing)就是解决这类问题的方法。它通过将秘密分拆给到多方,实现多方只有共同合作才能得到完整秘密。
我们来看下实现理想的藏宝图秘密分享要满足哪些条件:
1. 八个(n=8)旗主每人有部分数据,但通过自己的数据无法获取到任何秘密内容;
2. 八个旗主中任意的k位(k<=n,比如k=4)把各自的数据拼凑在一起,能解密出藏宝图。
3. 对手在获得k-1位旗主的数据时,也无法获取到秘密。
实现方式
Adi Shamir在论文《How to Share a Secret 》中提出的解法创建N个等式,每个等式有K个变量,用其中任意的K个等式就能解出来各个变量值,解密出秘密。
构造公式为:
即
这中间i是已知数,它代表的是第i为分享者,D₀是秘密值,k是完成解密需要的人数,所以只有a₁到ak以及D₀总共k个未知数。
我们还是直接套上面的例子进行验证,更直观
假设藏宝图的秘密对应的是数字95, 那D₀=95,参与分享秘密的总人数n=8, 凑满k=5人就可以解密。
我们预设a₁ = 1; a₂ = 2; a₃ = 3
这样为某个旗主分配的密文数据是:
旗主 #1 (i=1)得到的是 D1 = D₀ + a₁* i¹ + a₂*i² + a₃*i³ = 95 + 1 * 1¹ + 2*1²+ 3*1³ = 6+95=101
旗主 #2 (i=2)得到的是 D2 = D₀ + a₁* 2¹ + a₂*2² + a₃*2³ = 95 + 1 * 2¹ + 2*2²+ 3*2³ = 34+95=129
旗主 #3 (i=3)得到的是 D3 = D₀ + a₁* 3¹ + a₂*3² + a₃*3³ = 95 + 1 * 3¹ + 2*3²+ 3*3³ = 102+95=197
旗主 #4 (i=4)得到的是 D4 = D₀ + a₁* 4¹ + a₂*4² + a₃*4³ = 95 + 1 * 4¹ + 2*4²+ 3*4³ = 192+95=287
旗主 #5 (i=5)得到的是 D5 = D₀ + a₁* 5¹ + a₂*5² + a₃*5³ = 95 + 1 * 5¹ + 2*5²+ 3*5³ = 430+95=525
旗主 #6 (i=6)得到的是 D6 = D₀ + a₁* 6¹ + a₂*6² + a₃*6³ = 95 + 1 * 6¹ + 2*6²+ 3*6³ = 726+95=821
旗主 #7 (i=7)得到的是 D7 = D₀ + a₁* 7¹ + a₂*7² + a₃*7³ = 95 + 1 * 7¹ + 2*7²+ 3*7³ = 1134+95=1229
旗主 #8 (i=8)得到的是 D8 = D₀ + a₁* 8¹ + a₂*8² + a₃*8³ = 95 + 1 * 8¹ + 2*8²+ 3*8³ = 1672+95=1767
也就是说每个旗主分配到的是一个方程式,比如旗主#2拿到的是 D₀ + 2a₁ + 4a₂ + 8a₃=129。
接下来旗主#2汇合了另外三位旗主,我们随机选 #3 #6和#8,他们四位把四组信息组合在一起:
D₀ + 2a₁ + 4a₂ + 8a₃=129
D₀ + 3a₁ + 9a₂ + 27a₃=197
D₀ + 6a₁ + 36a₂ + 216a₃=821
D₀ + 8a₁ + 64a₂ + 512a₃=1767
求解这四个四元一次方程能得到: D₀=95,a₁=1, a₂=2, a₃=3。 这样就顺利获得了秘密 95.
我们再来验证一次这个实现方式是否满足了之前提到的三个需求
1. 八个(n=8)旗主每人都只有一个四元一次方程,从中无法获取到任何秘密内容;
2. 八个旗主中任意的4位把各自的数据拼凑在一起,就能获得四个四元一次方程,能顺利解密秘密。
3. k-1位(3位)旗主在一起时,只能获得3个四元方程组,无法解开D₀,所以无法解密。
上面介绍的是最简单的一种实现方式,希望能帮助你了解到秘密分享的大致思路。
参考资料:
知乎 - 隐私计算加密技术-秘密分享 - 作者:秃顶的码农