基于雙線性配對的適配器簽名方案*

王子瑞， 張 馳， 魏凌波，2

1. 中國科學技術(shù)大學 網(wǎng)絡空間安全學院， 合肥 230022

2. 中國電子科技南湖研究院， 嘉興 314002

1 引言

適配器簽名(adaptor signature) 是在數(shù)字簽名基礎(chǔ)上擴展而來的一類密碼學原語[1]. 它允許用戶生成一個隱含困難關(guān)系聲明的預簽名， 只有利用困難關(guān)系見證才可以將預簽名轉(zhuǎn)換為一個驗證合法的全簽名， 而使用預簽名和相應的全簽名就可以提取困難關(guān)系的見證. 這里的全簽名使用標準簽名方案的驗證算法來驗證其有效性. 也就是說， 適配器簽名中所包含的預簽名、全簽名和困難關(guān)系的見證這三者滿足如下的性質(zhì)， 即只有知道其中任意兩個的值， 才能算出第三個的值. 適配器簽名的這個性質(zhì)配合上區(qū)塊鏈的交易(含簽名) 在上鏈被確認后即公開有效的特性， 可以用來實現(xiàn)各種不依賴于可信第三方的原子交換(交換雙方或者都獲得了各自的交換對象， 或者都沒有所獲， 也稱為公平交換[2]).

假設(shè)只有Alice 知道一個離散對數(shù)關(guān)系Y=gy(這是一個典型的困難關(guān)系) 的見證y， Alice 希望用這個秘密見證y向Bob 換取Bob 的私鑰x對消息m的數(shù)字簽名， 而且這個簽名必須公開發(fā)布才能產(chǎn)生效力(例如這是上鏈交易的簽名). Bob 首先利用公開的困難關(guān)系聲明Y和自己的私鑰x生成對消息m的預簽名， 并發(fā)送給Alice. 由于Alice 知道見證y， 她可以將Bob 發(fā)來的預簽名轉(zhuǎn)換為Bob 的私鑰x對消息m的全簽名(Alice 還可以使用Bob 的公鑰來驗證這個全簽名的有效性)， 同時為了使得這個簽名生效， Alice 必須將包含這個全簽名的交易在區(qū)塊鏈上公開. Bob 一旦看到區(qū)塊鏈上公開的全簽名， 再加上自己生成的預簽名， 就能得到見證y. 在上述交換過程中， 無論哪一方在任何一個步驟偏離或者主動退出交換協(xié)議， 都會導致雙方一無所獲， 從而保證了交易的原子性.

適配器簽名還可用于實現(xiàn)跨鏈的加密貨幣原子交換[1]. 假設(shè)Alice 希望用1 比特幣換取Bob 的13以太幣. Alice 首先將1 比特幣鎖定到一個與Bob 商定的2-of-2 的比特幣地址中， 并且規(guī)定如果超出一個較長的時間后， 該地址中的比特幣還沒有被花費， 則1 比特幣返還到原先Alice 的地址. 隨后Alice 構(gòu)建比特幣交易TX1， 將2-of-2 地址中的1 比特幣輸出到Bob 指定的地址中， TX1解鎖的條件是同時提供Alice 和Bob 對該交易的簽名. Bob 對應地將13 以太幣鎖定在以太坊上由Alice 和Bob 共同管理的賬戶中， 同時規(guī)定如果超出一個較長的時間后， 該賬戶中的以太幣還沒有被花費， 則13 以太幣返還到原先Bob的賬戶. 隨后Bob 構(gòu)建以太坊交易TX2， 將共管賬戶中的13 以太幣輸出到Alice 指定的賬戶中， TX2解鎖的條件是同時提供Alice 和Bob 對該交易的簽名. 剩下的任務就是使得兩個交易TX1和TX2分別在各自的區(qū)塊鏈上一起生效或都不生效(從而保證交換的原子性).這兩個交易生效的關(guān)鍵都是除了己方的簽名外， 還需要對方對各自交易的簽名. 雙方都可以按照上述的適配器簽名方案針對不同的交易生成預簽名，這些預簽名通過相同的離散對數(shù)關(guān)系Y=gy綁定起來， 一旦知曉見證y的一方利用y將某一預簽名轉(zhuǎn)換為自己所需的全簽名， 并在對應的區(qū)塊鏈上公開交易(以及相應的全簽名)， 另一方就可以通過觀察到的公開信息來計算見證y， 從而獲得自己所需的全簽名， 然后在另一個區(qū)塊鏈上發(fā)布對應的交易.

