標(biāo)準模型下前向安全的格基有序聚合簽名

謝 佳，胡予濮，高軍濤，王保倉，江明明

1.河南財經(jīng)政法大學(xué) 計算機與信息工程學(xué)院，鄭州 450046

2.西安電子科技大學(xué) 通信工程學(xué)院，西安 710071

3.淮北師范大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，安徽 淮北 235000

日志是計算機信息系統(tǒng)的一個關(guān)鍵組成部分，它們記錄了系統(tǒng)“什么時候由誰發(fā)生了什么”，具有一定的取證價值。因而，保護系統(tǒng)的日志安全就顯得尤為重要。為防止攻擊者篡改歷史日志，傳統(tǒng)審計方法將日志寫到只能追加記錄的設(shè)備上，或進行遠程記錄，但這無法防范惡意系統(tǒng)管理員篡改日志。為了減少惡意系統(tǒng)管理員帶來的威脅，前向安全簽名技術(shù)被引入到日志系統(tǒng)中。

前向安全簽名的概念[1]始于1997 年，用以減少密鑰泄露的問題。為了達到前向安全性，密鑰生成中心（key generation center，KGC）將時間劃分為k個離散時間段，并在不同時段內(nèi)使用不同的密鑰。其中，i+1 時段的簽名密鑰由密鑰更新算法以i時段簽名密鑰為輸入計算得出，此處1 ≤i

在安全日志系統(tǒng)中部署前向安全簽名方案的主要障礙之一是它的開銷。對于大量生成消息的日志系統(tǒng)來說，為每個消息存儲簽名是一項繁重的工作。有序聚合簽名[2]概念的引入可有效解決這一問題。在有序聚合簽名方案中，證書鏈的聚合是循序漸進進行的。舉個例子，用戶U1首先使用其簽名私鑰SK1計算并輸出對于消息m1的簽名sig1；隨后，以sig1為輸入，用戶U2使用其簽名私鑰SK2計算并輸出對消息m1、m2的簽名sig2；以用戶U1,U2,…,Ui-1對消息m1,m2,…,mi-1的簽名sigi-1為輸入，Ui使用其簽名私鑰SKi計算并輸出對于消息m1,m2,…,mi的簽名sigi；直至Uk完成簽名。k個用戶如此循序漸進地進行簽名，在保留了聚合簽名最小通信開銷的同時也完全保證了簽名對消息的不可否認性。

為了兼顧日志系統(tǒng)的安全性和效率，2007 年，第一個前向安全的有序聚合簽名方案——BLS-FssAgg簽名[3]應(yīng)運而生。然而，由于BLS-FssAgg簽名的構(gòu)造依賴于雙線性對問題，而雙線性對操作的巨大開銷必然使得簽名的驗證花銷巨大。次年，Ma 又提出了兩個實用的FssAgg 簽名方案[4]，分別為BM-FssAgg簽名和AR-FssAgg 簽名。在這兩個FssAgg 簽名方案中，簽名構(gòu)造過程均采用了QRn群上的乘法運算，從而使得公鑰、私鑰和簽名尺寸均達到常數(shù)級別，且秘鑰更新和簽名的時間復(fù)雜度也為常數(shù)，進而體現(xiàn)其實用性；且與文獻[3]中BLS-FssAgg 簽名相比，這兩個簽名的驗證速度分別提高了16 倍和4 倍。2018年，基于強RSA 假設(shè)和橢圓曲線上的離散對數(shù)問題，韋性佳先后提出了一種具有前向安全的非抵賴的基于身份的聚合簽名方案[5]和具備前向安全性質(zhì)的基于身份的代理聚合簽名方案[6]，并在隨機預(yù)言機模型下證明其滿足前向安全性和存在性不可偽造。但是，以上兩個聚合簽名均是無序的，因而不能適用于日志系統(tǒng)。2019 年，Kim 和Oh 提出了一個高效的適用于安全日志系統(tǒng)前向安全有序聚合簽名方案[7]——FAS 簽名。除了滿足前向安全性以及存在性不可偽造之外，值得一提的是，F(xiàn)AS 簽名的公鑰和私鑰的尺寸均是恒定的，密鑰尺寸與前向安全非聚合簽名BM簽名[1]相當(dāng)；同時，F(xiàn)AS 簽名將BM 簽名的驗證復(fù)雜度由O(k2) 降至O(lk)，其中l(wèi)表示哈希函數(shù)的輸出長度。2021 年，韋性佳和蘆殿軍[8]利用中國剩余定理，結(jié)合雙線性對技術(shù)，基于橢圓曲線循環(huán)群提出了一種具有前向安全性質(zhì)的聚合簽名方案，方案的前向安全性由強RSA 假設(shè)得以保證，且方案的雙向驗證性和不可偽造性同樣可證。然而，現(xiàn)存的幾個實用的前向安全有序聚合簽名均是基于傳統(tǒng)數(shù)論問題。與此同時，前向安全的具備其他特殊性質(zhì)的簽名[9-12]研究也正在如火如荼地開展中。然而，早在1997 年，Shor 在文獻[13]一文中開創(chuàng)性地指出經(jīng)典數(shù)論問題在量子計算環(huán)境下已不再安全。隨著量子計算機的逐漸商業(yè)，后量子時代已向人們走來，尋找量子免疫的前向安全有序聚合簽名已迫在眉睫。

