基于Shamir秘密共享的可验证多秘密共享模型

基于Shamir秘密共享的可验证多秘密共享模型摘要:多秘密共享技术影响着信息安全和密码学在新型网络应用中的发展。分析了两种YCH改进和一种基于齐次线性递归的多秘密共享方案，基于Shamir秘密共享提出并实现了一种新的可验证的多秘密共享模型，该模型在秘密合成阶段的时间复杂度为O(k×t2)，优于两种YCH改进模型(O(t3)(tk)O(k3)(t≤k),O(k×(n+k)2))，实际模拟中秘密合成时间则少于其他三种模型，并且分析了四种模型在时间复杂度、可验证性和公开值等方面的优劣性。在nk时，新模型所需公开值小于其他三种模型，实验结果表明，新模型在秘密分发时间和秘密合成时间方面均优于其他三种模型。关键词:多秘密共享；lagrange插值；齐次线性递归；Shamir秘密共享中图分类号:TP393文献标识码:AVerifiablemulti-secretsharingschemebasedonShamirsecretsharingAbstract:Thedevelopmentoftheinformationsecurityandcryptographyinthenewnetworkapplicationsisinfluencedbymulti-secretsharingtechnology.Inthispaper,weanalysetwokindsofimprovedYCHandamulti-secretsharingsolutionbasedonhomogeneouslinearrecursion,andweproposeandrealizeanewverifiablemulti-secretsharingmodelbasedonShamirsecretsharing,thetimecomplexityofthismodelinthephaseofsecretsrecoveryisO(k×t2),whichissuperiortoothertwokindsofimprovedYCHmodel(O(t3)(tk)O(k3)(t≤k),O(k×(n+k)2)),thetimeofsecretssynthesisintheactualsimulationislessthantheotherthreemodels,andwealsoanalysetheadvantagesanddisadvantagesofthefourmodelsonthetimecomplexity,verifiabilityandopenvalues.Whennk,theopenvalueswhichthenewmodelneedsarefewerthanthatoftheotherthreemodels,theexperimentalresultsshowthatthenewmodelisbetterthantheotherthreemodelsonthetimeofsecretsdistributionandsecretsrecovery.Keywords:Multi-secretsharing;Lagrangeinterpolationpolynomial;Homogeneouslinearrecursion;Shamirsecretsharing1引言秘密共享在导弹发射、电子商务、电子选举和安全多方计算等方面有着广泛的应用。A.Shamir[1]和G.Blakley[2]分别在有限域的多项式插值和有限几何的基础之上提出了秘密共享的概念。由于Shamir的(t,n)门限秘密共享机制是最简单、最有效也是最实用的一种秘密共享机制[3]，Shamir秘密共享机制成为秘密共享研究的主流。但传统的秘密共享只能保护一个秘密信息，于是多秘密共享方案被Blundo[4]等人提出，在多秘密共享方案中，每个成员只需要分配一个秘密份额，便可以同时共享多个秘密。在随后的几年中，多秘密共享得到了迅速发展。Jackson[5]等人将所有的多秘密共享模型分为一次性模型和可重复使用模型。所谓一次性模型，即在每次秘密恢复之后，成员的秘密份额泄露，必须给每个成员重新分配秘密份额。而可重用模型可以避免这个问题，在可重用模型中，每次秘密恢复之后，无需重新分配秘密份额，也能保证每个成员秘密份额的安全性和有效性。但是当时提出的大多数模型都是一次性模型。基于此问题，He等人[6]提出了一种多阶段秘密共享方案，该方案期望通过运用单项函数来保护秘密份额并使得秘密按照一定次序顺次恢复。方案需要k个插值函数，每个插值函数的常数项gi(0)为秘密pi，因此重复性工作很多。该方案中需要的公开值个数为k×t个。随后Harn提出了一种改进模型[7]，改进后的模型需要的公开值个数为k×(n-t)个，改进方案适用于t的数目近似于n的情况下。但实际上这两种模型都是一次性模型，并不适合实际应用[8]，并且公开值的个数也没明显的减少。Chien等人[9]提出了一种基于分组码的多秘密共享模型，模型中运用单向双值函数保护秘密份额，保证了该模型的可重用性，在秘密恢复阶段通过解n+p-t个方程，秘密可被同时恢复出来。该方案将公开值降低到n+p-t+1个。Yang等人[10]认为Chien提出的模型虽然减少了公开值的个数，但并非建立在Shamir模型基础之上。于是他们给出一种基于Shamir模型的改进模型YCH模型，该模型分为两种情况考虑，当p≤t时，构建t-1次插值多项式，算法需要n+1个公开值，当pt时，构建p-1次插值多项式，算法需要n+p-t个公开值。此方案同样利用了双值单向函数，也同样通过解方程组来同时恢复所有秘密，因此在秘密恢复阶段的时间复杂度与[9]基本相同。显然，当pt时YCH模型的公开值与[9]相比并没有减少，于是Pang等人[11]对YCH模型进行了进一步的改进。在YCH方案中秘密pi作为插值函数的系数，而在Pang等人的模型中pi作为插值点的y坐标分量，构造n+p-1次插值多项式。该方案不需要分两种情况考虑，在任何情况下公开值都维持在n+p-t+1个。但在YCH模型和Pang模型中都没有考虑成员欺骗的问题，且由于秘密份额由秘密分发者生成，需要另外设立安全信道来向每个成员传输秘密份额。Zhao[12]等人基于YCH模型利用离散对数的难解性，在原模型的基础上添加了验证机制，使得每个成员都可以验证用于恢复秘密的秘密份额的正确性，有效地防止了成员欺骗，简称Z模型。另外在Z模型中，每个成员的秘密份额由自身生成，不需要额外开设用于传输秘密份额的安全信道。但由于Z模型的主体部分继承了YCH模型的方法，因此也继承了YCH模型的不足，在秘密分发和秘密合成阶段都需要分成两种情况考虑。随后，He等人[13]对Pang模型进一步完善，同样添加了验证机制，解决了安全信道问题，简称H模型，该模型继承了Pang模型的优点，可以用统一的方法来完成秘密分发和秘密合成，不需要分情况讨论。但该模型两次利用lagrange插值函数，且插值多项式为n+k-1阶，在秘密分发阶段的时间复杂度为O((n+k-t)×(n+k)2)，在秘密合成阶段的时间复杂度为O((k×(n+k)2)，计算开销很大。Dehkordi等人[14]提出了两种基于齐次线性递归的可验证多秘密共享模型，简称D模型。两种模型通过利用齐次线性递归构造t-1次多项式，将秘密恢复时间复杂度减低到O(k×t2)。但在秘密合成阶段D模型需要计算i，辅助计算开销很大。本文提出了一种基于Shamir模型的新模型，该模型在秘密恢复阶段的时间复杂度也为O(k×t2)，但本文模型在秘密恢复阶段无需计算大数幂方，辅助计算较少，所以实际秘密恢复时间比D模型少。新模型的成员欺骗问题和安全信道问题采用与其他三种模型相同的方法完成，这样能更清晰的反应模型主体在计算时间方面的差别。新模型需要2n+k+5个公开值，在nk时，新模型所需的公开值个数少于其他三种模型。另外，新模型在秘密分发阶段的时间复杂度小于H模型，而在秘密合成阶段，新模型与D模型同为时间复杂度最小的模型。通过实验进一步对四种模型在计算时间方面进行了分析，可以看出D模型和新模型都为计算时间较少，且稳定性较好的模型，新模型在秘密合成阶段的计算时间少于D模型，在秘密合成阶段，仅t值很大时新模型的合成时间在小范围内多于D模型，其他情况下均与D模型基本相同。本文其余部分结构如下：第2节介绍三种模型，给出本文提出的新模型，并对四种模型进行了理论分析；第3节给出实验数据，并对四种模型在计算时间方面做进一步分析；最后为结论和展望。2四种模型及其理论分析本文选择实现的三种模型都利用离散对数的难解性实现秘密份额的保护和验证，而用不同的方法实现了秘密分发和秘密恢复，因此能够更好地分析出多秘密共享模型中，由于秘密分发与秘密恢复方法的不同，对整体方案在公开值、时间复杂度等方面的影响。2.1Z模型此模型在YCH模型的基础上进行改进，考虑到成员欺骗问题，添加了验证，不需要单独开设安全信道。而秘密分发与秘密恢复方法与YCH模型中提出的方法基本相同。方案中p1,p2,…,pk为k个待保护的秘密。M1,M2,…,Mn为n个参与秘密共享的成员。D为秘密分发者。具体方案如下：2.1.1初始化阶段D选择两个强素数p和q，计算N=pq；在[N1/2,N]中随机选择一个整数g(g与p,q互素)；发布{g,N}。每个Mi在[2,N]中随机选择一个整数si作为自己的秘密份额，计算Ri=gsimodN，并将Ri和标识号IDi传送给D。D必须保证Ri≠Rj(Mi≠Mj)，否则D要通知Mi重新选择秘密份额，直到所有Ri都符合条件以后，发布{(IDi,Ri)}。2.1.2秘密分发阶段1)D在[2,N]中随机选择一个整数s0，s0与p-1和q-1互素。s0×f=1modΦ(N)，计算f；2)计算R0=gs0modN，计算Ii=Ris0modN，(i=1,2,…,n)；3)公布{R0,f},当k≤t时随机选择素数Q，随机在[0,Q]中选择整数a1,a2,…,at-k。用p1,p2,…,pk,a1,a2,…,at-k做系数，构造t-1阶多项式如下：h(x)=p1+p2x+…+pkxk-1+a1xk+a2xk+1+…+at-kxt-1modQ⑴计算yi=h(Ii)modQ(i=1,2,…,n)；公布{y1,y2,…,yn}。当kt时随机选择大于N的素数Q，用p1,p2,…,pk做系数构建k-1阶多项式：h(x)=p1+p2x+…+pkxk-1modQ⑵计算yi=h(Ii)modQ(i=1,2,…,n),计算h(i)modQ(i=1,2,…,k-t),公布{y1,y2,…,yn,h(1),h(2),…,h(k-t)}。2.1.3秘密恢复和验证阶段1)Mi计算I’i=R0simodN，作为自己的子秘密；2)每个参与秘密恢复的成员都可以验证其他参与成员给出的子秘密是否有效，如果I’if=RimodN说明I’i为有效，否则Mi可能有欺骗行为。3)当k≤t时，通过(I’i,yi)构建插值函数如下：11,'()mod''ttjiiijjjiQxIhxyII⑶=p1+p2x+···+pkxk-1+a1xk+a2xk+1+···+at-kxt-1modQ当kt时，通过(I’i,yi)和(i,h(i))构造插值函数如下：11,'()mod''ttjiiijjjixIhxQyII11,()modktktijjixjhiQij⑷=p1+p2x+···+pkxk-1modQ2.2H模型此模型秘密分发阶段将秘密作为插值点构造n+k-t次lagrange插值多项式，秘密合成阶段再次使用lagrange插值多项式将k个秘密恢复出来。模型子秘密验证和安全信道问题的解决方法与Z模型相同。p1,p2,…,pk,M1,M2,…,Mn,D的意义也同Z模型[10]。DC为秘密恢复者。2.2.1初始化阶段D选择两个强素数p和q，计算N=pq；随机选择一个大于N的素数Q；在[N1/2,N