徐 潛 譚成翔 馮 俊 樊志杰 朱文燁

(同濟(jì)大學(xué)電子與信息工程學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 上海 201804)

?

基于格的前向安全無(wú)證書(shū)數(shù)字簽名方案

徐 潛 譚成翔 馮 俊 樊志杰 朱文燁

(同濟(jì)大學(xué)電子與信息工程學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 上海 201804)

(1062842783@qq.com)

無(wú)證書(shū)簽名方案利用密鑰生成中心與用戶(hù)共同生成簽名密鑰的方式，解決了傳統(tǒng)的基于身份的數(shù)字簽名方案中存在的密鑰托管問(wèn)題.目前，針對(duì)無(wú)證書(shū)簽名方案的研究還存在3點(diǎn)可以改進(jìn)的地方:1)已有的基于隨機(jī)格構(gòu)建的無(wú)證書(shū)簽名方案，雖然具有后量子安全性，但都是建立在隨機(jī)預(yù)言模型下，尚無(wú)針對(duì)標(biāo)準(zhǔn)模型的相關(guān)研究；2)已有的格基無(wú)證書(shū)簽名方案大多只考慮外部敵手，缺乏抵御不誠(chéng)實(shí)用戶(hù)攻擊的能力；3)已有的無(wú)證書(shū)簽名方案均需要保證用戶(hù)密鑰是絕對(duì)安全的，無(wú)法解決密鑰泄露問(wèn)題.針對(duì)這3點(diǎn)不足，在隨機(jī)預(yù)言模型下的前向安全的無(wú)證書(shū)格基簽名方案的基礎(chǔ)上，首次提出了標(biāo)準(zhǔn)模型下可證明安全的基于隨機(jī)格的前向安全無(wú)證書(shū)數(shù)字簽名方案，并在不引入第三方代理的前提下同時(shí)解決了密鑰泄露和密鑰托管問(wèn)題.在面對(duì)不誠(chéng)實(shí)的用戶(hù)和惡意密鑰生成中心2類(lèi)強(qiáng)敵手的情況下，利用小整數(shù)解SIS假設(shè)證明了所提出的方案具有適應(yīng)性選擇消息、選擇身份攻擊下的前向安全強(qiáng)不可偽造性.

格基數(shù)字簽名；無(wú)證書(shū)；前向安全；隨機(jī)預(yù)言模型；標(biāo)準(zhǔn)模型

傳統(tǒng)的基于公鑰基礎(chǔ)設(shè)施(public key infrastr-ucture, PKI)的公鑰密碼系統(tǒng)通過(guò)引入證書(shū)管理機(jī)構(gòu)CA為用戶(hù)頒發(fā)數(shù)字證書(shū)，并鑒權(quán)用戶(hù)身份.然而，證書(shū)的更新、撤銷(xiāo)等管理操作給系統(tǒng)帶來(lái)較大的運(yùn)行負(fù)荷.為了消除證書(shū)管理帶來(lái)的昂貴開(kāi)銷(xiāo)，Shamir[1]于1984年提出了身份基加密的思想，利用用戶(hù)唯一的公共標(biāo)識(shí)ID作為用戶(hù)的公鑰，由密鑰生成器(private key generator, PKG)為用戶(hù)生成密鑰.目前已有很多高效的身份基簽名方案[2-5]，如Yao等人[2]利用拉格朗日插值公式，在隨機(jī)格的基礎(chǔ)上構(gòu)建了允許模糊身份驗(yàn)證的身份基簽名方案.以及Wei等人[3]提出的門(mén)限身份基簽名方案等.然而，由于用戶(hù)密鑰完全由PKG生成，對(duì)PKG可見(jiàn)，一旦PKG受到污染，整個(gè)系統(tǒng)中的用戶(hù)都將不再安全，這就產(chǎn)生了密鑰托管問(wèn)題(key escrow).

Al-Riyami等人[6]在2003年首次定義了無(wú)證書(shū)公鑰密碼學(xué)的概念，用來(lái)解決密鑰托管問(wèn)題并消除證書(shū)管理的開(kāi)銷(xiāo).無(wú)證書(shū)密碼學(xué)的核心思想為：密鑰生成中心(key generation centre, KGC)為用戶(hù)派發(fā)部分密鑰，用戶(hù)自己負(fù)責(zé)剩余密鑰，即私密值的生成，用戶(hù)完整的簽名密鑰由部分密鑰和私密值共同組成.由于KGC無(wú)法獲取用戶(hù)的私密值，也就無(wú)法知曉用戶(hù)的完整密鑰，從而消除了惡意KGC帶來(lái)的安全隱患，解決了密鑰托管問(wèn)題.無(wú)證書(shū)密鑰方案可以用于移動(dòng)環(huán)境下用戶(hù)敏感數(shù)據(jù)的保護(hù)或者高效的授權(quán)認(rèn)證等領(lǐng)域.

基于Al-Riyami的思想，很多無(wú)證書(shū)數(shù)字簽名方案被陸續(xù)提出[7-15].這些方案的安全性都是基于傳統(tǒng)數(shù)論難題，如離散對(duì)數(shù)和大整數(shù)分解等.然而隨著量子計(jì)算機(jī)的發(fā)展，基于傳統(tǒng)數(shù)論難題的密碼方案的安全性受到了挑戰(zhàn).事實(shí)上，早在1997年，Shor[16]就提出了多項(xiàng)式時(shí)間內(nèi)解決離散對(duì)數(shù)和大整數(shù)素分解的量子算法.因此，構(gòu)建能夠抵御量子攻擊的后量子安全的無(wú)證書(shū)簽名方案就具有十分重要的意義.為此，Kim等人[17]和Tian等人[18]設(shè)計(jì)了基于格的無(wú)證書(shū)簽名方案，并通過(guò)小整數(shù)解(short integer solution, SIS)問(wèn)題證明了方案的安全性.但是他們的方案以及安全證明都是基于隨機(jī)預(yù)言模型，在實(shí)際應(yīng)用中，很難保證諸如Hash函數(shù)等對(duì)象可以按照在隨機(jī)預(yù)言證明中所假設(shè)的那樣，實(shí)現(xiàn)完全的隨機(jī)化，從而難以保證系統(tǒng)的實(shí)際安全性[19].同時(shí)，他們的方案只考慮外部敵手，忽視了來(lái)自于內(nèi)部不誠(chéng)實(shí)簽名用戶(hù)的威脅.

