格上身份基可追蹤環(huán)簽名方案

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

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

1 引 言

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

2 預(yù)備知識

2.1 格的相關(guān)定義及困難假設(shè)

定義1整數(shù)格。Zn中的一個(gè)格

2.2 離散高斯分布和拒絕采樣技術(shù)

2.3 帶原像采樣的陷門函數(shù)

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

2.4 可追蹤環(huán)簽名的定義及安全需求

可追蹤環(huán)簽名方案包括5個(gè)算法:參數(shù)建立、密鑰提取、簽名、驗(yàn)證和追蹤算法。一個(gè)安全的可追蹤環(huán)簽名方案應(yīng)滿足4個(gè)性質(zhì),即正確性、標(biāo)簽可鏈接性、匿名性和抗陷害性。正確性包括完備性和公共可追蹤性兩個(gè)方面,其中完備性是環(huán)簽名的普遍要求,即誠實(shí)的簽名以壓倒性概率能通過驗(yàn)證算法的驗(yàn)證,而公共可追蹤性為可追蹤環(huán)簽名的特殊要求,主要是為了保證追蹤功能的正確性,即給定針對同一個(gè)標(biāo)簽的兩個(gè)誠實(shí)的簽名,如果它們?yōu)椴煌灻咚?追蹤算法將接受這兩個(gè)簽名;如果它們?yōu)橥缓灻邔ν幌⒌暮灻?追蹤算法將把它們“鏈接”起來;如果它們?yōu)橥缓灻邔Σ煌⒌暮灻?追蹤算法將輸出簽名者身份。標(biāo)簽可鏈接性是為了保護(hù)整個(gè)可追蹤環(huán)簽名系統(tǒng),它要求即使用戶的公私鑰都由攻擊者產(chǎn)生,攻擊者也不可能輸出N+1個(gè)消息簽名對,使它們都能通過驗(yàn)證算法并且它們中的任意兩個(gè)都被追蹤算法接受,其中N代表環(huán)中成員的個(gè)數(shù)。匿名性是環(huán)簽名的基本要求,即給定一個(gè)可追蹤環(huán)簽名,攻擊者僅能判斷它的簽名者來自一個(gè)環(huán),而不能確定具體是哪個(gè)環(huán)成員?？瓜莺π砸鬀]有環(huán)成員i的私鑰,攻擊者無法陷害成員i,即攻擊者無法產(chǎn)生兩個(gè)可追蹤環(huán)簽名,使得追蹤算法判定它們?yōu)槌蓡Ti所簽?？勺粉櫗h(huán)簽名的標(biāo)簽可鏈接性和抗陷害性包含不可偽造性?？勺粉櫗h(huán)簽名正式的定義及安全模型請參考文獻(xiàn)[3,7-8,13],此處不再贅述。

3 方案構(gòu)造

驗(yàn)證(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,將對應(yīng)的IDi存入TraceList,其中TraceList初始為一個(gè)空表;

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

下面分析方案的正確性。

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

4 安全性證明

在證明標(biāo)簽可鏈接性前,首先證明以下相關(guān)引理。

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

的概率為1-negl(n)。

證明 對以下兩種情況分別進(jìn)行分析:

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

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

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

證明 算法G描述如下:

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

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

證明 C分別接收ISIS或SIS實(shí)例如下:

5 性能分析

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

表1 時(shí)間開銷比較

表2 存儲開銷比較 bit

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

6 結(jié)束語

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