支持LSSS訪問結構的屬性基群簽名方案的研究

許玉嵐，陳燕俐，高詩堯

(南京郵電大學 計算機學院、軟件學院、網絡空間安全學院，江蘇 南京 210003)

0 引 言

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

1 相關工作

1.1 群簽名

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

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

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

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

1.2 屬性基群簽名

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

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

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

1.3 文中貢獻

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

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

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

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

2 預備知識

定義1. 雙線性映射(bilinear maps)[3]：設G1,G2,GT是階為素數p的乘法循環群,g1,g2分別是G1,G2的生成元，存在一個具有如下性質的雙線性映射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映射：同構映射ψ:G2→G1及其逆ψ-1:G1→G2都不能有效計算。

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

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

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

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

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

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

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

3.1 形式化定義

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

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

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

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

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

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

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

3.2 安全性定義

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

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

成立。

在以下定義中，對手可以運行協議:

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

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

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

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

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

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

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

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

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

第一步：A被賦予詢問joinP,corrupt,sign,tratt預言的權限。

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

第二步：A可以進行類似于第一步的查詢。但是A不能在任意時候對i進行corrupt查詢。

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

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

4 支持LSSS訪問結構的屬性基群簽名方案

4.1 角色分類

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

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

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

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

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

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

4.2 方案具體構造

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

由群管理員執行，具體步驟如下：

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

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

最后生成公開參數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。

用戶與群管理員交互執行，用戶可通過公私鑰(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,Υ)→σ。

由用戶執行，具體步驟如下：

(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是確定簽名者具有通過用戶密鑰算法頒發的有效成員證書(即Ai格式正確)；等式2確定簽名者具有滿足訪問結構Υ的屬性，并且證明了成員證書與屬性證書相關聯；等式3證明了ρ5正確(即用戶的身份ID正確)；等式4不需要任何承諾，因此可以直接驗證該簽名(ρ7,ρ8)是在密鑰ρ6下對M的有效簽名；等式5、6是確?？勺粉檶κ帜Ｐ椭行枰膟i,Xi的正確性；等式7用于在不可陷害性對手模型中進行檢測。

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

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

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

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

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

5 安全性分析與性能分析

5.1 安全性分析

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

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

證明：

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

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

此等式成立表示簽名者擁有滿足訪問結構的屬性證書；

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

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

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

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

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

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

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

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

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

查詢：由于B知道所有的密鑰，它可以根據屬性不可偽造性的定義響應攻擊者A產生的所有查詢。

5.2 性能分析

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

表1 方案功能比較

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

表2 方案效率分析

6 結束語

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