基于SM2 數(shù)字簽名算法的環(huán)簽名方案*

范 青, 何德彪, 羅 敏, 黃欣沂, 李大為

1. 武漢大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院, 武漢430072

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

3. 福建師范大學(xué) 計算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院, 福州350117

4. 深圳技術(shù)大學(xué) 大數(shù)據(jù)與互聯(lián)網(wǎng)學(xué)院, 深圳518118

1 引言

傳統(tǒng)數(shù)字簽名算法保證了數(shù)據(jù)完整性和簽名者抗抵賴性. 國家密碼管理局于2010 年12 月17 日發(fā)布了SM2 橢圓曲線公鑰密碼算法[1], 并于2012 年批準(zhǔn)為密碼行業(yè)標(biāo)準(zhǔn)(GM/T 0003-2012)[2], 2016年正式發(fā)布為中國國家密碼標(biāo)準(zhǔn)(GB/T32918-2016)[3]. SM2 數(shù)字簽名算法作為其中之一部分, 與基于有限域上困難問題的數(shù)字簽名算法相比, 在相同的安全強(qiáng)度下SM2 數(shù)字簽名具有存儲空間小、簽名速度快的優(yōu)勢. 在商用密碼體系中, 該標(biāo)準(zhǔn)提供了電子認(rèn)證服務(wù)系統(tǒng)所需的安全性能, 替代了國外的ECDSA、Schnorr 等簽名算法, 推動了密碼技術(shù)應(yīng)用發(fā)展的自主化和可控性, 豐富了國產(chǎn)密碼體系.

但是日益發(fā)展的信息安全技術(shù)對數(shù)字簽名提出了新的功能性需求, 如電子現(xiàn)金、電子投票、匿名通信等具體的應(yīng)用場景中, 要求用戶的身份和位置等隱私信息保密. 環(huán)簽名能夠隱藏真實簽名者的身份, 達(dá)到匿名性的效果. 2001 年, Rivest 等人首次提出了模糊簽名者身份的新型簽名概念——環(huán)簽名[4]. 環(huán)簽名是指簽名者自發(fā)選擇多個用戶, 然后利用自身公私鑰對和選取的用戶公鑰對文件進(jìn)行簽名. 簽名者及其選擇的用戶組成的群組稱為環(huán), 構(gòu)成環(huán)的成員由簽名者根據(jù)所需指定, 驗證者只能知道簽名值出自環(huán)中某一成員, 但不能確定出真實的簽名者. 環(huán)簽名實現(xiàn)了將真實簽名者的身份隱藏在環(huán)中, 以保護(hù)用戶的身份隱私.

為深入理解環(huán)簽名的概念, 下面給出環(huán)簽名和群簽名之間的聯(lián)系與區(qū)別. 環(huán)簽名和群簽名均為個體代表群體簽名的體制, 都實現(xiàn)了簽名身份的匿名性. 但二者之間也存在著區(qū)別, 主要體現(xiàn)在以下三個方面[5–7]: (1) 管理系統(tǒng): 環(huán)簽名具有自發(fā)性, 環(huán)中每個成員地位平等; 群簽名中存在一個管理員負(fù)責(zé)群成員的加入和離開. (2) 匿名特征: 環(huán)簽名具有無條件匿名性, 即任何人在任何情況下都不能恢復(fù)出簽名者的真實身份; 群簽名的匿名性是有條件的, 群管理員能夠根據(jù)簽名得出簽名出自群體中哪一個成員. (3) 簽名密鑰: 環(huán)簽名的生成使用用戶的密鑰, 包括簽名者私鑰和環(huán)成員公鑰; 群簽名不僅需要用戶密鑰還需要群管理員的密鑰.

