湯永利, 夏菲菲, 葉 青, 王永軍, 張曉航

1. 河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 焦作454003

2. 河南工業(yè)和信息化職業(yè)學(xué)院, 焦作454000

1 引言

近年來, 區(qū)塊鏈[1]技術(shù)已經(jīng)在人類生活的各個(gè)方面得到應(yīng)用, 在一定程度上解決了相互不信任的個(gè)體之間的協(xié)作與價(jià)值流轉(zhuǎn). 然而區(qū)塊鏈上數(shù)據(jù)的傳輸和存儲(chǔ)都是公開可見的, 可以提供任意信息的查詢, 僅通過“偽匿名” 的形式對(duì)交易雙方的隱私進(jìn)行保護(hù), 無法實(shí)現(xiàn)完備的隱私保護(hù)需求. 為了滿足這一應(yīng)用需求, 《中國(guó)區(qū)塊鏈技術(shù)和應(yīng)用發(fā)展白皮書》[2]明確提出: 環(huán)簽名比較有希望解決區(qū)塊鏈的隱私保護(hù)問題,從而滿足用戶身份匿名性及交易信息不可偽造性的需求.

Rivest 等[3]在2001 年提出第一個(gè)環(huán)簽名方案, 他們給出了基于Rabin 陷門函數(shù)和RSA 陷門置換的環(huán)簽名, 并在隨機(jī)諭言機(jī)模型下證明所提方案的安全性. 在環(huán)簽名中, 任意用戶可以代表整個(gè)環(huán)對(duì)任意消息進(jìn)行簽名, 獲取環(huán)公鑰的任意驗(yàn)證者都可以驗(yàn)證簽名是否來自此環(huán), 但無法確定具體是哪個(gè)成員生成的簽名. 將環(huán)簽名應(yīng)用于區(qū)塊鏈, 可以有效保護(hù)用戶的身份隱私. 值得注意的是若僅采用普通的環(huán)簽名體制解決區(qū)塊鏈中的隱私保護(hù)問題, 資金持有者在環(huán)簽名的庇護(hù)下, 可以對(duì)同一筆資金簽名(即花費(fèi)) 多次,而不能被檢測(cè)出來, 即出現(xiàn)所謂的“雙重花費(fèi)” 問題. 為了避免出現(xiàn)該問題, 應(yīng)采用可檢測(cè)兩個(gè)簽名是否為同一用戶所簽的可鏈接環(huán)簽名. 2004 年, Liu 等[4]對(duì)基本的環(huán)簽名方案添加可鏈接屬性, 基于離散對(duì)數(shù)假設(shè)提出了第一個(gè)隨機(jī)諭言機(jī)模型下的可鏈接環(huán)簽名. 2006 年, Au 等[5]基于累加器技術(shù)提出了簽名尺寸為常數(shù)的可鏈接環(huán)簽名, Yuen 等[6]在2013 年提出了第一個(gè)標(biāo)準(zhǔn)模型下基于橢圓曲線配對(duì)技術(shù)的可鏈接環(huán)簽名, 2014 年Liu 等[7]提出了具有無條件匿名性的可鏈接環(huán)簽名, 并給出形式化安全模型定義與證明,但上述可鏈接環(huán)簽名均基于公鑰證書, 存在密鑰管理負(fù)擔(dān), 難以避免復(fù)雜的用戶公鑰證書管理問題.

