广播多重签名方案中阈下信道的封闭协议

测试题四一、判断题（12分）1.通过执行协议必须完成某项任务或达成某项共识。

2.在对称密钥体制中，加密密钥和解密密钥是一样的或者彼此之间是容易相互确定的。

3.否认签名和普通数字签名最本质的不同在于：对于不可否认签名，在得不到签名者配合情况下其他人不能正确进行签名验证，从而可以防止非法复制和扩散签名者所签署的文件。

4.在公钥协议中，数字证书可离线担保实体确实是公钥的所有者。

5.Rabin体制和RSA体制基于大数问题。

6.阈下信道有密钥保护，安全性很高。

7.部分盲签名这里的部分就意味着代签名的消息是由签名申请方和签名方共同生成的。

8.在Rabin的一次签名方案中签名的验证只需要签名者。

9.无线网络的工作模式可分为基础结构模式和自组织网络模式。

10.部分盲签名这里的部分就意味着代签名的消息是由签名申请方和签名方共同生成的。

11.在Rabin的一次签名方案中签名的验证只需要签名者。

12.无线网络的工作模式可分为基础结构模式和自组织网络模式。

二、填空题（18分）1.秘密共享是一种将的密码技术。

2.根据RFID标签的能量来源，可以将其分为三大类：3.零知识证明具有正确性、、。

4.常用的保证新鲜值的机制有、、。

5.零知识证明的简单模型有、分割选择协议、一般的协议。

6.从证书包含的信息数量来看，数字证书的选择性泄露分为两种：单一数字证书内容泄露和。

7. _________________________________________ 在重放中，攻击者介入协议运行，通过 ______________________________________ 再重放的方式实现攻击。

8.理论上不可攻破的密码系统通常称作。

9.部分盲签名较好的克服了的一些固有的缺点。

10.若至多可以用来对一个消息进行签名，否则签名就可能被伪造，我们称这种签名为。

11.当用户接收到的信息都是二进制串时，用户无法判断二进制串是否经过加密等处理,就是利用这一点使得用户将一个消息错误的解释成其他的消息。

应急广播安全保护技术规范数字签名1 范围本技术文件规定了应急广播信息主体文件、应急广播消息指令文件和传输覆盖指令的数字签名安全保护机制。

本技术文件适用于应急广播从应急信息接入、制播、调度控制、传输覆盖到接收全流程的安全保护。

2 规范性引用文件下列文件对于本文件的应用是必不可少的。

凡是注日期的引用文件，仅注日期的版本适用于本文件。

凡是不注日期的引用文件，其最新版本（包括所有的修改单）适用于本文件。

GB/T 32905—2016 信息安全技术 SM3密码杂凑算法GB/T 32918（所有部分）信息安全技术 SM2椭圆曲线公钥密码算法3 术语和定义下列术语和定义适用于本文件。

3.1应急广播消息 emergency broadcasting message各级应急广播平台之间，以及应急广播平台到广播电视频率频道播出系统、各类应急广播传输覆盖资源和终端之间传递的播发指令等相关数据。

应急广播消息包括应急广播信息主体文件、应急广播信息主体签名文件、应急广播节目资源文件、应急广播消息指令文件、应急广播消息指令签名文件。

3.2应急广播数字证书 emergency broadcasting certificate由数字证书签发编号和数字证书编号唯一标识,包括数字证书格式版本号、数字证书签发编号、数字证书编号、数字证书有效期、公钥信息、数字签名信息等，用于应急广播各级系统之间、系统与终端之间的认证。

3.3数字签名 digital signature附加在数据单元上的数据，或是对数据单元所作的密码变换，这种数据或变换允许数据单元的接收者用以确认数据单元的来源和完整性，并保护数据防止被人（例如接收者）伪造或抵赖。

3.4应急广播数字证书管理系统 emergency broadcasting certificate management systemGD/J 081—2018进行应急广播各级系统和接收端数字证书生成、发放和撤销的管理系统。

