支持LSSS訪問結(jié)構(gòu)的屬性基群簽名方案的研究

許玉嵐，陳燕俐，高詩堯

(南京郵電大學(xué) 計算機學(xué)院、軟件學(xué)院、網(wǎng)絡(luò)空間安全學(xué)院，江蘇 南京 210003)

0 引 言

屬性基群簽名(attribute-based group signature，ABGS)是對傳統(tǒng)群簽名(group signature，GS)的一種擴展，通過對群成員的身份特征進行劃分，賦予用戶不同的“屬性”，這些“屬性”可以用來標(biāo)識群成員所擁有的權(quán)限，因此可以通過規(guī)定具有某些屬性的群成員簽署簽名，來對簽名者的權(quán)限進行限制，不符合要求的群成員生成的簽名將被驗證為無效簽名。因為屬性基群簽名是將基于屬性的簽名[1](attribute based signature，ABS)與傳統(tǒng)的群簽名相結(jié)合，因此訪問結(jié)構(gòu)的選擇與方案的好壞有著直接的關(guān)系。而目前屬性基的群簽名都是基于訪問樹結(jié)構(gòu)的情況，樹結(jié)構(gòu)能夠表示靈活的訪問控制策略，但其安全性證明僅基于一般的群假設(shè)，但因為訪問結(jié)構(gòu)表示為一棵樹，因此需要使用遞歸來進行運算。而遞歸的深度達到一定的程度時，程序的運行時間空間將受到一定影響。而LSSS訪問結(jié)構(gòu)很好地解決了這個問題。LSSS利用線性秘密分享方案的秘密可線性重組的性質(zhì)重構(gòu)秘密，不需要進行遞歸操作，提高了屬性基簽名方案的簽名和效率，并且LSSS與訪問控制樹的表達性相當(dāng)。因此，文中首次提出了一個支持LSSS訪問結(jié)構(gòu)的屬性基群簽名方案。

1 相關(guān)工作

1.1 群簽名

自Chaum和Heyst[2]首次提出了群簽名的概念，學(xué)者對群簽名方案的研究包括增加各種功能，定義不同的安全概念以及提高方案的性能。

2000年，Ateniese、Caneniseh、Joye和Tsudik[3]使用交互的零知識證明(non-interactive zero-knowledge proof，NIZK)構(gòu)造出第一個高效的、抗聯(lián)合攻擊的群簽名方案,并且給出了隨機預(yù)言模型下的安全性證明。Bellare，Micciancio等人[4]給出群簽名的兩個核心安全性質(zhì)為強匿名性和強可追蹤性。簡化了群簽名方案的安全性證明，即只需證明方案滿足這兩個安全性質(zhì)。

2007年，Boyen，Waters[5]在標(biāo)準(zhǔn)模型下提出了群簽名，該方案的基本思想是基于層次簽名，即成員證書是第一層簽名(即GM對用戶身份的簽名)，利用第一層簽名作為密鑰，用戶可生成第二層簽名(即對某信息的簽名)，此簽名還不可作為群簽名，還需利用承諾方案對簽名進行匿名化，最后利用標(biāo)準(zhǔn)模型下的NIZK證明承諾中的隱藏內(nèi)容是合法的簽名。

2019年，李雪蓮等人[6]提出適合群成員數(shù)量較大的動態(tài)群簽名，該方案利用群管理員或群成員本人與撤銷圖靈機通信，圖靈機確定其身份后將撤銷令牌添加到撤銷列表即完成了撤銷操作。2020年，葉青，楊曉孟等人[7]提出NTRU格上抗量子攻擊的群簽名方案，該方案利用NTRU格密碼體制所需公私鑰長度更短,運算速度更快的特點，構(gòu)建了一個系統(tǒng)公鑰長度小，計算效率高的群簽名方案。張緒霞等人[8]于2020年提出一個基于中國剩余定理的前向安全群簽名方案，該方案可以動態(tài)地增加和刪除群用戶成員而無須頻繁更改群公鑰，并在驗證簽名和打開簽名時只需要進行模運算即可實現(xiàn)，同時針對密鑰泄露問題實現(xiàn)了前向安全性。歐海文等人[9]于2020年提出一種具有前向和后向安全性的高效群簽名方案，通過添加隨機數(shù)的方式打破了公鑰狀態(tài)列表中公鑰和私鑰的直接聯(lián)系,規(guī)避了被撤銷成員聯(lián)合得出其他成員私鑰的風(fēng)險，且群成員私鑰隨時間段跨越而自然更新(群管理員的私鑰也因應(yīng)改變),避免以往群成員發(fā)生私鑰泄漏后需要重新選取密鑰對才能保證后續(xù)簽名安全性的繁瑣過程。