在適配器簽名出現(xiàn)之前， 完成類似的原子交換功能需要將交換邏輯通過區(qū)塊鏈所支持的腳本語言顯式地寫入能在區(qū)塊鏈上運行的智能合約之中[3]. 使用適配器簽名的原子交換則與此不同， 關(guān)鍵的交換步驟其實是在鏈下完成的， 而且除了最簡單的區(qū)塊鏈交易所必須支持的數(shù)字簽名類腳本之外， 不需要再使用其它類型的腳本， 因而這類實現(xiàn)方法也被比特幣社區(qū)稱為隱形腳本(scriptless script) 或最小化腳本(miniscript). 與大量使用顯示腳本的智能合約相比， 基于適配器簽名的實現(xiàn)方法有以下優(yōu)點: 首先， 由于上鏈的信息被最小化， 而且上鏈的交易與最普通的區(qū)塊鏈交易外觀相同， 無法被第三方區(qū)分開來， 相關(guān)交易的適配器簽名也無法被關(guān)聯(lián)起來， 從而在最大程度上保護了交換參與者的隱私. 其二， 由于需要上鏈執(zhí)行的腳本大大減少， 節(jié)約了交易參與方的交易費用， 也有利于改善區(qū)塊鏈系統(tǒng)整體的可擴展性. 其三， 由于不需要特殊的腳本語言來支持， 這種方法的普適性最強， 只要區(qū)塊鏈所使用的簽名方案可以擴展為適配器簽名， 這種方法就可以實施. 相反， 不同的區(qū)塊鏈所支持的腳本語言在功能上都有很大的差異， 在一個區(qū)塊鏈上能夠用智能合約實現(xiàn)并不意味著在另一個區(qū)塊鏈上也能夠?qū)崿F(xiàn). 正是由于上述的顯著優(yōu)勢， 適配器簽名已經(jīng)成為了區(qū)塊鏈理論和應用研究中的一大熱點.

適配器簽名的構(gòu)想最初是在2017 年由Poelstra 在比特幣研究社區(qū)的討論中提出的[4]， 隨后這一技術(shù)被廣泛應用于支付通道[5，6]、跨鏈原子交換[7，8]等眾多的區(qū)塊鏈應用場景之中， 但是Poelstra 和隨后的應用研究并沒有給出適配器簽名的形式化定義與安全模型. Fournier 在2019 年基于Boneh 等人提出的可驗證加密簽名(verifiably encrypted signature， VES) 的概念[9]， 首次將適配器簽名定義為一次性的VES[1]， 并給出了安全模型. Aumayr 等人則是在2021 年將適配器簽名作為一個獨立的密碼學原語[5]，給出了形式化的定義和目前普遍使用的安全模型. 他們還基于區(qū)塊鏈常用的Schnorr 數(shù)字簽名算法[10]和橢圓曲線數(shù)字簽名算法(elliptic curve digital signature algorithm， ECDSA)[11]構(gòu)造了具體的適配器簽名方案， 并給出了安全證明， 從而為適配器簽名在區(qū)塊鏈中的廣泛應用奠定了堅實的理論基礎(chǔ).

如前所述， 適配器簽名能否被應用的關(guān)鍵在于區(qū)塊鏈所使用的底層數(shù)字簽名方案擴展成為適配器簽名的可能性. 因而除了將目前的主流區(qū)塊鏈所使用的簽名方案(如ECDSA 等) 擴展為適配器簽名以外， 一個主要的研究方向就是考察其它有望用于區(qū)塊鏈的數(shù)字簽名體制能否擴展為適配器簽名. Erwig 等人系統(tǒng)研究了基于身份識別協(xié)議的數(shù)字簽名方案， 并提出了將這類數(shù)字簽名擴展為適配器簽名的通用方法[12].Peng 等人則研究并實現(xiàn)了將國密數(shù)字簽名SM2 擴展為適配器簽名的方案[13]. 面向區(qū)塊鏈對抗量子攻擊的數(shù)字簽名的需求， Esgin 等人基于格密碼[14]、Tairi 等人基于同源映射密碼[15]分別構(gòu)造了后量子安全的適配器簽名方案. 基于雙線性配對(bilinear pairing) 的數(shù)字簽名是另外一類有望在區(qū)塊鏈中獲得廣泛應用的密碼體制. 雙線性配對作為在橢圓曲線上可有效計算的雙線性二元映射， 是一種優(yōu)秀的密碼學算法構(gòu)造工具[16]. 以此為基礎(chǔ)， 密碼學家已經(jīng)構(gòu)造出了性能優(yōu)異的短簽名(BLS 簽名)[17]和帶有其它強大功能的簽名(如聚合簽名、可驗證的加密簽名、部分盲簽名等). 在比特幣社區(qū)一直有將BLS 簽名列為標準簽名的規(guī)劃. Boneh 等人則在2018 年為比特幣區(qū)塊鏈專門設(shè)計了基于雙線性配對的可聚合的多簽名[18].2020 年發(fā)布的以太坊2.0 規(guī)范已經(jīng)包括了BLS 簽名. 這就引發(fā)了一個重要問題: 基于雙線性配對的數(shù)字簽名是否可以擴展為適配器簽名？針對這一問題， Erwig 等人在2021 年首先給出了負面的結(jié)果: 他們主要是針對BLS 簽名這類確定型的數(shù)字簽名， 在理論上證明這類簽名不能擴展為適配器簽名[12].

