俞惠芳,付帥鳳

(西安郵電大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院,陜西 西安 7 10121)

1983年,Chaum[1]首次提出了盲簽名的概念.盲簽名是一種具有消息盲化特性的簽名.假設(shè)消息擁有者想要簽名者對待簽消息進(jìn)行簽名,但是又不想讓簽名者知道待簽消息的具體內(nèi)容,即使以后簽名者又見到了該消息簽名,也不確定什么時(shí)候他簽署了這個(gè)簽名,這種情況下就可以用到盲簽名.盲簽名可以理解為將需要簽名的文件放在裝有復(fù)印紙的文件袋中,簽名者看不到文件的具體內(nèi)容,他只需要在文件袋上簽名,這樣簽名可以通過復(fù)印紙印在文件上.盲簽名主要用于電子現(xiàn)金支付、電子投票等需要匿名性和認(rèn)證性的應(yīng)用場合中[2?4].自1983年以后,盲簽名引起了廣泛的關(guān)注,學(xué)者們也提出了眾多盲簽名方案[5?7],但是目前大多數(shù)盲簽名都是基于傳統(tǒng)公鑰密碼體制的[8?10].傳統(tǒng)公鑰密碼體制的安全性主要依賴于大整數(shù)分解問題或離散對數(shù)問題的難解性.隨著量子計(jì)算[11]的發(fā)展,使得基于傳統(tǒng)公鑰密碼體制的盲簽名方案受到了嚴(yán)重威脅.為此,研究具有抗量子計(jì)算特性的盲簽名方案具有重要的意義.多變量公鑰密碼作為后量子密碼的主要候選者之一,其安全性基于有限域上二次多變量多項(xiàng)式方程組(multivariate quadrati c,簡稱MQ)問題和多項(xiàng)式同構(gòu)(isomorphism of poly nomials,簡稱IP)問題的難解性,已有的量子算法目前還不能很好地解決MQ 問題和IP 問題.多變量公鑰密碼具有計(jì)算效率高、運(yùn)算速度快等優(yōu)點(diǎn),非常適用于計(jì)算能力有限的設(shè)備.文獻(xiàn)[12,13]提出了多變量環(huán)簽名方案;文獻(xiàn)[14]運(yùn)用公平劃分的思想,將文獻(xiàn)[12]轉(zhuǎn)化為多變量門限環(huán)簽名方案;文獻(xiàn)[15,16]提出了多變量代理簽名方案;文獻(xiàn)[17]提出了多變量群簽名方案;文獻(xiàn)[18]提出了多變量盲簽名方案,但是該方案運(yùn)用傳統(tǒng)的多變量簽名模型,為了產(chǎn)生一個(gè)有效的簽名,采用了兩個(gè)非滿射中心映射,其只能應(yīng)用在已知安全的多變量公鑰密碼體制下,而且安全性低、計(jì)算效率低;文獻(xiàn)[19]提出了一個(gè)交互式的多變量盲簽名方案,但是其公鑰長度和簽名長度較大.

2009年,Wang 等人[20]提出了一種多變量簽名模型改進(jìn)的方案,本質(zhì)上是增加一個(gè)秘密仿射變換M來分離簽名私鑰和驗(yàn)證公鑰之間的線性關(guān)系.2012年,Lu 等人[21]對Wang 等人的方案進(jìn)行了分析,指出:可以通過合法用戶的r+1 個(gè)已知簽名建立線性方程組,使Wang 等人的方案轉(zhuǎn)化為一般的簽名方案,進(jìn)而說明增加秘密仿射變換M并不能提高原有簽名方案的安全性.Lu 等人[22]提出使用非線性可逆變換L替代秘密仿射變換M,減少簽名私鑰和驗(yàn)證公鑰的線性關(guān)系,提高了簽名方案的安全性.Yasuda 等人[23]提出利用非滿射中心映射構(gòu)造多變量公鑰密碼,具有隱藏代數(shù)矩陣和線性對等線性性質(zhì).