通用可复合的ElGamal型广播多重签密协议李建民;俞惠芳;谢永【摘要】多重签密是指2个以上参与方对同一则消息进行签密,并且要求签密结果不能因为签密者数目增多而呈线性增长.普通的ElGamal型多重签名虽然具有不可伪造性,但不能抵制多个签名者的联合攻击.为了克服现有ElGamal型多重签名的缺点,将ElGamal型多重签名和公钥签密组合在一起研究,提出了一种新的ElGamal 型广播多重签密(ElGamal broadcasting multi-signcryption,EBMSC)协议,并给出了该协议的算法定义和安全模型,也在随机预言模型中证明了该协议在离散对数和计算性Diffie-Hellman假设下是语义安全的;然后在通用可复合框架下定义了ElGamal型广播多重签密协议的理想函数和现实协议,进而证明了现实协议能够实现广播多重签密协议的理想功能,同时还证明了现实协议是满足选择消息攻击下的不可伪造性;最后给出了ElGamal型广播多重签密协议与其他协议的效率比较.结果表明:该协议不仅在效率上要优于现有方案,而且在通用可复合框架下实现了多重签密功能.该协议适合应用在电子商务、合同签署、网上交易和财务出账等方面.【期刊名称】《计算机研究与发展》【年(卷),期】2019(056)005【总页数】11页(P1101-1111)【关键词】ElGamal多重签名;ElGamal型广播多重签密;语义安全;随机预言模型;通用可复合安全【作者】李建民;俞惠芳;谢永【作者单位】青海省气象台西宁 810001;青海师范大学计算机学院西宁 810008;西安邮电大学通信与信息工程学院西安 710121;青海大学计算技术与应用系西宁810003【正文语种】中文【中图分类】TP309多重签名[1]是指2个以上的签名者对同一则消息进行签名,同时要求签名的长度不会因为签名者数目增多而呈线性增长,该类方案在电子商务领域被广泛应用.目前多重签名主要使用RSA(rivest shamir adleman)[2]、ElGamal[3-4]、双线性对[5]、离散对数[6-7]等思想来设计.1994年Harn[8]提出了Meta-ElGamal多重签名.1996年Wu等人[9]依据签名的签署顺序不同,将多重签名区分为顺序多重签名和广播多重签名.顺序多重签名意味着签名者必须按照特有的顺序依次对消息进行签名;广播多重签名是指签名者不必拘泥于固有的顺序,按广播的方式对消息进行签名,由收集者合并且输出签名.广播多重签名相比顺序多重签名应用更为广泛,ElGamal 型多重签名的安全性基于DL(discrete logarithm)问题的难解性,满足不可伪造性,缺点是不具备签名者的身份验证,不能抵制多个签名者的联合攻击. 1997年Zheng[10]提出了签密方案.签密方案相对于传统的签名方案而言,能够同时完成签名和加密2项功能.签名方案只是确保设计方案的不可伪造性,在安全性分析时,只要方案满足选择消息攻击的不可伪造性,那么就说设计的方案是语义安全的.签密方案能够在一个合理的逻辑步骤内同时完成签名和加密，在安全性分析时,不仅要分析方案的保密性,还要分析方案的不可伪造性.2002年Baek等人[11]对Zheng的签密方案进行了改进,同时给出了随机预言模型下的安全性证明.2011年Fan等人[12]改进了2002版本的签密方案,在Hash函数的输入中添加了接收方和发送方的公钥.近年来,越来越多的学者将签密和具有特殊性质的签名结合起来进行研究,使用不同的认证方法来认证用户公钥[13-19].2016年周才学[20]指出很多签密方案还存在安全问题,同时他认为在解签密算法的验证等式中不应出现明文信息,加密部分应该包含发送者的公钥或身份信息,签名部分应包含接收者的公钥或身份信息,在无证书密码体制的签名部分中不要让部分私钥和秘密值之间只是存在简单的线性关系.UC(universally composalble)安全框架[21]满足协议的模块化设计要求,可以单独用来设计协议.只要协议满足UC安全性,则可以保证和其他协议并发组合运行的安全性.设计一个UC安全协议,首先要将协议所希望完成的功能抽象为一个理想函数,该理想函数相当于现实世界中一个不可攻破的可信第三方.2003年Canetti等人[22]纠正了自己在2001年提出的签名理想函数的定义,通过添加SID(session identifier)来编码签名者的身份,允许被收买的签名者对合法的签名进行验证,对公钥、签名、验证消息进行储存;2007年Kristian等人[23]利用用户友好交互提出了一个安全消息传递理想函数,给出了签密的理想函数;2012年Canetti等人[24]提出了不经意传输(oblivious transfer, OT)协议的理想函数,同时给出了使用OT协议的双向认证协议的通用方法.国内对UC安全的研究也取得了一些成果,冯涛等人[25]利用可否认加密体制和可验证平滑投影Hash函数提出了一个UC安全的高效不经意传输协议;苏婷等人[26]基于密钥注册模型形式化定义了签密协议的安全模型(即签密协议的理想函数),设计了一般化的签密协议,给出了UC框架下的证明;张忠等人[27]形式化定义了信息处理集合和无线射频识别(radio frequency identification, RFID)组证明的理想函数,然后设计了一个组证明RFID协议,证明了该协议安全地实现了理想功能;田有亮等人[28]利用身份签密机制提出了一个UC安全的群通信协议,解决了多播群组通信的组合安全问题,之后,他们又设计了一个通用可组合的安全多方计算协议[29],即在UC框架下能实现公平的安全两方计算协议,使人们认为的两方公平安全计算不能实现的问题得到解决.本文结合自认证公钥和Meta-ElGamal多重签名协议的思想,在UC框架下设计了一个ElGamal型广播多重签密(ElGamal broadcasting multi-sign-cryption, EBMSC)协议,进而在UC安全框架下分析了该协议的安全性.也给出了ElGamal型广播多重签密协议的UC安全性证明.1 预备知识1.1 困难假设定义1. DL假设.设G是阶为素数p的循环群, g是G的一个生成元.已知(p,G,w),找到一个a∈Z使得w∈ga是困难的.定义2. CDH假设.设G是素数阶p的循环群,g是G的一个生成元.已知(ga,gb∈G*,其中a,b∈Z找到ga b∈G是困难的.1.2 UC安全框架UC安全框架是由现实模型、理想模型和混合模型组成.在UC框架中,用交互式图灵机(inter-active turing machine, ITM)来描述协议的参与方、敌手和环境机等实体.每个ITM的运行都被限定在概率多项式时间内.在现实模型中,包括了参与方P、敌手A、协议π和环境机Z等实体,参与方P不仅诚实地执行协议π,而且相互之间还可以直接通信.在理想模型中,包括了参与方P、模拟者S、理想函数F和环境机Z等实体.和现实模型不一样的是,参与方P相互之间不能直接通信,而是通过理想函数F来转发信息,现实模型和理想模型的外部环境Z相同.由于模块化的设计思想,只要证明某个协议能满足UC安全性,则和其他协议并发运行也能保证其安全性.定义3. 不可区分性[21].X和Y是2个不可区分的二元分布集合(记作X≈Y),如果任何c∈N都有k0∈N,使得所有k>k0和所有的a,都有:|Pr(X(k,a)=1)-Pr(Y(k,a)=1)|<k-c.定义4. UC仿真[21].设n∈N,令F是理想函数,π具有n个参与方的协议,τ是现实中某类敌手.若对任何现实攻击者A∈τ都存在一个理想过程中的敌手S,使得任何环境机Z都不能区分它是与(π,A)交互还是与(F,S)交互，则称π安全实现了F,记作: IDEAL F,S,Z≈REALπ,A,Z.定义5. 组合定理[21].令F和G是理想函数,π是F-混合模型下的一个协议,ρ协议在G-混合模型下可以安全地实现F.则对于任何敌手AG,都存在一个AF,使得对于任何环境机Z,都有:1.3 基于离散对数的多重签名回顾Harn[8]利用离散对数提出了一种有效的多重签名方案.假设n个签名者对同一消息m进行签名.1) 每一个签名者ui从[1,p-1]中随机选取ki,计算然后将ri广播给所有的签名者.一旦来自所有签名者的ri(i=1,2,…,n),汇聚在广播通道中,每一签名者计算r的值:2) 签名者ui用秘钥zi和ki对消息m运行签名算法.即si=(zi(m′+r)-ki) mod p,其中0≤si≤p-2和m′=f(m).签名者把元组(m,si)发送给消息收集者.3) 收集者收到来自各个ui的签名(m,si),验证这里m′=f(m)，yi是ui的公钥.4) 消息收集者将对通过验证的消息进行合并：s=(s1+s2+…+sn) mod p，得到完整的签名(r,s).5) 验证者计算公钥:6) 验证ym′+r=r αsmod p,这里m′=f(m).2 EBMSC协议的形式化定义2.1 EBMSC算法定义一个EBMSC协议由4个算法组成:参与方包括消息发起者或签密收集者UC、签密者U1,U2,…,Un、接收者UV.系统设置算法:输入安全参数1k,生成系统主密钥s和系统参数params.密钥提取算法:身份IDu的用户随机选择秘密钥生成其公钥yu,而密钥生成中心(key generator central, KGC)随机选择秘密钥ηu,然后根据用户身份IDu和公钥yu生成其部分私钥Tu,之后安全的形式发给用户.用户收到部分私钥Tu后,计算完整私钥xu.多重签密算法:输入系统的参数params、明文m、签密者Ui的私钥xi及接收者UV的公钥yV,输出多重签密密文σ.解签密算法:输入密文σ、参数params、签密者Ui的公钥yi及接收者UV的私钥xV,输出明文m或者解签密符号⊥.2.2 安全模型一个EBMSC协议有2类敌手,即A1和A2.敌手A1无法得到系统的主密钥,但是可以替换用户的公钥(敌手A1相当于模拟了不诚实的用户);敌手A2可以得到系统的主密钥,但不能替换用户的公钥(敌手A2相当于模拟了恶意的KGC).定义6. 如果存在任何多项式有界的敌手A1和A2赢得游戏IND-CCA2-I和IND-CCA2-II的优势是可忽略的,则称EBMSC 协议是具有适应性选择密文攻击下的不可区分性(indistinguishability against adaptive chosen ciphertext attacks, IND-CCA2).IND-CCA2-I:这是挑战者C和敌手A1之间的交互游戏.初始化.C运行系统设置算法得到系统参数params和系统主密钥s,之后将系统参数params发给A1,但保留主密钥s.阶段1. A1进行多项式有限次询问.公钥询问:当收到A1的公钥询问时,C运行密钥提取算法中的用户公钥生成算法得到yi,返回给A1.部分私钥提取询问:A1可以请求身份IDu的部分私钥询问,C运行密钥提取算法中的部分密钥生成算法得到Tu,之后把Tu返回给A1.私钥提取询问:A1可以请求身份IDu的私钥询问,C运行密钥提取算法中的私钥生成算法得到xu,之后把xu返回给A1.签密询问:A1收到(IDi,IDV,m)的签密询问时,C通过调用签密算法得到多重签密密文σ,之后将σ发给A1.解签密询问:A1收到(IDi,IDV,σ)时,C通过调用解签密算法得到的消息mi之后返给A1.挑战阶段.A1生成2个等长的消息(mo,m1)及2个身份但要求接收者的部分私钥不能被询问.C随机选择δ∈{0,1},然后执行对δ的多重签密,之后将δ*发给A1.阶段2. A1可以像阶段1那样进行多项式有界次询问,但仍然要求的私钥不能被询问,此外不能做σ*的解签密询问.最后,输出δ′={0,1}作为对δ的猜测.如果δ′=δ,则A1赢得游戏.IND-CCA2-II: 前面各阶段和敌手A1一样,只是敌手A2最后赢得游戏的条件是的私钥不能被询问,而且不能做σ*的解签密询问,除非接收者的公钥被替换.定义7. 如果存在任何多项式有界的敌手A1和A2赢得游戏UF-CMA-I和UF-CMA-II的优势是可忽略的,则称EBMSC协议是具有适应性选择消息攻击下的不可伪造性(unforgeability against adaptive chosen message attacks, UF-CMA). UF-CMA-I:C和伪造者A1之间的交互游戏.初始化. C运行系统设置算法得到系统参数params和系统主密钥s,之后将系统参数params发给A1,但保留主密钥s.训练. A1进行的多项式有界次询问和定义6中IND-CCA2-I的阶段1一样.伪造. 当询问结束后,A1输出伪造的多重签密密文询问期间,不能做的部分私钥询问.如果密文通过解签密验证,则定义A1在游戏中获胜.UF-CMA-II:C和伪造者A2之间的交互游戏.初始化. C运行系统设置算法得到系统参数params和系统主密钥s,之后将系统参数params发给A2,但保留主密钥s.训练. A2进行的多项式有界次询问和定义6中IND-CCA2-II游戏的阶段1一样. 伪造. 询问结束后,A2输出伪造多重签密密文询问期间,不能做的秘密钥询问.如果σ*通过解签密验证，则定义A2在游戏中获胜.3 一个具体的EBMSC协议3.1 初始化(Setup)密钥生成中心(KGC)随机选择大素数p,g是Z上阶为p的生成元.定义4个安全Hash函数H1:{0,1}*×ZZZZZZZ随机选择系统主密钥s∈Z计算系统公钥PPub=gsmod p.最后KGC保密系统主密钥s,公开系统参数(p,g,l,PPub,H1,H2,H3,H4).3.2 密钥生成(Extract)1) 用户Ui随机选择ki∈Z并进一步计算公钥之后返回给KGC.2) KGC选择ηi∈RZ计算mod p, Ti=(ηi+sH1(IDi,λi,yi)) mod (p-1)，将(λi,Ti)返回给用户Ui.3) 用户Ui验证 mod p, 如果等式成立,则Ui计算xi=kiTimod (p-1),并把xi作为其私钥.通过以上步骤,签密者Ui将得到公私钥(xi,yi),接收者UV将获得公私钥(xV,yV).3.3 广播多重签密(MultiSC)签密者Ui选择ri∈RZ计算然后广播给其他的签密者,通过下面步骤得到密文,并发送给签密收集者UC.2) h=H2(m,α).4) C i=m⊕H3(Wi).5) μi=H4(m,Ti,TV,Wi).6) βi=(ki(μi+Ti+h α)-ri) mod (p-1).7) 输出(αi,α,βi,h,Ti,TV,Ci),通过验证是否成立,若等式成立,则计算:8) 签密收集者UC将进一步输出签密密文σ=(α,βi,h,Ti,TV,{C1,C2,…,Cn}) 给接收者UV.3.4 解签密(USC)接收者UV收到签密密文σ后,执行步骤.2) m=Ci⊕H3(Wi).3) μi=H4(m,Ti,TV,Wi).4) 验证：其中,若等式成立,则接受明文m;否则,输出⊥符号表示广播多重签密无效.3.5 正确性分析可通过验证等式确保所提协议的正确性:3.6 ROM下的安全性分析3.6.1 保密性在随机预言模型(ROM)下的安全性分析,我们参考文献[18]的思路.定理1. 在ROM中,如果没有任何多项式有界的敌手A1能以不可忽略的优势ε赢得定义6中的游戏IND-CCA2-I(至多进行qi次Hi询问(i=1,2,3,4),qPK次公钥替换询问,qPSK次部分私钥提取询问,qSK次私钥提取询问,qSC次签密询问,qUSC次解签密询问),则存在一个挑战者C能至少以ε′的优势解决CDH问题,这里:证明. 给定一个随机的CDH问题实例(p,g,ga,gb),其中a,b∈Z目标为了计算ga b mod p.为了达到这个目标,A1作为C的子程序在交互游戏中充当敌手.游戏开始之时,C运行Setup(1k),得到参数:params={p,g,l,PPub=ga,H1,H2,H3,H4},同时将params发给A1.在交互游戏中,表L1到L4用于记录H1至H4的询问与应答值,Lk用于记录公私钥的询问与应答值.阶段1.A1进行多项式有界次适应性询问.H1询问:C从个身份q1中选择第i个身份作为挑战的目标身份,A1发出H1询问.如果A1向C询问的Hash函数值已经在L1中存在,则返回相应的值给A1;否则,C 选取ψ∈R{0,1}.如果ψ=1,则将(IDi,yi,-,ψ)记录到L1中;否则选择h1∈RZ返回将(IDi,yi,λi,h1,ψ)记录到L1表中.这里设ψ=0的概率是ρ,即ρ=Pr[ψ=0].H2询问:A1发出H2询问时.C检查元组(m,α,h2)是否存在于L2,如果存在,则返回h2;否则,C随机选取h2∈Z然后将h2发给A1,并将(m,α,h2)记录到L2中.H3询问:A1发出H3询问.C检查元组(Wi,h3)是否存在于L3表中,如果存在,则返回h3;否则,C随机选取h3∈R{0,1}l,然后将h3发给A1,记录(Wi,h3)到L3中.H4询问:A1发出H4询问时,检查元组(m,Ti,TV,Wi,μ)是否存在于L4中,如果存在,则返回μ;否则,C选取h4∈RZ然后将h4发给A1,记录(m,Ti,TV,Wi,μ)到L4中.公钥询问:收到A1公钥询问时,C随机选择ki,并计算公钥之后将其添加到Lk表中. 部分私钥询问:A1询问身份IDi的部分私钥.若ψ=0,则C选择Ti∈Z将(IDi,Ti,ψ)记录到L1中,并返回Ti;否则,放弃仿真.私钥询问:A1询问身份IDi的私钥.假设已经询问过H1预言机.若ψ=0,则返回完整私钥xi=kiTimod p;否则,放弃仿真,之后将私钥添加到Lk中.公钥替换询问:A1对身份IDi进行公钥替换询问时.C用来替换Lk中的原有记录. 多重签密询问:A1可对任何消息m及签密人的身份IDi、接收者的身份IDV进行签密询问.假设在此之前已经做过Hash函数值询问和密钥提取询问.如果ψ=0,则正常执行多重签密算法;否则执行操作:1) 挑战者C选择ri∈RZ计算:继续执行操作:2) 计算3) 计算Ci=m⊕H3(Wi).4) 计算μi=H4(m,TV,Ti,Wi).5) 计算βi=(ki(μi+Ti+h α)-ri) mod (p-1).验证：是否成立.如果成立,则计算:6) 计算7) 输出σ=(α,β,h,Ti,TV,{C1,C2,…,Cn}).解签密询问:A1通过提供的多重签密密文,当A1询问σ是否合法时,挑战者C先从表中查找出记录yi,再查找表L1.如果ψ=0,则正常执行解签密算法;否则,挑战者C 计算⊕H3(Wi),μi=H4(m,TV,Ti,Wi),然后将(Wi,m)提交给预言机.如果:则通过解签密;否则认为不合法.挑战阶段.通过上面的询问过后,如果ψ=0.则放弃仿真;否则挑战者C随机选择δ={0,1},计算⊕然后提交多重签密密文阶段2. A1可以像阶段1那样进行多项式有界次适应性询问.但是要求身份IDV的私钥仍然不能被询问,此外不能做σ*的解签密询问.猜测.最后,输出δ′={0,1},用δ′作为对δ的猜测.如果δ′=δ,那么C计算输出作为CDH问题实例的解答,原因如下:概率分析[14]在阶段1或阶段2挑战者C不放弃仿真的概率是即在密钥提取阶段,至少有一个身份IDV的私钥xV没被A1询问,C不放弃游戏的概率为1e(qSK+qPSK),同时,A1对做H3询问的概率为1q3,那么C将成功.所以C解决CDH问题的概率是证毕.定理2. 在ROM中,如果没有任何多项式有界的敌手A2能以不可忽略的优势ε赢得定义6中的游戏IND-CCA2-Ⅱ(至多进行qi次Hi询问(i=1,2,3,4),qPK次公钥替换询问,qSK次私钥提取询问,qSC次签密询问,qUSC次解签密询问),则存在一个挑战者C能够至少以ε′的优势解决CDH问题,这里:证明. 给定一个随机的CDH问题实例(p,g,ga,gb),其中a,b∈Z目标为了计算ga b mod p.为了达到这个目的,A2作为C的子程序,在交互游戏IND-CCA2-II中充当敌手.游戏开始后,C运行Setup(1k),得到参数:params={p,g,l,PPub=gs,H1,H2,H3,H4},同时将params发给A2.在游戏中,表L1到L4用于记录H1至H4的询问与应答值,Lk用于记录公私钥的询问与应答值.阶段1.除了部分私钥询问,其他询问同定理1.挑战阶段. 通过上面的询问过后,若ψ=0.则放弃游戏;否则挑战者C随机选择δ∈{0,1},计算,yi=ga,⊕返回密文阶段2. A2可以像阶段1那样进行多项式有界次适应性询问.但是要求身份为IDV 的私钥仍然不能被询问,并且不能做关于σ*的解签密询问.猜测. 最后,输出δ′∈{0,1},用δ′作为对δ的猜测.如果δ′=δ,那么挑战者C计算即C 输出作为CDH问题实例的应答,因为:⟺⟺概率分析在阶段1或阶段2挑战者C不放弃仿真的概率是因为不进行部分私钥询问，即C不放弃游戏的概率为1e(qPK+qSK),同时,A1对做H3询问的概率为1q3,那么C将成功.所以C解决CDH问题的概率是证毕.3.6.2 不可伪造性定理3. 如果任何多项式有界的敌手A1和A2赢得定义7中的游戏UF-CMA-I和UF-CMA-II的优势是可忽略的,则EBMSC协议具有适应性选择消息攻击下的不可伪造性(至多进行qi次Hi询问(i=1,2,3,4),qPK次公钥替换询问,qPSK次部分私钥提取询问,qSK次私钥提取询问,qSC次签密询问,qUSC次解签密询问),在UF-CMA-I中,则存在一个挑战者C至少能够以的优势解决离散对数问题;在UF-CMA-II中,则存在一个挑战者C至少能够以的优势解决离散对数问题.证明. 给定一个随机的离散对数问题实例(p,g,ga)，目标为了计算a∈Z为了达到这个目的,A1作为挑战者C的子程序,在交互游戏UF-CMA-I中充当敌手,C充当敌手A1的挑战者.在交互游戏开始之时,游戏开始后,C运行Setup(1k),得到参数:params={p,g,l,PPub,H1,H2,H3,H4},并将params发给A1.在游戏中,表L1到L4记录H1至H4的预言机,Lk用于追踪公私钥的询问与应答值.询问阶段.和定理1相同.伪造. 对于不同的敌手伪造的过程不一样.1) A1输出一个伪造的广播多重签密密文σ*.如果A1没做过身份的私钥或部分私钥询问,σ*通过解签密验证,则A1赢得定义7中UF-CMA-I.设A1输出有效的伪造广播多重签密密文计算:①② PPub=ga.调用预言机H1可以得到h1,输出:作为离散对数问题实例的解答,原因如下:⟺⟺分析C成功解决离散对数问题的概率,A1没做过IDi的私钥或部分私钥询问的概率为通过解签密验证的概率为1qUSC,所以C解决离散对数问题的概率为ε′,这里:2) A2输出有效的伪造广播多重签密密文σ*.如果A2没有做过的私钥询问,同时σ*通过解签密验证,则A2赢得定义7中UF-CMA-II.设A2输出有效的伪造广播多重签密密文这里:①②③ yi=gamod p.分别调用预言机H2和H4得到h和h4.C输出:作为离散对数问题实例的应答,因为:⟺⟺分析C成功解决离散对数问题的概率,A2没有作过私钥询问的概率为1e qSK,σ*通过解签密验证的概率为1qUSC,所以C解决离散对数问题的概率为ε′,这里:证毕.4 EBMSC协议的UC安全性分析4.1 理想函数FEBMSC理想模型中,EBMSC协议的理想函数FEBMSC、参与方P1,P2,…,Pn及敌手S一起运行,执行过程如下:① 在收到(KGC,Setup,sid)请求后验证,若验证sid=(KGC,sid′)成功,则将此消息发送给敌手S.② 在收到敌手S回复的(Setup,Verify,sid,params)后,记录下Verify.③ 在收到Pi的(Key,sid,Pi)请求后,验证sid=(Pi,sid′),若验证成功,则将此消息发送给敌手S,然后收到敌手S回复的(Pi,sid,yi).④ 在收到PV的(Key,sid,PV)请求后,验证sid=(PV,sid′),若验证成功,则将此消息发送给敌手S.在收到敌手S回复的yV后,将yV发送给Pi.一旦收到来自Pi的消息(Key,sid,PV),则将此消息发送给敌手S,从敌手S处收到yi时,将yi发送给PV.之后,忽略所有的(Key,sid,PiPV).⑤ 在收到Pi多重签密者的请求后,验证sid=(Pi,sid′),若验证不成功,则将忽略发送过来的消息;否则,执行如下:如果同时参与方PV是诚实的,则发送(MultiSC,sid,|m|)给敌手S,这里|m|是消息长度;否则,发送(MultiSC,sid,m)给敌手.当从敌手S处收到σ时,将(MultiSC,sid,m,σ)给PV,并存储(m,σ).⑥ 在收到接受者PV的(USC,sid,σ,yi)请求后,验证sid=(PV,sid′),若验证不成功,则将忽略发送过来的消息;否则,执行如下:如果(m,σ)已经记录过,则验证Verify((params,sid,m,σ),f=1),并把(m,f)发给S.否则,将(USC,sid,σ,yi)发给敌手S,并从敌手S处得到m,并以(m,f=0)的形式发送给PV.4.2 协议πEBMSC下面是设计的ElGamal型广播多重签密协议πEBMSC=(Setup,Extract,MultiSC,USC),在UC框架下该协议运行如下:① 一旦收到(KGC,Setup,sid)消息请求,则验证sid=(KGC,sid′),运行Setup(1k)得到(s,params),返回参数params.② 收到(U,Key,sid),运行Extract(params,s,ID),得到(xID,yID),然后将(xID,yID)返回.③ 收到(MultiSC,m,yV,sid)消息请求后,运行MultiSC(params,m,xi,yV)→σ,并将σ返回.④ 收到(USC,sid,σ),运行USC(params,m,yi,xV),得到消息m,若收到(Verify,sid,m,σ)请求,则运行Verify(params,sid,m,σ)→f,并返回f的值.4.3 UC框架下协议的安全性证明定理4. 协议πEBMSC实现了广播多重签密理想函数FEBMSC.证明. 假设A为现实模型中的敌手.现在构造一个理想敌手S,使得对于任何环境机Z 都不能区分是与FEBMSC和S在理想模型下的交互,还是与πEBMSC和A在现实过程中的交互.理想敌手S、环境机Z、敌手A以及参与方P1,P2,…,Pn一起运行. 构造敌手S:在理想过程中,敌手S可以调用A的副本来与FEBMSC和S交互,模拟A在现实过程与协议πEBMSC的交互.首先,敌手S把输出带上的内容写到A的输入带上,并把A输出带的内容拷贝到Z的输出带上.模拟签密者Pi和接收者PV都不被入侵.当S收到FEBMSC的消息(Setup,sid),运行Setup算法生成公钥yV,并把消息(Verify,v)输出给FEBMSC.当S收到来自FEBMSC的一个消息(MultiSC,sid,m),运行多重签密算法MultiSC,得到签密σ并把(MultiSC,sid,m)输出给FEBMSC.当S收到来自FEBMSC的一个消息(Verify,sid,m,σ,v′)后,运行验证签名算法Verify,得到验证结果f,把(Verify,sid,m,f)输出给FEBMSC.现实环境下签密者对消息进行签密,并将签密结果发送给接收者.接收者验证签密的有效性.理想环境中仿真器S对真实过程进行仿真,仿真签密过程和验证过程,同样发送签密和验证结果,因而,环境机Z不能区分出是FEBMSC与S在理想模型中的交互,还是πEBMSC与A在现实过程中的交互.模拟签密者Pi被入侵.敌手S模拟A伪装成参与方Pi把(Setup,sid)发送给FEBMSC.同样,当S收到来自FEBMSC的消息(Extract,sid)后.运行密钥生成算法Setup,得到签密者公钥yi并将其返回给FEBMSC.当S收到来自FEBMSC的消息(MultiSC,sid),运行多重签密算法,得到密文并将其返回给FEBMSC.S模拟A入侵参与方Pi,并将(MultiSC,sid,m′)发送给FEBMSC.同样,当S接收到(MultiSC,sid,m′)时,可以得到多重签密σ′,即把(MultiSC,sid,m′,σ′)发送给FEBMSC.由此看来,环境Z 并不能区分现实过程和理想模型.模拟接收者PV被入侵.若参与方PV被收买,敌手S可以模拟参与方的身份把(Verify,sid,m′,σ′,v′)发送给FEBMSC,随后,当S接收到(Verify,sid,m′,σ′,v′)时,计算验证结果f,把(Verify,sid,m′,σ′,v′,f) 发送给FEBMSC.此时,环境机Z不能区分(m,σ)与(m′,σ′).模拟签密者Pi和接收者PV都被入侵.当多重签密者Pi和解签密者PV都被攻陷时,S将获得双方的所有输入信息,即Z可产生真实的数据来仿真协议的运行.综合上述4种情形,环境机Z不能区分出是FEBMSC与S在理想模型中的交互,还是πEBMSC与A在现实过程中的交互.即协议πEBMSC能够实现广播多重签密理想函数FEBMSC.证毕.定理5. 在UC安全框架下,协议πEBMSC满足选择消息攻击下的不可伪造性.证明. 假设存在伪造者F,则构造环境机Z和敌手A,使得对于任何敌手A,Z都以不可忽略的概率区分它是与(πEBMSC,A)交互还是与(FEBMSC,S)交互.构造环境机Z.当收到来自A的多重签密请求时,则Z激活Pi,然后输出多重签密密文σ,并返回给A.当收到来自A的解签密请求时,Z激活Pi,并输出(m,f)给A.构造敌手A.当A要求对消息m进行多重签密时,敌手A首先要求环境机Z对m进行多重签密,然后把多重签密密文σ给F;当F需要对σ′解签密时,敌手A首先要求环境机Z对σ′进行解签密,然后把(m′,f)返回给A,再发给伪造者F.一旦F收到了m′,并且f=1,则F伪造的多重签密是有效的,此时,Z输出f=1.显然,如果F以可忽略的概率赢得了定理3中的UF-CMA-I和UF-CMA-II游戏,则F能够成功地伪造出有效的F, 假设伪造者F以可忽略的概率存在,则Z以可忽略的概率输出f=1.而在理想模型。

