格上基于身份的群簽名方案

湯永利 李元鴻 張曉航 葉 青

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

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

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

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

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

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

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

1 預(yù)備知識

1.1 符號說明

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

Table 1 Symbol Description表1 符號說明

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

定義1.系數(shù)映射和環(huán)同態(tài)映射.給定多項(xiàng)式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上的一個(gè)概率分布χ.對于s∈Rq，隨機(jī)選取a←Rq和e←χ，定義由(a,b=a·s+e)產(chǎn)生的分布為As,χ.DRLWEn,m,q,χ問題是指判別m個(gè)樣本是取自分布As,χ還是取自分布U(Rq×Rq).

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

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

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

1.4 相關(guān)算法

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

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

1)Keygen(1n,1N).輸入安全參數(shù)n和群成員的最大可能個(gè)數(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).

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

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

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

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

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

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

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

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

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

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

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

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

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

③ A未對消息m*以及群成員j∈[N]進(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誠實(shí)地運(yùn)行Keygen(1n,1N)算法，得到系統(tǒng)公鑰PK管理員追溯密鑰gtk以及系統(tǒng)主密鑰gmk，將系統(tǒng)公鑰PK和追溯密鑰gtk發(fā)送給攻擊者A.

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

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

3 方案構(gòu)造

本文結(jié)合引理3～5的算法構(gòu)造了一個(gè)隨機(jī)預(yù)言模型下的格上基于身份的群簽名方案，核心思想是使用引理3的陷門生成算法建立，并獲得系統(tǒng)公鑰和主密鑰，然后利用引理5的格基委派技術(shù)和引理4的原像采樣算法提取用戶身份信息并生成用戶公私鑰.在簽名生成階段使用引理2的拒絕采樣技術(shù)以一定概率生成簽名，并使得簽名的概率分布與簽名私鑰的分布相獨(dú)立，簽名過程中同時(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運(yùn)行.輸入系統(tǒng)系統(tǒng)公鑰PK，系統(tǒng)主密鑰gmk以及用戶身份IDπ，KGC進(jìn)行如下操作提取用戶私鑰：

④ 計(jì)算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).

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

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

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

4 安全性證明

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

定理1.正確性.本文提出的方案是正確的，即一個(gè)真實(shí)的簽名是能夠被成功驗(yàn)證和打開的.

證明.

1) 驗(yàn)證正確性.

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

本方案的驗(yàn)證正確性得以滿足.

2) 打開正確性.

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

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

定理2.完全匿名性.在DRLWEn,l,q,χ問題的假設(shè)下，本文的方案在隨機(jī)預(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)行問詢，如果Σ由群中用戶j∈[N]合法產(chǎn)生，則返回用戶j的身份信息，否則返回⊥.

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

證畢.

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

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

證畢.

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

證畢.

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

證畢.

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

對上式化簡可得

(1)

(2)

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

證畢.

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

(3)

即

(4)

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

由于A偽造的簽名具有驗(yàn)證正確性，滿足

又因?yàn)棣?能夠被打開并追溯到j(luò)，所以有

即Σ通過了驗(yàn)證算法和打開算法.

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

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

移項(xiàng)可得

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

證畢.

5 效率分析

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

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

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

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

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

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

6 結(jié)束語

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

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