本文在盲簽名和多變量公鑰密碼的理論基礎(chǔ)上,借鑒文獻(xiàn)[22]改進(jìn)的多變量簽名模型和文獻(xiàn)[23]的非滿射中心映射,提出一種多變量公鑰密碼體制下的后量子盲簽名方案.由于所提方案只有一個(gè)非滿射中心映射,為了使方案可以產(chǎn)生一個(gè)有效的簽名,本文借鑒文獻(xiàn)[24]對消息增加幾個(gè)隨機(jī)比特的思想.所提方案的公私鑰之間沒有線性關(guān)系,使得盲簽名的安全性得到提高.經(jīng)過安全性分析,證明了該密碼方案滿足盲性、不可偽造性和不可追蹤性,而且計(jì)算效率高還能防御量子計(jì)算攻擊.

1 預(yù)備知識(shí)

1.1 多變量公鑰密碼

多變量公鑰密碼的單向陷門函數(shù)形式是有限域F上的多變量二次多項(xiàng)式映射,公鑰的一般形式如下:

P=(p1(x1,x2,…,xn),…,pr(x1,x2,…,xn)).

每個(gè)方程pi(i=1,2,…,r)是一個(gè)關(guān)于x=(x1,x2,…,xn)的非線性二次方程:

其中,方程的系數(shù)γijk,βij,αi∈F(1≤i≤n,1≤j≤k≤n),變量xj,xk∈F.多變量公鑰密碼的安全性主要依賴于MQ 問題和IP 問題的難解性.

定義1(MQ 問題).給定有限域Fq(q為有限域F的階)中的r個(gè)n元方程式的非線性方程組:

p1(x1,x2,…,xn),p2(x1,x2,…,xn)=…=pr(x1,x2,…,xn)=0.

求解該方程組的問題被稱為MQ 問題.已經(jīng)證明MQ 問題是非確定多項(xiàng)式(nondeterministic polynomials,簡稱NP)困難問題,即使是在最小的有限域F2上.

定義2(IP 問題).設(shè)P和Q是有限域Fq上隨機(jī)選取的r個(gè)n元方程的多變量方程組,且P和Q同構(gòu),則有P=T?Q?S,其中,T和S分別為兩個(gè)可逆仿射變換,則稱尋找從Q到P同構(gòu)的(T,S)問題為IP 問題[16].

多變量公鑰密碼的簽名和驗(yàn)證過程如下:

這里的S和T分別是Fn→Fn和Fr→Fr的兩個(gè)可逆仿射變換,Q是Fn→Fr的中心映射,公鑰為P=T?Q?S,私鑰為{T,Q,S}.

簽名:如果要對消息m進(jìn)行簽名,先計(jì)算消息m的哈希值v∈Fr,然后依次計(jì)算y=T?1(v)∈Fr,x=Q?1(y)∈Fn和σ=S?1(x)∈Fn,σ就是消息m的簽名.

驗(yàn)證:如果要對簽名σ進(jìn)行驗(yàn)證,先利用公鑰P=T?Q?S計(jì)算v′=P(σ):如果v′=v,則說明簽名是有效的;否則,簽名是無效的.

1.2 盲簽名的形式化定義

1.2.1 算法定義

盲簽名是一種具有消息盲化特性的簽名,確保了簽名者在不知道具體待簽消息內(nèi)容的情況下進(jìn)行簽名,即使簽名者以后又見到了該消息簽名,也不確定自己什么時(shí)候簽署了這個(gè)簽名.一個(gè)盲簽名方案由以下幾個(gè)算法組成.

?系統(tǒng)初始化:輸入安全參數(shù)λ,輸出系統(tǒng)參數(shù);

?密鑰生成:輸入系統(tǒng)參數(shù),輸出簽名者B的公私鑰對;

?盲簽名:該算法由如下3 個(gè)子算法組成.