更進(jìn)一步地，在移動(dòng)環(huán)境下特別是隨著手機(jī)等移動(dòng)端的大量使用，由于用戶(hù)的不安全行為，一旦移動(dòng)設(shè)備被攻擊，存儲(chǔ)在設(shè)備中的用戶(hù)簽名密鑰將很容易被竊取，即存在密鑰泄露問(wèn)題.目前后量子安全的無(wú)證書(shū)簽名方案[17-18]等均假設(shè)用戶(hù)密鑰是絕對(duì)安全的，缺乏有效解決密鑰泄露問(wèn)題的能力.同時(shí)，基于傳統(tǒng)數(shù)論難題的無(wú)證書(shū)簽名方案雖然考慮了密鑰泄露問(wèn)題，但主要通過(guò)引入第三方代理來(lái)更新用戶(hù)密鑰，不僅增加了系統(tǒng)的復(fù)雜度，而且，由于第三方代理的安全性無(wú)法保證，系統(tǒng)的安全隱患也隨之增加.

綜上所述，目前無(wú)證書(shū)簽名方案存在3個(gè)問(wèn)題：

1) 已有基于格的后量子安全的無(wú)證書(shū)簽名方案僅僅基于隨機(jī)預(yù)言模型，無(wú)法保證實(shí)際應(yīng)用中的系統(tǒng)安全性；

2) 已有無(wú)證書(shū)簽名方案的安全證明主要考慮外部敵手和惡意密鑰生成中心，而對(duì)來(lái)自于不誠(chéng)實(shí)的簽名用戶(hù)的威脅抵抗能力不足；

3) 目前無(wú)證書(shū)簽名方案還無(wú)法在不引入第三方代理的前提下解決密鑰泄露問(wèn)題.

針對(duì)這3個(gè)主要問(wèn)題，本文利用格基委派技術(shù)，基于隨機(jī)格理論，首先在隨機(jī)預(yù)言模型下引入了前向安全的無(wú)證書(shū)數(shù)字簽名方案RO_LFC_SIG，并在此基礎(chǔ)上，設(shè)計(jì)了第1個(gè)標(biāo)準(zhǔn)模型下可證安全的前向安全無(wú)證書(shū)ST_LFC_SIG方案.

本文的主要貢獻(xiàn)有4個(gè)方面：

1) 針對(duì)不誠(chéng)實(shí)的用戶(hù)和內(nèi)部惡意KGC攻擊者，首次形式化定義了前向安全強(qiáng)不可偽造性的安全模型.與文獻(xiàn)[8，18，20-21]中的安全模型相比，不僅增加了針對(duì)密鑰泄露的前向安全性部分，而且將外部敵手增強(qiáng)為不誠(chéng)實(shí)的簽名用戶(hù)，使得方案安全性更高.

2) 首次具體實(shí)現(xiàn)了基于格的前向安全無(wú)證書(shū)簽名方案，將前向安全與無(wú)證書(shū)方案基于隨機(jī)格結(jié)合，在不引入第三方代理的條件下同時(shí)解決密鑰泄露和密鑰托管問(wèn)題，且具有后量子安全性.

3) 提出的ST_LFC_SIG無(wú)證書(shū)簽名方案不僅具有前向安全性，也是首個(gè)在標(biāo)準(zhǔn)模型下可證安全的格基無(wú)證書(shū)簽名方案，與文獻(xiàn)[17-18]中的格基簽名方案相比，安全性更高.

4) 分別在隨機(jī)預(yù)言模型和標(biāo)準(zhǔn)模型下，利用隨機(jī)格的小整數(shù)解SIS難題，證明了提出的2個(gè)簽名方案在面對(duì)2類(lèi)強(qiáng)敵手時(shí)，具有適應(yīng)性選擇消息、選擇身份攻擊的前向安全強(qiáng)不可偽造性(forward secure and strongly existentially unforgeable against adaptive chosen message and adaptive chosen identity attack, FSU-AMAIA)；通過(guò)與已有的格基簽名方案和無(wú)證書(shū)簽名方案進(jìn)行安全性和效率的對(duì)比，證明本文方案在保證較低的漸近性復(fù)雜度的同時(shí)，達(dá)到了更好的安全性.

1 相關(guān)工作