美國國家標(biāo)準與技術(shù)研究所自2016 年開始便面向全球征集后量子密碼標(biāo)準。在2020 年7 月剛剛結(jié)束的第三輪密碼標(biāo)準的角逐中，勝出算法總共7 個，其中僅格公鑰密碼方案就占了5 個（其中加密算法3個，簽名算法2 個）。在美國國家標(biāo)準與技術(shù)研究所看來，這些基于格上困難問題的方案是公鑰加密和數(shù)字簽名方案中最有前途的通用算法。因而，基于格基困難問題構(gòu)造前向安全的有序聚合簽名可能會為后量子時代保證日志系統(tǒng)安全打開新的局面。

本文基于格上的小整數(shù)解問題，構(gòu)造了標(biāo)準模型下前向安全的格基有序聚合簽名方案。為達到高效率目的，方案借助于固定維數(shù)格基委派技術(shù)實現(xiàn)密鑰更新，達到前向安全性；隨后通過消息添加技術(shù)和原像采樣算法分別將待簽消息和格上困難問題嵌入到簽名中，使得簽名在標(biāo)準模型下是不可偽造的，且與現(xiàn)存的格基有序聚合簽名方案[14-17]相比，新方案在量子計算環(huán)境下仍然是前向安全的。

1 預(yù)備知識

定義1[18]（格）令B=(b1||b2||…||bn)，其中b1,b2,…,bn∈Rm是n個線性無關(guān)向量。則由矩陣B生成的格Λ定義為：

此時，n和m分別為格的Λ的秩和維數(shù)，B為其一組基。

定義2[18]（q-ary 格）定義m維滿秩q-ary 格，為：

其中，參數(shù)分別為素數(shù)q，正整數(shù)n和m，矩陣A∈，以及向量，且常將和分別簡寫為Λ⊥(A)和Λu(A)。

定義3[18]（高斯函數(shù)）給定正整數(shù)n和m，定義以σ∈R+為參數(shù)，c∈Rm為中心的高斯函數(shù)為ρσ,c(x)=exp(-π||x-c||2/σ2)。定義n維格Λ上以c為中心，σ為參數(shù)的離散高斯函數(shù)為：

其中，高斯函數(shù)滿足ρσ,c(Λ)=∑x∈Λ ρσ,c(x)。當(dāng)中心向量c=0 時，可將離散高斯函數(shù)和高斯函數(shù)簡寫為DΛ,σ(x)和ρσ(x)。

定義4[19]（Dm×m分布）已知q為素數(shù)，正整數(shù)m≥6nlbq，參數(shù)σ≥。Dm×m表示可逆矩陣Ai=[ai1||ai2||…||aim]在空間上的分布。其中aij～DZm,σ，j∈[m]。

引理1[20]（GPV08 格基陷門生成算法）存在一個概率多項式時間算法TrapGen(1n)以素數(shù)q≥3 和正整數(shù)m≥為輸入，能夠輸出和格Λ⊥(A)的一組短基T，滿足A的分布與上的均勻分布統(tǒng)計不可區(qū)分，且||T||≤O(nlbq)，此處，表示對T進行Gram-Schmidt正交化后的基。

