基于格的前向安全无证书数字签名方案

徐 潜 谭成翔 冯 俊 樊志杰 朱文烨

(同济大学电子与信息工程学院计算机科学与技术系 上海 201804)

(1062842783@qq.com)

摘 要:无证书签名方案利用密钥生成中心与用户共同生成签名密钥的方式,解决了传统的基于身份的数字签名方案中存在的密钥托管问题.目前,针对无证书签名方案的研究还存在3点可以改进的地方:1)已有的基于随机格构建的无证书签名方案,虽然具有后量子安全性,但都是建立在随机预言模型下,尚无针对标准模型的相关研究;2)已有的格基无证书签名方案大多只考虑外部敌手,缺乏抵御不诚实用户攻击的能力;3)已有的无证书签名方案均需要保证用户密钥是绝对安全的,无法解决密钥泄露问题.针对这3点不足,在随机预言模型下的前向安全的无证书格基签名方案的基础上,首次提出了标准模型下可证明安全的基于随机格的前向安全无证书数字签名方案,并在不引入第三方代理的前提下同时解决了密钥泄露和密钥托管问题.在面对不诚实的用户和恶意密钥生成中心2类强敌手的情况下,利用小整数解SIS假设证明了所提出的方案具有适应性选择消息、选择身份攻击下的前向安全强不可伪造性.

关键词:格基数字签名;无证书;前向安全;随机预言模型;标准模型

传统的基于公钥基础设施(public key infrastr-ucture, PKI)的公钥密码系统通过引入证书管理机构CA为用户颁发数字证书,并鉴权用户身份.然而,证书的更新、撤销等管理操作给系统带来较大的运行负荷.为了消除证书管理带来的昂贵开销,Shamir[1]于1984年提出了身份基加密的思想,利用用户唯一的公共标识ID作为用户的公钥,由密钥生成器(private key generator, PKG)为用户生成密钥.目前已有很多高效的身份基签名方案[2-5],如Yao等人[2]利用拉格朗日插值公式,在随机格的基础上构建了允许模糊身份验证的身份基签名方案.以及Wei等人[3]提出的门限身份基签名方案等.然而,由于用户密钥完全由PKG生成,对PKG可见,一旦PKG受到污染,整个系统中的用户都将不再安全,这就产生了密钥托管问题(key escrow).

Al-Riyami等人[6]在2003年首次定义了无证书公钥密码学的概念,用来解决密钥托管问题并消除证书管理的开销.无证书密码学的核心思想为:密钥生成中心(key generation centre, KGC)为用户派发部分密钥,用户自己负责剩余密钥,即私密值的生成,用户完整的签名密钥由部分密钥和私密值共同组成.由于KGC无法获取用户的私密值,也就无法知晓用户的完整密钥,从而消除了恶意KGC带来的安全隐患,解决了密钥托管问题.无证书密钥方案可以用于移动环境下用户敏感数据的保护或者高效的授权认证等领域.

基于Al-Riyami的思想,很多无证书数字签名方案被陆续提出[7-15].这些方案的安全性都是基于传统数论难题,如离散对数和大整数分解等.然而随着量子计算机的发展,基于传统数论难题的密码方案的安全性受到了挑战.事实上,早在1997年,Shor[16]就提出了多项式时间内解决离散对数和大整数素分解的量子算法.因此,构建能够抵御量子攻击的后量子安全的无证书签名方案就具有十分重要的意义.为此,Kim等人[17]和Tian等人[18]设计了基于格的无证书签名方案,并通过小整数解(short integer solution, SIS)问题证明了方案的安全性.但是他们的方案以及安全证明都是基于随机预言模型,在实际应用中,很难保证诸如Hash函数等对象可以按照在随机预言证明中所假设的那样,实现完全的随机化,从而难以保证系统的实际安全性[19].同时,他们的方案只考虑外部敌手,忽视了来自于内部不诚实签名用户的威胁.

更进一步地,在移动环境下特别是随着手机等移动端的大量使用,由于用户的不安全行为,一旦移动设备被攻击,存储在设备中的用户签名密钥将很容易被窃取,即存在密钥泄露问题.目前后量子安全的无证书签名方案[17-18]等均假设用户密钥是绝对安全的,缺乏有效解决密钥泄露问题的能力.同时,基于传统数论难题的无证书签名方案虽然考虑了密钥泄露问题,但主要通过引入第三方代理来更新用户密钥,不仅增加了系统的复杂度,而且,由于第三方代理的安全性无法保证,系统的安全隐患也随之增加.

综上所述,目前无证书签名方案存在3个问题:

1) 已有基于格的后量子安全的无证书签名方案仅仅基于随机预言模型,无法保证实际应用中的系统安全性;

2) 已有无证书签名方案的安全证明主要考虑外部敌手和恶意密钥生成中心,而对来自于不诚实的签名用户的威胁抵抗能力不足;

3) 目前无证书签名方案还无法在不引入第三方代理的前提下解决密钥泄露问题.

针对这3个主要问题,本文利用格基委派技术,基于随机格理论,首先在随机预言模型下引入了前向安全的无证书数字签名方案RO_LFC_SIG,并在此基础上,设计了第1个标准模型下可证安全的前向安全无证书ST_LFC_SIG方案.

本文的主要贡献有4个方面:

1) 针对不诚实的用户和内部恶意KGC攻击者,首次形式化定义了前向安全强不可伪造性的安全模型.与文献[8,18,20-21]中的安全模型相比,不仅增加了针对密钥泄露的前向安全性部分,而且将外部敌手增强为不诚实的签名用户,使得方案安全性更高.

2) 首次具体实现了基于格的前向安全无证书签名方案,将前向安全与无证书方案基于随机格结合,在不引入第三方代理的条件下同时解决密钥泄露和密钥托管问题,且具有后量子安全性.

3) 提出的ST_LFC_SIG无证书签名方案不仅具有前向安全性,也是首个在标准模型下可证安全的格基无证书签名方案,与文献[17-18]中的格基签名方案相比,安全性更高.

4) 分别在随机预言模型和标准模型下,利用随机格的小整数解SIS难题,证明了提出的2个签名方案在面对2类强敌手时,具有适应性选择消息、选择身份攻击的前向安全强不可伪造性(forward secure and strongly existentially unforgeable against adaptive chosen message and adaptive chosen identity attack, FSU-AMAIA);通过与已有的格基签名方案和无证书签名方案进行安全性和效率的对比,证明本文方案在保证较低的渐近性复杂度的同时,达到了更好的安全性.

1 相关工作

