一个可公开验证秘密共享方案的安全性证明

一种安全的公开可验证门限多秘密共享方案
刘佳;韩文报
【期刊名称】《计算机工程》
【年(卷),期】2009(35)1
【摘要】基于大整数分解以及离散对数问题的难解性,使用非交互的零知识证明协议,以Shamir共享体制为基础提出一种公开可验证的门限多秘密共享方案.分发者给每个参与者分发子秘密的有效性可以被任何人验证.在恢复秘密的时候,参与者只需要提供子秘密的一个影子来恢复秘密,由于影子难以得到子秘密,因此可以通过一组子秘密共享多个秘密.子秘密的影子的有效性也可以被其他参与者验证.该方案不但安全、高效,而且可以有效地防止分发者欺骗和参与者欺骗.
【总页数】3页(P24-26)
【作者】刘佳;韩文报
【作者单位】解放军信息工程大学信息工程学院,郑州,450002;解放军信息工程大学信息工程学院,郑州,450002
【正文语种】中文
【中图分类】TP393
【相关文献】
1.一种基于双线性对的公开可验证多秘密共享方案 [J], 张柄虹;张串绒;焦和平;张欣威;高胜国
2.一种可验证的（t，n）门限秘密共享方案 [J], 史英杰
3.一种基于大数分解和求解离散对数的可验证(k,n)门限秘密共享方案 [J], 马春波;何大可
4.可验证的(t,n)门限秘密共享方案及其安全性 [J], 庞辽军;李慧贤;王育民
5.公开可验证的门限秘密共享方案 [J], 石润华;仲红;黄刘生
因版权原因，仅展示原文概要，查看原文内容请购买。

华中科技大学硕士学位论文一种可验证的门限多秘密共享方案的设计与实现姓名：***申请学位级别：硕士专业：信息安全指导教师：***20090526华中科技大学硕士学位论文摘要随着计算机网络技术的快速发展和电子商务、电子政务的兴起，对重要信息、敏感信息的保护越来越受到整个社会的高度重视。

秘密共享是实现信息安全和数据保密的重要手段之一，它将责任进行分散，提高系统的安全性和健壮性。

在论述了门限秘密共享的产生以及目前国内外的发展状况的基础上，仔细研究分析了门限秘密共享方案、可验证的秘密共享方案和可验证的多秘密共享方案的优点和不足。

针对这些方案中存在的问题和不足，利用RSA 公钥密码算法理论设计了一种可验证的门限多秘密共享方案，并对其安全性进行了分析。

该方案具有以下特点：秘密共享的参与者能够对秘密分发者分发的可验证份额进行验证，防止秘密分发者试图分发假的可验证份额对参与者进行欺诈。

各合格子集中的参与者成员，能够对彼此提供的秘密子份额进行相互验证，防止了不诚实的参与者企图通过提供假的子份额对其他参与秘密恢复的成员的欺诈。

秘密分发者可以动态增加共享的秘密，秘密分发者不需要重新进行可验证秘密份额的分发，各参与者的可验证秘密份额可以重复使用，每个参与者只需保护好一个可验证秘密份额就可以共享多个秘密。

此外，探讨了方案所涉及的一些基本理论，如RSA 公钥密码算法、生成元的求解方法、伪随机数发生器、大素数的选择算法等。

在Windows XP 系统下，借助VC++ 6.0 开发工具和Oracle 9i 数据库建立了该方案的原型系统，试验结果表明，方案是正确和可行的，同时具有很好的安全性和健壮性。

最后进行了总结和展望。

关键词：秘密共享，RSA 公钥算法，可验证秘密共享华中科技大学硕士学位论文AbstractWith the rapid development of computer Network Technology and the rise of e-commerce and e-government, the protection of sensitive information and important information is increasingly attached great importance to society as a whole. Secret sharing is one of the important means to achieve information security and data confidentiality, with it the responsibility dispersed, the system security and robustness can be improved.Based on the discussion of the threshold secret sharing of the produce and the current state of development at home and abroad, careful analysis of the threshold secret sharing scheme, verifiable secret sharing scheme and the number of verifiable secret sharing scheme of the strengths and weaknesses of. Programs for these problems and lack of use of RSA public key cryptographic algorithm, a theoretical threshold verifiable multi-secret sharing scheme and its security analysis. The program is characterized by the following：Secret sharing of the participants were able to distribute the secret share distribution of the secret for authentication, to prevent the Density distribution of the distribution of false attempt to share the secret of the participants in fraud.Members of the various participants in the secret recovery phase, can provide the secret of each other sub-share for mutual authentication to prevent participants in the dishonest attempt to leave through the provision of sub-share participation of other members of the secret fraud recovery.Dynamic secret can increase the distribution of shared secret, the secret is no need for re-distribution of secret distribution, the participants share the secret can be re-used, just to protect each participant shares a secret can be shared on a number of secrets.In addition, the program explored some of the basic theory, such as the RSA public key cryptography algorithm, the solution generator, pseudo-random number generator, large prime numbers, such as the choice of algorithm. In the Windows XP system, using VC++ 6.0 development tool and Oracle 9i database to establish a prototype system of the华中科技大学硕士学位论文program, test results show that the program is correct and feasible, at the same time has good security and robustness. Finally, a summary and outlook.Key words：Secret sharing，RSA public key algorithm，Verifiable secret sharing独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。

1引言1997年文献[1]提出了签密的概念，并给出了一个具体的签密方案。

由于签密比先签名再加密的常规消息传递的代价要小得多，所以非常适合大量数据的认证安全传递。

又因为签密的节省代价与方案中采用的安全参数的长度成正比，当取较大的安全参数时，签密方案的安全性能更佳[2]。

基于身份的密码体制最初是由文献[3]提出，但直到2001年才由文献[4]利用Weil Pairing和Tate Pairing给出了一个很好的实现方案。

