防欺诈的广义多秘密分享方案

第37卷第1期电子科技大学学报Vol.37No.12008年1月JournalofUniversityofElectronicScienceandTechnologyofChinaJan.2008防欺诈的广义多秘密分享方案甘元驹，谢仕义，付东洋，李小立(广东海洋大学信息学院广东湛江524088)【摘要】针对现有的门限多秘密分享方案不能有效地解决秘密成员的动态增加或删除问题，在基于离散对数与单向Hash函数求逆难题，提出了一种具有广义接入结构的高效的多秘密分享方案。该方案可以高效地检测秘密管理者与分享者的欺诈行为；秘密管理者每增加一个新的共享秘密，只需要公开两个参数；子秘密恢复时，采用了并行算法；可高效、动态地增加新成员或删除旧成员，无需重新计算其他成员的秘密份额。关键词密码学;离散对数;单向Hash函数;秘密分享中图分类号TP309文献标识码AAGeneralMulti-SecretSharingSchemeforCheat-ProofGANYuan-ju，XIEShi-yi，FUDong-yang，LIXiao-li(SchoolofInformation,GuangdongOceanUniversityZhanjiangGuangdong524088)AbstractThemostpresentthresholdmulti-secretsharingschemescannotefficientlysolvetheproblemthataparticipantisdynamicaddedordeleted.Inthisstudy,anefficientmulti-secretsharingschemeisdesignedwithgeneralaccessstructurebasedontheintractabilityofreversingtheone-wayHashfunctionandsolvingthediscretelogarithmproblem.Theproposedschemehasthefollowingproperties:cheatingofthedealeroranyparticipantcanbedetectedefficiently;twopublicparametersofanewsecretwouldbepublishedbythedealer;theparticipantsreconstructasecretwithparallelprocedureinasecretrecoveryphase;andtheshadowsofotherparticipantswouldnotchangewhenthesystemacceptsanewparticipantorfiresanoldparticipant.Keywordscryptography;discretelogarithm;one-wayHashfunction;secretsharing*收稿日期：2006−04−06；修回日期：2006−10−27基金项目：广东海洋大学自然科学基金(2006032)；广东省科技基金(2006B501018)作者简介：甘元驹(1974−)，男，硕士，副教授，主要从事密码协议分析与信息安全等方面的研究.文献[1]提出了一种有效的秘密共享方案，可以解决秘密管理者和秘密共享成员的欺骗，且参与者可以用同一个秘密份额共享任意多个子秘密。然而该方案的不足在于为防止秘密管理者的欺诈，每个参与者需要执行模指数运算；同时为了防止参与者之间的相互欺诈，需要执行交互式验证协议。针对文献[1]方案的不足，文献[2]提出一种计算量相对较少、且不执行交互验证协议的多秘密共享方案。文献[3]认为文献[2]存在秘密共享成员欺骗的安全缺陷。文献[4-5]在文献[2]的基础上，各自提出了一种防欺诈的多秘密分享方案。文献[4-7]的方案存在以下不足：(1)这些方案都是基于门限接入结构。由于门限接入结构仅是广义接入结构中的一种特殊情况，在无形中增加了各分享者具有完全平等的地位、权利和可靠性的假设。(2)不能有效地解决秘密成员的增加或删除问题tNC[8]。基于对以上问题的研究，本文设计了一种计算复杂性低、能有效地增加或删除秘密成员的、防欺诈的广义多秘密分享方案。1新的秘密分享方案方案有n个秘密分享者和一个秘密管理者(SD)，有一个只有SD可修改的公告栏NB。1.1系统初始化SD选择如下参数：(1)p和q两个大素数，且q|p−1。(2)g是pZ中的一个q阶元素。(3)一个无碰撞的单向Hash函数H()，并将{p,q,g,H()}放入公告栏NB，其他参数保密。1.2秘密份额的生成设S={,12,,}msssL是在分享者H1,H2,L,Hn中分享的秘密的集合，Γ是H={H1,H2,L,Hn}上的任一单调接入结构，012{,,,}tAAAΓ=LΓ,{1,2,,1}jkn∈+L是的基，SD在NB中依次公布最小合格子集A1,A2,L,At。对每一个分享者Hj计算一个相应的身份信息IDj，j=1,2,L,n；再计算IDn+1，使当且j≠k时，第1期甘元驹等:防欺诈的广义多秘密分享方案69(IDj−IDk)∈Zp*，把IDj(1,2,,1jn=L+n)依次公布于NB中。SD选择一个次数为n的秘密多项式f(x)=cnxn+L+c1x+c0modq，。针对系数c0,1,2,,kck≠=Lk，计算一个检查向量V={v0,v1,,vLn}，其中，kv=modkcgp，k=0,1,L,n。把V放入NB，并计算jx=(ID)modjfq和。SD利用可靠信道把每一个人的秘密份额xmodjxjyg=p,)cj(j=1,2,L,n)安全地送给其拥有者Hj(j=1,2,L,n)，并在公告栏上公布其公钥yj(j=1,2,L,n)。每个分享者Hj收到xj后，验证方程是否成立来检验xmodjxjygp=j的有效性。对每一个最小合格子集，SD由，,,及(0,c12{,,jjjAHH=L}jkH11(ID,(ID))jjf22(ID,(ID))jjfL(ID,(ID))jkjkf0)共k+1个点用拉格朗日插值公式确定一个k次多项式fj(x)，并计算fj(IDn+1)的值[6]，将fj(IDn+1)(j=1,2,L,t)公布于NB中。1.3秘密子份额的生成对任意待分配的秘密sj(j=1,2,L,n)，秘密管理者随机选取一个整数tj∈Zq*，并对秘密sj计算和modjtjCgp=0(modjjjhHCsp=⊕，“⊕”为异或运算；最后SD将{Cj,hj}放入NB。1.4子秘密的恢复设A是H的一个合格子集，最小合格子集，AjAA⊂j中成员要合作恢复秘密ls，Aj成员从NB中获取{Cl,hl}之后，Aj中的每一个Hi计算；并随机选择一整数rmodiixlilQCpΔ=i∈Zq*，计算(,,,,mod,mod)iirrlilililBHgCyQgpCp=和liD=，。把{Q(mod)iliiirBxpΔ+,(0ID)/(IDkjikikHAHHΔ∈≠=−∏i−ID)kli,Bli,Dli,Δi}送给Aj中的其他成员。Aj中每一成员检验{Qli,Bli,Dli,Δi}的有效性为：(,,,,mod,mod)liliililiDBlililiiDBlliBHgCyQgypCQpΔ−−=(1)当Aj中所有成员的{Qli,Bli,Dli,Δi}检验有效后，恢复为：()mjijzlllliHAodshHCQp∈=⊕∏(2)式中。111(ID)(ID(IDID))kjjjnknkHAzf−++∈=−−∏子秘密恢复(式(2))的正确性证明如下：()modjijzllliHAhHCQp∈⊕∏=modjiiijzxlllHAhHCCpΔ∈⎛⎞⊕=⎜⎟⎜⎟⎝⎠∏11,ID0ID(ID)(ID)IDIDIDID(kkjnjinkikHAHAHAHHijkjkjikffllhHC++∈∈∈≠⎛⎞⎛⎞−−⎜⎟+⎜⎟⎜⎟−−⎝⎠⎜⎟⎝⎠∑∏∏⊕×mod)p=00(mod)(mod)cclllHCpsHCp⊕⊕l=s2安全性分析攻击1Aj中某个不诚实成员，企图获取合作者的秘密份额xi。该不诚实成员已知参数、，试图从关系方程求解xliQlCmodiixlilQCpΔ=i。而方程可等价于，因此要求出xmodiixlilQCpΔ=()modjiitxliQgΔ=pi，必须解决离散对数难题；或已知参数、liBliD，试图从关系方程(mod)liiliiDrBxp=+求解xi，但对攻击者该方程包括两个未知数，攻击者也不能求出xi。攻击2秘密sl恢复期间，Aj中不诚实的成员Hi企图为其他合作者给出不正确的{Qli,Bli,Dli,Δi}。若Hi给出伪{Qli,BB)li,Dli,Δi}能够成功地通过式(1)的验证，那么在Aj中的其他诚实合作者将获得假的子秘密sl；而只有Hi能获得真的子秘密sl。显然不诚实成员Hi伪造{Bli,Δi}是没有任何意义。为了通过式(1)的验证，因此Hi可随机选择Qli或Dli，然后从式(1)计算出Dli或Qli，这样将面临单向Hash函数求逆困难性和离散对数难题。[9-10]攻击3Aj中的某一个攻击者，在得不到任何最小合格子集全体成员Qli的前提之下，试图恢复S中的秘密。对于非合格子集，由于得不到某一最小合格子集的全体成员的Qli，就不能从式(2)计算出sl，于是攻击者设法得到c0，然后从方程0(modclllshHCp=⊕中计算出ls。要得到c0，攻击者可以采用如下方法：(1)攻击者从公开信息中求出c00modcvgp=0，会面临求解离散对数的难题。(2)由于c0是n次多项式f(x)及fj(x)的常数项，而每一分享者Hi只知道关于f(x)及fj(x)的公开信息和自己的(ID)modiixf=p)。由于得不到其他最小合格子集成员的f(IDi)，不能用拉格朗日插值公式求出c0，也就不能从0(modclllshHCp=⊕计算出ls。攻击4在没有其他t−1个成员的合作之下，攻击者试图从已经恢复的一些秘密去恢复S中剩下的秘密。(下转第80页)