引理2[18]（格上常見的采樣算法）已知正整數(shù)q≥2，m>n，矩陣，格Λ⊥(A)的一組基T，高斯參數(shù)σ≥，以及任意的向量c∈Rm，

（1）存在一個概率多項式時間算法SampleD(A,T,σ,c)能夠輸出一個分布統(tǒng)計接近于的向量v。

（2）存在一個概率多項式時間算法SamplePre(A,T,σ,u)能夠輸出一個分布統(tǒng)計接近于的向量v。

引理3[19]（格基委派算法）輸入滿秩矩陣A∈，矩陣R～Dm×m，格Λ⊥(A)的一組基T，高斯參數(shù)滿足σ>，則存在一個概率多項式時間算法BasisDel(A,R,T,σ) 能夠輸出Λ⊥(AR-1)的一組基T′，滿足。其中高斯參數(shù)滿足σR=，Dm×m表示Zm×m中滿足且模q可逆的矩陣的分布。若R是從Dm×m中抽取的l個矩陣的乘積，則參數(shù)滿足σ>

引理4[21]輸入滿秩矩陣，則存在一個概率多項式時間算法SampleRwithBasis(A)能夠輸出一個矩陣R～Dm×m以及格Λ⊥(AR-1)的一組基T′，滿足

定義5[18]（格上的小整數(shù)解問題，SISq,m,β）給定隨機矩陣和實數(shù)β>0，格上所謂的小整數(shù)解（small integer solution，SIS）問題即求出一個向量v∈Zm滿足Av=0 modq且0<||v||≤β。

引理5[22]（小整數(shù)解問題的困難性規(guī)約）已知任意多項式有界的實數(shù)m,β=poly(n) 和素數(shù)q≥β?，求解平均實例的SISq,m,β問題的困難性和求解格上最壞實例下的近似最短獨立向量問題（shortest independent vectors problem，SIVPγ）的困難性相當(dāng)，其中，

2 前向安全的有序聚合簽名

2.1 定義

本章將前向安全有序聚合簽名的定義以及安全性證明描述如下。

定義6（前向安全有序聚合簽名方案）一個完整的前向安全有序聚合簽名方案由6個多項式時間算法構(gòu)成，分別是系統(tǒng)建立算法Setup、簽名密鑰生成算法FssAgg-Keygen、簽名私鑰提取算法FssAgg-Extract、簽名密鑰更新算法FssAgg-KeyUpdate、聚合簽名算法FssAgg-Sign 和簽名驗證算法FssAgg-Verify。

Setup：以系統(tǒng)安全參數(shù)n為輸入，KGC 生成并輸出系統(tǒng)公共參數(shù)PP。

FssAgg-Keygen：輸入PP，KGC 運行該算法輸出主公/私鑰對(msk,mpk)。

FssAgg-Extract：以用戶U的身份id為輸入，該算法生成用戶U的密鑰skid|0。

FssAgg-KeyUpdate：以前一時間段的私鑰skid|i-1以及當(dāng)前時間段i為輸入，算法計算并輸出當(dāng)前時段i的簽名私鑰skid|i。

FssAgg-Sign：輸入待簽名消息mi和之前的聚合簽名sigi-1，算法使用skid|i計算輸出時段i的聚合簽名sigi。

FssAgg-Verify：輸入聚合簽名sigi以及消息集合mj(j≤i)，當(dāng)且僅當(dāng)聚合簽名sigi為消息集合mj(j≤i)的合法簽名時，算法輸出為“1”，否則輸出“0”。

2.2 安全性模型

一般情況下，認為前向安全有序聚合簽名應(yīng)滿足如下兩個條件：正確性和前向不可偽造性。

定義7（正確性）以上前向安全有序聚合簽名方案中，簽名方案滿足正確性是指FssAgg-Verify 能以近似1 的概率輸出“1”。

定義8[23]（前向安全的存在性不可偽造）若不存在多項式時間的敵手A能以不可忽略的概率贏得以下游戲，則稱該Fss-Agg 簽名方案在前向安全的聚合攻擊模型下是存在性不可偽造的。

Setup：輸入安全參數(shù)n，敵手得到系統(tǒng)公共參數(shù)PP。

Queries：敵手A可以做多項式次的如下詢問。