2002年文献[5]定义了基于身份的签密方案的安全模型，利用双线性对构造了第一个基于身份的签密方案，该方案提供了消息的保密性和签名的不可伪造性。

文献[6]提出了3个新方案，然而在这3个方案中，没有一个方案能同时满足公开验证性和前向安全性。

文献[7]提供了公开验证性和前向安全性，然而方案同时也有一些不好的特性，如密文的无关联性和匿名性。

文献[8]设计了一个能同时满足公开验证性和前向安全性的签密方案，然而他们的方案需要两个私钥：一个用于签密，一个用于解签密。

该文利用双线性对提出了一个新的基于身份的签密方案，该方案可以在基于身份的密码体制中运行，能够将数字签名和加密有效地结合起来，可以使接受者在不作任何转换的情况下由任意第三方来验证密文消息的来源并可以独立进行签名验证和消息恢复，具有很好的应用前景。

此外，方案效率也非常高。

2基于身份的签密方案的形式化定义采用Malone-Lee定义的基于身份的签密方案的安全概念。

这些概念是语义安全的，即具有在适应性选择密文攻击下不可区分性和在适应性选择消息攻击下不可伪造性。

2.1基于身份的签密方案的组成一个基于身份的签密方案由以下几个算法组成：（1）系统初始化算法（Setup）：此算法由PKG完成，PKG输入安全参数k。

输出系统主密钥s和系统参数params，PKG保密s，公开系统参数params。

（2）密钥生成算法（Extract）：用户U将其身份信息ID U提交给PKG，PKG计算用户公钥Q U=H0（ID U）和私钥S U=sQ U并通过安全方式发送给这个用户。

