素數階群上基于非對稱對的身份基環(huán)簽名

侯紅霞，張明瑞，趙艷琦，董曉麗,3

（1.西安郵電大學網絡空間安全學院，陜西 西安 710121；2.陜西師范大學計算機科學學院，陜西 西安 710061；3.廣西密碼學與信息安全重點實驗室，廣西 桂林 541004）

1 引言

環(huán)簽名的概念是由Rivest 等[1]于2001 年提出的。在環(huán)簽名中，環(huán)中的任意成員都能代表整個環(huán)對消息進行簽名，簽名驗證者僅知道簽名來自環(huán)，但卻不能確定具體的簽名者。環(huán)簽名中沒有管理員，沒有環(huán)的建立和撤銷過程，因此真實的簽名者對于驗證者而言是無條件匿名的。

為了簡化傳統(tǒng)公鑰基礎設施中的證書管理問題，Shamir[2]于1984 年引入了身份基公鑰密碼體制。在身份基密碼體制中，用戶的公鑰可以是標識該用戶身份的任意二進制串，比如E-mail 地址等；對應的私鑰則是由一個可信任的私鑰生成中心（PKG,private key generator）根據該用戶的身份生成的。因此，PKG 不需要保存已發(fā)布的證書列表，每個用戶僅需保存系統(tǒng)參數而不需要保存其他用戶的公鑰證書。

身份基環(huán)簽名將身份基公鑰密碼體制和環(huán)簽名技術相融合，既實現了匿名性、不可偽造性，又避免了用戶證書的管理。作為實現匿名性的一個重要的密碼學原語，身份基環(huán)簽名在許多場合（如電子選舉、電子現金、區(qū)塊鏈技術、車聯網等[3-8]）中有重要的應用。

自從Zhang 等[9]正式給出身份基環(huán)簽名的概念后，許多身份基環(huán)簽名方案及其變種被相繼提出[10-16]。然而，這些方案的安全性都是在隨機預言機模型下證明的。在隨機預言機模型中，哈希函數被作為一個完全隨機的理想化模型，這是一個非常強的假設。已有文獻[17]表明，在隨機預言機模型下被證明安全的方案在實際應用中可能并不安全。因此，設計標準模型下可證明安全的身份基環(huán)簽名方案更具實際意義。2006 年，Au 等[18]在標準模型下提出了2 個身份基環(huán)簽名方案，但遺憾的是，這2 個方案后來被證明并不能滿足環(huán)簽名的安全需求。此后，有許多工作致力于構造標準模型下高效安全的身份基環(huán)簽名方案。文獻[19-20]從節(jié)約通信成本和提高計算效率的角度出發(fā)，分別在標準模型下提出了改進的身份基環(huán)簽名方案，但遺憾的是，這2 個方案之后被證明不安全。2012 年，文獻[21]給出了一個標準模型下具有固定簽名長度的身份基環(huán)簽名方案，但該方案被指出有漏洞。2013 年，通過分析分層身份基加密方案與身份基環(huán)簽名方案之間的聯系，Au 等[22]在標準模型下提出了一個身份基環(huán)簽名方案。2018 年，基于Au 等[22]方案，趙艷琦等[23]在標準模型下構造了一個新的身份基環(huán)簽名方案。方案[22-23]在安全性證明時都采用了對偶系統(tǒng)加密技術，從而在標準模型下都達到了全安全性和完全匿名性。對偶系統(tǒng)加密技術為安全性歸約證明開辟了一條新思路。然而，這2 個方案都是在合數階雙線性群上構造的，因而實現效率都很低。已有文獻[24]指出，階數n為160 bit 的素數階群具有與階數n為1 024 bit 的合數階群同樣的安全水平，合數階群上的雙線性對運算要比素數階群上的對運算慢許多。因此，在素數階群上設計高效安全的環(huán)簽名方案具有重要的實際意義。文獻[22]也將此作為一個公開問題提出。