（1）FssAgg-Extract Queries：輸入用戶U的身份id，挑戰(zhàn)者C 返還其密鑰skid|0。

（2）Break in Queries：當(dāng)敵手A對時段j做Break in Queries 詢問時，挑戰(zhàn)者C 返回此時段簽名私鑰skid|j給敵手。

（3）FssAgg-Sign Queries：以當(dāng)前時段i，待簽名消息mi，私鑰skid|i，以及之前的簽名sigi-1為輸入，挑戰(zhàn)者C 返還當(dāng)前時段i的聚合簽名sigi給敵手A。

Forgery：結(jié)束以上詢問之后，敵手A輸出對于消息m1,m2,…,mk的聚合簽名sigk。稱敵手A贏得以上游戲，當(dāng)且僅當(dāng)如下條件滿足：（1）簽名sigk滿足正確性；（2）簽名sigk是不平凡的，也就是說，至少存在一個時間段i*∈[k]未對消息m1,m2,…,mi*做聚合簽名詢問；（3）1 ≤i*

3 標(biāo)準模型下前向安全的格基有序聚合簽名

本章基于格上的困難性問題，構(gòu)造標(biāo)準模型下的前向安全格基有序聚合簽名方案。相較于格上傳統(tǒng)的簽名方案，為達到高效的前向安全性，方案借助于固定維數(shù)格基委派技術(shù)實現(xiàn)密鑰更新；隨后通過消息添加技術(shù)和原像采樣算法分別將待簽消息和格上困難問題嵌入到簽名中，使得簽名在標(biāo)準模型下是不可偽造的。

3.1 方案構(gòu)造

令n為安全參數(shù)，素數(shù)q≥β?ω(lbn)，β=poly(n)，m≥6nlbq，那么格上的前向安全有序聚合簽名方案描述如下。

Setup：輸入系統(tǒng)的安全參數(shù)n，KGC 生成系統(tǒng)公共參數(shù)PP如下。k為預(yù)先指定的時間段數(shù)以及高斯參數(shù)(σ0,σ1,…,σk)，高斯參數(shù)(σ′1,σ′2,…,σ′k)，其中σi≥Lmi?ω(lbi+1m)，σ′i≥σi?t1，t2，l為正整數(shù)。2(k+1)t1個隨機矩陣Dm×m(i∈{0,1,…,k},j∈[t1])，t2個隨機矩陣滿足Ci←(i∈[t2])。三個哈希函數(shù)分別為H:{0,1}*→H′:{0,1}*→，H1:{0,1}*→和以及陷門函數(shù)fA:和文獻[24]中的加密函數(shù)enc:{0,1}*→{0,1}*×以及解密函數(shù)dec:{0,1}*×{0,1}*。

FssAgg-KeyGen：輸入公共參數(shù)PP，KGC 運行引理1 中陷門生成算法TrapGen(1n)生成格Λ⊥(A)，及其陷門基T∈Zm×m，滿足，||T||≤L。最后，KGC將矩陣A和T分別保存為主公鑰和主私鑰。

FssAgg-Extract：為了獲得用戶U（身份為id）的密鑰，KGC 首先計算哈希值H(id|0)=ρ0=ρid|0，R0=。隨后運行引理3 中格基委派算法BasisDel(A,R0,T,σ0) 輸出 矩陣Tid|0=[t1||t2||…||tm]作為密鑰skid|0。最后，KGC 將Tid|0發(fā)送給用戶U。

FssAgg-KeyUpdate：輸入密鑰Tid|i-1和當(dāng)前時段i，KGC 首先計算Ri=，Rid|i-1=Ri-1Ri-2…R0以及矩陣Aid|i-1=。隨后，KGC 運行格基委派算法BasisDel(Aid|i-1,Ri,Tid|i-1,σi)生成當(dāng)前時段簽名私鑰Tid|i。

FssAgg-Sign：輸入當(dāng)前消息mi以及當(dāng)前時段i，簽名算法工作如下：

（1）如果i=1，則

（2）Σ0←(e,e,e,e,0n)，結(jié)束。其中e表示空串或者空向量。如果i=2,3,…,k，則執(zhí)行如下。

（3）把Σi-1拆分成，其中，為格基陷門函數(shù)集合，滿足，sigi-1為前一時段聚合簽名，αi-1為sigi-1的加密簽名，為加密簽名的集合，即hi-1是長度為常數(shù)l的哈希值。