本文通過給出一個具有可證明安全的適配器簽名方案， 說明基于雙線性配對的數(shù)字簽名方案可以擴展為適配器簽名方案， 從而極大地擴展了適配器簽名在區(qū)塊鏈系統(tǒng)中的應用范圍. 由于Erwig 等人已經(jīng)證明確定型數(shù)字簽名不能用于擴展適配器簽名， 本文首先設(shè)計了一個基于雙線性配對的概率型數(shù)字簽名方案(見第4 節(jié))， 在盡量保留BLS 短簽名優(yōu)點的前提下， 在簽名中引入隨機因子， 并與擴展后需要嵌入的困難關(guān)系保持同樣的代數(shù)結(jié)構(gòu). 然后將該數(shù)字簽名方案擴展為適配器簽名方案(見第5 節(jié))， 確保預簽名不能透露全簽名的任何信息， 即只有預簽名不能偽造一個有效的全簽名; 預簽名還要具有適配性， 即利用預簽名和見證y可以計算得到一個驗證合法的全簽名. 全簽名還要具有見證可提取性， 即利用全簽名、預簽名可以計算得到見證y. 最后， 在第6 節(jié)還將所設(shè)計方案的安全性和性能開銷與文獻中有代表性的適配器簽名方案進行了全面的比較.

2 預備知識

本節(jié)給出本文需要使用的雙線性配對、困難關(guān)系假設(shè)和困難關(guān)系的定義.

定義1 (雙線性配對) : 設(shè)G 和GT均為階是大素數(shù)q的循環(huán)群. 稱映射e:G×G→GT為雙線性配對， 如果e滿足以下性質(zhì):

(1) 雙線性: 對于任意x，y ∈G 和任意a，b ∈Zq， 都有e(xa，yb)=e(x，y)ab.

(2) 非退化: 若g是群G 的生成元， 則e(g，g)/=1GT.

(3) 可計算: 對于任意x，y ∈G，e(x，y)∈GT可被有效計算.

定義2 (計算Diffie-Hellman 問題) : 對于任意的a，b ∈Z*q， 給定(g，ga，gb)， 計算gab.

若對任意概率多項式時間敵手A， 都有Pr[h ←A(n，g，ga，gb):h=gab]≤negl(n) (negl 是一個關(guān)于安全參數(shù)n可忽略函數(shù))， 則稱在循環(huán)群G 上計算Diffie-Hellman 問題是困難的.

定義3 (困難關(guān)系): 設(shè)R為(Y，y) 所滿足的一個二元關(guān)系， 其中Y被稱作聲明，y被稱作見證. 記LR:={Y|?ys.t. (Y，y)∈R}是描述R的語言. 稱R為一個困難關(guān)系， 若R滿足以下性質(zhì):

(1) 存在一個概率多項式時間算法GenR， 輸入安全參數(shù)n， 輸出(Y，y)∈R.

(2) 存在一個確定多項式時間算法能夠判定(Y，y)∈R或(Y，y) /∈R.

(3) 對任意多項式時間的敵手和任意Y ∈LR， 計算y使得(Y，y)∈R的概率可忽略.

本文具體所使用的困難關(guān)系R為離散對數(shù)困難關(guān)系， 即聲明與見證對(Y，y) 滿足Y=gy. 當需要運行算法GenR 得到一組離散對數(shù)困難關(guān)系實例時， 輸入安全參數(shù)n， 此時算法隨機選取y ∈Z*q， 計算Y=gy， 輸出(Y，y).

3 適配器簽名及其安全性定義

本節(jié)首先回顧數(shù)字簽名算法及其安全模型， 然后介紹適配器簽名算法和其安全模型. 在后面的章節(jié)中將根據(jù)這些定義構(gòu)造具體的數(shù)字簽名方案和適配器簽名方案并給出安全證明.

3.1 數(shù)字簽名算法及其安全模型

定義4 (數(shù)字簽名):一個數(shù)字簽名方案SIG=(KeyGen，Sign，Vrfy)，包含密鑰生成算法KeyGen、簽名算法Sign 和簽名驗證算法Vrfy.

· KeyGen(1n): 輸入安全參數(shù)n， 輸出一對公私鑰對(pk，sk).

· Sign(sk，m): 輸入消息m和私鑰sk， 輸出對消息m的簽名σ.