1.2 屬性基群簽名

2007年，Khader[10]將傳統(tǒng)的群簽名方案進行了擴展，利用屬性基的簽名技術(shù)與群簽名方案相結(jié)合，提出了屬性基群簽名。和屬性基簽名方案相同，用戶是由屬性集合表示，所以驗證者并不知道群中用戶的身份信息，只知道其相關(guān)屬性，這樣做到了對用戶身份信息的隱私保護。與一般屬性基方案不同的是，屬性基群簽名中的簽名者在需要的時候可以由群管理員揭示。2008年，Khader在文獻[11]中對上一方案進行了改進，實現(xiàn)了對群中用戶的撤銷和對屬性的刪除操作，使之更接近實際應(yīng)用。

Emura等人[12]于2009年提出了動態(tài)的屬性基群簽名方案，其中允許訪問結(jié)構(gòu)樹可變。2013年，Syed，Amberker[13]等人提出了一種具有屬性匿名性和具有恒定簽名大小的跟蹤功能的ABGS方案，并證明了它在標(biāo)準(zhǔn)模型中的安全性。該方案的構(gòu)造使用成員資格證書格式來實現(xiàn)標(biāo)準(zhǔn)模型中的不可陷害性，并使用Groth-Sahai[14]非交互式證明系統(tǒng)為標(biāo)準(zhǔn)模型下的群簽名中的關(guān)系生成非交互式目擊者不可區(qū)分性(NIWI)證明。

2017年，基于Merkle類的訪問樹，Kuchta[15]等人首次給出了基于格的屬性基群簽名方案，該方案同時具有加入和撤銷機制，但該方案撤銷成員時需要更新哈希樹，計算復(fù)雜且耗時較長，并且該方案的簽名長度與群成員數(shù)量相關(guān)。2019年P(guān)erera，Nakamura等人[16]提出了一種具有高效跟蹤機制的新型VLR-ABGS方案。使用靜態(tài)群簽名方案中使用的跟蹤算法來跟蹤簽名者及其在該方案中用于簽名的屬性。還使用群管理員的公鑰來加密簽名者的身份及其屬性。因此，只有群管理員才能識別簽名者和簽名者的屬性。2020年張彥華等人[17]針對本地驗證者撤銷的屬性基群簽名群公鑰尺寸過長、空間效率不高的問題，采用身份編碼技術(shù)對群成員身份信息進行編碼,減少群公鑰長度，通過單向和單射的帶誤差學(xué)習(xí)函數(shù)來完成撤銷。

1.3 文中貢獻

文中提出一種支持LSSS訪問結(jié)構(gòu)的屬性基群簽名方案，具體貢獻如下：

(1)方案簽名采用LSSS訪問結(jié)構(gòu)，效率更高。因為訪問結(jié)構(gòu)需要使用遞歸來進行運算，遞歸的深度達到一定的程度時，程序的運行時間空間將受到一定影響。本方案利用線性秘密分享方案的秘密可線性重組的性質(zhì)重構(gòu)秘密，不需要進行遞歸操作，且LSSS與訪問控制樹的表達性相當(dāng)。

(2)實現(xiàn)了簽名屬性匿名性且簽名長度固定。一般屬性基群簽名中將簽名屬性與簽名一起發(fā)送給驗證者，方案利用Groth-Sahai非交互式證明系統(tǒng)實現(xiàn)了簽名屬性的匿名性。并且方案使簽名長度和計算開銷是固定值，與簽名者的屬性數(shù)量無關(guān)，減少了通信和計算開銷。

