湯永利 李元鴻 張曉航 葉 青

1(河南理工大學計算機科學與技術(shù)學院 河南焦作 454003)2(河南工業(yè)和信息化職業(yè)學院 河南焦作 454003)(yltang@hpu.edu.cn)

群簽名由Chaum等人[1]在1991年提出，是密碼學領(lǐng)域中的一個重要概念.在群簽名中，合法群成員能夠代表整個群進行簽名，但是無法通過簽名來確定簽名者的身份信息，即群簽名有匿名性.此外，當有爭議發(fā)生時，群管理員能夠利用追蹤密鑰打開簽名并得到簽名者的真實信息，即群簽名有可追溯性.匿名性和可追溯性使得群簽名能夠在多種場景下得到應(yīng)用，例如，匿名電子投票、受信計算平臺以及電子商務(wù)系統(tǒng)等.

近幾年，量子計算機的研究不斷取得突破，一旦量子計算機得到應(yīng)用，基于傳統(tǒng)數(shù)論難題構(gòu)造的群簽名就能夠在概率多項式時間(probabilistic poly-nomial time, PPT)內(nèi)被攻破，因此建立在最壞情況困難性假設(shè)上的格密碼成為了后量子密碼時代的研究熱點.2010年，Gordon等人[2]在隨機預(yù)言模型下提出了第1個格上的群簽名方案，并且將該方案的匿名性和可追溯性分別規(guī)約到容錯學習(learning with errors, LWE)問題和GapSVP(gap shortest vector problem)問題，但其密鑰和簽名的開銷過大.隨后，Laguillaumie等人[3]提出了一種更為高效的格上群簽名方案，將其方案的可追溯性規(guī)約至小整數(shù)解(short integer solution, SIS)問題上，同時優(yōu)化了密鑰長度和簽名長度，但代價是公共參數(shù)開銷較大.2015年，Nguyen等人[4]和Ling等人[5]設(shè)計了2種不同的格上群簽名方案，前者使用了與身份編碼技術(shù)相結(jié)合的非交互零知識證明協(xié)議，使得該方案的結(jié)構(gòu)更為簡單，而后者基于多項式環(huán)以及環(huán)上小整數(shù)解(ring short integer solution, RSIS)、環(huán)上容錯學習(ring learning with errors, RLWE)問題，具有更低的存儲開銷和時間復(fù)雜度.張彥華等人[6]利用文獻[4]提出的身份編碼技術(shù)構(gòu)造了支持驗證者本地撤銷的群簽名.Libert等人[7]基于Merkle Hash樹以及Stern非交互式零知識證明協(xié)議，提出了第1個不依賴GPV陷門[8]的格上群簽名方案.2017年，Ling等人[9]提出了完全動態(tài)的群簽名方案，允許用戶動態(tài)地加入和離開群組，李雪蓮等人[10]在此基礎(chǔ)上構(gòu)造了新的群成員撤銷機制，支持動態(tài)地加入和撤銷用戶.2018年，Ling等人[11]提出了固定簽名長度的群簽名方案，該方案利用Ducas等人[12]提出的簽名算法設(shè)計了零知識證明協(xié)議，使密鑰大小和簽名大小都與用戶成員數(shù)N無關(guān).Pino等人[13]基于小型的零知識證明[14]構(gòu)造了計算效率更高和存儲開銷更小的群簽名方案.2019年，Katsumata等人[15]提出了標準模型下的格上群簽名，該方案沒有使用零知識證明系統(tǒng)，提高了運算效率，且滿足CCA(chosen ciphertext attack)自身匿名性和完全可追溯性.2020年，Sun等人[16]和Canard等人[17]在文獻[15]的基礎(chǔ)上進行了改進.但上述的格上群簽名方案均基于傳統(tǒng)公鑰基礎(chǔ)設(shè)施(public key infrastructure, PKI)進行構(gòu)造，無法抵抗公鑰偽造攻擊，且存在PKI體系中復(fù)雜的用戶證書管理問題.

基于身份的加密體制(identity based encryption, IBE)是另一種密碼學原語，由Shamir[18]于1984年提出.在基于身份的密碼體制中，密鑰生成中心(key generation center, KGC)根據(jù)用戶的身份信息，例如：姓名、身份證號、電子郵箱等生成用戶公鑰，并使用用戶身份信息和系統(tǒng)私鑰計算生成對應(yīng)的私鑰并發(fā)放給用戶，有效地避免了PKI體系中公鑰證書管理的問題.Ibraimi等人[19]、Emura等人[20]分別提出了基于身份的群簽名方案，但都基于有限域離散對數(shù)的傳統(tǒng)數(shù)論難題，難以抵抗量子算法的攻擊.

