安浩楊 何德彪 包子健 彭 聰 羅 敏

（武漢大學(xué)國家網(wǎng)絡(luò)安全學(xué)院 武漢 430072）

（haoyangan@whu.edu.cn）

區(qū)塊鏈[1]是一種去中心化的分布式賬本技術(shù)，具有不可篡改、去中心化和公開透明等特點.隨著區(qū)塊鏈技術(shù)的應(yīng)用與發(fā)展，數(shù)字身份和交易數(shù)據(jù)的重要性日益增加，同時也帶來了更多隱私泄露的風(fēng)險.環(huán)簽名概念最初由Rivest 等人[2]提出，它允許一個實體代表一個潛在的簽名者群體（稱為環(huán)）簽署消息，同時在環(huán)中保持匿名性.與群簽名相比，環(huán)簽名被認(rèn)為是簡化的群簽名[3].環(huán)簽名不需要群管理員和其他環(huán)成員的合作或批準(zhǔn)，可以實現(xiàn)自組織的匿名認(rèn)證.環(huán)簽名在區(qū)塊鏈隱私保護(hù)、匿名憑證、車輛自組織網(wǎng)絡(luò)等方面都有許多應(yīng)用.門羅幣[4]使用了可鏈接環(huán)簽名[5]技術(shù)實現(xiàn)了交易方身份隱私保護(hù).Bünz 等人[6]結(jié)合了環(huán)簽名技術(shù)，提出了一種基于賬戶模型的區(qū)塊鏈隱私保護(hù)方案Zether.

然而，文獻(xiàn)[2-6]的方案基于公鑰基礎(chǔ)設(shè)施體系（public key infrastructure,PKI），用戶公鑰需要由可信證書頒發(fā)機構(gòu)（certificate authority,CA）簽署的證書進(jìn)行認(rèn)證.在該體系中，證書的管理包括證書的吊銷、存儲、分發(fā)和驗證，代價是較高的.為解決該問題，Adi[7]在1984 年提出了基于身份的公鑰密碼學(xué)（identitybased public key cryptography,ID-PKC）.ID-PKC 允許用戶公鑰是任何能夠唯一標(biāo)識用戶的字符串（例如電子郵件地址），從而消除了證書的需要.同時，引入了一個完全可信的密鑰生成中心，根據(jù)用戶的身份標(biāo)識生成并發(fā)放用戶私鑰.已有科研人員提出了基于身份的數(shù)字簽名方案[8-10].

SM9 數(shù)字簽名算法[11]是由中國國家密碼管理局于2016 年發(fā)布，并于2018 年納入國際標(biāo)準(zhǔn)的基于身份的密碼算法.SM9 數(shù)字簽名算法采用了非對稱雙線性對技術(shù)，具有可證明的安全性和高效性[12]，適用于各種需要身份認(rèn)證和通信安全的場景，例如區(qū)塊鏈、電子現(xiàn)金、電子投票等.隨著區(qū)塊鏈系統(tǒng)國產(chǎn)化的應(yīng)用需求不斷增加，現(xiàn)有的國密算法已不能滿足日益復(fù)雜的區(qū)塊鏈應(yīng)用需求.已有科研人員提出了基于SM9 標(biāo)識密碼算法的功能型密碼算法[13-15].彭聰?shù)热薣16]提出了一種基于SM9 標(biāo)識密碼算法的環(huán)簽名方案.然而，現(xiàn)有方案的計算開銷和通信開銷均隨著環(huán)成員數(shù)量的增加而增加.

本文的主要貢獻(xiàn)有3 個方面：

1）提出了一種基于SM9 數(shù)字簽名的常數(shù)級大小環(huán)簽名方案，并基于該環(huán)簽名算法設(shè)計了一種區(qū)塊鏈隱私保護(hù)方案；

2）在隨機諭言機模型下證明了本文方案滿足不可偽造性和匿名性；

3）分析了本文方案的計算開銷和通信開銷，并與現(xiàn)有的方案做對比，實驗分析結(jié)果表明本文方案實現(xiàn)了環(huán)簽名大小不隨環(huán)用戶數(shù)量變化的需求，因而具有更高的實用性.

1 國內(nèi)外相關(guān)工作