使用阈下信道的可逆R-S数字水印
赵险峰;李宁;黄炜
【期刊名称】《计算机研究与发展》
【年(卷),期】2009(046)001
【摘要】由于难以获得足够的冗余水印容量,一些面向内容认证的可逆水印方案仅嵌入了用对称算法加密的杂凑值,它的数据尺寸显著地小于数字签名,但这使不诚实的验证者能伪造合法的内容.然而研究发现,虽然当前公钥签名的长度是杂凑值的数倍,但通过使用阈下信道,在方案中引入公钥签名仅需增加数个字节的容量.据此,一个改进的R-S(regular-singular)可逆数字水印方案被提出,它采用RSAPSS公钥签名,并利用签名中阈下信道存储部分或全部压缩的R-S向量.该方案仅需增加4个字节的额外水印容量,也具有篡改定位功能和可靠的安全性.
【总页数】8页(P100-107)
【作者】赵险峰;李宁;黄炜
【作者单位】中国科学院软件研究所信息安全国家重点实验室,北京,100190;中国科学院软件研究所信息安全国家重点实验室,北京,100190;中国科学院软件研究所信息安全国家重点实验室,北京,100190
【正文语种】中文
【中图分类】TP309
【相关文献】
1.基于可逆数字水印认证的无线传感网数据融合协议 [J], 蒋文贤;张振兴;吴晶晶
2.双层差值扩展可逆数字水印算法 [J], 苏文桂;沈玉龙;王祥
3.基于DCT-SVD和标记矩阵的鲁棒可逆数字水印算法 [J], 阮涛;张学波
4.应用可逆数字水印的无线传感器网络层级安全模型 [J], 蒋建峰;尤澜涛
5.ε~λ（R－ε_CT_Hσ）最大时不可逆卡诺制冷机的ε、R [J], 解文方
因版权原因，仅展示原文概要，查看原文内容请购买。

信息隐藏技术及应用-标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII信息隐藏技术及应用1什么是信息隐藏信息隐藏(InformatiOn Hiding)：主要研究如何将某一机密信息秘密(Secret Message)隐藏于另一公开的信息(载体、宿主)中，然后通过公开信息的传输来传递机密信息。

第三方则难以从公开信息中判断机密信息是否存在，难以截获机密信息，从而能保证机密信息的安全。

信息隐藏学是一门新兴的交叉学科，在计算机、通讯、保密学等领域有着广阔的应用前景。

信息隐藏是上世纪90年代开始兴起的信息安全新技术，并成为信息安全技术研究的热点；传统通信领域为了保证传递的信息能够不被窃听或破坏，常采用密码来保护信息，即让窃听者无法看到或听懂，但是这种技术的缺点是告诉窃听者这就是秘密信息，特别是随着计算机技术的发展，密码的安全性受到很大挑战。

而新的信息隐藏技术是将需要传递的秘密信息，隐藏在一个普通的非秘密消息当中，再进行传输，这样即使窃听者窃听了传输的信息，也只会将其当成普通的消息，而不会怀疑或者无法得知是否有秘密信息的存在。

一般而言，信息隐藏是分为四个阶段：预处理阶段、嵌入阶段、传输阶段和提取阶段。

为了使每个阶段都达到安全，所以必须在预处理阶段，引入加密术中的加密算法。

在嵌入阶段，使用基于小波的隐藏信息的算法，在传输阶段，进行隐蔽通信，从而使用传输阶段也是安全的。

所以这套信息隐藏的处理方案，将形成一个安全的体系，因此既能隐藏秘密信息的内容，也能隐蔽通信的接收方和发送方，从而建立隐藏通信。

信息隐藏的原理如图1。

信息隐藏技术的分类见图2。

信息隐藏不同于传统的加密，传统的加密是研究如何将机密信息进行特殊的编码，以形成不可识别的密码形式进行传递，它仅隐藏了信息的内容；而信息隐藏不但隐藏了信息的内容，而且隐藏了信息的存在。

根据信息隐藏的目的和技术要求，该技术存在以下特性：鲁棒性(Robustness)：指不因图像文件的某种改动而导致隐藏信息丢失的能力。