環(huán)簽名因其自發(fā)性和無條件匿名性得到廣泛應(yīng)用, 包括電子郵件、數(shù)據(jù)交換、電子交易和電子貨幣等領(lǐng)域[7]. 根據(jù)密鑰生成方式不同, 環(huán)簽名分為公鑰基礎(chǔ)設(shè)施(PKI) 體系下的環(huán)簽名[4,8–16]、基于身份(IBC) 的環(huán)簽名[17–23]以及無證書(CLC) 體系下的環(huán)簽名[24–29]. PKI 體系下經(jīng)典的環(huán)簽名包含基于RSA 簽名算法的RST 環(huán)簽名算法[4]和基于Schnorr 簽名的AOS 環(huán)簽名[8], 但是尚未有公開可查詢到的基于SM2 數(shù)字簽名算法的環(huán)簽名.

電子商務(wù)的廣泛深入發(fā)展對環(huán)簽名提出了多樣化的應(yīng)用需求, 根據(jù)不同的屬性特征, 環(huán)簽名分為可鏈接環(huán)簽名[30]、可否認(rèn)的環(huán)簽名[31]、門限環(huán)簽名[32]、可撤銷匿名性的環(huán)簽名[33]等等, 目前應(yīng)用較為廣泛的是可鏈接環(huán)簽名. Liu 等人在2004 年首次提出具有自發(fā)性的可鏈接環(huán)簽名概念[30], 并提出第一個可鏈接環(huán)簽名方案——LSAG. 在環(huán)簽名算法的基礎(chǔ)上, 用戶利用自身私鑰生成一個關(guān)聯(lián)此次簽名的標(biāo)簽, 該標(biāo)簽不可偽造且同一簽名者對不同消息生成的環(huán)簽名具有相同的鏈接標(biāo)簽, 實現(xiàn)了對同一簽名者所生成簽名的鏈接. 在Liu 等人的文章中, 利用LSAG 構(gòu)建的投票系統(tǒng)既能確保選民身份匿名性又能避免重復(fù)投票. 2013 年, Saberhagen 等人將可鏈接環(huán)簽名應(yīng)用于基于區(qū)塊鏈的數(shù)字貨幣協(xié)議[34], 提出了適用于門羅幣的CryptoNote 協(xié)議, 該協(xié)議有效保護(hù)了交易雙方的身份隱私; 在此基礎(chǔ)上, 出現(xiàn)了可鏈接環(huán)簽名在區(qū)塊鏈中的典型應(yīng)用——RingCT1.0[35], RingCT2.0[36]和RingCT3.0[37].

為了彌補(bǔ)SM2 數(shù)字簽名算法在環(huán)簽名研究中的空缺, 奠定國產(chǎn)SM2 數(shù)字簽名算法應(yīng)用于區(qū)塊鏈的基礎(chǔ), 進(jìn)而把握區(qū)塊鏈發(fā)展中密碼技術(shù)的自主可控權(quán), 本文基于SM2 數(shù)字簽名算法提出了SM2 環(huán)簽名方案, 并且通過嵌入安全的鏈接標(biāo)簽提出了SM2 可鏈接環(huán)簽名方案及其兩種變型方案.

本文結(jié)構(gòu)如下: 第2 節(jié)介紹了環(huán)簽名的預(yù)備知識, 包括環(huán)簽名和可鏈接環(huán)簽名的定義, 正確性、不可偽造性、無條件匿名性以及鏈接性、不可誹謗性等安全性要求, 同時介紹了SM2 數(shù)字簽名算法; 第3 節(jié)提出了SM2 環(huán)簽名的系統(tǒng)參數(shù)生成、密鑰生成、(可鏈接) 環(huán)簽名、環(huán)簽名驗證等4 個算法, 從系統(tǒng)參數(shù)生成、密鑰生成、可鏈接環(huán)簽名生成、可鏈接環(huán)簽名驗證、鏈接等5 個方面介紹了SM2 可鏈接環(huán)簽名及其兩種變型方案; 第4 節(jié)證明了SM2 環(huán)簽名和可鏈接環(huán)簽名的安全性; 第5 節(jié)分析了其通信成本和計算成本與環(huán)成員數(shù)量的關(guān)系; 最后在第6 節(jié)給出了本文的總結(jié)和展望.

2 預(yù)備知識

2.1 環(huán)簽名定義與安全性

本節(jié)給出環(huán)簽名的定義、安全性需求[38]以及橢圓曲線上的困難問題假設(shè).

