格上身份基可追蹤環簽名方案

葉 青,陳晴晴,豆永鵬,張 靜,湯永利

(1.河南理工大學 軟件學院,河南 焦作 454003;2.陸軍裝備部駐西安軍事代表局駐西安地區第七軍事代表室,陜西 西安 710065)

1 引 言

環簽名[1]是一種可為簽名者提供匿名保護的特殊的數字簽名,它允許簽名者代表一組用戶(環)簽名,驗證者僅能判定簽名者來自一個環,并不能確定具體是哪個用戶?？涉溄迎h簽名(Linkable Ring Signature,LRS)[2]除了具備普通環簽名的匿名性功能,還能檢測兩個簽名是否由同一個簽名者生成。而可追蹤環簽名(Traceable Ring Signature,TRS)[3]可看作是功能完備版本的可鏈接環簽名,在可追蹤環簽名中,如果簽名者用相同標簽(標簽包含一個環和一個關于某個社會問題的字符串issue)對相同消息進行簽名,則兩個簽名能夠被檢測出屬于同一簽名者的兩次簽名,但是簽名者的身份不會被泄露;但如果簽名者利用相同標簽對不同消息進行簽名,則追蹤環簽名可追蹤到兩個簽名的簽名者身份,簽名者的身份被揭露?？勺粉櫗h簽名適用于電子投票[4]、區塊鏈[5-6]、匿名電子支付等既需要匿名保護也要避免重復簽名的場景。例如,在電子投票系統中應用可追蹤環簽名時,若某個選民基于同一個環對“張三當選人大代表”(issue)兩次投“贊成”票,即對消息“贊成”簽名兩次,則這兩次投票會被檢測出為重復投票,但該選民的身份并不會暴露;若他基于同一個環對“張三當選人大代表” (issue)投一次“贊成”票,再投一次“反對”票,即對消息“贊成”和“反對”分別簽名時,則其身份會被揭露。FUJISAKI[7]提出了一種在標準模型下次線性尺寸的可追蹤環簽名,AU 等[8]構造了一個基于離散對數問題的身份基可追蹤環簽名方案。但上述環簽名方案[1-3,7-8]都基于傳統數論難題構造,不足以抵抗量子計算機的攻擊。近年來,格上密碼系統因具有較好的漸近效率、可并行性以及抗量子攻擊等特點,成為后量子密碼的研究熱點。格上可鏈接環簽名最近取得了一些研究進展[9-12],但格上可追蹤環簽名方面研究成果較少,目前已知的僅有FENG等[13]提出的格上可追蹤環簽名方案。針對目前格上可追蹤環簽名方案[13]基于PKI體制構造,具有復雜的數字證書管理負擔這一現狀,筆者將基于身份的密碼體制與格上可追蹤環簽名相結合,依據BAUM等[12]格上可鏈接環簽名方案的框架,采用原像采樣[14]和拒絕采樣等技術[15],提出了一個基于SIS困難問題的身份基可追蹤環簽名方案。與大多數可追蹤環簽名方案[3,7-8,13]不同,所提方案避免使用臃腫的零知識證明,簽名長度較短,方案簡潔高效。

2 預備知識

2.1 格的相關定義及困難假設

定義1整數格。Zn中的一個格

2.2 離散高斯分布和拒絕采樣技術

2.3 帶原像采樣的陷門函數

2008年GENTRY等[14]提出的基于SIS問題的帶原像采樣的陷門函數成為構造格上簽名方案的重要技術,具體包括以下3個部分:

2.4 可追蹤環簽名的定義及安全需求

