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

1、基于Shamir秘密共享的可验证多秘密共享模型摘要:多秘密共享技术影响着信息安全和密码学在新型网络应用中的发展。分析了两种YCH改进和一种基于齐次线性递归的多秘密共享方案，基于Shamir秘密共享提出并实现了一种新的可验证的多秘密共享模型，该模型在秘密合成阶段的时间复杂度为O(kt2)，优于两种YCH改进模型(O(t3)(tk) O(k3)(tk),O(k(n+k)2)，实际模拟中秘密合成时间则少于其他三种模型，并且分析了四种模型在时间复杂度、可验证性和公开值等方面的优劣性。在nk时，新模型所需公开值小于其他三种模型，实验结果表明，新模型在秘密分发时间和秘密合成时间方面均优于其他三种模型。关

2、键 词: 多秘密共享；lagrange插值；齐次线性递归； Shamir秘密共享中图分类号: TP393文献标识码: AVerifiable multi-secret sharing scheme based on Shamir secret sharingAbstract: The development of the information security and cryptography in the new network applications is influenced by multi-secret sharing technology. In this paper, we

3、analyse two kinds of improved YCH and a multi-secret sharing solution based on homogeneous linear recursion, and we propose and realize a new verifiable multi-secret sharing model based on Shamir secret sharing, the time complexity of this model in the phase of secrets recovery is O(kt2), which is s

4、uperior to other two kinds of improved YCH model (O(t3)(tk) O(k3)(tk) ,O(k(n+k)2), the time of secrets synthesis in the actual simulation is less than the other three models, and we also analyse the advantages and disadvantages of the four models on the time complexity ,verifiability and open values

5、. When n k, the open values which the new model needs are fewer than that of the other three models, the experimental results show that the new model is better than the other three models on the time of secrets distribution and secrets recovery.Key words: Multi-secret sharing;Lagrange interpolation

6、polynomial;Homogeneous linear recursion; Shamir secret sharing1 引言秘密共享在导弹发射、电子商务、电子选举和安全多方计算等方面有着广泛的应用。A.Shamir1和G.Blakley2分别在有限域的多项式插值和有限几何的基础之上提出了秘密共享的概念。由于Shamir的(t,n)门限秘密共享机制是最简单、最有效也是最实用的一种秘密共享机制3，Shamir秘密共享机制成为秘密共享研究的主流。但传统的秘密共享只能保护一个秘密信息，于是多秘密共享方案被Blundo4等人提出，在多秘密共享方案中，每个成员只需要分配一个秘密份额，便可以同时共享

7、多个秘密。在随后的几年中，多秘密共享得到了迅速发展。Jackson5等人将所有的多秘密共享模型分为一次性模型和可重复使用模型。所谓一次性模型，即在每次秘密恢复之后，成员的秘密份额泄露，必须给每个成员重新分配秘密份额。而可重用模型可以避免这个问题，在可重用模型中，每次秘密恢复之后，无需重新分配秘密份额，也能保证每个成员秘密份额的安全性和有效性。但是当时提出的大多数模型都是一次性模型。基于此问题， He等人6提出了一种多阶段秘密共享方案，该方案期望通过运用单项函数来保护秘密份额并使得秘密按照一定次序顺次恢复。方案需要k个插值函数，每个插值函数的常数项gi(0)为秘密pi，因此重复性工作很多。该方案

8、中需要的公开值个数为kt个。随后Harn提出了一种改进模型7，改进后的模型需要的公开值个数为k(n-t)个，改进方案适用于t的数目近似于n的情况下。但实际上这两种模型都是一次性模型，并不适合实际应用8，并且公开值的个数也没明显的减少。Chien等人9提出了一种基于分组码的多秘密共享模型，模型中运用单向双值函数保护秘密份额，保证了该模型的可重用性，在秘密恢复阶段通过解n+p-t个方程，秘密可被同时恢复出来。该方案将公开值降低到n+p-t+1个。Yang等人10认为Chien提出的模型虽然减少了公开值的个数，但并非建立在Shamir模型基础之上。于是他们给出一种基于Shamir模型的改进模型YCH

9、模型，该模型分为两种情况考虑，当pt时，构建t-1次插值多项式，算法需要n+1个公开值，当pt时，构建p-1次插值多项式，算法需要n+p-t个公开值。此方案同样利用了双值单向函数，也同样通过解方程组来同时恢复所有秘密，因此在秘密恢复阶段的时间复杂度与9基本相同。显然，当pk时，新模型所需的公开值个数少于其他三种模型。另外，新模型在秘密分发阶段的时间复杂度小于H模型，而在秘密合成阶段，新模型与D模型同为时间复杂度最小的模型。通过实验进一步对四种模型在计算时间方面进行了分析，可以看出D模型和新模型都为计算时间较少，且稳定性较好的模型，新模型在秘密合成阶段的计算时间少于D模型，在秘密合成阶段，仅t值

10、很大时新模型的合成时间在小范围内多于D模型，其他情况下均与D模型基本相同。本文其余部分结构如下：第2节介绍三种模型，给出本文提出的新模型，并对四种模型进行了理论分析；第3节给出实验数据，并对四种模型在计算时间方面做进一步分析；最后为结论和展望。2 四种模型及其理论分析本文选择实现的三种模型都利用离散对数的难解性实现秘密份额的保护和验证，而用不同的方法实现了秘密分发和秘密恢复，因此能够更好地分析出多秘密共享模型中，由于秘密分发与秘密恢复方法的不同，对整体方案在公开值、时间复杂度等方面的影响。2.1 Z模型此模型在YCH模型的基础上进行改进，考虑到成员欺骗问题，添加了验证，不需要单独开设安全信道。

11、而秘密分发与秘密恢复方法与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= gsi mod N，并将Ri 和标识号IDi 传送给D。D必须保证RiRj(MiMj)，否则D要通知Mi重新选择秘密份额，直到所有Ri都符合条件以后，发布(IDi ,Ri)。2.1.2 秘密分发阶段1) D在2,N中随机选择一个整

12、数s0，s0与p-1和q-1互素。s0f = 1 mod (N)，计算f；2) 计算R0=gs0 mod N，计算Ii= Ris0mod N，(i=1,2,n)；3) 公布R0 ,f,当kt时随机选择素数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-1 mod Q 计算yi=h(Ii)modQ(i=1,2,n)；公布y1,y2,yn。当kt时随机选择大于N的素数Q，用p1,p2,pk 做系数构建k-1阶多项式：h(x)= p1 + p2x

