彭 聰 羅 敏 何德彪 黃欣沂

1(武漢大學(xué)國(guó)家網(wǎng)絡(luò)安全學(xué)院 武漢 430072) 2(福建師范大學(xué)計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院 福州 350117)

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

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

適配器簽名方案是標(biāo)準(zhǔn)數(shù)字簽名的一種擴(kuò)展形式，它可以創(chuàng)建一個(gè)隱含困難關(guān)系(例如離散對(duì)數(shù))狀態(tài)的“預(yù)簽名”，并通過困難關(guān)系證據(jù)將該預(yù)簽名可以轉(zhuǎn)換為一個(gè)完整簽名，且轉(zhuǎn)換得到的完整簽名可以由一個(gè)標(biāo)準(zhǔn)簽名方案的驗(yàn)證算法驗(yàn)證有效性.直觀地說，適配器簽名應(yīng)具備2個(gè)屬性：1)只有知道困難關(guān)系證據(jù)的用戶才能夠?qū)㈩A(yù)簽名轉(zhuǎn)變?yōu)橥暾灻?)任何用戶可以通過預(yù)簽名和完整簽名提取困難關(guān)系證據(jù).基于這2個(gè)性質(zhì)，適配器簽名方案能夠在區(qū)塊鏈中提供很好的原子交換性質(zhì)，并已在實(shí)踐中被證明應(yīng)用非常廣泛.例如，它可以構(gòu)建鏈下支付應(yīng)用程序，包括通用支付通道[8]、支付通道網(wǎng)絡(luò)[10]、支付通道集線器[11]等，也可被實(shí)際的區(qū)塊鏈協(xié)議采用，例如閃電網(wǎng)絡(luò)、雷電網(wǎng)絡(luò)等.

在本文中，我們以SM2數(shù)字簽名算法為基礎(chǔ)，構(gòu)造了一個(gè)新的適配器簽名方案，記為SM2-AS.該方案能夠有效地銜接SM2簽名方案的密鑰生成、簽名生成和簽名驗(yàn)證算法.我們?cè)陔S機(jī)預(yù)言模型下證明了SM2-AS方案是安全的，即滿足預(yù)簽名正確性、預(yù)簽名可適配性、選擇明文攻擊下的存在不可偽造性和證據(jù)可提取性.理論分析和實(shí)驗(yàn)測(cè)試表明，SM2-AS方案的性能雖然弱于Schnorr適配器簽名方案，但與ECDSA適配器簽名方案相當(dāng).

1 相關(guān)工作

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

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

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

本節(jié)我們給出本文的符號(hào)約定，并描述簽名算法、困難關(guān)系和非交互式零知識(shí)證明的概念.

2.1 符號(hào)約定

2.2 簽名算法

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

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

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

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

從安全性角度而言，若一個(gè)數(shù)字簽名方案是安全的，則必須滿足2個(gè)性質(zhì)：

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

2.3 困難關(guān)系

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

1) 存在一個(gè)概率多項(xiàng)式時(shí)間算法能夠產(chǎn)生一組實(shí)例，記為(Y,y)←GenΠ(1λ).

2) 存在一個(gè)確定性的多項(xiàng)式時(shí)間算法能夠驗(yàn)證給定的(Y,y)是否屬于關(guān)系Π.

3) 對(duì)于任意的多項(xiàng)式時(shí)間敵手，通過Y計(jì)算得到y(tǒng)的概率是可忽略的.

一般稱Y為困難關(guān)系狀態(tài)，y為困難關(guān)系證據(jù).

2.4 非交互式零知識(shí)證明

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

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

2) 零知識(shí)性(zero-knowledge).即存在一個(gè)多項(xiàng)式時(shí)間的模擬器S，能夠模擬產(chǎn)生任意困難關(guān)系實(shí)例(Y,y)∈Π的一個(gè)證明π.

3) 在線提取器(online extractor).存在一個(gè)多項(xiàng)式時(shí)間的在線提取器K能夠訪問隨機(jī)預(yù)言機(jī)的詢問列表，并能夠提取任意狀態(tài)Y及其證明π中的證據(jù)y.

3 適配器簽名基本概念

本節(jié)我們主要介紹適配器簽名的系統(tǒng)模型和安全模型.

3.1 系統(tǒng)模型

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

3.2 安全模型

相比普通數(shù)字簽名方案而言，適配器簽名方案需要滿足5個(gè)定義性質(zhì).

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

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

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

定義5.安全適配器簽名方案.一個(gè)適配器簽名方案是安全的，當(dāng)它滿足aEUF-CMA安全性、預(yù)簽名可適配性和證據(jù)可提取性.

4 基于SM2的適配器簽名

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