(3)實現(xiàn)了屬性可追蹤性。在上述具有屬性匿名性的ABGS方案的基礎(chǔ)上，提出了屬性追蹤，在發(fā)生用戶濫用簽名權(quán)限時，不但可以追蹤到用戶的身份，還可以追蹤到用戶具有的屬性和簽名的屬性。

2 預(yù)備知識

定義1. 雙線性映射(bilinear maps)[3]：設(shè)G1,G2,GT是階為素數(shù)p的乘法循環(huán)群,g1,g2分別是G1,G2的生成元，存在一個具有如下性質(zhì)的雙線性映射e:G1×G2→GT：

(a)雙線性：對于任意的u∈G1,v∈G2,a,b∈Zp，有e(ua,vb)=e(u,v)ab；

(b)非退化性：G1,G2中存在g1,g2，滿足e(g1,g2)≠1。

這里的雙線性映射被認為是type-3映射：同構(gòu)映射ψ:G2→G1及其逆ψ-1:G1→G2都不能有效計算。

定義2. 線性秘密分享方案(linear secret sharing schemes，LSSS)[17]:設(shè)={p1,p2,…,pn}為n個參與者集合。一個上的秘密共享方案∏被稱為Zp上線性秘密共享方案,如果滿足以下條件:

(1)每個參與者的秘密份額構(gòu)成Zp上的一個向量。

根據(jù)上述定義的線性秘密共享方案具有線性重構(gòu)性質(zhì)，其定義如下：設(shè)∏為訪問結(jié)構(gòu)上的線性秘密共享方案，S∈為授權(quán)集合，定義I={i,ρ(i)∈S}?{1,2,…,l}，如果{λi}是參與者ρ(i)根據(jù)∏關(guān)于s的有效秘密份額，則存在多項式時間算法計算得到常數(shù)向量{wi∈Zp,i∈I}，使得從而使得

定義3. DL[13](discrete logarithm)假設(shè)：已知G1是一個階為素數(shù)p的雙線性群，隨機選擇g∈G1,ξ∈Zp，對所有多項式算法A，下面的優(yōu)勢是可忽略的：

Pr[A(g,gξ)=ξ]

定義4. SXDH假設(shè)[18]：在群G1和G2上的DDH問題都是困難的，即不能有效計算同構(gòu)映射ψ:G2→G1及其逆ψ-1:G1→G2。

3 形式化定義與安全性定義

3.1 形式化定義

具有用戶和屬性匿名及追蹤功能的ABGS方案由以下6個多項式算法組成：

(a)Setup(1k)→(params,ik,okuser,tkatt)：輸入安全參數(shù)1k，輸出公共參數(shù)params，群密鑰ik，用戶打開密鑰okuser和屬性追蹤密鑰tkatt。

(b)UserKey(params,ik,Atti)→ski:輸入公共參數(shù)params，群密鑰ik，用戶屬性集Atti?Att。輸出用戶成員私鑰ski，最新的成員注冊表reg。

(c)Sign(params,ski,m,Υ)→σ：輸入公共參數(shù)params，用戶成員私鑰ski，消息m，訪問結(jié)構(gòu)Υ，輸出群簽名σ。

(d)Verify(params,m,Υ,σ)→0/1:輸入公共參數(shù)params，信息m，訪問策略Υ，群簽名σ，返回是否接受該簽名。

(e)OpenUser(params,okuser,m,reg,σ,Υ)→(i,Atti)/⊥：輸入公共參數(shù)params，用戶打開密鑰okuser，消息m，訪問結(jié)構(gòu)Υ，群簽名σ，群成員列表reg，返回身份i和用戶的屬性集Atti或者⊥。

(f)TraceAtt(params,tkatt,m,σ,Υ)→ζ/⊥：輸入公共參數(shù)params，屬性追蹤密鑰tkatt，信息m，訪問策略Υ，群簽名σ，返回簽名屬性集合ζ/⊥。

3.2 安全性定義

定義6. 正確性：當(dāng)滿足下列條件時，可認為該屬性群簽名方案是正確的：

對于所有的Setup(1k)→(params,ik,okuser,tkatt)，UserKey(params,ik,Atti)→ski,Υ,m∈{0,1}*，如果σ=Sign(params,ski,m,Υ)，則：