Rivest 等人[2]提出的環(huán)簽名方案是基于RSA 加密算法的.Abe 等人[17]提出了基于離散對數(shù)問題的環(huán)簽名方案.Wong 等人[18]利用Reed-Solomon 碼的擦除校正技術(shù)和多項式插值之間的等價性提出了一種環(huán)簽名方案.為了抵抗量子計算機的攻擊，Wang 等人[19]提出了一種基于多變量的環(huán)簽名方案，隨后他們又利用基于格的無陷門簽名方案[20]提出了一種基于格的環(huán)簽名方案[21].為了減少簽名大小，Dodis 等人[22]利用基于單向域的累加器提出了首個常數(shù)級大小的環(huán)簽名方案，且該方案所有身份驗證的時間都與環(huán)成員數(shù)量無關(guān).

Zhang 等人[23]提出了基于雙線性對的基于身份的環(huán)簽名方案.Herranz 等人[24]提出了一種基于身份的環(huán)簽名方案，并將他們的方案擴展到匿名子集場景.Awasthi 等人[25]提出了一種基于身份的環(huán)簽名方案和代理環(huán)簽名方案.Nguyen[26]提出了一個基于雙線性對的動態(tài)累加器方案，并基于此構(gòu)建了一個具有常數(shù)級簽名大小的基于身份環(huán)簽名方案.Chow 等人[27]提出了高效的基于身份的環(huán)簽名方案，對于任意環(huán)成員數(shù)量僅需要2 個雙線性對計算，并在隨機諭言機模型下證明對自適應(yīng)選擇的消息和身份攻擊具有存在性不可偽造.包嘉斌[28]提出了基于SM9 標(biāo)識密碼算法的環(huán)簽密方案.鄧浩明等人[29]提出了基于SM9 標(biāo)識密碼算法的門限環(huán)簽名方案.

2 預(yù)備知識

本節(jié)給出了符號約定、雙線性對、數(shù)學(xué)困難問題、SM9 數(shù)字簽名算法、知識簽名和動態(tài)累加器的概念.

2.1 符號約定

本文使用 λ表示安全參數(shù)，?（·）表示可忽略函數(shù)，PPT 表示概率多項式時間，p和N為大素數(shù)，={1,2,…,N}，F(xiàn)p是階為p的有限域，E(Fp)表示以Fp為基域的橢圓曲線，k·P表示橢圓曲線上點P的k倍點，KGC 表示密鑰生成中心，ID表示用戶身份標(biāo)識.

2.2 雙線性對

令 G1是由P1作為生成元的N階加法循環(huán)群，G2是由P2作為生成元的N階加法循環(huán)群，GT是階為N的乘法循環(huán)群，雙線性對是滿足下列性質(zhì)的一個映射e:G1×G2→GT.

1）雙線性.對于任意的U∈G1,V∈G2和a,b∈都有e(a·U,b·V)=e(U,V)a·b.

2）非退化性.存在a,b∈使得e(U,V)≠1.

3）可計算性.對于所有U∈G1,V∈G2，存在多項式時間算法有效計算e(U,V).

2.3 數(shù)學(xué)困難問題

定義1.q-SDH 問題（q-strong Diffie-Hellman problem,q-SDH）.對于U∈G1，V∈G2，未知的a∈給定U,V,a·V,a2·V,…,aq·V，PPT 敵手輸出 (c,(a+c)-1)，其中c∈

定義2.離散對數(shù)問題（discrete logarithm problem,DLP）.對于U∈G1，未知的a∈給定W=a·U，PPT敵手輸出a.

2.4 SM9 數(shù)字簽名算法

SM9 數(shù)字簽名算法包括4 個算法，分別是系統(tǒng)初始化算法、密鑰提取算法、簽名算法和簽名驗證算法.

1）系統(tǒng)初始化算法.輸入安全參數(shù) λ，選取特定曲線生成參數(shù)t，構(gòu)建橢圓曲線基域Fp，構(gòu)建E(Fp)上的雙線性對e:G1×G2→GT，選擇哈希函數(shù)H1(·),H2(·):{0,1}*→KGC 隨機選取d∈作為簽名主密鑰msk，并計算主公鑰Ppub=d·P2.最后，輸出系統(tǒng)參數(shù)Params={e,G1,G2,GT,P1,P2,Ppub,H1,H2}作為以下算法的默認(rèn)輸入.