无证书数字签名方案的研究目前已有很多,例如Yu等人[7]就是利用双线性对构造了无证书签名方案;Guan等人[8]通过应用公钥替换攻击证明了Yu等人[7]方案并不是存在不可伪造的;Yeh等人[9]通过椭圆曲线设计了无证书签名方案,但是只考虑了第三方敌手的攻击;陈虎等人[10]将无证书签名与群签名结合,基于双线性对设计了高效的无证书群签名方案,实现了群成员的动态更新;Choi等人[12]基于计算性Diffie-Hellman假设(computational Diffie-Hellamn, CDH)构造了高效的无证书签名方案,但主要实现了存在不可伪造性而非强不可伪造;Huang等人[13]构造了能够抵御2类强敌手的无证书签名方案,并基于提出的签名方案设计了身份鉴权协议;Tso等人[14]基于CDH假设并针对公钥替换攻击问题设计了强不可伪造的无证书签名方案;同样基于CDH假设的还有Chen等人[15]的方案.以上的无证书签名方案[7-15]都是基于传统数论难题的,不具备后量子安全性;Kim等人[17]和Tian等人[18]设计了基于格的随机预言模型下可证安全的无证书签名方案,并通过小整数解SIS问题证明了方案的存在不可伪造性;文献[17-18]的方案实现了后量子安全的无证书签名方案,但是随机预言模型无法保证方案的实际安全性,其安全证明也只考虑了外部敌手,没有针对不诚实用户的安全性分析.同时,文献[17-18]的签名方案依赖于绝对安全的用户密钥,因此存在密钥泄露问题.

解决密钥泄露问题的一种有效的方法是构建前向安全的公钥密码系统.针对密钥泄露的前向安全性是指,某一个时刻用户密钥的泄露不会危及之前任意时刻的方案的安全性.在前向安全的数字签名研究方面,目前采用的主要思想是构建不可逆的密钥更新算法.已有很多前向安全的签名方案[22-25],例如Yu等人[22]的方案;Ebri等人[23]赋予用户指定密钥更新时间的能力;文献[24]则将前向安全与门限签名相结合,利用周期性密钥更新和群组门限同时保证密钥的安全性;文献[25]中利用时间序列树等实现了前向安全的细粒度属性控制.但同很多无证书密码方案一样,这些前向安全的签名方案仍然是基于双线性对等数学难题,不具有抗量子计算攻击的能力;Zhang等人[20]设计了首个基于格的前向安全的签名方案FSIBS,其主要的思路是建立在Rückert[26]的分层的身份基签名方案的基础上,利用格基委派算法实现密钥的前向更新;然而同文献[17-18]中的方案一样,Zhang等人[20]的方案也仅仅实现了随机预言模型下的证明;而且Zhang等人[20]的方案只考虑了外部敌手,不具备抵抗恶意KGC攻击的能力,安全模型也仅考虑了存在不可伪造性而缺乏针对前向安全性的形式化定义;Li等人[27]仍然基于双线性对考虑了前向安全与无证书方案的结合问题,没有给出安全模型的形式化定义,而且文献[27]通过引入第三方代理实现前向安全性,增加了方案复杂度,也没有证明当第三方代理受到攻击时方案的可靠性.

2 预备知识

标识与记号:设q为正素数,q表示]范围内的整数.表示向量vl2范数.本文中使用标准的O记号表示函数的复杂度上界,即g(n)=O(f(n))当且仅当存在正常数cn0,使得对任意的nn0有成立.相应地,定义下界复杂度记号ω,即g(n)=ω(f(n))当且仅当存在正常数cn0,使得对任意的nn0有成立.定义关于n的可忽略函数negl(n),使得对任意多项式g(n),当n足够大时都有.如果概率p=1-negl(n)则称概率是压倒性成立的,若p=negl(n),则称概率是可忽略的.

定义1. 小整数解问题SIS[28]:给定一个正整数q,随机矩阵Aq,实数β,定义(q,m,β)上的SIS问题PSIS(q,m,β)是:找到非0向量vm,使得Av=0 mod q并且β.Micciancio等人[29]已经证明,对任意多项式有界的,平均情况下的PSIS(q,m,β)问题与解决最坏情况下格上的近似独立向量问题是同等困难的.

引理1[28]. 设表示参数为σ且中心为0的离散正态分布,向量,则以压倒性概率成立.α为正实数,vm,如果,则,其中的概率密度为2).

引理2[28]. 无抽样技术:若签名人从某个随机分布中抽取y,签名的目标分布为f(x),与签名人私钥sk无关,实际分布为g(x),可能与sk有关,且对于任意x及某个正实数Mf(x)≤Mg(x).则以概率f(y)Mg(y)输出签名y将使得y服从分布f(x).

由引理1,若设M=e12α+12α2,以(y)输出签名y,则y服从于分布且以压倒性的概率满足.

引理3. 陷门生成算法[30]:设q≥3,m≥5n lb q,存在有效的多项式时间算法TrapGen在多项式时间内生成统计接近于n×mq上随机分布的矩阵A以及整数格Λ(A)的短基TAm×m,设Gram-Schmidt正交化后为A,则以压倒性概率成立.

引理4. 原像抽样算法[31]:设q≥3,mO(n lb q),随机矩阵An×mq以及整数格Λ(A)的短基TAm×m,设高斯参数,那么对任意的u,存在有效的多项式时间算法SamplePre(A,TA,s,u),统计近似于从离散高斯分布GΛu(A),s中抽取向量vΛu(A).由高斯分布的性质,v将以压倒性的概率满足.其中Λu(A)={em:Ae=u mod q}.可以很容易的扩展到矩阵的原像抽样算法,即:

对任意的矩阵Un×k,其余参数与基本的原像抽样算法相同,存在扩展的多项式时间算法SamplePre(A,TA,s,U),统计近似于从离散高斯分布GΛU(A),s中得到矩阵VΛu(A),且AV=U mod q.同时以压倒性概率成立.

引理5. 格基委派算法[32]:设q上小范数可逆矩阵(按离散高斯分布独立抽取每一列)的集合为Dm×m,矩阵An×mq,整数格Λ(A)的短基TAm×m,高斯参数,矩阵RDm×m,存在多项式时间算法BasicDel(A,R,TA,s)输出格Λ(B=AR-1)的短基).且不存在多项式时间BasicDel的求逆运算.存在多项式时间算法SampleRwithBasis(A)输出矩阵RDm×m以及格Λ(B=AR-1)的短基).存在确定性的多项式算法ExtBasis(F=A|C,TA)输出A|C对应的整数格Λ(A|C)的基TF,且.

定义2. 本文提出的数字签名方案包括5个多项式时间算法:

1) 系统建立Setup.由密钥生成中心KGC运行,输入安全参数n,输出系统公共参数PP和主密钥MSK.

2) 用户密钥提取KeyExtract.由KGC与用户交互完成,输入公共参数PP、用户ID、主密钥MSK以及当前时刻t,输出用户公钥、用户私钥.

3) 密钥更新算法Update.输入用户当前ID与更新的时间区间,KGC与用户交互完成密钥更新.

4) 签名算法Sign.输入系统公共参数、用户公钥与私钥、待签名消息、输出签名.

5) 验证算法Verify.输入系统公共参数、签名消息、用户公钥与用户ID以及签名,算法判断该签名是否是有效签名.

定义3. 前向安全强不可伪造性FSU-AMAIA:定义2类多项式时间强敌手:1)强敌手A1模拟内部不诚实的用户,不诚实的用户指在签名过程中,会在未获得合法部分密钥的情况下尝试伪造自己或其他用户的签名,显然,伪造自身某一时刻的签名需要的安全性更高;2)强敌手A2模拟恶意的密钥生成中心KGC,在文献[8,18]中提出的安全模型的基础上,给出针对2类强敌手的安全游戏Game1与Game2,如果敌手A1与A2分别赢得Game1和Game2的概率是可忽略的,则称签名方案在适应性选择消息、选择身份攻击下对强敌手是前向安全强不可伪造的,游戏Gameb,b∈{1,2}具体描述如下.

