葉 青，楊曉孟，秦攀科，趙宗渠，湯永利

河南理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，河南 焦作454000

1 引言

1991 年，Chaum 和Heyst[1]提出了群簽名的概念，并構(gòu)建了第一個群簽名方案。在群簽名中，有多個成員，其中每個成員都可以代表群體進行簽名，驗證者可以通過系統(tǒng)公鑰驗證簽名是否合法，但無法確定具體是哪個用戶執(zhí)行了簽名，發(fā)生爭議時可由群管理員通過追蹤密鑰找到簽名者的身份。隨后文獻[2-3]對文獻[1]進行了改進，使方案效率提升且更具有實用性。但以上群簽名方案的共同特點是基于傳統(tǒng)的數(shù)論難題（例如：大整數(shù)分解問題、離散對數(shù)問題和橢圓曲線問題）構(gòu)建，而在量子計算機得到應(yīng)用的前提下，傳統(tǒng)基于數(shù)論難題構(gòu)建的群簽名方案都將在多項式時間內(nèi)被破解，因而，研究抗量子攻擊的群簽名方案成為該領(lǐng)域亟待解決的問題。近幾年，基于格理論構(gòu)造的簽名方案[4-5]和加密方案[6-7]因具有運算效率高、計算可并行化、抗量子攻擊和存在最壞情況下的隨機實例等優(yōu)點，成為后量子密碼時代的研究熱點。

2010年，Gordon等[8]在ASIACRYPT'10提出了第一個基于格的群簽名方案（簡稱GKV2010 方案），該方案首先用Gentry等[9]中的格上簽名方案對消息進行簽名得到簽名e，然后基于Regev[10]的格上加密方案使用系統(tǒng)公鑰對簽名e 進行加密得到密文c，最后構(gòu)造了一個非交互式證據(jù)不可區(qū)分（Non-Interactive Witness Indistinguishable，NIWI）的證明，證明密文c 是通過系統(tǒng)公鑰對簽名e 進行加密得到的，該方案簽名長度為O(N)（其中N 為群成員的個數(shù)）。2013年，Laguillaumie等[11]在ASIACRYPT'13 提出了第一個簽名大小為O(lb N)的格上群簽名方案。2015年，Nguyen等[12]在PKC'15提出了更加簡單高效且簽名長度同樣為O(lb N)的格上群簽名方案。Kawachi 等[13]在ASIACRYPT'08 上首次將零知識證明與格上SVP 困難問題相結(jié)合提出了格上并發(fā)安全的認證方案。在零知識證明系統(tǒng)中，證明者可以在不向驗證者提供任何有用信息的情況下，而使驗證者相信某個論斷是正確的，零知識證明的這種特性使得它在構(gòu)造密碼方案的匿名性方面可以發(fā)揮重要作用。隨后，Ling 等[14]在PKC'13 上基于SIS 難題和LWE 難題使零知識證明能夠處理矩陣-向量關(guān)系，于是零知識證明進一步被用于構(gòu)造格上密碼方案[15-17]。

近幾年，基于格的群簽名方案成果很多[15-19]，但是都有通信代價高、系統(tǒng)公鑰尺寸過大的弱點，而NRTU格是一類基于多項式環(huán)的特殊格，因在其計算過程中只涉及到多項式環(huán)上的乘法和小整數(shù)求模運算，與一般格相比較，NTRU 格密碼體制所需的公私鑰長度更短，運算速度更快。本文依據(jù)GKV2010群簽名方案“簽名-加密-NIWI 證明”的構(gòu)造思路，采用Ducas 等[20]在ASIACRYPT'14 提出的NTRU 格上高效參數(shù)生成的算法（簡稱DLP算法），構(gòu)造了一個基于NTRU格的群簽名方案。在本文方案中，首先采用DLP算法產(chǎn)生NTRU格上群簽名的系統(tǒng)公鑰、追蹤密鑰和用戶簽名密鑰，然后用Hoffstein等[21]提出的NTRUSign簽名算法對消息進行簽名得到簽名e，再用文獻[22]提出的NTRUEncrypt 加密算法使用系統(tǒng)公鑰對簽名e 進行加密得到密文c，最后基于NIWI 證明[8]來證明密文c 是系統(tǒng)公鑰對簽名e 進行加密得到的。在GKV2010 方案的安全模型下，基于LWE困難問題證明本文的NTRU 格上群簽名方案滿足匿名性，基于近似CVP 困難問題證明所提群簽名方案滿足可追蹤性。

