通用可复合的ElGamal型广播多重签密协议

李建民 俞惠芳 谢 永

1(青海省气象台 西宁 810001)2(西安邮电大学通信与信息工程学院 西安 710121)3(青海师范大学计算机学院 西宁 810008)4(青海大学计算技术与应用系 西宁 810003)

多重签名[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.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)|

定义4.UC仿真[21].设n∈N,令F是理想函数,π具有n个参与方的协议,τ是现实中某类敌手.若对任何现实攻击者A∈τ都存在一个理想过程中的敌手S,使得任何环境机Z都不能区分它是与(π,A)交互还是与(F,S)交互，则称π安全实现了F,记作:

IDEALF,S,Z≈REALπ,A,Z.

定义5.组合定理[21].令F和G是理想函数,π是F-混合模型下的一个协议,ρ协议在G-混合模型下可以安全地实现F.则对于任何敌手AG,都存在一个AF,使得对于任何环境机Z,都有:

1.3 基于离散对数的多重签名回顾

Harn[8]利用离散对数提出了一种有效的多重签名方案.假设n个签名者对同一消息m进行签名.

2) 签名者ui用秘钥zi和ki对消息m运行签名算法.即si=(zi(m′+r)-ki) modp,其中0≤si≤p-2和m′=f(m).签名者把元组(m,si)发送给消息收集者.

4) 消息收集者将对通过验证的消息进行合并：s=(s1+s2+…+sn) modp，得到完整的签名(r,s).

6) 验证ym′+r=rαsmodp,这里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.

最后,输出δ′={0,1}作为对δ的猜测.如果δ′=δ,则A1赢得游戏.

定义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一样.

UF-CMA-II:C和伪造者A2之间的交互游戏.

初始化.C运行系统设置算法得到系统参数params和系统主密钥s,之后将系统参数params发给A2,但保留主密钥s.

训练.A2进行的多项式有界次询问和定义6中IND-CCA2-II游戏的阶段1一样.

3 一个具体的EBMSC协议

3.1 初始化(Setup)

3.2 密钥生成(Extract)

3.3 广播多重签密(MultiSC)

2)h=H2(m,α).

4)Ci=m⊕H3(Wi).

5)μi=H4(m,Ti,TV,Wi).

6)βi=(ki(μi+Ti+hα)-ri) mod (p-1).

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).

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问题,这里:

params={p,g,l,PPub=ga,H1,H2,H3,H4},

同时将params发给A1.在交互游戏中,表L1到L4用于记录H1至H4的询问与应答值,Lk用于记录公私钥的询问与应答值.

阶段1.A1进行多项式有界次适应性询问.

H3询问:A1发出H3询问.C检查元组(Wi,h3)是否存在于L3表中,如果存在,则返回h3;否则,C随机选取h3∈R{0,1}l,然后将h3发给A1,记录(Wi,h3)到L3中.

私钥询问:A1询问身份IDi的私钥.假设已经询问过H1预言机.若ψ=0,则返回完整私钥xi=kiTimodp;否则,放弃仿真,之后将私钥添加到Lk中.

多重签密询问:A1可对任何消息m及签密人的身份IDi、接收者的身份IDV进行签密询问.假设在此之前已经做过Hash函数值询问和密钥提取询问.如果ψ=0,则正常执行多重签密算法;否则执行操作:

继续执行操作:

3) 计算Ci=m⊕H3(Wi).

4) 计算μi=H4(m,TV,Ti,Wi).

5) 计算βi=(ki(μi+Ti+hα)-ri) mod (p-1).验证：

是否成立.如果成立,则计算:

7) 输出σ=(α,β,h,Ti,TV,{C1,C2,…,Cn}).

则通过解签密;否则认为不合法.

阶段2.A1可以像阶段1那样进行多项式有界次适应性询问.但是要求身份IDV的私钥仍然不能被询问,此外不能做σ*的解签密询问.