無(wú)證書(shū)數(shù)字簽名方案的研究目前已有很多，例如Yu等人[7]就是利用雙線性對(duì)構(gòu)造了無(wú)證書(shū)簽名方案；Guan等人[8]通過(guò)應(yīng)用公鑰替換攻擊證明了Yu等人[7]方案并不是存在不可偽造的；Yeh等人[9]通過(guò)橢圓曲線設(shè)計(jì)了無(wú)證書(shū)簽名方案，但是只考慮了第三方敵手的攻擊；陳虎等人[10]將無(wú)證書(shū)簽名與群簽名結(jié)合，基于雙線性對(duì)設(shè)計(jì)了高效的無(wú)證書(shū)群簽名方案，實(shí)現(xiàn)了群成員的動(dòng)態(tài)更新；Choi等人[12]基于計(jì)算性Diffie-Hellman假設(shè)(computational Diffie-Hellamn, CDH)構(gòu)造了高效的無(wú)證書(shū)簽名方案，但主要實(shí)現(xiàn)了存在不可偽造性而非強(qiáng)不可偽造；Huang等人[13]構(gòu)造了能夠抵御2類(lèi)強(qiáng)敵手的無(wú)證書(shū)簽名方案，并基于提出的簽名方案設(shè)計(jì)了身份鑒權(quán)協(xié)議；Tso等人[14]基于CDH假設(shè)并針對(duì)公鑰替換攻擊問(wèn)題設(shè)計(jì)了強(qiáng)不可偽造的無(wú)證書(shū)簽名方案；同樣基于CDH假設(shè)的還有Chen等人[15]的方案.以上的無(wú)證書(shū)簽名方案[7-15]都是基于傳統(tǒng)數(shù)論難題的，不具備后量子安全性；Kim等人[17]和Tian等人[18]設(shè)計(jì)了基于格的隨機(jī)預(yù)言模型下可證安全的無(wú)證書(shū)簽名方案，并通過(guò)小整數(shù)解SIS問(wèn)題證明了方案的存在不可偽造性；文獻(xiàn)[17-18]的方案實(shí)現(xiàn)了后量子安全的無(wú)證書(shū)簽名方案，但是隨機(jī)預(yù)言模型無(wú)法保證方案的實(shí)際安全性，其安全證明也只考慮了外部敵手，沒(méi)有針對(duì)不誠(chéng)實(shí)用戶(hù)的安全性分析.同時(shí)，文獻(xiàn)[17-18]的簽名方案依賴(lài)于絕對(duì)安全的用戶(hù)密鑰，因此存在密鑰泄露問(wèn)題.

解決密鑰泄露問(wèn)題的一種有效的方法是構(gòu)建前向安全的公鑰密碼系統(tǒng).針對(duì)密鑰泄露的前向安全性是指，某一個(gè)時(shí)刻用戶(hù)密鑰的泄露不會(huì)危及之前任意時(shí)刻的方案的安全性.在前向安全的數(shù)字簽名研究方面，目前采用的主要思想是構(gòu)建不可逆的密鑰更新算法.已有很多前向安全的簽名方案[22-25]，例如Yu等人[22]的方案；Ebri等人[23]賦予用戶(hù)指定密鑰更新時(shí)間的能力；文獻(xiàn)[24]則將前向安全與門(mén)限簽名相結(jié)合，利用周期性密鑰更新和群組門(mén)限同時(shí)保證密鑰的安全性；文獻(xiàn)[25]中利用時(shí)間序列樹(shù)等實(shí)現(xiàn)了前向安全的細(xì)粒度屬性控制.但同很多無(wú)證書(shū)密碼方案一樣，這些前向安全的簽名方案仍然是基于雙線性對(duì)等數(shù)學(xué)難題，不具有抗量子計(jì)算攻擊的能力；Zhang等人[20]設(shè)計(jì)了首個(gè)基于格的前向安全的簽名方案FSIBS，其主要的思路是建立在Rückert[26]的分層的身份基簽名方案的基礎(chǔ)上，利用格基委派算法實(shí)現(xiàn)密鑰的前向更新；然而同文獻(xiàn)[17-18]中的方案一樣，Zhang等人[20]的方案也僅僅實(shí)現(xiàn)了隨機(jī)預(yù)言模型下的證明；而且Zhang等人[20]的方案只考慮了外部敵手，不具備抵抗惡意KGC攻擊的能力，安全模型也僅考慮了存在不可偽造性而缺乏針對(duì)前向安全性的形式化定義；Li等人[27]仍然基于雙線性對(duì)考慮了前向安全與無(wú)證書(shū)方案的結(jié)合問(wèn)題，沒(méi)有給出安全模型的形式化定義，而且文獻(xiàn)[27]通過(guò)引入第三方代理實(shí)現(xiàn)前向安全性，增加了方案復(fù)雜度，也沒(méi)有證明當(dāng)?shù)谌酱硎艿焦魰r(shí)方案的可靠性.

2 預(yù)備知識(shí)

標(biāo)識(shí)與記號(hào)：設(shè)q為正素?cái)?shù)，q表示]范圍內(nèi)的整數(shù).表示向量v的l2范數(shù).本文中使用標(biāo)準(zhǔn)的O記號(hào)表示函數(shù)的復(fù)雜度上界，即g(n)=O(f(n))當(dāng)且僅當(dāng)存在正常數(shù)c和n0，使得對(duì)任意的n≥n0有成立.相應(yīng)地，定義下界復(fù)雜度記號(hào)ω，即g(n)=ω(f(n))當(dāng)且僅當(dāng)存在正常數(shù)c和n0，使得對(duì)任意的n≥n0有成立.定義關(guān)于n的可忽略函數(shù)negl(n)，使得對(duì)任意多項(xiàng)式g(n)，當(dāng)n足夠大時(shí)都有.如果概率p=1-negl(n)則稱(chēng)概率是壓倒性成立的，若p=negl(n)，則稱(chēng)概率是可忽略的.

定義1. 小整數(shù)解問(wèn)題SIS[28]：給定一個(gè)正整數(shù)q，隨機(jī)矩陣A∈q，實(shí)數(shù)β，定義(q,m,β)上的SIS問(wèn)題PSIS(q,m,β)是：找到非0向量v∈m，使得Av=0 modq并且≤β.Micciancio等人[29]已經(jīng)證明，對(duì)任意多項(xiàng)式有界的，平均情況下的PSIS(q,m,β)問(wèn)題與解決最壞情況下格上的近似獨(dú)立向量問(wèn)題是同等困難的.

引理2[28]. 無(wú)抽樣技術(shù)：若簽名人從某個(gè)隨機(jī)分布中抽取y，簽名的目標(biāo)分布為f(x)，與簽名人私鑰sk無(wú)關(guān)，實(shí)際分布為g(x)，可能與sk有關(guān)，且對(duì)于任意x及某個(gè)正實(shí)數(shù)M有f(x)≤Mg(x).則以概率f(y)Mg(y)輸出簽名y將使得y服從分布f(x).

