基于二次剩余的匿名代理者簽密方案

劉 禎,楊啟良,楊 波

(1.陜西師范大學(xué)計算機科學(xué)學(xué)院,西安710062;2.樹德科技大學(xué)信息學(xué)院,中國臺灣高雄82445)

基于二次剩余的匿名代理者簽密方案

劉 禎1,楊啟良2,楊 波1

(1.陜西師范大學(xué)計算機科學(xué)學(xué)院,西安710062;2.樹德科技大學(xué)信息學(xué)院,中國臺灣高雄82445)

由于現(xiàn)有簽密方案大多基于雙線性對,配對運算計算量較大,且實現(xiàn)效率不高,不能滿足對代理簽密者的匿名要求,因此無需配對的簽密方案是密碼學(xué)的研究方向。而基于二次剩余的簽名方案不僅具有描述簡單,能夠抵抗選擇密文攻擊的優(yōu)點,且相較于基于配對的簽名方案具有更高的實現(xiàn)效率。為此,將二次剩余的方法應(yīng)用到簽密方案中,并結(jié)合匿名性,提出一種基于二次剩余的匿名代理者簽密方案。分析結(jié)果表明,該方案具有匿名性與公開驗證性。

代理者簽密;匿名性;二次剩余;隨機預(yù)言機模型;公開驗證;可追蹤性;不可否認(rèn)性

1 概述

1997年,文獻(xiàn)[1]提出了簽密體制,即在一個合理的邏輯步驟內(nèi)同時完成數(shù)字簽名和公鑰加密2項功能,而計算量和通信成本都低于傳統(tǒng)的“先簽名后加密”。在文獻(xiàn)[1]提出簽密體制后,簽密就得到了廣泛的應(yīng)用,如電子支付、移動代理安全等。隨著簽密體制的廣泛應(yīng)用以及應(yīng)用場合的不同,又有許多新的有效的簽密體制被相繼提出[2-4]。1999年,文獻(xiàn)[5]首先提出了代理簽密體制。代理簽密體制主要是為了滿足原始簽密者由于出差等原因無法親自對消息進(jìn)行簽密,而將簽密權(quán)利授權(quán)給代理簽密者。授權(quán)信息一般包括原始簽密者的身份信息、代理簽密者的權(quán)利范圍和代理簽密的時間限制等。隨著代理簽密體制的廣泛應(yīng)用,又衍生出來新的代理簽密體制,如基于身份的代理簽密體制[6]、無證書的代理重簽密[7]等。

現(xiàn)有的大多數(shù)代理簽密方案都是基于雙線性對的,而配對運算需要很大的計算量,故使用無配對的簽密方案是密碼學(xué)的研究方向。近年來,由于基于二次剩余構(gòu)造的簽名方案幾乎對明文空間沒有限制,描述簡單,并且可抵抗選擇密文攻擊,因此使用二次剩余構(gòu)造的簽名方案得到了廣泛研究。2000年,文獻(xiàn)[8]利用二次剩余提出了一個新的Rabin簽名方案,又在2005年文獻(xiàn)[9]利用二次剩余提出一個基于身份的簽名方案。2001年,文獻(xiàn)[10]利用二次剩余構(gòu)造了一個基于身份的簽名方案。2009年,文獻(xiàn)[11]也提出了一個利用二次剩余構(gòu)造的基于身份的簽名方案。2012年,文獻(xiàn)[12]不僅利用二次剩余構(gòu)造出了一個代理簽名方案,同時比較了基于二次剩余困難問題的代理簽名方案與基于其他數(shù)學(xué)難題的代理簽名方案,得出基于二次剩余困難問題的方案在抵抗相同敵手的情況下具有更高效率的結(jié)論。由此,可以看出基于二次剩余構(gòu)造方案具有很重要的研究意義。

2005年,文獻(xiàn)[13]提出一種新型代理簽名方案,該方案指出在很多特殊的場合下,原始簽名者并不希望驗證者知道代理簽名者的身份,從而將代理簽名者的身份保護(hù)起來,使得驗證者從簽名結(jié)果中無法獲取代理簽名者的身份信息。本文通過將代理簽密與身份隱藏相結(jié)合,構(gòu)造一種基于二次剩余的匿名代理者簽密方案,并給出預(yù)言機模型下的安全性證明。