1) 系统建立Setup.输入安全参数n,挑战者C生成系统公共参数PP与主密钥MSK,如果b=1,CPP发送给敌手A1,否则,将PPMSK一起发给A 2.

2) 敌手适应性的进行如下问询.

① 公钥问询:敌手提交{ID,t},挑战者返回相应的公钥回答问询.

② 密钥问询:敌手Ab提交{ID,t},如果b=1,挑战者C生成用户的部分签名密钥并发送给敌手.同时,敌手可以问询除自己之外的其他用户的私密值.注意如果{ID,t}对应的公钥发生过替换,挑战者返回⊥.如果b=2,密钥问询只包括私密值问询,挑战者返回私密值给敌手.

③ 公钥替换问询:敌手可以替换任意身份下的公钥.

④ 密钥更新问询:敌手Ab提交更新时间区间与身份,挑战者返回更新后的密钥作为应答.

⑤ 签名问询:敌手Ab问询关于任意消息的签名,挑战者生成消息的签名并返回给敌手.注意如果相应的公钥被敌手替换过,则敌手需要提交对应的私密值.

敌手Ab可以选择变更用户身份或签名时刻并问询密钥和签名,也可以直接进入伪造阶段.

3) 伪造Forgery.敌手Ab输出以身份ID*,时刻t*下的关于消息μ*的签名e*,敌手Ab赢得游戏当且仅当:

Verify(ID*,e*,μ*,t*)=Accept;

② 若b=1,(ID*,t*)未作为密钥问询的输入;若b=2,(ID*,tt*)未作为私密值问询的输入;

③ 若b=1,(ID*,ti,t*)未作为密钥更新问询的输入;若b=2,(ID*,ti,tjt*)未作为密钥更新问询的输入;

④ 若b=2,(ID*,tt*)未作为公钥替换问询的输入;

e*未作为签名问询的应答返回给敌手.

若敌手Ab获胜的概率为AdvAb=Pr[Forgery(ID*,e*,μ*,t*)=Success],则当且仅当AdvAb关于安全参数n是可忽略的时,签名方案是适应性选择消息、选择身份攻击下前向安全强不可伪造FSU-AMAIA安全的.

3 随机预言模型下的签名方案RO_LFC_SIG

本节给出随机预言模型下的前向安全的格基无证书数字签名方案RO_LFC_SIG,作为构建标准模型下前向安全无证书签名方案的基础.RO_LFC_SIG方案具体包括5个多项式时间的算法.

1) 系统建立Setup.设n为安全参数,实数M>0,α>0,k,λ,T为正整数,素数q≥3.设正整数,取3个抗碰撞的Hash函数:H1:{0,1}*n×kqH2:{0,1}*Dm×m}.

KGC运行〈A,TA〉=TrapGen(n,q,m),得到近似随机矩阵An×mq及整数格Λ(A)的基).设高斯参数,参数序列{σ0,σ1,…,σT},其中σ0=ω(lb m),σim3i2ω(lb m)2i+1.设离散正态分布参数.随机矩阵Bn×mq.

KGC公布公共参数PP={A,B,H1,H2,H3},主密钥MSK={TA}.

2) 密钥提取KeyExtract.给定PPID、密钥生

成时刻t0∈[1,T],KGC生成部分密钥:Tt0A=BasicDel(A,H2(ID|t0),TA,σt0),其中Tt0A为整数格的短基,且有.

KGC选取从高斯分布中抽取随机矩阵Ct0ID,且.之后调用得到,且满足.则用户ID在时刻t0的部分密钥为2m×kq.

用户从离散高斯分布中随机采样矩阵Xt0ID作为私密值.

因此,用户ID在时刻t0的完整密钥为m×3kq.公钥为n×kq.

3) 密钥更新KeyUpdate.假设密钥更新时间区

间为,设矩阵).KGC运行:TtiA=BasicDel(Atj,H2(ID|ti)H2(ID|ti-1)H2(ID|ti-2)…H2(ID|tj+1),TtjA,σti),以及SamplePre(Ati,TtiA,s,H1(ID|ti)-ACtiID)得到StiID.则时刻ti用户的密钥为,其中为用户从中随机采样得到.

关于高斯参数σti的选取:由引理5,有 m)2,若取σ0=ω(lb m),则有σtim3ti2ω(lb m)2ti+1.由引理1,可以得到.

4) 签名算法Sign.设待签名消息为μ∈{0,1}*,用户公钥,私钥.用户随机选取向量3m,其中.

3mε=x+y,以概率输出签名(ε,h).

5) 验证算法Verify.输入(ID,(ε,h),μ,t),算法输出Accept当且仅当:

.

正确性:

① 由引理2,签名统计不可区分于分布,从而以压倒性概率成立;

.

4 RO_LFC_SIG的安全性分析

本节基于SIS假设证明随机预言模型下方案的前向安全强不可伪造性.不失一般性,设敌手的问询时刻为[1,T]区间上的连续值,时刻t0=1.设Q为总的问询身份数,TSam,TBas,TTrap,TSamRwithBas,TExt为算法,BasicDel,TrapGen,SampleRwithBasis以及ExtBasis运行时间,Tmul为一次m×m矩阵乘法的近似运行时间.

定理1. RO_LFC_SIG方案对于第1类强敌手的前向安全强不可伪造性FSU-AMAIA基于小整数解假设).具体地,令A1为第1类多项式时间敌手,若AdvA1=ξ为不可忽略的,则有多项式算法,在至多τ′=τ+TQ(TSam+TSamRwithBas+(T+2)Tmul)+(T-t*)TBas的时间内以概率AdvB=ξ(1-2-ω(lb n))TQ解决问题,其中τGame1运行时间.

证明. 假设存在敌手A1可以伪造签名,则可以如下构造多项式算法.

1) 系统建立Setup.设安全参数为n,实数M>0,α>0,正整数,素数).取抗碰撞的Hash函数}.高斯参数s,δ,{σ0,σ1,…,σT}与RO_LFC_SIG方案中相同.

挑战者C随机选择A0∈n×mq为SIS实例,随机矩阵Bn×mq,维护4个Hash列表LH1,LH2,LH3,Lsig.C从Gmq,s逐列采样选取t*个可逆的小范数矩阵Rim×mq,并设A=A0Rt*Rt*-1R1γ∈[1,Q].

C将公共参数PP={A,A0,B,H3}发送给敌手A1.

2) 敌手可以适应性的进行如下问询.

H2问询:敌手提交{ID,ti},C查找列表LH2判断是否有对应的Hash值,若有,则直接作为敌手的应答返回敌手,否则,设Dm×mq上的小范数可逆阵集合.若ID不为第γ次问询身份,C调用多项式时间函数〈R,TtiAR〉=SampleRwithBasis(A)生成RDm×m以及Λ(AR-1)的基TtiARm×m,C设置H2(ID|ti)=R并将其返回给敌手作为应答.同时,将{TtiAR,R}插入到列表LH2中.

ID为第γ次问询身份,tit*,C直接令H2(ID|ti)=RtiTtiAR=⊥,将H2(ID|ti)=Rti返回给敌手,并将{TtiAR,Rti}插入到LH2中.