一种基于身份加密的可验证秘密共享方案李大伟,杨 庚,朱 莉(南京邮电大学计算机学院,江苏南京210003)摘 要: 提出了一种使用IBE 公钥算法实现的可验证秘密共享方案.该方案中秘密分发者将IBE 私钥作为共享秘密在接入结构中分发,任何参与者可以通过公开的验证信息验证影子秘密的正确性.随后在随机预言模型中证明了所提方案的语义安全性.理论分析和仿真实验表明,方案可以有效检测来自内外部攻击者的欺骗攻击,并具有较低的时间复杂度和通信开销.关键词: 可验证;秘密共享;基于身份加密中图分类号: TP309 文献标识码: A 文章编号: 0372 2112(2010)09 2059 07An ID Based Verifiable Secret Sharing SchemeLI Da wei,YANG Geng,Z HU Li(Colle ge o f Computer Scie nce,Nanjing U nive rsity of Posts and Telecommunications.Nanjing ,Jiangsu 210003,China )Abstract: A verifiable secret sharing scheme based IBE is proposed.In the scheme,the shared secret is the private key which extracted by IBE algorithm and every participator can verify the s hares conveniently by the public information.A formal proof of se mantic security of the scheme is provided in the random oracle model.The theoretical analy sis indicates that the scheme can detect cheatings from both inside and outside attacker.The simulation results demons trate that the proposed scheme has remarkable perfor mance in both computation and communication cost.Key words: verifiable;secret s haring ;identity based encryption (IBE)1 引言秘密共享技术是分布式系统中数据保密的重要手段.其主要思想是将共享的秘密分发给接入结构中不同的参与者,达到门限数量的参与者合作才能重构共享的秘密.目前典型的秘密共享体制是Sha mir 提出的基于拉格朗日插值的方案.Shamir 方案的一个假设前提是系统中所有参与者都是可信的,因此无法抵抗某些不诚实参与者发起的欺骗攻击.为解决这个问题,Chor 等[1]首次提出了可验证秘密共享(Verifiable Secret Sharing,VSS)的概念.通过附加的交互式认证算法,参与者可以检验所收到的影子秘密的正确性.此方案的缺点是参与者只能验证各自收到的影子秘密的正确性,难以验证来自其它参与者的影子秘密.为此,Stadler [2]对Chor 方案进行改进,提出了公开可验证的秘密共享(Publicly Ve rifiable Secret Sharing,PVSS)概念.所谓公开可验证是指任何人可以通过公开信息验证影子秘密是否有效而不泄露共享的秘密和参与者持有的影子秘密.Stadler 分别基于离散对数和复合数取模的e 次方根给出了两个PVSS 方案,但这两个方案通信量和计算量都很大(最坏情况为O( 2n)),难以在实际环境中广泛应用.随后有学者致力于对Stadler 方案效率的改进,例如Fujisaki 和Okamoto [3]提出的方案.为降低验证过程的通信开销,Sc hoenmakers [4]使用非交互零知识证明协议实现了一个PVSS 方案,达到了O ( n)的复杂度.近年来,随着密钥托管系统、具有可撤销匿名性的电子支付协议以及电子选举协议的发展,PVSS 方案研究得到了广泛关注[5~7].Yu 等[8]基于零知识证明协议提出的动态P VSS 方案能灵活处理节点加入和退出.Wang 等[9]和Tar tary 等[10]提出的可验证多秘密共享方案能为每个共享秘密设置不同的门限值,提高了系统灵活性和易用性.Pang 等[11]提出的方案影子秘密具有可重用的特性,而Dehkordi 的方案[12,13]具有较好的可用性.上述方案的缺点是验证过程多基于离散对数难解问题,需进行多次模指数运算实现,计算量较大.当方案中秘密共享过程不以离散对数难题作为安全基础时,则需要额外的算法支持,带来计算开销.收稿日期:2009 06 25;修回日期:2010 04 28基金项目:国家自然科学基金(No.60873231);国家973研究发展规划项目(No.2011CB302903);江苏省高校自然科学基金(No.08KJB520006);江苏省 六大人才高峰 基金(No.06 E 044)第9期2010年9月电 子 学 报ACTA ELECTRONICA SINICA Vol.38 No.9Sep. 2010可验证秘密共享方案主要解决秘密共享中的欺骗问题.秘密共享中欺骗攻击主要包括秘密分发者欺骗和参与者欺骗两种情况.分发者欺骗指秘密分发者为某个参与者分配假的影子秘密,致使该参与者在秘密重构时不能提供有效的秘密份额.而参与者欺骗是参与者在秘密重构过程中对其他合作者提供假的影子秘密,会在不影响自身利益的情况下妨碍其合作者秘密重构.针对以上两种攻击,典型的可验证秘密共享方案应该满足:(1)在秘密分发阶段,每个参与者可有效的检验秘密分发者是否发送了正确的影子秘密.(2)在秘密重构阶段,每个参与者可有效的检验其他参与者是否提供了正确的影子秘密.本文基于IBE公钥加密算法,提出了一个可验证的秘密共享方案.方案使用双线性映射在秘密分发阶段生成影子秘密的同时生成验证信息,不需要额外的辅助算法.验证算法采用基于双线性映射的零知识证明算法,参与者可通过公开信息方便有效的对影子秘密进行验证.2 IBE公钥算法基础IBE公钥算法的安全性建立在CD H(Computa t ional Diffie Hellman)困难问题的一个变形之上,称之为BDH (Bilinear Diffie Hellman)问题[14].记Z q={0,!,q-1}为素数阶q的加法群,Z为正整数,G为加法群,F为乘法群.定义1(双线性映射) 对所有x,y∀G,a,b∀Z,映射^e:G#G∃F称为双线性映射,满足:(1)双线性:^e(ax,b y)=^e(x,y)ab;(2)非退化性: P,Q∀G,满足^e(P,Q)%1;(3)可计算性:存在多项式时间算法计算^e(x,y).给定&G,q,P,aP,b P∋,随机选择a,b∀Z*q,计算abP∀G称群G上的CD H问题.随机算法G( )使用一个安全参数 ∀Z+,在 阶多项式时间内输出阶q的加法群G和乘法群F,及其上的双线性映射^e:G#G∃F.对P∀G*,a,b,c∀Z*q,计算^e(P,P)abc称为BDH 问题.I BE公钥算法由四个函数Setup,Extract,Encrypt和Decrypt组成,分别完成系统参数建立、密钥提取、加密和解密的功能.若s为主密钥,Ppub 为系统公钥,H1,H2为单向散列函数,M为明文,身份I D对应的公私钥分别为QID=H1(ID),D ID=sQ ID.Encrypt:选择r∀Z*q.密文C=(U,V),其中U= rP,V=H2(k)M,k=^e(Q ID,P pub)r.Decrypt:M=V H2(^e(D ID,U)).3 方案构成方案基于IBE公钥加密算法,加密者可以通过特定ID的公钥对消息M进行加密得到C.需要进行解密时,解密者首先需要联系持有共享秘密的解密服务器节点,得到多于门限t份影子秘密后,解密者可以通过拉格朗日插值定理重构解密算子,进而解密密文C得到明文M.方案包括系统初始化,共享秘密分发和秘密重构三个阶段.前两个阶段由秘密分发者D完成,方案中秘密分发者同时作为I BE算法的PKG,在秘密分发过程中运行Setup和Extract算法.影子秘密验证过程基于Chaum和Pede rsen非交互零知识证明算法[15]的改进算法,我们称之为B-DLEQ (g1,h1;g2,h2; )算法.其中g1,g2∀(G,+),h1,h2∀GF(P2)*, 为证明者要证明的秘密参数,满足h1=^e ( ,g1),h2=^e( ,g2).H为安全散列函数.证明者选取w∀(G,+),计算E1=^e(w,g1),E2=^e(w,g2),c= H(E1(E2),r=w- c mod q.公开证据PROOF P=(r, c).验证者V通过等式c)H(^e(r,g1)h c1||^e(r,g2)h c2)验证证明者是否拥有正确的 .3!1 基本假设系统结构和信道假设.系统由秘密分发者D(兼有PKG功能)和n个参与者P={P1,P2,!,P n}组成,P 中参与者是解密服务器节点,同时根据实际需要担当解密者的角色.所有节点共享一条广播信道,该信道在稳定性,延迟等方面处于理想状态.任何两个节点间存在一条私有信道,在此信道中传输的信息无法被第三者获取.私有信道可以由硬件实现也可通过加密方法实现.攻击者假设.攻击者分为内部攻击者和外部攻击者.内部攻击者的攻击行为主要表现为影子秘密欺骗.即通过提供虚假的影子秘密企图阻止其他参与者获得共享秘密,在其理想情况(其他参与者都诚实)下只有欺骗者可获得共享秘密.外部攻击者能获得广播信道中所有的公开信息,其攻击行为表现在攻击P中节点,企图获得节点存储的信息(如ID,影子秘密等),并操纵攻破的节点.所有类型的攻击者都可以访问广播信道,进行诸如插入错误信息等攻击.3!2 方案描述3!2!1 系统初始化阶段给定一个安全参数 ,选择大素数p( bit),找一条满足CD H安全假设的超奇异椭圆曲线E/GF(p),生成E/GF(p)上的q(q>2 )阶子群(G,+)和其生成元P,双线性映射^e:G#G| GF(P2)*.设l为明文长度.单向散列函数H1,H2,H3定义为:2060 电 子 学 报2010年H1:{0,1}*| G*;H2,H3:GF(P2)*| {0,1}l.选择主密钥s∀Z*q,计算系统公钥P pub=sP,返回系统参数pa ra=(G,q,P,^e,H1,H2,H3,P pu b).3!2!2 秘密分发和验证阶段秘密分发过程由秘密分发者D完成.秘密分发者执行Extract算法生成特定I D对应的公私钥对Q ID= H1(I D)和D ID=s Q I D.将D I D作为共享秘密分发给参与者集合P中成员.Step1 随机选择插值多项式的系数集合{a j|a j∀G*;j=1,2,!,t-1;a t-1%0}构造t-1阶多项式F(x)=D I D+∗t-1j=1a j x j, x∀{0}+I N(1)其中I N为正整数集合.Step2 计算参与者P i的影子秘密S i=F(i),计算y i=^e(S i,P),1,i,n;Step3 计算验证密钥U j=^e(a j,P pub),1,j,t-1,U0=^e(D ID,P pub);Setp4 通过私有信道发送S i给P i,通过广播信道公布yi,U j,1,i,n,0,j,t-1.任何参与者可以通过公开信息计算Y i=−t-1j=0U i j j(2)分发者D使用B-DLEQ(Ppub,Y i;P,y i;S i)算法生成证据.首先随机选择wi ∀(G,+),计算E1i=^e(w i,P pub),E2i=^e(w i,P),c i=H3(Y i(y i(E1i(E2i),r i= w i-S i c i mod q.公开证据PROOF i=(r i,c i),1,i,n.收到影子秘密后,参与者Pi 通过公开信息计算E1i=^e(r i,P pub)Y c i i,E2i=^e(r i,P)y c i i.验证等式c i)H3(Y i(yi (E1i(E2i).若等式成立,说明D发送的影子秘密是正确的.3!2!3 秘密重构阶段需要解密M的参与者PD向P中成员提出解密申请,通过身份验证后收到来自P中t个成员的影子秘密,其执行的操作如下(设t个成员组成的授权子集为).Step1 验证收到的影子秘密合法性.一般的,参与者Pi 收到参与者Pj(i%j)的影子秘密S j后,根据公开信息Ui,0,i,t-1计算Y j=−t-1l=0U j l l.结合公开参数运行B-DLEQ(Ppub,Y j;P,y j;S j)中验证算法,若成立则证明收到的影子秘密是正确的.Step2 给定IBE密文(U,V),P i计算k=−j∀^e(S i,U)C0,j.其中C0,j为拉格朗日系数,定义为:Cx,j=−l∀,l%j x-lj-l∀Zq.集合∀{1,2,!,n},.t.于是参与者PD得到解密算子k,根据IBE加密算法,明文M=V H2(k).4 证明和分析4!1 正确性证明下面通过两个定理证明方案的正确性.定理1若参与者P i收到的影子秘密通过B-D LEQ(P p ub,Y i;P,y i;S i)验证,则S i为正确秘密多项式产生的影子秘密且在传输中没有被篡改.证明 已知,秘密分发过程中秘密分发者D发送的公开参数y i=^e(S i,P),验证密钥U0=^e(D ID,P pub), U j=^e(a j,P pub),0,j,t-1.根据双线性映射的性质,参与者P i容易得到:Yi=−t-1j=0U i j j=^e(D ID+∗t-1j=1a j i j,P pub)=^e(S i,P p ub)根据B-DLEQ(Ppub,Y i;P,y i;S i)算法的证据PROOF i,有:E1i=^e(r i,P pub)Y c i i=^e(w i-S i c i,P pub)^e(S i,P p ub)c i=^e(w i,P pub)同理,E2i=^e(r i,P)y c i i=^e(w i,P).显然,正确的影子秘密能够通过前述的基于双线性映射的零知识证明协议.证毕.由于参数PROOFi,y i,U j,(1,i,n,0,j,t-1)在共享秘密分发时已经公开,因此在秘密重构过程中,解密请求者也可通过这些信息验证来自任意参与者的影子秘密.定理2 若存在接入结构中的授权子集,满足.t(t为门限值),则解密者根据中成员提供的影子秘密可以解密密文C得到M.证明 需要解密C的参与者PD向中成员发送解密请求,认证通过后得到通过验证的影子秘密{Si|i∀}.将Si同密文中的分量U做双线性运算,结合拉格朗日插值定理,有:k=−j∀^e(S j,U)C0,j=^e(∗j∀C0,j S j,U)=^e(D ID,U)根据IBE算法,明文为:M=V H2(k).证毕4!2 安全性证明类似于公钥加密算法语义安全性证明,我们给出方案在随机预言模型下的安全性证明.本方案核心为根据特定I D在接入结构下共享IBE私钥,证明的基本2061第 9 期李大伟:一种基于身份加密的可验证秘密共享方案思想是攻击者选择两个ID发送给挑战者,后者随机选择一个ID对应的IBE私钥在授权子集中共享.若攻击者通过重构恢复共享秘密后不能以明显大于1/2的概率正确猜测共享秘密来自哪个ID,就称方案具有语义安全性.关于秘密共享方案语义安全性证明的详细论述,参见文献[16].假设多项式时间算法A对秘密共享方案进行攻击,其过程如下:初始化阶段:攻击者宣布被挑战的参与者集合P.系统运行系统初始化过程,根据安全参数k生成系统参数para并公布.攻击者发出影子秘密询问请求,得到P中子集P/的影子秘密.集合P/满足P0P/=t-1 (t为门限值).询问阶段:攻击者提供2个身份标识I D,I D1提交给秘密分发者.后者随机掷硬币得到b∀{0,1},然后运行秘密分发算法,将ID b对应的IBE私钥D I Db在集合P 成员中分发.猜测阶段:重复前一阶段过程.攻击者通过猜测第t个参与者的影子秘密,重构D IDb.输出对b的猜测b/,攻击算法A的优势定义为adv IND CC AA =Pr[b/=b]-12(3)下面通过一个定理证明对本方案的攻击具有攻破IBE公钥算法具有等同的困难性.定理3 若攻击者能攻破本方案,则存在一个多项式时间模拟算法能以不可忽略的优势攻破IBE公钥算法.证明 假设存在一个多项式时间攻击者能够以优势!攻破本方案,构造一个模拟算法Simulator,使其能模拟本方案,并能对IBE公钥算法进行攻击.运行初始化过程,根据安全参数k选择大素数p(k bit),选择椭圆曲线E/GF(p),生成E/GF(p)上的q(q>2k)阶子群(G,+)和生成元P,双线性映射^e:G #G| GF(P2)*.单向散列函数H1,H2,H3,选择主密钥s∀Z*q,系统公钥P pub=sP,返回系统参数para=(G,q,P,^e,H1,H2,H3,P pub).算法Simulator中Extract函数掷硬币得到∀∀{0, 1}.若∀=0,根据攻击者询问的ID,生成对应的私钥D ID =sQ ID.Simulator选择随机多项式F(x),计算影子秘密S i=F(i),y i=^e(S i,P),1,i,n;计算验证密钥U j=^e (a j,P),1,j,t-1,U0=^e(D ID,P).若∀=1,随机生成与正确私钥等长的信息,在授权子集中分发.询问阶段:攻击者提交挑战信息ID,ID1给模拟算法Simula tor.Si mula tor随机掷硬币得到#∀{0,1}.选择P 中子集P/,满足生成私钥,并将P/中成员应得的影子秘密发送给攻击者,公开验证信息.猜测阶段:模拟算法重复前一阶段过程.攻击者猜测#的值,记为#/.当#/=#时,表示攻击者猜中了正确的结果,模拟算法调用Extract函数,输出对应ID的正确的IBE私钥并分发,此时Simulator输出∀/=0.相反,若#/%#,模拟算法输出并分发与正确IBE私钥等长的随机信息,此时Simulator输出∀/=1.考虑以下两种情况:(1)∀=0时,模拟算法分发了正确的IBE私钥,成功的攻击者能恢复正确的共享秘密,表明攻击者攻破了本方案.根据假设条件,这种情况发生的概率为!.于是有:Pr[#/=#|∀=0]=12+!(4)在成功的情况下,∀/=0.事件#/=#等价于事件∀/=∀,由公式(4)可得在∀=0时模拟算法成功攻破IBE 公钥算法的概率为:Pr[∀/=0]=Pr[∀/=∀|∀=0]=12+!(5)(2)∀=1时,模拟算法分发的影子秘密中不包括IBE私钥相关的任何信息,因此攻击者无论如何猜测,都不能得到共享秘密的任何信息.有:Pr[#/%#|∀=1]=Pr[#/=#|∀=1]=12(6)在此情况下,Simulator输出∀/=1,因此事件#/%#的等价事件为∀/=∀.公式(6)可得在∀=1时模拟算法成功攻破IBE算法的概率为:Pr[∀/=1]=Pr[∀/=∀|∀=1]=Pr[#/%#|∀=1]=12(7)结合公式(5)和(7),有:Pr[∀/=∀]=Pr[∀/=0]1Pr[∀=0]+Pr[∀/=1]1Pr[∀=1]=(12+!)112+12112=!2+12故Si mulator成功攻破IBE公钥算法的优势为:advAIND-C C A=Pr[∀/=∀]-12=!2.证毕.4!3 欺骗检测秘密分发者欺骗发生在秘密分发阶段,不诚实的秘密分发者通过为某个参与者分配虚假影子秘密,使该参与者所持的影子秘密无法进行秘密重构.在本方案中,参与者Pi收到影子秘密后,可以通过公开的验证信息PROOFi,y i,U j(1,i,n,0,j,t-1)验证影子秘密的正确性.由于验证密钥是公开的,并且同秘密多项式系数相关联,秘密分发者不能在不影响其他参与者影子秘密验证的情况下对特定的参与者进行欺骗.2062 电 子 学 报2010年在秘密重构阶段,任何参与者都可以通过公开的验证信息判断收到的影子秘密的正确性.验证过程基于双线性映射的零知识证明协议,参与者并不知道秘密多项式的相关信息,无法伪造信息通过验证.因此可以有效检测参与者欺骗行为.综上所述,方案满足前述的可验证秘密共享方案必须满足的两个条件.4!4 抗攻击分析(1)内部攻击内部攻击主要来自于秘密分发者和参与者之间的恶意欺骗.对于参与者来说,发送错误的影子秘密可以在不影响自己秘密重构的前提下防止其他参与者重构共享秘密.在(t,t)密钥共享体制下,存在一种情况使得除恶意参与者之外的其他所有参与者都得不到共享的秘密信息.本文方案的验证机制可有效的对发送方的影子秘密进行正确性验证,从而能阻止内部攻击的发生.此外,由于秘密共享方案具有一定的鲁棒性,在(n, t)秘密共享体制下,即使有恶意参与者存在的情况下,任何包括t个通过影子秘密正确验证的子集都能恢复共享秘密.(2)外部攻击若攻击者A不属于参与者集合P,即A为外部攻击者.A能获取广播信道上传输的所有公开信息,包括系统参数para,验证参数等.公开信息中Uj是秘密多项式系数经过双线性映射计算后的数值.根据双线性映射的性质,攻击者通过U j推测秘密多项式系数面临CD H难解问题的复杂度.同理,攻击者通过y i也无法得到关于影子秘密的任何信息.外部攻击者的另一攻击方法是通过各种手段攻破P中参与者,获得影子秘密等信息.若攻击者获得了少于t个正确的影子秘密企图重构共享秘密,其难度相当于攻破Shamir秘密共享方案.若攻击者获得了t-1个正确的影子秘密企图猜测最后一个影子秘密的值恢复共享秘密,相当于在GF(q)中进行随机猜测,其成功概率仅为1/q.4!5 性能分析与对比(1)计算性能方案主要由共享秘密的分发、影子秘密验证和共享秘密恢复三个协议组成.其中共享秘密的分发和恢复使用基于IBE的门限算法,影子秘密验证使用基于双线性对的零知识证明算法.从计算复杂度方面分析,计算量主要集中在双线性对^e的计算拉格朗日插值等方面(表1).需要指出的是,秘密分发过程包含了分发者对所有影子秘密证明参数的计算,从而带来了一定的计算开销,考虑到实际应用中秘密分发节点通常具有较多的系统资源,因此这些开销不会造成系统瓶颈.表1 方案计算量操作秘密分发份额验证秘密重构^e运算3n+t2tHash运算210Lagrange插值001模指数运算0t+1t-1注:n为节点数量,t为门限值.表1显示,方案的计算量与系统规模有关.设系统中节点数量为n,门限值为t.目前求解双线性映射的一种可行算法是Boneh Franklin提出的基于有限域内超奇异椭圆曲线的算法[17],其计算复杂度为O(log2q).目前普遍使用的快速求幂方法求解模指数运算的计算复杂度为O(log2n).相对于^e运算和模指数运算,拉格朗日插值多项式的运算具有更高的计算复杂度,目前已知的构造经过n个点的插值多项式需要O(n lg2n)次乘法运算,而目前拉格朗日插值算法的复杂度为O(n log22n),插值的计算开销与插值多项式的次数有关.(2)通信量方案通信主要包括广播和单播.众所周知,广播通信是最有效、最节省能量的通信方式.我们方案的各个阶段较多的使用了广播通信,如公布公共参数和验证信息以及系统同步等.相对于广播通信,方案中只有在分发和交换影子秘密时使用安全信道的点对点单播,通信数据量较小.(3)与现有方案的比较与分析下面就秘密共享各阶段的运算量、通信量等方面将本方案与已有方案进行对比分析(表2).比较的标准为复杂运算的调用次数,因为这些运算是方案计算复杂度的主要来源.我们比较的运算包括:双线性对运算(E)、椭圆曲线标量乘运算(M)、模指数运算(S)和拉格朗日插值运算(L),其它运算由于运算量较小而忽略不计.表2 与已有方案的对比分析方案秘密分发阶段影子秘密验证阶段秘密重构阶段通信量验证算法基础本文方案(3n+t)E2E+(t+1)StE+(t-1)S+1L(3n+t)|q|CDH Ti an Peng方案[6](4n+t)M(t+1)E+tS2E+3M+1L(3n+t+1)|q|ECC Yu Kong方案[8](4n+2t+1)S(2n+t+2)S2nS+1L(5n+2)|q|D LPang Li方案[11]>6nM nM tM+1L(3n+1)|q|ECC Dehkordi Mas hhadi方案[13]3nS tS(n-t)S+1L(3n+t+1)|q|D L通过对比可以看出,方案[8,13]由于使用离散对数难题实现影子秘密的验证,引入了较多的模指数运算,其2063第 9 期李大伟:一种基于身份加密的可验证秘密共享方案计算复杂度比使用椭圆曲线(ECC)和CDH 的方案高.而方案[11]在秘密分发阶段生成了一个过n +t 个点的秘密多项式,需要额外付出O ((n +t )lg 2(n +t))的计算量.显然,所提方案在计算量方面具有优势.通信量方面,所提方案主要使用广播信道和非交互式验证,可以用较少通信量实现可验证秘密共享.5 仿真实验为验证方案在实际场景中的性能,我们使用MSVC6.0实现并部署了所提方案.仿真环境是实验室局域网中的计算机集群,节点计算机配置Intel 酷睿2.0GHz CPU,512M DDRII 内存,Windows XP(sp3)操作系统.所有数据均为10次实验结果的平均值.图1显示了秘密分发过程执行时间随网络规模变化呈线性关系.图2为不同门限值下秘密分发过程的计算性能.可以看出,计算时间随网络规模变大而增大,而门限值变化对秘密分发执行时间影响不大.图3、图4显示了影子秘密验证过程的计算性能.结果显示,当系统门限值增大时,验证执行的时间增加,这是因为t 增大时秘密多项式F(x )的阶增加,增大了验证信息处理的复杂度.而验证耗时受网络规模的影响较小,因而方案具有良好的可扩展性.方案中秘密重构过程的计算性能如图5、图6所示.可以看出,秘密重构过程计算时间随网络规模变化不大,但受t 值的影响较为明显.这是因为拉格朗日插值的计算开销与插值多项式的次数相关,实验结果与前述理论分析一致.从绝对量上看,验证和重构所需要的运算量远小于秘密分发需要的计算量,更适合服务器和客户机同时存在的计算环境.图7、图8显示了方案整体的计算性能.从总体上看,所提方案计算性能与网络规模呈斜率较小的线性增长关系,但受t 值的影响较小,因而具有很好的可扩展性.6 结论可验证秘密共享方案具有防欺骗攻击的性质,被广泛应用于密钥分配、电子选举、电子现金等应用环境中.本文基于IBE 公钥算法,提出了一个可验证秘密共享方案.我们使用双线性运算改进了经典的Chaum 和Pederse n 非交互零知识证明算法,提高了方案中影子秘密验证的有效性.通过对方案安全性和可用性的分析显示,所提方案满足可验证秘密共享方案应满足的特2064 电 子 学 报2010年性,同时具有随机预言模型下可证明语义安全性,能抵抗来自内外攻击者的各种攻击.与已有算法的对比显示,所提算法具有较优的时间复杂度和通信开销.参考文献:[1]Chor B,Goldwasser S,Micali S,et al.Verifiable secret sharingand achiev i ng simultaneity in the presence of faults[A].Pro ceedings of26IEEE Symposiu ms on Foundations of Computer Science[C].Washington:IEEE Computer Society,1985.383-395.[2]Stadler M.Publicly verifiable secret s haring[A].Advances inCrypto logy EURO CRYPT296[C].Berlin:Springer Verlag, 1996.32-46.[3]Fujisaki E,Okamoto T.A practical and provably secure schemefor publicly verifiable secret s haring and its applications[A].Advances in Cryptology EUROCRYPT298[C].Berlin: Springer Verlag,1998.32-46.[4]Schoenmakers B.A simple publicly verifiable s ecret sharingscheme and its application to electronic voti ng[A].Advances in Crypto logy Crypto299Proceedings[C].Berlin:Springer V erlag,1999.148-164.[5]Ho u Z F,Han J H,Hu D H.A new authentication schemebas ed on verifiable secret sharing[A].2008International Con ference on Compu ter Science and Software Engineering[C].Wuhan,China:IEEE Computer So ciety,2008.1028-1030. [6]T ian Y L,Peng C G,Z hang R P,et al.A practical publicly verifiable secret s haring scheme based on bilinear pairi ng[A].2nd International Conference on Anti counterfei ting,Security and I dentification,2008(A SID2008)[C].G uiyang,China:IEEE, 2008.71-75.[7]Liu F,Gao D M.On the design of divisible PVSS based electronic cash schemes[A].IEEE International Symposium on Knowledge Acquisition and M odeling Workshop(KAM Work shop2008)[C].Wuhan China:IEEE,2008.112-115.[8]Y u J,Kong F Y,Hao R.Publicly verifiable secret sharing w i thenrollment ability[A].8th ACIS International Conference on Software Engineeri ng,Artificial Intelligence,Networki ng,and Parallel/Distribu ted Computing,2007(SNPD2007)[C].Qing dao,China:IEEE Computer Society,2007.194-199.[9]Wang F,Gu L,Z heng S,et al.A novel verifiable dynamic multi policy secret sharing scheme[A].The12th International Conference on Advanced Communication Techno logy (ICACT2010)[C].Paris France:IEEE,2010.1474-1479. [10]Tartary C,Pieprzyk J,Wang H X.V erifiable multi secret sharing schemes for multiple threshold access structures[A].Infor mation Security and Cryptology2007[C].Berlin:Pringer Ver lag Heidelberg,2008.167-181.[11]Pang L J,Li H X,Y ao Y,et al.A verifiable(t,n)multiples ecret s haring scheme and its analyses[A].2008InternationalSymposiu m on Electronic Commerce and Secu rity(ISECS2008)[C].Guangzho u,China:IEEE Computer Society,2008.22-26.[12]Dehkordi M H,Mashhadi S.An efficient threshold verifiablemulti secret sharing[J].Computer Standards&Interfaces,2008,30(3):187-190.[13]Dehkordi M H,M ashhadi S.New efficient and practical verifiable multi secret sharing schemes[J].Information Sciences:anInternational Journal,2008,178(9):2262-2274.[14]杨庚,王江涛,程宏兵,容淳铭.基于身份加密的无线传感器网络密钥分配方法[J].电子学报,2007,35(1):180 -184.Yang G,Wang J T,Cheng H B,Rong C M.A key establis hscheme for wsn bas ed on ibe and diffie hellman algorithms [J].A cta Electronica Sinia,2007,35(1):180-184.(in Chi nes e)[15]Chaum D,Pedersen T P.Wallet databases w ith observers[A].Advances i n Cryptolo gy CRY PTO292[C].Berlin:SpringerVerlag,1992.89-105.[16]李慧贤,庞辽军.基于双线性变换的可证明安全的秘密共享方案[J].通信学报,2008,29(10):45-50.Li H X,Pang L J.Provably secure secret sharing schemebased on bilinear maps[J].Journal on Communications,2008,29(10):45-50(in Chinese).[17]Boneh D,Franklin M.Identity based encryption from the weilpairing[A].Advances in Cryptology,CRYPTO2001,L ectureNotes in Computer Science[C].Berlin:Springer V erlag,2001.2139.213-229.作者简介:李大伟 男,1981年生于山东潍坊,南京邮电大学计算机学院博士研究生.研究方向为计算机通信网与安全、密钥管理.E mail:lidw1981@杨 庚 男,1961年生于江苏建湖,IEEECE和中国计算机学会会员.南京邮电大学教授、博士生导师.目前研究方向为计算机通信与网络、网络安全、分布与并行计算等.E mail:yangg@朱 莉 女,1984年生于河南商丘,南京邮电大学计算机学院硕士研究生.研究方向为计算机应用技术,信息安全.E mail:zhuli.1984@2065第 9 期李大伟:一种基于身份加密的可验证秘密共享方案。