Ramanna 等[25]在非對稱雙線性對環(huán)境中提出了一些Waters 對偶系統(tǒng)原語[26]的變形機制。許多研究結果[27-29]已表明，相比于對稱雙線性對運算，非對稱雙線性對運算更加快速和緊致。基于文獻[22-23,25]的工作，本文給出了一種在素數階群上構造身份基環(huán)簽名方案的方法。在素數階群上基于非對稱雙線性對構造了一個高效的身份基環(huán)簽名方案。該方案可以抵抗適應性選擇身份攻擊和適應性選擇消息攻擊。通過采用對偶系統(tǒng)加密技術，該方案的安全性被歸約到素數階群上非對稱對環(huán)境中的3 個困難性假設。實驗結果表明，與已有的基于對偶系統(tǒng)的身份基環(huán)簽名方案相比較，本文方案在效率方面更具優(yōu)勢。

2 預備知識

2.1 符號說明

本文中，κ表示安全參數，negl(κ)表示一個關于κ的可忽略函數，表示x均勻隨機地取自集合X，|R|表示集合R的基，[n] 表示集合{1,2,…,n}，ε表示一個可忽略的參數。

2.2 非對稱雙線性對

令(G1,G2,GT)分別是3 個階為素數p的循環(huán)群，其中和分別表示由P1和P2生成的加法群，GT是乘法群。

雙線性對e:G1×G2→GT是滿足以下性質的映射。

1) 雙線性。對于P1,Q1∈G1和P2,Q2∈G2，有

2) 非退化性。e(P1,P2)≠1∈GT。

3) 有效可計算性。對于任意的P∈G1和Q∈G2，存在一個有效的算法計算e(P,Q)。

當G1=G2時，雙線性映射被稱為對稱或類型1 雙線性映射，否則被稱為非對稱雙線性映射。非對稱雙線性映射進一步可分為類型2 和類型3非對稱雙線性映射。類型2 非對稱雙線性映射是指由G1到G2或由G2到G1存在一個有效的可計算同構，而類型3 非對稱雙線性映射則不存在這樣的同構。對于S1∈G1和S2∈G2，文中用S1～S2表示S1（以P1為底）和S2（以P2為底）具有相同的離散對數。

2.3 復雜性假設

判定性 Diffie-Hellman（DDH,decision Diffie-Hellman）假設[25]。令P1,P2分別是群G1,G2的隨機生成元，x1,x2,

G1中的DDH 問題（記為DDH1）是指給定(P1,x1P1,x2P1,P2,Z1=(x1x2+c)P1)，判定c=0還是

令B是一個輸出為0 或1 的多項式時間（PPT,probabilistic polynomial time）算法。定義B解決DDH1 問題的優(yōu)勢為

如果對于任意敵手B，其運行時間至多為t，解決 DDH1 問題的優(yōu)勢為≤ε，則稱(ε,t)-DDH1假設成立。

G2中的DDH 假設（記為DDH2）定義類似。

DDH2v 假設[25]。令P1,P2分別是群G1,G2的隨機生成元，

DDH2v 問題是指給定(P1,dP1,dzP1,zx1P1,P2,dP2,x1P2,x2P2,Z2=(x1x2+c)P2)，判定c=0還是

令B是一個輸出為0 或1 的PPT 算法。定義B解決DDH2v 問題的優(yōu)勢為

如果對于任意敵手B，其運行時間至多為t，解決DDH2v 問題的優(yōu)勢為≤ε，則稱(ε,t)-DDH2v 假設成立。

判定性雙線性Diffie-Hellman（DBDH,decision bilinear Diffie-Hellman）假設[25]。令P1,P2分別是群G1,G2的隨機生成元，