（4）如果FssAgg-Verify(Σi-1)==(⊥,⊥)，則結(jié)束。

（5）計算(αi,βi)←

（7）計算hi=

（8）計算gi←

（9）選擇一個隨機字符串ri∈{0,1}n，計算向量vi=H′(mi,id|i|ri)以及嵌入了消息的矩陣

（11）輸出Σi←

FssAgg-Verify：輸入Σk，驗證算法運行如下：

（1）將Σk拆分成

（2）對于i=k→1，執(zhí)行：

（3）如果||sigi||≥

（4）則返回(⊥,⊥)，結(jié)束。

（5）否則，計算gi←

（6）將簽名sigi拆分成sigi=（其中，向量ui1,ui2滿足ui1,ui2∈Zm），計算隨機向量vi=H′(mi,id|i|ri)，嵌入消息的矩陣以及βi=(C||Aid|i)(sigi)-gi(ui2)-gi+Cui1。

（7）計算sigi-1←(αi,βi)。

（8）計算hi-1=

（9）如果Σ0←(e,e,e,e,0n)，則

（11）否則，返回(⊥,⊥)。

3.2 正確性

定理1如上構(gòu)造的前向安全有序聚合簽名方案滿足正確性。

證明由FssAgg-KeyUpdate 階段可知，Tid|i對應(yīng)的格的隨機矩陣為：

又因為ui2由FssAgg-Sign 階段（9）中原像采樣算法SamplePre(Aid|i,Tid|i,si,(gi+βi-Cui1))采樣而得，所以有Aid|iui2=gi+βi-Cui1，且成立；又因為，所以

因而，不難求得||sigi||≤，且gi+Cui1成立。因此簽名驗證階段可順利通過，即，簽名滿足正確性。

3.3 安全性證明

定理2如果格上的SIS 問題在多項式時間算法攻擊下是困難的，則以上構(gòu)造的格基前向安全的有序聚合簽名在標(biāo)準模型下是前向安全的且存在性不可偽造的。

證明假定存在一個多項式時間的敵手A，在多項式次的詢問之后能夠以概率ε輸出一個偽造有序聚合簽名，則可以構(gòu)造一個模擬器C 能夠以近似ε的概率求解格上的SIS 問題。選定身份為id*。

調(diào)用：算法C 調(diào)用格上的SIS 問題。

返 回：向 量v∈Zm，滿 足A0v=0 modq且0 ≠|(zhì)|v||≤β。

Setup：挑戰(zhàn)者C 隨機選擇一個矩陣A0∈隨后，挑戰(zhàn)者C 選擇t2個隨機矩陣E1,E2,…其中所有矩陣Ei的每一列都隨機獨立地按照分布選取。對所有的i∈[t2]，計算Ci=A0Ei。挑戰(zhàn)者C隨后選擇(k+1)t1個隨機矩陣Ri,j∈Dm×m（其中i∈{0,1,…,k},j∈[t1]）。對于所有的j∈[t1]，其余的公共參數(shù)參照如下方式選擇。

（1）對所有的i∈{0,1,…,k}，令

（4）對所有的i∈{0,1,…,k}，計算，并且定義A0,1=A1,2=…A1,1=A。

（5）運行引理4 中SampleRwithBasis(Ai,j)，生成一個矩陣R～Dm×m以及格Λ⊥(Ai,jR-1)的一小范數(shù)基T。

（6）存儲項{i,j,R,Ai,jR-1,T}至列表l1，令

Queries：首先，挑戰(zhàn)者隨機選中i*(1 ≤i*≤k)作為敵手A偽造簽名的時段。

（1）FssAgg-Extract Queries：挑戰(zhàn)者C 維持一個列表l2={id,0,Tid|0} 。敵手A適應(yīng)性地選中l(wèi)∈{1,2,…,Q}，其中Q表示敵手能做密鑰提取詢問次數(shù)的最大值，挑戰(zhàn)者C 按如下方式做詢問應(yīng)答。

如果id并非第l次密鑰提取詢問，挑戰(zhàn)者C 執(zhí)行如下：

①輸入身份(id,0)，挑戰(zhàn)者C 定義ρ0=H(id|0)，然后計算R0=

②令j是滿足的第一個位置，其中，j∈[t1]。