(1)盲化:輸入系統(tǒng)參數(shù),消息擁有者O隨機(jī)選取一個(gè)盲因子e,對消息m進(jìn)行盲化處理,將盲化后的消息發(fā)送給B;

(2)簽名:B用私鑰對盲化后的消息進(jìn)行簽名,得到盲簽名σ′;

(3)去盲化:O用B的公鑰和盲化后的消息對盲簽名σ′進(jìn)行驗(yàn)證:若成立,O對盲簽名σ′去盲化處理,輸出最終的簽名σ;否則,簽名無效;

?驗(yàn)證:輸入系統(tǒng)參數(shù)、消息m和B的公鑰對簽名σ進(jìn)行驗(yàn)證:如果簽名有效,輸出1;否則,輸出0.

一般地,對于消息m,如果簽名者按照正確的步驟對消息m進(jìn)行簽名,而且在傳播的過程中簽名沒有被篡改,那么簽名σ可以通過驗(yàn)證.

1.2.2 安全模型

1.盲性

定義3.簽名者B對消息m進(jìn)行簽名,但是不知道消息m的具體內(nèi)容.

對于盲性的安全模型,通過游戲Game1 進(jìn)行形式化定義.

Game1:敵手A(模擬簽名者B)和挑戰(zhàn)者C的盲簽名交互過程如下所述.

(1)C通過運(yùn)行系統(tǒng)初始化算法生成系統(tǒng)參數(shù),同時(shí),通過運(yùn)行密鑰生成算法生成簽名的公私鑰對,然后將系統(tǒng)參數(shù)和私鑰發(fā)送給A;

(2)A隨機(jī)選取兩個(gè)等長的不同的消息m0和m1發(fā)送給C;

(3)C隨機(jī)選取兩個(gè)等長的不同的盲因子ec∈F和e1?c∈F,然后隨機(jī)選擇c∈{0,1}.最后運(yùn)行盲簽名中的盲化算法生成盲化消息bc和b1?c,并將bc和b1?c隨機(jī)發(fā)送給A;

(4)A對bc和b1?c依次執(zhí)行盲簽名中的簽名算法,得到盲簽名cσ′和σ1′?c,并將cσ′和σ1′?c依次發(fā)送給C;

(5)C利用盲因子ec和e1?c對盲簽名cσ′和σ1′?c去盲化處理,得到簽名σc和σ1?c;然后,將σc和σ1?c依次發(fā)送給A;

(6)A輸出一個(gè)c的猜測值c′∈{0,1}.

敵手A贏得挑戰(zhàn)的優(yōu)勢為,其中,Pr(c=c′)是c=c′的概率.若敵手A以不可忽略的優(yōu)勢猜測正確,則挑戰(zhàn)成功.

2.不可偽造性

定義4.對于任意的消息m,敵手A通過盲簽名交互過程,成功偽造一個(gè)有效的簽名并能通過驗(yàn)證的概率是可以忽略的.

對于不可偽造性的安全模型,通過游戲Game2 進(jìn)行形式化定義.

Game2:敵手A和消息擁有者O的盲簽名交互過程如下所述.

(1)O通過運(yùn)行系統(tǒng)初始化算法生成系統(tǒng)參數(shù),同時(shí),通過運(yùn)行密鑰生成算法生成簽名的公私鑰對,然后將系統(tǒng)參數(shù)和公鑰發(fā)送給A;

(2)O訪問隨機(jī)預(yù)言機(jī),A通過公開的公鑰猜測簽名的私鑰,與隨機(jī)預(yù)言機(jī)分別進(jìn)行t次盲簽名交互過程,得到簽名δj和σj(j=1,2,…,t);

(3)經(jīng)過驗(yàn)證算法,簽名δj和σj都驗(yàn)證成功.