Shamir 在1984 年提出了基于身份的密碼體制[8], 在基于身份的密碼體制中, 密鑰生成中心(key generation center,KGC)根據(jù)用戶的身份信息(例如: 身份證號(hào)、郵箱地址等)生成該用戶公鑰,根據(jù)系統(tǒng)主密鑰和用戶的身份信息進(jìn)行計(jì)算生成對(duì)應(yīng)的私鑰, 避免了傳統(tǒng)公鑰基礎(chǔ)設(shè)施(public key infrastructure,PKI) 體系中用戶公鑰證書復(fù)雜的管理問題. Zhang 等[9]在2002 年提出了第一個(gè)基于身份的環(huán)簽名方案, 之后基于身份的環(huán)簽名方案[10–13]被相繼提出. 2013 年, Au 等[14]給出了第一個(gè)基于身份的可鏈接環(huán)簽名, 且簽名長(zhǎng)度為常數(shù), 使用離散對(duì)數(shù)難題(discrete logarithm problem, DLP) 等困難假設(shè)在隨機(jī)諭言機(jī)模型下證明所提方案的安全性. 由于量子計(jì)算技術(shù)帶來的威脅, 傳統(tǒng)基于數(shù)論難題(例如: 大整數(shù)因子分解難題、有限域離散對(duì)數(shù)難題) 的密碼體制將會(huì)被攻破, 若環(huán)簽名仍采用基于數(shù)論難題進(jìn)行構(gòu)造, 在量子時(shí)代, 環(huán)簽名的安全性將難以保證. 近幾年, 基于格理論構(gòu)造的新型密碼體制因其具有較好的漸進(jìn)效率、可并行化、運(yùn)算簡(jiǎn)單、抗量子攻擊和存在最壞情況下的隨機(jī)實(shí)例等優(yōu)點(diǎn), 成為后量子密碼時(shí)代的研究熱點(diǎn), 而基于格的環(huán)簽名方案[15,16]也相繼被提出. 2018 年, Torres 等[17]提出了隨機(jī)諭言機(jī)模型下第一個(gè)基于格的一次可鏈接環(huán)簽名, 采用拒絕抽樣技術(shù)使得輸出簽名的分布與簽名私鑰的分布相互獨(dú)立, 使簽名生成的效率進(jìn)一步提高. 隨后, Torres 等[18]又在文獻(xiàn)[17] 方案的基礎(chǔ)上進(jìn)行擴(kuò)展給出了支持多輸入、多輸出的可鏈接環(huán)簽名方案, 實(shí)用性更強(qiáng). 2018 年, Baum 等[19]給出了格上更加簡(jiǎn)單、高效的可鏈接環(huán)簽名方案.

為了使基于身份的可鏈接環(huán)簽名能夠抵抗量子攻擊, 本文提出了一個(gè)格上基于身份的可鏈接環(huán)簽名.主要貢獻(xiàn)有:

(1) 將格密碼學(xué)與基于身份的可鏈接環(huán)簽名相結(jié)合, 構(gòu)造了隨機(jī)諭言機(jī)模型下安全的格上基于身份的可鏈接環(huán)簽名;

(2) 利用Gentry 等[20]提出的原像抽樣算法和Lyubashevsky[21]提出的拒絕抽樣技術(shù)分別生成用戶的私鑰及簽名, 提高了用戶密鑰和簽名的生成效率;

(3) 在隨機(jī)諭言機(jī)模型下證明本文所提的方案滿足無條件匿名性、不可偽造性及可鏈接性, 將所提可鏈接環(huán)簽名方案的不可偽造性歸約至格上小整數(shù)解(SIS) 困難假設(shè);

(4) 分別從時(shí)間開銷和存儲(chǔ)開銷兩個(gè)方面給出詳細(xì)的性能分析. 結(jié)果表明, 與格上的可鏈接環(huán)簽名方案相比, 本方案密鑰和簽名生成以及簽名驗(yàn)證的效率有了進(jìn)一步的提高.

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

2.1 符號(hào)說明

為表述方便對(duì)文中符號(hào)進(jìn)行說明, 如表1 所示.

表1 符號(hào)說明Table 1 Symbol description

除了表1 中的符號(hào), 文中還用到計(jì)算復(fù)雜度符號(hào)O, ω, 并定義了negl(n) 表示n 的可忽略函數(shù).

2.2 格的相關(guān)定義

2.3 困難假設(shè)

2.4 相關(guān)算法

2.5 拒絕抽樣技術(shù)

3 基于身份的可鏈接環(huán)簽名定義及安全模型

3.1 基于身份的可鏈接環(huán)簽名定義

一個(gè)基于身份的可鏈接環(huán)簽名方案[23]包括以下5 個(gè)概率多項(xiàng)式時(shí)間算法:

(1) Setup(1n): 由密鑰生成中心(KGC) 執(zhí)行, 輸入安全參數(shù)n, 輸出系統(tǒng)公開參數(shù)PP 和系統(tǒng)主密鑰MSK.

(2) KeyExt(IDi,MSK,PP): 由密鑰生成中心(KGC) 執(zhí)行, 輸入用戶身份IDi和系統(tǒng)主密鑰MSK以及系統(tǒng)公開參數(shù)PP, 輸出用戶身份IDi對(duì)應(yīng)的私鑰SIDi.