本文將格上的群簽名與基于身份加密體制相結(jié)合，提出了一種格上基于身份的群簽名方案.主要貢獻有2個方面：

1) 通過環(huán)上陷門生成算法[5]生成系統(tǒng)公鑰和系統(tǒng)主密鑰，再利用格基委派技術(shù)[21]和原像采樣算法生成用戶私鑰，采用拒絕采樣算法[22]和經(jīng)過Naor-Yung變換[23]的雙重加密算法[24](LPR加密算法)生成簽名.在Bellare等人[25]的群簽名安全模型下，對所提方案進行嚴謹?shù)陌踩C明.證明結(jié)果表明，在隨機預(yù)言模型下，所提方案滿足正確性、完全匿名性、不可偽造性以及完全可追溯性.其中，完全匿名性可規(guī)約至RLWE困難性假設(shè)，不可偽造性和完全可追溯性可規(guī)約至RSIS困難性假設(shè).

2) 將本文方案與4個現(xiàn)有的格上群簽名方案[7,9,11,26]進行了效率比較，分析比較結(jié)果表明，與其他方案相比，本文方案具有更小的密鑰和簽名尺寸.且由于使用了拒絕采樣技術(shù)，本文方案在簽名時避免零知識證明系統(tǒng)的并行重復(fù)，有效地提高了簽名和驗證過程的計算效率.

1 預(yù)備知識

1.1 符號說明

表1對本文出現(xiàn)的符號進行簡要的說明.

Table 1 Symbol Description表1 符號說明

1.2 格的相關(guān)定義

定義1.系數(shù)映射和環(huán)同態(tài)映射.給定多項式v=v0+v1x+…+vn-1xn-1∈Rq，令τ(v)=(v0,v1,…,vn-1)T∈令Rot(v)=(τ(v),τ(v·x),…,τ(v·xn-1))∈對于Rot(A)=(Rot(a1),Rot(a2),…,Rot(am))∈

定義3.DRLWEn,m,q,χ問題[24].給定n,m≥1，q≥2，R上的一個概率分布χ.對于s∈Rq，隨機選取a←Rq和e←χ，定義由(a,b=a·s+e)產(chǎn)生的分布為As,χ.DRLWEn,m,q,χ問題是指判別m個樣本是取自分布As,χ還是取自分布U(Rq×Rq).

1.3 離散高斯分布和拒絕采樣算法

引理1[13].給定σ>0，正整數(shù)m，和任意正整數(shù)k>0，則式1)～2)成立：

引理2.拒絕采樣算法[22].令V={v∈為1個概率分布，則存在常數(shù)M=O(1),使得2個算法①～②的輸出在統(tǒng)計上的距離小于2-ω log m/M：

1.4 相關(guān)算法

2 基于身份的群簽名定義及安全模型

定義5.基于身份的群簽名.結(jié)合Bellare等人[25]和Shamir[18]的定義，1個基于身份的群簽名方案有5個多項式時間算法：

1)Keygen(1n,1N).輸入安全參數(shù)n和群成員的最大可能個數(shù)N，輸出系統(tǒng)公鑰PK，管理員追溯密鑰gtk以及系統(tǒng)主密鑰gmk.

2)Extract(PK,gmk,IDπ).輸入系統(tǒng)公鑰PK，系統(tǒng)主密鑰gmk以及用戶π的身份信息IDπ，輸出用戶私鑰gskπ=(xπ,1,xπ,2).

基于身份的群簽名需要滿足正確性、匿名性、不可偽造性和完全可追溯性.其中，群簽名的正確性包括驗證正確性和打開正確性；匿名性是指攻擊者無法確定一個群簽名具體是由群中哪個用戶生成的，而本文方案具有的完全匿名性又稱作CCA匿名性[4,15]，是指在允許攻擊者A進行簽名問詢和打開問詢后仍然能夠保持簽名的匿名性，具體見定義6；不可偽造性是指在沒有群成員簽名密鑰的情況下，攻擊者無法生成有效的群簽名，具體見定義7；完全可追溯性是指任意1個合法的群簽名一定能夠被群管理員通過追蹤密鑰打開，具體見定義8.本文通過攻擊者A和挑戰(zhàn)者C之間進行的一系列游戲來刻畫基于身份群簽名的安全性定義.在隨機預(yù)言模型下，攻擊者A能夠訪問隨機預(yù)言機并且向挑戰(zhàn)者C進行3種問詢：