成立。

在以下定義中，對手可以運行協(xié)議:

(1)通過JoinP-oracle，這意味著它創(chuàng)建了一個不知道其私鑰的誠實用戶：將索引i添加到HU(誠實用戶)列表中。

(2)通過JoinA-oracle，這表示它將與群管理員交互以創(chuàng)建它控制的用戶：將索引i添加到CU(不誠實用戶)列表中。

當(dāng)對手被賦予群密鑰(群管理器已不誠實)時，對手不需要訪問JoinA-oracle，因為它可以自己模擬來創(chuàng)建不誠實用戶(不一定在CU)。創(chuàng)建用戶后，對手扮演不誠實用戶的角色，并可以與誠實的用戶交互，授予一些預(yù)言：

(1)corrupt(i)：如果i∈HU，則提供此用戶的特定私鑰。對手可以在整個模擬過程中對其進行控制。將i從HU轉(zhuǎn)移到CU中。

(2)sign(i,m,Υ)：如果i∈HU，作為誠實的用戶i將在簽名過程中使用訪問結(jié)構(gòu)Υ在消息m上生成簽名。

(3)openusr(m,σ,Υ)：如果(m,σ,Υ)是有效的，則返回簽名者的身份i和屬性集Atti。

(4)tratt(m,σ,Υ)：如果(m,σ,Υ)是有效的，則返回用于生成簽名的屬性集ζ。

定義7. 屬性匿名性：對于所有多項式時間算法A，A贏得以下游戲的概率是可以忽略不計的，則稱該方案具有屬性匿名性。

初始化：挑戰(zhàn)者C運行Setup(1k)→(params,ik,okuser,tkatt)，并將(params,ik,tkatt)發(fā)送給A。

第一步：A被賦予詢問joinP,corrupt,sign,tratt預(yù)言的權(quán)限。

挑戰(zhàn)：A輸出信息m*，訪問結(jié)構(gòu)Υ*，誠實用戶Ui(即i?CU)，則?ζi0,ζi1?Atti,Υ(ζi0)=1,Υ(ζi1)=1成立。C隨機選擇k∈R{0,1}，并響應(yīng)一個群簽名σ*←Sign(params,ski,ζik,m,Υ)。

第二步：A可以進行類似于第一步的查詢。但是A不能在任意時候?qū)進行corrupt查詢。