2 符號介紹

表1對下文中出現(xiàn)的符號進行說明。

表1 符號介紹

除了表1 中的符號，文中還用到O ，O~ 等符號，為常用計算復(fù)雜度符號。

3 預(yù)備知識

3.1 NTRU格的相關(guān)定義

定義1（格）設(shè)b1,b2,…,bm是n 維歐式空間?n上m 個線性無關(guān)向量，格定義為所有這些向量的整系數(shù)線性組合，即，其中，向量組b1,b2,…,bm稱為格Λ 的一組基。

定義2（q 元格）設(shè)q,n,m ∈?,A ∈,且u ∈滿足Ax=u mod q。定義：

定義3（NTRU 格）令n,q ∈?+，多項式f、g、F、G ∈R 滿足f*G-g*F=q，由f、g、F、G 生成的NTRU格是指以矩陣的行向量作為格基生成的格，其中，A(x)表示多項式x 所對應(yīng)的卷積多項式。

定義4（離散高斯分布）對任意σ ＞0，定義以向量c為中心，σ 為參數(shù)的格Λ 上離散高斯分布為：

其中有x ∈Λ,ρσ,c(x)=e

3.2 困難問題假設(shè)

定義5（最近向量問題（Closest Vector Problem，CVP））求出格中與某一個給定向量距離最短的向量，即任意給出一個點p，格L 中與點p 距離最近的向量稱之為最近向量。格L 與點p 的距離記為λ1(p,L)，同樣地，格L中與點p 距離次近的向量與p 的距離記為λ2(p,L)，以此類推，那么有：

可以證明，在p 范數(shù)(p ≥1)的形式下，CVP 是NP難題。

近似最近向量問題（Approximate Closest Vector Problem，Appr-CVP）：某個算法對于輸入的格L 和任意的目標向量p 可以找到格L 中距離p 不超過cλ1(p,L)的非零格向量v(v ∈L)（c 為近似因子，是格中某個量的函數(shù)），可稱該算法以因子c 近似解決CVP。已經(jīng)證明：具有小因子c 的近似最近向量問題（Appr-CVP）是NP難題。

定義6（判定性容錯學(xué)習(xí)（Decisional Learning With Errors，DLWE）問題）給定正整數(shù)n，整數(shù)m ≥n 和q ≥2及向量s，一個?m上的概率分布χ 。定義兩種在×[0,q)m上的分布：

（1）LWEm,q,χ(s)：選取中均勻分布的矩陣A，進行抽樣得到e ←χ，然后輸出(A,ATs+e)。

（2）Um,q：選取中均勻分布的矩陣A 與[0,q)m中均勻分布的向量y，然后輸出(A,y)。

判定性LWE 問題即為：區(qū)分LWEm,q,χ(s)和Um,q。假設(shè)存在概率多項式時間算法時間D，可以得出Pr[s ←；(A,y)←LWEm,q,χ(s):D(A,y)=1]=1-Pr[(A,y)←Um,q:D(A,y)=1]是可忽略的，那么DLWEm,q,χ(s)是困難的。

本文方案基于DLWE難題，由于分布χ 取自離散高斯分布D?m,αq,所以判定性LWE問題表示為DLWEm,q,α。

3.3 非交互證據(jù)不可區(qū)分（Non-Interactive Witness Indistinguishable，NIWI）證明

文獻[8]給出了非交互證據(jù)不可區(qū)分的證明系統(tǒng)，定義如下。

首先定義判定語言Ls,γ：

以下為兩種等價情況：