1) 簽名問詢.攻擊者A選擇群中成員j∈[N]以及待簽消息m∈{0,1}*進行問詢，C運行Signature()簽名算法使用IDj對應(yīng)的私鑰gskj對m進行簽名，并返回對應(yīng)的Σ給A.

2) 私鑰問詢.A選擇群中成員j∈[N]進行問詢，C運行Extract()私鑰提取算法返回IDj對應(yīng)的私鑰gskj.

3) 打開問詢.A選擇消息m∈{0,1}*及其對應(yīng)的群簽名Σ進行問詢，C運行Opening()打開算法，如果Σ由群中用戶j∈[N]合法產(chǎn)生，則返回用戶j的身份信息IDj，否則返回⊥.

定義6.完全匿名性[4,15].與CPA匿名性不同，完全匿名性(CCA匿名性)是指挑戰(zhàn)者C在問詢階段授予攻擊者A簽名問詢和打開問詢的權(quán)限，攻擊者A贏得4個階段的游戲的優(yōu)勢仍然是忽略的:

1) 系統(tǒng)建立.挑戰(zhàn)者C輸入安全參數(shù)λ和用戶數(shù)N誠實地運行Keygen(1n,1N)算法，得到系統(tǒng)公鑰PK管理員追溯密鑰gtk以及系統(tǒng)主密鑰gmk，將系統(tǒng)公鑰PK和群用戶私鑰gskj發(fā)送給攻擊者A.

2) 問詢階段.攻擊者A可以訪問預(yù)言機并進行系統(tǒng)建立階段的簽名問詢和打開問詢.

4) 猜測階段.攻擊者A對簽名者身份進行猜測，得出b*∈{0,1}，若滿足條件b*=b，則稱A贏得了完全匿名性游戲.

定義A贏得游戲的優(yōu)勢為

1) 系統(tǒng)建立.輸入安全參數(shù)λ和用戶數(shù)N，挑戰(zhàn)者C誠實地運行Keygen(1n,1N)算法，得到系統(tǒng)公鑰PK，管理員追溯密鑰gtk以及系統(tǒng)主密鑰gmk，將系統(tǒng)公鑰PK和追溯密鑰gtk發(fā)送給攻擊者A.

2) 問詢階段.攻擊者A被允許進行上述的簽名問詢和私鑰問詢.

3) 偽造階段.攻擊者A給出關(guān)于消息m*的簽名Σ*，判斷是否滿足條件(①～③)：

② A未對群成員j∈[N]進行過私鑰問詢.

③ A未對消息m*以及群成員j∈[N]進行過簽名問詢.

定義攻擊者A贏得不可偽造性游戲的優(yōu)勢為

Fig. 1 The flow chart of identity-based group signature on lattice圖1 格上基于身份的群簽名方案流程圖

1) 系統(tǒng)建立.挑戰(zhàn)者C輸入安全參數(shù)λ和用戶數(shù)N誠實地運行Keygen(1n,1N)算法，得到系統(tǒng)公鑰PK管理員追溯密鑰gtk以及系統(tǒng)主密鑰gmk，將系統(tǒng)公鑰PK和追溯密鑰gtk發(fā)送給攻擊者A.

2) 問詢階段.攻擊者A能夠訪問預(yù)言機并進行上述的簽名問詢和私鑰問詢.令Γ用來存儲經(jīng)過私鑰問詢的j；令Ι用來存儲經(jīng)過簽名問詢的(j,m).

定義A贏得完全可追溯游戲的優(yōu)勢為

3 方案構(gòu)造

本文結(jié)合引理3～5的算法構(gòu)造了一個隨機預(yù)言模型下的格上基于身份的群簽名方案，核心思想是使用引理3的陷門生成算法建立，并獲得系統(tǒng)公鑰和主密鑰，然后利用引理5的格基委派技術(shù)和引理4的原像采樣算法提取用戶身份信息并生成用戶公私鑰.在簽名生成階段使用引理2的拒絕采樣技術(shù)以一定概率生成簽名，并使得簽名的概率分布與簽名私鑰的分布相獨立，簽名過程中同時使用了LPR雙重加密算法，能夠?qū)⒈疚姆桨傅耐耆涿砸?guī)約到RLWE困難假設(shè)下.方案的流程圖如圖1所示.

④ 輸出系統(tǒng)公鑰PK=(A,B,u,a,b)，追溯密鑰gtk=s，主密鑰gmk=TA.