如果敵手贏得游戲的事件用Win表示,則敵手A獲勝的優(yōu)勢可定義為.如果等式δj=σj成立的概率可以忽略,則敵手A贏得挑戰(zhàn)的優(yōu)勢可以忽略,故而盲簽名具有不可偽造性.

3.不可追蹤性

定義5.簽名σ公布以后,即使留有當(dāng)時(shí)的盲消息,簽名者B也無法確定是他何時(shí)簽署的.

對于不可追蹤性的安全模型,通過下面Game3 進(jìn)行形式化定義.

Game3:挑戰(zhàn)者C(模擬簽名者B)和消息擁有者O的盲簽名交互過程如下所述.

(1)O通過運(yùn)行系統(tǒng)初始化算法生成系統(tǒng)參數(shù),同時(shí),通過運(yùn)行密鑰生成算法生成簽名的公私鑰對,并將系統(tǒng)參數(shù)和私鑰發(fā)送給C;

(2)O隨機(jī)選取兩個(gè)等長的不同的盲因子eθ和e1?θ,然后選擇一個(gè)隨機(jī)的比特θ∈{0,1},將消息m作為輸入,執(zhí)行盲簽名中的盲化算法,生成盲化消息bθ和b1?θ,并將bθ和b1?θ隨機(jī)發(fā)送給C;

(3)C對bθ和b1?θ依次執(zhí)行盲簽名中的簽名算法,生成盲簽名θσ′ 和σ1θ?′ ,然后將θσ′ 和σ1θ?′ 依次發(fā)送給O;

(4)O利用盲因子eθ和e1?θ對盲簽名θσ′ 和σ1θ?′ 去盲化處理,得到簽名σθ和σ1?θ;然后,將σθ和σ1?θ依次發(fā)送給C;

(5)C輸出一個(gè)θ的猜測值θ′∈{0,1}.

挑戰(zhàn)者C贏得挑戰(zhàn)的優(yōu)勢為,其中,Pr(θ=θ′)是θ=θ′的概率.若挑戰(zhàn)者C以不可忽略的優(yōu)勢猜對,則挑戰(zhàn)成功.

1.3 Lu等人改進(jìn)的多變量簽名模型

Lu 等人[22]改進(jìn)了Wang 等人[20]的簽名模型,即把文獻(xiàn)[20]中的秘密仿射變換M改為非線性可逆變換L,其結(jié)構(gòu)如下.

私鑰:L,S和Q中的某些參數(shù).

公鑰:h?L?1,h?N?1和N?Q?S,其中,N(N≠E,N≠L)是一秘密仿射變換,E表示恒等變換,h是一個(gè)保密的單向不可逆哈希函數(shù).

簽名:設(shè)v是消息m的哈希值,依次計(jì)算y=L?1(v),x=Q?1(y)和σ=S?1(x),σ即為簽名.

驗(yàn)證:輸入公鑰P=N?Q?S和簽名σ,輸出w=N?Q?S(σ),驗(yàn)證h?L?1(v)=h?N?1(w)是否成立:若成立,則接受簽名;否則,拒絕簽名.

1.4 Yasuda等人提出的非滿射中心映射

設(shè)r是多變量方程組的個(gè)數(shù),n是變量的個(gè)數(shù).這里的r和n均為有限的正整數(shù),并且滿足n=z2,r=z(z+1)/2.Yasuda 等人[23]利用非滿射來構(gòu)造多變量的中心映射,具體結(jié)構(gòu)如下:

2 方案實(shí)例

本節(jié)給出了一個(gè)具體的抗量子計(jì)算的多變量盲簽名方案.詳細(xì)算法細(xì)節(jié)如下所述.

1.系統(tǒng)初始化(Setup)

生成系統(tǒng)參數(shù)(F,p,l,r,n,H),其中,F=GF(pl)是特征為p的有限域,r是多變量方程組的個(gè)數(shù),n是變量的個(gè)數(shù),哈希函數(shù)H:{0,1}*→Fr.這里的p是素?cái)?shù),l,r和n均為有限的正整數(shù).

