基于SM2數字簽名算法的適配器簽名方案

彭 聰 羅 敏 何德彪 黃欣沂

1(武漢大學國家網絡安全學院 武漢 430072) 2(福建師范大學計算機與網絡空間安全學院 福州 350117)

在過去幾年中，區塊鏈技術受到了學術界、產業界以及政府部門的高度關注，它能夠在互不信任的分布式系統中實現安全支付、數據交易甚至更為普適的計算模式.它的核心是通過一個去中心化的共識協議，每個參與節點共同建立并維護一個存儲所有交易的分布式賬本.以比特幣、以太坊為代表的數字貨幣均依賴于區塊鏈系統，并基于區塊鏈的腳本語言提供豐富的交易方式.雖然區塊鏈上每筆交易記錄具有公開可驗證性，但它的交易吞吐量擴展問題也非常明顯[1].例如，比特幣每秒大約可以完成10筆交易，比信用卡網絡低3個數量級[2].

為解決區塊鏈交易擴容問題，研究人員提出了支付通道(payment channels)[3]的概念，即在不破壞交易安全性的前提下支持任意數量的線下交易，且僅將最終的交易狀態上鏈，從而完成交易.比特幣中的閃電網絡(Lightning Network)[4]和以太坊中的雷電網絡(Raiden Network)[5]均采用支付通道技術實現.然而，構建支付通道的一個關鍵點是如何撤銷舊的交易狀態.為此，以閃電網絡為代表的支付通道采用了懲罰機制來讓受騙方獲取所有的貨幣(包括不誠實交易方的貨幣)[6].由于礦工收取的交易費用與每筆交易中包含的腳本大小以及礦工驗證所需的計算量成正比，故需要盡可能的降低鏈上交易規模.一種有效的途徑是在鏈下管理一些交易邏輯，即將交易邏輯編碼為發送方和接收方之間的點對點協議，而不是直接在交易腳本中進行邏輯編碼.由此出發，Polestra引入了無腳本腳本(scriptless scripts)的概念[7]，后來將其形式化為適配器簽名(adaptor signature, AS)[8-9].

適配器簽名方案是標準數字簽名的一種擴展形式，它可以創建一個隱含困難關系(例如離散對數)狀態的“預簽名”，并通過困難關系證據將該預簽名可以轉換為一個完整簽名，且轉換得到的完整簽名可以由一個標準簽名方案的驗證算法驗證有效性.直觀地說，適配器簽名應具備2個屬性：1)只有知道困難關系證據的用戶才能夠將預簽名轉變為完整簽名；2)任何用戶可以通過預簽名和完整簽名提取困難關系證據.基于這2個性質，適配器簽名方案能夠在區塊鏈中提供很好的原子交換性質，并已在實踐中被證明應用非常廣泛.例如，它可以構建鏈下支付應用程序，包括通用支付通道[8]、支付通道網絡[10]、支付通道集線器[11]等，也可被實際的區塊鏈協議采用，例如閃電網絡、雷電網絡等.

在本文中，我們以SM2數字簽名算法為基礎，構造了一個新的適配器簽名方案，記為SM2-AS.該方案能夠有效地銜接SM2簽名方案的密鑰生成、簽名生成和簽名驗證算法.我們在隨機預言模型下證明了SM2-AS方案是安全的，即滿足預簽名正確性、預簽名可適配性、選擇明文攻擊下的存在不可偽造性和證據可提取性.理論分析和實驗測試表明，SM2-AS方案的性能雖然弱于Schnorr適配器簽名方案，但與ECDSA適配器簽名方案相當.

1 相關工作

在Polestra提出無腳本腳本[7]的概念后，Aumayr等人[8]設計了基于Schnorr簽名和ECDSA簽名的適配器簽名方案，并將其用于通用支付通道的構建.Malavolta等人[10]基于單向同態函數構建了適配器簽名方案.同年，Moreno-Sanchez等人[12]針對門羅幣中的可鏈接環簽名方案構造了一個新的適配器簽名，以改進門羅幣的交易腳本邏輯.此外，文獻[10-11]分別給出了將適配器簽名方案用于構建支付通道網絡和支付通道集線器的方法.