(3) Sign(PP,R,u,SIDi): 由簽名者執(zhí)行, 輸入公開參數(shù) PP, 構(gòu)成環(huán)的用戶身份集合 R =(ID1,ID2,··· ,IDl), 待簽消息u ∈{0,1}?以及簽名者身份IDi∈R 對(duì)應(yīng)的私鑰SIDi, 輸出環(huán)R 關(guān)于消息u 的可鏈接環(huán)簽名σR(u), 簽名σR(u) 包含可鏈接標(biāo)簽I, 對(duì)于同一簽名者產(chǎn)生的兩個(gè)可鏈接環(huán)簽名σR(u1), σR?(u2), 有I(1)= I(2).

(4) Verify(PP,R,u,σR(u)): 由驗(yàn)證者執(zhí)行, 輸入公開參數(shù) PP, 構(gòu)成環(huán)的用戶身份集合 R =(ID1,ID2,··· ,IDl), 待簽消息u ∈{0,1}?以及簽名σR(u). 若驗(yàn)證成功則輸出“Valid”, 否則輸出“Invalid”.

(5) Link(σR(u1),σR?(u2)): 由驗(yàn)證者執(zhí)行, 輸入簽名σR(u1), σR?(u2), 驗(yàn)證I(1)=I(2)是否成立.如果相等則輸出“Link”, 否則輸出“Unlink”.

3.2 安全模型

基于身份的可鏈接環(huán)簽名的安全性定義[23,24]除了滿足普通環(huán)簽名的正確性、匿名性和不可偽造性之外, 還要滿足可鏈接性. 可鏈接環(huán)簽名的正確性包括簽名驗(yàn)證正確性和鏈接正確性兩方面, 具體定義見定義4; 匿名性是指攻擊者無法確定簽名是由環(huán)中具體哪個(gè)成員生成, 具體定義見定義5; 不可偽造性是指在不知簽名者簽名私鑰的情況下, 環(huán)外成員無法代替真實(shí)簽名者進(jìn)行簽名, 具體定義見定義6; 可鏈接性是指只具有一個(gè)簽名私鑰的用戶無法給出兩個(gè)簽名能夠通過鏈接算法的檢測(cè), 具體定義見定義7. 我們用攻擊者A 與挑戰(zhàn)者S 之間進(jìn)行的一系列游戲來刻畫基于身份的可鏈接環(huán)簽名的安全性定義, 在隨機(jī)諭言機(jī)模型下, 攻擊者A 可以訪問隨機(jī)諭言機(jī)(Random Oracle) 并進(jìn)行以下兩種詢問:

(1) 私鑰詢問(Corruption Oracle): 攻擊者A 選擇用戶身份IDi發(fā)送給挑戰(zhàn)者S 進(jìn)行私鑰詢問, 挑戰(zhàn)者S 運(yùn)行密鑰提取算法KeyExt(IDi,MSK,PP) 生成IDi對(duì)應(yīng)的私鑰SIDi, 并將結(jié)果返回給攻擊者A.

(2) 簽名詢問(Singing Oracle): 攻擊者A 選擇一個(gè)環(huán)R = (ID1,ID2,··· ,IDl), 一個(gè)用戶身份IDk∈ R 和消息u ∈ {0,1}?發(fā)送給挑戰(zhàn)者S 進(jìn)行簽名詢問, 挑戰(zhàn)者S 運(yùn)行簽名算法Sign(PP,R,u,SIDk), 用IDk對(duì)應(yīng)的私鑰SIDk進(jìn)行簽名, 并將生成的簽名結(jié)果σR(u) 返回給攻擊者A.

定義4 (Correctness) 可鏈接環(huán)簽名的正確性包括簽名驗(yàn)證正確性和簽名鏈接正確性兩方面, 其中,驗(yàn)證正確性是指對(duì)于合法簽名σR(u), 驗(yàn)證算法Verify(PP,R,u,σR(u)) 輸出“Invalid” 的概率是可忽略的, 即:

鏈接正確性是指兩個(gè)簽名 (σR(u1), σR?(u2)) 若為用戶用同一個(gè)簽名私鑰生成, 鏈接算法Link(σR(u1),σR?(u2)) 輸出“Unlink” 的概率是可忽略的, 即:

匿名性(Anonymity) 可鏈接環(huán)簽名的匿名性用如下攻擊者A 與挑戰(zhàn)者S 之間進(jìn)行的游戲來刻畫.

(1) 系統(tǒng)建立: 輸入安全參數(shù)n, 挑戰(zhàn)者S 運(yùn)行系統(tǒng)建立算法Setup(1n) 得到系統(tǒng)公開參數(shù)PP 和系統(tǒng)主密鑰MSK, 并將公開參數(shù)PP 發(fā)送給攻擊者A.