ID为第γ次问询身份,ti=t*+1,C调用SampleRwithBasis(A0)生成RDm×mTtiARm×m.C设置H2(ID|t*+1)=R并将其返回给敌手作为应答.同时,将{TtiAR,R}插入到列表LH2中.

ID为第γ次问询身份,ti>t*+1,C从Dm×m中随机采样得到H2(ID|ti),由H2(ID|t*+2),Tt*+1AR,σti)得到TtiAR.之后将H2(ID|ti)返回给敌手并将{TtiAR,H2(ID|ti)}插入到LH2中.

H1问询:敌手提交{ID,ti},C查找列表LH1判断是否有对应的Hash值,若有,则直接作为敌手的应答返回敌手,否则,C从离散高斯分布中逐

列采样得到CtiID,且以绝对优势成立.

ID不为第γ次问询身份,C查找列表LH2中的表项{TtiAR,H2(ID|ti)},若不存在,则首先进行H2问询.之后C调用得到,其中Mn×kq为随机矩阵.从而H1(ID|ti)=M+ACtiID,C将H1(ID|ti)保存到LH1中并作为敌手的应答.同时,将部分密钥保存到Lsig中.

ID为第γ次问询身份,tit*,C从列采样得到StiID,并将保存到Lsig中.同时将H1(ID|ti)=A0(StiID+CtiID)作为应答,并保存到LH1中.

ID为第γ次问询身份,tit*+1,C从列表LH2中取得{TtiAR,H2(ID|ti)},由得到,保存到LH1中并返回给敌手,保存到Lsig中.

③ 部分密钥问询:敌手提交{ID,t},需要满足H1问询已经执行,否则先执行H1问询.若ID不为第γ次问询身份,或者tt*,C查找列表Lsig并返回部分密钥;否则C退出.

④ 私密值问询:敌手提交对应于其他用户的{ID,t},C从离散高斯分布中逐列采样得到私密值,且以绝对优势成立.C将插入Lsig并作为A1私密值问询的应答.

⑤ 公钥问询:敌手提交},其中为敌手自己选取的私密值或之前经过私密值问询获得的其他用户的私密值.C验证是否成立,若不成立则拒绝敌手.否则,C查询Lsig并验证{ID,t}对应的部分密钥是否存在,若不存在,需提前进行部分密钥问询,并将{ID,t}作为部分密钥问询输入.之后挑战者C返回n×kq并将公钥和敌手提交的合法私密值保存到Lsig中.

⑥ 密钥更新问询:敌手提交[tj,ti]和ID,需要满足已经对{ID,ti}进行H1问询.若ID不为第γ次问询身份,或者tit*,C直接将返回给敌手;否则,C退出.

⑦ 公钥替换问询:敌手提交{ID,t}以及,C查找表Lsig并替换{ID,t}对应的公钥.

H3问询:C查找列表LH3并判断否已经存在,若存在则直接作为敌手的应答,否则,从k}中随机选取h作为应答并保存到LH3中.

⑨ 签名问询:敌手A1提交{ID,t,μ},C查找LH3,Lsig得到对应的密钥与h,之后正常签名并应答敌手.如果{ID,t}对应的公钥发生过替换,则A1需要提交对应的私密值.

3) 伪造Forgery.A1输出消息μ*在{ID*,t*}下的伪造签名(ε*,h*),当且仅当ID*为第γ次问询身份且Verify(ID*,(ε*,h*),μ*,t*)=Accept时敌手成功.根据一般分叉引理[21],敌手可以以不可忽略的概率输出另一个有效伪造签名(ε′,h′),因此有,且At*=A0.即.由于,因此‖‖≤以压倒性概率成立.

由原像抽样函数与最小熵性的概率至多为1-2-ω(lb n),因此,算法B成功解决问题的概率为AdvB=ξ(1-2-ω(lb n))TQ,总时间为τ′=τ+TQ(TSam+TSamRwithBas+(T+2)Tmul)+(T-t*)TBas.

证毕.

定理2. RO_LFC_SIG方案对于第2类强敌手的前向安全强不可伪造性FSU-AMAIA基于小整数解假设).具体地,令A2为第2类多项式时间敌手,若AdvA2=ξ为不可忽略的,则有多项式算法B,在至多τ′=τ+TQ(TSam+2Tmul)的时间内以概率AdvB=ξ(1-2-ω(lb n))TQ解决问题,其中τGame2运行时间.

证明. 假设存在敌手A2可以伪造签名,则构造多项式算法步骤如下.

1) 系统建立Setup.设n,k,λ,T,M,α,m,L,s,t*,γ,β,q,δ以及参数序列{σ0,σ1,…,σT}与定理1中一样.3个抗碰撞的Hash函数H1,H2,H与RO_LFC_SIG方案中一样.〈A,TA〉=TrapGen(n,q,m).随机矩阵Bn×mq为SIS实例,维护2个Hash列表LH3,LsigLsig中的表项为}.

挑战者C将公共参数PP={A,B,H1,H2,H3}与主密钥MSK={TA}发送给敌手A2.

2) 敌手可以适应性的进行如下问询.

① 私密值问询:敌手提交{ID,t},C查找列表Lsig,若{ID,t}对应的私密值已经存在,直接将其返回给敌手,否则,C从离散高斯分布中逐列采样得到私密值,且以绝对优势成立.C将插入Lsig.若ID不为第γ次问询,或ID为第γ次问询但作为A2问询的应答.若ID为第γ次问询且t=t*,C退出.

敌手A2已知主密钥MSK,因此不需要进行部分密钥问询.部分密钥的更新也可以由敌手自己完成.

② 公钥问询:敌手提交{ID,t},若{ID,t}对应的私密值不存在,则先进行私密值问询.之后,挑战者C返回,敌手A2可以生成完整的公钥n×kq.

③ 公钥替换问询:敌手提交{ID,t}以及,挑战者查找表Lsig并替换{ID,t}对应的公钥.若ID为第γ次问询且t=t*,C退出.

H3问询:与定理1相同.

⑤ 签名问询:敌手A2提交,CtID,μ},C可以通过以及验证的合法性.若提交的部分密钥合法,C查找LH3,Lsig得到对应的,之后正常签名并应答敌手.

3) 伪造Forgery.敌手输出消息μ*在{ID*,t*}下的伪造签名(ε*,h*),当且仅当ID*为第γ次问询身份且Verify(ID*,(ε*,h*),μ*,t*)=Accept时敌手成功.同定理1一样,根据一般分叉引理[21],敌手可以以不可忽略的概率输出另一个有效伪造签名(ε′,h′),因此有,即0.与定理1一样,‖以不可忽略的概率成立.

由原像抽样函数与最小熵性的概率至多为1-2-ω(lb n),因此,算法B成功解决问题的概率为AdvB=ξ(1-2-ω(lb n))TQ,总时间为τ′=τ+TQ(TSam+2Tmul).

证毕.

5 标准模型下的签名方案ST_LFC_SIG

随机预言模型下RO_LFC_SIG签名方案的安全性依赖于方案所采用的Hash函数的完全随机性,这在实际应用中可能无法满足.因此,为了增强格基前向安全的无证书签名方案的应用性与安全性,我们在RO_LFC_SIG的基础上,研究了基于标准模型的ST_LFC_SIG方案.本节给出方案的具体实现.

