格上可編程哈希函數(shù)的環(huán)簽名方案

葛炳輝,趙宗渠,何 錚,秦攀科

(河南理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,河南 焦作 454000)

0 概述

隨著現(xiàn)代科技的發(fā)展,電子簽名技術(shù)已廣泛應(yīng)用于人們的日常生活。環(huán)簽名作為電子簽名中的一種,常用于電子現(xiàn)金、匿名電子投票、匿名舉報和區(qū)塊鏈應(yīng)用等。環(huán)簽名由密碼學(xué)家RIVEST等人[1]于2001年提出,其與群簽名一樣,都為簽名者提供匿名性簽名方案。在環(huán)簽名中,沒有管理者只有環(huán)成員,環(huán)成員之間彼此獨立,無需相互合作。在簽名過程中,簽名者首先選定1個臨時簽名者集合,簽名者也包含在該集合中,然后簽名者利用自己的私鑰和集合成員的公鑰就可單獨對消息進行簽名。任何1位環(huán)成員都能代表集合對消息進行簽名,且驗證簽名只需集合成員的公鑰、消息和簽名,無需簽名者的私鑰,從而確保環(huán)簽名的匿名性。研究人員采用不同安全模型提出多種環(huán)簽名方案,其安全性主要基于大整數(shù)因子化[1-3]、離散對數(shù)[4-5]和雙線性配對[6-8]等數(shù)論假設(shè)。隨著量子計算機技術(shù)的進步,大整數(shù)因子化和離散對數(shù)等問題可用Shor量子算法在概率多項式時間(Probabilistic Polynomial Time,PPT)內(nèi)求解,這給密碼設(shè)置帶來新的挑戰(zhàn),上述環(huán)簽名方案等傳統(tǒng)安全保護方法在量子計算環(huán)境下已不再安全[9]。

基于格的密碼構(gòu)造能抵抗量子攻擊,且格中主要為線性運算和模運算,相較傳統(tǒng)密碼指數(shù)運算速度更快,因此其有望成為后量子傳統(tǒng)公鑰替代者之一,基于格的密碼方案設(shè)計也成為學(xué)者們的研究熱點[10-11]。由于格中問題在一般情況和最壞情況下困難性相同,因此格上任意實例的安全性都相同,該特性吸引眾多密碼學(xué)家對基于格的環(huán)簽名方案進行研究[12-13]。2010年,CASH等人[14]提出首個基于格的環(huán)簽名方案,并采用格基派生技術(shù)為環(huán)成員產(chǎn)生公私鑰,但是該方案簽名長度較長,計算費時不利于實施。2011年,WANG等人[15]提出基于格的環(huán)簽名新方案,但該方案缺少標(biāo)準(zhǔn)模型下的安全性證明。2012年,田苗苗等人[16]利用GPV格點篩選算法[11]提出一種基于格的環(huán)簽名高效方案,但如果將該方案中驗證矩陣的l+2個公鑰和環(huán)簽名向量代入簽名驗證公式,則敵手最多試(l+2)2次就可找到滿足簽名驗證公式的公鑰從而找到簽名者,因此該方案不具備匿名性。2018年,熱娜等人[17]針對文獻[15]方案中不滿足不可偽造性的問題進行優(yōu)化后,提出基于格的環(huán)簽名改進方案,該方案在隨機預(yù)言模型下證明滿足環(huán)簽名中的匿名性和不可偽造性,并使用MP12陷門函數(shù)[10]生成陷門。雖然該方案已證明具有安全性,但是在隨機預(yù)言模型下證明安全的方案在實際應(yīng)用中有可能不安全,且該方案的簽名密鑰和簽名長度較長。

2012年,HOFHEINZ等人[18-19]提出可編程哈希函數(shù)(Programmable Hash Function,PHF),該函數(shù)是一種可模擬隨機預(yù)言機某些可編程性質(zhì)的特殊哈希函數(shù)[20],并利用可編程哈希函數(shù)分別構(gòu)造了基于雙線性映射和基于RSA算法的簽名方案,這2種方案具有更短的簽名長度,且從理論上更容易證明其安全性。傳統(tǒng)可編程哈希函數(shù)的定義與構(gòu)造都存在特定于DL群之間的代數(shù)結(jié)構(gòu)問題,這也是幾乎所有已知可編程哈希函數(shù)均由DL問題構(gòu)造的原因。2016年,ZHANG等人[21]提出格上可編程哈希函數(shù)的概念,利用格上可編程哈希函數(shù)重新構(gòu)造了格上簽名方案,該方案繼承了傳統(tǒng)可編程哈希函數(shù)簽名方案的優(yōu)點,改進了公鑰過長的不足。雖然格和DL群之間代數(shù)結(jié)構(gòu)差異較大,傳統(tǒng)可編程哈希函數(shù)定義看似不適合格,且格上可編程哈希函數(shù)已超過傳統(tǒng)可編程哈希函數(shù)的范圍,但由于格上可編程哈希函數(shù)繼承了傳統(tǒng)可編程哈希函數(shù)的概念,并運用格上分區(qū)證明技巧[21],因此仍將其歸類于可編程哈希函數(shù)。

