謝 佳，胡予濮，高軍濤，王保倉(cāng)，江明明

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

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

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

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

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

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

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

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

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

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

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

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

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

其中，參數(shù)分別為素?cái)?shù)q，正整數(shù)n和m，矩陣A∈，以及向量，且常將和分別簡(jiǎn)寫(xiě)為Λ⊥(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ù)滿(mǎn)足ρσ,c(Λ)=∑x∈Λ ρσ,c(x)。當(dāng)中心向量c=0 時(shí)，可將離散高斯函數(shù)和高斯函數(shù)簡(jiǎn)寫(xiě)為DΛ,σ(x)和ρσ(x)。

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

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

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

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

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

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

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

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

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

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

2.1 定義

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

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

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

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

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

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

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

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

2.2 安全性模型

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

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

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

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

Queries：敵手A可以做多項(xiàng)式次的如下詢(xún)問(wèn)。

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

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

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

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

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

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

3.1 方案構(gòu)造

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

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

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

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

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

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

（1）如果i=1，則

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

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

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

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

（7）計(jì)算hi=

（8）計(jì)算gi←

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

（11）輸出Σi←

FssAgg-Verify：輸入Σk，驗(yàn)證算法運(yùn)行如下：

（1）將Σk拆分成

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

（3）如果||sigi||≥

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

（5）否則，計(jì)算gi←

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

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

（8）計(jì)算hi-1=

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

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

3.2 正確性

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

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

又因?yàn)閡i2由FssAgg-Sign 階段（9）中原像采樣算法SamplePre(Aid|i,Tid|i,si,(gi+βi-Cui1))采樣而得，所以有Aid|iui2=gi+βi-Cui1，且成立；又因?yàn)椋?/p>

因而，不難求得||sigi||≤，且gi+Cui1成立。因此簽名驗(yàn)證階段可順利通過(guò)，即，簽名滿(mǎn)足正確性。

3.3 安全性證明

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

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

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

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

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

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

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

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

（6）存儲(chǔ)項(xiàng){i,j,R,Ai,jR-1,T}至列表l1，令

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

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

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

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

②令j是滿(mǎn)足的第一個(gè)位置，其中，j∈[t1]。

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

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

如果id剛好是第l次密鑰提取詢(xún)問(wèn)，則終止。

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

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

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

②令j是滿(mǎn)足的第一個(gè)位置，其中，j∈[t1]。

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

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

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

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

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

③如果i*+1

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

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

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

如果id剛好是第l次詢(xún)問(wèn)，挑戰(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)，然后隨機(jī)選擇一個(gè)字符串ri∈{0,1}n，令v=H′(mi,id|i|ri)，并計(jì)算A0Ev，選擇一個(gè)隨機(jī)向量，并計(jì)算vi2=(A0)-1(αi+βi)-Evvi1(modq)，如果Evvi1=0，則重復(fù)以上步驟，直至Evvi1≠0 。令簽名sigi=，并在列表l4中存儲(chǔ)(id,i,mi,sigi,Aid|isigi)。最后，挑戰(zhàn)者C返回相應(yīng)的sigi給敵手A。

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

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

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

（1）1 ≤t*

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

（4）偽造簽名的驗(yàn)證輸出為“1”。

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

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

3.4 效率分析

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

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

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

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

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