13、+pkxk-1 mod Q 计算yi=h(Ii) mod Q (i= 1,2,n),计算h(i)mod Q (i=1,2,k-t),公布 y1,y2,yn, h(1),h(2),h(k-t)。2.1.3 秘密恢复和验证阶段1) Mi计算Ii = R0si mod N，作为自己的子秘密；2) 每个参与秘密恢复的成员都可以验证其他参与成员给出的子秘密是否有效，如果Ii f = Ri mod N 说明Ii为有效，否则Mi可能有欺骗行为。3) 当kt时，通过(Ii ,yi)构建插值函数如下： = p1+p2x+pkxk-1+a1xk+a2xk+1 + +at-kxt-1 mod Q 当kt时，通过(I

14、i ,yi)和(i,h(i)构造插值函数如下： = p1 + p2x +pkxk-1 mod Q2.2 H模型此模型秘密分发阶段将秘密作为插值点构造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中随机选择一个整数g(gp,gq)；发布g,N,Q。每个Mi 在2,N中随机选择一个整数si作为秘密份额，并计算

15、Ri=gsi mod N；在k,Q-1中随机选取IDi作为身份标识，并把Ri 和IDi 发送给D。D要确保RiRj (MiMj)，否则D通知Mi 重新选择秘密份额，发布Ri ,IDi。2.2.2 秘密分发阶段1) D在2,N中随机选取s0 ，s0与p-1和q-1互素，计算R0=gs0 mod N；2) s0f = 1 mod(N)，Ii = Ris0 mod N，D计算f和Ii，公布f,R0；3)用(0,p1),(1,p2),(k-1,pk),(ID1,I1), (ID2,I2),(IDn ,In)构造n+k-1阶多项式：h(x) = a0 + a1x +an+k-1x n+k-1 mod Q