隨著量子計算威脅日益增強，以太坊和零幣均開展了向抗量子攻擊的密碼學原語遷移的計劃.為此，Esgin等人[13-14]設計了第1個基于標準格的適配器簽名方案LAS.但LAS在正確性、通信開銷和隱私性方面存在一些問題，即僅具備弱預簽名可適配性、較大的預簽名尺寸.隨后，Tairi等人[14]設計了第1個基于同源的適配器簽名方案IAS，該方案是基于CSI-Fish簽名方案擴展而成的.另外，Qin等人[15]給出了第1個基于身份鑒別協議的適配器簽名通用構造方法，并驗證該方法可支持離散對數形式、RSA形式、格基形式的鑒別協議.并且，Qin等人[15]給出了適配器盲簽名和可鏈接適配器環簽名的實例.

2 預備知識

本節我們給出本文的符號約定，并描述簽名算法、困難關系和非交互式零知識證明的概念.

2.1 符號約定

2.2 簽名算法

一般而言，傳統的數字簽名方案Σ=(Gen,Sign,Vrfy)包含3個算法：密鑰生成算法Gen、簽名生成算法Sign和簽名驗證算法Vrfy.各算法的功能描述為：

1)Gen(1λ).該算法以系統安全參數λ為輸入，輸出一對私鑰sk和公鑰pk.

2)Signsk(m).該算法以私鑰sk和消息m∈{0,1}*為輸入，輸出一個簽名值σ.

3)Vrfypk(m;σ).該算法以公鑰pk、消息m和簽名值σ為輸入，輸出驗證結果b∈{0,1}.若b=1，則表示簽名有效；否則，簽名無效.

從安全性角度而言，若一個數字簽名方案是安全的，則必須滿足2個性質：

1) 正確性.即對任意的消息m和密鑰對(sk,pk)，有Vrfypk(m;Signsk(m))=1.

2.3 困難關系

令Π是一種二元關系，LΠ是描述這種關系的語言，即LΠ{Y|?ys.t.(Y,y)∈Π}.若3個性質成立，則稱Π是一種困難關系：

1) 存在一個概率多項式時間算法能夠產生一組實例，記為(Y,y)←GenΠ(1λ).

2) 存在一個確定性的多項式時間算法能夠驗證給定的(Y,y)是否屬于關系Π.

3) 對于任意的多項式時間敵手，通過Y計算得到y的概率是可忽略的.

一般稱Y為困難關系狀態，y為困難關系證據.

2.4 非交互式零知識證明

對于某種給定的困難關系，當證據持有者需要向他人證明其所擁有的證據且不泄露證據的任何信息時，就需要用到零知識證明.非交互式零知識證明(NIZK)包括2個算法：證明生成算法P和證明驗證算法V.其中，證明生成算法P(Y,y)以狀態Y和證據y為輸入，產生一個有效的證明π；證明驗證算法V(Y,π)以狀態Y和證明π為輸入，輸出一個比特b∈{0,1}表示該證明是否有效.若b=1，則表示證明有效；否則，表示證明無效.在本方案中，所使用的零知識證明協議需要滿足3個性質：

1) 完備性(completeness).即對任意的(Y,y)∈Π，均有V(Y,P(Y,y))=1.

2) 零知識性(zero-knowledge).即存在一個多項式時間的模擬器S，能夠模擬產生任意困難關系實例(Y,y)∈Π的一個證明π.

3) 在線提取器(online extractor).存在一個多項式時間的在線提取器K能夠訪問隨機預言機的詢問列表，并能夠提取任意狀態Y及其證明π中的證據y.

3 適配器簽名基本概念

本節我們主要介紹適配器簽名的系統模型和安全模型.

3.1 系統模型

定義1.適配器簽名.對于一個數字簽名方案Σ=(Gen,Sign,Vrfy)和一個困難關系Π，適配器簽名方案ΞΣ,Π=(pSign,Adapt,pVrfy,Ext)包含4個算法：預簽名生成算法pSign、預簽名驗證算法pVrfy、適配算法Adapt和提取算法Ext.各算法的功能描述為：

3.2 安全模型

相比普通數字簽名方案而言，適配器簽名方案需要滿足5個定義性質.

定義1.預簽名正確性(pre-signature corr-ectness).一個適配器簽名方案是預簽名正確的，若對于任意消息m和任意困難問題實例Y，均有:

可見，定義1中隱含了數字簽名方案Σ的正確性，并對預簽名過程和證據提取過程進行正確性約束.

給出適配器簽名方案的安全性定義.首先，延續選擇消息攻擊下的存在不可偽造性(existential unforgeability under chosen message attacks, EUF-CMA)的定義，考慮敵手能夠訪問簽名預言機獲取任意消息mi的合法簽名值.其次，允許敵手能夠訪問預簽名預言機獲取任意消息mi和困難問題實例Y的合法預簽名值.最后，對于敵手選取的挑戰消息m*，允許敵手可以獲取消息m*的關于實例Y的預簽名值.那么，適配器方案的不可偽造性的要求就是即使敵手具備攻擊能力，它在不知道困難問題證據的情況下成功偽造一個合法簽名的概率是可忽略的.

定義5.安全適配器簽名方案.一個適配器簽名方案是安全的，當它滿足aEUF-CMA安全性、預簽名可適配性和證據可提取性.

4 基于SM2的適配器簽名

在本節中，我們首先回顧下SM2數字簽名方案，再給出適用于SM2算法的適配器簽名方案.

一般而言，標準的SM2數字簽名方案[16-17]采用素數階的橢圓曲線點群為基本的循環群結構.不妨令是一個階為q的橢圓曲線點群，G是的生成元，函數f(·):→q表示取中橢圓曲線點的x坐標，H(·)是一個密碼雜湊函數.那么，SM2簽名算法ΣSM2=(Gen,Sign,Vrfy)的描述為：

3) 簽名驗證算法b=Vrfypk(m;σ)：對于消息m∈{0,1}*和簽名值σ=(r,s)∈q×q，驗證式子r=H(m)+f(s·G+(r+s)·P)是否成立；若成立，則b=1；否則，b=0.

顯然，因為s·G+(r+s)·P=(s+(1+d)-1·(k·d+r·d))·G=k·G，SM2數字簽名方案的正確性是可以滿足的.

假設ΠG?×q是群上的困難關系，即ΠG{(Y,y)|Y=y·G}，IY表示困難關系ΠG中對于狀態Y的實例.為將困難關系ΠG嵌入到SM2簽名方案中，我們設計了適配器簽名方案：

Fig. 1 SM2-based adaptor signature scheme圖1 基于SM2的適配器簽名方案

輸入：私鑰d、消息m∈{0,1}*和困難關系狀態Y；

③ 產生零知識證明π=PY((P,Q),d)；

輸出：驗證結果b.

② 驗證式子r′=r是否成立；若成立，則br=1；否則，br=0；

③ 驗證bY=VY((P,Q),π)；

④ 輸出驗證結果為b=br∧bY.

算法3.適配算法σ

輸出：簽名值σ.

② 令簽名值σ=(r,s).

算法4.提取算法y′

輸出：證據y′或失敗符號⊥.

② 驗證(Y,y)∈ΠG是否成立；

③ 若成立，則返回y′；否則，返回⊥.

5 安全性證明

本節我們將給出基于SM2算法的適配器簽名方案的安全性證明.

定理1.基于SM2的適配器簽名方案滿足預簽名可適配性.

證明. 對于任意的公鑰P∈、困難關系實例(IY,y)∈ΠG、消息m∈{0,1}*和預簽名值如果成立，則有

根據適配算法的定義，σ中的那么，

s·G-Y+(r+s-y)P+(1+d)·Y=s·G+(r+s)P.

顯然，適配得到的簽名值σ是一個關于公鑰和消息的有效簽名.

證畢.

定理2.基于SM2的適配器簽名方案滿足預簽名正確性.

證畢.

定理3.如果SM2簽名方案ΣSM2是EUF-CMA安全的，且ΠG是一個困難關系，則基于SM2的適配器簽名方案滿足aEUF-CMA安全性.

③ 模擬零知識證明πS=S((P,Q),1)；

證畢.

定理4.如果SM2簽名方案ΣSM2是EUF-CMA安全的，且ΠG是一個困難關系，則基于SM2的適配器簽名方案滿足證據可提取性.

① 通過NIZK方案的在線提取器獲取證據y，即y如果(Y,y)?ΠG，則報錯退出；

④ 模擬零知識證明πS=S((P,Q),1)；

證畢.