2.密鑰生成(KeyGen)

生成簽名者B的私鑰sk:{L?1,G?1,S?1}和公鑰pk:{N?G?S,h?L?1,h?N?1},公開公鑰,其中,G:Fn→Fr是非滿射中心映射,具體結(jié)構(gòu)參照本文第1.4 節(jié)和文獻(xiàn)[23]中的fδ,B.L:Fr→Fr是隨機(jī)選取的非線性可逆變換,N和S分別是Fr→Fr,Fn→Fn隨機(jī)選取的可逆仿射變換,h是一個(gè)保密的單向不可逆哈希函數(shù).

3.盲簽名(BlindSIG)

(1)對消息m增加幾個(gè)隨機(jī)比特m′[24];

下面介紹如何給消息m增加幾個(gè)隨機(jī)比特m′:

b)令m′=[W]0→2為2-bit 字符串.

(2)盲化(Blind):O隨機(jī)選取盲因子e∈F,計(jì)算b=eH(m||m′),將盲化后的消息b發(fā)送給B;

(3)簽名(Sign):B收到b后,用私鑰sk:{L?1,G?1,S?1}依次計(jì)算y=L?1(b),x=G?1(y),若y沒有與之對應(yīng)的原像x,則返回步驟(1),并用H(W)替換步驟a)中的W;否則繼續(xù)計(jì)算σ′=S?1(x),然后將盲簽名σ′發(fā)送給O;

現(xiàn)在說明一下簽名失敗的概率:根據(jù)文獻(xiàn)[24]的證明,對消息m增加幾個(gè)隨機(jī)比特m′,在簽名過程中,y沒有與之對應(yīng)的原像x的概率約為2?85,即簽名失敗的概率約為2?85.這個(gè)概率是可以完全忽略不計(jì)的,因此對簽名過程的效率影響可以忽略不計(jì).

(4)去盲化(MoveBlind):O收到B的盲簽名σ′后,先驗(yàn)證h?N?1(N?G?S(σ′))=h?L?1(b)是否成立:若成立,O對盲簽名σ′去盲化處理,計(jì)算σ=σ′/e2,得到簽名σ;否則,簽名無效.

4.驗(yàn)證(Verify)

輸入系統(tǒng)參數(shù)、消息m||m′和B的公鑰,驗(yàn)證者計(jì)算h?L?1(H(m||m′)),并用公鑰N?G?S和h?N?1驗(yàn)證等式h?L?1(H(m||m′))=h?N?1(N?G?S(σ))是否成立:若等式成立,則簽名有效;否則,簽名無效.

3 正確性分析

根據(jù)第1.2.1 節(jié)中盲簽名的定義,只有合法的盲簽名才能通過驗(yàn)證.在證明本文方案滿足正確性之前,先介紹用到的相關(guān)性質(zhì).

性質(zhì)1[23].若一有限域F,V是有限域F上的n維向量空間.當(dāng)映射?:V→F具有二次形式時(shí),有:

?(ax)=a2?(x),

其中,a∈F,x∈V.

定理1.本文提出的抗量子計(jì)算的多變量盲簽名方案是正確的.

證明:對消息m增加幾個(gè)隨機(jī)比特m′,假設(shè)對m||m′進(jìn)行盲簽名交互過程,可以產(chǎn)生一個(gè)有效的簽名.若接收方收到消息m||m′的簽名σ是按上述簽名步驟進(jìn)行的,并且在傳播過程中沒有被篡改,則:

h?N?1(N?G?S(σ))=h?N?1(N?G?S(σ′/e2))=h?N?1(N?G?S(sk(eH(m||m′))/e2)).

根據(jù)性質(zhì)1 可得:

sk(eH(m||m′))=e2sk(H(m||m′)).

所以,

h?N?1(N?G?S(σ))=h?N?1(N?G?S(sk(H(m||m′))))=h?L?1(H(m||m′)).

