格上可編程哈希函數的環簽名方案

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

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

0 概述

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

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

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

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

1 預備知識

1.1 格

(1)

(2)

1.2 格上的困難問題

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

1.3 格上可編程哈希函數

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

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

1.4 環簽名

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

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

1.5 環簽名安全模型

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

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

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

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

2 方案描述

3 安全性分析

3.1 匿名性分析

定理1本文格上可編程哈希函數的環簽名方案滿足完全匿名性。

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

3)敵手A適應性選擇詢問用戶i

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

3.2 不可偽造性分析

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

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

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

4 效率分析

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

表1 4種格上環簽名方案評價指標比較結果Table 1 Evaluation index comparison results of four ring signature schemes on lattices

5 結束語

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