(2) 詢問階段: 攻擊者A 可以進(jìn)行多項(xiàng)式次訪問諭言機(jī), 并進(jìn)行如上私鑰詢問及簽名詢問.

(3) 挑戰(zhàn)階段: 攻擊者A 輸入環(huán)用戶身份集合R = (ID1,ID2,··· ,IDl) 和待簽消息u ∈{0,1}?, 兩個(gè)用戶身份IDi0, IDi1∈R 進(jìn)行簽名詢問, 挑戰(zhàn)者S 隨機(jī)選擇b ∈{0,1} 計(jì)算IDib對(duì)應(yīng)的私鑰SIDib, 運(yùn)行簽名算法用簽名私鑰SIDib對(duì)消息u 進(jìn)行簽名, 將生成的簽名結(jié)果σR(u) 返回給攻擊者A.

(4) 猜測(cè)階段: 攻擊者A 輸出b?作為對(duì)簽名人身份的猜測(cè), 如果b=b?則攻擊者A 贏得游戲.則攻擊者A 贏得匿名性游戲. 攻擊者A 贏得匿名性游戲的優(yōu)勢(shì)定義為:

定義5 (Anonymity) 當(dāng)對(duì)于任意多項(xiàng)式時(shí)間攻擊者A, A是可忽略的, 則稱一個(gè)可鏈接環(huán)簽名方案是匿名的.

不可偽造性(Unforgeability) 可鏈接環(huán)簽名的不可偽造性用如下攻擊者A 與挑戰(zhàn)者S 之間進(jìn)行的游戲來刻畫.

(1) 系統(tǒng)建立: 輸入安全參數(shù)n, 挑戰(zhàn)者S 運(yùn)行系統(tǒng)建立算法Setup(1n) 得到系統(tǒng)公開參數(shù)PP 和系統(tǒng)主密鑰MSK, 并將公開參數(shù)PP 發(fā)送給攻擊者A, 將系統(tǒng)主密鑰MSK 保密.

(2) 詢問階段: 攻擊者A 可以進(jìn)行多項(xiàng)式次訪問諭言機(jī), 并進(jìn)行如上私鑰詢問及簽名詢問.

(3) 偽造階段: 攻擊者A 給出(u?,R?,σR?(u?)), 若滿足以下條件:

(a) Verify(u?,R?,σR?(u?))=“Valid”;

(b) 攻擊者A 未詢問過環(huán)R?中任一用戶的私鑰;

(c) 攻擊者A 未發(fā)起過(u?,R?) 的簽名詢問;

(d) 環(huán)R?中任一用戶的公鑰均由挑戰(zhàn)者S 給出.則攻擊者A 贏得不可偽造性游戲. 攻擊者A 贏得不可偽造性游戲的優(yōu)勢(shì)定義為:

定義6 (Unforgeability) 對(duì)于任意多項(xiàng)式時(shí)間攻擊者A,是可忽略的, 則稱一個(gè)可鏈接環(huán)簽名方案是不可偽造的.

可鏈接性(Linkability) 可鏈接環(huán)簽名的可鏈接性用如下攻擊者A 與挑戰(zhàn)者S 之間進(jìn)行的游戲來刻畫.

(1) 系統(tǒng)建立: 輸入安全參數(shù)n, 挑戰(zhàn)者S 運(yùn)行系統(tǒng)建立算法Setup(1n) 得到系統(tǒng)公開參數(shù)PP 和系統(tǒng)主密鑰MSK, 并將公開參數(shù)PP 發(fā)送給攻擊者A, 將系統(tǒng)主密鑰MSK 保密.

(2) 詢問階段: 攻擊者A 可以進(jìn)行多項(xiàng)式次訪問諭言機(jī), 并進(jìn)行如上私鑰詢問及簽名詢問.

4 方案構(gòu)造

為解決現(xiàn)有基于身份的可鏈接環(huán)簽名不能抵抗量子攻擊的問題, 本文基于原像抽樣和拒絕抽樣等技術(shù)構(gòu)造了一個(gè)格上基于身份的可鏈接環(huán)簽名. 本文核心思想是將基于身份的密碼學(xué)引入在Torres 等[17]提出的基于格的可鏈接環(huán)簽名方案中, 在系統(tǒng)建立階段用陷門生成算法[20]獲取系統(tǒng)主密鑰, 在密鑰提取階段釆用原像抽樣[20]技術(shù)獲取用戶私鑰, 在簽名生成階段采用拒絕抽樣技術(shù)[21]以一定的概率生成簽名.本文所構(gòu)造的方案具體描述如下:

5 安全性證明

定理2 (Correctness) 本文提出的格上基于身份的可鏈接環(huán)簽名是正確的.

證明: 下面將從簽名驗(yàn)證正確性及鏈接正確性兩方面證明本方案滿足正確性.

(1) 驗(yàn)證正確性: 由可鏈接環(huán)簽名的生成過程我們有:

由于序列{Ci} (i=1,2,··· ,l) 在可鏈接環(huán)簽名驗(yàn)證過程中與簽名過程中相同, 我們有C1=Cl+1.

因此, 本方案滿足簽名驗(yàn)證正確性.

(2) 鏈接正確性: 一個(gè)用戶用自己的私鑰SIDi簽署兩條消息u1,u2生成兩個(gè)簽名σR(u1), σR?(u2),σR(u1), σR?(u2) 分別包含對(duì)應(yīng)的可鏈接標(biāo)簽I(1), I(2). 則鏈接算法進(jìn)行驗(yàn)證時(shí)必然輸出為“Link”.

分析: 簽署消息u1的可鏈接標(biāo)簽為I(1)=H2(C,r), 簽署消息u2的可鏈接標(biāo)簽為I(2)=H2(C,r),由于, I(1), I(2)的產(chǎn)生均用同一個(gè)隨機(jī)選取的矩陣C, 若簽名者用相同的私鑰r 簽署消息u1, u2則必有I(1)=I(2).

因此, 本方案滿足簽名鏈接正確性.

綜上所述, 本文提出的格上基于身份的可鏈接環(huán)簽名滿足正確性.

定理3 (Anonymity) 對(duì)于任意多項(xiàng)式時(shí)間攻擊者A, 本方案在隨機(jī)諭言機(jī)模型下是無條件匿名的.

證明: 通過挑戰(zhàn)者S 和攻擊者A 之間進(jìn)行游戲交互完成無條件匿名性證明. Game0模擬挑戰(zhàn)者S對(duì)身份IDi0進(jìn)行簽名, Game1模擬挑戰(zhàn)者S 對(duì)身份IDi1進(jìn)行簽名. 如果攻擊者A 對(duì)兩個(gè)簽名的離散高斯分布不可區(qū)分, 那么本文方案滿足無條件匿名性.

Game0游戲:

(3) 挑戰(zhàn)者S 運(yùn)行簽名算法Sign(PP,R,u,SIDi0), 生成簽名σR(u) = (C1,t1,··· ,tl,I,b) 并發(fā)送給攻擊者A.

(4) 攻擊者A 收到簽名后給出關(guān)于b 的猜測(cè).

Game1游戲:

定理4 (Unforgeability) 如果SIS 問題是困難的, 對(duì)于任意多項(xiàng)式時(shí)間攻擊者A, 本方案在隨機(jī)諭言機(jī)模型下是不可偽造的.

證明: 通過挑戰(zhàn)者S 和攻擊者A 之間進(jìn)行游戲交互完成不可偽造性證明. 假設(shè)攻擊者A 能夠以不可忽略的概率ε 成功偽造簽名, 下面將展示挑戰(zhàn)者S 如何利用攻擊者A 的偽造結(jié)果找到一個(gè)短向量e, 構(gòu)造一個(gè)SIS 問題的解.

攻擊者A 與挑戰(zhàn)者S 之間的游戲交互如下:

故//e//≤2σ2(m+1), 令β = 2σ2(m+1), 短向量e 即是SIS(n,m,β) 的解.

概率分析: 假設(shè)攻擊者A 能夠成功偽造一個(gè)合法環(huán)簽名的概率為ε, 允許進(jìn)行私鑰詢問的最大次數(shù)為qE. 下面分析S 成功解決SIS 問題的概率ε?, 挑戰(zhàn)者S 會(huì)在下列情況下放棄游戲, 導(dǎo)致模擬失敗.

i) (R?,u?,T?,v?) 不在詢問列表L2中. 因?yàn)镠2是隨機(jī)諭言, 若A 沒有向S 提交過(R?,u?)詢問, 簽名σR?(u?) 通過驗(yàn)證C1=Cl+1的概率為1/(2d)l.

