前向安全的格基代理簽名

謝 佳 胡予濮 江明明

1(河南財(cái)經(jīng)政法大學(xué)計(jì)算機(jī)與信息工程學(xué)院 鄭州 450046) 2(綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室(西安電子科技大學(xué)) 西安 710071) 3(淮北師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 安徽淮北 235000)

(xiejia199325@163.com)

1996年Mambo等人[1]首次提出代理簽名這一概念.在代理簽名模型中，原始簽名人委托代理人進(jìn)行簽名，簽名驗(yàn)證者能夠有效區(qū)分當(dāng)前簽名來自代理簽名人還是原始簽名人.由于其在移動通信、分布式系統(tǒng)和電子拍賣等領(lǐng)域的廣泛應(yīng)用[2-5]，2003年前后，各種代理簽名[6-9]如雨后春筍般涌現(xiàn).然而，量子計(jì)算機(jī)的出現(xiàn)使得我們對代理簽名的安全性有了更高的要求.2010年Jiang等人[10]首次利用盆景樹模型構(gòu)造了格基代理簽名方案.該方案在標(biāo)準(zhǔn)模型下代理簽名人不能偽造原始簽名人進(jìn)行簽名權(quán)力委托，但原始簽名人卻可以成功偽造出代理簽名者的簽名.2011年夏峰等人[11]和Wang等人[12]同樣使用盆景樹模型構(gòu)造了格上代理簽名方案.為了克服格維數(shù)隨代理權(quán)利委托逐漸增大的問題，Kim等人[13]使用格上固定維數(shù)的委派技術(shù)構(gòu)造了格上高效的身份基代理簽名方案.隨后，更加高效的格基代理簽名方案[14-16]相繼被提出.

在傳統(tǒng)的簽名方案中，一旦簽名密鑰暴露，簽名就變得不可信任，無論該簽名來自密鑰泄露事件之前還是密鑰泄露之后.為了解決這個問題，1997年Anderson[17]提出了前向安全簽名的概念.前向安全簽名，顧名思義，即使暴露當(dāng)前時段簽名密鑰，也不會影響之前簽名的有效性.因而，前向安全簽名可以減少密鑰暴露的威脅.前向安全的簽名方案大致可分為2類：1)常規(guī)前向安全簽名[18-21]；2)具有特殊性質(zhì)的前向安全簽名，如身份基前向安全簽名[22-24]、前向安全閾值簽名[25-26]、前向安全代理簽名[27-32]、前向安全群簽名[33-37]、前向安全的序列聚合簽名[38]等.

由于兼顧可代理和前向安全的優(yōu)勢，前向安全的代理簽名自提出以來得到了快速發(fā)展[27-32].然而，現(xiàn)存的前向安全代理簽名大都基于離散對數(shù)或整數(shù)分解問題，而Shor[39]早在1997年已經(jīng)指出，經(jīng)典數(shù)論問題(大整數(shù)分解和離散對數(shù)問題)在量子計(jì)算環(huán)境下已不再安全.隨著量子計(jì)算機(jī)的逐漸推廣，尋找量子免疫的前向安全代理簽名就顯得尤為迫切.

幸運(yùn)的是，格公鑰密碼以其存在任意實(shí)例到最壞實(shí)例的規(guī)約、計(jì)算簡單高效(格基密碼的相關(guān)運(yùn)算只是簡單的矩陣向量乘法和模加法)、能抗量子攻擊等諸多優(yōu)勢，成為后量子時代密碼算法的不二選擇.因而，基于格基困難問題構(gòu)造前向安全代理簽名可能會是一個很好的嘗試.

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

1) 基于格上的小整數(shù)解問題，我們提出了首個隨機(jī)預(yù)言機(jī)模型下前向安全的格基代理簽名；

2) 借助于格基委派技術(shù)和消息添加技術(shù)，我們構(gòu)造了標(biāo)準(zhǔn)模型下前向安全的格基代理簽名.

1 預(yù)備知識

本節(jié)我們將對文中用到的一些符號和參考文獻(xiàn)中已知的一些結(jié)論作出說明.

1.1 基本定義

1.2 格的相關(guān)知識