一个可公开验证且前向安全的签密方案喻琇瑛1，2何大可1，2(1. 西南交通大学信息安全与国家计算网格实验室，成都610031；2. 西南交通大学信息科学与技术学院，成都610031)摘要：签密是实现认证加密的一种新的密码技术，其效率远远高于传统“先签名再加密”认证加密方法。

现有的签密方案往往不能像传统方法那样同时提供前向安全性和可公开验证性。

本文对一个可公开验证的签密方案进行了改进, 提出一个同时具有公开验证性的和前向安全的签密方案。

使攻击者不可能通过发送者私钥得到本次及以前通信者的秘密信息，实现了可公开验证性和前向安全性。

关键词：签密；前向安全；公开验证；Abstract: Signcryption, as a new cryptographic technique, its efficiency is much higher than that of the traditional method “signature- then- encryption”. But signcryption schemes usually cannot provide both forward secrecy and public verifiability simultaneity as the traditional method does.An signcryption schemesis improved and as a result, a public verifiable signcryption schemes with forward secrecy is proposed. In the improved schemes, the attacks which obtain the sender’s private key can not get any secret information between these participates before this communication.By these methods the improved schemes achieve public verifiability and forward security simultaneity.Keywords: signcryption; forward secrecy; public verify;1 引言保密性与认证性是密码学中要研究的重要课题，数字签名和加密是密码学的两个基本而重要的功能，其中数字签名具有提供消息完整性、认证性和不可否认性的功能，而加密则可以提供消息的机密性。