需要注意的是,本文提出的ST_LFC_SIG方案是第1个标准模型下基于格的无证书数字签名方案,方案具体由5个多项式时间的算法构成.

1) 系统建立Setup.设安全参数为n,实数M>0,α>0,设正整数k,b,d,l,T,素数q≥3,m≥5n lb q).高斯参数s,参数序列{σ0,σ1,…,σT}以及矩阵〈A,TA〉与RO_LFC_SIG方案相同.离散正态分布参数.设抗碰撞的Hash函数:H1:{0,1}*→{0,1}dH2:{0,1}*×{0,1}*→{0,1}l.

取2Td个矩阵,其中i∈[1,d],j∈[1,T],b∈{0,1}.设随机均匀小范数矩阵Cin×kq,i∈[1,d];Fin×mq,i∈[1,l].

公共参数;主密钥MSK={TA}.

2) 密钥提取KeyExtract.给定用户身份ID,起始时刻t0∈[1,T].KGC运行h=H1(ID|t0),.由TAC=ExtBasis(A|CID|t0,TA)得到[A|CID|t0]的短基TAC.KGC调用得到发送给用户作为部分密钥.

用户验证否成立.

若用户ID为第1次生成密钥,运行〈B,TB〉=TrapGen(n,q,m)得到密钥根矩阵〈B,TB〉.

用户计算,由得到时刻t0公钥n×mq和私密值.

用户时刻t0私钥(2m+km.

3) 密钥更新KeyUpdate.假设密钥更新时间区间为.KGC计算h=H1(ID|ti)和,之后调用KeyExtract算法得到(m+km作为时刻ti的部分密钥并发送给用户.

用户计算h=H1(ID|t),对t∈[tj+1,ti],有,并代入到公式中得到时刻ti的私密值以及公钥.

4) 签名算法Sign.输入用户公钥,私钥、待签名消息μ∈{0,1}*.随机选取向量.设,用户计算,并设.

以概率输出签名(ε,x).

5) 验证算法Verify.输入(ID,(ε,h),μ,t),算法输出Accept当且仅当:

③ 验证者计算CID|t并代入验证等式.

正确性:由引理5,签名(ε,x)统计不可区分于离散正态分布,从而以压倒性概率成立;由引理,且x3,则②成立.根据以及可以代入Verify中验证③成立.

6 ST_LFC_SIG的安全性分析

定理3. ST_LFC_SIG方案对于第1类强敌手的FSU-AMAIA安全性基于小整数解假设).具体地,令A1为第1类多项式时间敌手,若AdvA1=ξ为不可忽略的,则有多项式算法B,在至多τ′=τ+TQ(2TSam+TBas+TTrap+TSamRwithBas+(Td+2)Tmul)的时间内以概率AdvB=ξ(1-2-ω(lb n))TQ解决问题,其中τGame1运行时间,k,d定义与ST_LFC_SIG中相同.

证明. 假设存在敌手A1可以伪造签名,则构造多项式算法步骤如下.

1) 系统建立Setup.设n,M,α,k,b,d,l,T,q,m,L,δ,H1,H2,参数序列{σ0,σ1,…,σT}以及2Td个矩阵与ST_LFC_SIG方案相同,.

i∈[1,d],从分布Gm,s中逐列采样得到小范数矩阵Dim×kq,且以压倒性概率成立.设正整数pi,〈E,TE〉=TrapGen(n,q,k),Ci=ADi+piE,其中随机矩阵An×mq为SIS实例.则Ci统计不可区分于n×kq上的随机均匀矩阵.对i∈[1,l],设Fin×mq为随机均匀矩阵.

维护Hash表Lsig,表项为,其中b∈{0,1}为标记位,初始化为0.

挑战者C将发给敌手A1.

2) 敌手可以适应性地进行如下问询.

① 部分密钥问询:敌手提交{ID,t},挑战者计算,其中.

如果p=0 mod q第1次出现,C随机生成(m+km上的矩阵并返回给敌手作为部分密钥应答,设置Lsig中{ID,t}对应表项的b=1.若p=0不为第1次出现,C终止游戏.

p≠0,挑战者C从Gm,s中逐列采样得到矩阵m×m.由于TEΛ(pE)的短基,C可由得到,从而m×m.将作为部分密钥应答返回敌手.显然,将保存于Lsig中.

② 公钥和私密值问询:敌手提交{ID,t},挑战者可以调用方案的KeyExtract的正常计算并回答敌手(若t>1需要运行KeyUpdate的公钥和私密值更新部分).同时将公钥和私密值保存到Lsig中.注意敌手仅需要对其他用户进行公钥和私密值问询,其自己的公钥和私密值可以由敌手自己生成.

③ 密钥更新问询:敌手提交[tj,ti]和ID,挑战者C调用部分密钥问询并以{ID,ti}作为输入进行部分密钥更新.如果游戏没有终止,且ID对应于敌手之外的用户,则挑战者C调用KeyUpdate算法完成公钥和私密值更新.

④ 公钥替换问询:敌手提交{ID,t}以及,挑战者查找表Lsig并替换{ID,t}对应的公钥.

⑤ 签名问询:敌手提交},C验证是否成立且是否为对应的整数格的基,若不是,则拒绝敌手.否则,如果Lsig中{ID,t}的表项存在且b=0,则C将Lsig中保存的代入Sign算法对消息μ进行签名并回答敌手.若{ID,t}对应表项不存在,C先以{ID,t}为输入跳转到部分密钥问询,更新Lsig中的{ID,t}表项之后再进行签名问询.同时,C将公钥和私密值保存到Lsig对应表项中.

若{ID,t}表项存在,但b=1,C终止游戏.

3) 伪造Forgery.敌手输出消息μ*在{ID*,t*}下的伪造签名(ε*,x*),敌手成功当且仅当{ID*,t*}恰为Lsig中的标记项b=1且Verify(ID*,(ε*,x*),μ*,t*)=Accept.将CID*|t*=AD代入到Verify算法中可以得到方程,即.如果(ε*,x*)为正确的伪造,那么以压倒性概率成立,同时,因此有以压倒性概率成立.游戏模拟的时间上限为τ′=τ+TQ(2TSam+TBas+TTrap+TSamRwithBas+(Td+2)Tmul).由原像抽样函数和最小熵性质,的概率至多为1-2-ω(lb n),因此算法B成功解决问题的概率为AdvB=ξ(1-2-ω(lb n))TQ.

证毕.

定理4. ST_LFC_SIG方案对于第2类强敌手的FSU-AMAIA安全性基于小整数解假设).具体地,令A2为第2类多项式时间敌手,若AdvA2=ξ为不可忽略的,则有多项式算法B,在至多τ′=τ+TQ(TSam+TBas+T×TSamRwithBas+(Td+2)Tmul)的时间内以概率AdvB=ξ(TQ-t*)(1-2-ω(lb n))TQ(TQ-1)解决问题,其中τGame2运行时间.

证明. 假设存在敌手A2可以伪造签名,则构造多项式算法步骤如下.