2 預(yù)備知識

2.1 二次剩余

定義1 設(shè)n是正整數(shù),a是整數(shù),(a,n)=1。若同余式x2≡amodn有解,則a為模n的平方剩余(或二次剩余);否則,a為模n的平方非剩余(或二次非剩余)。定義符號Qn為二次剩余,為二次非剩余。

2.2 勒讓德符號

定義2 設(shè)p是素數(shù),a是整數(shù),定義勒讓德符號如下:

2.3 合數(shù)的二次剩余

命題1設(shè)N=pq,其中,p和q是不同的素數(shù);且滿足y=yp·yq。當(dāng)yp為關(guān)于p的二次剩余,yq為關(guān)于q的二次剩余,則y是一個關(guān)于模N的二次剩余[14]。

2.4 Blum整數(shù)

定義3若p,q為不相等的素數(shù),且p,q均為模4與模3同余的素數(shù),則稱N=pq為Blum整數(shù)。

2.5 Williams整數(shù)

定義4設(shè)N為一個合數(shù),N=pq,且p,q是不同的素數(shù),其中,p=3mod8,q=7mod8,則稱N為Williams整數(shù)。

定理2若x∈Jn,N=pq是一個Blum整數(shù),則有:

3 匿名代理者簽密方案模型

3.1 匿名代理者簽密系統(tǒng)的定義

方案中有3個參與者:原始簽密者Alice、代理簽密者Bob和驗證者Verifier。7個算法,即初始化、公私鑰對生成算法、身份存儲算法、委托算法、代理簽密算法、解簽密算法、揭示代理簽密者身份算法。具體如下:

(1)初始化:輸入?yún)?shù)1n,輸出系統(tǒng)所用的參數(shù)params。

(2)公私鑰對生成算法:輸入系統(tǒng)參數(shù)params,輸出Alice、Bob和Verifier的公私鑰對(PKa,SKa), (PKb,SKb)和(PKv,SKv)。

(3)身份存儲算法:輸入系統(tǒng)參數(shù)params、Bob的身份信息ID、Bob生成的隨機值R,輸出Bob的身份信息的數(shù)字簽名σ1。Alice存儲此簽名。

(4)委托算法:輸入系統(tǒng)參數(shù)params、授權(quán)信息mw和Alice的私鑰SKa,輸出Alice委托Bob的委托簽名σ2。

(5)代理簽密算法:輸入系統(tǒng)參數(shù)params、委托信息mw、Alice的公鑰PKa、Alice生成的隨機值Ra、Bob的私鑰SKb,生成代理簽密私鑰(PK0,SK0)。輸入Verifier的公鑰PKv和簽密的消息m,輸出簽密消息σ。

(6)解簽密算法:輸入系統(tǒng)參數(shù)params、簽密結(jié)果σ和Verifier的私鑰SKv,驗證消息的有效性并恢復(fù)消息m。

(7)揭示代理簽密者身份算法:輸入簽密結(jié)果σ和Alice的公鑰PKa,Alice驗證簽密消息是否有效。若有效,輸出代理簽密者的身份信息ID。

3.2 匿名代理者簽密系統(tǒng)的安全性

方案的安全性需求包括機密性、強不可偽造性、強不可否認(rèn)性、匿名性、公開驗證性、可追蹤性和防止代理權(quán)濫用。具體如下:

(1)機密性:從簽署的密文中,只有驗證者才可以恢復(fù)出明文消息,其他任何人通過密文獲得消息的任何內(nèi)容在計算上都是不可行的。

(2)強不可偽造性:任何第三方,包括原始簽名者,如果未被指定作為代理簽名者,都無法產(chǎn)生有效的代理簽名。

(3)強不可否認(rèn)性:在簽密出現(xiàn)爭議的時候,原始簽密者可以揭示代理簽密者的身份,并且對這個身份信息,代理簽密者無法否認(rèn)。