定義1.格.已知矩陣B=(b1‖b2‖…‖bm)，b1,…,bm∈Rn為m個線性無關(guān)向量，則由B生成的格Λ為

其中，格Λ的秩、格Λ的維數(shù)分別為m和n，B為格Λ的一組基.

DΛ,s,c(x)=ρs,c(x)ρs,c(Λ)，

引理1.給定任意實(shí)數(shù)σ>0，正整數(shù)m，有:

1) 存在1個PPT算法SampleD(A,T,σ,c)能夠輸出一個分布統(tǒng)計(jì)接近于DΛ⊥(A),σ,c的向量v；

2) 存在一個PPT算法SamplePre(A,T,σ,u)能夠輸出一個分布統(tǒng)計(jì)接近于DΛu(A),σ的向量v.

2 前向安全代理簽名的定義

本節(jié)我們將對前向安全代理簽名的定義以及安全性證明作出闡述.

定義6.前向安全代理簽名方案.1個完整的前向安全簽名方案由7個多項(xiàng)式時間算法構(gòu)成：系統(tǒng)建立算法Setup、密鑰生成算法Keygen、代理委派算法Delegate、委派認(rèn)證算法D-Verify、密鑰更新算法KeyUpdate、代理簽名算法ProxySign和簽名驗(yàn)證算法ProxyVerify.

1) Setup.輸入安全參數(shù)n，密鑰生成中心(KGC)運(yùn)行該算法生成并輸出系統(tǒng)公共參數(shù)PP.

2) Keygen.輸入公共參數(shù)PP，KGC運(yùn)行該算法輸出原始簽名人Alice的公私鑰對(ska,pka)和代理簽名人的公私鑰對(skb,pkb).

3) Delegate.為了將簽名權(quán)利委派給代理人Bob，原始簽名人Alice以自身私鑰ska和Bob的身份idb為輸入，運(yùn)行該算法生成代理簽名私鑰SKid|0并將該私鑰發(fā)送給Bob.

4) D-Verify.接收到SKid|0后，Bob驗(yàn)證其是否為Alice的合法委派私鑰，若否，則返回至上一步繼續(xù)請求委派.

5) KeyUpdate.輸入當(dāng)前時間i、代理簽名者身份idb以及之前時段的代理簽名私鑰SKid|i-1，該算法輸出當(dāng)前最新的代理簽名私鑰SKid|i.

6) ProxySign.輸入簽名消息m和當(dāng)前時間i，Bob利用代理簽名私鑰SKid|i生成簽名sigi，并將sigi作為m的代理簽名.

7) ProxyVerify.以(sigi,m)為輸入，當(dāng)且僅當(dāng)sigi為消息m的合法簽名時，算法輸出為“1”；否則輸出“0”.

定義7.正確性.定義6的前向安全代理簽名方案中，簽名方案滿足正確性是指ProxyVerify(sigi,m,id,i)能以壓倒勢的概率輸出“1”.

定義8.不可偽造性.考慮前向安全代理簽名方案的不可偽造性時，往往有2種安全威脅要考慮：

1) 敵手A1，即未被授權(quán)的代理簽名人想要模仿被授權(quán)的代理簽名人進(jìn)行簽名；

2) 敵手A2，即惡意的原始簽名人試圖代替代理簽名人完成代理簽名.

對于任意多項(xiàng)式時間的敵手A1和A2，挑戰(zhàn)者能夠贏得以下游戲(游戲由Setup，Queries和Forgery三個步驟組成)的概率均為可忽略時，我們稱該方案是不可偽造的，且是前向安全的.

1) Setup.挑戰(zhàn)者C運(yùn)行方案的初始化算法，生成系統(tǒng)公共參數(shù)PP，并將其向敵手公布.

2) Queries.在詢問階段敵手可作3個詢問.

① DelegateQuery.當(dāng)敵手發(fā)送代理簽名者身份id作委派詢問時，挑戰(zhàn)者C生成相應(yīng)的代理簽名私鑰SKid|0并將其返還給敵手.

② BereakinQuery.當(dāng)敵手發(fā)送時段j，代理簽名者身份idb作詢問時，挑戰(zhàn)者C生成當(dāng)前時段的代理簽名私鑰SKid|j并將其返還給敵手.

