新的NTRU格上抗量子攻擊的群簽名方案

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

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

1 引言

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

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

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

2 符號(hào)介紹

表1對(duì)下文中出現(xiàn)的符號(hào)進(jìn)行說(shuō)明。

表1 符號(hào)介紹

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

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

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

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

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

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

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

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

3.2 困難問(wèn)題假設(shè)

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

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

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

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

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

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

判定性LWE 問(wèn)題即為：區(qū)分LWEm,q,χ(s)和Um,q。假設(shè)存在概率多項(xiàng)式時(shí)間算法時(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問(wèn)題表示為DLWEm,q,α。

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

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

首先定義判定語(yǔ)言Ls,γ：

以下為兩種等價(jià)情況：

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

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

4.1 NTRUEncrypt算法

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

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

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

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

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

4.2 NTRUSign算法

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

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

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

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

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

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

如果有v ＜Normbound ，則表示驗(yàn)證成功，否則，表示驗(yàn)證失敗。

5 群簽名及安全模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

①敵手A可詢問(wèn)私鑰預(yù)言機(jī)，對(duì)于輸入i，輸出SKi。

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

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

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

②對(duì)于i ?C,A 未進(jìn)行G.Sign(i,M)的詢問(wèn)；

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

6 本文的方案

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

6.1 密鑰生成算法

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

密鑰生成算法具體如下：

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

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

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

（4）在Rq上對(duì)f 進(jìn)行求逆運(yùn)算生成fq，在Rp上對(duì)f 進(jìn)行求逆運(yùn)算生成fp，即進(jìn)行運(yùn)算和

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

6.2 簽名生成算法

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

然后進(jìn)行運(yùn)算?=-{ }x 和?′=-{ }y 。

再計(jì)算：ej=?fj+?′gj。

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

6.3 簽名驗(yàn)證算法

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

如果v ≤NormBound 則驗(yàn)證正確，輸出1；否則輸出0。

6.4 簽名打開算法

7 安全性分析

7.1 正確性

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

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

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

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

7.2 匿名性

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

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

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

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

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

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

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

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

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

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

7.3 可追蹤性

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

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

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

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

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

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

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

（3）當(dāng)詢問(wèn)其他預(yù)言機(jī)時(shí)，敵手F 會(huì)詢問(wèn)自身的隨機(jī)預(yù)言機(jī)，然后將結(jié)果發(fā)送給敵手A。

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

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

8 效率分析

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

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

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

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

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

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

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