可验证秘密分享及其应用研究可验证秘密分享及其应用研究近年来，随着信息技术的快速发展和广泛应用，秘密分享成为了信息安全领域的一个重要研究课题。

在许多现实场景中，我们需要将秘密信息分为多份并分发给不同的参与者，以保证信息的安全性和完整性。

然而，传统的秘密分享方案存在一些问题，如参与者之间的互信要求高、高计算开销等。

为了解决这些问题，可验证秘密分享应运而生，它不仅能够有效地分发秘密信息，还能够在分发过程中进行验证，以确保数据的完整性和正确性。

首先，我们来回顾一下传统的秘密分享方案。

传统的秘密分享方案通常使用秘密分割算法（如Shamir's秘密共享算法）将秘密信息分为多份，然后将这些份额分发给不同的参与者。

为了恢复秘密，参与者需要合作把自己手中的份额进行组合。

然而，这种方案存在的一个问题是参与者之间需要高度互信。

如果有一个参与者恶意修改了自己手中的份额，就有可能导致最终恢复的秘密信息不正确。

此外，传统方案需要大量的计算开销，因为每次恢复秘密都需要多个参与者的合作，这在某些情况下可能不可行。

可验证秘密分享解决了传统方案存在的问题。

可验证秘密分享不仅能够将秘密信息进行分发，还能够对分发过程进行验证。