定義1 (環(huán)簽名) 環(huán)簽名包含4 個多項式時間算法: 系統(tǒng)初始化、密鑰生成、環(huán)簽名生成和環(huán)簽名驗證.

? 系統(tǒng)初始化算法(Setup(λ)→params): 一個概率多項式時間(PPT) 算法, 其輸入為安全參數(shù)λ,輸出系統(tǒng)參數(shù)Params.

? 密鑰生成算法(KeyGen(λ, params)→(PK, sk)): 一個PPT 算法, 輸入為安全參數(shù)λ和系統(tǒng)參數(shù)params, 輸出用戶的公鑰PK 和私鑰sk.

? 環(huán)簽名生成(RSign(M,n,S,skπ)→σ): 一個PPT 算法, 其輸入為待簽名消息M、n個成員公鑰組成的集合S={PK1,PK2,··· ,PKn}以及簽名者私鑰skπ(1≤π ≤n), 輸出簽名值σ.

? 環(huán)簽名驗證(RVerify(M,S,σ)→accept/reject): 一個確定性算法, 其輸入為簽名消息M、公鑰集合S以及簽名值σ, 若σ是M的有效環(huán)簽名輸出accept, 否則輸出reject.

定義2 (可鏈接環(huán)簽名) 具有鏈接性的環(huán)簽名稱為可鏈接環(huán)簽名, 在環(huán)簽名的基礎(chǔ)上, 可鏈接環(huán)簽名不僅包含系統(tǒng)初始化、密鑰生成、可鏈接環(huán)簽名生成、可鏈接環(huán)簽名驗證, 還包含鏈接算法.

? 系統(tǒng)初始化算法(Setup(λ)→params): 一個概率多項式時間(PPT) 的算法, 其輸入為安全參數(shù)λ, 輸出系統(tǒng)參數(shù)params.

? 密鑰生成算法(KeyGen(λ)→(PK, sk)): 一個PPT 算法, 其輸入為安全參數(shù)λ和系統(tǒng)參數(shù)params, 輸出用戶的公鑰PK 和私鑰sk.

? 可鏈接環(huán)簽名生成(LRSign(M,n,S,skπ)→(σ,Qπ)): 一個PPT 算法, 其輸入為消息M、n個成員組成的公鑰集合S={PK1,PK2,··· ,PKn}以及簽名者私鑰skπ(1≤π ≤n), 輸出簽名值σ和鏈接標(biāo)簽Qπ.

? 可鏈接環(huán)簽名驗證(LRVerify(params,M,S,σ,Qπ)→accept/reject): 一個多項式時間的確定性算法, 其輸入為系統(tǒng)參數(shù)params、簽名消息M、環(huán)成員公鑰集合S、簽名值σ和鏈接標(biāo)簽Qπ, 若(σ,Qπ) 是關(guān)于M的有效簽名, 則輸出accept; 否則, 輸出reject.