可見,驗(yàn)證等式h?L?1(H(m||m′))=h?N?1(N?G?S(σ))成立.這說明所構(gòu)造的抗量子計(jì)算的多變量盲簽名方案是正確的.證畢.□

4 安全性分析

4.1 盲 性

定理2.本文提出的抗量子計(jì)算的多變量盲簽名方案滿足盲性.

證明:利用第1.2.2 節(jié)中的Game1 安全模型證明所提方案滿足盲性.假設(shè)敵手A偽裝成簽名者B與挑戰(zhàn)者C進(jìn)行盲簽名交互過程.

可見,敵手A無法以不可忽略的優(yōu)勢贏得挑戰(zhàn).從而證明了所構(gòu)造的抗量子計(jì)算的多變量盲簽名方案滿足盲性.證畢.□

4.2 不可偽造性

定理3.如果IP 問題在有限域F上是困難的,那么本文提出的抗量子計(jì)算的多變量盲簽名方案滿足不可偽造性.

?證法1

證明:利用第1.2.2 節(jié)中的Game2 安全模型,采用反證法證明所提方案滿足不可偽造性.對于一個(gè)消息m,先對消息m增加幾個(gè)隨機(jī)比特m′,假設(shè)對m||m′進(jìn)行盲簽名交互過程,可以產(chǎn)生一個(gè)有效的簽名.以一次盲簽名交互過程為例,假設(shè)敵手A成功地偽造了一個(gè)有效的盲簽名δ′,同時(shí),隨機(jī)預(yù)言機(jī)產(chǎn)生了一個(gè)真實(shí)的盲簽名σ′,并且經(jīng)過消息擁有者O去盲化后,得到的簽名δ和σ都能夠通過驗(yàn)證.

(1)若δ=σ,根據(jù)去盲化過程,有:

δ′/e2=σ′/e2.

根據(jù)簽名過程,有:

δ′=sk(eH(m||m′))′=e2sk(H(m||m′))′,σ′=sk(eH(m||m′))=e2sk(H(m||m′)),

則:

e2sk(H(m||m′))′/e2=e2sk(H(m||m′))/e2,sk(H(m||m′))′=sk(H(m||m′)).

若想要上式成立,那么敵手A必須得到簽名者B的私鑰{L?1,G?1,S?1}.由于h是一個(gè)保密的單向不可逆哈希函數(shù),所以通過h?L?1和h?N?1求得L?1和N?1是不可行的,由N?G?S得到N?1,G?1,S?1是不可行的,這相當(dāng)于解決IP 困難問題.

(2)若δ≠σ,根據(jù)去盲化過程,有:

δ′/e2≠σ′/e2.

根據(jù)簽名過程,有:

e2sk(H(m||m′))′/e2≠e2sk(H(m||m′))/e2,sk(H(m||m′))′≠sk(H(m||m′)).

通過上式可知,敵手A不可能偽造一個(gè)有效的簽名.

綜上所述,經(jīng)過t次盲簽名交互過程,所得到的有效簽名δj和σj都通過驗(yàn)證,若想要簽名δj=σj(j=1,2,…,t),則必須得到簽名者B的私鑰{L?1,G?1,S?1}.由公鑰N?G?S,h?L?1和h?L?1得到私鑰{L?1,G?1,S?1},這相當(dāng)于解決IP 問題.因此,敵手A無法以不可忽略的優(yōu)勢贏得挑戰(zhàn),假設(shè)不成立.從而證明了若IP 問題在有限域F上是困難的,則所構(gòu)造的抗量子計(jì)算的多變量盲簽名方案滿足不可偽造性.證畢.□

?證法2