DBDH 問題是指給定(P1,x1P1,x2P1,x3P1,P2,，判定還是

令B是一個輸出為0 或1 的PPT 算法。定義B解決DBDH 問題的優(yōu)勢為

如果對于任意敵手B，其運行時間至多為t，解決 DBDH 問題的優(yōu)勢為，則稱(ε,t)-DBDH 假設成立。

2.4 安全模型

定義1一個(1,n) 身份基環(huán)簽名方案由以下4 個PPT 算法組成。

Setup。該算法由PKG 運行，輸入一個安全參數κ，輸出主密鑰MSK 和系統(tǒng)公開參數Params。

Extract。對于身份ID，該算法輸入主密鑰MSK，輸出身份ID 所對應的私鑰SKID。

Sign。輸入系統(tǒng)公開參數Params、身份集Ring={ID1,…,IDn]、消息m以及用戶私鑰{SKID|ID ∈Ring}，輸出一個(1,n) 身份基環(huán)簽名σ。

Verify。輸入系統(tǒng)公開參數Params、n個用戶的身份集Ring={ID1,…,IDn}、消息m以及環(huán)簽名σ，輸出Valid 或Invalid。

一個安全的(1,n) 身份基環(huán)簽名方案應滿足不可偽造性和匿名性。

定義2不可偽造性。如果沒有多項式時間敵手能以不可忽略的優(yōu)勢贏得以下游戲，一個(1,n)身份基環(huán)簽名方案在適應性選擇消息攻擊和適應性選擇身份攻擊下是不可偽造的。

該游戲在敵手A與挑戰(zhàn)者C之間進行。

1) 輸入安全參數κ，挑戰(zhàn)者C運行Setup 算法，然后將系統(tǒng)公開參數Params 發(fā)送給敵手A。

2) 通過訪問下述預言機，敵手A在多項式時間內適應性地向挑戰(zhàn)者C發(fā)起以下詢問。

密鑰提取預言機（EO,extraction oracle）：輸入身份ID，SKID←Extract(params,ID)被返回給敵手A。

簽名預言機（SO,signing oracle）：敵手A選取一個身份集Ring={ID1,…,IDn}和消息m，簽名預言機會返回一個有效的(1,n) 身份基環(huán)簽名σ給A。此過程中，簽名預言機可以詢問密鑰提取預言機。

3) 最后，A輸出(Ring*,m*,σ*)，且(Ring*,m*)沒有在之前的簽名詢問中出現過，同時對于環(huán)Ring*中的任意身份ID ∈Ring*，不允許A做密鑰提取詢問。

如果Verify(Ring*,m*,σ*)的輸出結果為Valid，則A贏得該游戲。定義敵手A的獲勝優(yōu)勢為

定義3匿名性。當且僅當以下條件被滿足，一個(1,n)身份基環(huán)簽名方案是無條件匿名的。

給定任意身份集Ring={ID1,…,IDn}，消息m以及環(huán)簽名σ，即使以無限的計算能力，任意敵手都不能以優(yōu)于隨機猜測的概率識別出真實的簽名者。換句話說，敵手A僅能以不高于的概率輸出真實簽名者的身份。

2.5 敵手模型

存在2 種類型的簽名和密鑰：正常類型，記為type-N；半功能類型，記為type-S。type-S 類型的簽名和密鑰僅在安全性證明中使用，并不會出現在真實的簽名方案中。

根據簽名的類型可將敵手劃分為2 種類型。

type-S 偽造者：如果敵手為type-S，這種情況下，模擬器僅輸出type-N 簽名和密鑰。

type-N 偽造者：如果敵手為type-N，這種情況下，模擬器需要使用game-hopping 技術在敵手未察覺的情況下將簽名和密鑰逐步由type-N 轉變?yōu)閠ype-S。

3 基于非對稱對的身份基環(huán)簽名方案

3.1 方案構造

Setup。令e:G1×G2→GT是一個類型3 非對稱雙線性映射，其中G1=P1和G2=P2都是階為素數p的加法群。隨機選取參數，使V2=vP2，，τP2=V2+（τ=v+av′）。H0:{0,1}*→Zp，H1:{0,1}*×{0,1}*→Zp是2 個抗碰撞哈希函數。PKG 隨機選取α∈Zp，Q1,W1,U1∈G1，Q2,W2,U2∈G2且Q1～Q2，W1～W2，U1～U2。系統(tǒng)主密鑰為MSK=αP2，系統(tǒng)公開參數為Params={P1,aP1,τP1,Q1,W1,U1,e(P1,P2)α,H0,H1}。

Extract。為了生成身份ID ∈{0,1}?的用戶私鑰，該算法隨機選取和標簽計算