? 鏈接算法(Link(S,M1,M2,σ1,Q1,σ2,Q2)→linked/unlinked: 一個確定性算法, 輸入用戶公鑰集合S、兩個不同的簽名消息M1,M2及其分別對應(yīng)的可鏈接環(huán)簽名(σ1,Q1),(σ2,Q2), 若σ1,σ2是有效的環(huán)簽名且有相同的鏈接標(biāo)簽Q1=Q2, 輸出linked, 否則輸出unlinked.一個安全的環(huán)簽名方案需要滿足以下3 個性質(zhì):

? 正確性: 由“環(huán)簽名生成” 算法輸出的簽名值作為“環(huán)簽名驗證” 算法的輸入, 總是輸出accept.環(huán)簽名方案的不可偽造性和無條件匿名性通過模擬器S和敵手A之間的游戲定義, 下面首先介紹A可查詢的諭言機(jī)JO、CO、SO.

– 加入諭言機(jī)(JO(⊥)→PK): 通過此查詢, 一個新用戶被添加到系統(tǒng)并輸出新用戶的公鑰PK.

– 腐化諭言機(jī)(CO(PKi)→ski): 輸入用戶的公鑰PKi, 輸出對應(yīng)的私鑰ski.

– 簽名諭言機(jī) (SO(M,n,S,PKπ)→ σ): 輸入簽名消息M, 大小為n的公鑰集合S={PK1,PK2,··· ,PKn}, 簽名者公鑰PKπ(1≤n ≤π), 返回有效的環(huán)簽名σ.

Pointcheval 等人最早基于“諭言重放攻擊” 技術(shù)的分叉引理給出了數(shù)字簽名方案的安全性證明[39], 諭言重放攻擊是通過重放敵手一個有效的攻擊實現(xiàn), 該敵手是一個概率多項式時間的圖靈機(jī), 能夠使用不同的隨機(jī)諭言機(jī)獲得關(guān)于同一個消息m的兩個簽名(δ0,h0,σ0) 和(δ1,h1,δ1),其中σ0,σ1分別是攻擊者通查詢環(huán)簽名生成諭言機(jī)輸出的兩個簽名值, (δ0,h0),(δ1,h1) 分別是計算兩個簽名值過程中的中間值,h0,h1為隨機(jī)諭言機(jī)的輸出, 且有δ0=δ1,h ?=h′. 根據(jù)上述兩個簽名就可以得到一個困難問題的解.

在一般環(huán)簽名(generic ring signature) 的定義下, Herranz 等人使用基于“諭言重放攻擊” 技術(shù)的分叉引理證明了環(huán)簽名方案的不可偽造性[40]. 一般環(huán)簽名的定義如下:

定義3 (一般環(huán)簽名) 一般環(huán)簽名的定義與本文所定義的環(huán)簽名都包含4 個基本算法: 系統(tǒng)初始化算法、密鑰生成算法、環(huán)簽名生成以及環(huán)簽名驗證. 關(guān)鍵之處在于一般環(huán)簽名對簽名值的生成過程提出了更具體的要求: 輸入消息M、n個成員的公鑰(A1,A2,··· ,An)、簽名者私鑰skπ(1≤π ≤n) 以及安全的哈希函數(shù), 通過產(chǎn)生一組r1,r2,··· ,rn,h1,h2,··· ,hn, 最終輸出簽名值σ. 其中ri ?=rj,i ?=j,hi(1≤i ≤n) 是由m,ri(1≤i ≤n) 以及環(huán)成員的公鑰確定的哈希值,簽名值σ完全由r1,r2,··· ,rn,h1,h2,··· ,hn和消息m決定.

下面給出在一般環(huán)簽名的定義下不可偽造性的概念.

? 不可偽造性: 環(huán)簽名的不可偽造性通過模擬器S和敵手A之間的下述游戲定義:

–S生成系統(tǒng)參數(shù)params 并將其發(fā)送給A;

–A適應(yīng)性查詢諭言機(jī)JO、CO、SO 以及隨機(jī)諭言機(jī)H;(2)S?中所有的公鑰均通過查詢加入諭言機(jī)JO 得到;

(3)S?中所有的公鑰都沒有被腐化查詢, 即敵手沒有得到S?中任意環(huán)成員的私鑰;

(4)σ?不是通過查詢簽名諭言機(jī)SO 得到.如果對任意PPT 的敵手A來說, 贏得上述游戲的概率是可忽略的, 則稱環(huán)簽名方案是不可偽造的.

? 無條件匿名性: 環(huán)簽名方案的無條件匿名性通過模擬器S和有無限計算力的敵手A之間的游戲

定義:

–S生成系統(tǒng)參數(shù)params 并將其發(fā)送給A.

–A可適應(yīng)性查詢加入諭言機(jī)JO.的基數(shù), 則稱環(huán)簽名滿足無條件匿名性.可鏈接環(huán)簽名不僅滿足上述正確性、不可偽造性和無條件匿名性, 還需要具備可鏈接性和不可誹謗性.

? 鏈接性: 鏈接性是可鏈接環(huán)簽名的必備性質(zhì), 即一個簽名者不能生成兩個有不同鏈接標(biāo)簽的簽名值. 鏈接性通過模擬器S和敵手A之間的下述游戲定義:

–S生成系統(tǒng)參數(shù)params 并將其發(fā)送給A;

–A可適應(yīng)性查詢諭言機(jī)JO、CO、SO;

–A輸出兩組可鏈接環(huán)簽名值(S,M1,σ1,Q1) 和(S,m2,σ2,Q2).稱A贏得了上述游戲如果滿足以下4 個條件:

(1) 集合S中的公鑰均是通過查詢加入諭言機(jī)JO 得到;

(2)A向腐化諭言機(jī)CO 查詢S中公鑰對應(yīng)的私鑰不超過兩次, 即敵手A最多獲取S中一個用戶的私鑰;

(3) (σ1,Q1),(σ2,Q2) 分別是關(guān)于消息M1,M2的有效環(huán)簽名, 即LRVerify(M1,S,σ1,Q1)→accept, LRVerify(M2,S,σ2,Q2)→accept, 并且σ1,σ2不是簽名諭言機(jī)SO 的輸出值;

(4) Link(S,M1,M2,σ1,σ2)→unlinked.

如果對任意PPT 的敵手A來說, 贏得上述游戲的概率是可忽略的, 則稱可鏈接環(huán)簽名滿足鏈接性.

? 不可誹謗性: 不可誹謗性指敵手A不能生成與真實簽名者簽名相同的簽名標(biāo)簽, 這一性質(zhì)保證了

A不能陷害真實簽名者. 不可誹謗性通過模擬器S和敵手A之間的下述游戲定義:

–S生成系統(tǒng)參數(shù)params 并將其發(fā)送給A.

–A可適應(yīng)性查詢加入諭言機(jī)JO.

–A將簽名消息M,n個用戶公鑰組成的集合S={PK1,PK2,··· ,PKn}以及隨機(jī)選擇的π ∈{1,2,··· ,n}發(fā)送給S, 其中用戶π的公鑰PKπ沒有被腐化查詢或沒有作為簽名查詢SO查詢中的輸入;S使用PKπ對應(yīng)的私鑰skπ執(zhí)行可鏈接環(huán)簽名生成算法LRSign(M,n,S,skπ),最后將生成的簽名值{σ,Q}發(fā)送給A.

–A適應(yīng)性查詢諭言機(jī)JO、CO、SO.

(1) LRVerify(params,M?,S,σ?,Q?)=accept;

(2)σ?不是簽名諭言機(jī)SO 的輸出;

(3)S?中的公鑰都是加入諭言機(jī)JO 的輸出;

(4) PKπ沒有被敵手腐化查詢;

(5) Link(S,M,M?,σ,Q,σ?,Q?)→linked.

如果對任意PPT 的敵手A來說, 贏得上述游戲的概率是可忽略的, 則稱可鏈接環(huán)簽名方案滿足不可誹謗性.

本小節(jié)最后給出橢圓曲線上的離散對數(shù)問題.

橢圓曲線離散對數(shù)問題(ECDLP): 給定橢圓曲線E(Fp) 上任意兩點(diǎn)P,Q, 求解滿足等式Q=x·P的值x是多項式時間內(nèi)不可解的.

2.2 SM2 數(shù)字簽名算法

本節(jié)介紹SM2 數(shù)字簽名算法的4 個階段: 系統(tǒng)參數(shù)生成、密鑰生成、簽名和驗證.

3 基于SM2 數(shù)字簽名算法的環(huán)簽名方案

3.1 SM2 環(huán)簽名方案

環(huán)簽名方案因其“環(huán)簽名生成算法” 生成的某些值按一定規(guī)則構(gòu)成一個環(huán)狀而得名, 本文以Rivest 等人提出的環(huán)簽名概念為基準(zhǔn), 基于SM2 數(shù)字簽名算法設(shè)計了一個安全的環(huán)簽名方案, 下面給出SM2 環(huán)簽名方案的4 個算法.

算法1 SM2 環(huán)簽名生成算法Input: m,L = {P1,P2,··· ,Pn},dπ Output: 環(huán)簽名σL(m) = (c1,s1,s2,··· ,sn)1 產(chǎn)生隨機(jī)數(shù)kπ ∈Z?q, 計算cπ+1 = H1(L,m,kπ ·G);2 對i = π+1,··· ,n,1,··· ,π ?1,, 依次執(zhí)行以下運(yùn)算:3 隨機(jī)產(chǎn)生si ∈Z?q, 計算Zi = si·G+(si+ci)·Pi,ci+1 = H1(L,m,Zi), 其中記c1 = cn+1;4 計算sπ = ((1+dπ)?1 ·(kπ ?cπ ·dπ)) mod q;5 輸出在L 上關(guān)于m 的環(huán)簽名(c1,s1,s2,··· ,sn).

3.2 SM2 可鏈接環(huán)簽名

本節(jié)在SM2 環(huán)簽名方案的基礎(chǔ)上, 通過嵌入安全的簽名標(biāo)簽, 設(shè)計了基于SM2 數(shù)字簽名算法的可鏈接環(huán)簽名方案極其兩種變型方案, 下面介紹SM2 可鏈接環(huán)簽名方案的5 個算法: 系統(tǒng)初始化算法、密鑰生成算法、可鏈接環(huán)簽名生成、可鏈接環(huán)簽名驗證和鏈接算法.

? 系統(tǒng)初始化算法: 該算法輸入安全參數(shù)λ,輸出系統(tǒng)參數(shù)params={p,Fp,E(Fp),G,G,q,H1,Hp},其中p是大素數(shù),E(Fp) 是定義在有限域Fp上的橢圓曲線, G 表示橢圓曲線上的點(diǎn)構(gòu)成的加法循環(huán)群,G是循環(huán)群G 的生成元, 階為素數(shù)q,H1:{0,1}?→Z?q,Hp:{0,1}?→G 是兩個安全的哈希函數(shù).

圖1 環(huán)結(jié)構(gòu)Figure 1 Ring structure

? 可鏈接環(huán)簽名生成: 簽名者任意選取n?1 個用戶公鑰,加上自身公鑰構(gòu)成群組L={P1,P2,··· ,Pn}; 簽名者為其中第π(1≤π ≤r) 個用戶, 利用私鑰dπ和環(huán)成員公鑰L生成對消息m的可鏈接環(huán)簽名, 如算法2:

算法2 SM2 可鏈接環(huán)簽名生成算法Input: m,L = {P1,P2,··· ,Pn},dπ Output: 可鏈接環(huán)簽名σL(m) = (Qπ,c1,s1,s2,··· ,sn)1 計算簽名標(biāo)簽Qπ: R = Hp(L),Qπ = dπ ·R;2 隨機(jī)選取kπ ∈Z?q, 計算cπ+1 = H1(L,Qπ,m,kπ ·G,kπ ·R);3 對i = π+1,··· ,n,1,··· ,π ?1, 隨機(jī)產(chǎn)生si ∈Z?q, 并依次計算Vi = si·G+(si+ci)·Pi,Wi = si·R+(si+ci)·Qπ,ci+1 = H1(L,Qπ,m,Vi,Wi), 其中記c1 = cn+1;4 計算sπ = ((1+dπ)?1 ·(kπ ?cπ ·dπ)) mod q;5 輸出可鏈接環(huán)簽名(Qπ,c1,s1,s2,··· ,sn).

? 可鏈接環(huán)簽名驗證: 為了檢驗收到的消息m′及其可鏈接環(huán)簽名(c′1,s′1,s′2,··· ,s′n,Q′π), 驗證者實現(xiàn)以下步驟:

– 計算R=Hp(L);

下面給出SM2 可鏈接環(huán)簽名方案的兩種變型.

算法3 SM2 可鏈接環(huán)簽名變型一Input: m,L = {P1,P2,··· ,Pn},dπ Output: 可鏈接環(huán)簽名σL(m) = (Qπ,c1,s1,s2,··· ,sn)1 計算簽名標(biāo)簽Qπ: R = Hp(L),Qπ = dπ ·R;2 隨機(jī)選取kπ ∈Z?q, 計算cπ+1 = H1(L,Qπ,m,kπ ·(G+R));3 對i = π+1,··· ,n,1,··· ,π ?1, 隨機(jī)產(chǎn)生si ∈Z?q, 并依次計算Zi = (si +ci)·(Pi +Qπ)+si ·(G+R),4 ci+1 = H1(L,Qπ,m,Zi), 其中記c1 = cn+1;5 計算sπ = ((1+dπ)?1 ·(kπ ?cπ ·dπ)) mod q;6 輸出可鏈接環(huán)簽名(Qπ,c1,s1,s2,··· ,sn).

算法4 SM2 可鏈接環(huán)簽名變型二Input: m,L = {P1,P2,··· ,Pn},dπ Output: 可鏈接環(huán)簽名σL(m) = (Qπ,c1,s1,s2,··· ,sn)1 計算簽名標(biāo)簽Qπ: R = Hp(L),Qπ = dπ ·R;2 隨機(jī)選取kπ ∈Z?q, 計算(xπ,yπ) = kπ ·(G+R),cπ+1 = (H1(L,Qπ,m)+xπ) mod q;3 對i = π+1,··· ,n,1,··· ,π ?1, 隨機(jī)產(chǎn)生si ∈Z?q, 并依次計算Zi = (xi,yi) = (si +ci)·(Pi +Qπ)+si ·(G+R),4 ci+1 = (H1(L,Qπ,m)+xi) mod q, 其中記c1 = cn+1;5 計算sπ = ((1+dπ)?1 ·(kπ ?cπ ·dπ)) mod q;6 輸出可鏈接環(huán)簽名(Qπ,c1,s1,s2,··· ,sn).

4 安全性分析

本節(jié)主要證明SM2 (可鏈接) 環(huán)簽名方案的正確性、不可偽造性、無條件匿名性以及SM2 可鏈接環(huán)簽名方案的鏈接性、不可誹謗性.

定理1 SM2 環(huán)簽名方案滿足正確性.

證明: 假定簽名σL(m) = (c1,s1,s2,··· ,sn) 按照算法1 產(chǎn)生, 驗證者根據(jù)環(huán)簽名驗證算法進(jìn)行驗證, 則有:

因此滿足c1=cn+1, 正確性得證.

為了證明本文中的方案在隨機(jī)諭言模型下抵抗適應(yīng)性選擇消息攻擊, 首先分析本文的方案滿足一般環(huán)簽名的概念, 然后證明在橢圓曲線離散對數(shù)問題困難的假設(shè)下, 本文提出的方案滿足不可偽造性.

分析: 在SM2 環(huán)簽名方案中,算法1 展示了簽名值的生成過程: 輸入為消息m、公鑰L={P1,P2,···,Pn}、私鑰skπ以及哈希函數(shù)H1, 中間值為(Z1,Z2,··· ,Zn,c1,c2,··· ,cn), 輸出的簽名值為σ=(c1,s1,s2,··· ,sn). 其中,ci+1=H1(L,m,Zi) 顯然是由L,m,Zi確定的哈希值, 從而SM2 環(huán)簽名是文獻(xiàn)[40] 定義的一般環(huán)簽名的一個實例, 因此分叉引理適用. 同理可分析SM2 可鏈接環(huán)簽名方案也滿足一般環(huán)簽名的定義. 下面主要介紹SM2 環(huán)簽名方案的不可偽造性.

定理2 若橢圓曲線離散對數(shù)問題(DLP) 是困難的, 則SM2 環(huán)簽名具有不可偽造性.

(G,Q) 問題可解, 與假設(shè)矛盾, 定理得證.

定理3 SM2 環(huán)簽名方案滿足無條件匿名性.

可鏈接環(huán)簽名方案的正確性、不可偽造性、無條件匿名性證明過程與環(huán)簽名方案相似, 下面主要證明SM2 可鏈接環(huán)簽名的可鏈接性和不可誹謗性.

定理4 假設(shè)離散對數(shù)問題(DLP) 是困難的, 則在隨機(jī)諭言機(jī)模型下SM2 可鏈接環(huán)簽名具有鏈接性.

定理5 SM2 可鏈接環(huán)簽名滿足不可誹謗性.

5 效率分析

5.1 通信量

5.2 計算量

本節(jié)分別統(tǒng)計SM2 環(huán)簽名方案和SM2 可鏈接環(huán)簽名方案的計算量與環(huán)成員數(shù)量的關(guān)系, 如表1 所示.

表1 SM2 環(huán)簽名方案的計算量Table 1 Computation quantity for SM2 ring signature schemes

圖2 通信量與環(huán)成員數(shù)量關(guān)系Figure 2 Relationship between communication cost and number of ring members

針對SM2 環(huán)簽名方案, 假設(shè)環(huán)成員數(shù)量為n, 以循環(huán)群G 上的點(diǎn)乘、點(diǎn)加、H1運(yùn)算以及Zq上逆運(yùn)算的計算量統(tǒng)計計算復(fù)雜度. SM2 環(huán)簽名過程中, 生成cπ+1時包含一次G 上點(diǎn)乘運(yùn)算、一次H1運(yùn)算,生成與其他n ?1 個ci(1≤i ≤n,i ?=n) 時包含2n ?2 次G 上點(diǎn)乘、n ?1 次G 上點(diǎn)加和n ?1 次H1運(yùn)算, 最后生成sπ時包含一次Zq上逆運(yùn)算; 驗證過程包含n次G 上點(diǎn)加、2n次G 上點(diǎn)乘和n次H1運(yùn)算.

針對SM2 可鏈接環(huán)簽名方案, 假設(shè)環(huán)成員數(shù)量為n, 以循環(huán)群G 上的點(diǎn)乘、點(diǎn)加、H1運(yùn)算以及Zq上逆運(yùn)算的計算量統(tǒng)計計算復(fù)雜度.SM2 可鏈接環(huán)簽名生成過程中, 首先計算鏈接標(biāo)簽Qπ需要1 次Hp運(yùn)算、1 次G 上點(diǎn)乘運(yùn)算; 然后計算cπ+1包含2 次點(diǎn)乘運(yùn)算、1 次H1運(yùn)算, 計算其他n ?1 個ci(1≤i ≤n,i ?=n) 時總共包含4n ?4 次點(diǎn)乘、2n ?2 次點(diǎn)加和n ?1 次H1運(yùn)算, 最后生成sπ時包含一次Zq上的逆運(yùn)算; 可鏈接環(huán)簽名驗證過程包含1 次Hp運(yùn)算、4n次G 上點(diǎn)乘、2n次點(diǎn)加和n次H1運(yùn)算.

6 結(jié)束語

環(huán)簽名是一種特殊的數(shù)字簽名, 它允許一個成員代表一組人進(jìn)行簽名而不泄漏簽名者的信息, 實現(xiàn)了簽名的無條件匿名性, 可以保護(hù)用戶的隱私; 可鏈接環(huán)簽名是一種具有簽名人關(guān)聯(lián)性的環(huán)簽名, 實現(xiàn)了簽名的無條件匿名性和可鏈接性, 即保護(hù)用戶隱私的同時保證了簽名的可鏈接性. 環(huán)簽名/可鏈接環(huán)簽名在電子投票、數(shù)字貨幣等多個領(lǐng)域有著廣泛應(yīng)用. 科研人員已經(jīng)提出了多種不同形式和不同特性的環(huán)簽名算法, 但沒有基于SM2 數(shù)字簽名算法的環(huán)簽名. 為了推廣SM2 數(shù)字簽名算法在這些領(lǐng)域的應(yīng)用, 本文提出了基于SM2 數(shù)字簽名算法的環(huán)簽名/可鏈接環(huán)簽名, 并證明了其安全性, 具有安全性高、實現(xiàn)簡單、易驗證的特點(diǎn). 下一步的工作重點(diǎn)是減弱環(huán)簽名通信量、計算量與環(huán)成員數(shù)量的關(guān)系, 如對數(shù)關(guān)系甚至與環(huán)成員數(shù)量無關(guān).