證明:對于一個(gè)消息m,先對消息m增加幾個(gè)隨機(jī)比特m′,假設(shè)對m||m′進(jìn)行盲簽名交互過程,可以產(chǎn)生一個(gè)有效的簽名.分別用列表LH,LS和LV記錄H詢問、簽名詢問和驗(yàn)證詢問,所用列表初始均為空.最多可以執(zhí)行qLH次H詢問、qLS次簽名詢問和qVL次驗(yàn)證詢問.假設(shè)敵手A以不可忽略的優(yōu)勢ε成功偽造簽名,則存在挑戰(zhàn)者C以不可忽略的優(yōu)勢ε′解決IP 問題.

挑戰(zhàn)者C運(yùn)行系統(tǒng)初始化算法和密鑰生成算法,將系統(tǒng)參數(shù)(F,p,l,r,n,H)和公鑰發(fā)送給敵手A.

(1)H詢問:當(dāng)A向C請求關(guān)于m||m′的H詢問時(shí),首先,C查詢列表LH:若LH中存在相應(yīng)的記錄(m||m′,H),則C直接返回結(jié)果H給A;否則,C隨機(jī)選取H∈Fr發(fā)送給A,同時(shí)將(m||m′,H)添加到列表LH中;

(2)簽名詢問:當(dāng)A向C請求關(guān)于m||m′的簽名詢問時(shí),首先,C查詢簽名列表LS:若LS中存在相應(yīng)的記錄,則返回簽名σ;否則,調(diào)用H詢問(若在此詢問之前,表中已經(jīng)存在此詢問記錄,則偽造簽名失敗),再執(zhí)行盲簽名算法得到簽名σ,然后將此記錄添加到簽名列表LS中;

(3)驗(yàn)證詢問:當(dāng)A向C請求關(guān)于m||m′的驗(yàn)證詢問時(shí),首先,C查詢驗(yàn)證列表LV:若LV中存在相應(yīng)的記錄,則返回消息m||m′;否則,執(zhí)行驗(yàn)證算法得到m||m′.再對LH進(jìn)行查找:若存在相應(yīng)的記錄,則返回m||m′;否則,拒絕這個(gè)簽名.

經(jīng)過多次盲簽名交互過程后,A提交一個(gè)偽造的簽名σ*.

通過上面的詢問,如果敵手A想要偽造一個(gè)有效的簽名σ*,他必須得到簽名者B的私鑰{L?1,G?1,S?1}.由N?G?S,h?L?1和h?N?1得到私鑰{L?1,G?1,S?1},這相當(dāng)于解決IP 問題.

我們用E1和E2表示敵手A偽造簽名失敗的事件.

1)E1:當(dāng)在步驟(2)簽名詢問時(shí),重新調(diào)用的H詢問已經(jīng)在步驟(1)中所記錄,則偽造簽名失敗.這個(gè)優(yōu)勢為:

2)E2:當(dāng)在步驟(3)驗(yàn)證詢問時(shí),拒絕了一個(gè)有效的簽名.這個(gè)優(yōu)勢為.

因此,挑戰(zhàn)者C解決IP 問題的優(yōu)勢是ε′=Pr[E1∧E2∧E3∧E4].又因?yàn)楦魇录g是相互獨(dú)立的,所以挑戰(zhàn)者C解決IP 問題的優(yōu)勢為

可見,挑戰(zhàn)者C無法以不可忽略的優(yōu)勢ε′解決IP 問題.從而證明了如果IP 問題在有限域F上是困難的,那么所構(gòu)造的抗量子計(jì)算的多變量盲簽名方案滿足不可偽造性.證畢.□

4.3 不可追蹤性

定理4.本文提出的抗量子計(jì)算的多變量盲簽名方案滿足不可追蹤性.

證明:利用第1.2.2 節(jié)中的Game3 安全模型證明所提方案滿足不可追蹤行性.下面介紹挑戰(zhàn)者C(模擬簽名者B)和消息擁有者O的盲簽名交互過程.

(1)O通過運(yùn)行系統(tǒng)初始化算法生成系統(tǒng)參數(shù)(F,p,l,r,n,H),同時(shí),通過運(yùn)行密鑰生成算法生成簽名的公私鑰對,并將系統(tǒng)參數(shù)和私鑰發(fā)送給C;

