素?cái)?shù)階群上基于非對(duì)稱(chēng)對(duì)的身份基環(huán)簽名

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

（1.西安郵電大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，陜西 西安 710121；2.陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710061；3.廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004）

1 引言

環(huán)簽名的概念是由Rivest 等[1]于2001 年提出的。在環(huán)簽名中，環(huán)中的任意成員都能代表整個(gè)環(huán)對(duì)消息進(jìn)行簽名，簽名驗(yàn)證者僅知道簽名來(lái)自環(huán)，但卻不能確定具體的簽名者。環(huán)簽名中沒(méi)有管理員，沒(méi)有環(huán)的建立和撤銷(xiāo)過(guò)程，因此真實(shí)的簽名者對(duì)于驗(yàn)證者而言是無(wú)條件匿名的。

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

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

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

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

2 預(yù)備知識(shí)

2.1 符號(hào)說(shuō)明

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

2.2 非對(duì)稱(chēng)雙線性對(duì)

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

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

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

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

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

當(dāng)G1=G2時(shí)，雙線性映射被稱(chēng)為對(duì)稱(chēng)或類(lèi)型1 雙線性映射，否則被稱(chēng)為非對(duì)稱(chēng)雙線性映射。非對(duì)稱(chēng)雙線性映射進(jìn)一步可分為類(lèi)型2 和類(lèi)型3非對(duì)稱(chēng)雙線性映射。類(lèi)型2 非對(duì)稱(chēng)雙線性映射是指由G1到G2或由G2到G1存在一個(gè)有效的可計(jì)算同構(gòu)，而類(lèi)型3 非對(duì)稱(chēng)雙線性映射則不存在這樣的同構(gòu)。對(duì)于S1∈G1和S2∈G2，文中用S1～S2表示S1（以P1為底）和S2（以P2為底）具有相同的離散對(duì)數(shù)。

2.3 復(fù)雜性假設(shè)

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

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

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

如果對(duì)于任意敵手B，其運(yùn)行時(shí)間至多為t，解決 DDH1 問(wèn)題的優(yōu)勢(shì)為≤ε，則稱(chēng)(ε,t)-DDH1假設(shè)成立。

G2中的DDH 假設(shè)（記為DDH2）定義類(lèi)似。

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

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

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

如果對(duì)于任意敵手B，其運(yùn)行時(shí)間至多為t，解決DDH2v 問(wèn)題的優(yōu)勢(shì)為≤ε，則稱(chēng)(ε,t)-DDH2v 假設(shè)成立。

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

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

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

如果對(duì)于任意敵手B，其運(yùn)行時(shí)間至多為t，解決 DBDH 問(wèn)題的優(yōu)勢(shì)為，則稱(chēng)(ε,t)-DBDH 假設(shè)成立。

2.4 安全模型

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

Setup。該算法由PKG 運(yùn)行，輸入一個(gè)安全參數(shù)κ，輸出主密鑰MSK 和系統(tǒng)公開(kāi)參數(shù)Params。

Extract。對(duì)于身份ID，該算法輸入主密鑰MSK，輸出身份ID 所對(duì)應(yīng)的私鑰SKID。

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

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

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

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

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

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

2) 通過(guò)訪問(wèn)下述預(yù)言機(jī)，敵手A在多項(xiàng)式時(shí)間內(nèi)適應(yīng)性地向挑戰(zhàn)者C發(fā)起以下詢(xún)問(wèn)。

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

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

3) 最后，A輸出(Ring*,m*,σ*)，且(Ring*,m*)沒(méi)有在之前的簽名詢(xún)問(wèn)中出現(xiàn)過(guò)，同時(shí)對(duì)于環(huán)Ring*中的任意身份ID ∈Ring*，不允許A做密鑰提取詢(xún)問(wèn)。

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

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

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

2.5 敵手模型

存在2 種類(lèi)型的簽名和密鑰：正常類(lèi)型，記為type-N；半功能類(lèi)型，記為type-S。type-S 類(lèi)型的簽名和密鑰僅在安全性證明中使用，并不會(huì)出現(xiàn)在真實(shí)的簽名方案中。

根據(jù)簽名的類(lèi)型可將敵手劃分為2 種類(lèi)型。

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

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