4）簽名驗證算法.給定主公鑰Ppub，用戶A的身份標(biāo)識IDA，消息m和簽名值 σ，驗證者計算P=H1(IDA)·P2+Ppub，驗證是否成立，若成立，則 σ為合法簽名，否則簽名無效.

2.5 知識簽名

知識簽名（signatures of knowledge,SoK）是一種證明系統(tǒng)，證明者可以證明知道某個論斷而不泄露對應(yīng)的證據(jù)，它可以用于構(gòu)造數(shù)字簽名方案來提供認(rèn)證性、完整性和不可否認(rèn)性.例如，S oK{(x)|X=x·P1}(m)表示證明者擁有知識x滿足關(guān)系X=x·P1，且不泄露x的真實值，并對消息m進(jìn)行簽名.知識簽名需要滿足正確性、可靠性、零知識性和存在性不可偽造，它包含3 個算法：

1）密鑰生成.輸入安全參數(shù) λ，輸出系統(tǒng)公開參數(shù)Params.

2）證明.輸入系統(tǒng)公開參數(shù)Params，消息m和關(guān)系(x,X)∈R，輸出知識簽名 π.

3）驗證.給定消息m和知識簽名 π，輸出accept，表明證明有效；反之，則證明無效.

2.6 動態(tài)累加器

動態(tài)累加器可以讓用戶證明一個元素屬于一個集合，而不用透露集合中的單個成員.它可以用于匿名憑證、群簽名和環(huán)簽名等應(yīng)用場景，可以實時地對集合狀態(tài)進(jìn)行更新，同時存儲和計算規(guī)模不會隨著元素數(shù)量的增加而受到影響.本文結(jié)合了Nguyen[26]提出的動態(tài)累加器方案，包含以下4 個算法：

1）累加器初始化算法.按照2.2 節(jié)定義雙線性對e:G1×G2→GT，隨機選擇L={P1,s·P1,s2·P1,…,sq·P1}，其中q是可以被累加器累加的最大上限值.創(chuàng)建動態(tài)累加器實例，隨機選擇累加器值初始化為V0=u·P1.

2）累加器評估算法.給定累加器值V0和集合累加器值可以通過元組L在不知道s的情況下計算.

3）累加器成員增加算法.增加成員x′?X，更新累加器值為V′=(x′+d)V，并更新證據(jù)W′=V+(x′-x)W.

4）累加器成員刪除算法.刪除成員x′∈X，更新累加器值為V′=(x′+d)-1V，并更新證據(jù)W′=(x′-x)-1(W-V′).

3 基于SM9 簽名的環(huán)簽名方案

本節(jié)介紹了如圖1 所示的基于身份環(huán)簽名的系統(tǒng)模型和安全模型，并提出了基于SM9 數(shù)字簽名的常數(shù)級大小環(huán)簽名方案.

Fig.1 Identity-based ring signature model圖1 基于身份的環(huán)簽名模型

3.1 系統(tǒng)模型

基于身份的環(huán)簽名包含3 種角色：KGC、簽名者和驗證者.其中可信的KGC 負(fù)責(zé)初始化系統(tǒng)公開參數(shù)，并為用戶生成對應(yīng)其身份標(biāo)識的私鑰.基于身份的環(huán)簽名包含4 個算法：

1）系統(tǒng)初始化算法Setup(λ).由KGC 執(zhí)行，輸入安全參數(shù) λ，輸出系統(tǒng)公開參數(shù)Params和KGC 的主密鑰msk.

2）密鑰提取算法Extract(ID,msk).由KGC 執(zhí)行，輸入用戶身份標(biāo)識ID和 KGC 主密鑰msk，輸出用戶私鑰dID.

3）環(huán)簽名算法RSign(m,Yn,dID).由簽名者執(zhí)行，輸入消息m，環(huán)用戶標(biāo)識集合Yn={ID1,ID2,…,IDn}，用戶私鑰dID，輸出環(huán)簽名值 σ.

4）簽名驗證算法RVerify(m,σ,Yn).由驗證者執(zhí)行，輸入消息m，簽名 σ，環(huán)用戶集合Yn={ID1,ID2,…,IDn}，輸出accept/reject.

