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

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

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

?

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

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

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

(1062842783@qq.com)

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

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

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

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

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

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

綜上所述，目前無證書簽名方案存在3個問題：

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

2) 已有無證書簽名方案的安全證明主要考慮外部敵手和惡意密鑰生成中心，而對來自于不誠實的簽名用戶的威脅抵抗能力不足；

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

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

本文的主要貢獻有4個方面：

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

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

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

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

1 相關(guān)工作

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

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

2 預(yù)備知識

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

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

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

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

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

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

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

引理5. 格基委派算法[32]：設(shè)q上小范數(shù)可逆矩陣(按離散高斯分布獨立抽取每一列)的集合為Dm×m，矩陣A∈n×mq，整數(shù)格Λ⊥(A)的短基TA∈m×m，高斯參數(shù)，矩陣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對應(yīng)的整數(shù)格Λ⊥(A|C)的基TF，且.

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

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

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

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

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

定義3. 前向安全強不可偽造性FSU-AMAIA：定義2類多項式時間強敵手：1)強敵手A1模擬內(nèi)部不誠實的用戶，不誠實的用戶指在簽名過程中，會在未獲得合法部分密鑰的情況下嘗試偽造自己或其他用戶的簽名，顯然，偽造自身某一時刻的簽名需要的安全性更高；2)強敵手A2模擬惡意的密鑰生成中心KGC，在文獻[8，18]中提出的安全模型的基礎(chǔ)上，給出針對2類強敵手的安全游戲Game1與Game2，如果敵手A1與A2分別贏得Game1和Game2的概率是可忽略的，則稱簽名方案在適應(yī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)性的進行如下問詢.

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

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

③ 公鑰替換問詢：敵手可以替換任意身份下的公鑰.

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

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

敵手Ab可以選擇變更用戶身份或簽名時刻并問詢密鑰和簽名，也可以直接進入偽造階段.

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

①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*未作為簽名問詢的應(yīng)答返回給敵手.

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

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

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

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

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

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

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

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

正確性：

4 RO_LFC_SIG的安全性分析

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

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

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

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

2) 敵手可以適應(yīng)性的進行如下問詢.

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

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

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

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

證畢.

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

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

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

2) 敵手可以適應(yīng)性的進行如下問詢.

敵手A2已知主密鑰MSK，因此不需要進行部分密鑰問詢.部分密鑰的更新也可以由敵手自己完成.

④H3問詢：與定理1相同.

證畢.

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

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

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

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

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

6 ST_LFC_SIG的安全性分析

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

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

2) 敵手可以適應(yīng)性地進行如下問詢.

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

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

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

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

證畢.

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

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]，隨機均勻小范數(shù)矩陣Ci∈n×kq.對i∈[1,l]，逐列從G中采樣得到Di∈m×mq，則Fi=B0Di統(tǒng)計不可區(qū)分于n×mq上的隨機均勻分布，其中隨機矩陣B0為SIS實例.

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

② Foreacht≤t*do

③h=H1(ID*|t)；

⑥ End Foreach

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

⑧B′=B0；

⑨ Forj=t*+1 toT

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

2) 敵手可以適應(yīng)性地進行如下問詢.

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

敵手A2已知主密鑰MSK，因此不需要進行部分密鑰問詢.部分密鑰的更新也可以由敵手自己完成.

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

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

證畢.

7 方案安全性與效率對比分析

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

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

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

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

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

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

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

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

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

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

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

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

8 結(jié)束語

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

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

由于本文提出的2個無證書簽名方案主要是基于隨機格進行方案構(gòu)造，因此依然存在改進的空間，一個潛在的思路是采用理想格替代隨機格優(yōu)化存儲空間，但是標(biāo)準(zhǔn)模型下基于理想格的簽名方案的安全性證明是目前一個研究難點.因此我們下一步的研究目標(biāo)將集中在設(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)(陳虎, 朱昌杰, 宋如順. 高效的無證書簽名和群簽名方案[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)(于佳, 孔凡玉, 郝蓉, 等. 一個基于雙線性映射的前向安全門限簽名方案的標(biāo)注[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é)報, 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

國家重點研發(fā)計劃項目(2017YFB0802302) This work was supported by the National Key Research and Development Program of China (2017YFB0802302)

譚成翔(jerrytan@#edu.cn)

TP309