【密码学】【多方安全计算】Secret Sharing秘密共享浅析

秘密共享(Secret Sharing)是实现多方安全计算的一种常用方式,MPC当然也可以用混淆电路(Garbled Circuit)实现,本文旨在浅析秘密共享的基本原理,有对混淆电路感兴趣的同学可阅读下一篇博客。

什么是秘密共享

Secret Sharing被称为秘密共享或私密共享,有一个秘密数值D,数值D被分解为n个片段并设置一个阈值k,当拥有k个以上片段时才可以恢复数值D,这种秘密分享叫做阈值秘密分享。

普通的秘密分享指将秘密数值D,分解成n个片段,当n个片段都被集合起来时才可以恢复秘密值D。

普通的秘密共享的问题在于,秘密的安全性得到了保证,但是管理的风险增加了,如果有一个片段被丢失将导致整个秘密无法被恢复。所以在业界常用的是阈值秘密共享。本文也就此进行讨论。

加解密过程

在阈值秘密分享中,每个i人手中的信息被记为D_i,从D计算出D_1,…,D_n的过程被称为加密。从k个D_i中计算D的过程称之为解密。
1.加密过程
随机生成k-1个数,a_1,…,a_{k-1},加上a_0==D凑够k个数。多项式的定义:D_i = a_0 + … + a_{k-1}*i^(k-1)。
2.解密过程
凑齐k个人,每人手中有i和D_i。D_i值为上述多项式计算出来的结果,k个多项式就构成了一个方程组,其中a_0,…,a_{k-1}为未知数。通过对方程组的求解即可获得未知数的值。其中a_0为D。

这里方程组未知数的个数为k,所以需要k个以上的方程才能明确未知数的值。如果凑的人数少于k,是无法求解出未知数的。

验证加解密

我们可以设置一个秘密值D来对上述的过程进行验证。我们假设秘密值D=7,只有凑够了k=3人时才可以解密出D的值。
我们构造k个系数,其中a_0=D=7,剩下两个参数我们随机指定,a_1=0,a_2=1。

假设我们有n个人有可能需要了解秘密D,我们给他们每个人的信息如下:
D_1 = q(1)= D + a_1 + a_2 = 8
D_2 = q(2) = D + 2a_1 + 4a_2 = 11
D_3 = q(3) = D + 3a_1 + 9a_2 = 16

D_n = q(n) = D + n*a_1 + n^2 * a_2

假设现在第 1, 3, 10 三个人凑到一起了,他们可以凑出来以下方程组:
D_1 = 8 = D + a_1 + a_2
D_3 = 16 = D + 3a_1 + 9a_2
D_10 = 107 = D + 10a_1 + 100a_2

求解这个方程组,我们得到 a_0=D=7,a_1=0, a_2=1 。其中 a_0=7 就是要揭示的秘密。

参考文献

如何共享一个秘密
密钥分享Secret Sharing介绍

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇

)">
下一篇>>