ii) tk?tk?=0(簽名σR(u) 對(duì)應(yīng)的簽名私鑰和偽造簽名σR?(u?) 對(duì)應(yīng)的簽名私鑰相等) 的概率為ε1, 由于攻擊者A 在不知道簽名私鑰的情況下, 簽名與簽名私鑰是相互獨(dú)立的, 因此簽名σR(u) 和σR?(u?) 的私鑰相等的概率ε1是可忽略的.

綜上所述, 挑戰(zhàn)者S 成功解決SIS 問題的概率ε?≥ε ?1/(2d)l?ε1.

定理5 (Linkability) 如果本方案是不可偽造的, 對(duì)于任意多項(xiàng)式時(shí)間攻擊者A, 本方案在隨機(jī)諭言機(jī)模型下是可鏈接的.

證明: 通過挑戰(zhàn)者S 和攻擊者A 之間進(jìn)行游戲交互完成可鏈接性證明. 根據(jù)可鏈接性的定義, 假設(shè)存在攻擊者A 能夠以不可忽略的概率ε 贏得定義7 中的可鏈接性游戲, 則攻擊者A 將與挑戰(zhàn)者S 進(jìn)行如下游戲交互:

(1) 挑戰(zhàn)者S 運(yùn)行系統(tǒng)建立算法Setup(1n) 得到系統(tǒng)公共參數(shù)PP、系統(tǒng)主密鑰MSK, 發(fā)送公共參

數(shù)PP 給攻擊者A.

(2) 攻擊者A 可以進(jìn)行多項(xiàng)式次的訪問諭言機(jī), 并進(jìn)行Hash 詢問、私鑰詢問及簽名詢問, 挑戰(zhàn)者S返回其詢問對(duì)應(yīng)的結(jié)果給攻擊者A.

1) Hash 詢問.

a. H1詢問: A 可以選擇用戶身份IDi∈R 進(jìn)行詢問, S 將aIDi返回給A.

6 性能分析

本文選擇三個(gè)代表性方案作為參照對(duì)象: 2017 年, Jia 等[15]提出的格上高效的基于身份的環(huán)簽名,2018 年, Torres 等[17]提出的第一個(gè)格上的可鏈接環(huán)簽名以及Baum 等[19]提出的格上更加簡(jiǎn)單、高效的可鏈接環(huán)簽名. 將從時(shí)間開銷與存儲(chǔ)開銷兩個(gè)方面分別對(duì)本文方案與以上三個(gè)方案進(jìn)行性能分析.