由引理1，若設(shè)M=e，以(y)輸出簽名y，則y服從于分布且以壓倒性的概率滿足.

引理3. 陷門(mén)生成算法[30]：設(shè)q≥3，m≥5nlbq，存在有效的多項(xiàng)式時(shí)間算法TrapGen在多項(xiàng)式時(shí)間內(nèi)生成統(tǒng)計(jì)接近于n×mq上隨機(jī)分布的矩陣A以及整數(shù)格Λ⊥(A)的短基TA∈m×m，設(shè)Gram-Schmidt正交化后為A，則以壓倒性概率成立.

引理4. 原像抽樣算法[31]：設(shè)q≥3，m≥O(nlbq)，隨機(jī)矩陣A∈n×mq以及整數(shù)格Λ⊥(A)的短基TA∈m×m，設(shè)高斯參數(shù)，那么對(duì)任意的u∈，存在有效的多項(xiàng)式時(shí)間算法SamplePre(A,TA,s,u)，統(tǒng)計(jì)近似于從離散高斯分布GΛu(A),s中抽取向量v∈Λu(A).由高斯分布的性質(zhì)，v將以壓倒性的概率滿足.其中Λu(A)={e∈m:Ae=umodq}.可以很容易的擴(kuò)展到矩陣的原像抽樣算法，即：

對(duì)任意的矩陣U∈n×k，其余參數(shù)與基本的原像抽樣算法相同，存在擴(kuò)展的多項(xiàng)式時(shí)間算法SamplePre(A,TA,s,U)，統(tǒng)計(jì)近似于從離散高斯分布GΛU(A),s中得到矩陣V∈Λu(A)，且AV=Umodq.同時(shí)以壓倒性概率成立.

引理5. 格基委派算法[32]：設(shè)q上小范數(shù)可逆矩陣(按離散高斯分布獨(dú)立抽取每一列)的集合為Dm×m，矩陣A∈n×mq，整數(shù)格Λ⊥(A)的短基TA∈m×m，高斯參數(shù)，矩陣R←Dm×m，存在多項(xiàng)式時(shí)間算法BasicDel(A,R,TA,s)輸出格Λ⊥(B=AR-1)的短基).且不存在多項(xiàng)式時(shí)間BasicDel的求逆運(yùn)算.存在多項(xiàng)式時(shí)間算法SampleRwithBasis(A)輸出矩陣R←Dm×m以及格Λ⊥(B=AR-1)的短基).存在確定性的多項(xiàng)式算法ExtBasis(F=A|C,TA)輸出A|C對(duì)應(yīng)的整數(shù)格Λ⊥(A|C)的基TF，且.

定義2. 本文提出的數(shù)字簽名方案包括5個(gè)多項(xiàng)式時(shí)間算法：

1) 系統(tǒng)建立Setup.由密鑰生成中心KGC運(yùn)行，輸入安全參數(shù)n，輸出系統(tǒng)公共參數(shù)PP和主密鑰MSK.

3) 密鑰更新算法Update.輸入用戶(hù)當(dāng)前ID與更新的時(shí)間區(qū)間，KGC與用戶(hù)交互完成密鑰更新.

4) 簽名算法Sign.輸入系統(tǒng)公共參數(shù)、用戶(hù)公鑰與私鑰、待簽名消息、輸出簽名.

5) 驗(yàn)證算法Verify.輸入系統(tǒng)公共參數(shù)、簽名消息、用戶(hù)公鑰與用戶(hù)ID以及簽名，算法判斷該簽名是否是有效簽名.

定義3. 前向安全強(qiáng)不可偽造性FSU-AMAIA：定義2類(lèi)多項(xiàng)式時(shí)間強(qiáng)敵手：1)強(qiáng)敵手A1模擬內(nèi)部不誠(chéng)實(shí)的用戶(hù)，不誠(chéng)實(shí)的用戶(hù)指在簽名過(guò)程中，會(huì)在未獲得合法部分密鑰的情況下嘗試偽造自己或其他用戶(hù)的簽名，顯然，偽造自身某一時(shí)刻的簽名需要的安全性更高；2)強(qiáng)敵手A2模擬惡意的密鑰生成中心KGC，在文獻(xiàn)[8，18]中提出的安全模型的基礎(chǔ)上，給出針對(duì)2類(lèi)強(qiáng)敵手的安全游戲Game1與Game2，如果敵手A1與A2分別贏得Game1和Game2的概率是可忽略的，則稱(chēng)簽名方案在適應(yīng)性選擇消息、選擇身份攻擊下對(duì)強(qiáng)敵手是前向安全強(qiáng)不可偽造的，游戲Gameb,b∈{1,2}具體描述如下.

1) 系統(tǒng)建立Setup.輸入安全參數(shù)n，挑戰(zhàn)者C生成系統(tǒng)公共參數(shù)PP與主密鑰MSK，如果b=1，C將PP發(fā)送給敵手A1，否則，將PP和MSK一起發(fā)給A2.

2) 敵手適應(yīng)性的進(jìn)行如下問(wèn)詢(xún).

① 公鑰問(wèn)詢(xún)：敵手提交{ID,t}，挑戰(zhàn)者返回相應(yīng)的公鑰回答問(wèn)詢(xún).

② 密鑰問(wèn)詢(xún)：敵手Ab提交{ID,t}，如果b=1，挑戰(zhàn)者C生成用戶(hù)的部分簽名密鑰并發(fā)送給敵手.同時(shí)，敵手可以問(wèn)詢(xún)除自己之外的其他用戶(hù)的私密值.注意如果{ID,t}對(duì)應(yīng)的公鑰發(fā)生過(guò)替換，挑戰(zhàn)者返回⊥.如果b=2，密鑰問(wèn)詢(xún)只包括私密值問(wèn)詢(xún)，挑戰(zhàn)者返回私密值給敵手.