引理1[8]當時，在隨機預(yù)言模型下，對于Ls,γ，存在一個對的非交互式不可區(qū)分的證明系統(tǒng)，該系統(tǒng)長度為O(mnN lb q)bit。

4 NTRU格上相關(guān)算法的介紹

4.1 NTRUEncrypt算法

密鑰選取。首先定義p,q 為整數(shù)，滿足gcd(p,q)=1,其中q ＞p。在多項式環(huán)R=?[x]/(xn-1)中，隨機選取兩個多項式f,g，次數(shù)均為N-1，系數(shù)為整數(shù)。多項式f 滿足模p 和模q 都有逆，分別記為fp,fq，即：

fp*f=1(mod p),fq*f=1(mod q)

計算h=pfq*g(mod q) ，上述式子中的mod p 和mod q 是指多項式的系數(shù)分別是區(qū)間中的整數(shù)。那么有公鑰pk=h，私鑰sk=(f,fp)。

加密。消息m 為多項式，次數(shù)為N-1，系數(shù)為整數(shù)。隨機選取一個多項式r ，次數(shù)也為N-1，系數(shù)為整數(shù)。計算：c=r*h+m(mod q)。

解密。首先計算a=f*c(mod q)，其中a 的系數(shù)屬于集合。然后計算m=Fq*a(mod q)。

4.2 NTRUSign算法

密鑰選取。首先定義β 為平衡因子，其范圍為0 ＜β ≤1，NormBound 為驗證簽名是否合法的臨界值。在多項式環(huán)R=Z[x]/(xn-1)中，隨機選擇兩個小多項式f,g，滿足模q 有逆。計算多項式(F,G)滿足：

在Rq上對f 進行求逆運算生成fq，在Rq上對g進行求逆運算生成gq，那么公鑰為h=F*fq(mod q)，私鑰為(f,g)。

簽名。對消息B 使用hash 變換：H(B)，得到消息摘要m ∈[0,q)N。進行如下計算：

其中{ }x 表示{ }x =x-round(x)。

輸出簽名：s=?fj+?′gj。

驗證。對消息B 使用hash 變換：H(B)，得到消息摘要m ∈[0,q)N。首先計算t=s*h mod q，然后計算規(guī)范數(shù)：

如果有v ＜Normbound ，則表示驗證成功，否則，表示驗證失敗。

5 群簽名及安全模型

一個群簽名方案[1，8，11-12，15-18]G 一般包括以下四個基本算法：

（1）密鑰生成算法（G.KeyGen）：輸入安全參數(shù)λ，輸出群公鑰PK ，用戶私鑰gsk 和追蹤密鑰TK 。

（2）簽名生成算法（G.Sign）：輸入消息M 和用戶私鑰gsk，輸出對消息的簽名σ。

（3）簽名驗證算法（G.Verify）：輸入消息M ，對消息的簽名σ 和群公鑰PK，驗證成功輸出1，驗證失敗輸出0。

（4）簽名打開算法（G.Open）：輸入對消息的簽名σ，消息M 和追蹤密鑰TK ，輸出簽名者身份i。

Gordon 等[8]在ASIACRYPT'10 提出了第一個格上群簽名并給出了具體的安全模型，即群簽名應(yīng)滿足正確性，匿名性和可追蹤性。2015年，Nguyen等[16]在該安全模型下證明了PKC'15 上提出的簽名長度為O(lb n)的格上群簽名方案的安全性，Libert 等[17]同樣在該安全模型下證明了EUROCRYPT'16提出的不需要陷門的格上群簽名方案的安全性，因此，本文方案也采用該安全模型[8]，定義如下：

定義7（正確性）一個合法的簽名，必然能通過簽名驗證算法的檢驗并且群管理員可推導(dǎo)出該簽名對應(yīng)的用戶身份。即：對于G.KeyGen 生成的(PK,TK,gsk)，任意消息M 和任意用戶i，如果簽名為σ ←G.Sign(gsk[i],M)，那么必然可以得到：