· Vrfy(pk，m，σ): 輸入消息m、簽名σ和公鑰pk， 輸出一個比特值b ∈{0，1}，b=1 表示接受該簽名，b=0 表示拒絕該簽名.

一個數(shù)字簽名方案SIG 最基本的安全要求是要滿足選擇消息攻擊下存在不可偽造性(existential unforgeability against chosen message attacks， EUF-CMA)[19]， 這一安全性質(zhì)是由挑戰(zhàn)者C和敵手A之間交互的游戲SigForgeA，SIG(n) 來定義的， 具體過程如下:

(1) 初始化階段: 挑戰(zhàn)者C運行KeyGen(1n) 生成公私鑰對(pk，sk)， 將pk 交給敵手A， 保留sk 以回答敵手的簽名詢問.

(2) 簽名詢問階段:敵手A自適應地選擇消息mi向挑戰(zhàn)者C詢問簽名.挑戰(zhàn)者C運行Sign(sk，mi)，得到簽名σi并發(fā)送給敵手A.

(3) 簽名偽造階段: 敵手A給出偽造簽名的消息m*和偽造的簽名σ*.

若驗證σ*合法且敵手未詢問過消息m*的簽名， 則敵手贏得游戲， 輸出1; 否則， 輸出0.

定義5 (EUF-CMA): 若對任意概率多項式時間的敵手A， 運行游戲SigForgeA，SIG(n)， 敵手A贏得游戲的概率是可忽略的， 即

則稱數(shù)字簽名方案SIG 是EUF-CMA 安全的.

3.2 適配器簽名算法及其安全模型

定義6 (適配器簽名): 一個基于困難關(guān)系R和簽名方案SIG=(KeyGen， Sign， Vrfy) 的適配器簽名方案aSIGR，SIG除了包含原有簽名方案SIG 的三個算法外， 還包含五個新的算法， 即困難關(guān)系生成算法GenR、預簽名算法pSign、預簽名驗證算法pVrfy、適配算法Adapt 和見證提取算法Ext.

· GenR(1n): 輸入安全參數(shù)n， 輸出一個聲明見證對(Y，y)∈R.

· pSign(sk，m，Y): 輸入私鑰sk、消息m ∈{0，1}*和聲明Y， 輸出一個預簽名～σ.

· pVrfy(pk，m，Y，～σ): 輸入公鑰pk、消息m ∈{0，1}*、聲明Y和預簽名～σ， 輸出一個比特值b ∈{0，1}，b=1 表示預簽名合法，b=0 表示預簽名不合法.

· Adapt(～σ，y): 輸入預簽名～σ和見證y， 輸出一個全簽名σ.

· Ext(σ，～σ，Y): 輸入全簽名σ、預簽名～σ和聲明Y ∈LR， 輸出一個見證y使得(Y，y)∈R.

一個適配器簽名方案aSIGR，SIG是安全的， 如果它滿足以下三個性質(zhì): 選擇消息攻擊下存在不可偽造性(existential unforgeability against chosen message attacks for adaptor signature， aEUF-CMA)、預簽名適配性(pre-signature adaptability) 和見證可提取性(witness extractability)[5]. 下面分別給出三個性質(zhì)的定義.

3.2.1 aEUF-CMA

aEUF-CMA 安全是適配器簽名方案最重要的安全性質(zhì)， 它保證了任何不具有見證y的人， 即使可以獲取針對消息m的有效的預簽名， 也難以偽造針對消息m的一個全簽名. 適配器簽名的aEUFCMA 安全與數(shù)字簽名的EUF-CMA 安全類似， 也是通過挑戰(zhàn)者C和敵手A之間交互的游戲aSig-ForgeA，aSIGR，SIG(n) 來定義的， 具體如下:

(1) 初始化階段:挑戰(zhàn)者C運行KeyGen(1n)生成公私鑰對(pk，sk)，運行GenR(1n)生成(Y，y)∈R，將pk 和Y交給敵手A， 保留sk 以回答敵手的預簽名和簽名詢問.

(2) 預簽名詢問階段: 敵手A自適應地選擇消息mi作預簽名詢問， 挑戰(zhàn)者將消息mi加入消息詢問列表Q， 運行pSign 算法， 將mi和對應的預簽名～σi發(fā)送給敵手.

(3) 簽名詢問階段: 敵手A自適應地選擇消息mi作簽名詢問， 挑戰(zhàn)者將消息mi加入消息詢問列表Q， 運行Sign 算法， 將mi和對應的簽名σi發(fā)送給敵手.

(4) 全簽名偽造階段: 敵手A選擇要偽造全簽名的消息m*發(fā)送給挑戰(zhàn)者C. 挑戰(zhàn)者C運行pSign(sk，m*，Y) 得到預簽名～σ*， 發(fā)送給敵手A. 敵手A給出針對消息m*的偽造簽名σ*.

