一种基于ECC 具有时间限制的动态秘密共享方案

曹 阳，洪 歧，陈 勇，李 军

(陕西理工学院数学与计算机科学学院，陕西汉中723000)

0 引言

基于Lagrange插值多项式(t，n)门限秘密共享方案是Shamir［1］在1979提出的，随后学者对其进行了大量研究。文献［2］中各参与者的秘密份额是由分发者分发的，增加了通信、计算及存储的复杂度;文献［3］解决了参与者的子秘密更新问题，但更新不定期［4］;文献［5］以时间为代价实现了共享秘密的定期动态更新;文献［6］提出的是基于XTR的秘密共享方案;文献［7］提出的秘密共享方案是在秘密分发者安全存储各参与者秘密份额的前提下，参与者的加入与退出不改变其他参与者的秘密份额［8］;文献［9］提出的是基于RSA可验证的动态多重秘密共享方案;文献［10］实现了参与者之间相互验证子秘密，防止了参与者之间的欺诈行为。但以上文献提出的秘密共享方案都具有一定的局限性，基于大数分解、离散对数的难解问题及Shamir的门限方案提出了具有时间限制的动态秘密共享方案。该方案实现了参与者秘密份额由自己生成，秘密更新不需要秘密分发者的参与，参与者只需要维护自己的一份秘密份额就可以共享任意多个秘密;秘密份额必须在有效时间范围内更新才有效，无需额外通信量;参与者的加入与退出不影响其他参与者秘密份额的改变;秘密恢复在有效期内对秘密份额进行验证，防止欺骗行为。

1 相关知识

1.1 椭圆曲线

椭圆曲线［11］指的是由韦尔斯特拉斯(Weierstrass)方程

y2+a1xy+a3y=x3+a2x2+a4x+a6

所确定的平面曲线。系数ai(i=1，2，…，6)可以是有理数域、实数域、复数域，还可以是有限域E(Fp)，椭圆曲线密码体制(elliptic curve cryptosystem，ECC)中用到的椭圆曲线都定义在有限域上的。

1.2 椭圆曲线离散对数问题

G是椭圆曲线E(Fp)上的基点，N为G的阶(N为一个安全的大素数)，如整数m(0＜m＜N－1)存在，Q=mG，则称m为Q的以G为基的离散对数。对于E(Fp)上的一点G，对任意的Q，求整数m，使得Q=mG的问题称为椭圆曲线上的离散对数问题(elliptic curve discrete logarithm problem，ECDLP)［11-12］，椭圆曲线密码体制正是利用这个困难问题设计而来。

1.3 最小授权子集

设A={P1，P2，…，Pn}为用户集P构成的访问结构，Bj={P1j，P2j，…，Pij}(1 ≤ i≤m，1 ≤j≤n)是A的用户子集，Bj∈A，若∀a∈Bj，Bj－a∉A，则称Bj为A的最小授权子集［6］，A为授权集。令Pij∈ Bj，［T1i，T2i］为参与者 Pij的有效期 (1 ≤ i≤m)，称［T1Bj，T2Bj］=［T11，T21］∩［T12，T22］∩…∩［T1m，T2m］=∩mi［T1i，T2i］为最小授权子集 Bj的有效期［6］。本文中提到的授权子集都指的是最小授权子集。

2 方案构成

设SD为可信第三方秘密分发者，NB(notice board)为公告牌，SD通过公告牌将秘密k分为m个子秘密分发给授权子集Bj中的m个不同的参与者{P1j，P2j，…，Pij}(1 ≤i≤m)共享，当且仅当授权子集中的s个或s以上个参与者联合才能恢复秘密k，而非授权子集中的参与者联合不能恢复秘密k的任何信息。公告牌上的内容只有SD才能更新和修改，其他人只能查看下载。本方案由初始化参数选取、注册、秘密份额生成、秘密恢复、秘密份额及秘密的更新5部分组成。

2.1 初始化参数的选取

1)在椭圆曲线E(Fp)上选取基点G，N(N为一个安全的大素数)，N为G的阶，SD在NB上发布G，N;

2)参与者Pij随机选择一个整数ri(1＜ri＜N)，计算Gi=riG，Pij保密ri，将Gi发送给SD;

3)SD选取整数r0(1＜r0＜N)，计算G0=r0G;

4)SD与Pij共同协商一个哈希函数H()，要求冲突的概率足够小;

5)SD在NB上公布参数Gi，G0，H()。

2.2 注 册

设有β个授权子集参与秘密共享。

1)SD 选取 β 个不同的数d1，d2，…，dβ∈［1，N－1］来标识A中的每个授权子集;

2)SD将时间划分成一些小区间，时间的长度可以小时、天、日期、月等为单位，如 1，2，3，…，L，L表示系统中存在的最长时间;