这意味着每个参与者都可以验证自己手中的份额是否正确，如果不正确则可以及时发现并阻止参与者尝试修改。

可验证秘密分享采用了零知识证明等技术来实现验证过程，其核心思想是通过参与者之间的相互验证，保证最终恢复的秘密信息的正确性和完整性。

通过引入验证机制，可验证秘密分享方案能够降低参与者之间的互信要求，避免了因为单个参与者的不诚实行为导致数据的破坏。

那么可验证秘密分享有哪些具体的应用呢？它在许多领域都有广泛的应用前景。

首先，可验证秘密分享在云计算安全中具有重要作用。

随着云计算的快速发展，越来越多的用户将数据存储在云端。

而可验证秘密分享可以确保用户在云端存储的数据在传输和存储过程中不被篡改或丢失。

其次，在联邦学习等领域，可验证秘密分享可以保证参与者之间的数据共享过程中的安全性，防止恶意参与者操纵数据。

密码学可证明安全的几种方法
密码学的安全性通常是通过证明其抵抗特定攻击的难度来评估的。

以下是密码学中几种常见的可证明安全的方法：
1. 理论证明：这种方法通过使用数学证明来证明密码方案的安全性。

例如，Diffie-Hellman密钥交换协议的安全性可以通过
数学证明基于数论或离散对数的难解性来得到保证。