定理5.如果SM2簽名方案ΣSM2是EUF-CMA安全的，且ΠG是一個困難關系，則基于SM2的適配器簽名方案是安全的.

證明.顯然，根據定義5和定理1～4可知，基于SM2的適配器簽名方案是安全的.

證畢.

6 效率分析

本節我們以計算開銷和通信開銷來評估基于SM2的適配器簽名方案的效率,并將評估結果與文獻[8]中的基于Schnorr的適配器簽名方案和基于ECDSA簽名方案進行比較.

6.1 計算開銷分析

在計算開銷方面，我們主要考慮預簽名生成算法、預簽名驗證算法、適配算法和提取算法的計算開銷.對于密鑰生成算法而言，SM2,Schnorr和ECDSA的密鑰生成機制是一樣的，故不作比較.表1給出了3種方案計算開銷，其中TP和TV分別使用NIZK證明生成算法和驗證算法的計算耗時，Tpm和Tpa分別表示群中點乘和點加運算的計算耗時，Tinv,Tmul和Tadd分別表示中模逆、模乘和模加運算的計算耗時，Th表示一次雜湊運算的計算耗時.由于，Tadd在pSign和pVrfy算法中的占比極低，故可忽略.另外，SM2算法中的(1+d)-1可預計算，故該運算亦可忽略.

對于預簽名生成算法而言，SM2適配器簽名方案比Schnorr適配器簽名方案多1個NIZK證明、1個點乘和1個模乘，比ECDSA適配器簽名方案多1個模乘、少1個模逆.從圖2中可知，SM2適配器簽名方案的預簽名生成耗時與ECDSA適配器簽名方案相當，但是Schnorr適配器簽名方案的3.2倍.

Fig. 2 Execution time of different adaptor signature schemes圖2 不同適配器簽名方案的運行耗時

對于預簽名驗證算法而言，SM2適配器簽名方案比Schnorr適配器簽名方案多1個NIZK驗證和2個模乘，少1個點乘，比ECDSA適配器簽名方案少1個模逆.從圖2中可知，SM2適配器簽名方案的預簽名驗證耗時與ECDSA適配器簽名方案相當，但是Schnorr適配器簽名方案的2.3倍.

對于適配算法和提取算法而言，SM2適配器簽名方案和Schnorr適配器簽名方案均采用了加法形式構造，其所調用的模加/減運算幾乎可以忽略不計.而ECDSA適配器簽名方案采用乘法方式構造，需要調用1次模逆和1次模乘，其運算量遠大于另外2個方案.

6.2 通信開銷分析

在通信開銷方面，我們主要考慮預簽名值的尺寸.對于參與比較的3個適配器簽名方案，其私鑰、公鑰和簽名值尺寸是一樣的.

如表2所示，SM2適配器簽名方案和ECDSA適配器簽名方案的預簽名值尺寸為4|q|+||(192 B)，其中NIZK證明需要2個q上的元素表示.Schnorr適配器簽名方案的預簽名值尺寸為2|q|(64 B).

Table 2 Comparisons of Communication Costs for Different Adaptor Signature Schemes表2 不同適配器方案的通信開銷比較

SM2適配器簽名方案在計算和通信開銷方面與ECDSA適配器簽名方案相當，但在適配算法和提取算法的計算開銷方面更優；SM2適配器簽名方案的運算性能約為Schnorr適配器簽名方案的一半，且預簽名值尺寸為Schnorr適配器簽名方案的3倍.

7 結 論

作為標準數字簽名方案的一種擴展，適配器簽名可以在簽名邏輯中內聯困難問題，并限制完整簽名的獲取條件.該功能已經成為了區塊鏈系統中鏈下支付通道構建的關鍵模塊.然而，現在的適配器簽名方案均以國外算法為原型，缺少基于國家商用密碼標準的適配器簽名方案.為此，本文以SM2數字簽名方案為基礎，構造了一個新的適配器簽名方案，并在隨機預言模型下證明其滿足適配器簽名方案的安全要求.通過性能分析，可知所提出的適配器簽名方案的性能與基于ECDSA的適配器簽名方案相當，且在適配算法和提取算法的計算開銷方面具有極大的優勢.下一步，我們將以本文的方案為出發，試圖構造基于SM2的指定提取者適配器簽名方案、盲適配器簽名方案和環適配器簽名方案等.