3)SD为每个授权子集Bj中的秘密共享成员设定有效期［T1ij，T2ij］，并在 NB 上发布;

4)SD根据各成员的有效期，计算出每个授权子集的有效期，并在NB上发布;

5)SD随机选取2m个不同的数ai，bi(1≤i≤m)，计算HT1ij(ai)，HL－T2ij(bi)，通过安全信道分别发送给对应的参与者，同时销毁ai，bi。

2.3 秘密份额生成

秘密份额生成的过程由秘密分发者SD和参与者共同完成，生成过程如下。

1)SD随机选取一整数l(1＜l＜N)，l必须与其他秘密分发选取的随机数不同，计算s=lG，并将s在公告牌上公布;

2)A 中的每个一授权子集 Bj={P1j，P2j，…，Pij}(1≤i≤m)，参与者Pij随机选取一整数j(1＜j＜ N)，计算eij=jG，e'ij=jG0，令c0ij=sri⊕e'ij。并将c0ij，eij发送给秘密分发者SD，如果一个参与者同时在多个授权子集中，则该参与者只发送一个c0ij，eij给 SD;

3)SD检查收到的c0ij，eij，保证不同的参与者有不同的c0ij，eij，以免不同的参与者拥有相同的秘密份额。如果相同，参与者就必须重新选取初始秘密份额，直到各参与者都拥有不同的秘密份额，并将参与者的信息c0ij，eij在公告牌上公布;

4)SD计算e'ij=r0eij=r0jG ，sri=cij⊕e'ij，令x0ij=sr，利用公告信息验证sriG是否等于sGi，若相等，则接收x0ij;

5)SD从［1，N －1］中任选整数b，q，生成Lagrange多项式f(x)=(bx+k)mod q，计算f(1)，将(1，f(1))在公告牌上公布;

6)SD为每个授权子集Bj计算Xj=H(d1x01j⊕d2x02j⊕…⊕djx0ij)，f(Xj)，并将f(Xj)，dj在公告牌上公布。

2.4 秘密恢复

秘密恢复是由秘密生成者SG(secret generator)来完成的，SG可以是Bj中的参与者，也可以是非Bj中的其他成员。秘密恢复工作是在t+1次更新前，t次更新后进行的。

1)Bj中的参与者Pij随机选取一整数(1＜j＜N)，计算eij=jG，e'ij=jG0，令ctij=sri⊕ e'ij，将ctij，eij发送给 SG;

2)SG从公告牌上下载((1，f(1))，f(Xj))和dj的有效期;

3)SG判断dj是否在有效期内，如果在，则继续第4)步，如果不在，则向Bj中的每一个参与者发送一个报怨;

4)计算e'ij=r0eij=r0jG，则sri=ctij⊕ e'ij，令xtij=sr，利用公开信息，验证sriG是否等于sGi，如ijiii果相等，接收xtij，验证通过，否则放弃;

5)SG根据Xj=H(d1x1tj⊕d2x2tj⊕…⊕djxtij)和((1，f(1))，f(Xj))，利用Lagrange恢复多项式，从而恢复出秘密k。

2.5 秘密份额及秘密信息的更新

秘密分发者 SD 在时刻 t=1，2，3，…，L进行如下工作。

1)Bj中的每一个参考者 Pij在 t时刻，若t∈ ［T1ij，T2ij］则 计 算utij= Ht(aij)HL－t(bij)=［Ht－T1ij(HT1ij(aij))］［HT2ij－t(HL－T2ij(bij))］;

2)Pij计算xtij=xtij－1+utij，更新所持有的秘密份额，销毁 xtij－1;

3)如果需要更新秘密信息为k'，则SD从［1，N－1］中随机选择一个整数 b'，q，计算f(x)=(k'+b'x)mod q，然后将f(1)公布在公告牌上，如果不需要更新秘密信息则执行下一步;

4)SD为每个授权子集Bj计算Xj=H(d1x1tj⊕d2x2tj⊕…⊕djxtij)，f(Xj)，将f(Xj)，dj公布在公告牌上。

3 方案讨论

3.1 多重秘密共享

方案中每个参与者Pij只需维护自己的秘密份额。如果m个参与者共享n个秘密k1，k2，…kn，当且仅当A中的每一个授权子集Bj中的参与者共同合作才能恢复出秘密，其他未被恢复的秘密的安全性并不会因为此秘密的恢复而受到影响。秘密分发时，分发者SD均随机生成整数l(1＜l＜N)且与其他的随机数不同，计算s=lG，参与者计算sri，根据椭圆曲线离散对数的难解性，攻击者无法从sri计算出ri。公告牌上公布了f(1)，但在构造多项式时，为每个秘密生成了一个参数b，并且为每个授权子集计算了f(Xj)。秘密共享时参与者之间并不会泄露私有秘密份额，加上秘密份额具有时间限制，攻击者就无法利用本次秘密共享结果去计算恢复其他秘密，当然也不会因为重复使用秘密份额而影响系统的安全性。