G.Verify(PK,M,σ)=1；G.Open(TK,M,σ)=i

定義8（匿名性）匿名性是指，在沒有追蹤密鑰的情況下，即使給出所有用戶的簽名密鑰，也推斷不出具體是哪個群成員對消息進行了簽名。即：一個群簽名方案G具有匿名性，那么對于任意概率多項式時間敵手在下列游戲中獲勝的優(yōu)勢是可忽略的：

（1）挑戰(zhàn)者運行G.KeyGen ，并將公鑰PK 發(fā)送給敵手A。

（2）敵手A輸出兩個ID:i0,i1∈[N]以及消息M 。挑戰(zhàn)者隨機選擇比特b，并將群簽名G.Sign(gsk[ib],M)發(fā)送給敵手A。

（3）敵手A經(jīng)過一系列的詢問后輸出b′。

定義9（可追蹤性）可追蹤性是指群管理員可以通過追蹤密鑰找到正確簽名者的身份。即：一個群簽名方案G具有可追蹤性，那么對于任意概率多項式時間敵手在下列游戲中獲勝的優(yōu)勢是可忽略的：

（1）挑戰(zhàn)者運行G.KeyGen ，并將公鑰PK 和TK發(fā)送給敵手A。

（2）敵手A可適應(yīng)性地進行如下的預(yù)言機詢問：

①敵手A可詢問私鑰預(yù)言機，對于輸入i，輸出SKi。

②敵手A可詢問私鑰預(yù)言機，對于輸入i,M ，輸出G.Sign(SKi,M)。

（3）經(jīng)過一系列詢問后，A 輸出一個消息M 和簽名σ ，設(shè)C 為A對私鑰預(yù)言機進行過詢問的i 的集合。如果以下三個條件均成立，則稱A獲勝。

①G.Verify(PK,M,σ)=1；

②對于i ?C,A 未進行G.Sign(i,M)的詢問；

③G.Open(TK,M,σ)?C 均成立。

6 本文的方案

本文方案依據(jù)GKV2010 方案“簽名-加密-NIWI 證明”的構(gòu)造思路，但與GKV2010 方案的不同之處在于，密鑰生成算法采用DLP算法[20]產(chǎn)生系統(tǒng)公鑰、追蹤密鑰以及用戶簽名密鑰；簽名生成算法，首先采用NTRUSign 算法[21]對消息進行簽名得到簽名e ，然后基于NTRUEncrypt 算法[22]用系統(tǒng)公鑰對簽名e 進行加密得到密文c，最后基于一個NIWI 證明[8]，證明密文c 是系統(tǒng)公鑰對簽名e 進行加密得到的；簽名驗證算法基于NTRUSign算法的簽名驗證算法。方案具體構(gòu)造如下。

6.1 密鑰生成算法

設(shè)λ 為安全參數(shù)，N 為群簽名中用戶個數(shù)（其中N=2l），令大模數(shù)q=poly(λ)，小模數(shù)p=negl(λ)，維數(shù)為n 。對于一個f ∈R′ ，定義為R′ 中滿足條件的特殊多項式，如果那么有

密鑰生成算法具體如下：

（2）根據(jù)歐幾里德算法，計算rf、rg∈R,Rf、Rg∈?,并且滿足rff=Rfmod(xn+1) 和rgg=Rgmod(xn+1)（如果GCD(Rf,Rg)≠1或GCD(Rf,q)≠1則返回上一步）。

（3）計算tf、tg∈?，使tfRf+tgRg=1。然后計算：

再根據(jù)計算得到的F′,G′,k 計算：F=F′′-K*f ，G=G′-k*g。

（4）在Rq上對f 進行求逆運算生成fq，在Rp上對f 進行求逆運算生成fp，即進行運算和

那么群成員的簽名密鑰為(f,g)。計算群成員的公鑰為hi=g×fq(mod q) ，系統(tǒng)公鑰。令S=，則計算追蹤密鑰為

6.2 簽名生成算法

群成員j 要對消息B 進行簽名，首先對消息B 使用hash 變換：H(B)，得到消息摘要m ∈[0,q)N。計算：