③ 公鑰替換問(wèn)詢(xún)：敵手可以替換任意身份下的公鑰.

④ 密鑰更新問(wèn)詢(xún)：敵手Ab提交更新時(shí)間區(qū)間與身份，挑戰(zhàn)者返回更新后的密鑰作為應(yīng)答.

⑤ 簽名問(wèn)詢(xún)：敵手Ab問(wèn)詢(xún)關(guān)于任意消息的簽名，挑戰(zhàn)者生成消息的簽名并返回給敵手.注意如果相應(yīng)的公鑰被敵手替換過(guò)，則敵手需要提交對(duì)應(yīng)的私密值.

敵手Ab可以選擇變更用戶(hù)身份或簽名時(shí)刻并問(wèn)詢(xún)密鑰和簽名，也可以直接進(jìn)入偽造階段.

3) 偽造Forgery.敵手Ab輸出以身份ID*，時(shí)刻t*下的關(guān)于消息μ*的簽名e*，敵手Ab贏得游戲當(dāng)且僅當(dāng)：

①Verify(ID*,e*,μ*,t*)=Accept；

② 若b=1，(ID*,t*)未作為密鑰問(wèn)詢(xún)的輸入；若b=2，(ID*,t≤t*)未作為私密值問(wèn)詢(xún)的輸入；

③ 若b=1，(ID*,ti,t*)未作為密鑰更新問(wèn)詢(xún)的輸入；若b=2，(ID*,ti,tj≤t*)未作為密鑰更新問(wèn)詢(xún)的輸入；

④ 若b=2，(ID*,t≤t*)未作為公鑰替換問(wèn)詢(xún)的輸入；

⑤e*未作為簽名問(wèn)詢(xún)的應(yīng)答返回給敵手.

若敵手Ab獲勝的概率為AdvAb=Pr[Forgery(ID*,e*,μ*,t*)=Success]，則當(dāng)且僅當(dāng)AdvAb關(guān)于安全參數(shù)n是可忽略的時(shí)，簽名方案是適應(yīng)性選擇消息、選擇身份攻擊下前向安全強(qiáng)不可偽造FSU-AMAIA安全的.

3 隨機(jī)預(yù)言模型下的簽名方案RO_LFC_SIG

本節(jié)給出隨機(jī)預(yù)言模型下的前向安全的格基無(wú)證書(shū)數(shù)字簽名方案RO_LFC_SIG，作為構(gòu)建標(biāo)準(zhǔn)模型下前向安全無(wú)證書(shū)簽名方案的基礎(chǔ).RO_LFC_SIG方案具體包括5個(gè)多項(xiàng)式時(shí)間的算法.

KGC運(yùn)行〈A,TA〉=TrapGen(n,q,m)，得到近似隨機(jī)矩陣A∈n×mq及整數(shù)格Λ⊥(A)的基).設(shè)高斯參數(shù)，參數(shù)序列{σ0,σ1,…,σT}，其中σ0=ω(lbm)，σi≥m3i2ω(lbm)2i+1.設(shè)離散正態(tài)分布參數(shù).隨機(jī)矩陣B∈n×mq.

KGC公布公共參數(shù)PP={A,B,H1,H2,H3}，主密鑰MSK={TA}.

2) 密鑰提取KeyExtract.給定PP、ID、密鑰生

3) 密鑰更新KeyUpdate.假設(shè)密鑰更新時(shí)間區(qū)

5) 驗(yàn)證算法Verify.輸入(ID,(ε,h),μ,t)，算法輸出Accept當(dāng)且僅當(dāng)：

正確性：

4 RO_LFC_SIG的安全性分析

本節(jié)基于SIS假設(shè)證明隨機(jī)預(yù)言模型下方案的前向安全強(qiáng)不可偽造性.不失一般性，設(shè)敵手的問(wèn)詢(xún)時(shí)刻為[1,T]區(qū)間上的連續(xù)值，時(shí)刻t0=1.設(shè)Q為總的問(wèn)詢(xún)身份數(shù)，TSam,TBas,TTrap,TSamRwithBas,TExt為算法,BasicDel,TrapGen,SampleRwithBasis以及ExtBasis運(yùn)行時(shí)間，Tmul為一次m×m矩陣乘法的近似運(yùn)行時(shí)間.

證明. 假設(shè)存在敵手A1可以偽造簽名，則可以如下構(gòu)造多項(xiàng)式算法.

挑戰(zhàn)者C隨機(jī)選擇A0∈n×mq為SIS實(shí)例，隨機(jī)矩陣B∈n×mq，維護(hù)4個(gè)Hash列表LH1,LH2,LH3,Lsig.C從G逐列采樣選取t*個(gè)可逆的小范數(shù)矩陣Ri∈m×mq，并設(shè)A=A0Rt*Rt*-1…R1，γ∈[1,Q].

C將公共參數(shù)PP={A,A0,B,H3}發(fā)送給敵手A1.

2) 敵手可以適應(yīng)性的進(jìn)行如下問(wèn)詢(xún).

①H2問(wèn)詢(xún)：敵手提交{ID,ti}，C查找列表LH2判斷是否有對(duì)應(yīng)的Hash值，若有，則直接作為敵手的應(yīng)答返回?cái)呈郑駝t，設(shè)Dm×m為q上的小范數(shù)可逆陣集合.若ID不為第γ次問(wèn)詢(xún)身份，C調(diào)用多項(xiàng)式時(shí)間函數(shù)〈R,TtiAR〉=SampleRwithBasis(A)生成R←Dm×m以及Λ⊥(AR-1)的基TtiAR∈m×m，C設(shè)置H2(ID|ti)=R并將其返回給敵手作為應(yīng)答.同時(shí)，將{TtiAR,R}插入到列表LH2中.

