具有时间限制的动态秘密共享方案.doc

第11A期赵佳等：具有时间限制的动态秘密共享方案5具有时间限制的动态秘密共享方案赵佳1，刘吉强1，韩臻1，沈昌祥1,2(1. 北京交通大学 计算机与信息技术学院，北京 100044；2. 北京工业大学 计算机学院，北京 100022)摘 要：基于XTR公钥体制，提出了一种同时间特性绑定的动态秘密共享方案。方案在同等的安全强度下，将有限域上的求幂运算时间降为原来的1/3；每个参与者在有效期之外不能参与共享秘密；参与者更新秘密份额时不需要秘密分发者的参与；秘密分额更新过程简单且具有前向安全性；每个参与者只需要维护一个秘密份额就可以实现多重秘密共享。方案的安全性基于Shamir门限方案、求解迹离散对数的困难性和散列函数的单向性。关键词：秘密共享；XTR体制；前向安全；秘密更新中图分类号：TN918.1 文献标识码：A 文章编号：1000-436X(2008)11A-0001-06Time-bound dynamic secret sharing schemeZHAO Jia1, LIU Ji-qiang1, HAN Zhen1, SHEN Chang-xiang1,2(1.School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China; 2.College of Computer, Beijing University of Technology, Beijing 100022, China)Abstract: A time-bound dynamic secret sharing scheme based on the XTR public key system was proposed which can reduce three times on exponential operations at the same security. In the scheme, every participant can not share the secret out of the period of validity; the dealer delivers nothing when participants update the shadows; the process of updating shadow is forward secure and each participants share many secrets with other participants by holding only one shadow. The security of the scheme is based on the security of Shamirs threshold scheme, the XTR discrete logarithm problem and the security of one-way hash function.Key words: secret sharing; XTR system; forward secure; secret update1 引言收稿日期：2008-10-15基金项目：国家高技术研究发展计划（“863”计划）基金资助项目（2007AA01Z410，2007AA01Z177，20060101Z4015）；国家重点基础研究发展规划（“973”计划）基金资助项目（2007CB307101）；北京交通大学基金资助项目（K08J0030）Foundation Items: The National High Technology Research and Development Program of China (863 Program)(2007AA01Z410, 2007AA01Z177, 20060101Z4015); The National Basic Research Program of China (973 Program)( 2007CB307101); Foundation of Beijing Jiaotong University (K08J0030)1979年Shamir1和Blakley2分别独立提出了基于Lagrange插值多项式方法和基于射影几何理论的秘密共享方案，这2种方法都属于(t, n)门限秘密共享方案。此后，秘密共享方案在密钥管理和多方安全计算等方面得到广泛的研究和长足的发展，如动态的秘密共享方案3,4，具有前向安全性的共享方案5，多重秘密共享方案6，基于图的攻击结构的秘密共享方案7等等。(t, n)门限秘密共享方案是在n个参与者中共享秘密，使得至少要t个参与者才可以重构出该秘密。2004年Pang等人在文献8中提出了一种基于一般访问结构的多重秘密共享方案，以下称为PLJ方法。一般访问结构下的秘密共享是指将秘密信息在一组参与者的集合中进行分配，每个人分享一个子秘密，单个参与者无法恢复出秘密，只有满足条件的合格子集才能由每个人分享的子秘密恢复出完整秘密信息的一种方法。显然，(t, n)门限秘密共享方案只是一般访问结构中的一种特殊情况。PLJ方法基于Shamir门限方案和RSA密码体制，使用一阶的Lagrange插值多项式，降低了多项式的计算时间。但是在该方案中，较多地使用了有限域上的求幂运算，这就使得整个方案的效率不高。此外，PLJ方案中，如果更新秘密时不更新每个参与者的秘密份额，那么该方案中每个参与者的秘密份额就不具有前向安全性；如果更新秘密的同时也更新每个参与者的秘密份额，那么又增加了秘密分发者和秘密共享者之间的通信量。基于上述几个方面的需求，文中提出了具有时间限制的动态秘密共享方案。本文的贡献主要体现在如下几个方面：给秘密份额增加了时间限制，只有在给定的时间范围内，秘密份额才有效；更新秘密份额无需额外的通信量，参与者只需少量的计算即可；使用了XTR公钥秘密体制，使得有限域上求幂的运算量降低为原来的1/3。2 XTR公钥密码体制理论文中的秘密共享方案是基于XTR（efficient and compact subgroup trace representation）公钥密码体制的，以下先对XTR密码体制作一些简单介绍。XTR公钥密码体制是一种基于有限域中乘法子群元素的迹函数表示方法的密码体制9。XTR属于移位寄存器序列密码体制，研究者所熟知的RSA公钥密码体制和ElGamal公钥密码体制采用的是GF(p)上的1阶移位寄存器序列，而XTR公钥密码体制采用的是3阶移位寄存器序列，应用了上的阶为q（q为且大于3 的素因子）的特殊子群，可以在同等安全强度下较大地降低计算复杂性。设，则3阶多项式可以表示为，则由生成的q阶子群称为XTR群。若为既约多项式，设其中任一个根为，其阶为q，则q为的大于3 的因子。g的共轭元为：；g的迹函数为，且有。已知 ，求k的值在计算上是不可行的。这称为求解迹离散对数问题（XDL）。XTR公钥系统的安全性是基于在XTR群中求解迹离散对数的困难性。在XTR体制下求解XDL问题的困难程度与在中求解离散对数问题的难度相同。在已知和k时，求的计算量相当于在中进行次乘法运算，比已知g和k时，计算的运算速度快大约3倍。此外，因为而，所以的表示、存储、传输所需要的时间和空间复杂度都是的1/310。本文就是应用XTR公钥系统的迹运算代替PLJ方案中的求幂运算，在不降低安全性的前提下提高了运算效率。3 方案构成文中提出的具有时间限制的动态秘密共享方案分为参数选择、注册、生成初始秘密份额、更新秘密份额及秘密信息和恢复秘密5个阶段。秘密分发者D（dealer）通过公告牌（notice board）将秘密s分发给最小特权子集A中的n个不同的参与者P1,P2，Pn共享。只有秘密分发者D可以修改和更新公告牌上的内容，其他人只能阅读和下载这些内容。分发者将秘密s分成n个子秘密分别给予n个参与者，使得访问结构的授权子集中的成员能够联合恢复出秘密s；而非授权子集中的参与者联合不能得到秘密s的任何信息。假设，如果对于，则称A为的最小授权子集。时间被划分成一些离散的区间段，例如1, 2, z，其中z表示系统存在的最长时间，而这些时间段的长度可以是一天，一个月，一个季度等等。每一个参与者Pi都有一个有效期t1i, t2i，只有在该有效期内Pi才能分享秘密。定义1 A为的最小授权子集，t1i, t2i为参与者Pi的有效期。则称 为最小授权子集A的有效期。为了叙述方便，如不特别说明，下文中的授权子集均指最小授权子集。3.1 公共参数选取秘密分发者D选取参数1) 随机选取2个大素数u和v满足RSA密码体制的要求，令N=uv；2) 选取素数，且 ，g的阶为q；3) D在公告版上公布系统参数，并销毁u, v；4) 从2, N中随机选取整数k，使得k与u1和v1互素，计算；找到一个满足的整数e，保密k，在公告牌上公布。其中，表示欧拉函数，即不大于N且与N互素的正整数的个数；5) 选取并公布单向散列函数h( )。3.2 注册阶段假设系统中共有r个授权子集参与，1) 秘密分发者D选取r个不同的数 来标识中的每个授权子集；2) D设定每个授权子集中的成员Pi共享秘密的有效期t1i, t2i并发布在公告牌上；3) D根据成员的有效期，计算出每一个授权子集的有效期并发布在公告牌上；4) D随机选取2n个不同的数，计算分别通过安全通道发送给对应的参与者，并销毁。3.3 初始秘密份额的生成1) 对中的每一个授权子集，随机选取整数作为自己的初始子秘密，计算，Pij保密，并将发送给D。如果一个参与者同时在多个授权子集中，那么该参与者只需计算一个发送给D；2) D检查收到的，确保对于任意2个不同的参与者都有不同的，以避免不同的参与者使用相同的秘密份额，一旦出现相同的情况，D必须要求这些参与者重新选取其初始秘密份额，直到所有参与者都拥有不同的份额为止；3) D在公告牌上公布每个参与者Pij的信息；4) D从1, u1中随机选择一个整数b，构造Lagrange插值多项式，然后计算并在公告牌上公布信息f(1)；5) D为每个授权子集计算(1)6) D在公告牌上公布每个授权子集的信息。3.4 秘密份额及秘密信息的更新在时刻进行以下工作。1) 对中的每一个授权子集中的参与者在时刻t，若，则计算 2) Pij按照更新所持有的秘密份额，并销毁；3) D为每个参与者Pij计算和 ，并根据和计算出 （使用文献11中的迹的快速计算方法来实现），D在公告牌公布； 4) 如果不需要更新秘密信息，则转至第5）步。如果需要更新秘密信息为s时，则D从1, u-1中随机选择一个整数b，更新Lagrange插值多项式，然后计算并在公告牌上更新信息；5) D为每个授权子集计算(2)6) D在公告牌上公布每个授权子集的信息。3.5 秘密的恢复恢复工作在第t次更新后，第t+1次更新前进行，秘密的恢复由秘密生成者DC（designated combiner）来完成，DC可以是中的参与者也可以是其他成员。1)中的每一个授权子集，计算自己的子秘密 ，并发送给DC；2) DC从公告牌下载和的有效期；3) DC判断此时是否在的有效期内，如果在有效期内，则继续进行第4)步，否则，向中的每一个参与者发送一个抱怨；4) 计算5) DC利用2个点和，由Lagrange插值法1重构：(3)6) 恢复的共享秘密为s= f (0) mod q。3.6 子秘密的验证为防止参与者出示伪造的子秘密，已知，其他成员可以利用式(4)对参与者提供的子秘密进行验证。(4)4 访问结构的改变在实际情况中，中的访问结构会有所变化，而且中的参与者也会变化，参与者的变化主要是添加或删除操作，下面是添加和删除参与者的具体操作步骤。4.1 增加参与者假设在t0时刻增加参与者Pn+1。1) D为新增加的参与者Pn+1确定对秘密共享的有效期t1n+1, t2n+1，并发布在公告牌上；2) D随机选取2个不同的数，且，计算通过安全通道发送给Pn+1，并销毁；3) Pn+1随机选取作为初始秘密份额，并计算发送给D，Pn+1保密；4) D检查收到的，确保没有，然后公布；5) 增加参与者Pn+1的m个授权子集为，D根据成员的有效期，计算出m个授权子集的有效期并发布在公告牌上；6) D随机选择m个整数 ，计算相应的，在公告牌上公布。4.2 删除参与者假设在时刻删除参与者Pi。系统有2种情况需要删除参与者，一种情况是该参与者的有效期到期，要退出授权子集；另一种情况是该参与者虽然还在有效期内，但是由于某种原因需要强行删除该参与者。删除参与者要进行以下步骤。1) D在公告牌上将参与者Pi的信息和有效期移入公告牌的撤销列表中；2) D在公告牌上删除含有Pi的m个授权子集的信息及有效期。访问结构的改变也可能是参与者没有变化，而是增加或减少了授权子集。如果是增加了授权子集，可以应用4.1节的第5）步和第6）步完成；如果是减少授权子集，可以应用4.2节的第2）步完成。这里就不再详述。5 性能分析文中提出的秘密共享方案是基于PLJ方案的，所以具有PLJ方案的所有安全特性。在PLJ方案中重构一次多项式f(x)时，需要知道使得该多项式成立的2个点的值。其中一个点(1, f(1)已经公开，对于一个授权子集的参与者，可以合作计算出，得到另一个点；而非同一个授权子集中的参与者不能够联合计算出这样的点。攻击者对用户秘密份额猜测的成功率为，假设授权子集中含有d个参与者，而且每个参与者的秘密份额不同，所以攻击者通过猜测用户秘密份额而得到共享秘密的概率为；如果攻击者直接对点进行猜测，成功率为，当N (N q)足够大时，和都趋近于0。此外，文中的秘密共享方案还满足如下性质。定理1 在秘密份额的更新过程中，只有参与者Pij在自己的有效期内，Pij才能更新秘密份额。证明 在时刻，每个参与者都需要更新自己的秘密份额，中的每一个授权子集中的成员在注册过程中得到，通过计算来更新秘密份额。 1) 当时，因此虽然可以求得，但是无法求出；2) 当时，因此虽然可以求得，但是无法求出；3） 当且仅当时，且，因此既可以求出也可以求得。综上所述，只有参与者Pij在有效期内，才能更新自己的秘密份额。证毕定理2 秘密份额的更新是安全的。证明 在上述方案的秘密更新过程中，是根据通过式(5)计算得到的。(5)只有Pij和秘密分发者D知道，其他参与者无法获得这2个散列函数值，所以就不能计算出。根据散列函数的单向性和求解迹离散对数的困难性，可知除Pij以外的其他参与者都无法得到Pij的秘密份额，所以秘密份额的更新是安全的。证毕定理3 上述秘密共享方案具有前向安全性。证明 根据文献5中的前向安全理论可知，上述方案的前向安全性质应该体现在2个方面：被共享秘密的前向安全性；每一个参与者所分享的子秘密的前向安全性。下面就从这2方面证明方案的前向安全性。1) 因为每一个被共享的秘密信息是独立选择的，所以攻击者无法根据现在的共享秘密推断出以前的共享秘密，因而被共享的秘密具有前向安全性。2) 当攻击者得到方案中某个参与者Pij在t时刻的子秘密后，试图通过式(6)求解w时刻Pij的子秘密，这是基于XDL困难问题的，因此攻击者无法通过得到时刻的子秘密。 证毕(6)效率分析：因为文中的方案是对PLJ方案的改进，所以主要同PLJ方案的效率进行比较。1) 使用了PLJ方案中的一阶插值函数，比Shamir门限方案中多项式的计算复杂度低；2) 求幂运算：使用XTR公钥密码体制下的迹的运算代替了PLJ方案中的有限域上的幂运算，使得在相同的安全强度下，运算所需的时间降为原来的1/3；3) 传输量方面：由于给秘密份额增加了时间限制，当参与者更新秘密份额时，只需要少量散列函数的计算即可，不需要与D进行同步交互，因而减少了传输量。6 结束语基于迹离散对数的困难问题，使用与时间绑定的秘密份额更新方法对PLJ方案进行了改进，提出了一种同时间特性绑定动态秘密共享方案。该方案在同等的安全强度下，将有限域上的求幂运算时间降为原来的1/3；参与者更新秘密份额时不需要秘密分发者的参与；每个参与者在有效期之外不能参与共享秘密；秘密份额更新过程简单且具有前向安全性；每个参与者只需要维护一个秘密份额就可以实现多重秘密共享。该方案既保证了各参与者的秘密份额具有前向安全性，又不增加秘密分发者和秘密共享者之间的通信量，应用价值较高。参考文献：1SHAMIR A. How to share a secretJ. Communications of the ACM. 1979, 24(11): 612-613.2BLAKLEY G. Safeguarding cryptographic keysA. Proc AFIPS 1979 Natl, ConfC. New York, 1979. 313-317.3LAIH C, HARN L, LEE J, et al. Dynamic threshold scheme based on the definition of cross-product on n-dimensional linear spaceA. Proc Crypto89C. Santa Babara, California, USA, 1989.20-24.4何业锋，张建中. 基于因子分解和离散对数的动态秘密分享方案J. 电子与信息学报, 2004, 26(6): 1005-1008.HE Y F, ZHANG J Z. A dynamic secret sharing scheme based on factorization and discrete logarithmsJ. Journal of Electronics and Information Technology, 2004, 26(6): 1005-1008. 5王彩芬，刘军龙，贾爱库等. 具有前向安全性质的秘密共享方案J. 电子与信息学报, 2006, 28(9): 1714-1716.WANG C F, LIU J L, JIA A K, et al. A forward secure secret sharing J. Journal of Electronics and Information Technology, 2006, 28(9): 1714-1716. 6CHANG T, HWANG M, YANG W. An improvement on the Lin-Wu threshold verifiable multi-secret sharing scheme J. Applied Mathematics and Computation, 2005, 163: 169-178.7郭渊博，马建峰，王亚弟. 一种基于图的攻击结构的秘密共享方案J. 计算机研究与发展, 2005, 42(5): 877-882.GUO Y B, MA J F, WANG Y D. An efficient secret sharing scheme realizing graph-based adversary structures J. Journal of Computer Research and Development,