四種方案的時(shí)間開銷比較結(jié)果如表2 所示, 其中l(wèi) 代表環(huán)成員個(gè)數(shù), TTG,TSP,TSD,TBD,TLHL,TMUL,TINV分別表示算法TrapGen、SamplePre、SampleDom、格基委派算法(BasisDel)、剩余哈希定理(Leftover Hash Lemma, LHL)[25]、標(biāo)量乘法運(yùn)算及矩陣求逆運(yùn)算的單步平均耗時(shí). 主要從系統(tǒng)密鑰生成、用戶密鑰生成、簽名生成和簽名驗(yàn)證所消耗的時(shí)間分別進(jìn)行分析. 考慮矩陣標(biāo)量乘運(yùn)算、高斯采樣(SampleDom) 等相對(duì)耗時(shí)較多的計(jì)算過程, 忽略Hash 運(yùn)算、矩陣的加減法等相對(duì)耗時(shí)較少的運(yùn)算過程.在系統(tǒng)密鑰生成方面, 由于本文方案和文獻(xiàn)[15] 的方案均賦予了基于身份的屬性, 運(yùn)用陷門生成算法TTG生成系統(tǒng)主密鑰, 即系統(tǒng)主密鑰生成時(shí)間為TTG. 而文獻(xiàn)[17] 的方案和文獻(xiàn)[19] 的方案不是基于身份的可鏈接環(huán)簽名, 沒有這部分時(shí)間開銷. 在用戶密鑰生成方面, 本文方案運(yùn)用耗時(shí)較短的哈希函數(shù)生成用戶的公鑰, 調(diào)用原像抽樣算法(SamplePre) 生成用戶的私鑰, 因此, 環(huán)用戶公鑰生成時(shí)間可忽略, 環(huán)用戶密鑰生成耗時(shí)為TSP; 文獻(xiàn)[15] 的方案用戶公鑰運(yùn)用矩陣的標(biāo)量乘運(yùn)算和求逆運(yùn)算生成, 私鑰經(jīng)調(diào)用格基委派算法(BasisDel) 和原像抽樣算法(SamplePre) 生成; 而文獻(xiàn)[17] 的方案和文獻(xiàn)[19] 的方案用戶公鑰生成均由一個(gè)隨機(jī)選取的矩陣與向量進(jìn)行標(biāo)量乘運(yùn)算生成. 文獻(xiàn)[17] 的方案用戶私鑰經(jīng)運(yùn)用剩余哈希定理(LHL) 生成, 文獻(xiàn)[19] 的方案用戶私鑰由高斯采樣算法(SampleDom) 生成. 綜上考慮, 本文用戶密鑰生成效率優(yōu)于其他三種方案. 在簽名生成方面, 本文方案最終生成的簽名為σR(u)=(C1,t1,··· ,tl,I,b), 其中序列{Ci}, (i = 1,2,··· ,l) 的生成需要2l 個(gè)矩陣與向量的標(biāo)量乘運(yùn)算, 在簽名生成過程需要調(diào)用高斯釆樣算法(SampleDom) 隨機(jī)選取l 個(gè)m+1 維的列向量, 可鏈接標(biāo)簽I 經(jīng)調(diào)用耗時(shí)較少哈希函數(shù)生成,因此, 可鏈接標(biāo)簽的生成時(shí)間可忽略, n 維列向量b 的生成需要1 個(gè)矩陣與向量的標(biāo)量乘運(yùn)算. 經(jīng)對(duì)比,本文與文獻(xiàn)[19] 的方案簽名生成耗時(shí)相當(dāng), 較文獻(xiàn)[17] 的方案簽名生成少了l+1 個(gè)矩陣的標(biāo)量乘運(yùn)算,較文獻(xiàn)[15] 的方案簽名生成多了l 個(gè)矩陣的標(biāo)量乘運(yùn)算. 在簽名驗(yàn)證方面, 本文方案進(jìn)行驗(yàn)證時(shí), 需要計(jì)算序列{Ci}, (i=2,··· ,l+1) 的值, 需要進(jìn)行2l 次矩陣與向量的標(biāo)量乘運(yùn)算得到Cl+1的值與C1比較進(jìn)而對(duì)生成的簽名進(jìn)行驗(yàn)證. 經(jīng)比較, 本文方案的簽名驗(yàn)證效率與所選的三個(gè)參考方案相比有了一定的提高. 文獻(xiàn)[15] 的方案在簽名生成方面具有一定的優(yōu)勢(shì), 但其在密鑰生成階段消耗時(shí)間過多. 綜合整個(gè)系統(tǒng)的時(shí)間開銷, 我們的方案在用戶密鑰生成、簽名生成、簽名驗(yàn)證方面具有更高的效率.

四種方案的存儲(chǔ)開銷比較結(jié)果如表3 所示, 其中l(wèi) 仍代表環(huán)成員個(gè)數(shù). 主要從公鑰長(zhǎng)度、私鑰長(zhǎng)度及簽名長(zhǎng)度分別進(jìn)行分析. 在用戶公鑰長(zhǎng)度方面, 本文方案中用戶的公鑰由用戶的身份信息進(jìn)行哈希運(yùn)算生成, 用戶公鑰為n 維列向量. 文獻(xiàn)[15] 的方案用戶公鑰由一個(gè)n×m 維矩陣與一個(gè)m×m 維矩陣進(jìn)行標(biāo)量乘運(yùn)算生成, 用戶公鑰為一個(gè)n×m 維矩陣. 文獻(xiàn)[17] 的方案用戶公鑰由一個(gè)n×(m ?1) 維的矩陣與一個(gè)m ?1 維的列向量進(jìn)行標(biāo)量乘運(yùn)算生成, 用戶公鑰為一個(gè)n 維列向量. 文獻(xiàn)[19] 的方案用戶公鑰由一個(gè)n×m 維的矩陣與一個(gè)m 維的列向量進(jìn)行標(biāo)量乘運(yùn)算生成, 用戶公鑰為一個(gè)n 維列向量. 比較結(jié)果表明本文方案的用戶公鑰長(zhǎng)度與文獻(xiàn)[17] 的方案和文獻(xiàn)[19] 的方案相等, 較文獻(xiàn)[15] 的方案有了明顯的減小. 在用戶私鑰長(zhǎng)度方面, 本文用戶的私鑰基于原像抽樣算法(SamplePre) 生成, 用戶私鑰為一個(gè)m維的列向量, 文獻(xiàn)[15] 的方案中用戶私鑰經(jīng)調(diào)用格基委派算法(BasisDel) 和原像抽樣算法(SamplePre)生成為一個(gè)m×k 維矩陣, 文獻(xiàn)[17] 的方案中用戶私鑰經(jīng)調(diào)用剩余哈希定理(LHL) 定義為一個(gè)m ?1 維列向量, 文獻(xiàn)[19] 的方案中用戶私鑰運(yùn)用高斯采樣算法(SampleDom) 生成為一個(gè)m 維的列向量, 比較結(jié)果表明本文方案的用戶私鑰長(zhǎng)度與文獻(xiàn)[17] 的方案相等, 較文獻(xiàn)[15] 的方案有了明顯的減小. 在簽名長(zhǎng)度方面, 本文方案生成的簽名中向量ti(i = 1,2,··· ,l) 是m+1 維列向量, 向量b 是n 維列向量. 分析結(jié)果表明, 文獻(xiàn)[17] 的方案和文獻(xiàn)[19] 的方案簽名長(zhǎng)度相等, 本文生成簽名的長(zhǎng)度略高于所選的三個(gè)參考方案. 綜合分析整個(gè)系統(tǒng)的存儲(chǔ)開銷性能, 文獻(xiàn)[15] 的方案用戶公鑰、私鑰長(zhǎng)度較長(zhǎng), 其他方面四種方案的存儲(chǔ)開銷基本相當(dāng).