然后進行運算?=-{ }x 和?′=-{ }y 。

再計算：ej=?fj+?′gj。

對于每個1 ≤i ≤N ，隨機選取ri←Dr（其中Dr為小多項式的集合），計算Zi=ri×hi+ei(mod q)，然后通過判定語言Ls,γ和證據(jù)(ri,i)構(gòu)造一個基于NIWI 的證明π ，輸出加密的簽名c=(γ,Z1,Z2,…,Zn,π)（其中γ 為構(gòu)造NIWI證明時的參數(shù)）。

6.3 簽名驗證算法

本節(jié)中，NormBound 為驗證簽名是否合法的臨界值，β 為平衡因子，其范圍為0 ＜β ≤1。驗證者首先設(shè)置mˉ=m||γ，然后驗證π ，如果π 是正確的，且對于每個1 ≤i ≤N ，進行如下運算：

如果v ≤NormBound 則驗證正確，輸出1；否則輸出0。

6.4 簽名打開算法

7 安全性分析

7.1 正確性

本文方案簽名過程基于NTRUSign算法，所以簽名方案的正確性基于NTRUSign算法的正確性。在NTRUSign 算法中，假設(shè)有一個合法的簽名，計算，則 必然有v′≤num 。在本文方案中，驗證等式為v=，而對于一個合法的簽名c=(γ,Z1,Z2,…,Zn,π),有Zi=ri×hi+ei(mod q),等式兩邊同時乘以f ：

根據(jù)NTRU格上的性質(zhì)，小多項式g*r 的值是可忽略的，因此Zif=eif(mod q)。所以可以得到：v=v′≤num，即合法簽名能通過驗證算法的檢驗。

另外，由于本文方案方案利用NTRUSign算法得到的簽名ej是距離消息摘要m 最近的NTRU 格點，而Zj=rj×hj+ej是對rj×hj輕微擾動后的NTRU格點。而群管理員通過追蹤密鑰TK=可以解密(Z1,Z2,…,Zn),此時求出(‖ Z1-h1r1‖,‖ Z2-h2r2‖,…,‖ Zn-hnrn‖)中最小值所對應(yīng)的i，即為簽名ej所對應(yīng)的用戶j。即通過關(guān)系式min‖ ‖Zi-hiri，群管理員可成功推導(dǎo)出c 為群成員j 所簽。

綜上，本文群簽名方案滿足正確性。

7.2 匿名性

本文方案通過證明一系列的游戲G0,G0′,G1′,G1[4]中，G0和G0′ 不可區(qū)分，G0′ 和G1′ 不可區(qū)分，G1′ 和G1不可區(qū)分來證明G0和G1不可區(qū)分，進而證明方案的匿名性。

定理1 如果DLWEm,q,α問題是困難的，那么游戲G0和G1具有計算不可區(qū)分性。

證明如果引理2、引理3、引理4可證，則定理1可證。

引理2 如果DLWEm,q,α問題是困難的，那么G0和G0′具有計算不可區(qū)分性。

證明首先定義D 和A，D 為一個概率多項式時間算法，試圖攻破DLWEm,q,α難題，A 為模擬挑戰(zhàn)算法，試圖攻破G0和G0′ 的計算不可區(qū)分性。算法D 與算法A 進行交互，進行如下運算：首先，輸入(f,y),D 首先隨機選擇i*←[N]，令fi*=f ，對于其他的i ≠i*，隨機選擇均勻分布的Fi，計算fq←Invert(f),A 可獲得公鑰和追蹤密鑰TK=,A 進行的哈希詢問都可以得到正確的回應(yīng)，結(jié)果A 輸出i0,i ∈[N]和消息摘要m。此時結(jié)果若為i*≠i1，那么算法D 將隨機輸出一個比特后停止；結(jié)果若為i*=i1，算法D 將隨機地產(chǎn)生數(shù)值ri←Dr，然后D 計算eio=?fio+?′gio，并且滿足條件v ≤num ，同理，對于其他的i ≠i1，Zi獲得的方法和G0,G9′ 類似。如果i=i1，那么令Zii=y。設(shè)定Dy為y的均勻分布的情況，對A 而言，Dy和G0是統(tǒng)計接近的。在G0中，首先計算ei1=?fi1+?′gi1，然后得到Zi1=ri1×hi1+ei1；在Dy′中，計算ei1=?fi1+?′gi1，然后得到Zi1=ri1×hi1+ei1。由于D 停止的概率為1/N ，并且D 停止與A 獲勝相互獨立。如果A 以概率ε 區(qū)分出G0和G0′ ，則D 以概率ε/N 攻破了DLWEm,q,α難題，由此得出引理2。