③ ProxySignQuery.當(dāng)敵手發(fā)送(id,i,m)作代理簽名詢問時，挑戰(zhàn)者C生成當(dāng)前時段的代理簽sigi并將其返還給敵手.

① 1≤t*

3 隨機(jī)預(yù)言機(jī)模型下格基前向安全代理簽名

3.1 方案描述

3) Delegate.為了將簽名權(quán)利委派給代理人Bob，原始簽名人Alice計(jì)算H(ida|idb|0)=R0=Ra→b|0.隨后Alice運(yùn)行引理6中的格基委派算法BasisDel(A,R0,TA,σ0)生成并輸出Ta→b|0=[t1‖t2‖…‖tm]作為Alice授權(quán)給Bob的代理簽名密鑰.

6) ProxySign.輸入簽名消息m，Bob計(jì)算μ=H1(ida|idb|m|i)，隨后運(yùn)行引理3中的原像采樣算法得向量ui←SamplePre(Aa→b|i,Ta→b|i,si,μ)和vi←SamplePre(Bb|i,Tb|i,si,μ).最后，Bob輸出(ui,vi)作為當(dāng)前時段對消息m的簽名.

7) ProxyVerify.接收到簽名之后，驗(yàn)證者首先計(jì)算矩陣Ra→b|i=H(ida|idb|i)…H(ida|idb|0)和矩陣Rb|i=H(idb|i)…H(idb|1)，μ=H1(ida|idb|m|i).算法輸出為“1”，當(dāng)且僅當(dāng)：

3.2 正確性

定理1.3.1節(jié)構(gòu)造的格基前向安全代理簽名滿足正確性.

證明. 假設(shè)(ui,vi)為對消息m的簽名，由ProxySign可知ui,vi分別來自2個原像采樣算法，即由SamplePre(Aa→b|i,Ta→b|i,si,μ)求得ui以及vi←SamplePre(Bb|i,Tb|i,si,μ).由引理3可知ui和vi分別服從分布DΛμ(Aa→b|i),si和DΛμ(Bb|i),si.因而可得Aa→b|iui=μmodq，Bb|iui=μmodq.由KeyUpdate以及引理6可知：

A(H(ida|idb|i)…H(ida|idb|0))-1=

證畢.

3.3 安全性分析

定理2.假定格上的SIS問題在多項(xiàng)式時間算法攻擊下是困難的，則以上格上的前向安全代理簽名方案在隨機(jī)預(yù)言機(jī)模型下是存在性不可偽造的.

引理7.假定格上的SIS問題在多項(xiàng)式時間算法攻擊下是困難的，則3.1節(jié)構(gòu)造的格前向安全代理簽名方案在類型1敵手攻擊下是存在性不可偽造的.

調(diào)用：調(diào)用格上的SIS問題實(shí)例，模擬器C需要返還一個合法的解.

首先，我們假設(shè)3個條件成立：

1) 對于每一個時間段i=0,1,…,T-1，敵手A1可以適應(yīng)性地對任意身份作多項(xiàng)式次H詢問；

2) 對于任意的j

3) 在對任意簽名人作簽名私鑰詢問之前，假定A1已經(jīng)預(yù)先完成相關(guān)的H和H1詢問.

Queries.當(dāng)敵手A1偽造簽名時，假設(shè)C隨機(jī)選擇i*(1≤i*≤T-1)作為偽造簽名的時段.敵手A1可以適應(yīng)性地作詢問:

1)H-Oracle-Query.對于任意的時間i=0,1,…,T-1，A1可以適應(yīng)性地對任意身份作H詢問.

模擬者C維持一個列表L1={ida,idb,i,Ri}.輸入身份和時間的一組數(shù)據(jù)(ida,idb,i)，C首先在列表L1中查找(ida,idb,i).若(ida,idb,i)已存在于L1中，則模擬者C返還相應(yīng)的Ri給敵手A1.否則，C從Dm×m中選擇1個矩陣Ri并存儲(ida,idb,i,Ri)在列表L1中.最后，模擬者C返還相應(yīng)的Ri給敵手A1.

2) DelegateQuery.模擬者C維持1個列表L3={ida,idb,0,Ta→b|0}.假定Q表示敵手能夠作委派詢問的最大次數(shù)，敵手A1隨機(jī)選擇l∈{1,2,…,Q}，C所作回應(yīng)如下：