正確性.對于環(huán)簽名算法生成的簽名，能夠通過驗證算法，即滿足等式：

3.2 安全模型

基于身份的環(huán)簽名需要滿足：1）在自適應(yīng)選擇消息和身份攻擊下的存在性不可偽造（existential unforgeability under adaptive chosen-message-and-identity attack,EUF-CMIA）；2）匿名性.

定義3.EUF-CMIA.使用模擬器 S 與敵手 A之間的游戲來定義該性質(zhì).

1）系統(tǒng)初始化.S調(diào)用Setup(λ)生成系統(tǒng)參數(shù)Params和KGC 的主公私鑰對 (Ppub,msk). S將Params和Ppub發(fā)送給敵手 A.

2）詢問階段.A以自適應(yīng)的方式進(jìn)行3 個查詢：

①哈希諭言機查詢.A詢問任意輸入的哈希值.

②密鑰提取查詢.A詢問身份標(biāo)識ID，S返回對應(yīng)的私鑰.

③簽名查詢.A 詢問環(huán)用戶集合Yn={ID1,ID2,…,

IDn}和一個消息m，S 返回對應(yīng)的簽名 σ.

定義4.匿名性.使用模擬器 S 與敵手 A之間的游戲來定義該性質(zhì).

1）系統(tǒng)初始化.S調(diào)用Setup(λ)生成系統(tǒng)參數(shù)Params和 KGC 的主公私鑰對 (Ppub,msk). S將Params和Ppub發(fā)送給A.

2）詢問階段.A以自適應(yīng)的方式進(jìn)行3 個查詢：

①哈希諭言機查詢.A詢問任意輸入的哈希值.

②密鑰提取查詢.A詢問身份標(biāo)識ID，S返回對應(yīng)的私鑰.

③簽名查詢.A 詢問環(huán)用戶集合Yn={ID1,ID2,…,IDn}

和一個消息m，S 返回對應(yīng)的簽名值 σ.

3.3 方案設(shè)計

1）系統(tǒng)初始化算法Setup.由KGC 運行，輸入安全參數(shù)λ，輸出系統(tǒng)公開參數(shù)Params和KGC 的主密鑰msk.參數(shù)選取同國密標(biāo)準(zhǔn)SM9 數(shù)字簽名算法.

2）密鑰提取算法Extract.由KGC 運行，輸入用戶A的身份標(biāo)識IDA，KGC 主密鑰msk，輸出用戶A（簽名者）的私鑰

KGC 計算用戶A的私鑰=d·(H1(IDA)+d)-1·P1并發(fā)送給用戶A.

3）環(huán)簽名算法RSign.由用戶A運行，輸入用戶A的私鑰n個成員標(biāo)識組成的環(huán)用戶集合Yn={ID1,ID2,…,IDn}，待簽名消息m，輸出環(huán)簽名值 σ.

4）簽名驗證算法RVerify.由驗證者運行，輸入消息m，簽名值σ=(ch,s1,…,s7,A1,…,A3,T1,…,T4,V)，環(huán)用戶標(biāo)識集合Yn={ID1,ID2,…,IDn}，輸出accept/reject.

驗證等式：

若等式成立，則簽名有效，返回accept；否則，簽名無效，返回reject.

4 正確性和安全性分析

4.1 正確性分析

4.2 安全性分析

本節(jié)將給出基于SM9 數(shù)字簽名的環(huán)簽名方案的安全性證明.假設(shè)KGC 是可信的，僅考慮惡意用戶作為敵手.假設(shè)q-SDH 問題是困難的，本文使用的累加器方案滿足抗碰撞性，其中q是累加器要累加元素的上限，文獻(xiàn)[26]中給出了具體的證明，本文不再贅述.

定理1.在隨機諭言機模型下，假設(shè)群G1上的離散對數(shù)問題是困難的，本文方案中的知識簽名 π滿足完備性、可靠性和零知識性.

證明.完備性可由4.1 節(jié)得證.本節(jié)只證明可靠性和零知識性.

根據(jù)式(1)(2)，證明者具有

可以得到模擬的分布與真實記錄的分布相同.

證畢.