可追蹤環簽名方案包括5個算法:參數建立、密鑰提取、簽名、驗證和追蹤算法。一個安全的可追蹤環簽名方案應滿足4個性質,即正確性、標簽可鏈接性、匿名性和抗陷害性。正確性包括完備性和公共可追蹤性兩個方面,其中完備性是環簽名的普遍要求,即誠實的簽名以壓倒性概率能通過驗證算法的驗證,而公共可追蹤性為可追蹤環簽名的特殊要求,主要是為了保證追蹤功能的正確性,即給定針對同一個標簽的兩個誠實的簽名,如果它們為不同簽名者所簽,追蹤算法將接受這兩個簽名;如果它們為同一簽名者對同一消息的簽名,追蹤算法將把它們“鏈接”起來;如果它們為同一簽名者對不同消息的簽名,追蹤算法將輸出簽名者身份。標簽可鏈接性是為了保護整個可追蹤環簽名系統,它要求即使用戶的公私鑰都由攻擊者產生,攻擊者也不可能輸出N+1個消息簽名對,使它們都能通過驗證算法并且它們中的任意兩個都被追蹤算法接受,其中N代表環中成員的個數。匿名性是環簽名的基本要求,即給定一個可追蹤環簽名,攻擊者僅能判斷它的簽名者來自一個環,而不能確定具體是哪個環成員?？瓜莺π砸鬀]有環成員i的私鑰,攻擊者無法陷害成員i,即攻擊者無法產生兩個可追蹤環簽名,使得追蹤算法判定它們為成員i所簽?？勺粉櫗h簽名的標簽可鏈接性和抗陷害性包含不可偽造性?？勺粉櫗h簽名正式的定義及安全模型請參考文獻[3,7-8,13],此處不再贅述。

3 方案構造

驗證(Vfy(pp,T,μ,Ω))。該算法操作如下:

(1) 對于i∈[N],檢查是否‖zi‖≤2σ(m)1/2,如不滿足則輸出“invalid”;

(3) 如果c1=H(T,μ,pN,gN,hN)=cN+1,輸出“valid”,否則輸出“invalid”。

(1) 對于所有的i∈[N],如果pi=p′i,將對應的IDi存入TraceList,其中TraceList初始為一個空表;

(2) 如果|TraceList|=N,輸出“linked”,其中|·|表示列表或集合中元素的個數;如果IDi是TraceList中唯一的記錄,則輸出IDi;其他情況,輸出“accept”。

下面分析方案的正確性。

由文獻[3,7-8,13],可追蹤環簽名方案的正確性包括完備性和公共可追蹤性兩個方面,由引理2和引理3,所提方案的完備性是顯而易見的,此處不再贅述。下面重點分析所提方案的公共可追蹤性:

4 安全性證明

在證明標簽可鏈接性前,首先證明以下相關引理。

引理4給定關于所提方案的一個有效的簽名(T,μ,Ω),則

的概率為1-negl(n)。

證明 對以下兩種情況分別進行分析:

引理5給定兩個簽名(T,μ,Ω),(T,μ′,Ω′)滿足Trace(pp,T,μ,Ω,μ′,Ω′)=accept,則概率|TraceList|>0的概率是可忽略的。

定理1(標簽可鏈接性) 所提方案在隨機預言模型(ROM)下是滿足標簽可鏈接性的。

在證明匿名性之前,首先介紹一個關于所提方案的簽名模擬算法G。

證明 算法G描述如下:

(3) 輸出Ω=(c1,τ,(zi)i∈[N])。

定理2(匿名性) 在ROM下,對于PPT敵手A,所提方案滿足匿名性。

證明 C分別接收ISIS或SIS實例如下:

5 性能分析

鑒于目前還沒有可以比較的格上基于身份的可追蹤環簽名方案,這里將所提方案與2個較新的格上基于身份的可鏈接環簽名方案[9,11]進行性能對比,時間開銷和存儲開銷的對比結果分別列于表1和表2中。在這兩表中,n為安全參數,q是大素數,正整數m≥5nlogq,N代表環成員個數,T1,TTG,TSP,TSD,TRS,TDT分別表示矩陣-向量乘法、陷門生成、原像取樣、高斯取樣、拒絕采樣和陷門派生等算法運行一次所需的時間。在計算存儲開銷時,用到了引理2,并且只考慮簽名中的向量或矩陣等長度較長的部分。

表1 時間開銷比較

表2 存儲開銷比較 bit

由表1、表2可以看出,在算法時間開銷和存儲開銷方面,本文方案與最新的格上基于身份的可鏈接環簽名方案相當或更小,而普遍認為可追蹤環簽名比可鏈接環簽名在功能上更加完備。所以總體而言,本文方案優于兩個比較對象。

6 結束語

基于原像采樣和拒絕采樣等技術,筆者提出了第一個格上基于身份的可追蹤環簽名方案。隨機預言模型下,所提方案被證明滿足標簽的可鏈接性、匿名性以及抗陷害性,方案的安全性可歸約至格上SIS和ISIS困難問題。與類似方案相比,所提方案在時間開銷與存儲開銷方面具有一定的優勢。