引理3 如果游戲G0′ 和G1′ 基于的NIWI 證明系統(tǒng)滿足證據(jù)不可區(qū)分性，則游戲G0′ 和G1′ 具有計算不可區(qū)分性。

證明證明游戲G0′ 和G1′ 具有計算不可區(qū)分性只需要證明在π 進行運算時所使用的證據(jù)的不同即可。方案中基于的是NIWI 證明系統(tǒng)，該系統(tǒng)具有證據(jù)不可區(qū)分性，其中G0′ 的證據(jù)為(ri0,i0) ，而G1′ 的證據(jù)為(ri1,i1)，因此可得到G0′和G1′是計算不可區(qū)分的。

引理4 如果DLWEm,q,α問題是困難的，那么游戲G1和G1′具有計算不可區(qū)分性。

證明證明G1和G1′ 計算不可區(qū)分性的過程與引理2證明過程類似，此處不再贅述。

由引理2、引理3 和引理4，可得出如果DLWEm,q,α問題是困難的，則游戲G0和游戲G1是計算不可區(qū)分的，即定理1得證。

7.3 可追蹤性

可追蹤性的直觀定義是群管理員可以通過追蹤密鑰找到正確簽名者的身份，意味著，所有合法產(chǎn)生的簽名都是可追蹤的，即使攻擊者在擁有系統(tǒng)公鑰，追蹤密鑰，但沒有簽名密鑰的情況下，與任意群成員進行交互也無法偽造出一個合法的不能被追蹤的簽名。

本文所提方案的可追蹤性證明包括兩個方面：（1）證明合法產(chǎn)生的簽名都是可追蹤的；（2）證明攻擊者偽造不出一個合法的不可追蹤的簽名。根據(jù)本文7.1節(jié)正確性可以得知，合法產(chǎn)生的簽名都是可追蹤的。下面重點證明（2）攻擊者偽造不出一個合法的不可追蹤的簽名。定理2描述本文方案的可追蹤性依賴于NTRUSign簽名的不可偽造性，由定理2，假設(shè)攻擊者偽造了一個合法的不可追蹤的簽名，意味著NTRUSign簽名的不可偽造性被攻破，而NTRUSign 簽名在Appr-CVP 的困難假設(shè)下是安全的，所以本文方案具有可追蹤性。

定理2 假定存在一個概率多項式時間算法A（簡稱敵手A），執(zhí)行詢問后，能夠以概率ε 攻破本文方案的可追蹤性，那就會存在一個概率多項式時間算法F（簡稱敵手F）能以概率ε/N 攻破NTRUSign 簽名的不可偽造性。

證明如果有敵手F，與另一個敵手A 進行交互試圖攻擊NTRUSign算法，首先，執(zhí)行如下算法：

F 選定i*∈[N]，hi*=h，h 為F 所攻擊NTRUSign方案的公鑰，計算fq←Invert(f)，將公鑰和追蹤密鑰TK=發(fā)送給A。對于A 的詢問，F(xiàn) 進行如下回應(yīng)：

（1）當詢問私鑰預(yù)言機時，假若i ≠i*，則將fp發(fā)送給A，當i=i*時，F(xiàn) 終止游戲。