若Vrfy(pk，m*，σ*)=1 且m*/∈Q， 則敵手贏得游戲， 輸出1; 否則， 輸出0.

定義7 (aEUF-CMA): 若對任意概率多項式時間的敵手A， 運行游戲aSigForgeA，aSIGR，SIG(n)， 敵手A贏得游戲的概率是可忽略的， 即

則稱適配器簽名方案aSIGR，SIG是aEUF-CMA 安全的.

3.2.2 預簽名適配性

預簽名適配性是使得預簽名能夠提供原子交換功能的第一個關(guān)鍵性質(zhì)， 它保證了任何擁有見證y的人， 只要獲取到在相應聲明Y下驗證合法的預簽名， 就一定可以將該預簽名轉(zhuǎn)換為在原有簽名驗證算法下驗證合法的全簽名. 預簽名適配性的規(guī)范化定義表述如下.

定義8 (預簽名適配性): 若對任意消息m ∈{0，1}*、任意公鑰pk、任意(Y，y)∈R和預簽名～σ， 當預簽名驗證合法， 即滿足pVrfy(pk，m，Y，～σ)=1 時， 使用預簽名～σ和見證y計算得到的全簽名一定合法，即滿足Vrfy(pk，m，Adapt(～σ，y))=1， 則稱該適配器簽名方案滿足預簽名適配性.

3.2.3 見證可提取性

見證可提取性是使得預簽名能夠提供原子交換功能的第二個關(guān)鍵性質(zhì)， 它保證了獲取到一對驗證合法的預簽名與全簽名對的用戶可以從中提取秘密見證y. 見證可提取性是通過挑戰(zhàn)者C和敵手A之間交互的游戲WitExtA，aSIGR，SIG(n) 來定義的， 具體如下:

(1) 初始化階段: 挑戰(zhàn)者C運行KeyGen(1n) 生成公私鑰對(pk，sk)， 將pk 交給敵手A， 保留sk 以回答敵手的預簽名詢問和簽名詢問. 敵手A運行GenR 算法生成(Y，y)∈R， 公布聲明Y， 保密見證y.

(2) 預簽名詢問階段: 敵手A自適應地選擇消息mi作預簽名詢問， 挑戰(zhàn)者將消息mi加入消息詢問列表Q， 運行pSign 算法， 將mi和對應的預簽名～σi發(fā)送給敵手.

(3) 簽名詢問階段: 敵手A自適應地選擇消息mi作簽名詢問， 挑戰(zhàn)者將消息mi加入消息詢問列表Q， 運行Sign 算法， 將mi和對應的簽名σi發(fā)送給敵手.

(4) 見證提取階段: 敵手A選擇消息m*和Y*， 發(fā)送給挑戰(zhàn)者C. 挑戰(zhàn)者C運行pSign(sk，m*，Y*)，得到預簽名～σ*， 發(fā)送給敵手A. 敵手A生成針對消息m*的簽名σ*， 交給挑戰(zhàn)者C. 挑戰(zhàn)者C運行Ext(σ*，～σ*，Y*)， 得到見證y′.

若Vrfy(pk，m*，σ*)=1， 同時m*/∈Q且(Y*，y′) /∈R， 則敵手贏得游戲， 輸出1; 否則， 輸出0.

定義9 (見證可提取性): 若對任意概率多項式時間的敵手A， 運行游戲WitExtA，aSIGR，SIG(n)， 敵手A贏得游戲的概率是可忽略的， 即

則稱適配器簽名方案aSIGR，SIG滿足見證可提取性.

游戲WitExt 和游戲aSigForge 非常相似， 然而有一個重要的不同點是在游戲WitExt 中是由敵手A來運行GenR 算法. 因此， 敵手A可能知道對應的見證y*， 可以利用y*和預簽名～σ*給出消息m*的一個簽名σ*. 然而敵手A要贏得游戲WitExt 的要求是給出的簽名不能泄露見證y的信息.

4 基于雙線性配對的概率型數(shù)字簽名方案

本節(jié)首先構(gòu)造一個基于雙線性配對的概率型數(shù)字簽名方案Π， 作為下一節(jié)擴展為適配器簽名方案的基礎(chǔ)， 然后基于計算Diffie-Hellman 困難問題假設(shè)， 在隨機預言機模型下證明該方案是EUF-CMA 安全的.

設(shè)H:{0，1}*→G 是抗碰撞的哈希函數(shù)，e: G×G→GT是第2 節(jié)中定義的雙線性配對， 數(shù)字簽名方案Π 構(gòu)造如下:

· KeyGen(1n): 簽名者隨機選取x ∈Z*q， 計算h=gx. 令(pk，sk)=(h，x)， 公開pk， 保密sk.