(4)匿名性:驗證者無法從簽密結(jié)果,授權(quán)信息等獲得代理簽密者的身份信息,只有通過原始簽密者才可以揭示代理者的身份。

(5)公開驗證性:任何人可以驗證簽密結(jié)果的有效性,判斷此簽密是否為一個原始簽密者承認(rèn)的有效簽密。

(6)可追蹤性:原始簽密者可以追蹤代理簽密者的身份信息。

(7)防止代理權(quán)濫用:代理簽密者簽署消息不能超出委托信息的范圍,如果濫用,則造成的后果將由代理簽密者負(fù)責(zé),并且代理權(quán)是不可轉(zhuǎn)移的。

3.3 不可偽造性的攻擊模型

為了定義合理的攻擊模型,假設(shè)敵手擁有更大的自由度,可以模擬現(xiàn)實生活中的各種行為。攻擊模型中除了一個外部攻擊者,還有2種類型的內(nèi)部攻擊者。

類型1A1是一個外部敵手,只有Alice和Bob的公鑰。

類型2A2是一個惡意簽密者,有Bob的私鑰。

類型3A3是一個惡意原始簽密者,有Alice的私鑰。

顯然,如果這個簽密系統(tǒng)可以抵抗第2類型和第3類型的惡意敵手,那么它一定可以抵抗第1類型的敵手。為此,構(gòu)造2種類型的攻擊模型。

下面證明匿名代理簽密方案在第2類型的敵手A2攻擊下存在不可偽造性。

代理簽密系統(tǒng)在第2類型的敵手A2攻擊下存在不可偽造性,即沒有給定委托證書mw,或者即使獲得符合委托證書mw的消息m,偽造一個有效簽密也是困難的。為了描述匿名代理簽密方案在第2類敵手攻擊下具有不可偽造性,構(gòu)造一個參與者為挑戰(zhàn)者C和第2類型的敵手A2的交互游戲:

(1)初始化:挑戰(zhàn)者C運行初始化算法得到系統(tǒng)參數(shù),運行公私鑰對生成算法,得到原始簽密者Alice和代理簽密者Bob的公私鑰對(PKa,SKa)和(PKb,SKb),之后挑戰(zhàn)者C發(fā)送(PKa,PKb,SKb)給敵手A2。

(2)敵手A2進(jìn)行一系列(多項式有界次)適應(yīng)性詢問。

(3)委托詢問:A2詢問委托信息mw。挑戰(zhàn)者C運行委托算法得到σw,并將σw發(fā)送給A2。

(4)代理簽密詢問:A2詢問關(guān)于σw的消息m的代理簽密。挑戰(zhàn)者C運行代理簽密算法,得到簽密σ,并將σ返回給A2。

定義5如果沒有任何多項式有界的第2類敵手A2在多項式時間t內(nèi),以qw次委托詢問,qps次代理簽密詢問,以一個比ε更大的優(yōu)勢贏得上面的游戲,則稱匿名代理簽密方案在適應(yīng)性選擇消息攻擊下是(t,qw,qps,ε)存在性不可偽造的。

下面證明匿名代理簽密方案在第3類型的敵手A3攻擊下存在不可偽造性。

代理簽密系統(tǒng)在第3類型的敵手A3攻擊下存在不可偽造性,也就是說原始簽密者很難對消息m?生成一個指定為代理簽密者的有效簽密。為了描述匿名代理簽密方案在第3類型的敵手攻擊下存在不可偽造性,構(gòu)造一個參與者為挑戰(zhàn)者C和第3類型的敵手A3的交互游戲:

(1)初始化:挑戰(zhàn)者C運行初始化算法得到系統(tǒng)參數(shù),運行公私鑰對生成算法,得到原始簽密者Alice和代理簽密者Bob的公私鑰對(PKa,SKa)和(PKb,SKb)。之后,運行代理簽密算法,得到代理簽密公私鑰對(PK0,SK0)。挑戰(zhàn)者C發(fā)送(PK0,PKa,SKa)給敵手A3。