（2）當詢問簽名預(yù)言機時，假若i ≠i*，F(xiàn) 利用fp計算合法簽名然后發(fā)送給A；當i=i*時，F(xiàn) 會產(chǎn)生隨機數(shù)值ri←Dr，然后再一次針對消息向自己的簽名預(yù)言機進行詢問，此時該預(yù)言機會計算出一個合法的簽名ei*,然后發(fā)送給A。

（3）當詢問其他預(yù)言機時，敵手F 會詢問自身的隨機預(yù)言機，然后將結(jié)果發(fā)送給敵手A。

設(shè)C 為通過私鑰詢問系統(tǒng)的i 的集合（當i*∈C時則A 終止）。經(jīng)過交互詢問后，A 輸出一個消息摘要m 和 對 應(yīng) 的 密 文c=(γ,Z1,Z2,…,Zn,π) 。如 果G.Verify(PK,m,c)=1,并且敵手A 的所有簽名問詢G.Sign(i,m)都能得到i ∈C 。此時由于F 有追蹤密鑰TK=，所以可得到群成員G.Open(PK,m,c)的信息。在j=i*時，F(xiàn) 利用恢復(fù)出，此時滿足。然后輸出偽造的簽名；而當j ≠i*時，敵手F 停止游戲。

用ε 表示A 獲勝的概率。 F 不終止游戲的概率為1/N ，A 在從未詢問過G.Sign(i,m) 的基礎(chǔ)上可以以ε/N 的概率輸出滿足條件G.Verify(PK,m,c)=1 ，G.Open(TK,m,c)=i*的簽名(m,c)，對于上述簽名(m,c)，其中c=(γ,Z1,Z2,…,Zn,π)。由于G.Open(TK,m,c)=i*，所以F 可以利用追蹤密鑰恢復(fù)出ei*，并且滿足條件。由于G.Verify(PK,m,c)=1 ，那么可以得到v ≤NormBound ，即是對消息m‖ r ‖i*的合法簽名，此時A 并未詢問過G.Sign(i,m) ，也即F 從未對進行過簽名詢問就得到了合法簽名。即敵手A 以概率ε 攻破了本文方案的可追蹤性，那么在概率多項式時間內(nèi)敵手F 也可以以概率ε/N 攻破NTRUSign簽名的不可偽造性，定理2得證。

8 效率分析

本章選擇七個優(yōu)秀的格上群簽名方案作為比較對象：Gordon等[8]在ASIACRYPT'10提出了第一個基于格的群簽名方案（簡稱GKV2010 方案）；Laguillaumie 等[11]在ASIACRYPT'13 提出的簽名長度大小為O(lb N)的格上群簽名方案（簡稱LLLS2013方案）；Langlois等[15]在PKC'14提出的基于格的支持本地驗證者撤銷的群簽名方案（簡稱LLNW2014方案）；Nguyen等[12]在PKC'15提出的簽名長度大小為O(lb N)的格上群簽名方案（簡稱NZZ2015方案）；Ling等[16]在PKC'15提出的基于環(huán)的更簡單高效的格上群簽名方案（簡稱LNW2015 方案）；Libert 等[17]在EUROCRYPT'16 提出的不需要陷門的格上群簽名方案（簡稱LLNW2016方案）；Ling等[19]提出的格上全同態(tài)群簽名方案（將其稱為LLNX2017 方案）。表2 將本文方案與以上7 個方案在系統(tǒng)公鑰長度、用戶的簽名密鑰長度，簽名長度以及是否需要陷門等方面進行比較。在表2中，λ 為安全參數(shù)，N 為群簽名中用戶的數(shù)量（其中N=2l），λ ?l，O~ 為省略對數(shù)的計算復(fù)雜度。

表2 格上群簽名方案的性能比較