· Sign(sk，m): 簽名者隨機選取r ∈Z*q， 計算R=gr， 令(σ1，σ2) =(r，H(R||m)x)， 輸出對消息m的簽名(σ1，σ2).

· Vrfy(pk，m，σ1，σ2): 若e(σ2，g)=e(H(gσ1||m)，h)， 簽名合法， 輸出1; 否則， 簽名不合法， 輸出0.

定理1 設(shè)哈希函數(shù)H是一個隨機預言機. 若計算Diffie-Hellman 問題是困難的， 則上述數(shù)字簽名方案Π 滿足EUF-CMA.

證明: 若存在敵手A在多項式時間贏得游戲SigForgeA，Π(n)， 則可以構(gòu)造一個模擬器S在多項式時間成功求解計算Diffie-Hellman 問題. 隨機預言機由模擬器S控制， 模擬器S依照如下過程為敵手A模擬游戲SigForgeA，Π(n)， 其中p1和p2均是關(guān)于安全參數(shù)n的多項式.

(1) 初始化階段: 挑戰(zhàn)者C生成一個群G 上計算Diffie-Hellman 問題的實例(g，ga，gb)， 交給模擬器S. 模擬器S設(shè)置pk=h=ga， 相應的私鑰sk=a， 將pk 交給敵手A.

因為假定計算Diffie-Hellman 問題是困難的， 所以數(shù)字簽名方案Π 滿足EUF-CMA.

5 基于雙線性配對的適配器簽名方案

本節(jié)基于第4 節(jié)中的數(shù)字簽名方案Π 構(gòu)造適配器簽名方案， 并證明其滿足第3 節(jié)中定義的適配器簽名的三個安全性質(zhì).

一個基于離散對數(shù)關(guān)系Rg和數(shù)字簽名方案Π 的適配器簽名方案ΞΠ構(gòu)造如下:

· GenR(1n): 驗證者隨機選取y ∈Z*q， 計算Y=gy， 輸出聲明與見證對(Y，y)∈Rg. 驗證者將聲明Y發(fā)給簽名者.

· pSign(sk，m，Y): 簽名者使用該算法生成對消息m的預簽名. 隨機選取r ∈Z*q， 計算R=gr， 令(～σ1，～σ2)=(r，H(RY||m)x)， 輸出對消息m的預簽名(～σ1，～σ2).

· pVrfy(pk，m，Y，～σ1，～σ2): 驗證者使用該算法驗證簽名者生成的對消息m的預簽名是否合法. 若e(～σ2，g)=e(H(g～σ1Y||m)，h)， 預簽名合法， 輸出1; 否則， 預簽名不合法， 輸出0.

· Adapt(～σ1，～σ2，y): 驗證者使用該算法提取簽名者對消息m全簽名. 計算σ1= ～σ1+y，σ2= ～σ2， 輸出(σ1，σ2).

· Ext(σ1，～σ1，Y): 一旦驗證者公布了全簽名(σ1，σ2)， 簽名者就可使用該算法提取原本只有驗證者知曉的見證值y. 計算y=σ1-～σ1， 輸出y.

定理2 設(shè)哈希函數(shù)H是一個隨機預言機. 若計算Diffie-Hellman 問題是困難的， 則上述適配器簽名方案ΞΠ滿足aEUF-CMA.

證明: 若存在敵手A在多項式時間贏得游戲aSigForgeA，ΞΠ(n)， 則可以構(gòu)造一個模擬器S在多項式時間成功求解計算Diffie-Hellman 問題. 隨機預言機由模擬器S控制， 模擬器S為敵手A模擬aSigForgeA，ΞΠ(n) 過程， 游戲模擬按照如下過程進行， 其中p1，p2，p3均是關(guān)于安全參數(shù)n的多項式.

(1) 初始化階段: 挑戰(zhàn)者C生成一個群G 上計算Diffie-Hellman 問題的實例(g，ga，gb)， 交給模擬器S. 模擬器S設(shè)置pk =h=ga， 相應的私鑰sk =a. 模擬器S運行GenR(1n) 生成一個聲明與見證對(Y，y) 滿足Y=gy， 將pk，Y交給敵手A. 消息詢問集合Q初始化為空.

若(σ1，σ2) 驗證合法且消息m*/∈Q， 則敵手成功偽造了簽名. 由于預簽名算法pSign 和簽名算法Sign 都是概率算法， 因此安全模型中并不要求模擬器S給出的預簽名和敵手A偽造的簽名是匹配的， 只需要模擬器S提供的預簽名通過pVrfy 算法驗證即可. 也就是說， 即使敵手A成功偽造了簽名， 也可能無法用該簽名提取見證y.