3.2 参与者的加入/退出

应用中，参与者的加入/退出都会引起访问结构的改变，但并不影响其他参与者秘密份额的改变。当增加一个新的参与者Pn+1时，SD为新增加的参与者Pn+1确定对秘密共享的有效期［T1n+1，T2n+1］，并发布在公告牌上。SD随机选取2个不同的数an+1，bn+1，计算HT1(n+1)j(an+1)，HL－T2(n+1)j(bn+1)，通过安全信道分别发送给对应的参与者，同时销毁 an+1，bn+1。Pn+1从［1，N － 1］中随机选取整数 jn+1，rn+1，计算en+1=jn+1G，e'n+1=jG0，cn+1=srn+1⊕e'n+1，并将srn+1⊕e'n+1，en+1发送给SD。SD检查验证，保证不同的参与者有不同的秘密份额，即对任意的xi(i=1，…，n)，xi≠xi+1。如果参与者 Pn+1的加入导致授权子集的增加，SD需在［1，N－1］选取一个整数dn+1，标识增加的授权子集，并按2.3中的5)和6)计算公布相关信息。当删除参与者Pij时，可能导致某些授权子集变成非授权子集，SD需在公告牌上删除Pij的相关信息，及与Pij相关的授权子集信息、有效期标识。为了安全起见，应该更新共享秘密。

3.3 方案安全性分析

1)方案是安全的。

证明:t时刻，攻击者将要根据公开信息 (1，f(1))以及各授权子集的信息f(Xj)，dj获取秘密k，必须得到 Xj，由 Xj=H(d1x1tj⊕d2x2tj⊕…⊕dxt)可知，要获得X还必须同时获得授权子集中的所有参与者Pij的有效期限和秘密份额xtij。假设攻击者截取ctij，eij，试图计算出秘密份额xtij，由于e'ij=rteij=rtjG，sri=ctij⊕ e'ij，xtij=sri，但要计算出正确的秘密份额还必须获得参与者与秘密分发者的秘密数，由椭圆曲线离散对数问题知，攻击者无法计算出xtij，也就无法获取秘密k，因此方案是安全的。

2)秘密份额及秘密更新是安全的。

证明:时 刻 t=1，2，3，…，L，若 t ∈［T1ij，T2ij］，参与者Pij需要更新自己的秘密份额。秘密份额的更新是通过SD和参与者Pij在秘密生成过程中共同拥有的哈希函数 HT1ij(ai)，HL－T2ij(bi)，计算utij= Ht(aij)HL－t(bij)=［Ht－T1ij(HT1ij(aij))］×［HT2ij－t(HL－T2ij(bij))］来更新秘密份额 xtij=xtij－1+utij。

①当T1ij≤ T2ij＜t时，只能求出 Ht(aij)=［Ht－T1ij(HT1ij(aij))］，但无法求出 HL－t(bij);

②当t＜ T1ij≤ T2ij时，只能求出 HL－t(bij)=［HT2ij－t(HL－T2ij(bij))］，但无法求出 Ht(aij);

③当且仅当T1ij≤t≤T2ij时，才能同时求出Ht(aij)，HL－t(bij)。

综上所述，只有参与者在有效期内，才能更新自己的秘密份额。由于参与者与分发者之间不存在通信，加上哈希函数的单向性及求解的困难性知，Pij以外的参与者是无法得到Pij的秘密份额，所以秘密份额更新是安全的。

通过计算f(x)=(k'+b'x)mod q可将秘密k更新为k'，b'，q是SD从［1，N－1］中随机选择一个整数。

3)方案防止参与者的欺骗。

证明:秘密恢复过程第4)步，计算e'ij=r0eij=r0jG，则sri=ctij⊕e'ij，SG验证sriG是否等于sGi，若相等，说明参与者Pij提供了正确的信息，继续进行秘密恢复工作，否则参与者可能存在欺骗行为，放弃秘密恢复。

4)方案具有前向安全性。

证明:秘密份额生成过程中，参与者Pij在公开信道上向SD发送的c0ij，eij，攻击者截取 c0ij，eij也无法计算出sri，因为e'ij=r0eij=r0jG，sri=c0ij⊕ e'ij，其安全性是建立在椭圆曲线离散对数的安全性之上。

3.4 同类方案相比

下面主要从安全性能、通信复杂度、计算复杂度、运算量四方面与引言中提到的文献［2］方案相比。