1) 系统建立Setup.设设n,M,α,k,b,d,l,T,q,m,L,δ,H1,H2,参数序列{σ0,σ1,…,σT},参数s,δ与定理3中一样.〈A,TA〉=TrapGen(n,q,m).设i∈[1,d],随机均匀小范数矩阵Cin×kq.对i∈[1,l],逐列从Gm,s中采样得到Dim×mq,则Fi=B0Di统计不可区分于n×mq上的随机均匀分布,其中随机矩阵B0为SIS实例.

维护Hash表Lsig,表项为,其中X为用户ID的密钥根矩阵,TXΛ(X)的基.

算法1. 生成Td个矩阵算法.

① Set γ∈[1,Q],t*∈[1,T] *ID*为第r次秘钥问询对应的身份*

② Foreach tt*do

h=H1(ID*|t);

⑥ End Foreach

B=B0RID*|t*RID*|t*-1RID*|1*BID*对应的秘钥根矩阵*

B′=B0;

⑨ For j=t*+1 to T

h=H1(ID*|j-1);

SampleRwithBasis(B′);

End For

剩余dTDm×m上的随机均匀矩阵.

C公布,并将主密钥MSK={TA}一起发给敌手A2.

2) 敌手可以适应性地进行如下问询.

① 公钥问询:敌手提交{ID,t},若ID不为第γ次问询身份,挑战者C首先查询表Lsig看是否有对应于身份ID的密钥根矩阵.如果没有,由SampleRwithBasis(B)得到RDm×mΛ(BR-1)的基TBR,C将BR-1作为当前身份ID的密钥根矩阵,并将其和TBR一起保存到Lsig中.C调用签名方案的KeyExtractKeyUpdate(t>1)算法正常计算用户的公钥应答.

ID为第γ次问询身份且tt*,设,将作为敌手的公钥问询应答.

ID为第γ次问询身份且tt*+1,设得到的基.将为公钥返回敌手,并与私密值一起保存到Lsig中.可以看出,的密钥根矩阵依然为B.

② 私密值问询:敌手提交{ID,t},若ID不为第γ次问询身份或tt*+1,需要满足敌手已经进行过公钥问询,并得到私密值,否则先进行公钥问询,之后C从表Lsig中取出返回敌手.若ID为第γ次问询身份且tt*,C退出.

敌手A2已知主密钥MSK,因此不需要进行部分密钥问询.部分密钥的更新也可以由敌手自己完成.

③ 私密值更新问询:若ID不为第γ次问询身份时,敌手公钥和私密值均正常生成,因此挑战者C可以直接调用KeyUpdate算法完成更新.

ID为第γ次问询身份,设更新区间[tj,ti],若tjt*ti>t*tj,C可以查表Lsig得到时刻t′=max(tj,t*+1)的公钥和私密值,之后可以调用KeyUpdate算法在[t′,ti]上完成更新.若t*ti,C退出.

④ 公钥替换问询:敌手提交{ID,t}以及,挑战者C查找表Lsig并替换{ID,t}对应的公钥.若ID为第γ次问询且tt*,C退出.

⑤ 签名问询:敌手提交,μ},若ID不为第γ次问询,或ID为第γ次问询但tt*+1,C拥有合法的公钥和私密值,可以直接为敌手进行签名应答并生成合法签名.否则,C退出.

3) 伪造Forgery.敌手输出消息μ*在{ID*,t*}下的伪造签名(ε*,x*),敌手成功时有Verify(ID*,(ε*,x*),μ*,t*)=Accept.设v=H2(ID*,t*,μ*),,将代入到Verify算法中,注意到,可以得到方程:,即.如果(ε*,x*)为正确的伪造,那么以压倒性概率成立,同时以压倒性概率成立,因此有以压倒性概率成立.游戏模拟的时间上限为τ′=τ+TQ(TSam+TBas+T×TSamRwithBas+(Td+2)Tmul).同定理的概率至多为1-2-ω(lb n),因此算法成功解决PSIS(q,m,的概率为AdvB=ξ(TQ-t*)(1-2-ω(lb n))TQ(TQ-1).

证毕.

由于用户的密钥由KGC和用户一同完成,而KGC生成的部分私钥依赖于主密钥TA和当前时刻下的H1(ID|t)值,由H1的抗碰撞性可知,在未知TA的情况下,不诚实的用户获得时刻t′<t的部分密钥的难度不会小于破解)问题的难度.同时,用户私密值为用户公钥对应的整数格的基.由引理5,即使恶意KGC获取t时刻的私密值,也无法获取任意时刻t′<t.而敌手在未知的情况下伪造签名组件v2的难度不会小于破解)问题的难度.根据定义1,破解SIS问题的概率是可忽略的,综合定理3和定理4,本文提出的标准模型下的ST_LFC_SIG签名方案对于不诚实的用户和恶意KGC均满足适应性选择消息、选择身份攻击的FSU-AMAIA前向安全强不可伪造性.

7 方案安全性与效率对比分析

文献[33]对无证书签名方案的安全模型进行了分析,并依据签名问询与私密值问询,对第1类强敌手和第2类强敌手分别给出了8种和4种不同能力的敌手攻击等级,归纳如表1和表2所示.N-Sign表示在签名问询,若身份ID对应的公钥发生过替换,则拒绝应答.S-Sign表示无论公钥是否发生替换,都响应敌手的签名问询.

Table 1 Eight Different Attack Levels of Type 1 Adversary
表1 敌手1对应的8种攻击等级

NameSignOracle(ID*,μ*)→SignOracleID*toSecretValueOracleN-Type1N-SignNoNoSU-Type1N-SignYesNoSV-Type1N-SignNoYesSS-Type1S-SignNoNoSV-SU-Type1N-SignYesYesSS-SV-Type1S-SignNoYesSS-SU-Type1S-SignYesNoS-Type1S-SignYesYes

Table 2 Four Different Attack Levels of Type 2 Adversary
表2 敌手2对应的4种攻击等级

NameSignOracle(ID*,μ*)→SignOracleN-Type2N-SignNoSU-Type2N-SignYesSS-Type2S-SignNoS-Type2S-SignYes

由表1和表2可以看出,S -Type 1和S -Type 2类型的S-Type敌手具有最强的攻击能力.表3将本文提出的随机预言模型下的RO_LFC_SIG方案与标准模型下的ST_LFC_SIG方案,以及Kim等人[17]和Tian等人[18]的格基无证书签名方案,和文献[12-15]中的无证书签名方案进行安全性对比.

由表3可以看出,本文提出的无证书签名方案不仅具有抗量子攻击的能力,具有前向安全性,同时所基于的敌手模型攻击等级较高,因此方案具有较好的安全性.更进一步地,本文提出的ST_LFC_SIG方案是第1个基于格的标准模型下的无证书签名方案,较之文献[12-15,17-18]中以及RO_LFC_SIG随机预言模型下的签名方案,在实际应用中的安全性更高.

Table 3 Comparison of Security
表3 方案安全性对比

SchemesPostQuantumKeyExposureSecurityModelThreatModelRef[12]NoNoRandomSU-TypeRef[13]NoNoRandomSU-TypeRef[14]NoNoRandomSS-SU-TypeRef[15]NoNoRandomS-TypeRef[17]YesNoRandomSS-SU-TypeRef[18]YesNoRandomSV-SU-TypeRO_LFC_SIGYesYesRandomS-TypeST_LFC_SIGYesYesStandardS-Type