定理2.在隨機諭言機模型下，假設(shè)q-SDH 問題是困難的，累加器方案滿足抗碰撞性，知識簽名 π滿足零知識性，我們的基于SM9 簽名的環(huán)簽名方案滿足匿名性.

定理3.在隨機諭言機模型下，假設(shè)q-SDH 問題是困難的，累加器方案滿足抗碰撞性，知識簽名 π滿足可靠性，我們的基于SM9 簽名的環(huán)簽名方案是EUF-CMIA 安全的.

證明.由于本文方案是基于非交互式零知識證明構(gòu)造的知識簽名方案，定理2 和定理3 可以很容易地從定理1 的結(jié)論中得出，故省略.

證畢.

5 基于環(huán)簽名的區(qū)塊鏈隱私保護(hù)方案

本文對Hyperledger Fabric 聯(lián)盟鏈結(jié)構(gòu)進(jìn)行修改，利用提出的環(huán)簽名方案，設(shè)計了一種區(qū)塊鏈隱私保護(hù)方案.用戶通過使用該環(huán)簽名簽署交易提案，實現(xiàn)了交易發(fā)起方的身份隱私保護(hù).交易核心過程如圖2所示.

Fig.2 Blockchain transaction process based on ring signature圖2 基于環(huán)簽名的區(qū)塊鏈交易流程

該區(qū)塊鏈隱私保護(hù)方案包含3 個實體，即KGC、用戶、區(qū)塊鏈節(jié)點，其中區(qū)塊鏈節(jié)點可以分為背書節(jié)點、排序節(jié)點和記賬節(jié)點.本文方案使用KGC 替換了Fabric 框架中的CA 模塊，避免了PKI 體系帶來的證書管理問題，在本文方案中KGC 是可信的.具體核心交易流程描述如下：

? 由KGC 執(zhí)行Setup算法，完成系統(tǒng)初始化.

①用戶向KGC 提交自己的身份標(biāo)識ID以請求用戶密鑰.

②KGC 執(zhí)行Extract算法，生成用戶的私鑰dID并發(fā)送給用戶.

③用戶在發(fā)送交易之前，先構(gòu)造交易提案，隨機選取n個成員標(biāo)識組成的環(huán)用戶集合Yn={ID1,ID2,···,IDn}，使用RSign算法對交易提案進(jìn)行簽署，并發(fā)送給背書節(jié)點.

④背書節(jié)點首先使用RVerify算法驗證交易提案簽名，根據(jù)背書策略，模擬交易執(zhí)行，完成交易驗證.

⑤背書節(jié)點對交易提案進(jìn)行簽名背書，并發(fā)送給交易發(fā)起方用戶.

⑥用戶收集到一定數(shù)量的背書簽名后，發(fā)送交易給排序節(jié)點.

⑦排序節(jié)點對收集到的交易進(jìn)行排序，構(gòu)造交易區(qū)塊.

⑧排序節(jié)點廣播交易區(qū)塊給其他節(jié)點.

⑨記賬節(jié)點使用RVerify算法驗證交易簽名，驗證背書簽名.

⑩記賬節(jié)點將確認(rèn)后的交易區(qū)塊寫入公開賬本.

6 效率分析

本節(jié)從計算開銷和通信開銷兩方面對基于身份的環(huán)簽名方案進(jìn)行評估，將本文所提出的SM9 環(huán)簽名方案與文獻(xiàn)[16]中的基于SM9 標(biāo)識密碼算法的環(huán)簽名方案和文獻(xiàn)[27]所提出的基于身份的環(huán)簽名方案進(jìn)行了比較.

6.1 計算開銷分析

在計算開銷方面，主要考慮密鑰提取、環(huán)簽名算法和簽名驗證算法的計算開銷.本文使用256 b 的BN 曲線實例化雙線性對，使用SHA-256 算法實例化哈希函數(shù)，省略了耗時很短的哈希運算和加法運算.首先在電腦端利用Miracl 庫測試1 000 次取平均值得到方案所需運算的，其中平臺參數(shù)為DELL 牌電腦，Windows 11 操作系統(tǒng)，i7-10 700 2.90 GHz 處理器和16 GB 內(nèi)存.為方便起見，表1 給出了符號定義和運算耗時結(jié)果.表2 分析了3 個方案的計算開銷.