因為假定計算Diffie-Hellman 問題是困難的， 所以適配器簽名方案ΞΠ滿足aEUF-CMA.

定理3 上述適配器簽名方案ΞΠ滿足預簽名適配性.

證明: 對任意消息m ∈{0，1}*， 任意公鑰h=gx， 任意(Y，y) 滿足Y=gy， 預簽名(～σ1，～σ2) =(r，H(grY||m)x)， 滿足pVrfy(pk，m，Y，～σ1，～σ2) = 1， 即e(H(grY||m)x，g)=e(H(grY||m)，h). 則簽名(σ1，σ2) = Adapt(～σ1，～σ2，y) =(r+y，H(grY||m)x)， 所以e(H(grY||m)x，g)=e(H(gr+y||m)，h)， 即Vrfy(pk，m，Adapt(～σ1，～σ2，y))=1. 因此適配器簽名方案ΞΠ滿足預簽名適配性.

定理4 上述適配器簽名方案ΞΠ滿足見證可提取性.

證明: 若存在敵手A在多項式時間贏得游戲WitExtA，ΞΠ(n)， 則可以構(gòu)造一個模擬器S在多項式時間內(nèi)找到哈希函數(shù)H的一對碰撞. 模擬器S為敵手A模擬游戲WitExtA，ΞΠ(n). 游戲模擬按照如下過程進行.

(1) 初始化階段: 模擬器S運行KeyGen 算法生成公私鑰對(pk，sk)=(gx，x)， 將公鑰pk 交給敵手A， 保留sk 以回答敵手A的預簽名詢問和簽名詢問. 敵手A運行GenR 算法生成聲明與見證對(Y，y) 滿足Y=gy， 將聲明Y交給模擬器S. 消息詢問集合Q初始化為空.

(2) 預簽名詢問階段: 敵手A在此階段可以向模擬器S作預簽名詢問. 假設(shè)敵手A針對消息mi作預簽名詢問， 模擬器S運行pSign 算法生成關(guān)于消息mi的預簽名(～σ1，～σ2) 發(fā)給敵手A， 并將消息mi加入集合Q.

(3) 簽名詢問階段: 敵手A在此階段可以向模擬器S作簽名詢問. 假設(shè)敵手A針對消息mi作簽名詢問， 模擬器S運行Sign 算法生成關(guān)于消息mi的簽名(σ1，σ2) 發(fā)給敵手A， 并將消息mi加入集合Q.

(4) 見證提取階段: 敵手A選擇消息m*∈{0，1}*， 發(fā)送給模擬器S. 模擬器S運行pSign 算法生成消息m*的預簽名(～σ*1，～σ*1) 發(fā)送給敵手A. 敵手A產(chǎn)生一個消息m*的簽名(σ*1，σ*2) 交給模擬器S. 模擬器S運行Ext 算法提取見證y′.

若Vrfy(par，m*，σ*1，σ*2，pk)=1 且m*/∈Q且Y/=gy′， 則敵手贏得游戲， 輸出1; 否則， 輸出0.

設(shè)～σ*1=r. 模擬器S提取見證得到y(tǒng)’ 后， 將比特串gr+y′||m*和grY||m*發(fā)送給挑戰(zhàn)者C作為哈希函數(shù)H的一對碰撞.

下面分析模擬器S成功給出哈希函數(shù)H一對碰撞的概率. 已知(r，H(grY||m*)x)是模擬器S給出的關(guān)于消息m*的一個合法的預簽名. 若游戲輸出1， 則模擬器S成功提取了見證y′使得Y/=gy′且(r+y′，H(grY||m*)x)是一個合法的全簽名. 同時，(r+y′，H(gr+y′||m*)x)也一定是一個合法的全簽名.因此，一定有e(H(gr+y′||m*)x，g)=e(H(grY||m*)x，g).這時，若H(gr+y′||m*)/=H(grY||m*)，那么雙線性配對e將不滿足定義1 中的非退化. 因此， 當游戲輸出1 時， 一定會有H(gr+y′||m*)=H(grY||m*).而Y/=gy′， 所以gr+y′||m*和grY||m*是兩個不同的比特串， 這正是哈希函數(shù)H的一對碰撞. 所以， 模擬器S成功給出哈希函數(shù)H的一對碰撞的概率

因為哈希函數(shù)H滿足抗碰撞性， 所以適配器簽名方案ΞΠ滿足見證可提取性.

6 適配器簽名方案的性能與安全性比較

下面將本文方案與基于Schnorr 簽名的適配器簽名方案和基于ECDSA 的適配器簽名方案在安全性、計算開銷與存儲開銷方面進行比較. 后兩種方案也是目前區(qū)塊鏈系統(tǒng)中使用最為廣泛的適配器簽名方案.