算法輸出SKID=(AID,BID,CID,DID)作為身份ID 的用戶私鑰，并秘密發(fā)送SKID和{ktagID,P2,V2,Q2,W2,U2}給用戶ID。

Sign。令環(huán)Ring={ID1,…,IDn}為包含n個身份的身份集。假設環(huán)Ring 中的一個用戶ID，不失一般性，假設ID 是環(huán)Ring 的第π個用戶（π∈[n]），即IDπ=ID。為了生成消息m∈{0,1}*的環(huán)簽名，該算法分別計算idi=H0(IDi)（i∈[n]）以及M=H1(m,Ring)，然后執(zhí)行以下步驟。

1) 隨機選取λi,ri（i∈[n]，令ktagπ=ktagID）使其滿足限制和

2) 對于i∈[n]，有以下結論成立。

當i≠π時，有

當i=π時，有

3) 輸出簽名σ=

Verify。在收到消息m的環(huán)簽名σ={Ai,Bi,Ci,Di,后，驗證者先計算idi=H0(IDi)（i∈[n]）和M=H1(m,Ring)；然后隨機選取s,ctag1,…,（其 中 ctagi≠ktagi,i∈[n]）并計算T1=sP1,T2=asP1,T3=-sτ P1+sW1,T4,i=s(idiQ1+ctagiW1+U1)；最后驗證者檢驗式(1)是否成立。

3.2 正確性

方案的正確性成立，是因為

4 安全性證明

本文方案的安全性采用對偶系統(tǒng)加密技術進行證明，為此需定義2 個額外的結構，即半功能密鑰和半功能簽名，半功能密鑰和半功能簽名不會出現在真實的簽名方案中，僅用于方案的安全性證明。

半功能密鑰。若身份ID 的正常密鑰為SKID=，則其半功能密鑰被設置為DID=)，其中

半功能簽名。對于環(huán)Ring={ID1,…,IDπ,IDn}，若簽名算法輸出的正常簽名為σ′=，則其半功能簽名σ設置為，其余元素與σ′中的元素相同，即

定理1若假設DDH1、DDH2v 和DBDH 成立，則3.1 節(jié)所構造的方案是不可偽造的。

證明為了證明本文方案在 type-S 偽造者和type-N 攻擊下是不可偽造的，考慮下面2 種情況。

情況1若敵手A能輸出一個type-S 的偽造，則可構造一個能利用敵手A的能力攻破假設DDH1 的模擬器B。

換句話說，模擬器B的目的是在收到一個DDH1 實例(P1,sP1,aP1,P2,Z1=(as+c)P1)后，判定c是否等于0。為此，模擬器B與敵手A執(zhí)行以下游戲。

系統(tǒng)建立模擬器B隨機選取α,yv,yv′,yq,，并設置參數

這里相當于隱式地令τ=yv+ayv′，則。接著模擬器B利用α計算其余參數，然后選取2 個哈希函數H0,H1，發(fā)送系統(tǒng)公開參數給敵手A

詢問由于模擬器B知道系統(tǒng)主密鑰，因此能正確回答所有來自敵手A的密鑰詢問。

偽造當敵手A輸出一個關于環(huán)Ring 和消息m的偽造環(huán)簽名后，模擬器B首先計算M=H1(m,Ring)，idi=H0(IDi)（i∈[n]），然后隨機選取s′,ctag1,…,，（其中ctagi≠ktagi，i∈[n]），計算T1=s′P1，T2=s′aP1，T3=-s′τP1+s′W,T4,i=s′(idiQ1+ctagiW1+U1)，于是有

因為敵手A輸出的是一個type-S 偽造，所以一定存在π，使。利用這一點，模擬器B便可判定c是否等于0，具體如下。

模擬器B可設置T1=sP1，T2=Z1，+yu)(sP1)，然后驗證式(3)是否成立。

如果c=0，則式(3)成立；否則，式(3)不成立，因為會有額外的一項e(P1,P2)γc≠ 1。