輸出：最后，A輸出k'，如果k=k'則獲勝。A的優(yōu)勢定義Advuser-anon(A)=|Pr(k=k')-1/2|。

因此不存在任何多項式時間攻擊者將群簽名聯(lián)系到用于生成它的一組屬性。

4 支持LSSS訪問結(jié)構(gòu)的屬性基群簽名方案

4.1 角色分類

系統(tǒng)共有5個角色：群管理員(group manager，GM)，用戶，驗證者，打開者(opener)以及屬性追蹤者(attribute tracer)

(a)群管理員：群管理員被認為是可以信任的，主要負責(zé)系統(tǒng)公共參數(shù)的生成，其次群管理通過群密鑰與群成員交互為其發(fā)布密鑰。

(b)用戶：用戶與GM進行交互，從而成為該群的成員，并且在滿足訪問策略的情況下代表該群進行簽名，并將簽名發(fā)送給驗證者。

(c)驗證者：在接收到群簽名后，驗證者可驗證此簽名的合法性，即是該群中的某一人簽署了此簽名，但不能確定具體的簽名者。

(d)打開者：當(dāng)發(fā)生用戶濫用其簽名權(quán)利時，打開者可以通過打開群簽名找到簽名者的身份和擁有屬性。

(e)屬性追蹤者：可以追蹤來自群簽名的簽名屬性集，該屬性集滿足訪問結(jié)構(gòu)。

4.2 方案具體構(gòu)造

(1)初始化Setup(1k)→(params,ik,okuser，tkatt)。

由群管理員執(zhí)行，具體步驟如下：

(a)生成階為q的循環(huán)群G1,G2和GT，雙線性映射e:G1×G2→GT，g1,g2分別是群G1,G2的生成元。

(d)選擇生成元h,u0,…,un∈G1，定義Water函數(shù)[16],:{0,1}m→G1,即對M={μ1,…,μm}∈{0,1}m，

最后生成公開參數(shù)params，群密鑰ik，用戶打開密鑰okuser和屬性跟蹤密鑰tkatt如下：

params=(q,G1,G2,e,g1,g2,Att,,h,u0,u1,…,um,Z,u,v)

ik=(S={sj}attj∈Att,α),okuser=α1,tkatt={Qj}attj∈Att

(2)用戶密鑰生成UserKey(params,ik,Atti)→ski。

用戶與群管理員交互執(zhí)行，用戶可通過公私鑰(upki,uski)和群管理員之間進行信息的交互。具體步驟如下：

(e)用戶檢驗e(Xi,1,g2)=e(Xi,2,g1)，驗證通過后，用戶擁有有效的成員證書(Ai,Xi,yi)和屬性證書{Ti,j}?attj∈Atti。

最后，用戶獲得私鑰ski={(Ai,Xi,yi),{Ti,j}?attj∈Atti,{sj}?attj∈Atti}，GM獲得最新的群成員列表reg。

(3)簽名Sign(params,ski,m,Υ)→σ。

由用戶執(zhí)行，具體步驟如下：

(e)對群元素進行承諾得到σi=(ρi),i={1,3,4},σ2=((1)(ρ2),(2)(ρ2))。

(f)計算NIWI Groth-Sahai證明[13]的承諾變量ρ1,ρ2,ρ3,ρ4滿足下列等式：

(1)

e(ρ4,Zρ3,2)=e(h,{Tk}k∈{1,n'})

(2)

(3)

e(ρ7,g2)=e(h,ρ6,2)×e(F(m),ρ8)

(4)

(5)

e(ρ3,1,g2)=e(g1,ρ3,2)

(6)

e(ρ6,1,g2)=e(g1,ρ6,2)

(7)

本方案通過簽名上Groth-Sahai零知識證明，證明了上述映射等式的有效性。等式1是確定簽名者具有通過用戶密鑰算法頒發(fā)的有效成員證書(即Ai格式正確)；等式2確定簽名者具有滿足訪問結(jié)構(gòu)Υ的屬性，并且證明了成員證書與屬性證書相關(guān)聯(lián)；等式3證明了ρ5正確(即用戶的身份ID正確)；等式4不需要任何承諾，因此可以直接驗證該簽名(ρ7,ρ8)是在密鑰ρ6下對M的有效簽名；等式5、6是確保可追蹤對手模型中需要的yi,Xi的正確性；等式7用于在不可陷害性對手模型中進行檢測。

(4)簽名驗證Verify(params,m,Υ,σ)→1/0。

由驗證者執(zhí)行，根據(jù)Groth-Sahai證明驗證所有的等式是否成立，若成立返回1則說明該簽名有效。若不成立則返回0表示不接受該簽名。

(5)打開OpenUser(params,okuser,σ,m,reg,Υ)→(i/Atti)/⊥。

由打開者(Opener)執(zhí)行，對于有效的群簽名，打開者只需在簽名σ中打開Ai的承諾，并在群成員列表reg中找到與Ai對應(yīng)的身份i和屬性Atti，否則輸出⊥。

(6)屬性追蹤TraceAtt(params,tkatt,m,σ,Atti,Υ)→ζ/⊥。

5 安全性分析與性能分析

5.1 安全性分析

文中方案具有屬性匿名性、用戶匿名性、可追蹤性、不可偽造性、屬性抗聯(lián)合攻擊性及屬性不可偽造性，但因篇幅，僅給出了屬性匿名性、可追蹤性證明，其他證明見完整版。

定理1：文中方案具有正確性。

證明：

此等式成立表示簽名者擁有通過密鑰生成算法頒發(fā)的有效成員證書；

e(h,{Tk}k∈{1,n'})

此等式成立表示簽名者擁有滿足訪問結(jié)構(gòu)的屬性證書；

此等式表示簽名者的身份是正確的；

e(hzF(m)r,g2)=e(hz,g2)×e(F(m)r,g2)=

e(h,ρ6,2)×e(F(m),ρ8)

此等式表示該簽名是在密鑰ρ6下對m的有效簽名；

對于誠實的用戶來說，根據(jù)零知識證明的完備性，擁有成員證書和屬性證書的誠實用戶始終可以生成一個有效的證明。通過以上分析，合法的簽名總是可以通過驗證，根據(jù)定義該方案滿足正確性定義。

定理2：文中方案在SXDH假設(shè)下具有屬性匿名性。

證明：該證明來自Groth-Sahai證明系統(tǒng)。也就是說屬性隱藏在ρ4中，且用Groth-Sahai證明技術(shù)承諾到σ4中。因此，在SXDH假設(shè)下，它是完全隱藏的。

定理3：如果存在偽造屬性簽名通過驗證的攻擊者A，那么就存在一個可以破壞DL和KEA假設(shè)的攻擊者B。

初始化：該ABGS方案初始化階段模擬器B生成系統(tǒng)參數(shù)params。B設(shè)置g1=g,h=g'，生成其余參數(shù)(ik,okuser,tkatt)。并將(params,ik,tkatt)給攻擊者A。

查詢：由于B知道所有的密鑰，它可以根據(jù)屬性不可偽造性的定義響應(yīng)攻擊者A產(chǎn)生的所有查詢。

5.2 性能分析

首先對本方案與現(xiàn)有屬性基群簽名方案進行功能上的比較，結(jié)果如表1所示。文獻[11-13]方案都是采用訪問樹結(jié)構(gòu)，訪問樹結(jié)構(gòu)因為要采用遞歸運算，因此計算效率較低。本方案在提供了細粒度訪問控制的同時支持LSSS訪問結(jié)構(gòu)，LSSS利用線性秘密分享方案的秘密可線性重組的性質(zhì)重構(gòu)秘密，且LSSS與訪問控制樹的表達性相當(dāng)。由于不需要遞歸運算，因此計算效率較高。文獻[11-12]不具備屬性匿名性和屬性可追蹤性，與文獻[11]方案的屬性可追蹤性相比，本方案不僅可以追蹤到簽名用戶的屬性集，并且還可以追蹤到用戶簽名屬性集，即該用戶簽名時符合訪問結(jié)構(gòu)的子屬性集合。

表1 方案功能比較

本方案與現(xiàn)有屬性基群簽名方案效率比較如表2所示。設(shè)n表示與簽名相關(guān)的屬性數(shù)，l表示用戶的屬性數(shù)。通過對比發(fā)現(xiàn)，文獻[11-12]的簽名大小和驗證計算開銷都與簽名屬性數(shù)相關(guān)，而文獻[13]和文中方案的簽名大小和計算開銷均為固定值，與屬性數(shù)無關(guān)。雖然文獻[13]和文中方案的簽名計算開銷復(fù)雜度相同，但文獻[13]的方案在簽名前需要構(gòu)建一個冗余訪問樹，并且其為滿足訪問樹可變，添加了冗余節(jié)點，增加了存儲開銷。而且在生成簽名時，需要使用拉格朗日插值法，因此簽名計算開銷要大于文中方案，但文中方案在驗證計算開銷和滿足簽名策略的屬性集合數(shù)相關(guān),因此驗證開銷大于文獻[13]方案。

表2 方案效率分析

6 結(jié)束語

文中實現(xiàn)了一種支持LSSS訪問結(jié)構(gòu)的屬性基的群簽名方案。該方案不僅降低了計算開銷，實現(xiàn)了屬性匿名性，并且在發(fā)生用戶濫用簽名權(quán)利時，不但可以追蹤到用戶的身份和屬性，還可以追蹤到用戶簽名屬性。方案的簽名長度和驗證計算開銷均和屬性數(shù)量無關(guān)，具有良好的通信和計算開銷。文中的構(gòu)造是基于雙線性對的，隨著量子計算機的到來，此類方案的安全性將受到威脅，而格密碼系統(tǒng)不僅可抵抗量子計算攻擊，安全性更高，因此在未來的工作中，將對格上基于LSSS訪問結(jié)構(gòu)的屬性基群簽名方案進行研究。