16、 4) 在k,Q-1-IDi |i=1,2,n中依次选取n+k-t个最小的素数d1,d2,dn+k-t，计算并发布h(d1),h(d2),h(dn+k-t)。2.2.3 秘密恢复阶段1) 每个参与秘密恢复的成员计算I i =R0si mod N,作为子秘密，并将I i 发送给DC；2) 子秘密验证阶段与Z模型11相同。3) DC用与秘密分发阶段相同的方法选取n+k-t个最小的素数d1,d2,dn+k-t，利用(d1,h(d1),(d2,h(d2),(dn+k-t,h(dn+k-t),(ID1,I1),(ID2, I 2),(IDt ,I t)构造lagrange插值多项式如下： = a0 +

17、a1x +an+k-1x n+k-1 mod Q4) 计算pi =h(i-1) mod Q ( i=1,2,k)。2.3 D模型该模型在秘密分发阶段运用齐次线性递归，将k个秘密与递归数列联系在一起，在秘密合成阶段通过lagrange插值得到辅助方程，将递归数列和k个秘密恢复出来。模型中验证阶段和安全信道问题同Z和H模型的解决方法相同，M1 ,M2 ,Mn ,D的意义也与Z和H模型相同。P1, P2,Pk 为k个秘密。2.3.1 初始化阶段D选择两个强素数p1和p2，计算 p1, p2；在N1/2,N中选择一个整数g ，g的阶为素数p(pN)；选择整数0，构造辅助方程：(x-)t = xt +

18、a1xt-1 + + at = 0 D选择素数q(qpai (i=1,2,t)，发布N, g, q,。每个Mi 在2,N中随机选择整数si作为秘密份额，计算Ri=gsi mod N，并将(Ri ,i)传送给D。D要确保RiRj (Miz Mj)，否则通知Mi重新选择秘密份额，发布R1,R2,Rn 。2.3.2 秘密分发阶段1) D随机选择一个整数f，f和(N)互素，计算s0使其 满足s0f = 1 mod (N)。2) 计算R0=gs0 mod N，计算Ii=Ris0mod N (i=1,2,n)。3) 构造齐次线性递归方程组： 4) 计算ui (tin+k)。5) 计算yi=Ii - ui-

19、1 (tt)时间复杂度秘密分发O(nt) (kt)O(n+k-t)(n+k)2)O(n+k-t)t)O(n+k)t)O(n+k-t)k) (kt)秘密合成O(t3) (kt)O(k(n+k) 2)O(kt2)O(kt2)O(k3) (kt)通过表1可以看出当nk时，D模型和本文模型的公开值个数较少，且此时本文模型更优于D模型。D模型秘密分发阶段的时间复杂度最小， H模型在秘密分发阶段的时间复杂度最大。在秘密合成阶段D模型和本文模型的时间复杂度最小。当t值很大时，Z模型的秘密合成时间复杂度最大，当n值和k值很大时，H模型秘密合成时间复杂度最大。3 实验与讨论实验环境为Lenovo QiTianM

20、6900；CPU：Inter Core 2 Duo，E7500 2.93GHz；内存：2038MB RAM；编程工具为Microsoft Visual Studio 2008。分别考察成员个数(n)、门限值(t)和秘密个数(k)对四种模型的秘密分发时间(TD)和秘密恢复时间(TR)的影响，并进一步分析四个模型在计算时间方面的性能。Fig.1 secret distrubiting time, t=5,k=5图1 秘密分发时间，t=5 k=5Fig.2 secret recovering time, t=5 k=5图2 秘密恢复时间，t=5 k=5首先，分析成员个数n对秘密分发时间和秘密合成时间