情況2這部分證明中，假設敵手A的偽造為type-N。進一步，假設敵手A共做了L次密鑰提取詢問和簽名詢問。該部分證明是通過一系列游戲的game-hopping 技術來完成的，這一系列游戲記為Game0,Game1,…,GameL。

Game0：真實的不可偽造性游戲。

Gamek：對于每個k∈[L]，游戲Gamek如同Game0，除了返回給敵手A的第k個密鑰和簽名為type-S。

對于每個k∈[L]，Gamek-1與Gamek的不可區(qū)分性可歸約到DDH2v 困難性假設上。

換句話說，模擬器B的目的是在收到一個DDH2v 實例(P1,dP1,dzP1,zx1P1,P2,dP2,x1P2,x2P2,Z2=(x1x2+c)P2)后，判定c是否等于0。為此，模擬器B與敵手A執(zhí)行以下游戲。

系統(tǒng)建立模擬器B隨機選取a,α,μ,ξ,，并設置參數Q2=-μ(dP2)+yqP2,U2=-ξ(dP2)+yuP2,W2=(dP2)+ywP2,Q1=-μ(dP1)+yqP1,U1=-ξ(dP1)+yuP1,W1=(dP1)+ywP1,V2=-a(x1P2)，

令τ=，則τP1=ayv′P1。同樣，Q1,W1,U1也可由dP1類似地計算而得。其余的公開參數以及困難問題中的其他元素均可由a和α計算得到，然后模擬器B選取2 個哈希函數H0,H1，將以下公開參數發(fā)送給敵手A

詢問對于第j次詢問，模擬器B需根據j∈[L]的值給敵手返回type-S 或type-N 的密鑰或簽名。

如果j＞k，則模擬器B利用主密鑰和秘密參數生成一個type-N 的密鑰或簽名。

如果j＜k且第j次詢問是針對身份ID 的一個密鑰提取詢問，則模擬器B首先生成一個正常密鑰然后隨機選取計算得到一個半功能密鑰

如果j＜k且第j次詢問是針對環(huán)Ring=和消息m的一個簽名詢問，則模擬器B首先生成一個正常簽名，然后隨機選取計算得到一個半功能簽名如下。

對于i∈[n]，有以下結論成立。

當i≠π時，有

當i=π時，有

如果j=k且第j次詢問是針對身份ID 的一個密鑰提取詢問，則模擬器B首先生成一個正常密鑰，并令ktagID=μid+ξ（其中id=H0(ID)），然后計算身份ID 的私鑰

這里隱式地設置r=r′+x2。如果Z2=x1x2P2，則身份ID 的私鑰是正常密鑰，否則Z2=(x1x2+c)P2，身份ID 的私鑰就是一個γ=c的半功能密鑰。

如果j=k且第j次詢問是針對環(huán)Ring={ID1,…,IDn}和消息m的一個簽名詢問，則模擬器B首先利用主密鑰生成一個正常密鑰(π∈[n])，選取滿足和限制的隨機數λi,，選?。ㄆ渲衖∈{1,…,π-1,π+1,…,n}），ktagπ=μidπ+ξ。然后模擬器B回答第j次簽名詢問如下。

對于i∈[n]，有以下結論成立。

當i≠π時，有

當i=π時，有

在上述模擬過程中，如果c=0，則模擬器B與敵手A執(zhí)行游戲Gamek-1；否則，執(zhí)行游戲Gamek。如果敵手A在這2 個游戲中獲勝的概率有差異，則模擬器B利用這點差異就可以解決DDH2v 問題。然而，如果敵手A的偽造由type-N轉變?yōu)閠ype-S，A在這2 個游戲中獲勝的概率有可能保持不變。因此，模擬器B不得不檢測A輸出的偽造是否仍然是type-N。為此，B隨機選取，對于每一個i∈[n]，設置ctagi=μidi+ξ，并計算

這里隱式地設置s=s′+zx1。然后B驗證式(5)是否成立。

如果偽造為type-N，則式(5)成立；否則，式(5)不成立，因為會產生額外的一項e(P1,P2)dzγ。

因此，如果敵手A能夠區(qū)分Gamek-1和Gamek，模擬器B就能利用敵手A的能力攻破DDH2v 假設。