如果idb并非第l次委派詢問，則C回應(yīng)如下.輸入身份和時間的一組數(shù)據(jù)(ida,idb,0)，C首先查找列表L1找到其對應(yīng)的Hash值R0并運(yùn)行BasisDel(A,R0,TA,σ0)生成Ta→b|0.最后，模擬者C將(ida,idb,0,Ta→b|0)存儲在列表L3中，并將Ta→b|0發(fā)送給A1.

如果idb剛好是第l次委派詢問，則C終止操作.

3) KeyUpdateQueries.C維持列表L4={ida,idb,i,Aa→b|i,Ta→b|i,Bb|i,Tb|i}.當(dāng)敵手A1發(fā)送(ida,idb,i)作簽名私鑰詢問時，C所作回應(yīng)為：

如果idb剛好是第l次委派詢問，則C回應(yīng)為:

③ 如果i*+1

4)H1-Oracle-Queries.C維持列表L5={ida,idb,i,m,ui,vi,Aa→b|iui}.當(dāng)敵手A1發(fā)送(ida,idb,i,m)作H1詢問時，C所作回應(yīng)如下：如果L5列表中已經(jīng)存在(ida,idb,i,m)，則將其對應(yīng)的Aa→b|iui作為其Hash值H1(ida|idb|m|i)發(fā)送敵手；否則，C在列表L1，L2和L4中分別查找H(ida|idb|i)，H(idb|i))和(ida,idb,i,Aa→b|i,Ta→b|i,Bb|i)，然后模擬者計(jì)算ui←SampleDom(1n)以及Aa→b|iui，由于A1知道TB，在做完H詢問后敵手A1可知Tb|i，而后計(jì)算vi←SamplePre(Bb|i,Tb|i,Aa→b|iui,si).最后，模擬者將(ida,idb,i,m,ui,vi,Aa→b|iui)存儲于列表L5中，并將Aa→b|iui作為其Hash值H1(ida|idb|m|i)發(fā)送敵手A1.

5) ProxySignQueries.當(dāng)敵手A1發(fā)送(ida,idb,i,m)作代理簽名詢問時，C所作回應(yīng)為：

① 如果idb并非第l次委派詢問，C在列表L5中查找(ida,idb,i,m)，并將其對應(yīng)的(ui,vi)作為代理簽名發(fā)送給敵手A1.

② 如果idb剛好是第l次委派詢問，當(dāng)i*

6) BreakinQueries.當(dāng)敵手A1發(fā)送(idb,j)作密鑰更新詢問時，C所作回應(yīng)為：

① 如果idb并非第l次委派詢問，C在列表L4中查找(Ta→b|j,Tb|j)，并將其作為此時的簽名私鑰發(fā)送給敵手A1.

② 如果idb為第l次委派詢問且j=i*，C終止計(jì)算.

1) 1≤t*

證畢.

引理8.假定格上的SIS問題在多項(xiàng)式時間算法攻擊下是困難的，則以上格上的前向安全代理簽名方案在類型2敵手攻擊下是存在性不可偽造的.

調(diào)用：調(diào)用格上的SIS問題實(shí)例，模擬器C需要返還一個合法的解.

首先，我們假設(shè)3個條件成立：

1) 對于每一個時間周期i=0,1,…,T-1，敵手A2可以適應(yīng)性地對任意身份作多項(xiàng)式次H詢問；

2) 對于任意的j

3) 在對任意簽名人作簽名私鑰詢問之前，假定A2已經(jīng)預(yù)先完成相關(guān)的H和H1詢問.

Queries.當(dāng)敵手A2偽造簽名時，假設(shè)C隨機(jī)選擇i*(1≤i*≤T-1)作為偽造簽名的時段.敵手A2可以適應(yīng)性地作詢問.

1)H-Oracle-Query.對于任意的時間i=0,1,…,T-1，A2可以適應(yīng)性地對任意身份作H詢問.