2. 归约证明：这种方法将密码学问题归约到一个已知的难题上，通过证明已知难题的安全性来间接证明密码方案的安全性。

例如，将密码方案的安全性归约到离散对数问题或大整数的分解问题。

3. 零知识证明：零知识证明是一种交互式证明协议，用于证明某个秘密信息的真实性，而不泄露该信息的任何详细内容。

通过使用零知识证明，可以证明密码方案的某些属性而不泄露密钥或其他敏感信息。

4. 难解性假设：这种方法基于某些普遍接受的数学假设，如离散对数问题的难解性或大整数的分解问题的难解性。

如果这些假设成立，那么相应的密码方案应该是安全的。

需要注意的是，虽然这些方法可以提供一定程度上的安全性保证，但它们并不意味着密码方案是绝对安全的。

密码学的安全性还依赖于实现和使用的细节，以及攻击者的能力和资源。

因此，在设计和使用密码方案时，仍然需要综合考虑多个因素来确保安全性。

证明书的保密要求和隐私保护措施尊敬的各位领导：我谨向贵公司出具本次证明书，以确认对保密要求和隐私保护措施的合规性，并为进一步保障相关信息的机密性提供明确指导。

一、保密要求概述保密要求是为了防止敏感信息泄露，保护相关方的权益和利益。