③挑戰(zhàn)者C 在列表l1中找到對應(yīng)項(0,j,R,AR-1,T) 。隨后運行格基委派算法BasisDel(AR-1,T,σ0)求得Tid|0。

最后，挑戰(zhàn)者C 將(id,0,Tid|0)存儲至列表l2中，并將Tid|0返還給敵手A。

如果id剛好是第l次密鑰提取詢問，則終止。

（2）FssAgg-KeyUpdate Queries：挑戰(zhàn)者C 維持一個列表l3={id,i,Aid|i,Tid|i}。輸入當(dāng)前時段i，挑戰(zhàn)者C按如下方式做密鑰更新詢問應(yīng)答。

如果id并非第l次密鑰更新詢問，挑戰(zhàn)者C 執(zhí)行如下：

①輸入身份(id,i)，挑戰(zhàn)者C 定義ρi=H(id|i)，然后計算Ri=

②令j是滿足的第一個位置，其中，j∈[t1]。

③挑戰(zhàn)者C 在列表l1中找到對應(yīng)項(i,j,R,Ai,jR-1,T)。隨后運行格基委派算法求得Tid|i。

最后，挑戰(zhàn)者C 將(id,i,Aid|i,Tid|i) 存儲至列表l2中，并將Tid|i返還給敵手A。

如果id剛好是第l次密鑰更新詢問，挑戰(zhàn)者C按如下方式做密鑰更新詢問應(yīng)答。

①如果i≤i*，挑戰(zhàn)者C 隨機選擇并將其返還給敵手A。

②如果i=i*+1，挑戰(zhàn)者C 運行陷門生成算法TrapGen(1n)生成格，及其陷門基，滿足，≤L。最后，挑戰(zhàn)者C 存儲至列表l3中，并將返還給敵手A。

③如果i*+1

（3）FssAgg-Sign Queries：挑戰(zhàn)者C 維持一個列表l4=(id,i,mi,sigi,Aid|isigi)。輸入i，sigi-1，mi和身份id，挑戰(zhàn)者C 首先計算(αi,βi)←，然后按如下方式做詢問應(yīng)答。

如果id并非第l次詢問，挑戰(zhàn)者C 首先在列表l5中查找(id,i,mi,sigi,Aid|isigi,gi)。若能找到，則返回相應(yīng)的gi給敵手A。否則，挑戰(zhàn)者首先在l3中查找(id,i,Aid|i,Tid|i)，然后隨機選擇字符串ri∈{0,1}n，令v=H′(mi,id|i|ri)，計算gi←，選擇一個隨機向量，計算vi2←SamplePre(Aid|i,Tid|i,σ′i,(gi+βi-Cvi1))。

令簽名sigi=，并在列表l4中存儲(id,i,mi,sigi,Aid|isigi)。最后，挑戰(zhàn)者C 返回相應(yīng)的sigi給敵手A。

如果id剛好是第l次詢問，挑戰(zhàn)者執(zhí)行如下：

①如果i*≤i≤k，挑戰(zhàn)者C 首先在列表l5中查找(id,i,mi,sigi,Aid|isigi,gi)。若能找到，則返回相應(yīng)的gi給敵手A。否則，挑戰(zhàn)者首先在l3中查找(id,i,Aid|i,Tid|i)，然后隨機選擇一個字符串ri∈{0,1}n，令v=H′(mi,id|i|ri)，并計算A0Ev，選擇一個隨機向量，并計算vi2=(A0)-1(αi+βi)-Evvi1(modq)，如果Evvi1=0，則重復(fù)以上步驟，直至Evvi1≠0 。令簽名sigi=，并在列表l4中存儲(id,i,mi,sigi,Aid|isigi)。最后，挑戰(zhàn)者C返回相應(yīng)的sigi給敵手A。

②如果i*≤i≤k不成立，則終止。

（4）Breakin in Queries：當(dāng)敵手A對特殊的(id,j)做密鑰更新詢問時，如果id并非第l次詢問，挑戰(zhàn)者C 在列表l3中查找Tid|j并將其返還給敵手A；如果id剛好為第l次詢問，并且j=i*，則終止。