安全性能方面:秘密更新必须在有效期内完成，参与者和秘密分发者之间不存在通信，加上哈希函数的单向性及离散对数求解的困难性知，秘密更新的安全性进一步加强。

通信复杂度:参与者秘密份额是由参与者自己生成，且只需维护自己的一份秘密份额就可以共享任意多个秘密，降低了通信的复杂度，进而减少存储空间。

计算复杂度:由文献［8］知Lagrange多项式的计算复杂度比高次多项式的计算复杂度低，加之秘密份额的更新是通过哈希函数完成，秘密分发者与参与者之间不需要同步更新，也不存在传输量问题，所以方案降低了通信、计算的复杂度，提高了更新效率。

运算量:增加授权子集时，秘密分发者SD增加的计算量主要是哈希运算，因而运算量不会大幅度增加。

4 总结

本文基于大数分解、离散对数的难解问题及Shamir的门限方案提出了具有时间限制的动态秘密共享方案。方案实现了参与者Pij秘密份额的生成，更新不需要秘密分发者SD的参与，参与者只需要维护自己的一份秘密份额就可以共享任意多个秘密;秘密份额更新必须在有效的时间范围内更新才有效，参与者和秘密分发者无需同步更新，也不存在通信量的问题;参与者的加入/退出不影响其他参与者秘密份额的改变，当引起授权子集的增加时，计算量主要是秘密分发者进行的哈希运算，参与者的计算量不会随授权子集的增加而增加;秘密恢复在有效期对秘密份额进行验证，防止欺骗行为。方案的安全性基于大数分解、椭圆曲线离散对数问题的难解性及Shamir的门限方案的安全性。

［1］SHAMIR A.How to Share a Secret［J］.Communications of the ACM，1979，22(11):612-613.

［2］LIU Duo，HUANG Dongping，LUO Ping，et al.New Schemes for Sharing Points on an Elliptic Curve［J］.Computers and Mathematics with Applications，2008，56(6):1556-1561.

［3］LAIH C S，HAM L，LEE J Y，et al.Dynamic Threshod Schemes Based on the Definition of Cross Product in Dimensional Linear Space［J］.Joural of Information Science and Engineering，1991，7(1):13-23.

［4］肖立国，钟诚.基于ECC的定期更新的可验证秘密共享方案［J］.计算机工程与科学，2006，28(7):25-27.XIAO Liguo，ZHONG Cheng.A Periodically Renewed Verifiable Secret Sharing Scheme Based on the Elliptic Curve Cryptosystem［J］.Computer Engineering ＆ Science，2006，28(7):25-27.

［5］张建中，张艳丽.一种子秘密可更新的动态多秘密共享方案［J］.计算机工程，2011，37(20):117-119.ZHANG Jianzhong，ZHANG Yanli.Dynamic Multi-secret Sharing Scheme with Updatable Sub-secret［J］.Computer Engineering，2011，37(20):117-119.

［6］赵佳.可信认证关键技术研究［D］.北京:北京交通大学，2008:59-67.ZHAO Jia.Research on Key Technology of Trusted Authentication［D］.Beijing:Beijing Jiaotong University，2008:59-67.

［7］PINCH R.On-line multiple secret sharing［J］.Electronics Letters，1996，32(12):1087-1088.

［8］庞辽军，姜正涛.基于一般访问结构的多重秘密共享方案［J］.计算机研究与发展，2006，43(1):33-38.PANG Liaojun，JIANG Zhengtao.A Multi-Secret Sharing Scheme Based on the General Access Structure ［J］.Journal of Computer Research and Development，2006，43(1):33-38.

［9］王锋，张建中.基于RSA的可验证的动态多重秘密共享方案［J］.计算机应用研究，2008，25(6):1806-1808.WANG Feng，ZHANG Jianzhong. Dynamicverified threshold multi-secret sharing scheme based on RSA cryptosystem［J］Application Research of Computers，2008，25(6):1806-1808.

［10］戴元军，马春光.一种改进的基于拉格朗日插值的(t，n)门限秘密共享［J］.北京邮电大学学报，2004，27(2):24-28.DAI Yuanjun，MA Chunguang.An Kind of(t，n)Threshold Secret Sharing Based on Lagrange Insert Value［J］.Journal of Beijing University of Posts and Telecommunications，2004，27(2):24-28.

［11］曹阳，郝玉洁，洪歧.一种基于ECDLP有身份认证的ECDH密钥协商方案［J］.重庆邮电大学学报:自然科学版，2012，24(1):118-120.CAO Yang，HAO Yujie，HONG Qi.One ECDH key agreement scheme with authentication based on ECDLP［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2012，24(1):118-120.

［12］HANKERSON D，MENEZES A，VANSTONES S.Guide to Elliptic Curve Crypotography［M］.New York，USA:Springer-Verlag，2004.