(2)代理簽密詢問:敵手A3運行關(guān)于σw的消息m的代理簽密詢問。挑戰(zhàn)者C運行代理簽密算法,得到簽密σ,并將σ返回給A3。

定義6如果沒有任何多項式有界的第3類敵手A3在多項式時間t內(nèi),以qps次代理簽密詢問,以一個比ε更大的優(yōu)勢贏得上面的游戲,則稱匿名代理簽密方案在適應(yīng)性選擇消息攻擊下是(t,qps,ε)存在性不可偽造的。

4 方案實現(xiàn)

本文方案利用二次剩余進(jìn)行設(shè)計。可以用簽密者的門牌號或者電子郵箱等作為代理簽密者的身份信息ID。其中,(Na,pa,qa)為原始簽密者的公私鑰對;(Nb,pb,qb)為代理簽密者的公私鑰對;(Nv,pv,qv)為驗證者的公私鑰對;(N0,p0,q0)為代理公私鑰對。

4.1 身份儲存算法

原始簽密者發(fā)出需要Bob代理簽密的請求,Bob向原始簽密者證明自己的身份。

并利用自己的私鑰pb,qb計算:

4.2 委托算法

Alice確定Bob的身份后,生成委托信息,發(fā)送委托信息給Bob,授予Bob簽密權(quán)利。

并利用自己的私鑰pa,qa計算:

4.3 代理簽密算法

如果消息符合委托信息的約定,Bob利用委托信息進(jìn)行代理簽密。

首先,Bob計算x≡S2modpb,并令p0為與x右相鄰,且滿足p0≡3mod8的大素數(shù),q0=qb≡7mod8,其中,p0,q0為代理私鑰,并且令N0=p0q0。則N0作為代理公鑰。其次,Bob隨機選取,計算T=t2modNv,C=Enct(m),Z=t·S2·C·YpmodNv(Yp從授權(quán)信息中獲得)。并且分別計算a0,b0的值:

利用代理簽密私鑰p0,q0計算:

4.4 解簽密算法

Verifier對收到的簽密消息進(jìn)行驗證。首先, Verifier檢查代理簽密是否符合代理委托信息mw的約定。如果符合,則進(jìn)行下一步。若不符合,則拒絕此簽密結(jié)果。然后,Verifier計算:

Verifier檢驗h1=H2(Ra,mw,C,Z,T′)是否成立。若成立,則進(jìn)行下一步。Verifier通過自己的私鑰(pv,qv),首先利用中國剩余定理恢復(fù)出密鑰t,再利用對稱加密算法Dect(m)恢復(fù)出消息m,如果消息與需要簽密的消息一致,那么接受簽密結(jié)果,否則拒絕。

4.5 揭示代理簽密者身份的算法

當(dāng)驗證者對代理簽密結(jié)果有爭議時,可通過原始簽密者揭示代理簽密者的身份。

5 方案的安全性驗證

公開驗證性:

由上式可看出,任何人都可以驗證該簽密結(jié)果的有效性。因此,方案具有公開驗證性。

在證明過程中,構(gòu)造一個算法B,B的任務(wù)是解決因式分解實例,即給定一個輸入N=p×q,以不可忽略的概率輸出p,q。證明中,B模擬C與A2進(jìn)行交互。由于A2這種類型的敵手擁有代理簽密者的公私鑰對,因此他能給出任意的身份信息,故身份存儲算法將不再需要。B運行A2作為子程序,回答A2的詢問。

(2)委托詢問:A2可以在任何時候進(jìn)行至多qw次委托詢問。當(dāng)B收到A2關(guān)于委托信息mwi發(fā)的委托詢問時,B首先在H1列表上搜尋(Rai,mwi,S2i,a2i,b2i,h1i),若存在,則返回(Rai,mwi,S2i,a2i,b2i)給A2。否則,B將如同在H1查詢中一樣,在H1列表中添加包含委托信息mwi的新項,并將(Rai,mwi,S2i,a2i,b2i)發(fā)送給A2。