在效率对比方面,本文除了选择文献[17-18]中的随机预言模型下的格基无证书签名方案外,还选择了Yao等人[2]和Zhang等人[20]的FSIBS以及Rückert[26]的随机格签名方案,虽然后3种方案并不是无证书签名方案,但由于其均基于随机格,因此可以作为时间和空间复杂度对比的参照.

设参数与第3节方案中定义的相同,n为安全参数,m≥5n lb qk为正整数.TSam,TBas,TTrap,TRand,TExt分别为算法SamplePre,BasicDel,TrapGen,RandBasis,ExtBasis运行时间.Tmul为一次标量乘法耗费时间.7种方案的渐近性复杂度对比如表4所示.

Table 4 Comparison of Asymptotic Complexity
表4 渐近复杂度对比

SchemesPublicKeySecretKeySignatureKeyGenerationSignVerifyRef[2]O(ID)2mnlb(pq)O(ID)2mO(ID)2mO(ID)(TRand+TExt)O(ID)TSam(mn+n)TmulRef[17]nm3m23mTSam+TTrap6mnTmul+TSam6mnTmulRef[18]nm2m24mTSam4mnTmul4mnTmulRef[20]nmm2m+n∕2TBas+nm2TmulTSam(m2+mn)TmulRef[26]3n2m+m+n4m24m+n∕2TBas+TRand+TExtTSam+TExt+n2m2Tmul2nmTmulRO_LFC_SIGnk3km3m+kTBas+TSam+nmkTmul3mkTmul6mnTmulST_LFC_SIGnmm(2m+k)2m+kTBas+TSam+TExtTSam+(m+k)mTmul4mnTmul

kn4,则由表4可以看出,在保证安全性的基础上,本文方案的公钥尺寸优于其他的格基或身份基签名方案.标准模型下的ST_LFC_SIG签名方案的签名长度优于除文献[20]以外的其他方案.在私钥长度方面,本文方案优于文献[17,26]的方案,比Yao等人[2]、Tian等人[18]和Zhang等人[20]的FSIBS方案略大.这主要是由于无证书签名方案需要利用部分密钥和私密值2个子部分来构造基于随机格的2个PSIS等式,从而实现对不诚实用户和恶意KGC的前向安全强不可伪造性,而Zhang等人[20]的方案只考虑了随机预言模型下的外部敌手.此外,本文通过引入变量k降低了签名长度,并通过密钥根矩阵保证了较小的公钥长度以及安全证明中正确的敌手视角,而文献[20]中的安全证明由于缺少与身份绑定的密钥根矩阵的定义,将导致敌手关于同一挑战身份与挑战时刻的2次公钥问询产生不同的应答结果.而Yao等人[2]和Tian等人[18]的方案则不具备前向安全性.因此与文献[2,18,20]相比,本文方案的安全性更高.

时间复杂度方面,根据文献[30-31],有TExt<TSam<nm2Tmul<TRand<TRand+nm2Tmul<TBas<TTrap,在忽略采样时间的情况下,TSamn2Tmul.因此本文提出的2个签名方案的签名算法时间复杂度较文献[2,17,26]等方案均有优势.ST_LFC_SIG方案在验证算法方面也基本优于其他方案.在密钥生成算法方面,本文优于Yao等人[2]和Rückert[26]的方案,与文献[17,20]的方案基本持平.略大于Tian等人[18]的方案,这主要是由于为实现前向安全性,本文方案调用了BasicDel函数,增加了密钥生成算法时间.一种改进的方法是利用理想格构建前向安全的无证书签名方案,也是下一步的研究目标.

由以上分析可知,本文提出的RO_LFC_SIG和ST_LFC_SIG无证书签名方案首次在不引入第三方代理的条件下基于随机格实现了前向安全性与无证书的结合.同时,ST_LFC_SIG方案也是第1个基于格的标准模型下可证安全的无证书签名方案,并解决了密钥泄露问题.通过以上安全性与效率的对比分析可知,在保证相对较低的时空复杂度的基础上,随机预言模型下RO_LFC_SIG方案和标准模型下的ST_LFC_SIG方案均可以达到较好的安全性与实用性.

8 结束语

本文基于格基委派技术,针对密钥泄露的前向安全性,在提出随机预言模型下RO_LFC_SIG方案的基础上,设计了标准模型下前向安全的无证书签名方案ST_LFC_SIG,并给出了2个方案的具体构造.同时,基于随机预言模型和标准模型,证明了所提出的方案面对2类强敌手在适应性选择消息、选择身份攻击下的前向安全强不可伪造性FSU-AMAIA.本文方案的安全性建立在不诚实用户和恶意密钥生成中心的基础上,较之已有方案中的外部敌手模型,安全性更高.最后,通过对比分析,证明了本文提出的前向安全无证书签名方案具有较好的安全性与实用性.

本文提出的ST_LFC_SIG签名方案是第1个基于随机格的标准模型下可证安全的无证书数字签名方案,并结合了前向安全性以抵御密钥泄露的威胁.

由于本文提出的2个无证书签名方案主要是基于随机格进行方案构造,因此依然存在改进的空间,一个潜在的思路是采用理想格替代随机格优化存储空间,但是标准模型下基于理想格的签名方案的安全性证明是目前一个研究难点.因此我们下一步的研究目标将集中在设计基于理想格的前向安全无证书签名方案,以提高方案的整体效率.

参考文献:

[1]Shamir A. Identity-based cryptosystems and signature schemes[G] LNCS 196: Proc of the CRYPTO 1984. Berlin: Springer, 1985: 47-53

[2]Yao Yanqing, Li Zhoujun. A novel fuzzy identity based signature scheme based on the short integer solution problem[J]. Computers and Electrical Engineering, 2014, 40(6): 1930-1939

[3]Wei Baodian, Du Yusong, Zhang Huang, et al. Identity-based threshold ring signature from lattices[G] LNCS 8792: Proc of the 8th Int Conf on Network and System Security. Berlin: Springer, 2014: 233-245

[4]Tian Miaomiao. Identity-based proxy re-signatures from lattices[J]. Information Processing Letters, 2015, 115(4): 462-467

[5]Kim K S, Hong D W, Jeong I R. Identity-based proxy signature from lattices[J]. Journal of Communications and Networks, 2013, 15(1): 1-7

[6]Al-Riyami S, Paterson K G. Certificateless public key cryptography[G] LNCS 2894: Proc of the ASIACRYPT 2003. Berlin: Springer, 2003: 452-473

[7]Yu Yong, Mu Yi, Wang Guilin, et al. Improved certificateless signature scheme provably secure in the standard model[J]. Information Security IET, 2012, 6(2): 102-110

[8]Guan Chaowen, Weng Jian, Deng R H, et al. Unforgeability of an improved certificateless signature scheme in the standard model[J]. Information Security IET, 2014, 8(5): 273-276

[9]Yeh K H, Tsai K Y, Fan C Y. An efficient certificateless signature scheme without bilinear pairings[J]. Multimedia Tools and Applications, 2015, 74(16): 6519-6530

