基于SM9 數字簽名的環簽名及其在區塊鏈隱私保護中的應用

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

（武漢大學國家網絡安全學院 武漢 430072）

（haoyangan@whu.edu.cn）

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

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

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

本文的主要貢獻有3 個方面：

1）提出了一種基于SM9 數字簽名的常數級大小環簽名方案，并基于該環簽名算法設計了一種區塊鏈隱私保護方案；

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

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

1 國內外相關工作

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

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

2 預備知識

本節給出了符號約定、雙線性對、數學困難問題、SM9 數字簽名算法、知識簽名和動態累加器的概念.

2.1 符號約定

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

2.2 雙線性對

令 G1是由P1作為生成元的N階加法循環群，G2是由P2作為生成元的N階加法循環群，GT是階為N的乘法循環群，雙線性對是滿足下列性質的一個映射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 數學困難問題

定義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.離散對數問題（discrete logarithm problem,DLP）.對于U∈G1，未知的a∈給定W=a·U，PPT敵手輸出a.

2.4 SM9 數字簽名算法

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

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

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

2.5 知識簽名

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

1）密鑰生成.輸入安全參數 λ，輸出系統公開參數Params.

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

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

2.6 動態累加器

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

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

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

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

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

3 基于SM9 簽名的環簽名方案

本節介紹了如圖1 所示的基于身份環簽名的系統模型和安全模型，并提出了基于SM9 數字簽名的常數級大小環簽名方案.

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

3.1 系統模型

基于身份的環簽名包含3 種角色：KGC、簽名者和驗證者.其中可信的KGC 負責初始化系統公開參數，并為用戶生成對應其身份標識的私鑰.基于身份的環簽名包含4 個算法：

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

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

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

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

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

3.2 安全模型

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

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

1）系統初始化.S調用Setup(λ)生成系統參數Params和KGC 的主公私鑰對 (Ppub,msk). S將Params和Ppub發送給敵手 A.

2）詢問階段.A以自適應的方式進行3 個查詢：

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

②密鑰提取查詢.A詢問身份標識ID，S返回對應的私鑰.

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

IDn}和一個消息m，S 返回對應的簽名 σ.

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

1）系統初始化.S調用Setup(λ)生成系統參數Params和 KGC 的主公私鑰對 (Ppub,msk). S將Params和Ppub發送給A.

2）詢問階段.A以自適應的方式進行3 個查詢：

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

②密鑰提取查詢.A詢問身份標識ID，S返回對應的私鑰.

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

和一個消息m，S 返回對應的簽名值 σ.

3.3 方案設計

1）系統初始化算法Setup.由KGC 運行，輸入安全參數λ，輸出系統公開參數Params和KGC 的主密鑰msk.參數選取同國密標準SM9 數字簽名算法.

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

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

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

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

驗證等式：

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

4 正確性和安全性分析

4.1 正確性分析

4.2 安全性分析

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

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

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

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

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

證畢.

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

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

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

證畢.

5 基于環簽名的區塊鏈隱私保護方案

本文對Hyperledger Fabric 聯盟鏈結構進行修改，利用提出的環簽名方案，設計了一種區塊鏈隱私保護方案.用戶通過使用該環簽名簽署交易提案，實現了交易發起方的身份隱私保護.交易核心過程如圖2所示.

Fig.2 Blockchain transaction process based on ring signature圖2 基于環簽名的區塊鏈交易流程

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

? 由KGC 執行Setup算法，完成系統初始化.

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

②KGC 執行Extract算法，生成用戶的私鑰dID并發送給用戶.

③用戶在發送交易之前，先構造交易提案，隨機選取n個成員標識組成的環用戶集合Yn={ID1,ID2,···,IDn}，使用RSign算法對交易提案進行簽署，并發送給背書節點.

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

⑤背書節點對交易提案進行簽名背書，并發送給交易發起方用戶.

⑥用戶收集到一定數量的背書簽名后，發送交易給排序節點.

⑦排序節點對收集到的交易進行排序，構造交易區塊.

⑧排序節點廣播交易區塊給其他節點.

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

⑩記賬節點將確認后的交易區塊寫入公開賬本.

6 效率分析

本節從計算開銷和通信開銷兩方面對基于身份的環簽名方案進行評估，將本文所提出的SM9 環簽名方案與文獻[16]中的基于SM9 標識密碼算法的環簽名方案和文獻[27]所提出的基于身份的環簽名方案進行了比較.

6.1 計算開銷分析

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

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

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

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

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

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

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

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

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

6.2 通信開銷分析

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

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

7 結論

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

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