一般而言，標(biāo)準(zhǔn)的SM2數(shù)字簽名方案[16-17]采用素?cái)?shù)階的橢圓曲線點(diǎn)群為基本的循環(huán)群結(jié)構(gòu).不妨令是一個(gè)階為q的橢圓曲線點(diǎn)群，G是的生成元，函數(shù)f(·):→q表示取中橢圓曲線點(diǎn)的x坐標(biāo)，H(·)是一個(gè)密碼雜湊函數(shù).那么，SM2簽名算法ΣSM2=(Gen,Sign,Vrfy)的描述為：

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

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

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

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

輸入：私鑰d、消息m∈{0,1}*和困難關(guān)系狀態(tài)Y；

③ 產(chǎn)生零知識(shí)證明π=PY((P,Q),d)；

輸出：驗(yàn)證結(jié)果b.

② 驗(yàn)證式子r′=r是否成立；若成立，則br=1；否則，br=0；

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

④ 輸出驗(yàn)證結(jié)果為b=br∧bY.

算法3.適配算法σ

輸出：簽名值σ.

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

算法4.提取算法y′

輸出：證據(jù)y′或失敗符號(hào)⊥.

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

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

5 安全性證明

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

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

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

根據(jù)適配算法的定義，σ中的那么，

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

顯然，適配得到的簽名值σ是一個(gè)關(guān)于公鑰和消息的有效簽名.

證畢.

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

證畢.

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

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

證畢.

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

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

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

證畢.

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

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

證畢.

6 效率分析

本節(jié)我們以計(jì)算開銷和通信開銷來評(píng)估基于SM2的適配器簽名方案的效率,并將評(píng)估結(jié)果與文獻(xiàn)[8]中的基于Schnorr的適配器簽名方案和基于ECDSA簽名方案進(jìn)行比較.

6.1 計(jì)算開銷分析

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

對(duì)于預(yù)簽名生成算法而言，SM2適配器簽名方案比Schnorr適配器簽名方案多1個(gè)NIZK證明、1個(gè)點(diǎn)乘和1個(gè)模乘，比ECDSA適配器簽名方案多1個(gè)模乘、少1個(gè)模逆.從圖2中可知，SM2適配器簽名方案的預(yù)簽名生成耗時(shí)與ECDSA適配器簽名方案相當(dāng)，但是Schnorr適配器簽名方案的3.2倍.

Fig. 2 Execution time of different adaptor signature schemes圖2 不同適配器簽名方案的運(yùn)行耗時(shí)

對(duì)于預(yù)簽名驗(yàn)證算法而言，SM2適配器簽名方案比Schnorr適配器簽名方案多1個(gè)NIZK驗(yàn)證和2個(gè)模乘，少1個(gè)點(diǎn)乘，比ECDSA適配器簽名方案少1個(gè)模逆.從圖2中可知，SM2適配器簽名方案的預(yù)簽名驗(yàn)證耗時(shí)與ECDSA適配器簽名方案相當(dāng)，但是Schnorr適配器簽名方案的2.3倍.

對(duì)于適配算法和提取算法而言，SM2適配器簽名方案和Schnorr適配器簽名方案均采用了加法形式構(gòu)造，其所調(diào)用的模加/減運(yùn)算幾乎可以忽略不計(jì).而ECDSA適配器簽名方案采用乘法方式構(gòu)造，需要調(diào)用1次模逆和1次模乘，其運(yùn)算量遠(yuǎn)大于另外2個(gè)方案.

6.2 通信開銷分析

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

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

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

SM2適配器簽名方案在計(jì)算和通信開銷方面與ECDSA適配器簽名方案相當(dāng)，但在適配算法和提取算法的計(jì)算開銷方面更優(yōu)；SM2適配器簽名方案的運(yùn)算性能約為Schnorr適配器簽名方案的一半，且預(yù)簽名值尺寸為Schnorr適配器簽名方案的3倍.

7 結(jié) 論

作為標(biāo)準(zhǔn)數(shù)字簽名方案的一種擴(kuò)展，適配器簽名可以在簽名邏輯中內(nèi)聯(lián)困難問題，并限制完整簽名的獲取條件.該功能已經(jīng)成為了區(qū)塊鏈系統(tǒng)中鏈下支付通道構(gòu)建的關(guān)鍵模塊.然而，現(xiàn)在的適配器簽名方案均以國(guó)外算法為原型，缺少基于國(guó)家商用密碼標(biāo)準(zhǔn)的適配器簽名方案.為此，本文以SM2數(shù)字簽名方案為基礎(chǔ)，構(gòu)造了一個(gè)新的適配器簽名方案，并在隨機(jī)預(yù)言模型下證明其滿足適配器簽名方案的安全要求.通過性能分析，可知所提出的適配器簽名方案的性能與基于ECDSA的適配器簽名方案相當(dāng)，且在適配算法和提取算法的計(jì)算開銷方面具有極大的優(yōu)勢(shì).下一步，我們將以本文的方案為出發(fā)，試圖構(gòu)造基于SM2的指定提取者適配器簽名方案、盲適配器簽名方案和環(huán)適配器簽名方案等.