格上基于身份的可鏈接環(huán)簽名*

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

1. 河南理工大學 計算機科學與技術學院, 焦作454003

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

1 引言

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

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

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

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

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

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

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

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

2 預備知識

2.1 符號說明

為表述方便對文中符號進行說明, 如表1 所示.

表1 符號說明Table 1 Symbol description

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

2.2 格的相關定義

2.3 困難假設

2.4 相關算法

2.5 拒絕抽樣技術

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

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

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

(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對應的私鑰SIDi.

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

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

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

3.2 安全模型

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

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

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

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

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

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

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

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

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

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

定義5 (Anonymity) 當對于任意多項式時間攻擊者A, A是可忽略的, 則稱一個可鏈接環(huán)簽名方案是匿名的.

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

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

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

(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)勢定義為:

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

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

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

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

4 方案構(gòu)造

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

5 安全性證明

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

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

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

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

因此, 本方案滿足簽名驗證正確性.

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

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

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

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

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

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

Game0游戲:

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

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

Game1游戲:

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

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

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

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

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

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

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

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

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

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

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

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

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

1) Hash 詢問.

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

6 性能分析

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

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

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

表2 時間開銷比較Table 2 Comparison of time costs

表3 存儲開銷比較Table 3 Comparison of storage overhead

我們設置參數(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 運行內(nèi)存下進行實現(xiàn)與評估. 表4、表5 中分別給出所選的三個參考方案與本文方案在環(huán)成員數(shù)量不同情況下的時間開銷和存儲開銷對比結(jié)果. 給出本方案的時間開銷分別在l = 1, l = 8, l = 32, l = 128 的結(jié)果如表6 所示.實驗結(jié)果與理論分析基本一致, 綜合整個系統(tǒng)的時間開銷, 我們的方案在用戶密鑰生成、簽名生成、簽名驗證方面具有更高的效率. 綜合分析整個系統(tǒng)的存儲開銷性能, 文獻[15] 的方案用戶公鑰、私鑰長度較長,其他方面4 種方案的存儲開銷基本相當. 本文方案有待進一步優(yōu)化從而獲得更小的存儲開銷.

7 結(jié)束語

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

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

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

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