3 基于非對(duì)稱(chēng)對(duì)的身份基環(huán)簽名方案

3.1 方案構(gòu)造

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

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

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

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

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

2) 對(duì)于i∈[n]，有以下結(jié)論成立。

當(dāng)i≠π時(shí)，有

當(dāng)i=π時(shí)，有

3) 輸出簽名σ=

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

3.2 正確性

方案的正確性成立，是因?yàn)?/p>

4 安全性證明

本文方案的安全性采用對(duì)偶系統(tǒng)加密技術(shù)進(jìn)行證明，為此需定義2 個(gè)額外的結(jié)構(gòu)，即半功能密鑰和半功能簽名，半功能密鑰和半功能簽名不會(huì)出現(xiàn)在真實(shí)的簽名方案中，僅用于方案的安全性證明。

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

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

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

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

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

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

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

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

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

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

因?yàn)閿呈諥輸出的是一個(gè)type-S 偽造，所以一定存在π，使。利用這一點(diǎn)，模擬器B便可判定c是否等于0，具體如下。

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

如果c=0，則式(3)成立；否則，式(3)不成立，因?yàn)闀?huì)有額外的一項(xiàng)e(P1,P2)γc≠ 1。

情況2這部分證明中，假設(shè)敵手A的偽造為type-N。進(jìn)一步，假設(shè)敵手A共做了L次密鑰提取詢(xún)問(wèn)和簽名詢(xún)問(wèn)。該部分證明是通過(guò)一系列游戲的game-hopping 技術(shù)來(lái)完成的，這一系列游戲記為Game0,Game1,…,GameL。

Game0：真實(shí)的不可偽造性游戲。

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

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

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

系統(tǒng)建立模擬器B隨機(jī)選取a,α,μ,ξ,，并設(shè)置參數(shù)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類(lèi)似地計(jì)算而得。其余的公開(kāi)參數(shù)以及困難問(wèn)題中的其他元素均可由a和α計(jì)算得到，然后模擬器B選取2 個(gè)哈希函數(shù)H0,H1，將以下公開(kāi)參數(shù)發(fā)送給敵手A

詢(xún)問(wèn)對(duì)于第j次詢(xún)問(wèn)，模擬器B需根據(jù)j∈[L]的值給敵手返回type-S 或type-N 的密鑰或簽名。

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

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

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

對(duì)于i∈[n]，有以下結(jié)論成立。

當(dāng)i≠π時(shí)，有

當(dāng)i=π時(shí)，有

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

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

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

對(duì)于i∈[n]，有以下結(jié)論成立。

當(dāng)i≠π時(shí)，有

當(dāng)i=π時(shí)，有

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

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

如果偽造為type-N，則式(5)成立；否則，式(5)不成立，因?yàn)闀?huì)產(chǎn)生額外的一項(xiàng)e(P1,P2)dzγ。

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

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

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

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

對(duì)于i∈[n]，有以下結(jié)論成立。

當(dāng)i≠π時(shí)，有

當(dāng)i=π時(shí)，有

最終得到一個(gè)type-S 的簽名。

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

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

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

5 性能比較

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

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

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

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

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

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

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

表1 列出了當(dāng)環(huán)大小為n=150時(shí)3 個(gè)方案中各個(gè)算法的操作時(shí)間，相較于文獻(xiàn)[22-23]方案，本文方案中各算法運(yùn)行時(shí)間更短，這主要是因?yàn)槲墨I(xiàn)[22-23]方案是基于合數(shù)階群上的對(duì)稱(chēng)對(duì)構(gòu)造的，而本文方案是基于素?cái)?shù)階群上的非對(duì)稱(chēng)對(duì)構(gòu)造的。對(duì)運(yùn)算是各個(gè)算法中最耗時(shí)的運(yùn)算，而合數(shù)階群上的對(duì)運(yùn)算要比素?cái)?shù)階群上的對(duì)運(yùn)算慢許多。相比于對(duì)稱(chēng)對(duì)，非對(duì)稱(chēng)對(duì)在實(shí)現(xiàn)時(shí)也更快更緊致。

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

6 結(jié)束語(yǔ)

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