模擬者C維持一個列表L6={ida,idb,i,Ri}.輸入身份和時間的一組數(shù)據(jù)(ida,idb,i)，C首先在列表L6中查找(ida,idb,i).若(ida,idb,i)已存在在L6中，則模擬者C返還相應(yīng)的Ri給敵手A2.否則，C從Dm×m中選擇一個矩陣Ri并存儲(ida,idb,i,Ri)在列表L6中.最后，模擬者C返還相應(yīng)的Ri給敵手A2.

2) DelegateQuery.模擬者C維持一個列表L8={ida,idb,0,Ta→b|0}.假定Q表示敵手能夠做的委派詢問的最大次數(shù)，敵手A2隨機(jī)選擇l∈{1,2,…,Q}，C所作回應(yīng)如下：

如果idb并非第l次委派詢問，則C回應(yīng)為:輸入身份和時間列表(ida,idb,0)，C首先查找列表L6找到其對應(yīng)的Hash值R0并運(yùn)行BasisDel(A,R0,TA,σ0)生成Ta→b|0.最后，模擬者C將(ida,idb,0,Ta→b|0)存儲在列表L8中，并將Ta→b|0發(fā)送給A2.

如果idb剛好是第l次委派詢問，則C終止操作.

3) KeyUpdateQueries.C維持列表L9={ida,idb,i,Aa→b|i,Ta→b|i,Bb|i,Tb|i}.當(dāng)敵手A2發(fā)送(ida,idb,i)作簽名私鑰詢問時，C所作回應(yīng)如下.

如果idb剛好是第l次委派詢問，則C回應(yīng)為:

③ 如果i*+1

4)H1-Oracle-Queries.C維持列表L10={ida,idb,i,m,ui,vi,Bb|ivi}.當(dāng)敵手A2發(fā)送(ida,idb,i,m)作H1詢問時，C所作回應(yīng)為：如果L10列表中已經(jīng)存在(ida,idb,i,m)，則將其對應(yīng)的Bb|ivi作為其Hash值H1(ida|idb|m|i)發(fā)送敵手；否則，C在列表L6，L7和L9中分別查找H(ida|idb|i)，H(idb|i))和(ida|idb,i,Aa→b|i,Ta→b|i,Bb|i)，然后模擬者采樣可得vi←SampleDom(1n)并計(jì)算Bb|ivi.由于敵手A2知道TA，在做完H詢問后敵手A2可知Ta→b|i，然后計(jì)算ui←SamplePre(Aa→b|i,Ta→b|i,Bb|i,si)，并將數(shù)據(jù)(ida,idb,i,m,ui,vi,Bb|ivi)存儲于列表L10中.

5) ProxySignQueries.當(dāng)敵手A2發(fā)送(ida,idb,i,m)作代理簽名詢問時，C所作回應(yīng)為：

① 如果idb并非第l次委派詢問，C在列表L10中查找(ida,idb,i,m)，并將其對應(yīng)的(ui,vi)作為代理簽名發(fā)送給敵手A2.

② 如果idb剛好是第l次委派詢問，當(dāng)i*

6) BreakinQueries.當(dāng)敵手A2發(fā)送(idb,j)作密鑰更新詢問時，C所作回應(yīng)為：

① 如果idb并非第l次委派詢問，C在列表L9中查找(Ta→b|j,Tb|j)，并將其作為此時的簽名私鑰發(fā)送給敵手A2；

② 如果idb為第l次委派詢問且j=i*，C終止計(jì)算.

1) 1≤t*

證畢.

由引理7和引理8可知，定理2必然成立.故而3.1節(jié)構(gòu)造的前向安全的格基代理簽名在隨機(jī)預(yù)言機(jī)模型下是不可偽造的，且是前向安全的.

3.4 效率分析

由表1容易看出，文獻(xiàn)[14-15]中方案的代理私鑰長度和代理簽名長度明顯比其他方案的相應(yīng)長度短.這是由于采用了拋棄采樣技術(shù)而非原像采樣技術(shù)，而拋棄采樣技術(shù)是提高格基簽名效率的主要應(yīng)用手段.本文提出的代理簽名方案由于要實(shí)現(xiàn)前向安全性，故而采用了格基委派技術(shù)和原像采樣算法技術(shù)(而非拋棄采樣技術(shù)，若采用拋棄采樣技術(shù)則無法逐級實(shí)現(xiàn)密鑰更新)，因而，相較于文獻(xiàn)[13]，私鑰及簽名長度會隨著分級i增大而增加.

