如何共享秘密?

2020年4月19日22:37:40 发表评论

请不要想太多,这里讲的是有一个秘密需要N个人共同保守,但任意其中K(<N)个人可以恢复秘密,而少于K的任何几个人都不能恢复秘密。如何做到这一点呢?

插值函数

首先介绍一下什么是插值函数,它是指一个多项式

f(x)=a0+a1x1+...+ak-1xk-1

然后我们插入k个(xi,yi)对,就可以得到k个次方程组,然后利用线性代数知识我们便能求解系数。因此,只要知道了k个点就能确定这个多项式系数。

共享秘密

利用插值函数,我们可以生成N个不同x的(xi,yi)对,而只需要其中k个便能确定这个多项式。最后秘密就是和y轴的交点即(0,y)中的y。第i个人会得到一个片段Di,Di计算方法如下:

Di=f(i)

然后凭借k个Di我们便可恢复秘密。这个方案也被称之为(K,N)门限。

但这个方案有一个问题,即它处理的结果是一个实数,可能难以保存或者记忆,因此我们对上述方案醉了一点更改,即对f(x)的结果取模p,并且p>N并且p>M(秘密)。即:

f(x)=a0+a1x1+...+ak-1xk-1mod p

这样得到的Di片段就在[0,p)之间了。另外,系数也是从[0,p)中选取。因为进行了模运算,因此想要恢复秘密也要困难上一丢丢,下面给出恢复秘密的方法:

如何共享秘密?

代入x=0即可求解f(0)=a0。其中指数-1表示它关于模p的乘法逆元。

PS:博主猜测是利用范德蒙行列式解的,但一时没找到公式推导来源。

作业

假设k=3、N=5、p=17、p1=8、p3=10、p5=11,求解信息a0

答案:

此处为隐藏的内容!
发表评论并刷新,才能查看

共享秘密的应用

共享秘密可以用作权力限制,假如一家对所有支票进行数字签名的公司,假如高管们都共享签名,那么这个签名很可能会被滥用或者泄露,而如果让所有高管都同时在场才能签名效率未免太过低下。于是,共享秘密就可以在两者之间取得一个很好的平衡,即规范了权力,又能保证签名有足够的安全性。

flyingsheep

发表评论