最后，本文證明如果敵手A在游戲GameL中輸出一個type-N 的偽造，模擬器B就能利用敵手A的能力攻破DBDH 假設。

這里需要注意的是，由于B并不知道α，因此僅能生成半功能密鑰給A。

簽名詢問為了回答簽名詢問，模擬器B首先利用米主要生成簽名者IDπ的一個半功能密鑰，選取滿足和限制的隨機數λi,ri,，然后回答簽名詢問如下。

對于i∈[n]，有以下結論成立。

當i≠π時，有

當i=π時，有

最終得到一個type-S 的簽名。

這里，模擬器B隱式地設置δ′=δ+as，其中。然后B通過檢驗e(P1,P2)αs=Z3是否成立攻破DBDH 假設。

定理2匿名性。3.1 節(jié)給出的環(huán)簽名方案是無條件匿名的。

證明簽名中，由于是由真實簽名者隨機生成的，因此{Ai,Bi,Ci,Di,ktagi}(i∈[n]{π])是均勻分布的。另一方面，由于αP2是主密鑰，r和ktagπ是由PKG隨機生成的，與真實簽名者無關，因此{Aπ,Bπ,Cπ,Dπ,ktagπ]也是均勻分布的。因此，整個簽名過程中，有關真實簽名者的信息沒有被泄露。敵手想要通過簽名確定真實簽名者身份的概率不會優(yōu)于從環(huán)Ring={ID1,…,IDn}中隨機猜測真實簽名者身份的概率。故3.1 節(jié)給出的環(huán)簽名方案是無條件匿名的。

5 性能比較

本節(jié)將本文方案與已有的基于對偶系統(tǒng)的身份基環(huán)簽名方案[22-23]進行性能比較。

為了比較方案在各個階段的運行效率，本文使用Java 語言編程實現3 個方案，通過調用JPBC 密碼庫實現相關的密碼運算，基于PC 端開發(fā)，主要運行環(huán)境如下。中央處理器：AMD Ryzen 7-4800H；內存：16 GB；硬盤：240 GB；操作系統(tǒng)：Windows 10 專業(yè)版。

圖1～圖4 是本文方案與文獻[22-23]中各算法運行時間的對比曲線。由圖1～圖4 可以看出，由于本文方案在素數階群上構造，因此在效率方面具有很大優(yōu)勢。

圖1 各方案Setup 算法的性能比較

圖2 各方案Extract 算法的性能比較

圖3 各方案Sign 算法的性能比較

圖4 各方案Verify 算法的性能比較

表1 列出了當環(huán)大小為n=150時3 個方案中各個算法的操作時間，相較于文獻[22-23]方案，本文方案中各算法運行時間更短，這主要是因為文獻[22-23]方案是基于合數階群上的對稱對構造的，而本文方案是基于素數階群上的非對稱對構造的。對運算是各個算法中最耗時的運算，而合數階群上的對運算要比素數階群上的對運算慢許多。相比于對稱對，非對稱對在實現時也更快更緊致。

表1 環(huán)大小為n=150 時的計算效率比較

6 結束語

環(huán)簽名中，環(huán)中任意成員都能以一種完全匿名的方式對消息進行簽名。這一性質被稱為環(huán)簽名的無條件匿名性，可用于保護簽名者的隱私。因在隱私保護等方面的重要應用，身份基環(huán)簽名已成為一個熱門的研究方向。然而，大多數已有的身份基環(huán)簽名方案的安全性證明不是基于隨機預言機模型就是使用了公共參考串模型。本文提出了一個基于素數階群上非對稱對的身份基環(huán)簽名方案。基于對偶系統(tǒng)加密技術，該方案被證明在標準模型下是不可偽造和無條件匿名的。與文獻[22-23]方案相比，本文方案更高效。然而，本文方案中簽名大小仍然會隨著環(huán)成員個數的增長而呈線性增長。因此，在素數階群上基于對偶系統(tǒng)加密技術構造標準模型下，可證明安全的具有常量大小的身份基環(huán)簽名方案是筆者今后研究的主要方向。