在本次证明书中，我们将侧重于以下几个方面的保密要求：1. 保密责任：公司与个人都应认真履行保密责任，不得泄露或未经授权使用任何属于公司或他人的机密信息。

2. 标记与分类：敏感信息应进行正确的标记和分类，以便辨别其重要性和机密级别，并采取相应的保护措施。

3. 信息存储与处理：公司应确保信息存储设备的安全性，并采取合适的措施，防范黑客攻击、病毒传播等风险。

4. 数据传输与通信：对于涉及敏感信息的数据传输和通信，应确保加密和安全性，防止被未授权的第三方获取。

5. 合同与协议：与外部供应商、合作伙伴等签订的合同和协议中应明确约定保密的具体要求，并设定违约责任和赔偿条款。

6. 员工培训与管理：公司应定期组织对员工进行保密培训，加强对保密政策及相关法律法规的宣传和教育。

二、隐私保护措施概述隐私保护措施旨在保护个人的隐私权，确保个人信息的安全和合法使用。

在本次证明书中，我们将重点关注以下几个方面的隐私保护措施：1. 合法收集和使用：公司应遵守相关法律法规，确保个人信息的合法收集和使用，并经过信息主体的同意。

2. 信息分类与访问权限：个人信息应进行分类和等级划分，并确定不同级别的访问权限，仅授权人员可访问相关信息。

3. 数据安全措施：公司应采取物理、技术和管理等多重手段来保障个人信息的安全，防止数据泄露和丢失。

4. 数据共享与转让：在与其他组织共享或转让个人信息时，公司应与相关方签订保密协议，并明确其合法使用和安全保护措施。

5. 客户知情权保护：公司应向客户清楚地披露个人信息的获取方式、使用目的、使用范围等，并尊重客户选择撤销同意的权利。

6. 安全审计和应急预案：公司应定期进行安全审计，发现问题及时解决，并建立健全的应急预案应对信息安全事件。