第５０卷第４期２０２０年７月　东南大学学报（自然科学版）ＪＯＵＲＮＡＬＯＦＳＯＵＴＨＥＡＳＴＵＮＩＶＥＲＳＩＴＹ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）Ｖｏｌ．５０Ｎｏ．４Ｊｕｌｙ２０２０ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１００１－０５０５．２０２０．０４．０１８可证安全的无证书多消息同步广播签密方案方光伟１，２　曹玖新１（１东南大学网络空间安全学院，南京２１１１８９）（２宜春学院数学与计算机科学学院，宜春３３６０００）摘要：针对现有多接收者签密方案中只能对单消息加密与密文难以定位等问题，需要进一步研究实现发送者在一个逻辑步骤中签密不同的消息，并同步安全广播给多个接收者的功能，基于椭圆曲线加密机制，提出了一种无证书多接收者多消息同步广播签密方案．该方案以每个接收者的身份标识作为输入，产生拉格朗日插值多项式系数向量，结合随机数生成密文索引，解决了接收者密文定位问题；结合椭圆曲线循环群上随机元素生成加密密钥，解决了接收者解密密文和身份匿名保护问题．在随机谕言机模型下，基于计算性Ｄｉｆｆｉｅ Ｈｅｌｌｍａｎ假设和椭圆曲线离散对数假设，证明了该方案满足机密性和不可伪造性．性能和效率分析表明，在未降低计算效率和通信效率的同时，该方案是安全性能和完整程度最优的方案．关键词：可证安全；无证书签密；多消息；拉格朗日插值；椭圆曲线中图分类号：ＴＰ３０９．７ 文献标志码：Ａ 文章编号：１００１－０５０５（２０２０）０４ ０７２８ １３Ｐｒｏｖａｂｌｙｓｅｃｕｒｅｃｅｒｔｉｆｉｃａｔｅｌｅｓｓｍｕｌｔｉ ｍｅｓｓａｇｅｓｙｎｃｈｒｏｎｏｕｓｂｒｏａｄｃａｓｔｓｉｇｎｃｒｙｐｔｉｏｎｓｃｈｅｍｅＦａｎｇＧｕａｎｇｗｅｉ１，２　ＣａｏＪｉｕｘｉｎ１（１ＳｃｈｏｏｌｏｆＣｙｂｅｒＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＳｏｕｔｈｅａｓｔＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ２１１１８９，Ｃｈｉｎａ）（２ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＹｉｃｈｕｎＵｎｉｖｅｒｓｉｔｙ，Ｙｉｃｈｕｎ３３６０００，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｉｎｖｉｅｗｏｆｔｈｅｅｘｉｓｔｉｎｇｍｕｌｔｉ ｒｅｃｉｐｉｅｎｔｓｉｇｎｃｒｙｐｔｉｏｎｓｃｈｅｍｅ，ｗｈｉｃｈｃａｎｏｎｌｙｅｎｃｒｙｐｔｓｉｎｇｌｅｍｅｓｓａｇｅａｎｄｃｉｐｈｅｒｔｅｘｔｉｓｄｉｆｆｉｃｕｌｔｔｏｌｏｃａｔｅ，ｉｔｉｓｎｅｃｅｓｓａｒｙｔｏｆｕｒｔｈｅｒｓｔｕｄｙｔｈｅｒｅａｌｉｚａｔｉｏｎｔｈａｔｔｈｅｓｅｎｄｅｒｓｉｇｎｓａｎｄｅｎｃｒｙｐｔｓｄｉｆｆｅｒｅｎｔｍｅｓｓａｇｅｓｉｎｏｎｅｌｏｇｉｃａｌｓｔｅｐ，ａｎｄｓｉｍｕｌｔａｎｅｏｕｓｌｙａｎｄｓａｆｅｌｙｂｒｏａｄｃａｓｔｓｔｏｍｕｌｔｉｐｌｅｒｅｃｅｉｖｅｒｓ．Ｂａｓｅｄｏｎｔｈｅｅｌｌｉｐｔｉｃｃｕｒｖｅｅｎｃｒｙｐｔｉｏｎｍｅｃｈａｎｉｓｍ，ａｃｅｒｔｉｆｉｃａｔｅｌｅｓｓｍｕｌｔｉ ｒｅｃｅｉｖｅｒｍｕｌｔｉ ｍｅｓｓａｇｅｓｉｍｕｌｔａｎｅｏｕｓｂｒｏａｄｃａｓｔｓｉｇｎｃｒｙｐｔｉｏｎｓｃｈｅｍｅｉｓｐｒｏｐｏｓｅｄ．Ｔａｋｉｎｇｔｈｅｉｄｅｎｔｉｔｙｏｆｅａｃｈｒｅｃｅｉｖｅｒａｓａｎｉｎｐｕｔ，ｔｈｉｓｓｃｈｅｍｅｇｅｎｅｒａｔｅｓａＬａｇｒａｎｇｅｉｎｔｅｒｐｏｌａｔｉｏｎｐｏｌｙｎｏｍｉａｌｃｏｅｆ ｆｉｃｉｅｎｔｖｅｃｔｏｒ，ａｎｄｇｅｎｅｒａｔｅｓａｃｉｐｈｅｒｔｅｘｔｉｎｄｅｘｉｎｃｏｍｂｉｎａｔｉｏｎｗｉｔｈａｒａｎｄｏｍｎｕｍｂｅｒ，ｗｈｉｃｈｓｏｌｖｅｓｔｈｅｒｅｃｅｉｖｅｒｃｉｐｈｅｒｔｅｘｔｐｏｓｉｔｉｏｎｉｎｇｐｒｏｂｌｅｍ．Ｃｏｍｂｉｎｅｄｗｉｔｈｒａｎｄｏｍｅｌｅｍｅｎｔｓｉｎａｎｅｌｌｉｐｔｉｃｃｕｒｖｅｃｙ ｃｌｉｃｇｒｏｕｐ，ｔｈｅｅｎｃｒｙｐｔｉｏｎｋｅｙｉｓｇｅｎｅｒａｔｅｄ，ｗｈｉｃｈｓｏｌｖｅｓｔｈｅｐｒｏｂｌｅｍｓｏｆｒｅｃｅｉｖｅｒｄｅｃｒｙｐｔｉｏｎｃｉｐｈｅｒ ｔｅｘｔａｎｄｉｄｅｎｔｉｔｙａｎｏｎｙｍｉｔｙｐｒｏｔｅｃｔｉｏｎ．Ｕｎｄｅｒｔｈｅｒａｎｄｏｍｏｒａｃｌｅｍｏｄｅｌ，ｂａｓｅｄｏｎｃｏｍｐｕｔａｔｉｏｎａｌＤｉｆ ｆｉｅ Ｈｅｌｌｍａｎｈｙｐｏｔｈｅｓｉｓａｎｄｅｌｌｉｐｔｉｃｃｕｒｖｅｄｉｓｃｒｅｔｅｌｏｇａｒｉｔｈｍｈｙｐｏｔｈｅｓｉｓ，ｉｔｉｓｐｒｏｖｅｄｔｈａｔｔｈｅｓｃｈｅｍｅｍｅｅｔｓｃｏｎｆｉｄｅｎｔｉａｌｉｔｙａｎｄｕｎｆｏｒｇｅａｂｉｌｉｔｙ．Ｔｈｅｐｅｒｆｏｒｍａｎｃｅａｎｄｅｆｆｉｃｉｅｎｃｙａｎａｌｙｓｉｓｓｈｏｗｓｔｈａｔｔｈｅｐｒｏ ｐｏｓｅｄｓｃｈｅｍｅｉｓｔｈｅｏｎｅｗｉｔｈｔｈｅｂｅｓｔｓｅｃｕｒｉｔｙｐｅｒｆｏｒｍａｎｃｅａｎｄｉｎｔｅｇｒｉｔｙｗｉｔｈｏｕｔｒｅｄｕｃｉｎｇｔｈｅｃｏｍｐｕ ｔａｔｉｏｎａｌｅｆｆｉｃｉｅｎｃｙａｎｄｃｏｍｍｕｎｉｃａｔｉｏｎｅｆｆｉｃｉｅｎｃｙ．Ｋｅｙｗｏｒｄｓ：ｐｒｏｖａｂｌｅｓｅｃｕｒｉｔｙ；ｃｅｒｔｉｆｉｃａｔｅｌｅｓｓｓｉｇｎｃｒｙｐｔｉｏｎ；ｍｕｌｔｉ ｍｅｓｓａｇｅ；Ｌａｇｒａｎｇｅｉｎｔｅｒｐｏｌａｔｉｎｇ；ｅｌｌｉｐｔｉｃｃｕｒｖｅ收稿日期：２０１９ ０９ ０６．　作者简介：方光伟（１９７４—），男，副教授，ｆａｎｇｇｗ＠２６３．ｎｅｔ．基金项目：国家自然科学基金资助项目（６１６６２０８３）．引用本文：方光伟，曹玖新．可证安全的无证书多消息同步广播签密方案［Ｊ］．东南大学学报（自然科学版），２０２０，５０（４）：７２８７４０．ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１００１－０５０５．２０２０．０４．０１８． 机密性和不可伪造性是网络安全通信的基本需求，加密明文可实现通信的机密性，数字签名可实现通信的不可伪造性．传统方式将签名和加密作为２个过程单独处理，即先签名后加密，这种方式存在计算和通信开销较大的缺点．文献［１］提出了签密密码原语，将签名和加密２个功能融合在一个逻辑步骤中完成，克服了传统方式的缺点，有效提高了计算和通信的效率．广播和组播是计算机网络中一种重要的通信方式，发送者需要将一个或多个消息同时传输给多个接收者．把签密应用于广播安全通信环境，Ｄｕａｎ等［２］２００６年提出了多接收者签密概念．用签密者的私钥和接收者的公钥对待发送的信息进行签密；把签密密文广播给授权的接收者；接收者用自己的私钥进行解密并用签密者的公钥验证密文的合法性；验证通过则接收解密信息，否则拒绝．相较于一对一签密方案，除了保证方案机密性和不可伪造性之外，对发送者和接收者身份信息的匿名保护是多接收者签密方案中一个重要的安全需求．信息的发送者不希望自己的身份信息暴露给非授权的用户，对信息的接收者而言，自己的身份信息和订阅的某种网络服务更不能泄漏给除发送者之外的其他用户，哪怕是授权接收列表中的其他成员．多接收者签密概念提出后，由于其应用前景广阔，国内外学者对此进行了深入研究，相继提出了许多解决方案［２１８］．文献［２］是一个基于身份密码体制的多接收者签密方案，密文向量应由密文、签名和接收者列表组成．但该方案密文向量缺失了接收者信息列表，导致接收者实际上无法对接收的密文进行解密［３］．Ｙｕ等［３］改进了文献［２］的签密方案，补充了接收者身份列表信息，并且计算效率也更高．文献［４］是应用于移动网络场景的多接收者加密方案，方案的计算效率高且通信负载低，但该方案只有加密功能，因此接收者不能对消息的来源进行认证．文献［５］利用双线性对构造了一个基于身份的多接收者签密方案，该方案双线性对计算次数较多，计算工作量太大．文献［６］利用拉格朗日插值多项式构造了基于身份的双线性对多接收者匿名签密方案，密文无需添加接收者身份列表，声称任何攻击者（包括授权的接收者）无法获取接收者的身份信息．然而文献［７］安全分析表明文献［６］中授权的接收者身份信息无法实现匿名，并给出了改进方法和接收者匿名性的安全证明．文献［８］提出了标准模型下基于身份的无证书多接收者签密方案，虽然标准模型的安全性不依赖于随机谕言机，但这种可证安全性是以严重牺牲效率为代价［１９］，制约了其实际应用．文献［９］基于ＤＤＨ（Ｄｅ ｃｉｓｉｏｎＤｉｆｆｉｅ Ｈｅｌｌｍａｎ）困难问题设计了一个无证书的多接收者签密方案，方案无需双线性对运算，具有较高的计算效率．文献［１０］借鉴文献［６］中利用拉格朗日插值多项式保护接收者匿名性的思想，构造了一个高效无证书多接收者的签密方案，由于文献［７］证明了文献［６］不具有接收者匿名性这一安全属性，因此文献［１０］同样不能实现接收者的匿名性．文献［１１］提出了一个基于身份的多接收者（多消息）匿名混合签密方案，声称方案满足机密性和不可伪造性的同时，对发送者具有强匿名性，即通过构造发送者身份伪装集合，密文授权接收者无法准确定位发送者的具体身份，但本文分析表明该方案不具有发送者强匿名性．文献［１２１３］是基于乘法群上离散对数问题的多接收者多消息签密方案，文献［１２］在随机谕言机模型下证明了方案满足机密性和不可伪造性，然而文献［１３］指出了文献［１２］中存在发送者私钥泄漏问题，并针对密钥泄漏问题提出了改进措施．文献［１４１５］尽管实现了广播环境下多接收者多消息的发送需求，但方案无法满足收发双方的匿名保护．文献［１６］提出了一个满足广播通信环境下多消息匿名发送需求的无证书签密方案，该方案中接收者的匿名性通过定义单向索引函数ｆＩｎｄｅｘ来实现，但并未给出ｆＩｎｄｅｘ的实现细节，而且ｆＩｎｄｅｘ的输出空间为接收者人数，接收者人数不是一个很大的值，因此ｆＩｎｄｅｘ不满足单向函数的定义，该方案是一个不完善的方案．综上所述，现有解决广播环境下多接收者签密方案［２１８］还存在以下不足：①发送者和接收者的匿名性问题，如文献［２３，５］在密文中直接包含接收者身份信息；②密钥托管问题，在基于身份的密码体制中，用户私钥由密钥生成中心（ｋｅｙｇｅｎｅｒａ ｔｏｒｃｅｎｔｅｒ，ＫＧＣ）生成，因此存在密钥托管问题［３８，１１，１７１８］；③只具有单消息签密功能［２１０，１７１８］，即签密者只能将单个消息签密后广播给多个接收者，如果需要将多个消息同步广播给多个接收者时，则必须回归传统的一对一签密，计算工作量非常大，效率低；④方案的完善程度及其他问题［４，９１０，１２１６］．针对现有方案的不足，本文基于无证书密码体制（ＣＬ ＰＫＣ）提出了一个多接收者多消息同步广播签密方案，消息发送者通过一个逻辑步骤完成ｎ个消息的签密并同步广播给ｎ个接收者．方案借鉴９２７第４期方光伟，等：可证安全的无证书多消息同步广播签密方案ｈｔｔｐ：／／ｊｏｕｒｎａｌ．ｓｅｕ．ｅｄｕ．ｃｎｈｔｔｐ：／／ｊｏｕｒｎａｌ．ｓｅｕ．ｅｄｕ．ｃｎ了文献［６］中利用拉格朗日插值多项式实现接收者匿名的思想，但与文献［６］不同的是，本文方案利用拉格朗日插值多项式计算椭圆曲线群上的一个随机元素，因此文献［７］中对接收者匿名性攻击方法对本文方案无效，即本文方案有效解决了接收者隐私保护问题；另外本文方案基于椭圆曲线密码体制，没有使用双线性对和指数运算，计算效率更高；最后在随机谕言机模型下证明了方案满足机密性和不可伪造性．１　困难问题和安全模型１．１　困难问题定义１（离散对数问题（ＤＬＰ））　设Ｇ为椭圆曲线上阶为大素数ｑ的循环群，Ｐ是Ｇ上的生成元，Ｚｑ是阶为ｑ的有限域；算法Ｆ随机选择群中元素ａＰ∈Ｇ（ａ∈Ｚ ｑ且未知），Ｆ的目标是计算ａ；对于任意的概率多项式时间算法Ｆ成功解决ＤＬＰ问题概率ε＝Ｐｒ［Ｆ（Ｐ，ａＰ）＝ａａ∈Ｚ ｑ］是可忽略的．定义２（计算性Ｄｉｆｆｉｅ Ｈｅｌｌｍａｎ问题（ＣＤＨ））　设Ｇ为椭圆曲线上阶为大素数ｑ的循环群，Ｐ是Ｇ上的生成元，Ｚｑ是阶为ｑ的有限域；算法Ｆ随机选择群中元素ａＰ，ｂＰ∈Ｇ（ａ，ｂ∈Ｚ ｑ且未知），Ｆ的目标是计算ａｂＰ；对于任意的概率多项式时间算法Ｆ成功解决ＣＤＨ问题概率ε＝Ｐｒ［Ｆ（Ｐ，ａＰ，ｂＰ）＝ａｂＰａ，ｂ∈Ｚｑ］是可忽略的．１．２　算法通信模型本文无证书多接收者多消息同步广播签密算法模型同文献［２］中方案类似，由４个算法组成：系统参数建立算法（Ｓｅｔｕｐ）、用户密钥生成算法（ＫｅｙＧｅｎ）、多消息匿名签密算法（ＭＡＳｉｇｎｃｒｙｐｔ）和解签密算法（ＵｎＳｉｇｎｃｒｙｐｔ）．１）Ｓｅｔｕｐ：该算法由ＫＧＣ执行，ＫＧＣ输入安全参数（１λ），生成系统公开参数ｐａｒａｍｓ和主密钥ｓ，秘密保存主密钥ｓ，公开发布系统参数ｐａｒａｍｓ．２）ＫｅｙＧｅｎ：该算法由ＫＧＣ和用户合作完成，输入用户身份标识ＩＤｉ、系统主密钥ｓ和系统公开参数ｐａｒａｍｓ，输出用户的公钥和私钥，即（ＰＫｉ，ＳＫｉ）＝ＫｅｙＧｅｎ（ＩＤｉ，ｓ，ｐａｒａｍｓ）．３）ＭＡＳｉｇｎｃｒｙｐｔ：该算法由消息的发送者ＩＤＳ执行，输入系统公开参数ｐａｒａｍｓ、发送者私钥ＳＫＩＤＳ、接收者身份集合｛ＩＤＲ１，ＩＤＲ２，…，ＩＤＲｎ｝、接收者公钥集合｛ＰＫＲ１，ＰＫＲ２，…，ＰＫＲｎ｝和消息集合Ｍ＝｛Ｍ１，Ｍ２，…，Ｍｎ｝，输出签密密文σ＝ＭＡＳｉｇｎｃｒｙｐｔ（ｐａｒａｍｓ，ＳＫＩＤＳ，ＩＤＲ，Ｍ）．４）ＵｎＳｉｇｎｃｒｙｐｔ：该算法由密文接收者ＩＤＲ执行，输入系统公开参数ｐａｒａｍｓ、发送者公钥ＰＫＩＤＳ、接收者私钥ＳＫＩＤＲ和密文σ，如果验证密文σ为发送者发送的签密密文，则解密消息ｍ＝ＵｎＳｉｇｎｃｒｙｐｔ（ｐａｒａｍｓ，ＰＫＩＤＳ，ＳＫＩＤＲ，σ），否则输出⊥．无证书多接收者多消息同步广播签密方案算法模型和通信模型如图１表示．图１　算法通信模型 在无证书多接收者多消息同步广播签密算法通信模型中，发送者把发送给ｎ个接收者的ｎ个消息在一个逻辑步骤中完成签密，生成签密密文ｃ．通过公开信道把密文ｃ同步广播给每一个接收者．接收者收到密文ｃ后首先验证发送者的签名是否正确，正确则解密密文恢复明文ｍ，否则拒收密文．０３７东南大学学报（自然科学版） 第５０卷ｈｔｔｐ：／／ｊｏｕｒｎａｌ．ｓｅｕ．ｅｄｕ．ｃｎ１．３　无证书多接收者匿名签密安全模型密码体制可证安全性是指在特定的敌手能力模型下该体制能达到的安全目标［１９］．文献［６］给出了基于身份多接收者匿名签密安全模型，机密性安全目标是适应性选择密文攻击下的密文不可区分性（ＩＮＤ ｓＭＩＢＡＳ ＣＣＡ２）；不可伪造性安全目标是适应性选择消息攻击下不可伪造性（ＭＥＵＦ ＭＩＢ ＳＣ ＣＭＡ）．文献［１０］在文献［６］基础上，将基于身份签密机制安全模型推广到无证书多接收者匿名签密机制．本文方案与文献［１０］基于相同的密码体制，因此本文方案安全模型参照文献［１０］．根据文献［１０］定义的安全模型，攻击本文方案敌手分为２类：第１类是普通攻击者，定义为ＡｉＩ（ｉ＝１，２），敌手ＡｉＩ攻击能力为能够替换合法用户公钥但不掌握系统主密钥；第２类是好奇密钥生成中心ＫＧＣ，定义为ＡｉΠ（ｉ＝１，２），敌手ＡｉΠ攻击能力为不能替换用户公钥但掌握系统主密钥．其中，Ａ１Ι和Ａ１Π为攻击方案机密性敌手；Ａ２Ι和Ａ２Π为攻击方案不可伪造性敌手．２　本文方案２．１　方案描述２．１．１　系统参数设置ＫＧＣ执行如下操作：①选择安全参数（１λ）和安全大素数ｑ（ｑ≥２λ），设置椭圆曲线上阶为大素数ｑ的循环加法群Ｇ，在群Ｇ上随机选取生成元Ｐ．②定义４个满足密码学安全的散列函数：Ｈ０：｛０，１｝ｌ０×Ｇ×Ｇ→Ｚ ｑＨ１：｛０，１｝ｌ０→ＺｑＨ２：Ｇ→｛０，１｝ｌ０＋ｌ１＋ＺｑＨ３：｛０，１｝ｌ１×Ｇ×｛０，１｝ｌ０×Ｇ×Ｇ→Ｚｑ式中，ｌ０为用户身份ＩＤ的长度；ｌ１为明文消息的长度；Ｚ ｑ为Ｚｑ中元素的长度．③秘密选取随机数ｓ∈Ｚｑ作为系统的主密钥，计算系统公钥Ｐｐｕｂ＝ｓＰ∈Ｇ．秘密保存主密钥ｓ，公开发布系统参数ｐａｒａｍｓ＝｛ｑ，Ｚ ｑ，Ｇ，Ｐ，Ｐｐｕｂ，Ｈ０，Ｈ１，Ｈ２，Ｈ３，ｌ０，ｌ１｝．２．１．２　用户密钥生成用户公钥和私钥生成由ＫＧＣ与用户ＩＤｉ合作完成，具体步骤如下：①用户秘密选取随机数ｄｉ∈Ｚｑ，计算Ｄｉ＝ｄｉＰ，秘密保存ｄｉ，把身份ＩＤｉ和Ｄｉ发送给ＫＧＣ．②ＫＧＣ收到用户身份ＩＤｉ和公开参数Ｄｉ后，选取随机数ｒｉ∈Ｚｑ，计算Ｅｉ＝ｒｉＰ和ｅｉ＝ｒｉ＋ｓＨ０（ＩＤｉ，Ｄｉ，Ｅｉ），在安全信道上把部分公钥Ｅｉ和部分私钥ｅｉ传输给用户ＩＤｉ．③用户ＩＤｉ安全收到Ｅｉ和ｅｉ后，首先根据公开参数ｐａｒａｍｓ验证部分私钥ｅｉ和部分公钥Ｅｉ的正确性．即计算等式ｅｉＰ＝Ｅｉ＋ＰｐｕｂＨ０（ＩＤｉ，Ｄｉ，Ｅｉ）是否成立，如果成立，用户设置自己的完整私钥ＳＫｉ＝（ｄｉ，ｅｉ）和完整公钥ＰＫｉ＝（Ｄｉ，Ｅｉ），否则重新请求ＫＧＣ生成部分公私钥．２．１．３　多消息匿名签密设消息的发送者为Ａｌｉｃｅ，身份标识ＩＤＡ，ＩＤＡ输入系统公开参数ｐａｒａｍｓ，待发送消息集合ＬＭ＝｛ｍ１，ｍ２，…，ｍｎ｝，接收者集合ＬＲ＝｛ＩＤ１，ＩＤ２，…，ＩＤｎ｝．ＩＤＡ按如下步骤进行多消息签密：１）签名Ｓｉｇｎ①选取随机数ｋ∈Ｚｑ，计算Ｋ＝ｋＰ．②计算ｈｉ＝Ｈ３（ｍｉ，Ｋ，ＩＤＡ，ＤＡ，ＥＡ），ｕｉ＝ｋ／（ｄＡ＋ｅＡｈｉ），１≤ｉ≤ｎ．２）加密Ｅｎｃｒｙｐｔ①选取随机数序列ｔｉ∈Ｚｑ，计算Ｔｉ＝ｔｉＰ，１≤ｉ≤ｎ．②计算ｘｉ＝Ｈ１（ＩＤｉ），１≤ｉ≤ｎ，构造拉格朗日插值多项式ｆｉ（ｘ）＝∏ｎｊ＝１，ｊ≠ｉｘ－ｘｊｘｉ－ｘｊ＝ａｉ，１＋ａｉ，２ｘ＋…＋ａｉ，ｎｘｎ－１式中，ａｉ，１，ａｉ，２，…，ａｉ，ｎ∈Ｚｑ．③计算Ｚｉ＝∑ｎｊ＝１ａｊ，ｉＴｉ，１≤ｉ≤ｎ．④设发送给用户ＩＤｉ，ｉ∈｛１，２，…，ｎ｝的消息为ｍｉ，即第ｉ个消息发送给用户ＩＤｉ．随机从集合｛１，２，…，ｎ｝选取数值ｗｉ（要求ｎ个接收者的ｗｉ是唯一的），ｗｉ为消息ｍｉ的密文在密文集合中的索引，接收者ＩＤｉ通过ｗｉ唯一定位自己接收的密文．计算Ｗｉ＝∑ｎｊ＝１ａｊ，ｉｗｉ，１≤ｉ≤ｎ．⑤计算Ｙｉ＝ｔｉＤｉ＋ｋ（Ｅｉ＋ＰｐｕｂＨ０（ＩＤｉ，Ｄｉ，Ｅｉ）），Ｃｗｉ＝Ｈ２（Ｙｉ） （ｍｉ‖ＩＤＡ‖ｕｉ），１≤ｉ≤ｎ．⑥σ＝（Ｋ，Ｚ１，Ｚ２，…，Ｚｎ，Ｗ１，Ｗ２，…，Ｗｎ，Ｃｗ１，Ｃｗ２，…，Ｃｗｎ）为签密密文，Ａｌｉｃｅ将签密密文σ同步广播给接收者集合中的每一位成员．２．１．４　解签密接收者ＩＤｉ，ｉ∈｛１，２，…，ｎ｝接收到签密密文σ后，输入系统公开参数ｐａｒａｍｓ，私钥ＳＫｉ＝（ｄｉ，ｅｉ），完成密文解签密工作，具体步骤如下：１３７第４期方光伟，等：可证安全的无证书多消息同步广播签密方案ｈｔｔｐ：／／ｊｏｕｒｎａｌ．ｓｅｕ．ｅｄｕ．ｃｎ１）解密Ｄｅｃｒｙｐｔ①计算ｘｉ＝Ｈ１（ＩＤｉ），计算多项式Ｔｉ＝Ｚ１＋Ｚ２ｘｉ＋…＋Ｚｎｘｎ－１ｉ（ｍｏｄｑ），ｗｉ＝Ｗ１＋Ｗ２ｘｉ＋…＋Ｗｎｘｎ－１ｉ（ｍｏｄｎ），根据ｗ ｉ获取对应密文Ｃｗ ｉ．②计算Ｙ ｉ＝Ｔ ｉｄｉ＋Ｋｅｉ，（ｍ ｉ‖ＩＤ Ａ‖ｕｉ）＝Ｈ２（Ｙｉ） Ｃｗ ｉ，接收者从恢复的原始信息中分离出消息ｍ ｉ、发送者身份信息ＩＤ Ａ、签名信息ｕ ｉ．２）验证Ｖｅｒｉｆｙ①根据发送者身份信息ＩＤＡ计算ｈＡ０＝Ｈ０（ＩＤＡ，ＤＡ，ＥＡ）和ｈ′ｉ＝Ｈ３（ｍ ｉ，Ｋ，ＩＤ Ａ，ＤＡ，ＥＡ）．②利用发送者的公钥信息验证ｈ′ｉ＝Ｈ３（ｍｉ，ｕ ｉ（ＤＡ＋（ＥＡ＋ＰｐｕｂｈＡ０）ｈ′ｉ），ＩＤＡ，ＤＡ，ＥＡ）是否成立，如果成立，输出消息ｍｉ，否则输出无效密文符⊥．２．２　方案的正确性定理１　接收者ＩＤｉ能从接收的密文σ＝（Ｋ，Ｚ１，Ｚ２，…，Ｚｎ，Ｗ１，Ｗ２，…，Ｗｎ，Ｃｗ１，Ｃｗ２，…，Ｃｗｎ）中恢复出明文消息ｍｉ，ｉ∈｛１，２，…，ｎ｝．证明　接收者ＩＤｉ，ｉ∈｛１，２，…，ｎ｝，解密过程如下：①计算ｘｉ＝Ｈ１（ＩＤｉ）Ｔ ｉ＝Ｚ１＋Ｚ２ｘｉ＋…＋Ｚｉｘｎ－１ｉ（ｍｏｄｑ）＝∑ｎｊ＝１ａｊ，１Ｔｊ＋∑ｎｊ＝１ａｊ，２Ｔｊｘｉ＋…＋∑ｎｊ＝１ａｊ，ｎＴｊｘｎ－１ｉ＝（ａ１，１Ｔ１＋ａ２，１Ｔ２＋…＋ａｎ，１Ｔｎ）＋（ａ１，２Ｔ１ｘｉ＋ａ２，２Ｔ２ｘｉ＋…＋ａｎ，２Ｔｎｘｉ）＋…＋（ａ１，ｎＴ１ｘｎ－１ｉ＋ａ２，ｎＴ２ｘｎ－１ｉ＋…＋ａｎ，ｎＴｎｘｎ－１ｉ）＝∑ｎｊ＝１ａ１，ｊＴ１ｘｊ－１ｉ＋…＋∑ｎｊ＝１ａｉ，ｊＴｉｘｊ－１ｉ＋…＋∑ｎｊ＝１ａｎ，ｊＴｎｘｊ－１ｉ＝ｆ１（ｘｉ）Ｔ１＋…＋ｆｉ（ｘｉ）Ｔｉ＋…＋ｆｎ（ｘｉ）Ｔｎ＝Ｔｉｗｉ＝Ｗ１＋Ｗ２ｘｉ＋…＋Ｗｎｘｎ－１ｉ（ｍｏｄｎ）＝∑ｎｊ＝１ａｊ，１ｗｊ＋∑ｎｊ＝１ａｊ，２ｗｊｘｉ＋…＋∑ｎｊ＝１ａｊ，ｎｗｊｘｎ－１ｉ＝（ａ１，１ｗ１＋ａ２，１ｗ２＋…＋ａｎ，１ｗｎ）＋（ａ１，２ｗ１ｘｉ＋ａ２，２ｗ２ｘｉ＋…＋ａｎ，２ｗｎｘｉ）＋…＋（ａ１，ｎｗ１ｘｎ－１ｉ＋ａ２，ｎｗ２ｘｎ－１ｉ＋…＋ａｎ，ｎｗｎｘｎ－１ｉ）＝∑ｎｊ＝１ａ１，ｊｗ１ｘｊ－１ｉ＋…＋∑ｎｊ＝１ａｉ，ｊｗｉｘｊ－１ｉ＋…＋∑ｎｊ＝１ａｎ，ｊｗｎｘｊ－１ｉ＝ｆ１（ｘｉ）ｗ１＋…＋ｆｉ（ｘｉ）ｗｉ＋…＋ｆｎ（ｘｉ）ｗｎ＝ｗｉＹ ｉ＝Ｔ ｉｄｉ＋Ｋｅｉ＝Ｔｉｄｉ＋Ｋ（ｒｉ＋ｓＨｉ０）＝ｔｉＤｉ＋ｋ（Ｅｉ＋ＰｐｕｂＨｉ０）＝Ｙｉ②计算（ｍ ｉ‖ＩＤ Ａ‖ｕ ｉ）＝Ｈ２（Ｙｉ） Ｃｗ ｉ＝Ｈ２（Ｙｉ） Ｃｗｉ，即ｍ ｉ＝ｍｉ，ＩＤ Ａ＝ＩＤＡ，ｕｉ＝ｕｉ．证毕．定理２　接收者ＩＤｉ恢复的明文消息ｍｉ是合法的．证明　接收者ＩＤｉ，ｉ∈｛１，２，…，ｎ｝从恢复的消息（ｍｉ‖ＩＤＡ‖ｕｉ）中提取出明文ｍｉ、发送者身份标识ＩＤＡ、签名信息ｕｉ．签名验证过程如下：①计算ｈＡ０＝Ｈ０（ＩＤＡ，ＤＡ，ＥＡ）和ｈ′ｉ＝Ｈ３（ｍｉ，Ｋ，ＩＤＡ，ＤＡ，ＥＡ）．Ｈ３（ｍｉ，ｕｉ（ＤＡ＋（ＥＡ＋ＰｐｕｂｈＡ０）ｈ′ｉ），ＩＤＡ，ＤＡ，ＥＡ）＝Ｈ３ｍｉ，ｋｄＡ＋ｅＡｈ′ｉＤＡ＋（ＥＡ＋ＰｐｕｂｈＡ０）ｈ′()ｉ，ＩＤＡ，ＤＡ，Ｅ()Ａ＝Ｈ３ｍｉ，ｋｄＡ＋ｅＡｈ′ｉｄＡＰ＋（ｒＡＰ＋ｓＰｈＡ０）ｈ′()ｉ，ＩＤＡ，ＤＡ，Ｅ()Ａ＝Ｈ３（ｍｉ，ｋＰ，ＩＤＡ，ＤＡ，ＥＡ）＝Ｈ３（ｍｉ，Ｋ，ＩＤＡ，ＤＡ，ＥＡ）＝ｈ′ｉ（１）②判断等式（１）成立，接收者恢复的明文消息ｍｉ是发送者ＩＤＡ签名的合法消息．证毕．上述方案加密过程中，除了加密明文ｍｉ外，还对发送者身份ＩＤＡ和签名ｕｉ一同加密．因此非合法接收者无法知晓发送者身份信息，实现发送者身份匿名性；同时，通过接收者身份信息ＩＤｉ计算ｘｉ＝Ｈ１（ＩＤｉ），生成拉格朗日插值多项式的系数矩阵，通过矩阵元素ａｉ，ｊ（１≤ｉ，ｊ≤ｎ）计算向量∑ｎｉ＝１ａｉ，１，∑ｎｉ＝１ａｉ，２，…，∑ｎｉ＝１ａｉ，{}ｎ，利用该向量与群Ｇ中一个随机元素Ｔｉ建立关联，将接收者的身份信息隐藏在集合｛Ｚ１，Ｚ２，…，Ｚｎ｝中，密文中无需包含接收者身份列表，从而实现接收者身份匿名性；其次，利用该向量与集合｛１，２，…，ｎ｝中一个整数值ｗｉ关联，接收者根据ｗｉ从密文集合｛Ｃｗ１，Ｃｗ２，…，Ｃｗｎ｝中定位自己的密文Ｃｗｉ．３　安全性证明３．１　机密性定理３（敌手Ａ１Ｉ在随机谕言机模型下的机密性）　若存在敌手Ａ１Ｉ赢得文献［１０］中定义相关游戏，其获胜概率ε是不可忽略的．则挑战者Ｃ能在概率多项式时间内解决ＣＤＨ困难问题，Ｃ成功的概率为ｓｕｃｃＣＤＨＣ，Ａ１Ｉ()λ≥ε１－ｎｑＨ()２１－１ｑＨ()３，其中，ｑＨ２为Ｈ２询问次数，ｑＨ３为Ｈ３询问次数．证明　挑战者Ｃ输入元组〈Ｐ，ａＰ，ｂＰ〉（其中，ａ，ｂ∈Ｚｑ且ａ，ｂ未知），目标是利用敌手Ａ１Ｉ输出ａｂＰ．Ｃ以Ａ１Ｉ为子程序并运行Ｓｅｔｕｐ算法建立系统（令Ｐｐｕｂ＝ｂＰ，ｂ为系统主密钥，Ｃ不掌握），生成ｐａｒａｍｓ＝ｑ，Ｚ ｑ，Ｇ，Ｐ，Ｐｐｕｂ，Ｈ０，Ｈ１，Ｈ２，Ｈ３，ｌ０，ｌ{}１并２３７东南大学学报（自然科学版） 第５０卷ｈｔｔｐ：／／ｊｏｕｒｎａｌ．ｓｅｕ．ｅｄｕ．ｃｎ公开发布；Ｃ建立ＬＨ０、ＬＨ１、ＬＨ２、ＬＨ３、ＬＳＫ、ＬＰＫ索引列表用于跟踪Ａ１Ｉ对谕言机Ｈ０、Ｈ１、Ｈ２、Ｈ３、生成私钥和生成公钥的查询；Ｃ初始各列表为空；Ａ１Ｉ选择目标身份列表ＩＤ ｊ＝｛ＩＤ １，ＩＤ ２，…，ＩＤｎ｝．Ａ１Ｉ与Ｃ进行下述３个阶段的游戏交互．１）查询阶段Ｈ１询问．Ａ１Ｉ提交查询访问参数ＩＤｉ，Ｃ查询ＬＨ１列表，若存在元组〈ＩＤｉ，ｘｉ〉，则返回ｘｉ给Ａ１Ｉ，否则随机选取ｘ ｉ∈Ｚ ｑ且〈 ，ｘ ｉ〉 ＬＨ１，添加元组〈ＩＤｉ，ｘ ｉ〉到ＬＨ１并返回ｘ ｉ给Ａ１Ｉ．Ｈ２询问．Ａ１Ｉ提交查询访问参数Ｙｉ，Ｃ查询ＬＨ２列表，若存在元组〈Ｙｉ，ｈｉ２〉，则返回ｈｉ２给Ａ１Ｉ，否则随机选取ｈ ２∈｛０，１｝ｌ０＋ｌ１＋Ｚ ｑ且〈 ，ｈ２〉 ＬＨ２，添加元组〈Ｙｉ，ｈ ２〉到ＬＨ２并返回ｈ２给Ａ１Ｉ．Ｈ３询问．Ａ１Ｉ提交查询访问参数（ｍｉ，Ｋｉ，ＩＤｉ，Ｄｉ，Ｅｉ），Ｃ查询ＬＨ３列表，若存在元组〈ｍｉ，Ｋｉ，ＩＤｉ，Ｄｉ，Ｅｉ，ｈｉ３〉，则返回ｈｉ３给Ａ１Ｉ，否则随机选取ｈ３∈Ｚ ｑ且〈 ， ， ， ， ，ｈ ３〉 ＬＨ３，添加元组〈ｍｉ，Ｋｉ，ＩＤｉ，Ｄｉ，Ｅｉ，ｈ ３〉到ＬＨ３并返回ｈ ３给Ａ１Ｉ．公钥提取询问．Ａ１Ｉ提交查询访问参数ＩＤｉ，Ｃ查询ＬＰＫ列表，若存在元组〈ＩＤｉ，Ｄｉ，Ｅｉ〉，则返回（Ｄｉ，Ｅｉ）给Ａ１Ｉ，否则Ｃ按下面的规则生成用户公钥：①ＩＤｉ≠ＩＤｊ，ｊ∈｛１，２，…，ｎ｝，Ｃ随机选取ｄｉ，ｒｉ，ｈｉ０∈Ｚｑ，计算Ｄｉ＝ｄｉＰ，Ｅｉ＝ｒｉＰ－Ｐｐｕｂｈｉ０，其中要求满足条件〈 ，Ｄｉ，Ｅｉ〉 ＬＰＫ且〈 ， ， ，ｈｉ０〉 ＬＨ０且〈 ，ｄｉ，ｒｉ〉 ＬＳＫ，添加元组〈ＩＤｉ，Ｄｉ，Ｅｉ〉到ＬＰＫ中，添加元组〈ＩＤｉ，ｄｉ，ｒｉ〉到ＬＳＫ中，添加元组〈ＩＤｉ，Ｄｉ，Ｅｉ，ｈｉ０〉到ＬＨ０中，返回（Ｄｉ，Ｅｉ）给Ａ１Ｉ．②ＩＤｉ＝ＩＤｊ，ｊ∈｛１，２，…，ｎ｝，Ｃ随机选取ｄ ｉ，ｒ ｉ∈Ｚ ｑ，计算Ｄｉ＝ｄ ｉＰ，Ｅｉ＝ｒｉＰ，其中要求满足条件〈 ，Ｄｉ，Ｅｉ〉 ＬＰＫ，添加元组〈ＩＤｉ，Ｄｉ，Ｅｉ〉到ＬＰＫ中，Ｃ随机选取ｈ ０∈Ｚ ｑ，满足〈 ， ， ，ｈ０〉 ＬＨ０，添加元组〈ＩＤｉ，Ｄｉ，Ｅｉ，ｈ０〉到ＬＨ０中，返回（Ｄｉ，Ｅｉ）给Ａ１Ｉ．Ｈ０询问．Ａ１Ｉ提交查询访问参数（ＩＤｉ，Ｄｉ，Ｅｉ），Ｃ查询ＬＨ０列表，若存在元组〈ＩＤｉ，Ｄｉ，Ｅｉ，ｈｉ０〉，则返回ｈｉ０给Ａ１Ｉ，否则Ｃ对ＩＤｉ进行公钥询问后返回相应的ｈｉ０给Ａ１Ｉ．私钥提取询问．Ａ１Ｉ提交查询访问参数ＩＤｉ（ＩＤｉ≠ＩＤ ｊ，ｊ∈｛１，２，…，ｎ｝），Ｃ查询ＬＳＫ列表，若存在元组〈ＩＤｉ，ｄｉ，ｒｉ〉，则返回（ｄｉ，ｒｉ）给Ａ１Ｉ，否则Ｃ对ＩＤｉ公钥询问后返回相应的（ｄｉ，ｒｉ）给Ａ１Ｉ．公钥替换询问．Ａ１Ｉ提交公钥替换数据（ＩＤｉ，Ｄ′ｉ，Ｅ′ｉ），Ｃ把元组〈ＩＤｉ，Ｄｉ，Ｅｉ〉替换为〈ＩＤｉ，Ｄ′ｉ，Ｅ′ｉ〉．签密询问．Ａ１Ｉ提交签密询问参数（ＩＤＳ，ＩＤＲ＝｛ＩＤＲｉ｝，ＬＭ＝｛ｍｉ｝），１≤ｉ≤ｎ，Ｃ按下述规则签密：①如果ＩＤＳ≠ＩＤｊ，ｊ∈｛１，２，…，ｎ｝，Ｃ对ＩＤＳ私钥提取询问得到元组〈ＩＤＳ，ｄＳ，ｒＳ〉；对ＩＤＲ中每一个身份ＩＤＲｉ公钥提取询问得到元组集〈ＩＤＲｉ，ＤＲｉ，ＥＲｉ〉，１≤ｉ≤ｎ；Ｃ运行多消息匿名签密算法得到签密密文σ ＝（Ｋ ，Ｚ Ｒｉ，Ｗ Ｒｉ，Ｃ Ｒｉ），１≤ｉ≤ｎ，将σ返回给Ａ１Ｉ．②如果ＩＤＳ＝ＩＤｊ，ｊ∈｛１，２，…，ｎ｝，Ｃ对ＩＤＳ公钥提取询问得到元组〈ＩＤＳ，ＤＳ，ＥＳ〉，对（ＩＤＳ，ＤＳ，ＥＳ）作Ｈ０询问得ｈＳ０，随机选择ｕ ，ｈ ３∈Ｚｑ，计算Ｋ ＝ｕ （ＤＳ＋（ＥＳ＋ＰｐｕｂｈＳ０）ｈ ３），将〈ｍｉ，Ｋ ，ＩＤＳ，ＤＳ，ＥＳ，ｈ ３〉（其中，１≤ｉ≤ｎ）插入到ＬＨ３中，然后按照多消息匿名签密的Ｅｎｃｒｙｐｔ算法计算σ 并返回给Ａ１Ｉ．解签密询问．Ａ１Ｉ提交解签密询问参数（ＩＤＲｊ，σ＝（Ｋ，Ｚｉ，Ｗｉ，Ｃｉ）），１≤ｉ≤ｎ，ｊ∈｛１，２，…，ｎ｝，Ｃ按下述规则解签密：①ＩＤＲｊ≠ＩＤｊ，ｊ∈｛１，２，…，ｎ｝，Ｃ对ＩＤＲｊ私钥提取询问得到元组〈ＩＤＲｊ，ｄＲｊ，ｒＲｊ〉；Ｃ以ＩＤＲｊ为参数进行Ｈ１询问得到ｘＲｊ；计算ｗＲｊ＝Ｗ１＋Ｗ２ｘＲｊ＋…＋Ｗｎｘｎ－１Ｒｊ（ｍｏｄｎ），由ｗＲｊ定位对应密文ＣＲｊ，计算ＴＲｊ＝Ｚ１＋Ｚ２ｘＲｊ＋…＋Ｚｎｘｎ－１Ｒｊ（ｍｏｄｑ），ＹＲｊ＝ＴＲｊｄＲｊ＋ＫｒＲｊ；以ＹＲｊ为参数进行Ｈ２询问得到ｈＲｊ２，解密得到ｈＲｊ２ ＣＲｊ＝（ｍＲｊ‖ＩＤＳ‖ｕＲｊ），对ＩＤＳ公钥查询得到元组〈ＩＤＳ，ＤＳ，ＥＳ〉；对（ｍＲｊ，Ｋ，ＩＤＳ，ＤＳ，ＥＳ）作Ｈ３询问得ｈＲｊ，若〈ＩＤＳ，ＤＳ，ＥＳ〉∈ＬＰＫ，计算Ｋ＝ｕＲｊ（ＤＳ＋（ＥＳ＋ＰｐｕｂｈＳ０）ｈＲｊ），验证（ｍＲｊ，Ｋ，ＩＤＳ，ＤＳ，ＥＳ）的Ｈ３询问和（ｍＲｊ，Ｋ ，ＩＤＳ，ＤＳ，ＥＳ）的Ｈ３询问是否相等，相等返回ｍＲｊ给Ａ１Ｉ，不相等则返回无效密文符⊥．若〈ＩＤＳ，ＤＳ，ＥＳ〉 ＬＰＫ（公钥被替换），计算Ｋ＝ｕＲｊ（Ｄ′Ｓ＋（Ｅ′Ｓ＋ＰｐｕｂｈＳ０）ｈＲｊ），验证（ｍＲｊ，Ｋ，ＩＤＳ，Ｄ′Ｓ，Ｅ′Ｓ）的Ｈ３询问和（ｍＲｊ，Ｋ ，ＩＤＳ，Ｄ′Ｓ，Ｅ′Ｓ）的Ｈ３询问是否相等，相等返回ｍＲｊ给Ａ１Ｉ，不相等则返回无效密文符⊥．②ＩＤＲｊ＝ＩＤｊ，ｊ∈｛１，２，…，ｎ｝，Ｃ遍历ＬＨ２列表，对每一元组〈Ｔｉ，ｈｉ２〉（１≤ｉ≤ｑＨ２）计算ｈｉ２ ＣＲｊ＝（ｍ ｉ‖ＩＤ ｉ‖ｕ ｉ），对（ＩＤ ｉ）作公钥得〈ＩＤ ｉ，Ｄ ｉ，３３７第４期方光伟，等：可证安全的无证书多消息同步广播签密方案ｈｔｔｐ：／／ｊｏｕｒｎａｌ．ｓｅｕ．ｅｄｕ．ｃｎＥ ｉ〉，对（ｍ ｉ，Ｋ，ＩＤ ｉ，Ｄ ｉ，Ｅ ｉ）作Ｈ３询问得ｈｉ，若〈ＩＤ ｉ，Ｄ ｉ，Ｅ ｉ〉∈ＬＰＫ，计算ｕ ｉ（Ｄ ｉ＋（Ｅｉ＋Ｐｐｕｂｈｉ０）ｈ ｉ）＝Ｋ ，验证（ｍ ｉ，Ｋ，ＩＤ ｉ，Ｄ ｉ，Ｅｉ）的Ｈ３询问和（ｍ ｉ，Ｋ ，ＩＤ ｉ，Ｄ ｉ，Ｅ ｉ）的Ｈ３询问是否相等，相等返回ｍｉ给Ａ１Ｉ，不相等则返回无效密文符⊥；若〈ＩＤ ｉ，Ｄ ｉ，Ｅ ｉ〉 ＬＰＫ（公钥被替换），计算ｕ ｉ（Ｄ′ｉ＋（Ｅ′ｉ＋Ｐｐｕｂｈｉ０）ｈｉ）＝Ｋ，验证（ｍ ｉ，Ｋ，ＩＤ ｉ，Ｄ′ｉ，Ｅ′ｉ）的Ｈ３询问和（ｍ ｉ，Ｋ ，ＩＤｉ，Ｄ′ｉ，Ｅ′ｉ）的Ｈ３询问是否相等，相等返回ｍ ｉ给Ａ１Ｉ，不相等则返回无效密文符⊥．２）挑战阶段在查询阶段结束后，Ａ１Ｉ提交挑战签密用户（ＩＤＳ，ＩＤＲ１，ＩＤＲ２，…，ＩＤＲｎ）（其中ＩＤＲｊ∈ＩＤｊ，ｊ∈１，２，…，ｎ），以及２组等长的明文Ｍ０＝｛ｍ１０，ｍ２０，…，ｍｎ０｝和Ｍ１＝｛ｍ１１，ｍ２１，…，ｍｎ１｝（其中ｍｉ０＝ｍｉ１，１≤ｉ≤ｎ），Ｃ按下述步骤进行签密：①Ｃ令Ｋ＝ａＰ（Ｃ不掌握ａ）．②Ｃ随机选取β←｛０，１｝，对ＩＤＳ进行公钥查询得（ＤＳ，ＥＳ），以（ＩＤＳ，ＤＳ，ＥＳ）为参数作Ｈ０查询得ｈＳ０，以（ｍｉβ，Ｋ，ＩＤＳ，ＤＳ，ＥＳ）为参数做Ｈ３查询得ｈ′３，选取ｕ′∈Ｚｑ，满足Ｋ＝ｕ′（ＤＳ＋（ＥＳ＋ＰｐｕｂｈＳ０）ｈ′３）．③随机选取ｔＲｊ∈Ｚｑ，计算ＴＲｊ＝ｔＲｊＰ，以ＩＤＲｊ为参数作Ｈ１查询得ｘＲｊ，计算ｆｉ（ｘ）＝∏ｎｊ＝１，ｊ≠ｉｘ－ｘＲｊｘＲｉ－ｘＲｊ＝ａｉ，１＋ａｉ，２ｘ＋…＋ａｉ，ｎｘｎ－１，计算ＺＲｊ＝∑ｎｉ＝１ａｉ，ｊＴＲｊ，从集合｛１，２，…，ｎ｝中唯一选取ｗＲｉ，计算ＷＲｉ＝∑ｎｉ＝１ａｉ，ｊｗＲｉ；随机选取ｈＲｊ２∈｛０，１｝ｌ０＋ｌ１＋Ｚｑ，计算ＣＲｊ＝ｈＲｊ２ （ｍｉβ‖ＩＤＳ‖ｕ′）；Ｃ返回挑战密文σ′＝（Ｋ，ＺＲｊ，ＷＲｊ，ＣＲｊ）（其中１≤ｊ≤ｎ）给Ａ１Ｉ．３）猜测阶段Ａ１Ｉ收到挑战密文σ′后，可以继续阶段１）的各种询问，但不能对ＩＤｊ，ｊ∈｛１，２，…，ｎ｝进行私钥提取询问，也不能对σ′进行解签密询问．Ａ１Ｉ询问结束后，输出猜测β′给Ｃ，如果β′＝β，则Ａ１Ｉ以极大的概率至少提交了一个Ｈ２（ＹＲｊ）询问，Ｃ可输出ＣＤＨ问题的解答：ａｂＰ＝（ｈＲｊ０）－１（ＹＲｊ－ＴＲｊｄ Ｒｊ－Ｋｒ Ｒｊ）（其中，ｄ Ｒｊ，ｒ Ｒｊ为ＩＤＲｊ的私钥，见公钥提取询问第②步），否则Ｃ未能解决ＣＤＨ问题．Ｃ为Ａ１Ｉ提供了真实模拟攻击环境，若Ａ１Ｉ未对ｎ个指定的接收者中的任意一个ＹＲｊ进行Ｈ２询问和未对Ｋ进行Ｈ３询问，则Ｃ能利用Ａ１Ｉ成功解决ＣＤＨ问题．设事件Ｅ１表示Ａ１Ｉ未对ＹＲｊ进行Ｈ２询问，则Ｐｒ［Ｅ１］＝１－ｎｑＨ２，设事件Ｅ２表示Ａ１Ｉ未对Ｋ进行Ｈ３询问，则Ｐｒ［Ｅ２］＝１－１ｑＨ３，因此，Ｃ未终止模拟的概率至少为Ｐｒ［Ｅ１］∧Ｐｒ［Ｅ２］＝１－ｎｑＨ()２１－１ｑＨ()３．如果Ａ１Ｉ赢得上述游戏概率ε不可忽略，则Ｃ未终止且能成功解答ＣＤＨ问题优势为ｓｕｃｃＣＤＨＣ，Ａ１Ｉ（λ）≥ε１－ｎｑＨ()２１－１ｑＨ()３．证毕．定理４（敌手Ａ１Π在随机谕言机模型下机密性）若存在敌手Ａ１Π赢得文献［１０］中定义相关游戏，其获胜概率ε不可忽略．则挑战者Ｃ能在概率多项式时间内解决ＣＤＨ困难问题，Ｃ的概率为ｓｕｃｃＣＤＨＣ，Ａ１Π（λ）≥ε１－ｎｑＨ()２１－１ｑＨ()３．证明　挑战者Ｃ输入元组〈Ｐ，ａＰ，ｂＰ〉（其中，ａ，ｂ∈Ｚｑ且α，ｂ未知），目标是利用敌手Ａ１Π输出ａｂＰ．Ｃ以Ａ１Π为子程序并运行Ｓｅｔｕｐ算法建立系统，令ｖ＝ｂＰ，选取ｓ∈Ｚ ｑ为主密钥并秘密保存，计算Ｐｐｕｂ＝ｓＰ，公开ｐａｒａｍｓ＝｛ｑ，Ｚｑ，Ｇ，Ｐ，Ｐｐｕｂ，Ｈ０，Ｈ１，Ｈ２，Ｈ３，ｌ０，ｌ１｝；Ｃ建立ＬＨ０、ＬＨ１、ＬＨ２、ＬＨ３、ＬＳＫ、ＬＰＫ索引列表用于跟踪Ａ１Π对谕言机Ｈ０、Ｈ１、Ｈ２、Ｈ３、生成私钥和生成公钥查询；Ｃ初始各列表为空；Ａ１Π输出目标身份列表ＩＤ ｊ＝｛ＩＤ １，ＩＤ ２，…，ＩＤ ｎ｝；Ａ１Π与Ｃ进行下述３个阶段的游戏交互．１）查询阶段Ａ１Π在查询阶段的Ｈ１询问、Ｈ２询问、Ｈ３询问、Ｈ０询问、私钥提取询问和签密询问同定理３，Ａ１Π不能进行公钥替换询问．公钥提取询问．Ａ１Π提交查询访问参数ＩＤｉ，Ｃ以ＩＤｉ为索引查询ＬＰＫ列表，若存在元组〈ＩＤｉ，Ｄｉ，Ｅｉ〉，则返回（Ｄｉ，Ｅｉ）给Ａ１Π，否则Ｃ按下面规则生成用户公钥：①ＩＤｉ≠ＩＤｊ，ｊ∈｛１，２，…，ｎ｝，Ｃ随机选取ｄｉ，ｒｉ，ｈｉ０∈Ｚｑ，计算Ｄｉ＝ｄｉＰ，Ｅｉ＝ｒｉＰ－Ｐｐｕｂｈｉ０，其中要求满足条件〈 ，Ｄｉ，Ｅｉ〉 ＬＰＫ且〈 ， ， ，ｈｉ０〉 ＬＨ０且〈 ，ｄｉ，ｒｉ〉 ＬＳＫ，添加元组〈ＩＤｉ，Ｄｉ，Ｅｉ〉到ＬＰＫ中，添加元组〈ＩＤｉ，ｄｉ，ｒｉ〉到ＬＳＫ中，添加元组〈ＩＤｉ，Ｄｉ，Ｅｉ，ｈｉ０〉到ＬＨ０中，返回（Ｄｉ，Ｅｉ）给Ａ１Π．②ＩＤｉ＝ＩＤｊ，ｊ∈｛１，２，…，ｎ｝，Ｃ随机选取ｄ ｉ，ｒ ｉ∈Ｚ ｑ，计算Ｄｉ＝ｄ ｉｖ＝ｄ ｉｂＰ，Ｅｉ＝ｒｉＰ，其中４３７东南大学学报（自然科学版） 第５０卷ｈｔｔｐ：／／ｊｏｕｒｎａｌ．ｓｅｕ．ｅｄｕ．ｃｎ要求满足条件〈 ，Ｄｉ，Ｅｉ〉 ＬＰＫ，添加元组〈ＩＤｉ，Ｄｉ，Ｅｉ〉到ＬＰＫ中，Ｃ随机选取ｈ ０∈Ｚｑ，其中要求满足条件〈 ， ， ，ｈ０〉 ＬＨ０，添加元组〈ＩＤｉ，Ｄｉ，Ｅｉ，ｈ０〉到ＬＨ０中，返回（Ｄｉ，Ｅｉ）给Ａ１Π．解签密询问．Ａ１Π提交解签密参数（ＩＤＲｊ，σｊ＝（Ｋ，Ｚｉ，Ｗｉ，ＣＲｊ）），１≤ｉ≤ｎ，ｊ∈｛１，２，…，ｎ｝，Ｃ按下述规则进行解签密询问：①ＩＤＲｊ≠ＩＤｊ，ｊ∈｛１，２，…，ｎ｝，Ｃ对ＩＤＲｊ私钥提取询问得到元组〈ＩＤＲｊ，ｄＲｊ，ｒＲｊ〉；Ｃ由Ｈ１询问得到ｘＲｊ；计算ｗＲｊ＝Ｗ１＋Ｗ２ｘＲｊ＋…＋Ｗｎｘｎ－１Ｒｊ（ｍｏｄｎ），由ｗＲｊ定位对应密文ＣＲｊ，计算ＴＲｊ＝Ｚ１＋Ｚ２ｘＲｊ＋…＋Ｚｎｘｎ－１Ｒｊ（ｍｏｄｑ），ＹＲｊ＝ＴＲｊｄＲｊ＋ＫｒＲｊ；以ＹＲｊ为参数进行Ｈ２询问得到ｈＲｊ２，解密得到ｈＲｊ２ ＣＲｊ＝（ｍＲｊ‖ＩＤＳ‖ｕＲｊ），对ＩＤＳ公钥查询得到元组〈ＩＤＳ，ＤＳ，ＥＳ〉；若〈ＩＤＳ，ＤＳ，ＥＳ〉∈ＬＰＫ，计算Ｋ＝ｕＲｊ（ＤＳ＋（ＥＳ＋ＰｐｕｂｈＳ０）ｈＲｊ），验证（ｍＲｊ，Ｋ，ＩＤＳ，ＤＳ，ＥＳ）的Ｈ３询问和（ｍＲｊ，Ｋ，ＩＤＳ，ＤＳ，ＥＳ）的Ｈ３询问是否相等，相等返回ｍＲｊ给Ａ１Π，不相等则返回无效密文符⊥．②ＩＤＲｊ＝ＩＤ ｊ，ｊ∈｛１，２，…，ｎ｝，Ｃ遍历ＬＨ２列表，对每一元组〈Ｔｉ，ｈｉ２〉（１≤ｉ≤ｑＨ２）计算ｈｉ２ＣＲｊ＝（ｍｉ‖ＩＤ ｉ‖ｕ ｉ），查询ＩＤ ｉ公钥，若〈ＩＤ ｉ，Ｄ ｉ，Ｅ ｉ〉∈ＬＰＫ，计算ｕ ｉ（Ｄ ｉ＋（Ｅ ｉ＋Ｐｐｕｂｈｉ０）ｈｉ）＝Ｋ ，验证（ｍ ｉ，Ｋ，ＩＤ ｉ，Ｄ ｉ，Ｅ ｉ）的Ｈ３询问和（ｍ ｉ，Ｋ ，ＩＤ ｉ，Ｄ ｉ，Ｅ ｉ）的Ｈ３询问是否相等，相等返回ｍ ｉ给Ａ１Π，不相等则返回无效密文符⊥．２）挑战阶段在查询阶段结束后，Ａ１Π提交挑战签密的用户（ＩＤＳ，ＩＤＲ１，ＩＤＲ２，…，ＩＤＲｎ）（其中，ＩＤＲｊ∈ＩＤｊ，ｊ∈１，２，…，ｎ）和２组等长明文Ｍ０＝｛ｍ１０，ｍ２０，…，ｍｎ０｝，Ｍ１＝｛ｍ１１，ｍ２１，…，ｍｎ１｝（其中，ｍｉ０＝ｍｉ１，１≤ｉ≤ｎ），Ｃ按下述步骤进行签密：①Ｃ随机选取β←｛０，１｝，随机选取ｋ∈Ｚｑ，计算Ｋ＝ｋＰ，按Ｓｉｇｎ算法计算ｕ′．②随机选取ｔＲｊ∈Ｚｑ，令Ｑ＝ａＰ（Ｃ不掌握ａ），计算ＴＲｊ＝ｔＲｊＱ＝ｔＲｊａＰ，以（ＩＤＲｊ）为参数作Ｈ１查询得ｘＲｊ，计算ｆｉ（ｘ）＝∏ｎｊ＝１，ｊ≠ｉｘ－ｘＲｊｘＲｉ－ｘＲｊ＝ａｉ，１＋ａｉ，２ｘ＋…＋ａｉ，ｎｘｎ－１，计算ＺＲｊ＝∑ｎｉ＝１ａｉ，ｊＴＲｊ，从集合｛１，２，…，ｎ｝中唯一选取ｗＲｉ，计算ＷＲｉ＝∑ｎｉ＝１ａｉ，ｊｗＲｉ；随机选取ｈＲｊ２∈｛０，１｝ｌ０＋ｌ１＋Ｚ ｑ，计算ＣＲｊ＝ｈＲｊ２ （ｍｉβ‖ＩＤＳ‖ｕ′）；Ｃ返回挑战密文σ′＝（Ｋ，ＺＲｊ，ＷＲｊ，ＣＲｊ）（其中１≤ｊ≤ｎ）给Ａ１Π．３）猜测阶段Ａ１Π收到挑战密文σ′后，可以继续阶段１）的各种询问，但不能对ＩＤｊ，ｊ∈｛１，２，…，ｎ｝进行私钥提取询问，也不能对σ′进行解签密询问．Ａ１Π询问结束后，输出猜测β′给Ｃ，如果β′＝β，则Ａ１Π以极大的概率至少提交了一个Ｈ２（ＹＲｊ）询问，Ｃ输出ＣＤＨ问题的解答：ａｂＰ＝（ｄ ＲｊｔＲｊ）－１（ＹＲｊ－Ｋｒ Ｒｊ－ＫｓｈＲｊ０）（其中，ｄ Ｒｊｂ，ｒ Ｒｊ为ＩＤ Ｒｊ的私钥，Ｃ掌握ｄ Ｒｊ，ｒ Ｒｊ，但不掌握ｂ，见公钥提取询问第②步），否则Ｃ未能解决ＣＤＨ问题．同定理３安全分析相同，若Ａ１Π挑战成功的概率ε不可忽略，则Ｃ未终止游戏且能成功解答ＣＤＨ问题优势为ｓｕｃｃＣＤＨＣ，Ａ１Π（λ）≥ε１－ｎｑＨ()２１－１ｑＨ()３．证毕．３．２　不可伪造性定理５（敌手Ａ２Ｉ在随机谕言机模型下的不可伪造性）　若存在敌手Ａ２Ｉ赢得文献［１０］中定义相关游戏，其获胜概率ε是不可忽略．则挑战者Ｃ能在概率多项式时间内解决ＤＬＰ困难问题，Ｃ的概率为ｓｕｃｃＤＬＰＣ，Ａ２Ｉ（λ）≥１－ｑＳＫ２()λεｅ１－１ｑＨ()３，其中，ｑＳＫ为私钥询问次数，ｑＳＣ为签密询问次数．证明　挑战者Ｃ输入随机元组〈Ｐ，ａＰ〉（其中，ａ∈Ｚｑ且ａ未知），目标是利用敌手Ａ２Ｉ的输出计算ａ．Ｃ以Ａ２Ｉ为子程序并运行Ｓｅｔｕｐ算法建立系统（其中，令Ｐｐｕｂ＝ａＰ，ａ为系统主密钥，Ｃ不掌握），生成ｐａｒａｍｓ＝｛ｑ，Ｚｑ，Ｇ，Ｐ，Ｐｐｕｂ，Ｈ０，Ｈ１，Ｈ２，Ｈ３，ｌ０，ｌ１｝并公开发布；Ｃ建立ＬＨ０、ＬＨ１、ＬＨ２、ＬＨ３、ＬＳＫ、ＬＰＫ索引列表用于跟踪Ａ２Ｉ对谕言机Ｈ０、Ｈ１、Ｈ２、Ｈ３、生成私钥和生成公钥的查询；Ｃ初始各列表为空；Ａ２Ｉ与Ｃ进行下述２个阶段游戏交互．１）查询阶段Ａ２Ｉ在查询阶段的Ｈ０询问、Ｈ１询问、Ｈ２询问、Ｈ３询问同定理３．公钥提取询问．Ａ２Ｉ提交查询访问参数ＩＤｉ，Ｃ以ＩＤｉ为索引查询ＬＰＫ列表，若存在元组〈ＩＤｉ，Ｄｉ，Ｅｉ，ｃｉ〉，则返回（Ｄｉ，Ｅｉ）给Ａ２Ｉ；否则Ｃ随机选取ｃｉ←｛０，１｝，要求ｃｉ满足Ｐｒ［ｃｉ＝１］＝１ｑＳＣ＋１，Ｃ根据ｃｉ的值按如下规则生成用户公钥：①若ｃｉ＝０，Ｃ随机选取ｄｉ，ｒｉ，ｈｉ０∈Ｚｑ，计算Ｄｉ＝ｄｉＰ，Ｅｉ＝ｒｉＰ－Ｐｐｕｂｈｉ０，其中要求满足条件〈 ，５３７第４期方光伟，等：可证安全的无证书多消息同步广播签密方案ｈｔｔｐ：／／ｊｏｕｒｎａｌ．ｓｅｕ．ｅｄｕ．ｃｎＤｉ，Ｅｉ，ｃｉ〉 ＬＰＫ且〈 ， ， ，ｈｉ０〉 ＬＨ０且〈 ，ｄｉ，ｒｉ〉 ＬＳＫ，添加元组〈ＩＤｉ，Ｄｉ，Ｅｉ，ｃｉ〉到ＬＰＫ中，添加元组〈ＩＤｉ，ｄｉ，ｒｉ〉到ＬＳＫ中，添加元组〈ＩＤｉ，Ｄｉ，Ｅｉ，ｈｉ０〉到ＬＨ０中，返回（Ｄｉ，Ｅｉ）给Ａ２Ｉ．②若ｃｉ＝１，Ｃ随机选取ｄ ｉ，ｒ ｉ∈Ｚｑ，计算Ｄｉ＝ｄ ｉＰ，Ｅｉ＝ｒｉＰ，其中要求满足条件〈 ，Ｄｉ，Ｅｉ，ｃｉ〉 ＬＰＫ，添加元组〈ＩＤｉ，Ｄｉ，Ｅｉ，ｃｉ〉到ＬＰＫ中，Ｃ随机选取ｈ ０∈Ｚｑ，其中要求满足条件〈 ， ， ，ｈ ０〉 ＬＨ０，添加元组〈ＩＤｉ，Ｄｉ，Ｅｉ，ｈ ０〉到ＬＨ０中，返回（Ｄｉ，Ｅｉ）给Ａ２Ｉ．私钥提取询问．Ａ２Ｉ提交查询访问参数ＩＤｉ，Ｃ以ＩＤｉ为索引查询ＬＳＫ列表，若存在元组〈ＩＤｉ，ｄｉ，ｒｉ〉，则返回（ｄｉ，ｒｉ）给Ａ２Ｉ，否则Ｃ对ＩＤｉ进行公钥询问后得到元组〈ＩＤｉ，Ｄｉ，Ｅｉ，ｃｉ〉，如果ｃｉ＝０返回相应的（ｄｉ，ｒｉ）给Ａ２Ｉ，否则Ｃ终止模拟．公钥替换询问．Ａ２Ｉ提交公钥替换数据（ＩＤｉ，Ｄ′ｉ，Ｅ′ｉ），Ｃ把元组〈ＩＤｉ，Ｄｉ，Ｅｉ〉替换为〈ＩＤｉ，Ｄ′ｉ，Ｅ′ｉ〉．签密询问．Ａ２Ｉ提交签密询问参数（ＩＤＳ，ＩＤＲ＝｛ＩＤＲ１，ＩＤＲ２，…，ＩＤＲｎ｝，ＬＭ＝｛ｍ１，ｍ２，…，ｍｎ｝），Ｃ对ＩＤＳ和ＩＤＲｉ（１≤ｉ≤ｎ）进行公钥查询得到元组〈ＩＤＳ，ＤＳ，ＥＳ，ｃＳ〉和〈ＩＤＲｉ，ＤＲｉ，ＥＲｉ，ｃＲｉ〉，根据查询结果按下述规则进行签密：①若ｃＳ＝０，Ｃ对ＩＤＳ私钥提取询问得到元组〈ＩＤＳ，ｄＳ，ｒＳ〉；Ｃ运行多消息匿名签密算法得到签密密文σ ＝（Ｋ ，Ｚ Ｒｉ，Ｗ Ｒｉ，Ｃ Ｒｉ），１≤ｉ≤ｎ，将σ 返回给Ａ２Ｉ．②若ｃＳ＝１，Ｃ终止模拟．解签密询问．Ａ２Ｉ提交解签密询问参数（ＩＤＲｊ，σｊ＝（Ｋ，Ｚｉ，ＣＲｊ）），１≤ｉ≤ｎ，ｊ∈｛１，２，…，ｎ｝，Ｃ对ＩＤＲｊ进行公钥查询得到元组〈ＩＤＲｊ，ＤＲｊ，ＥＲｊ，ｃＲｊ〉，根据查询结果按下述规则进行解签密询问：①若ｃＲｊ＝０，Ｃ对ＩＤＲｊ私钥提取询问得到元组〈ＩＤＲｊ，ｄＲｊ，ｒＲｊ〉；Ｃ由Ｈ１询问得到ｘＲｊ；计算多项式ＴＲｊ＝Ｚ１＋Ｚ２ｘＲｊ＋…＋Ｚｎｘｎ－１Ｒｊ（ｍｏｄｑ），ＹＲｊ＝ＴＲｊｄＲｊ＋ＫｒＲｊ；以ＹＲｊ为参数进行Ｈ２询问得到ｈＲｊ２，解密得到ｈＲｊ２ ＣＲｊ＝（ｍＲｊ‖ＩＤＳ‖ｕＲｊ），对ＩＤＳ公钥查询得到元组〈ＩＤＳ，ＤＳ，ＥＳ，ｃＳ〉；若〈ＩＤＳ，ＤＳ，ＥＳ〉∈ＬＰＫ，计算Ｋ＝ｕＲｊ（ＤＳ＋（ＥＳ＋ＰｐｕｂｈＳ０）ｈＲｊ），验证（ｍＲｊ，Ｋ，ＩＤＳ，ＤＳ，ＥＳ）的Ｈ３询问和（ｍＲｊ，Ｋ ，ＩＤＳ，ＤＳ，ＥＳ）的Ｈ３询问是否相等，相等返回ｍＲｊ给Ａ２Ｉ，不相等则返回无效密文符⊥；若〈ＩＤＳ，ＤＳ，ＥＳ〉 ＬＰＫ（公钥被替换为〈ＩＤＳ，Ｄ′Ｓ，Ｅ′Ｓ〉），计算Ｋ＝ｕＲｊ（Ｄ′Ｓ＋（Ｅ′Ｓ＋ＰｐｕｂｈＳ０）ｈＲｊ），验证（ｍＲｊ，Ｋ，ＩＤＳ，Ｄ′Ｓ，Ｅ′Ｓ）的Ｈ３询问和（ｍＲｊ，Ｋ ，ＩＤＳ，Ｄ′Ｓ，Ｅ′Ｓ）的Ｈ３询问是否相等，相等返回ｍＲｊ给Ａ２Ｉ，不相等则返回无效密文符⊥．②若ｃＲｊ＝１，Ｃ遍历ＬＨ２列表，对每一元组〈Ｔｉ，ｈｉ２〉（１≤ｉ≤ｑＨ２）计算ｈｉ２ ＣＲｊ＝（ｍ ｉ‖ＩＤ ｉ‖ｕｉ），查询ＩＤ ｉ公钥，若〈ＩＤ ｉ，Ｄ ｉ，Ｅ ｉ〉∈ＬＰＫ，计算ｕ ｉ（Ｄ ｉ＋（Ｅ ｉ＋Ｐｐｕｂｈｉ０）ｈ ｉ）＝Ｋ ，验证（ｍ ｉ，Ｋ，ＩＤ ｉ，Ｄ ｉ，Ｅ ｉ）的Ｈ３询问和（ｍ ｉ，Ｋ ，ＩＤ ｉ，Ｄ ｉ，Ｅ ｉ）的Ｈ３询问是否相等，相等返回ｍ ｉ给Ａ２Ｉ，不相等则返回无效密文符⊥；若〈ＩＤ ｉ，Ｄ ｉ，Ｅ ｉ〉 ＬＰＫ（公钥被替换），计算ｕ ｉ（Ｄ′ｉ＋（Ｅ′ｉ＋ＰｐｕｂｈＳ０）ｈ′ｉ）＝Ｋ ，验证（ｍ ｉ，Ｋ，ＩＤ ｉ，Ｄ′ｉ，Ｅ′ｉ）的Ｈ３询问和（ｍ ｉ，Ｋ ，ＩＤ ｉ，Ｄ′ｉ，Ｅ′ｉ）的Ｈ３询问是否相等，相等返回ｍ ｉ给Ａ２Ｉ，不相等则返回无效密文符⊥．２）伪造阶段在查询阶段结束后，Ａ２Ｉ提交挑战签名用户ＩＤＳ的公钥查询，Ｃ查询ＩＤＳ公钥得元组〈ＩＤＳ，ＤＳ，ＥＳ，ｃＳ〉，若ｃＳ＝０，Ｃ终止模拟；若ｃＳ＝１，Ｃ返回〈ＩＤＳ，ＤＳ，ＥＳ，ｃＳ〉给Ａ２Ｉ．Ａ２Ｉ随机选取ｋ′，ｕ′∈Ｚ ｑ，计算Ｋ′＝ｋ′Ｐ，以（ｍ′，Ｋ′，ＩＤＳ，ＤＳ，ＥＳ）为参数进行Ｈ３询问得到ｈ′３，提交伪造签名δ′＝（ＩＤＳ，ｍ′，Ｋ′，ｕ′，ｈ′３）给Ｃ．Ｃ验证签名是否合法，若δ′是合法签名，则Ｃ输出ＤＬＰ问题的解答ａ＝ｋ′－ｕ′（ｄ Ｓ＋ｒｓｈ′３）ｈＳ０ｈ′３．若δ′是不合法签名，则Ｃ未能解决ＤＬＰ问题．从Ｃ为Ａ２Ｉ提供的模拟攻击环境表明，Ｃ能利用Ａ２Ｉ成功解决ＤＬＰ问题的前提条件是Ｃ必须在模拟过程中未终止．询问阶段，设事件Ｅ１表示Ａ２Ｉ私钥提取询问时未终止，则Ｐｒ［Ｅ１］＝１－ｑＳＫ２λ；设事件Ｅ２表示Ｃ在签密询问时未终止，则Ｐｒ［Ｅ２］＝１－１ｑＳＣ()＋１ｑＳＣ＝ｑＳＣｑＳＣ()＋１ｑＳＣ≥１(ｅ当ｑＳＣ比较大时，ｑＳＣｑＳＣ()＋１ｑＳＣ趋向于１)ｅ；伪造阶段，设事件Ｅ３表示Ａ２Ｉ未对ｕ′进行相应的Ｈ３询问，则Ｐｒ［Ｅ３］＝１－１ｑＨ３，因此，Ｃ未终止模拟的概率至少为Ｐｒ［Ｅ１］∧Ｐｒ［Ｅ２］∧Ｐｒ［Ｅ３］≥１－ｑＳＫ２()λ１ｅ１－１ｑＨ()３．如果Ａ２Ｉ赢得上述游戏的概率ε是不可忽略的，则Ｃ未终止游戏且能成功解答ＤＬＰ问题优势为ｓｕｃｃＤＬＰＣ，Ａ２Ｉ（λ）≥１－ｑＳＫ２()λεｅ１－１ｑＨ()３．证毕．６３７东南大学学报（自然科学版） 第５０卷。