作为CDH问题实例的解答,原因如下:

证毕.

定理2.在ROM中,如果没有任何多项式有界的敌手A2能以不可忽略的优势ε赢得定义6中的游戏IND-CCA2-Ⅱ(至多进行qi次Hi询问(i=1,2,3,4),qPK次公钥替换询问,qSK次私钥提取询问,qSC次签密询问,qUSC次解签密询问),则存在一个挑战者C能够至少以ε′的优势解决CDH问题,这里:

params={p,g,l,PPub=gs,H1,H2,H3,H4},

同时将params发给A2.在游戏中,表L1到L4用于记录H1至H4的询问与应答值,Lk用于记录公私钥的询问与应答值.

阶段1.除了部分私钥询问,其他询问同定理1.

阶段2.A2可以像阶段1那样进行多项式有界次适应性询问.但是要求身份为IDV的私钥仍然不能被询问,并且不能做关于σ*的解签密询问.

作为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至少能够以

的优势解决离散对数问题.

在交互游戏开始之时,游戏开始后,C运行Setup(1k),得到参数:

params={p,g,l,PPub,H1,H2,H3,H4},

并将params发给A1.在游戏中,表L1到L4记录H1至H4的预言机,Lk用于追踪公私钥的询问与应答值.

询问阶段.和定理1相同.

伪造. 对于不同的敌手伪造的过程不一样.

②PPub=ga.

调用预言机H1可以得到h1,输出:

作为离散对数问题实例的解答,原因如下:

分析C成功解决离散对数问题的概率,A1没做过IDi的私钥或部分私钥询问的概率为

③yi=gamodp.

分别调用预言机H2和H4得到h和h4.C输出:

作为离散对数问题实例的应答,因为:

⟺

分析C成功解决离散对数问题的概率,A2没有作过私钥询问的概率为1eqSK,σ*通过解签密验证的概率为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).

当从敌手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.而在理想模型中,Z输出f=1的概率总是等于0.换句话说,如果存在这样的伪造者F,Z总以可忽略的概率区分它是与(πEBMSC,A)交互还是与(FEBMSC,S)交互,故与定理5的假设矛盾.所以,不存在这样的伪造者F,也就是说,在UC安全框架下,协议πEBMSC满足选择消息攻击下的不可伪造性.

证毕.

5 性能分析

ElGamal型广播多重签密协议的计算开销主要集中在模指数和Hash函数运算.表1中E表示1次模指数运算,H表示1次Hash函数运算,M表示1 次乘法运算.本文方案与文献[30-33]中的方案效率比较如表1所示.从表1中看出,本文分案明显好于文献[30,32-33],并且本文还实现了广播多重签密功能.本文与文献[31]的效率相当, 但文献[31]只实现了多重数字签名,而本文方案不仅实现了多重签密功能,还在UC框架证明了该协议是安全的.

Table 1 Efficiency of this Paper Compared with Others References表1 本文方案与其他文献的效率比较

Notes: E: 1 exponential operation; M: 1 multiplication operation; H: 1 hash operation.

6 总 结

目前设计的ElGamal型广播多重签密协议的安全性一般是基于DL问题的难解性,虽然满足了不可伪造性,但是不具备签名者的身份验证,使得该类协议容易遭受多个签名者的联合攻击.本文设计了一个新的ElGamal型广播多重签密协议,由于本文是采用自认证方式来认证用户的公钥,克服了密钥管理问题以及能够抵抗文献[5-7]的攻击.在随机预言模型中证明了该协议在离散对数和CDH假设下是语义安全的.为了使所提协议适应更加复杂的网络环境,本文引入UC安全技术,而在UC安全框架下分析了该协议的安全性.我们定义了ElGamal型广播多重签密协议的理想函数FEBMSC,进而证明了UC安全的ElGamal型广播多重签密协议的通用可组合安全性.下一步将对集合相交协议进行研究.