Table 1 The Efficiency Comparison of Different Schemes in Random Model

4 標(biāo)準(zhǔn)模型下格基前向安全代理簽名

4.1 方案描述

4.2 正確性

定理3.以上格基前向安全代理簽名滿足正確性.

證明. 假設(shè)(ui,vi)為消息m的簽名，由ProxySign可知向量ui←SamplePre(Aa→b|i,Ta→b|i,si,μ)以及vi←SamplePre(Bb|i,Tb|i,si,μ).由引理3可知ui和vi分別服從分布DΛμ(Aa→b|i),si和DΛμ(Bb|i),si.因而可得Aa→b|iui=μmodq，Bb|iui=μmodq.由KeyUpdate以及引理6可知：

證畢.

4.3 安全性分析

定理4.假定格上的SIS問題在多項(xiàng)式時間算法攻擊下是困難的，則以上格上的前向安全代理簽名方案在標(biāo)準(zhǔn)模型下是存在性不可偽造的.

引理9.假定格上的SIS問題在多項(xiàng)式時間算法攻擊下是困難的，則以上格上的前向安全代理簽名方案在類型1敵手攻擊下是存在性不可偽造的.

調(diào)用：調(diào)用格上的SIS問題實(shí)例，模擬器C需要返還一個合法的解.

5) 運(yùn)行SampleRwithBasis(Ai,j)，生成1個矩陣R～Dm×m以及格Λ⊥(Ai,jR-1)的1個小范數(shù)基T.

Queries.當(dāng)敵手A1偽造簽名時，假設(shè)C隨機(jī)選擇i*(1≤i*≤T-1)作為偽造簽名的時段.敵手A1可以適應(yīng)性地作詢問.

1) DelegateQuery.模擬者C維持一個列表L2={ida,idb,0,Ta→b|0}.假定Q表示敵手能夠做的委派詢問的最大次數(shù)，敵手A1隨機(jī)選擇l∈{1,2,…,Q}，C所作回應(yīng)為：

如果idb并非第l次委派詢問，挑戰(zhàn)者C執(zhí)行如下:

④ 挑戰(zhàn)者C將(ida,idb,0,Ta→b|0)存儲至列表L2中，并將Ta→b|0返還給敵手A1.

如果idb剛好是第l次委派詢問，則C終止操作.

2) KeyUpdateQueries.C維持列表L3={ida,idb,i,Aa→b|i,Ta→b|i,Bb|i,Tb|i}.當(dāng)敵手A1發(fā)送(ida,idb,i)作簽名私鑰詢問時，C所作回應(yīng)如下.

如果idb并非第l次委派詢問，則C回應(yīng)為：

④ C將(ida,idb,i,Aa→b|i,Ta→b|i,Bb|i,Tb|i)存儲至L3中，并將Ta→b|i和Tb|i返還給敵手.

如果idb剛好是第l次委派詢問，則C回應(yīng)為：

③ 如果i*+1

3) ProxySignQueries.挑戰(zhàn)者C維持一個列表L4=(ida,idb,i,m,ui,vi).當(dāng)敵手A1發(fā)送(ida,idb,i,m)作代理簽名詢問時，C作詢問應(yīng)答：

② 如果idb剛好是第l次委派詢問，挑戰(zhàn)者C執(zhí)行為:

Ⅱ.如果i*≤i

4) BreakinQueries.當(dāng)敵手A1發(fā)送(idb,j)作密鑰更新詢問時，C所作回應(yīng)為：如果idb并非第l次委派詢問，C在列表L3中查找(Ta→b|j,Tb|j)，并將其作為此時的簽名私鑰發(fā)送給敵手A1；如果idb為第l次委派詢問且j=i*，C終止計(jì)算.

1) 1≤t*

證畢.

引理10.假定格上的SIS問題在多項(xiàng)式時間算法攻擊下是困難的，則以上格上的前向安全代理簽名方案在類型2敵手攻擊下是存在性不可偽造的.

調(diào)用：調(diào)用格上的SIS問題實(shí)例，模擬器C需要返還一個合法的解.