(4)代理簽密詢問:A2可以在任何時候進(jìn)行至多qps次代理簽密詢問。當(dāng)B收到A2對代理簽密的詢問時,B首先會從H1列表上查詢符合消息mi的委托信息mwi是否存在(Rai,mwi,S2i,a2i,b2i,h1i)上,并且(Rai,mwi,S2i,a2i,b2i,h1i)是否出現(xiàn)在H1列表上。如果沒有,B將如同在H1查詢中一樣在H1列表中添加包含委托信息mwi的新項。B得到與委托信息mwi相對應(yīng)的值(S2i,a2i,b2i)和隨機值Rai。由于A2有代理簽密者的私鑰(pb,qb),因此A2首先通過代理簽密算法生成代理簽密公私鑰對(N0,p0,q0),然后再生成符合委托信息mwi的消息m的有效簽密。

下面考慮解決整數(shù)分解問題:在隨機預(yù)言機模型下,B的輸出和協(xié)議真實執(zhí)行的輸出是不可區(qū)分的。因此,通過一系列的培訓(xùn),A2將以概率ε輸出符合委托信息的消息m?的有效代理簽密。如果敵手沒有詢問,那么σ?為有效的概率小于,因為回答H1哈希函數(shù)是隨機選取的。因此,A2在詢問H1預(yù)言機后會以概率輸出一個有效代理簽密。為了分解N,方案利用文獻(xiàn)[15-16]的重放攻擊技巧,讓B重新與A2進(jìn)行第2次交互。每次交互中,至多進(jìn)行qw次委托詢問。第2次交互與第1次交互的輸入完全相同,且對每次的回答也與第1次相同。直到對第i點進(jìn)行查詢,停止輸出,重新均勻選擇,輸出。如果A2在第2次交互后能輸出一個有效簽密,那么B就可以得到一對簽密,和。故可以得到的概率為,所以的概率為。并且可以以的概率使得為N的一個非平凡因子。

對于指定相同輸入,2次游戲得到的簽密都是基于第i點的,根據(jù)文獻(xiàn)[17]通用分叉引理的結(jié)論,可得基于第i點查詢的概率為:而第i點恰好為偽造簽密的委托信息的概率為,故可得到分解N的概率為:

定理5 在ROM中,如果存在一個第3類型的敵手A3,在概率多項式時間內(nèi)以不可忽略的概率ε在定義6中的游戲獲勝,那么存在一個算法B利用

定理5的證明方法與定理4類似。由于篇幅有限,這里將不再證明。

6 結(jié)束語

本文將代理者簽密與身份隱藏進(jìn)行有效結(jié)合,構(gòu)造一種基于二次剩余的匿名代理者簽密方案。分析結(jié)果表明,該方案具有不可偽造性。今后將研究方案的保密性,并在抗泄漏的條件下對其進(jìn)行改進(jìn),從而進(jìn)一步提高其應(yīng)用性能。

[1] Zheng Yuliang.Digital Signcryption or How to Achieve Cost(Sign-ature&Encryption Cost)＜＜Cost(Signature)+Cost(Encryption)[C]//Proceedings of the 17th Annual International Cryptology Conference.Santa Barbara,USA:[s.n.],1997:165-179.

[2] Steinfeld R,Zheng Yuliang.A Signcryption Scheme Based on Integer Factorization[C]//Proceedings of the 3rd International Workshop on Information Security. Wollongong,Australia:[s.n.],2000:131-146.

[3] Li Fagen,TsuyoshiT.SecureIdentity-based Signcryption in the Standard Model[J].Mathematical and Computer Modelling,2013,57(11/12):2685-2694.

[4] Pang Liaojun,Li Huixian,Gao Lu,et al.Completely Anonymous Multi-recipient Signcryption Scheme with Public Verification[J].PLOS One,2013,8(5).

[5] Gamage G,LeiwoJ,ZhengYuliang.AnEfficient Scheme for Secure Message Transmission Using Proxy Signcryption[C]//Proceedings of the 22nd Australasian Computer Science.Berlin,Germany:[s.n.],1999: 420-431.