2) 私鑰提取Extract(PK,gmk,IDπ).此步驟由KGC運行.輸入系統(tǒng)系統(tǒng)公鑰PK，系統(tǒng)主密鑰gmk以及用戶身份IDπ，KGC進行如下操作提取用戶私鑰：

④ 計算xπ,2←SamplePreRq(Dπ,Tπ,u-gπ,σ1).

⑤ 輸出用戶私鑰gskπ=(xπ,1,xπ,2).

⑤ 輸出用戶π對m的群簽名Σ=((zi,1,zi,2)1≤i≤N,v1,t1,t2,t3).

③ 如果步驟①和②都成立，則驗證者返回“Valid”，即認為群簽名Σ為群中某一成員對消息m的有效簽名；否則驗證者返回“Invalid”.

③ 根據(jù)每個用戶的身份信息IDi計算出對應(yīng)的Di，驗證gk是否滿足等式

④ 如果步驟③成立，則證明打開成功，并且返回用戶身份IDk；否則打開失敗，返回“⊥”.

4 安全性證明

此部分對所提方案的正確性、完全匿名性以及完全可追溯性3個重要的安全屬性進行詳細的證明，并且將完全匿名性和完全可追溯性分別規(guī)約到RLWE和RSIS問題上.

定理1.正確性.本文提出的方案是正確的，即一個真實的簽名是能夠被成功驗證和打開的.

證明.

1) 驗證正確性.

假設(shè)Σ=((zi,1,zi,2)1≤i≤N,v1,t1,t2,t3)是群中用戶π對消息m按照簽名算法產(chǎn)生的簽名，則下列等式成立：

本方案的驗證正確性得以滿足.

2) 打開正確性.

假設(shè)Σ=((zi,1,zi,2)1≤i≤N,v1,t1,t2,t3)是群中用戶π對消息m的有效簽名.

本方案的打開正確性得以滿足.證畢.

定理2.完全匿名性.在DRLWEn,l,q,χ問題的假設(shè)下，本文的方案在隨機預(yù)言模型中是完全匿名的.

證明.下面通過證明G0,G1,G2,G3一系列游戲的不可區(qū)分來證明本文方案的完全匿名性.

① 簽名問詢.輸入任意明文m∈{0,1}*以及用戶i，返回對應(yīng)的簽名Σ=((zi,1,zi,2)1≤i≤N,v1,t1,t2,t3)給A.

② 打開問詢.A選擇消息m∈{0,1}*及其對應(yīng)的群簽名Σ進行問詢，如果Σ由群中用戶j∈[N]合法產(chǎn)生，則返回用戶j的身份信息，否則返回⊥.

引理6.G1與G0在統(tǒng)計上不可區(qū)分.

證畢.

引理7.G1與G2在統(tǒng)計上不可區(qū)分.

證明.與引理6證明同理可得G2與G1的距離在統(tǒng)計上是可忽略的.

證畢.

引理8.G3與G2在計算上不可區(qū)分.

證畢.

G3可以看作是經(jīng)過Naor-Yung變換[23]的LPR加密方案[24]，而該加密方案被證明是IND-CCA安全的.且G3中所得簽名均由隨機向量構(gòu)成，所以A已無法從簽名中得到任何有關(guān)用戶IDb的信息.因此，可以計算出Pr[G3]=1/2+negl(n).由引理6～8可得，G0,G1,G2,G3在統(tǒng)計和計算上是不可區(qū)分的，因此得出A贏得G0的概率為Pr[G0]=1/2+negl(n)，即A攻破G0的完全匿名性的優(yōu)勢是可忽略的，而G0是挑戰(zhàn)者C誠實執(zhí)行本文方案后進行的交互游戲，因此A攻破本方案的完全匿名性的優(yōu)勢是可忽略的.

證畢.

定理3.不可偽造性.在RSISn,m,q,β問題的假設(shè)下，本文方案在隨機預(yù)言模型下滿足不可偽造性.

對上式化簡可得

(1)

(2)

聯(lián)立式(1)(2)后，得到

證畢.

又由于A偽造的簽名Σ*能夠滿足驗證正確性，則有

(3)

即

(4)

聯(lián)立式(3)(4)可得

由于A偽造的簽名具有驗證正確性，滿足

又因為Σ*能夠被打開并追溯到j(luò)，所以有

即Σ通過了驗證算法和打開算法.

此時式(3)和(4)成立，聯(lián)立可得

由于上述2種情況都能夠通過驗證算法，所以有

移項可得