21、的影响。图1给出了此情况下的四种模型的秘密分发时间曲线，可以看出随着n的增加，Z模型、D模型和本文模型秘密分发时间缓慢增加。H模型的秘密分发时间迅速增加。Z模型、D模型和本文模型在此情况下秘密分发时间基本相同，且均好于H模型。图2给出了成员个数n对秘密恢复时间的影响曲线。由于k和t不改变，Z模型、D模型和本文模型的秘密合成时间基本不变。此时，t和k的值相同，Z模型、D模型、本文模型的秘密合成时间大致相同，且均好于H模型。综合对图1和图2的分析，在t和k不变且数值较小时，n变换时，Z模型，D模型，本文模型表现较好，H模型表现较差。Fig.3 secret distrubiting time,k=

22、5 n=50图3 秘密分发时间，k=5 n=50Fig.4 secret recovering time,k=5 n=50图4 秘密恢复时间，k=5 n=50其次，考察门限值t对秘密分发时间与秘密合成时间的影响。通过图3可以看出，随着t的增加，Z模型和本文模型秘密的分发时间缓慢增加，H模型的秘密分发时间迅速下降。开始时由于辅助计算的增多，D模型秘密分发时间缓慢上升，后来随着t的增加又缓慢下降。当门限值t的值小于40时，D模型所用秘密分发时间最少，此后顺次为本文模型、Z模型和H模型。由于H模型的秘密分发时间随t的增加逐渐减少，当t值增加到40后，所用秘密分发时间逐渐少于Z模型，而t达到43左右，

23、所用秘密分发时间逐渐少于本文模型。图4展示了门限值t对秘密恢复时间的影响。可见随着t的增加，D模型和本文模型的秘密合成时间逐渐增加。此时tk，Z模型的时间复杂度为O(k3)，随着t的增大，Z模型秘密合成时间增加。从时间复杂度分析，Z模型所用秘密合成时间的增加幅度应该与D模型和本文模型基本相同。但实际上Z模型的秘密合成时间随着t的增加大幅度增加，原因是，Z模型在秘密合成阶段需要求解方程组来得到k个秘密，而系数矩阵中有t组行向量为(0,Ii,Iit-1)，因此随着t的增加需要求解的大数幂方增加，Z模型的秘密合成时间会大幅度增加。从时间复杂度分析，在n和k不变时，H模型的秘密和成时间应该保持不变，但

24、实际上随着t的增加H模型的秘密合成时间也逐渐增加。其原因是，在秘密合成阶段需要t个IDi和n+k-t个di作为插值点的x分量，x分量要进行大量的乘法运算，而ID的值要远远大于d的值，因此，t的增加使得H模型的秘密合成时间增加。当t25后合成时间少于D模型，在t45后合成时间少于本文模型。综合对图3和图4的分析，在k和n不变，t变化时，D模型和本文模型表现较好，H模型和Z模型分别在秘密分发阶段和秘密合成阶段所用时间最多。Fig.5 secret distrubiting time,t=5 n=50图5 秘密分发时间，t=5 n=50Fig.6 secret recovering time,t=5

25、 n=50图6 秘密恢复时间，t=5 n=50最后，讨论秘密个数k对秘密分发时间与秘密合成时间的影响，结果分别如图5和图6所示。从图5可以看出，随着k的增加，D模型和本文模型的秘密分发时间以极小的幅度增加。Z模型的分发时间相对前两种模型，增加幅度较大。此时n值很大，H模型所用的分发时间在开始时就达到400ms左右，随着k逐渐增加，H模型的秘密分发时间增加幅度非常大。从时间复杂度分析，当kt时，Z模型秘密分发的时间应该少与本文模型，但实际上本文模型所用的分发时间较少。原因是，在分发阶段Z模型需要计算h(Ii)，属于大数，计算开销较大，而本文模型只需计算h(i)即可。从图6中可以看出，随着k的增加