在系統(tǒng)公鑰長度方面，GKV2010 方案、LLLS2013方案、LLNW2014方案、NZZ2015方案、LLNW2016方案和LNWX2017 方案都是基于一般的格，其系統(tǒng)公鑰尺寸較大，而本文方案使用的是NTRU 格，由于NTRU 格特殊的矩陣結(jié)構(gòu)，使得本文方案中系統(tǒng)公鑰的長度為O~(λl2)，由于λ ?l，所以有O~(λ·l2)＜O~(λ2·l)，即本文方案的系統(tǒng)公鑰長度均低于這六個方案，既節(jié)省了群簽名算法中占用的存儲空間又降低了計算復(fù)雜度和通信代價；LNW2015 方案是第一次基于環(huán)構(gòu)造的格上群簽名方案，系統(tǒng)公鑰長度仍大于本文基于NTRU 格構(gòu)造的群簽名方案。在用戶簽名密鑰長度方面，本文方案的用戶簽名密鑰長度小于GKV2010 方案、LLLS2013 方案、LLNW2014 方案、NZZ2015 方案和LLNW2016 方案中用戶簽名密鑰的長度，但是與LNW2015 方案和LNWX2017 方案中用戶簽名密鑰長度相同，然而LNWX2017方案在簽名的過程中，由于在對消息進行簽名時，需要在時間點τ 檢測群信息inf oτ是否一致，相比本文方案需要額外的時間、空間上的消耗。在簽名長度方面，本文方案的簽名長度比GKV2010 方案的簽名長度小，原因在于雖然本文方案和GKV2010 方案都是基于NIWI 證明構(gòu)造的格上群簽名，但是本文方案基于的是NTRU格，產(chǎn)生簽名過程只涉及到多項式環(huán)的乘法和小整數(shù)求模運算，使得本文方案構(gòu)造的簽名的長度小于GKV2010 方案中基于一般格構(gòu)造的簽名的長度；但本文簽名長度比其他六個方案的簽名長度大，原因在于本文方案在基于NIWI 證明構(gòu)造群簽名方案的過程中，需輸出額外的證明信息π 來保證方案的匿名性，然而由引理1 可知，本文方案基于的NIWI 證明系統(tǒng)的長度為O(mnN lb q)bit，所以簽名長度雖然偏大但還是在可接受的范圍之內(nèi)的。在陷門需求方面，本文方案不需要陷門，簡化了整體的運算，使得密鑰生成更加快速，且方案在選擇參數(shù)時限制也會相對降低。

另外，表2 沒給出計算速度的比較。在計算速度上，本文方案只涉及到多項式環(huán)上的乘法和小整數(shù)求模運算，使得計算效率提高，并且由于NTRU 格特殊的矩陣結(jié)構(gòu)使得方案中系統(tǒng)公鑰、簽名密鑰和追蹤密鑰是并行計算的，使得運算更加簡單高效。

9 結(jié)束語

群簽名具有匿名性、可追蹤性等多種特點，在密碼學(xué)領(lǐng)域發(fā)揮重要作用。而在量子計算機得到應(yīng)用的前提下，傳統(tǒng)基于數(shù)論難題構(gòu)建的群簽名方案都將在多項式時間內(nèi)被破解，因而，研究基于格的群簽名是具有重要意義的。傳統(tǒng)的格上的群簽名方案都存在計算復(fù)雜度高、通信代價大和系統(tǒng)公鑰尺寸過大的弱點，研究格公鑰密碼尺寸更小的格上群簽名成為該領(lǐng)域值得深入研究的問題。本文采用一種NTRU 格上高效生成參數(shù)的算法構(gòu)建了一個基于NTRU格的群簽名，該方案有如下優(yōu)勢：（1）縮短了系統(tǒng)公鑰長度，節(jié)省了存儲空間，使得空間消耗降低；（2）由于NTRU格的特殊結(jié)構(gòu)，方案只涉及多項式環(huán)上的乘法和小整數(shù)求模運算，使方案中密鑰生成更為高效，且易于并行計算，提升計算效率。

本文方案不足之處在于由于方案在基于NIWI證明構(gòu)造簽名的過程中，需要輸出額外的證明信息來保證方案的匿名性，使得簽名長度偏大。如何在保證安全性的同時使簽名長度縮短，將是NTRU格上的群簽名值得進一步研究的問題。