若ID為第γ次問(wèn)詢(xún)身份，ti≤t*，C直接令H2(ID|ti)=Rti，TtiAR=⊥，將H2(ID|ti)=Rti返回給敵手，并將{TtiAR,Rti}插入到LH2中.

若ID為第γ次問(wèn)詢(xún)身份，ti=t*+1，C調(diào)用SampleRwithBasis(A0)生成R←Dm×m，TtiAR∈m×m.C設(shè)置H2(ID|t*+1)=R并將其返回給敵手作為應(yīng)答.同時(shí)，將{TtiAR,R}插入到列表LH2中.

⑨ 簽名問(wèn)詢(xún)：敵手A1提交{ID,t,μ}，C查找LH3,Lsig得到對(duì)應(yīng)的密鑰與h，之后正常簽名并應(yīng)答敵手.如果{ID,t}對(duì)應(yīng)的公鑰發(fā)生過(guò)替換，則A1需要提交對(duì)應(yīng)的私密值.

證畢.

證明. 假設(shè)存在敵手A2可以偽造簽名，則構(gòu)造多項(xiàng)式算法步驟如下.

1) 系統(tǒng)建立Setup.設(shè)n,k,λ,T,M,α,m,L,s,t*,γ,β,q,δ以及參數(shù)序列{σ0,σ1,…,σT}與定理1中一樣.3個(gè)抗碰撞的Hash函數(shù)H1,H2,H與RO_LFC_SIG方案中一樣.〈A,TA〉=TrapGen(n,q,m).隨機(jī)矩陣B∈n×mq為SIS實(shí)例，維護(hù)2個(gè)Hash列表LH3,Lsig，Lsig中的表項(xiàng)為}.

挑戰(zhàn)者C將公共參數(shù)PP={A,B,H1,H2,H3}與主密鑰MSK={TA}發(fā)送給敵手A2.

2) 敵手可以適應(yīng)性的進(jìn)行如下問(wèn)詢(xún).

敵手A2已知主密鑰MSK，因此不需要進(jìn)行部分密鑰問(wèn)詢(xún).部分密鑰的更新也可以由敵手自己完成.

④H3問(wèn)詢(xún)：與定理1相同.

證畢.

5 標(biāo)準(zhǔn)模型下的簽名方案ST_LFC_SIG

隨機(jī)預(yù)言模型下RO_LFC_SIG簽名方案的安全性依賴(lài)于方案所采用的Hash函數(shù)的完全隨機(jī)性，這在實(shí)際應(yīng)用中可能無(wú)法滿足.因此，為了增強(qiáng)格基前向安全的無(wú)證書(shū)簽名方案的應(yīng)用性與安全性，我們?cè)赗O_LFC_SIG的基礎(chǔ)上，研究了基于標(biāo)準(zhǔn)模型的ST_LFC_SIG方案.本節(jié)給出方案的具體實(shí)現(xiàn).

需要注意的是，本文提出的ST_LFC_SIG方案是第1個(gè)標(biāo)準(zhǔn)模型下基于格的無(wú)證書(shū)數(shù)字簽名方案，方案具體由5個(gè)多項(xiàng)式時(shí)間的算法構(gòu)成.

若用戶(hù)ID為第1次生成密鑰，運(yùn)行〈B,TB〉=TrapGen(n,q,m)得到密鑰根矩陣〈B,TB〉.

5) 驗(yàn)證算法Verify.輸入(ID,(ε,h),μ,t)，算法輸出Accept當(dāng)且僅當(dāng)：

6 ST_LFC_SIG的安全性分析

證明. 假設(shè)存在敵手A1可以偽造簽名，則構(gòu)造多項(xiàng)式算法步驟如下.

對(duì)i∈[1,d]，從分布G中逐列采樣得到小范數(shù)矩陣Di∈m×kq，且以壓倒性概率成立.設(shè)正整數(shù)pi，〈E,TE〉=TrapGen(n,q,k)，Ci=ADi+piE，其中隨機(jī)矩陣A∈n×mq為SIS實(shí)例.則Ci統(tǒng)計(jì)不可區(qū)分于n×kq上的隨機(jī)均勻矩陣.對(duì)i∈[1,l]，設(shè)Fi∈n×mq為隨機(jī)均勻矩陣.

2) 敵手可以適應(yīng)性地進(jìn)行如下問(wèn)詢(xún).

如果p=0 modq第1次出現(xiàn)，C隨機(jī)生成(m+k)×m上的矩陣并返回給敵手作為部分密鑰應(yīng)答，設(shè)置Lsig中{ID,t}對(duì)應(yīng)表項(xiàng)的b=1.若p=0不為第1次出現(xiàn)，C終止游戲.

若p≠0，挑戰(zhàn)者C從G中逐列采樣得到矩陣∈m×m.由于TE為Λ⊥(pE)的短基，C可由得到，從而m×m.將作為部分密鑰應(yīng)答返回?cái)呈?顯然，將保存于Lsig中.

③ 密鑰更新問(wèn)詢(xún)：敵手提交[tj,ti]和ID，挑戰(zhàn)者C調(diào)用部分密鑰問(wèn)詢(xún)并以{ID,ti}作為輸入進(jìn)行部分密鑰更新.如果游戲沒(méi)有終止，且ID對(duì)應(yīng)于敵手之外的用戶(hù)，則挑戰(zhàn)者C調(diào)用KeyUpdate算法完成公鑰和私密值更新.

若{ID,t}表項(xiàng)存在，但b=1，C終止游戲.

證畢.

證明. 假設(shè)存在敵手A2可以偽造簽名，則構(gòu)造多項(xiàng)式算法步驟如下.