文獻[21]指出在非齊次小整數(shù)解(Inhomogeneous Small Integer Solution,ISIS)假設(shè)下,任何基于格上的可編程哈希函數(shù)均抗碰撞,因此可直接應(yīng)用于環(huán)簽名方案。為縮短格上環(huán)簽名方案的簽名和密鑰長度,本文提出一種基于格上可編程哈希函數(shù)的環(huán)簽名新方案,利用可編程哈希函數(shù)的特殊性質(zhì)和MP12陷門函數(shù)生成陷門,將可編程哈希函數(shù)嵌入環(huán)簽名的構(gòu)造中,并對本文方案在標(biāo)準(zhǔn)模型下自適應(yīng)選擇消息攻擊的存在不可偽造性(Existential Unforgeability against Adaptive Chosen Messages Attack,EUF-CMA)安全進行分析。

1 預(yù)備知識

1.1 格

(1)

(2)

1.2 格上的困難問題

本文基于格上的小整數(shù)解(Small Integer Solution,SIS)問題和非齊次小整數(shù)解問題這2種困難問題研究格上可編程哈希函數(shù)環(huán)簽名方案的安全性。

1.3 格上可編程哈希函數(shù)

3)統(tǒng)計上更接近陷門密鑰。對于全部密鑰(K′,td)←H.TrapGen(1k,A,B)和K←H.Gen(1k),(A,K′)和(A,K)之間的統(tǒng)計距離最大為γ。

若γ可忽略而δ不可忽略,則稱該哈希函數(shù)為(u,v,β)-PHF;若u為k中隨機選取的多項式,則稱該哈希函數(shù)為(poly,v,β)-PHF。

1.4 環(huán)簽名

環(huán)簽名方案由KeyGen、Sign和Verify 3個概率多項式時間算法組成[3]。

1)KeyGen(1n)算法。輸入系統(tǒng)安全參數(shù)n,KeyGen算法為每位環(huán)成員生成其簽名密鑰ski和驗證密鑰vki。

1.5 環(huán)簽名安全模型

若環(huán)簽名方案滿足匿名性和不可偽造性2個條件,則該環(huán)簽名方案為安全的簽名方案。

1)匿名性。假設(shè)PPT內(nèi)敵手A以優(yōu)勢Padv=Psuc-1/2贏得游戲,Psuc為敵手A贏得此游戲的概率,若得到的Padv可忽略,則該環(huán)簽名方案滿足匿名性。

(3)敵手A輸出身份猜測b′。

2)不可偽造性。假設(shè)PPT內(nèi)敵手A贏得游戲的概率Psuc可忽略,則稱該環(huán)簽名方案在選擇子環(huán)和適應(yīng)性選擇消息攻擊下具有不可偽造性。

2 方案描述

3 安全性分析

3.1 匿名性分析

定理1本文格上可編程哈希函數(shù)的環(huán)簽名方案滿足完全匿名性。

證明對本文方案匿名性的證明過程如下:

3)敵手A適應(yīng)性選擇詢問用戶i

5)敵手A輸出身份猜測b′。

3.2 不可偽造性分析

證明對本文方案不可偽造性的證明過程如下:

(2)t=t′∧b=0:算法B停止。

假設(shè)全部消息M1,M2,…,Mu在回答簽名查詢時,通過算法B使用相同標(biāo)簽t=t′,對于i∈{1,2,…,u}使得(TMi,SMi)=H.TrapEval(td,K′,Mi),給出2個條件:1)某些標(biāo)簽t用于回答超過v個消息的簽名;2)SMi對于某些i∈{1,2,…,u}不可逆,當(dāng)SM*≠0或者t*≠t成立時,模擬過程中止。

4 效率分析

本文利用格上可編程哈希函數(shù)的特殊性質(zhì)設(shè)計出一種在標(biāo)準(zhǔn)模型下可證明安全性的環(huán)簽名方案,并以驗證密鑰長度、簽名密鑰長度、簽名長度以及基于格上的困難問題作為方案效率評價指標(biāo),將本文方案與文獻[15-17]中格上同類型環(huán)簽名方案進行對比,結(jié)果如表1所示。

表1 4種格上環(huán)簽名方案評價指標(biāo)比較結(jié)果Table 1 Evaluation index comparison results of four ring signature schemes on lattices

5 結(jié)束語

格上可編程哈希函數(shù)能模擬隨機預(yù)言機部分可編程性質(zhì),通過格上分區(qū)證明方式直接應(yīng)用于簽名構(gòu)造和安全性驗證。本文提出一種新的格上可編程哈希函數(shù)環(huán)簽名方案,利用MP12陷門函數(shù)生成陷門,將可編程哈希函數(shù)應(yīng)用到環(huán)簽名構(gòu)造中,進而形成驗證密鑰、簽名密鑰和簽名。分析結(jié)果表明,該方案所得簽名和密鑰較其他格上環(huán)簽名方案更短,且在標(biāo)準(zhǔn)模型下滿足EUF-CMA安全要求。后續(xù)將研究如何在保持簽名密鑰和簽名長度不變的情況下,縮短驗證密鑰長度并提高效率,同時考慮將本文方案推廣到基于身份的環(huán)簽名方案中,以得到更短的簽名和密鑰。