在安全性方面，基于Schnorr 簽名的適配器簽名方案將aEUF-CMA 安全歸約到Schnorr 簽名的強不可偽造性[5]，Kiltz 等人[20]將Schnorr 簽名的強不可偽造性歸約到離散對數(shù)問題的困難性.基于ECDSA的適配器簽名方案將aEUF-CMA 安全歸約到ECDSA 的強不可偽造性[5]， 然而ECDSA 的強不可偽造性至今沒有得到證明， 因此基于ECDSA 的適配器簽名方案的安全性沒有理論上的保障. 本文方案將aEUF-CMA 安全歸約到計算Diffie-Hellman 問題的困難性， 計算Diffie-Hellman 困難問題是目前基于雙線性配對的方案中常用的困難問題假設(shè).

在計算開銷方面， 比較以上三種方案中pSign、pVrfy、Adapt、Ext 算法的計算時間， 詳細的計算開銷對比見表1. 其中，Tp與Tv分別表示生成與驗證零知識證明的計算時間;Tgp和Tgm分別表示循環(huán)群G 中冪運算與乘運算的計算時間;Tinv、Tmul、Tadd分別表示Z*q中模逆、模乘、模加的計算時間;Tpair、Th1、Th2分別表示雙線性配對e， 哈希函數(shù)H1:{0，1}*→Z*q， 哈希函數(shù)H2:{0，1}*→G 的計算時間.

表1 計算開銷對比Table 1 Computational cost comparison

使用MacbookPro 筆記本電腦運行以上三種適配器簽名方案. 筆記本電腦使用的中央處理器為IntelCore i5@2.70 GHz， 內(nèi)存為8 GB. 得到這三種方案在pSign、pVrfy、Adapt、Ext 算法中的具體計算時間， 如圖1 所示.

圖1 計算時間對比Figure 1 Computational time comparison

本文方案pSign 算法的計算耗時比基于Schnorr 簽名的適配器簽名方案多1.188 ms， 然而比基于ECDSA 的適配器簽名方案少1.948 ms. 本文方案Adapt 算法和Ext 算法的計算耗時與基于Schnorr簽名的適配器簽名方案相當， 且均小于基于ECDSA 的適配器簽名方案. 由于本文方案在驗證預簽名時要使用雙線性配對， 雙線性配對運算較其他運算耗時要多， 因此本文方案pVrfy 算法的計算耗時比基于Schnorr 簽名的適配器簽名方案多19.125 ms， 比基于ECDSA 的適配器簽名方案多15.635 ms. 雖然與其他兩個方案相比本文方案pVrfy 算法的計算效率最低， 然而本文的目標不是構(gòu)造計算效率最優(yōu)的適配器簽名方案， 而是利用雙線性配對構(gòu)造方案以期望適配器簽名技術(shù)可以與雙線性配對結(jié)合， 在區(qū)塊鏈系統(tǒng)中獲得更為廣泛的應用.

在存儲開銷方面， 比較以上三種方案的密鑰長度、預簽名長度與簽名長度， 如表2 所示. 三種方案的密鑰生成算法是相同的， 它們的私鑰均為一個Z*q上的元素， 長度為32 字節(jié)， 公鑰均為一個群G 上的元素，長度為64 字節(jié)， 所以密鑰總長度為96 字節(jié). 基于Schnorr 簽名的適配器簽名方案產(chǎn)生的預簽名和簽名均為兩個Z*q上的元素， 長度為64 字節(jié). 基于ECDSA 的適配器簽名方案產(chǎn)生的預簽名是四個Z*q上的元素和一個群G 上的元素， 總長度為192 字節(jié); 產(chǎn)生的簽名是兩個Z*q上的元素， 長度為64 字節(jié). 本文方案產(chǎn)生的預簽名和簽名均為一個Z*q上的元素加一個群G 上的元素， 長度為96 字節(jié).

表2 存儲開銷對比(字節(jié))Table 2 Storage overhead comparison (byte)

7 結(jié)論

本文首次構(gòu)造了一個基于雙線性配對的適配器簽名方案. 首先提出了一種基于雙線性配對的數(shù)字簽名方案Π. 基于計算Diffie-Hellman 困難問題假設(shè)， 利用隨機預言機模型證明了該方案滿足EUF-CMA. 然后在方案Π 的基礎(chǔ)上， 構(gòu)造了基于雙線性配對的適配器簽名方案ΞΠ并證明其滿足aEUF-CMA， 預簽名適配性和見證可提取性. 本文還將所設(shè)計方案的安全性和性能開銷與文獻中有代表性的適配器簽名方案進行了全面比較. 下一步， 我們將研究在標準模型下可證明安全的雙線性配對適配器簽名方案， 并利用雙線性配對的優(yōu)良性質(zhì)， 開發(fā)具有更多功能的適配器簽名方案.