1) 系統(tǒng)建立Setup.設(shè)設(shè)n,M,α,k,b,d,l,T,q,m,L,δ,H1,H2，參數(shù)序列{σ0,σ1,…,σT}，參數(shù)s,δ與定理3中一樣.〈A,TA〉=TrapGen(n,q,m).設(shè)i∈[1,d]，隨機(jī)均勻小范數(shù)矩陣Ci∈n×kq.對(duì)i∈[1,l]，逐列從G中采樣得到Di∈m×mq，則Fi=B0Di統(tǒng)計(jì)不可區(qū)分于n×mq上的隨機(jī)均勻分布，其中隨機(jī)矩陣B0為SIS實(shí)例.

① Setγ∈[1,Q],t*∈[1,T]*ID*為第r次秘鑰問(wèn)詢(xún)對(duì)應(yīng)的身份*

② Foreacht≤t*do

③h=H1(ID*|t)；

⑥ End Foreach

⑦B=B0RID*|t*RID*|t*-1…RID*|1；*B為ID*對(duì)應(yīng)的秘鑰根矩陣*

⑧B′=B0；

⑨ Forj=t*+1 toT

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

2) 敵手可以適應(yīng)性地進(jìn)行如下問(wèn)詢(xún).

① 公鑰問(wèn)詢(xún)：敵手提交{ID,t}，若ID不為第γ次問(wèn)詢(xún)身份，挑戰(zhàn)者C首先查詢(xún)表Lsig看是否有對(duì)應(yīng)于身份ID的密鑰根矩陣.如果沒(méi)有，由SampleRwithBasis(B)得到R←Dm×m和Λ⊥(BR-1)的基TBR，C將BR-1作為當(dāng)前身份ID的密鑰根矩陣，并將其和TBR一起保存到Lsig中.C調(diào)用簽名方案的KeyExtract和KeyUpdate(t>1)算法正常計(jì)算用戶(hù)的公鑰應(yīng)答.

敵手A2已知主密鑰MSK，因此不需要進(jìn)行部分密鑰問(wèn)詢(xún).部分密鑰的更新也可以由敵手自己完成.

③ 私密值更新問(wèn)詢(xún)：若ID不為第γ次問(wèn)詢(xún)身份時(shí)，敵手公鑰和私密值均正常生成，因此挑戰(zhàn)者C可以直接調(diào)用KeyUpdate算法完成更新.

若ID為第γ次問(wèn)詢(xún)身份，設(shè)更新區(qū)間[tj,ti]，若tj≥t*或ti>t*≥tj，C可以查表Lsig得到時(shí)刻t′=max(tj,t*+1)的公鑰和私密值，之后可以調(diào)用KeyUpdate算法在[t′,ti]上完成更新.若t*≥ti，C退出.

證畢.

7 方案安全性與效率對(duì)比分析

文獻(xiàn)[33]對(duì)無(wú)證書(shū)簽名方案的安全模型進(jìn)行了分析，并依據(jù)簽名問(wèn)詢(xún)與私密值問(wèn)詢(xún)，對(duì)第1類(lèi)強(qiáng)敵手和第2類(lèi)強(qiáng)敵手分別給出了8種和4種不同能力的敵手攻擊等級(jí)，歸納如表1和表2所示.N-Sign表示在簽名問(wèn)詢(xún)，若身份ID對(duì)應(yīng)的公鑰發(fā)生過(guò)替換，則拒絕應(yīng)答.S-Sign表示無(wú)論公鑰是否發(fā)生替換，都響應(yīng)敵手的簽名問(wèn)詢(xún).

Table 1 Eight Different Attack Levels of Type 1 Adversary表1 敵手1對(duì)應(yīng)的8種攻擊等級(jí)

Table 2 Four Different Attack Levels of Type 2 Adversary表2 敵手2對(duì)應(yīng)的4種攻擊等級(jí)

由表1和表2可以看出，S -Type 1和S -Type 2類(lèi)型的S-Type敵手具有最強(qiáng)的攻擊能力.表3將本文提出的隨機(jī)預(yù)言模型下的RO_LFC_SIG方案與標(biāo)準(zhǔn)模型下的ST_LFC_SIG方案，以及Kim等人[17]和Tian等人[18]的格基無(wú)證書(shū)簽名方案，和文獻(xiàn)[12-15]中的無(wú)證書(shū)簽名方案進(jìn)行安全性對(duì)比.

由表3可以看出，本文提出的無(wú)證書(shū)簽名方案不僅具有抗量子攻擊的能力，具有前向安全性，同時(shí)所基于的敵手模型攻擊等級(jí)較高，因此方案具有較好的安全性.更進(jìn)一步地，本文提出的ST_LFC_SIG方案是第1個(gè)基于格的標(biāo)準(zhǔn)模型下的無(wú)證書(shū)簽名方案，較之文獻(xiàn)[12-15，17-18]中以及RO_LFC_SIG隨機(jī)預(yù)言模型下的簽名方案，在實(shí)際應(yīng)用中的安全性更高.

Table 3 Comparison of Security表3 方案安全性對(duì)比

在效率對(duì)比方面，本文除了選擇文獻(xiàn)[17-18]中的隨機(jī)預(yù)言模型下的格基無(wú)證書(shū)簽名方案外，還選擇了Yao等人[2]和Zhang等人[20]的FSIBS以及Rückert[26]的隨機(jī)格簽名方案，雖然后3種方案并不是無(wú)證書(shū)簽名方案，但由于其均基于隨機(jī)格，因此可以作為時(shí)間和空間復(fù)雜度對(duì)比的參照.

設(shè)參數(shù)與第3節(jié)方案中定義的相同，n為安全參數(shù)，m≥5nlbq，k為正整數(shù).TSam,TBas,TTrap,TRand,TExt分別為算法SamplePre,BasicDel,TrapGen,RandBasis,ExtBasis運(yùn)行時(shí)間.Tmul為一次標(biāo)量乘法耗費(fèi)時(shí)間.7種方案的漸近性復(fù)雜度對(duì)比如表4所示.