[6] 王 琴.一種基于身份的代理簽密體制[J].計算機工程,2011,37(19):120-121,125.

[7] 王會歌,王彩芬,曹 浩,等.無證書代理重簽密方案[J].武漢大學(xué)學(xué)報:理學(xué)版,2012,(4):370-376.

[8] 邱衛(wèi)東,陳克非,白英彩.新型Rabin簽名方案[J].軟件學(xué)報,2000,11(10):1333-1337.

[9] Qiu Weidong,Chen Kefei.Identity Oriented Signature Scheme Based on Quadratic Residues[J].Mathematics and Computation,2005,168(1):235-242.

[10] Clifford C.An Identity Based Encryption Scheme Based on Quadratic Residues[C]//Proceedings of the 8th IMA International Conference on Cryptography and Coding. Cirencester,UK:[s.n.],2001:360-363.

[11] 柴震川,董曉蕾,曹珍富.利用二次剩余構(gòu)造的基于身份的數(shù)字簽名方案[J].中國科學(xué),2009,39(2): 199-204.

[12] Yu Yong,Mu Yi,Susilo W.Provably Secure Proxy Signature Scheme from Factorization[J].Mathematics and Computation Modelling,2012,55(3/4):1160-1168.

[13] 谷利澤,張 勝,楊義先.一種新型代理簽密方案[J].電子與信息學(xué)學(xué)報,2005,27(9):1463-1466.

[14] Jonathan K,LindellY.IntroductiontoModern Cryptography[M].New York,USA:Chapman&Hall/ CRC,2008.

[15] Pointcheval D,Stern J.Security Arguments for Digital Signatures andBlindSignatures[J].Journalof Cryptology,2000,13(3):361-396.

[16] Pointcheval D,Stern J.Security Proofs for Signatures Schemes[EB/OL].(2012-12-20).http://www.di.ens.fr/ users/pointche/Documents/Papers/2000_joc.pdf.

[17] Bellare M,NevenG.Multi-signaturesinthePlain Public-key Model and a General Forking Lemma[C]// Proceedings of the13th Association for Computing Machinery Conference on Computer and Communications Security.Alexandria,USA:[s.n.],2006:390-399.

編輯 劉 冰

Anonymous Proxy Signcryption Scheme Based on Quadratic Residue

LIU Zhen1,YANG Qiliang2,YANG Bo1
(1.School of Computer Science,Shaanxi Normal University,Xi’an 710062,China;
2.College of Informatics,Shu-Te University,Kaohsiung 82445,Taiwan,China)

Most of the existing signcryptions are based on bilinear pairing,but the signcryption without bilinear pairing is a research of cryptography,because the pairing operation requires a lot of computations,and it can not anonymous the proxy signcrypter.The signature scheme based on quadratic residue is widely used with its advantages such as simple description,resistance of chosen ciphertext attack and high efficiency.Its efficient is higher compared with signcryption schemes based on bilinear pairing.This paper adds anonymity to the scheme based on quadratic residue to realize anonymous proxy signcryption.Analysis results show that the scheme not only provides anonymity,but also provides public verifiability.

proxy signcryption;anonymity;quadratic residue;random oracle model;public verification;traceability; non-repudiation

劉 禎,楊啟良,楊 波.基于二次剩余的匿名代理者簽密方案[J].計算機工程,2015,41(2):129-134,140.

英文引用格式:Liu Zhen,Yang Qiliang,Yang Bo.Anonymous Proxy Signcryption Scheme Based on Quadratic Residue[J].Computer Engineering,2015,41(2):129-134,140.

1000-3428(2015)02-0129-06

:A

:TP309.7

10.3969/j.issn.1000-3428.2015.02.025

國家自然科學(xué)基金資助項目(61272436,61370224);廣東省自然科學(xué)基金資助項目(10351806001000000)。

劉 禎(1989-),女,碩士,主研方向:信息安全,密碼學(xué);楊啟良,學(xué)士;楊 波,教授。

2014-02-24

:2014-04-14E-mail:liuzhen0227@126.com