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

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

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



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

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

(同济大学电子与信息工程学院计算机科学与技术系 上海 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表示]范围内的整数.表示向量v的l2范数.本文中使用标准的O记号表示函数的复杂度上界，即g(n)=O(f(n))当且仅当存在正常数c和n0，使得对任意的n≥n0有成立.相应地，定义下界复杂度记号ω，即g(n)=ω(f(n))当且仅当存在正常数c和n0，使得对任意的n≥n0有成立.定义关于n的可忽略函数negl(n)，使得对任意多项式g(n)，当n足够大时都有.如果概率p=1-negl(n)则称概率是压倒性成立的，若p=negl(n)，则称概率是可忽略的.

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

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

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

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

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

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

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

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

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

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，C将PP发送给敌手A1，否则，将PP和MSK一起发给A2.

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*,t≤t*)未作为私密值问询的输入；

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

④ 若b=2，(ID*,t≤t*)未作为公钥替换问询的输入；

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

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

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

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

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

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

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

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

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

正确性：

4 RO_LFC_SIG的安全性分析

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

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

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

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

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

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

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

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

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

证毕.

证明. 假设存在敌手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).随机矩阵B∈n×mq为SIS实例，维护2个Hash列表LH3,Lsig，Lsig中的表项为}.

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

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

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

④H3问询：与定理1相同.

证毕.

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

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

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

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

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

6 ST_LFC_SIG的安全性分析

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

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

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

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

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

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

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

证毕.

证明. 假设存在敌手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]，随机均匀小范数矩阵Ci∈n×kq.对i∈[1,l]，逐列从G中采样得到Di∈m×mq，则Fi=B0Di统计不可区分于n×mq上的随机均匀分布，其中随机矩阵B0为SIS实例.

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

② Foreacht≤t*do

③h=H1(ID*|t)；

⑥ End Foreach

⑦B=B0RID*|t*RID*|t*-1…RID*|1；*B为ID*对应的秘钥根矩阵*

⑧B′=B0；

⑨ Forj=t*+1 toT

⑩h=H1(ID*|j-1)；

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

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

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

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

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

证毕.

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种攻击等级

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

由表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 方案安全性对比

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

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

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

设k≤n4，则由表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

由以上分析可知，本文提出的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

(DepartmentofComputerScienceandTechnology,CollegeofElectronicsandInformationEngineering,TongjiUniversity,Shanghai201804)

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.

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