Table 4 Comparison of Asymptotic Complexity表4 漸近復(fù)雜度對(duì)比

設(shè)k≤n4，則由表4可以看出，在保證安全性的基礎(chǔ)上，本文方案的公鑰尺寸優(yōu)于其他的格基或身份基簽名方案.標(biāo)準(zhǔn)模型下的ST_LFC_SIG簽名方案的簽名長(zhǎng)度優(yōu)于除文獻(xiàn)[20]以外的其他方案.在私鑰長(zhǎng)度方面，本文方案優(yōu)于文獻(xiàn)[17，26]的方案，比Yao等人[2]、Tian等人[18]和Zhang等人[20]的FSIBS方案略大.這主要是由于無(wú)證書(shū)簽名方案需要利用部分密鑰和私密值2個(gè)子部分來(lái)構(gòu)造基于隨機(jī)格的2個(gè)PSIS等式，從而實(shí)現(xiàn)對(duì)不誠(chéng)實(shí)用戶(hù)和惡意KGC的前向安全強(qiáng)不可偽造性，而Zhang等人[20]的方案只考慮了隨機(jī)預(yù)言模型下的外部敵手.此外，本文通過(guò)引入變量k降低了簽名長(zhǎng)度，并通過(guò)密鑰根矩陣保證了較小的公鑰長(zhǎng)度以及安全證明中正確的敵手視角，而文獻(xiàn)[20]中的安全證明由于缺少與身份綁定的密鑰根矩陣的定義，將導(dǎo)致敵手關(guān)于同一挑戰(zhàn)身份與挑戰(zhàn)時(shí)刻的2次公鑰問(wèn)詢(xún)產(chǎn)生不同的應(yīng)答結(jié)果.而Yao等人[2]和Tian等人[18]的方案則不具備前向安全性.因此與文獻(xiàn)[2,18,20]相比，本文方案的安全性更高.

時(shí)間復(fù)雜度方面，根據(jù)文獻(xiàn)[30-31]，有TExt

由以上分析可知，本文提出的RO_LFC_SIG和ST_LFC_SIG無(wú)證書(shū)簽名方案首次在不引入第三方代理的條件下基于隨機(jī)格實(shí)現(xiàn)了前向安全性與無(wú)證書(shū)的結(jié)合.同時(shí)，ST_LFC_SIG方案也是第1個(gè)基于格的標(biāo)準(zhǔn)模型下可證安全的無(wú)證書(shū)簽名方案，并解決了密鑰泄露問(wèn)題.通過(guò)以上安全性與效率的對(duì)比分析可知，在保證相對(duì)較低的時(shí)空復(fù)雜度的基礎(chǔ)上，隨機(jī)預(yù)言模型下RO_LFC_SIG方案和標(biāo)準(zhǔn)模型下的ST_LFC_SIG方案均可以達(dá)到較好的安全性與實(shí)用性.

8 結(jié)束語(yǔ)

本文基于格基委派技術(shù)，針對(duì)密鑰泄露的前向安全性，在提出隨機(jī)預(yù)言模型下RO_LFC_SIG方案的基礎(chǔ)上，設(shè)計(jì)了標(biāo)準(zhǔn)模型下前向安全的無(wú)證書(shū)簽名方案ST_LFC_SIG，并給出了2個(gè)方案的具體構(gòu)造.同時(shí)，基于隨機(jī)預(yù)言模型和標(biāo)準(zhǔn)模型，證明了所提出的方案面對(duì)2類(lèi)強(qiáng)敵手在適應(yīng)性選擇消息、選擇身份攻擊下的前向安全強(qiáng)不可偽造性FSU-AMAIA.本文方案的安全性建立在不誠(chéng)實(shí)用戶(hù)和惡意密鑰生成中心的基礎(chǔ)上，較之已有方案中的外部敵手模型，安全性更高.最后，通過(guò)對(duì)比分析，證明了本文提出的前向安全無(wú)證書(shū)簽名方案具有較好的安全性與實(shí)用性.

本文提出的ST_LFC_SIG簽名方案是第1個(gè)基于隨機(jī)格的標(biāo)準(zhǔn)模型下可證安全的無(wú)證書(shū)數(shù)字簽名方案，并結(jié)合了前向安全性以抵御密鑰泄露的威脅.

由于本文提出的2個(gè)無(wú)證書(shū)簽名方案主要是基于隨機(jī)格進(jìn)行方案構(gòu)造，因此依然存在改進(jìn)的空間，一個(gè)潛在的思路是采用理想格替代隨機(jī)格優(yōu)化存儲(chǔ)空間，但是標(biāo)準(zhǔn)模型下基于理想格的簽名方案的安全性證明是目前一個(gè)研究難點(diǎn).因此我們下一步的研究目標(biāo)將集中在設(shè)計(jì)基于理想格的前向安全無(wú)證書(shū)簽名方案，以提高方案的整體效率.

[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)(陳虎, 朱昌杰, 宋如順. 高效的無(wú)證書(shū)簽名和群簽名方案[J]. 計(jì)算機(jī)研究與發(fā)展, 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)(于佳, 孔凡玉, 郝蓉, 等. 一個(gè)基于雙線性映射的前向安全門(mén)限簽名方案的標(biāo)注[J]. 計(jì)算機(jī)研究與發(fā)展, 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)(魏江宏, 劉文芬, 胡學(xué)先. 前向安全的密文策略基于屬性加密方案[J]. 通信學(xué)報(bào), 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@#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@#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

國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2017YFB0802302) This work was supported by the National Key Research and Development Program of China (2017YFB0802302)

譚成翔(jerrytan@#edu.cn)

TP309