5) 運(yùn)行SampleRwithBasis(Bi,j)，生成一個矩陣R～Dm×m以及格Λ⊥(Bi,jR-1)的一個小范數(shù)基T.

Queries.當(dāng)敵手A2偽造簽名時，假設(shè)C隨機(jī)選擇i*(1≤i*≤T-1)作為偽造簽名的時段.敵手A2可以適應(yīng)性地作詢問.

1) DelegateQuery.模擬者C維持一個列表L2={ida,idb,0,Ta→b|0}.假定Q表示敵手能夠做的委派詢問的最大次數(shù)，敵手A2隨機(jī)選擇l∈{1,2,…,Q}，C所作回應(yīng)：

如果idb并非第l次委派詢問，挑戰(zhàn)者C執(zhí)行如下.

③ 挑戰(zhàn)者C將(ida,idb,0,Ta→b|0)存儲至列表L2中，并將Ta→b|0返還給敵手A2.

如果idb剛好是第l次委派詢問，則C終止操作.

2) KeyUpdateQueries.C維持列表L3={ida,idbi,Aa→b|i,Ta→b|i,Bb|i,Tb|i}.當(dāng)敵手A1發(fā)送(ida,idb,i)作簽名私鑰詢問時，C所作回應(yīng).

如果idb并非第l次委派詢問，則C回應(yīng).

④ C將(ida,idb,i,Aa→b|i,Ta→b|i,Bb|i,Tb|i)存儲至L3中，并將Ta→b|i和Tb|i返還給敵手.

如果idb剛好是第l次委派詢問，則C回應(yīng):

③ 如果i*+1

3) ProxySignQueries.挑戰(zhàn)者C維持1個列表L4=(ida,idb,i,m,ui,vi).當(dāng)敵手A1發(fā)送(ida,idb,i,m)作代理簽名詢問時，C按照如下方式作詢問應(yīng)答：

如果idb并非第l次委派詢問，挑戰(zhàn)者C執(zhí)行如下：

① C首先在列表L3中查找其對應(yīng)的(Ta→b|i,Tb|i).

如果idb剛好是第l次委派詢問，挑戰(zhàn)者C執(zhí)行為：

② 如果i*≤i

4) BreakinQueries.當(dāng)敵手A1發(fā)送(idb,j)作密鑰更新詢問時，C所作回應(yīng)如下：如果idb并非第l次委派詢問，C在列表L3中查找(Ta→b|j,Tb|j)，并將其作為此時的簽名私鑰發(fā)送給敵手A1；如果idb為第l次委派詢問且j=i*，C終止計(jì)算.

1) 1≤t*

證畢.

由引理9和引理10可知，定理4必然成立.故而4.1節(jié)構(gòu)造的前向安全的格基代理簽名在標(biāo)準(zhǔn)模型下滿足不可偽造性和前向安全性.

5 總 結(jié)

鑒于其眾多的應(yīng)用場景，前向安全代理簽名自提出以來就受到了廣泛的關(guān)注.然而，隨著量子計(jì)算機(jī)的出現(xiàn)，基于傳統(tǒng)數(shù)論問題——大整數(shù)分解和離散對數(shù)的前向安全代理簽名方案在量子計(jì)算環(huán)境下已不再安全.因此，如何構(gòu)造量子免疫的前向安全代理簽名是后量子時代迫切需要解決的問題.

由于具備量子免疫性，計(jì)算簡單高效，任意實(shí)例下的安全性和最壞實(shí)例下的安全性相當(dāng)?shù)戎T多優(yōu)勢，格公鑰密碼成為后量子時代公鑰密碼的最佳選擇.本文基于格基困難問題——SIS問題提出了2個前向安全代理簽名方案.第1個簽名方案是在隨機(jī)預(yù)言機(jī)模型中被證明是不可偽造的；第2個簽名方案則是在標(biāo)準(zhǔn)模型中被證明是安全的.為了進(jìn)一步豐富格基簽名的應(yīng)用場景，在后續(xù)的工作中，我們將逐步關(guān)注具有特殊性質(zhì)的前向安全代理簽名，構(gòu)造格上安全的前向安全盲代理簽名、前向安全多級代理簽名，將成為我們今后的工作重心.