綜上所述，攻擊者A若贏得完全可追溯性游戲，則C將求得上述RSIS問題的小整數(shù)解，但是在RSIS困難假設(shè)下求小整數(shù)解是困難的，因此攻擊者A無法滿足以上2個條件，所以本方案具有完全可追溯性.

證畢.

5 效率分析

選擇4個現(xiàn)有的格上群簽名方案與本文方案進行對比，分別是Libert等人[7]提出的沒有陷門的對數(shù)大小的格上群簽名、Ling等人[9]提出的基于格的完全動態(tài)群簽名、Ling等人[11]提出的格上恒定大小的群簽名以及Xu[26]提出的前向安全群簽名.本文實驗針對系統(tǒng)公鑰長度、管理員追溯密鑰長度、用戶私鑰長度、簽名長度等指標進行對比.

表2為格上群簽名在漸進效率方面的對比，其中n為安全參數(shù)，N=2為最大群成員個數(shù).由表2可知，文獻[7,9,26]的系統(tǒng)公鑰、用戶私鑰以及簽名的長度均與最大群成員個數(shù)N呈對數(shù)關(guān)系，而本文方案的和文獻[11]方案的公私鑰均為固定長度，僅與安全參數(shù)n相關(guān).但注意到由于本文要實現(xiàn)的是基于身份的群簽名方案，需要采用格基委派技術(shù)生成用戶的私鑰，進而造成所生成簽名的長度與N呈線性關(guān)系；而其他方案雖然在簽名長度方面或與N呈對數(shù)關(guān)系(文獻[7,9,26])，或為固定長度(文獻[11])，但它們均不具有基于身份的屬性，存在公鑰證書管理的負擔.為了使比較結(jié)果更加直觀，本文在保證所提方案滿足安全性的前提下，選取了5組特定參數(shù)，即和N∈{256,512,1 024,2 048}，對4個方案的系統(tǒng)公鑰長度、管理員追溯密鑰長度、用戶私鑰長度及簽名長度進行量化對比，比較結(jié)果列于表3.

Table 2 Comparison for the Asymptotic Efficiency of Group Signature表2 群簽名漸進效率對比

Table 3 Comparison for the Efficiency of Group Signature Under Different Number of Members表3 不同成員個數(shù)下的群簽名效率對比

從表3可以看出，當安全參數(shù)n=512，最大群成員個數(shù)N∈{256,512,1 024,2 048}時，本文方案的公私鑰長度在5個方案中最短，平均縮小了79.6%；當N≤1 024時，本文方案的簽名長度在5個方案中仍為最短，平均縮小了57.3%；但當N=2 048時，本文方案的簽名長度超過文獻[7,9,26]的簽名長度.綜上所述，相較于文獻[7,9,11,26]，本文方案的公私鑰長度平均縮小了79.6%，簽名長度平均縮小了39.9%.

另外，文獻[7,9,11,26]的零知識證明系統(tǒng)存在健全性誤差，在生成簽名時均需要ω(logn)次的并行重復(fù)，而本文方案沒有使用到零知識證明系統(tǒng)，僅調(diào)用1次拒絕采樣算法即可實現(xiàn)簽名.因此，與同類方案相比，本文方案具有較小的存儲開銷和計算開銷，且更適用于小群組(例如N≤1 024)的場景.

6 結(jié)束語

相較于其他群簽名，格上的群簽名能夠抵抗量子算法的攻擊，格上基于身份的群簽名能夠避免復(fù)雜的用戶公鑰證書管理問題，可以有效地應(yīng)用于匿名電子投票和電子商務(wù)系統(tǒng)等領(lǐng)域.本文基于RLWE和RSIS困難假設(shè)，在隨機預(yù)言模型下提出了一個格上基于身份的群簽名方案，并給出了詳細的安全性證明.與已有的格上群簽名方案相比，本文方案沒有使用零知識證明，而是通過拒絕采樣算法提高簽名生成計算效率，密鑰尺寸也相較其他方案更具優(yōu)勢，但簽名長度與用戶數(shù)呈線性關(guān)系，用戶數(shù)N≥2 048時簽名尺寸相對于其他方案較長.因此，下一步將考慮構(gòu)造簽名長度更短、運行效率更高的格上基于身份的群簽名.

作者貢獻聲明：湯永利指導方案的整體設(shè)計、安全性分析以及論文撰寫，把握論文整體創(chuàng)新性；李元鴻負責方案擬定、論文撰寫以及效率分析；張曉航負責論文圖表設(shè)計與規(guī)劃，并參與了實驗數(shù)據(jù)的整理；葉青負責把握論文創(chuàng)新性，并參與數(shù)學公式校對和方案效率分析.