(2)對消息m增加幾個(gè)隨機(jī)的比特m′,假設(shè)對m||m′進(jìn)行盲簽名交互過程可以產(chǎn)生一個(gè)有效的簽名;

(3)O隨機(jī)選取兩個(gè)等長的不同的盲因子e0∈F和e1∈F;

(4)O選擇一個(gè)隨機(jī)的比特值θ∈{0,1},然后計(jì)算bθ=eθH(m||m′)和b1?θ=e1?θH(m||m′),然后將bθ和b1?θ以隨機(jī)順序發(fā)送給C;

(5)C先后分別依次計(jì)算:

(6)O利用盲因子eθ和e1?θ計(jì)算簽名和,并將σθ和σ1?θ先后發(fā)送給C;

(7)C輸出一個(gè)θ的猜測值θ′∈{0,1}.

現(xiàn)在分析挑戰(zhàn)者C猜對θ的概率.因?yàn)槊ひ蜃觘θ和e1?θ是消息擁有者O在有限域F上隨機(jī)選取的,而且選取的過程完全獨(dú)立于消息m||m′,因此盲因子eθ和e1?θ、消息m||m′、簽名σθ和σ1?θ這三者之間完全相互獨(dú)立.對于挑戰(zhàn)者C,在不知道盲因子的條件下,無法將消息、盲簽名、簽名這三者聯(lián)系起來.因此,即使C擁有無限的計(jì)算能力,他猜對θ的概率只有1/2,即Pr(θ=θ′)=1/2,則挑戰(zhàn)者C贏得挑戰(zhàn)的優(yōu)勢是:

可見,挑戰(zhàn)者C無法以不可忽略的優(yōu)勢贏得挑戰(zhàn).從而證明了所構(gòu)造的抗量子計(jì)算的多變量盲簽名方案滿足不可追蹤性.證畢.□

5 效率分析

簽名效率主要取決于簽名的公鑰長度、私鑰長度和簽名長度.本節(jié)依據(jù)這3 個(gè)要素分析本文構(gòu)造的抗量子計(jì)算的多變量盲簽名方案與類似方案的性能.由文獻(xiàn)[24]和L,N的構(gòu)造過程可知,對消息m增加幾個(gè)隨機(jī)的比特m′和增加公鑰h?N?1,h?L?1并不影響整個(gè)盲簽名交互過程的運(yùn)算效率.表1 從簽名的公鑰長度、私鑰長度和簽名長度分析文獻(xiàn)[18,19]和本文方案的效率.

表1 中的r為多變量方程組的個(gè)數(shù),n為變量的個(gè)數(shù).從表1 可看出:由于本文方案只采用一個(gè)非滿射中心映射,所以和文獻(xiàn)[18]相比,簽名的私鑰長度減少了50%;與文獻(xiàn)[19]相比,公鑰長度和簽名長度都有所減少.

6 結(jié)束語

目前,大多數(shù)盲簽名方案都是基于傳統(tǒng)公鑰密碼體制的.隨著量子計(jì)算技術(shù)的發(fā)展,使得傳統(tǒng)公鑰密碼體制下的盲簽名受到了嚴(yán)重威脅.本文提出了一種基于多變量的抗量子計(jì)算盲簽名方案.所提方案運(yùn)用改進(jìn)的多變量簽名模型,采用一個(gè)非滿射中心映射,將簽名的公私鑰分離,減少了公私鑰之間的線性關(guān)系,提高了盲簽名的安全性.和文獻(xiàn)[18,19]中的方案相比,計(jì)算效率較高.通過安全性分析知,方案具有盲性、不可偽造性和不可追蹤性.本文方案可應(yīng)用在電子現(xiàn)金交易系統(tǒng)、匿名電子投票系統(tǒng)等領(lǐng)域.