26、，D模型和本文模型的秘密合成时间都增加的非常缓慢，仅由辅助计算的增加引起了合成时间的增加。H模型的增加幅度略比D模型和本文模明显。由于此时kt，Z模型的时间复杂度为O(k3)，随着k的增大，Z模型秘密合成时间大幅度增加。从时间复杂度分析，Z模型在此情况下的合成时间曲线应该与仅t变化时秘密合成时间曲线相同。但实际上，显然当前情况下秘密合成时间较少。原因同样是Ii 的幂方的计算引起的，在此情况下由于t值很小，大数幂方的计算相对较少，因此所用的合成时间与t变化时相比明显减少。综合对图5和图6的分析，此情况下D模型和本文模型表现较好。H模型和Z模型分别在秘密分发和秘密合成阶段所用时间最多。从以上分析中

27、不难看出，H模型和Z模型都不稳定，都会出现计算时间最多的情况，不是适合于实际应用的模型。在任何情况下，D模型和本文模型下的秘密分发时间和合成时间都相对较少，属于稳定性较好的模型。在秘分发阶段，D模型和本文模型所用时间基本相同，仅当t值很大时，本文模型的秘密分发时间大于D模型，但在实验范围内，稳定在200ms之内，仍然好于其他两种模型。而在秘密合成阶段，本文模型所用时间均少于D模型。在秘密分发阶段，由于有秘密分发者参与，硬件配置较好，而在秘密合成阶段秘密分发者无法参与，考虑到成员组件本身的硬件制约以及秘密恢复的紧急性要求，秘密恢复阶段的计算时间应为考虑的重点。因此从计算时间上考虑，在上述四种模型

28、中，本文模型为最优模型。4 结束语随着多秘密共享的迅速发展，亟需对原有模型在公开值、可验证性、计算时间等方面进行对比分析，并提出一种更适合于实际应用的优质模型。本文实现了三种已有的可验证多秘密共享模型，基于Shamir秘密共享提出并实现了一个新的(t,n)可验证多秘密共享模型。对四种模型在公开值、可验证性、时间复杂度等方面进行了理论分析，新模型在nk时需要的公开值最少，且秘密合成阶段的时间复杂度仅为O(kt2)，好于H模型和Z模型。通过实验模拟对四种模型，并分析四种模型秘密分发时间与秘密恢复时间随着n、t和k的改变而变化的情况。分析结果表明新模型在秘密恢复阶段所用计算时间最少，在实验范围内秘密

29、分发时间也能稳定在200ms之内，仅在t值很大时，秘密分发时间多于D模型。实验验证了新模型在计算时间方面优于其他三种模型。下一步将研究动态的多秘密共享方案，即参与者集合可以动态变化，而无需重新分配秘密份额仍能保证秘密共享模型的可用性和安全性的方案。参考文献:1 A.Shamir, How to share a secret, Communications of the ACM 22 (11) (1979) 612-613.2 G.Blakley, Safeguarding cryptographic keys, Proc.AFIPS 1979 National Computer Confere

30、nce, AFIPS Press, New York, 1979,pp. 313-317.3 刘木兰，张志芳著。 秘密共享体制和安全多方计算。电子工业出版社2008年2月第一版。4 Blundo C.,De Santis A.,Di Crescenzo G.,Giorgio Gaggia A.,Vaccaro U. Multi-secret sharing schemes, Advances in Cryptology CRYPTO94,Y.G.Desmedt,ed.,Lecture Noters in Comuputer Science 839, pp.(1994),150-163.5 W.

31、-A.Jackson, K.M. Martin, C.M. OKeefe, On sharing many secrets, Asiacrypt94 917 (1994) 42-54.6 J. He, E. Dawson, Multistage secret sharing based on one-way function, Electronics Letters 30 (19) (1994) 1591-1592.7 L. Harn, Comment: Multistage secret sharing based on one-way function, Electronics Letters 31 (4) (1995) 262.8 T.-Y.Chang, M.-S.HWang, W.-P.Yang, A new multi-stage secret sh