表2 時(shí)間開銷比較Table 2 Comparison of time costs

表3 存儲(chǔ)開銷比較Table 3 Comparison of storage overhead

我們?cè)O(shè)置參數(shù)n = 8, m = 640, q = 232= 4 294 967 296, k = 6 使得我們的方案是安全的, 將本文方案在Windows 10 系統(tǒng)、Intel(R) Core(TM)i5-8300H CPU@2.30 GHz 處理器和8.00 GB 運(yùn)行內(nèi)存下進(jìn)行實(shí)現(xiàn)與評(píng)估. 表4、表5 中分別給出所選的三個(gè)參考方案與本文方案在環(huán)成員數(shù)量不同情況下的時(shí)間開銷和存儲(chǔ)開銷對(duì)比結(jié)果. 給出本方案的時(shí)間開銷分別在l = 1, l = 8, l = 32, l = 128 的結(jié)果如表6 所示.實(shí)驗(yàn)結(jié)果與理論分析基本一致, 綜合整個(gè)系統(tǒng)的時(shí)間開銷, 我們的方案在用戶密鑰生成、簽名生成、簽名驗(yàn)證方面具有更高的效率. 綜合分析整個(gè)系統(tǒng)的存儲(chǔ)開銷性能, 文獻(xiàn)[15] 的方案用戶公鑰、私鑰長(zhǎng)度較長(zhǎng),其他方面4 種方案的存儲(chǔ)開銷基本相當(dāng). 本文方案有待進(jìn)一步優(yōu)化從而獲得更小的存儲(chǔ)開銷.

7 結(jié)束語

相較普通基于數(shù)字證書的可鏈接環(huán)簽名, 基于身份的可鏈接環(huán)簽名能夠在保護(hù)用戶身份隱私的同時(shí),有效解決復(fù)雜的用戶證書管理問題. 但在量子技術(shù)得到應(yīng)用的前提下, 基于經(jīng)典數(shù)論難題的可鏈接環(huán)簽名(包括基于數(shù)字證書和基于身份的可鏈接環(huán)簽名) 方案都將不再安全. 因此, 本文運(yùn)用原像抽樣算法與拒絕抽樣等技術(shù), 提出了一種格上基于身份的可鏈接環(huán)簽名方案. 在隨機(jī)諭言機(jī)模型下, 將本方案的安全性歸約至小整數(shù)解(SIS) 困難假設(shè), 并給出了嚴(yán)格的安全性證明. 對(duì)比已有的格上可鏈接環(huán)簽名方案, 本文所提出的方案在用戶密鑰生成、簽名生成和驗(yàn)證的效率等有了進(jìn)一步的優(yōu)化與提高.

表4 時(shí)間開銷比較(ms)Table 4 Comparison of time costs (ms)

表5 存儲(chǔ)開銷比較(KB)Table 5 Comparison of storage overhead (KB)

表6 本文方案時(shí)間開銷比較(ms)Table 6 Comparison of time costs of proposed scheme (ms)