Forgery：在此階段，敵手A以不可忽略的概率輸出一個偽造簽名。其中，簽名驗證過程中Σ′i包含id*、。隨后，令u*=，C=A0Eu*。其中，矩陣A0滿足稱敵手A偽造成功，當(dāng)且僅當(dāng)以下條件滿足：

（1）1 ≤t*

（2）id*未被發(fā)送做FssAgg-KeyUpdate Queries詢問；

（4）偽造簽名的驗證輸出為“1”。

當(dāng)敵手A成功輸出偽造簽名sigk)后，挑戰(zhàn)者C 可按如下方式求解格上SIS 問題。首先，挑戰(zhàn)者檢查id*是否為第l次詢問，且t*=i*是否成立。若以上條件有一條不成立，挑戰(zhàn)者終止操作。否則，挑戰(zhàn)者就完成了完美模擬。由于(id*,t*,從未在簽名詢問階段出現(xiàn)過，則知道u*是一個新向量滿足，令向量滿足，由原像最小熵性質(zhì)可知向量v滿足Pr[v=0]≤negl(n)。由于不等式C 可以輸出v為調(diào)用階段SIS 問題的解。

如上所說，如果id*并非第l次詢問或t*≠i*，C終止操作，且Pr[v=0]≤negl(n)。因此，C 能夠解決SIS 問題的概率與A能輸出偽造簽名概率為ε/kQnegl(n)。由引理5 可知，多項式時間內(nèi)解決格上SIS問題的概率幾乎可忽略，因此敵手A輸出偽造簽名的概率也必然為可忽略的，即簽名滿足不可偽造性。成立，令實數(shù)

3.4 效率分析

目前，格上現(xiàn)存的有序聚合簽名有方案[14-17]，且均為隨機預(yù)言機模型下的簽名方案。本節(jié)從公鑰尺寸、私鑰尺寸和簽名尺寸三方面來比較格上的有序聚合簽名方案與之前簽名方案的效率，詳見表1。其中，參數(shù)滿足5nlbq，k表示3.1 節(jié)方案中預(yù)先指定的時間段數(shù)，i表示當(dāng)前分級所處階段且i=1,2,…,k。

由表1 容易看出，在文獻[14-17]中方案的公鑰、簽名私鑰、簽名尺寸均相當(dāng)。而本文提出的前向安全聚合簽名方案由于要實現(xiàn)前向安全性，故而采用了格基委派技術(shù)，因而，相較于文獻[14-17]，私鑰及簽名長度會隨著分級（即i）增大而增加?？梢岳斫鉃?，新方案以犧牲略大的簽名私鑰尺寸和簽名尺寸為代價換取了更高的安全性保證，從而適應(yīng)更加嚴苛的安全環(huán)境。簽名方案的具體實現(xiàn)可由C++語言在FLINT 庫的幫助下簡單完成。

Table 1 Efficiency comparison of different schemes on lattice表1 格上不同方案的效率比較

4 結(jié)束語

由于兼具前向安全性和較小存儲空間等諸多優(yōu)勢，前向安全的有序聚合簽名方案一經(jīng)提出便被廣泛應(yīng)用于日志系統(tǒng)中。然而，隨著量子計算機逐漸商用，現(xiàn)存的前向安全的有序聚合簽名方案已不再能滿足安全性需求。因而，尋找量子免疫的前向安全有序聚合簽名方案已勢在必行。由美國國家標(biāo)準與技術(shù)研究所公布的三輪后量子密碼備選方案不難發(fā)現(xiàn)，格公鑰密碼占據(jù)了舉足輕重的位置，因而相較于基于哈希的公鑰密碼體制、基于編碼的公鑰密碼體制以及多變量公鑰密碼體制而言，格公鑰密碼無疑是后量子時代密碼標(biāo)準的最佳選擇。本文基于格基困難問題——SIS 問題提出了標(biāo)準模型下量子安全的前向安全有序聚合簽名方案。方案借助于固定維數(shù)格基委派技術(shù)實現(xiàn)密鑰更新，達到前向安全性；隨后通過消息添加技術(shù)和原像采樣算法分別將待簽消息和格上困難問題嵌入到簽名中，使得簽名在標(biāo)準模型下是不可偽造的。為了進一步壓縮區(qū)塊鏈中區(qū)塊大小，在后續(xù)的工作中，將構(gòu)造指定驗證者有序聚合簽名作為工作重心。