[10]Chen Hu, Zhu Changjie, Song Rushun. Efficient certificateless signature and group signature schemes[J]. Journal of Computer Research and Development, 2010, 47(2): 231-237 (in Chinese)(陈虎, 朱昌杰, 宋如顺. 高效的无证书签名和群签名方案[J]. 计算机研究与发展, 2010, 47(2): 231-237)

[11]Du Hongzhen, Wen Qiaoyan. Security analysis of two certificateless short signature schemes[J]. Information Security IET, 2014, 8(4): 230-233

[12]Choi K, Park J H, Lee D H. A new provably secure certificateless short signature scheme[J]. Computers & Mathematics with Applications, 2011, 61(7): 1760-1768

[13]Huang X, Mu Y, Susilo W, et al. Certificateless signatures: New schemes and security models[J]. Computer Journal, 2012, 55(4): 457-474

[14]Tso R, Huang X, Susilo W. Strongly secure certificateless short signatures[J]. Journal of System & Software, 2012, 85(6): 1409-1417

[15]Chen Yuchi, Tso R, Horng G, et al. Strongly secure certificateless signature: Cryptanalysis and improvement of two schemes[J]. Journal of Information Science and Engineering, 2015, 31(1): 283-296

[16]Shor P W. Polynomial-time algorithm for prime factorization and discrete logarithm on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5): 1484-1509

[17]Kim K S, Jeong I R. A new certificateless signature scheme under enhanced security models[J]. Security and Communication Networks, 2015, 8(5): 801-810

[18]Tian Miaomiao, Huang Liusheng. Certificateless and certificate-based signatures from lattices[J]. Security and Communication Networks, 2015, 8(8): 1575-1586

[19]Bellare M, Boldyreva A, Palacio A. An uninstantiable random oracle-model scheme for a hybrid-encryption problem[G] LNCS 3027: Proc of the EUROCRYPT 2004. Berlin: Springer, 2004: 171-188

[20]Zhang Xiaojun, Xu Chunxiang, Jin Chunhua, et al. Efficient forward secure identity-based shorter signature from lattice[J]. Computers and Electrical Engineering, 2013, 40(6): 1963-1971

[21]Bellare M, Neven G. Multi-signatures in the plain public-key model and a general forking lemma[C] Proc of the 13th ACM Conf on Computer and Communications Security. New York: ACM, 2006: 390-399

[22]Yu Jia, Hao Rong, Kong Fanyu, et al. Forward-secure identity-based signature: Security notions and contribution[J]. Information Sciences, 2011, 181(3): 648-660

[23]Ebri N, Baek J, Shou F A. Forward-secure identity-based signature: New generic constructions and their applications[J]. Journal of Wireless Mobile Network, 2013, 4(1): 32-54

[24]Yu Jia, Kong Fanyu, Hao Rong, et al. A note on a forward secure threshold signature scheme from bilinear pairings[J]. Journal of Computer Research and Development, 2010, 47(4): 605-612 (in Chinese)(于佳, 孔凡玉, 郝蓉, 等. 一个基于双线性映射的前向安全门限签名方案的标注[J]. 计算机研究与发展, 2010, 47(4): 605-612)

[25]Wei Jianghong, Liu Wenfen, Hu Xuexian. Forward-secure ciphertext-policy attribute-based encryption scheme[J]. Journal on Communications, 2014, 35(7): 38-45 (in Chinese)(魏江宏, 刘文芬, 胡学先. 前向安全的密文策略基于属性加密方案[J]. 通信学报, 2014, 35(7): 38-45)

[26]Rückert M. Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles[G] LNCS 6061: Post-Quantum Cryptography. Berlin: Springer, 2010: 182-200

[27]Li Jiguo, Li Yanqiong, Zhang Yichen. Forward secure certificateless proxy signature scheme[G] LNCS 7873: Proc of the 7th Int Conf on Network and System Security. Berlin: Springer, 2013: 350-364

[28]Lyubashevsky V. Lattice signatures without trapdoors[G] LNCS 7237: Proc of the EUROCRYPT 2012. Berlin: Springer, 2012: 738-755

[29]Micciancio D, Regev O. Worst-case to average-case reductions based on Gaussian measures[J]. SIAM Journal on Computing, 2007, 37(1): 267-302

[30]Alwen J, Peikert C, et al. Generating shorter bases for hard random lattices[J]. Theory of Computer Systems, 2011, 48(3): 535-553

[31]Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions[C] Proc of the 14th Annual ACM Int Symp on Theory of Computing. New York: ACM, 2008: 197-206

[32]Agrawal S, Boneh D, Boyen X. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE[G] LNCS 6223: Advances in Cryptology (CRYPTO 2010). Berlin: Springer, 2010: 98-115

[33]Yu Chichen, Tso R. A survey on security of certificateless signature schemes[J]. IETE Technical Review, 2016, 33(2): 115-121

Xu Qian, born in 1986. PhD candidate. His main research interests include cryptography, cloud computing security and industrial control safety.

Tan Chengxiang, born in 1965. Professor and PhD supervisor. His main research interests include information security, cloud computing security and applied cryptography (Jerrytan@tongji.edu.cn).

Feng Jun, born in 1985. PhD candidate. His main research interests include security measure, security audit and mobile security (109056396@qq.com).

Fan Zhijie, born in 1982. PhD candidate. His main research interests include cyber security, cloud computing security and mobile security (1310898@tongji.edu.cn).

Zhu Wenye, born in 1991. PhD candidate. His main research interests include information security, security measure and mobile security (1549160994@qq.com).

Lattice-Based Forward Secure and Certificateless Signature Scheme

Xu Qian, Tan Chengxiang, Feng Jun, Fan Zhijie, and Zhu Wenye

(Department of Computer Science and Technology, College of Electronics and Information Engineering, Tongji University, Shanghai 201804)

Abstract:Certificateless signature scheme has solved key escrow problems existing in traditional identity-based signature schemes. The secret key of the user in certificateless signature scheme consists of two parts, one is partial secret key, which is generated by key generation centre, and the other is secret value from user itself. However, there are still three points to be improved in such scheme. Firstly, although some lattice-based certificateless signature schemes based on the random oracle model have been proposed in order to achieve the post-quantum security, their standard model counterparts remain unrealized. Secondly, most of the existing lattice-based certificateless signature schemes only consider the outside attacker and neglect the threats from semi-trusted user. Thirdly, the existing certificateless signature schemes all rely on the security of the secret key, which cannot be satisfied due to the key exposure problem. In this paper, based on the forward secure and certificateless signature scheme in the random oracle model, we propose the first lattice-based certificateless signature scheme which is provably secure in the standard model to eliminate key exposure and key escrow problems without introducing a third party proxy. With the help of the small integer solution problem, we have proved that our schemes can guarantee the forward secure and strongly existential unforgeability against the adaptive chosen message and adaptive chosen identity attack.

Key words:lattice-based signature scheme; certificateless; forward secure; random oracle model; standard model

收稿日期:2016-06-13;

修回日期:2016-08-23

基金项目:国家重点研发计划项目(2017YFB0802302) This work was supported by the National Key Research and Development Program of China (2017YFB0802302)

通信作者:谭成翔(jerrytan@tongji.edu.cn)

中图法分类号:TP309