Table 1 Symbol Definition and Running Time表1 符號定義和運行時間

Table 2 Comparison of Computation Costs for Ring Signature Schemes表2 環(huán)簽名方案的計算開銷對比

Table 3 Comparison of Communication Costs for Ring Signature Schemes表3 環(huán)簽名方案的通信開銷對比 b

本文方案的簽名生成算法需要計算14 個 G1點乘運算、6 個雙線性對運算、4 個 GT乘法運算和6 個模冪運算，耗時399.3 ms，使用預(yù)計算方法提高計算效率后，簽名生成計算可以減少4 個雙線性對運算，僅需耗時149.9 ms.簽名驗證算法需要計算9 個 G1點乘運算、10 個雙線性對運算、8 個 GT乘法運算和10個模冪運算，耗時640.7 ms，使用預(yù)計算方法后，簽名驗證計算可以減少5 個雙線性對運算，僅需耗時329 ms.

如圖3 所示，本文方案在簽名生成算法的計算開銷是常數(shù)級別的，當(dāng)環(huán)成員數(shù)量為10 時，本文方案的計算開銷與方案[27]相似.與基于SM9 的環(huán)簽名方案[16]相比，本文方案性能優(yōu)勢更加明顯，當(dāng)環(huán)成員數(shù)量為10 時，本文方案簽名生成算法的計算開銷僅為方案[16]的22.7%.

Fig.3 Signature generation computational cost comparison圖3 簽名生成計算開銷對比

如圖4 所示，本文方案在簽名驗證算法的計算開銷也是常數(shù)級別的.當(dāng)環(huán)成員數(shù)量為10 時，本文方案簽名驗證計算開銷大約是方案[27]的2 倍，不具有優(yōu)勢；當(dāng)環(huán)成員數(shù)量超過40 個時，本文方案簽名驗證計算開銷與方案[27]相似.與基于SM9 的環(huán)簽名方案[16]相比，本文方案性能優(yōu)勢明顯，當(dāng)環(huán)成員數(shù)量為10 時，本文方案簽名驗證計算開銷僅為方案[16]的一半.

Fig.4 Signature verification computational cost comparison圖4 簽名驗證計算開銷對比

6.2 通信開銷分析

如圖5 所示，本文方案的簽名通信開銷是常數(shù)級別的，當(dāng)環(huán)成員數(shù)量小于10 時，本文方案與方案[27]相比不具有優(yōu)勢.當(dāng)環(huán)成員數(shù)量小于20 時，本文方案與方案[16]對比不具有優(yōu)勢.隨著環(huán)成員數(shù)量的增長，本文方案的優(yōu)勢明顯.

Fig.5 Comparison of signature communication cost圖5 簽名通信開銷對比

7 結(jié)論

環(huán)簽名技術(shù)是一種重要的區(qū)塊鏈身份隱私保護(hù)技術(shù)，基于身份的環(huán)簽名方案具有廣泛的應(yīng)用場景，它可以避免PKI 體系帶來的證書管理問題，也具有環(huán)簽名的匿名性和不可偽造性.隨著區(qū)塊鏈系統(tǒng)國產(chǎn)化的應(yīng)用需求，傳統(tǒng)的國密算法已無法滿足復(fù)雜的區(qū)塊鏈應(yīng)用需求，本文提出了一種基于SM9 數(shù)字簽名的環(huán)簽名方案，并在隨機諭言機模型下證明了其安全性，與現(xiàn)有的方案相比，本文方案性能優(yōu)勢明顯.當(dāng)環(huán)成員數(shù)量大于20 時，本文方案在簽名通信開銷上具有明顯優(yōu)勢.隨著環(huán)簽名算法對環(huán)用戶數(shù)量增長的應(yīng)用需求，本文方案具備更高的實用性，有效解決了區(qū)塊鏈中的身份隱私泄露問題.未來工作，將研究降低環(huán)簽名通信開銷，設(shè)計面向輕量級設(shè)備的基于身份環(huán)簽名方案.

作者貢獻(xiàn)聲明：安浩楊提出了算法方案并撰寫論文；何德彪和包子健提出了指導(dǎo)意見；彭聰指導(dǎo)了實驗分析部分；羅敏修改了論文.