楊小東,李春梅,周思安,王彩芬

一種強(qiáng)不可偽造代理重簽名方案

楊小東,李春梅,周思安,王彩芬

(西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,蘭州730070)

已有的代理重簽名方案大多是存在性不可偽造的,攻擊者能對已經(jīng)簽名過的消息重新偽造一個(gè)有效的簽名,但強(qiáng)不可偽造性能阻止攻擊者對已經(jīng)簽名過的消息簽名對進(jìn)行重新偽造。為此,利用目標(biāo)抗碰撞(TCR)雜湊函數(shù),提出一種雙向代理重簽名方案?；赥CR雜湊函數(shù)的抗碰撞性和計(jì)算性Diffie-Hellman假設(shè),證明方案在適應(yīng)性選擇消息攻擊下是強(qiáng)不可偽造的。分析結(jié)果表明,該方案在計(jì)算效率上優(yōu)于現(xiàn)有的強(qiáng)不可偽造代理重簽名方案,系統(tǒng)公開參數(shù)長度、簽名長度和重簽名長度更短,且滿足更多的安全屬性。

雙向代理重簽名;強(qiáng)不可偽造性;可證明安全;計(jì)算性Diffie-Hellman假設(shè);標(biāo)準(zhǔn)模型

1 概述

代理重簽名具有簽名轉(zhuǎn)換的功能,允許一個(gè)擁有重簽名密鑰的代理者將受托者的簽名轉(zhuǎn)換為委托者對同一個(gè)消息的簽名(也稱重簽名),在跨域身份認(rèn)證、車聯(lián)網(wǎng)隱私保護(hù)等方面有廣泛的應(yīng)用前景。文獻(xiàn)［1］對代理重簽名進(jìn)行了形式化定義。文獻(xiàn)［2］提出一個(gè)在標(biāo)準(zhǔn)模型下可證明安全的雙向代理重簽名方案(下文簡稱Smd方案)。文獻(xiàn)［3］發(fā)現(xiàn)Smd方案存在安全缺陷,提出了一個(gè)改進(jìn)的簽名方案。然而,已有的代理重簽名方案［1-8］幾乎都是存在性不可偽造的,這種安全性僅要求攻擊者不能對一個(gè)新消息產(chǎn)生一個(gè)有效的簽名,但不能阻止對已經(jīng)簽過的消息重新偽造一個(gè)有效的簽名。強(qiáng)不可偽造性具有更強(qiáng)的安全性,不允許這種偽造［9-10］。強(qiáng)不可偽造性能保證攻擊者無法偽造新消息和已經(jīng)簽名過的消息的合法簽名,能有效防止電子投票、電子現(xiàn)金和數(shù)字版權(quán)等的篡改。

現(xiàn)有的在標(biāo)準(zhǔn)模型下可證明安全的代理重簽名方案［2-5］都是基于Waters簽名方案［11］,但Waters簽名方案是可延展的,這就意味著這些代理重簽名方案不滿足強(qiáng)不可偽造性。然而,具有強(qiáng)不可偽造性的代理重簽名的研究才剛剛起步,公開的相關(guān)文獻(xiàn)較少。文獻(xiàn)［12］提出了2個(gè)具有強(qiáng)不可偽造性的雙向代理重簽名方案(下文簡稱Vivek1方案和Vivek2方案),但這2個(gè)方案具有大量的系統(tǒng)公開參數(shù),對存儲空間的要求比較高。文獻(xiàn)［10］提出了一個(gè)標(biāo)準(zhǔn)模型下高效的強(qiáng)不可偽造短簽名方案,具有較短的公私鑰長度和簽名長度。

本文在文獻(xiàn)［10］方案的基礎(chǔ)上,利用基于密鑰的目標(biāo)抗碰撞(Target Collision Resistant,TCR)雜湊函數(shù)［13］,提出一個(gè)具有強(qiáng)不可偽造性的雙向代理重簽名方案。

2 預(yù)備知識

2.1 計(jì)算性Diffie-Hellman問題

設(shè)G1是階為素?cái)?shù)p的循環(huán)群,g是G1的生成元,計(jì)算性 Diffie-Hellman(Computational Diffie-Hellman,CDH)問題為:已知(g,ga,gb)∈G31,計(jì)算gab∈G1,其中,a,b∈RZp。

定義1 CDH假設(shè)

若沒有一個(gè)概率多項(xiàng)式時(shí)間算法能在時(shí)間t內(nèi)以至少ε的概率解決群G1上的CDH問題,則稱群G1上的(t,ε)-CDH假設(shè)成立［2］。

2.2 TCR雜湊函數(shù)

假設(shè)K為TCR雜湊函數(shù)的密鑰空間,M1和M2分別為輸入和輸出消息空間,一個(gè)TCR雜湊函數(shù)Hk:K×M1→M2實(shí)際上是一個(gè)通用的基于密鑰單向雜湊函數(shù),其中,k∈K。通過下面的游戲來定義一個(gè)TCR雜湊函數(shù)的安全性:

(1)攻擊者輸出消息m1∈M1;

(2)挑戰(zhàn)者隨機(jī)選取k∈K,并將k發(fā)送給攻擊者;

(3)攻擊者輸出消息m2∈M1,若Hk(m1)= Hk(m2)且m1≠m2,則攻擊者贏得游戲。

定義2 如果攻擊者在多項(xiàng)式時(shí)間t內(nèi)贏得上述游戲的概率ε是可忽略的,則稱TCR雜湊函數(shù)Hk是(t,ε)安全的［10］。

3 本文簽名方案

3.1 方案描述

利用TCR雜湊函數(shù),構(gòu)造一個(gè)雙向代理重簽名方案,具體描述如下:

(1)Setup:輸入一個(gè)安全參數(shù)τ,選擇2個(gè)階為大素?cái)?shù)p的循環(huán)群G1和G2,g是G1的一個(gè)生成元,并選擇一個(gè)雙線性映射e:G1×G1→G2;在G1中隨機(jī)選取4個(gè)元素g2,v,m0和m1;隨機(jī)選取一個(gè)TCR雜湊函數(shù)的密鑰k和TCR雜湊函數(shù)Hk:{0,1}*→Zp,其中,k∈K,K為TCR雜湊函數(shù)的密鑰空間;最后輸出系統(tǒng)公開參數(shù)cp=(G1,G2,p,e,g,g2,v,m0, m1,k,Hk)。

(3)ReKey:輸入一個(gè)受托者的私鑰skA=α和一個(gè)委托者的私鑰skB=β,生成代理者的重簽名密鑰rkA→B的過程如下:

1)代理者選取一個(gè)隨機(jī)數(shù)r0∈,將r0發(fā)送給受托者;

2)受托者收到r0后,計(jì)算r1=r0α(mod p),將r1發(fā)送給委托者;

3)委托者收到r1后,計(jì)算r2=β/r1(mod p),將r2發(fā)送給代理者;

4)代理者收到r2后,計(jì)算自己的重簽名密鑰rkA→B=r0r2=r0(β/r1)=r0(β/(r0α))=β/α(modp)。

(4)Sign:輸入一個(gè)私鑰sk=α和一個(gè)消息M,生成消息M的簽名過程如下:

2)檢查 h最右邊比特值 u∈{0,1},計(jì)算σ2=(muvh)s;

3)輸出消息 M 的簽名 σ =(σ1,σ2)= (gs,(muvh)s)。

(5)ReSign:輸入一個(gè)重簽名密鑰rkA→B,一個(gè)消息M,一個(gè)公鑰pkA和一個(gè)簽名σA=(σA1,σA2,),如果Verify(pkA,M,σA)=0,輸出⊥;否則,選取一個(gè)隨機(jī)數(shù)r∈,計(jì)算σB3=gr和h2=Hk(M||σB3),檢查h2的最右邊比特值u2,然后計(jì)算σB1=(σA1)rkA→B和σB2=(σA2)rkA→B(mu2vh2)r,最后輸出對應(yīng)于公鑰 pkB的消息M的簽名σB=(σB1,σB2,σB3)。

(6)Verify:輸入一個(gè)公鑰pk,一個(gè)消息M和一個(gè)待驗(yàn)證的簽名σ,如果σ=(σ1,σ2),則簽名驗(yàn)證過程如下:

1)計(jì)算h=Hk(M||σ1),檢查h的最右邊比特值u∈{0,1};

2)驗(yàn)證e(σ2,g)=e(σ1,muvh)e(pk,g2)是否成立,如果成立,那么σ是消息M的有效簽名,輸出1;否則,輸出0。

如果σ=(σ1,σ2,σ3),則簽名驗(yàn)證過程如下:

1)計(jì)算h=Hk(M||σ1)和h2=Hk(M||σ3),檢查h和h2的最右邊比特值u,u2∈{0,1};

2)驗(yàn)證e(σ2,g)=e(σ1,muvh)e(pk,g2)e(σ3, mu2vh2)是否成立,如果成立,那么σ是消息M的有效簽名,輸出1;否則,輸出0。

3.2 正確性分析

令受托者的公私鑰對(pkA,skA)=(gα,α),委托者的公私鑰(pkB,skB)=(gβ,β),消息 M 的簽名σA=(σA1,σA2)=(gs,(muvh)s)和重簽名密鑰rkA→B=β/α,則重簽名σB=(σB1,σB2,σB3)的正確性驗(yàn)證過程如下:

因?yàn)閞kA→B=β/α=1/(α/β)=1/rkB→A,所以新方案滿足雙向性;由于每個(gè)用戶保存的私鑰僅是Zp中的一個(gè)元素,因此新方案也滿足密鑰最優(yōu)性。

對于消息M的簽名:

3.3 安全性分析

定理 若TCR雜湊函數(shù)Hk是(t,ε/2)安全的或G1上的(t,ε/8)-CDH假設(shè)成立,則本文提出的代理重簽名方案是(t,ε)強(qiáng)不可偽造的。

證明:如果存在一個(gè)攻擊者A在多項(xiàng)式時(shí)間t內(nèi)最多查詢了qE次(未)攻陷用戶密鑰產(chǎn)生預(yù)言機(jī)、qs次簽名預(yù)言機(jī)、qRK次重簽名密鑰生成預(yù)言機(jī)和qRS次重簽名預(yù)言機(jī),能以一個(gè)不可忽略的概率ε攻破新方案的強(qiáng)不可偽造性,下面證明將存在一個(gè)攻擊者F能解決G1上的CDH問題或找到Hk的一個(gè)碰撞。

類型Ⅰ:對任意i∈{1,2,…,q},總有h*≠hi;

類型Ⅱ:存在某個(gè)i∈{1,2,…,q},滿足h*=hi。

如果攻擊者A能成功偽造一個(gè)合法簽名,則A的輸出必然是類型Ⅰ或類型Ⅱ。下面證明類型Ⅰ的偽造可解決一個(gè)CDH問題實(shí)例,類型Ⅱ的偽造可找到Hk的一對碰撞。

類型Ⅰ:假設(shè)A是類型Ⅰ的攻擊者,它能攻破新方案的(t,ε)強(qiáng)不可偽造性,將存在一個(gè)攻擊者F能解決G1上的CDH問題。給定一個(gè)CDH問題實(shí)例(g,gα,gβ)∈,F的任務(wù)是計(jì)算gαβ∈G1。攻擊者F執(zhí)行如下的模擬操作:

(1)建立:設(shè)置g1=gα,g2=gβ,隨機(jī)選取4個(gè)元素x,y,z,t∈,計(jì)算m0=gx,m1=gy和v=gz,運(yùn)行Setup算法得到系統(tǒng)其他參數(shù),并將(g,g1,g2,v, m0,m1,k)發(fā)送給攻擊者A。

(2)查詢:F建立如下的預(yù)言機(jī)。

1)OUKeyGen:F選取一個(gè)隨機(jī)數(shù)xi∈,輸出公鑰pki=(g1)xi=gαxi。

2)OCKeyGen:F選取一個(gè)隨機(jī)數(shù)xi∈,輸出公私鑰對(pki,ski)=(gxi,xi)。

3)OSign:攻擊者A輸入一個(gè)公鑰pki和一個(gè)消息Mj,F回復(fù)如下:

如果pki已被攻陷,F選取一個(gè)隨機(jī)數(shù)sj∈Zp,計(jì)算hj=Hk(Mj||gsj),然后檢查hj的最右邊比特值uj∈{0, 1},最后返回簽名σj=(σj1,σj2)=(gsj,g2xj(mujvhj)sj);

當(dāng)pki未被攻陷時(shí),pki=gαxi隱含了對應(yīng)的密鑰為αxi,簽名σj=(σj1,σj2)的正確性驗(yàn)證過程如下:

于是有:

4)OReKey:攻擊者A輸入2個(gè)公鑰(pki,pkj),如果pki和pkj均已被攻陷或均未被攻陷,攻擊者F返回一個(gè)重簽名密鑰rki→j=xj/xi(modp);否則,輸出⊥。

5)OReSign:攻擊者A輸入2個(gè)公鑰(pki,pkj),一個(gè)消息Mi和一個(gè)簽名σi,如果Verify(pki,Mx,σi)= 0,攻擊者F輸出⊥;否則,F進(jìn)行如下操作:

如果pki和pkj均已被攻陷或均未被攻陷,F運(yùn)行重簽名生成算法和查詢重簽名密鑰生成預(yù)言機(jī),然后返回一個(gè)簽名σi=ReSign(OReKey(pki,pkj),pki,Mi,σi);

如果pki和pkj中有一個(gè)已被攻陷,F首先查詢簽名預(yù)言機(jī),然后返回一個(gè)簽名σj=OSign(pkj,Mi)。

如果h*和的最右邊比特值是1,那么攻擊者F退出,模擬失敗;否則,此時(shí)m0=gx,該偽造必須滿足:

為解決 CDH實(shí)例(g,gα,gβ)∈G31,攻擊者F計(jì)算:

因此,如果攻擊者A能攻破新方案的強(qiáng)不可造性,那么攻擊者F能解決G1上的CDH問題。由于A成功偽造簽名的概率是ε,模擬不中斷的概率是1/4,選擇類型Ⅰ的概率都是1/2,所以F成功計(jì)算出CDH困難問題實(shí)例的概率是ε/8。

(1)建立:設(shè)置k=k*,運(yùn)行Setup算法得到系統(tǒng)其他參數(shù),將(G1,G2,p,e,g,pk*,g2,v,m0,m1,k,Hk)發(fā)送給攻擊者A,并秘密保存私鑰sk*。

(2)詢問:攻擊者A可以自適應(yīng)性地向F詢問用戶的公鑰/私鑰、重簽名密鑰、消息的簽名和重簽名,F通過運(yùn)行相應(yīng)的算法(KeyGen,ReKey,Sign和ReSign)響應(yīng)攻擊者A所發(fā)起的各種詢問請求,并將詢問結(jié)果返回給A。

3.4 有效性分析

文獻(xiàn)［2］提出的Smd方案、文獻(xiàn)［3］提出的Smd改進(jìn)方案和文獻(xiàn)［12］提出的2個(gè)代理重簽名方案都是基于Waters簽名方案［11］,需要將任意長度的待簽名消息映射為一個(gè)固定長度n的比特串。下面將已有的幾種雙向代理重簽名方案和本文方案進(jìn)行效率和安全屬性比較,如表1所示。假設(shè)所有方案選擇相同長度的大素?cái)?shù)p和循環(huán)群(G1,G2),其中,|·|表示元素長度;E表示指數(shù)運(yùn)算;P表示雙線性對運(yùn)算;n表示W(wǎng)aters簽名方案中的簽名消息長度;Y表示具有此種屬性;N表示不具有此種屬性。

表1 效率和安全屬性比較

從表1可以看出,本文所提出的雙向代理重簽名方案的重簽名比Smd方案［2］、Smd改進(jìn)方案［3］的重簽名多一個(gè)元素,但這2個(gè)方案不滿足強(qiáng)不可偽造性,并且具有較長的系統(tǒng)公開參數(shù)長度。文獻(xiàn)［12］提出的2個(gè)方案(Vivek1方案、Vivek2方案)滿足強(qiáng)不可偽造性,但與這2個(gè)方案相比,本文新方案具有更短的系統(tǒng)公開參數(shù)長度和重簽名長度,并且重簽名驗(yàn)證的計(jì)算量更小,同時(shí)滿足密鑰最優(yōu)性。

4 結(jié)束語

本文提出一個(gè)雙向代理重簽名方案,并證明了該方案在適應(yīng)性選擇消息攻擊下是強(qiáng)不可偽造的。與已有的強(qiáng)不可偽造雙向代理重簽名方案相比,該方案在系統(tǒng)公開參數(shù)長度、簽名長度、安全屬性等方面具有較大的性能優(yōu)勢。下一步工作將設(shè)計(jì)無雙線性對的強(qiáng)不可偽造代理重簽名方案。

［1］ Ateniese G,Hohenberger S.Proxy Re-signatures:New Definitions,Algorithms, and Applications［C］// Proceedings of ACM CCS'05.Alexandria,USA:ACM Press,2005:310-319.

［2］ Shao Jun,Cao Zhenfu,Wang Licheng,et al.Proxy ResignatureSchemesWithoutRandom Oracles［C］// Proceedings of INDO-CRYPT'07.Chennai,India:［s.n.］, 2007:197-209.

［3］ Kiate K,Ikkwon Y,Secogan L.Remark on Shao et al's Bidirectional Proxy Re-signature Scheme in Indocrypt'07［J］.International Journal of Network Security,2009,8(3): 308-311.

［4］ Benoit L,Damien V.Multi-use Unidirectional Proxy Resignatures［C］//Proceedings of the 15th ACM Conference on Computer and Communications Security.Alexandria, USA:ACM Press,2008:511-520.

［5］ 鄧宇喬,杜明輝,尤再來,等.一種基于標(biāo)準(zhǔn)模型的盲代理重簽名方案［J］.電子與信息學(xué)報(bào),2010,32(5): 1119-1223.

［6］ 孫昌毅,李益發(fā),斯雪明.基于多變量公鑰密碼體制的代理重簽名方案［J］.計(jì)算機(jī)工程,2012,38(17): 116-118.

［7］ 楊小東,王彩芬.高效的在線/離線代理重簽名方案［J］.電子與信息學(xué)報(bào),2011,33(12):2916-2921.

［8］ 楊小東,王彩芬.前向安全的單向門限代理重簽名［J］.計(jì)算機(jī)應(yīng)用,2011,31(3):801-804.

［9］ Buchmann J,Dahmen E,Ereth S,et al.On the Security of the Winternitz One-time Signature Scheme［J］.International Journal of Applied Cryptography,2013,3(1):84-96.

［10］ 劉振華,胡予濮,張襄松.標(biāo)準(zhǔn)模型下高效的強(qiáng)不可偽造短簽名方案［J］.江蘇大學(xué)學(xué)報(bào):自然科學(xué)版,2013, 34(3):309-313.

［11］ Waters B.Efficient Identity-based Encryption Without Random Oracles［C］//Proceedings of EuroCrypt'05.Aarhus,Danmark:［s.n.］,2005:114-127.

［12］ Vivek S S,Selvi S S D,Rangan C P,et al.Strongly Unforgeable Proxy Re-signature Schemes in the Standard Model［EB/OL］.［2013-12-25］.http://eprint.iacr.org/ 2012/080.pdf.

［13］ Matsuda T,Attrapadung N,Hanaoka G,et al.A CDH-based Strongly Unforgeable Signature Without Collision Resistant Hash Function［C］//Proceedings of Prov Sec'07.Wollongong,Australia:［s.n.］,2007:68-84.

編輯 金胡考

A Strongly Unforgeable Proxy Re-signature Scheme

YANG Xiaodong,LI Chunmei,ZHOU Si'an,WANG Caifen
(College of Computer Science&Engineering,Northwest Normal University,Lanzhou 730070,China)

Most existing proxy re-signature schemes are existential unforgeability,where an adversary will be able to forge a signature on a new message rather than on a message that has already been signed.However,strong unforgeability can protect the existing message-signature pairs from being forged.By using TCR hash function,a bidirectional proxy resignature scheme is proposed.Based on collision-resistant Target Collision Resistant(TCR) hash function and computational Diffie-Hellman assumption,the proposed scheme is proved to be strongly unforgeable under adaptive chosen message attacks.The results show that the proposed scheme in computational efficiency is superior to the available proxy re-signature schemes with strong unforgeability.Compared with these schemes,the new scheme has short system parameters,short signature,short re-signature and more security properties.

bidirectional proxy re-signature;strong unforgeability;provable security;Computational Diffie-Hellman (CDH)assumption;standard model

1000-3428(2014)11-0130-05

A

TP309.7

10.3969/j.issn.1000-3428.2014.11.026

國家自然科學(xué)基金資助項(xiàng)目(61262057,61163038);甘肅省科技計(jì)劃基金資助項(xiàng)目(145RJDA325);國家檔案局科技計(jì)劃基金資助項(xiàng)目(2014-X-33);甘肅省自然科學(xué)基金資助項(xiàng)目(1308RJYA039);蘭州市科技計(jì)劃基金資助項(xiàng)目(2013-4-22)。

楊小東(1981-),男,副教授、博士,主研方向:現(xiàn)代密碼學(xué),云計(jì)算安全;李春梅、周思安,碩士研究生;王彩芬,教授、博士生導(dǎo)師。

2013-12-16

2014-02-20E-mail:y200888@163.com

中文引用格式:楊小東,李春梅,周思安,等.一種強(qiáng)不可偽造代理重簽名方案［J］.計(jì)算機(jī)工程,2014,40(11):130-134.

英文引用格式:Yang Xiaodong,Li Chunmei,Zhou Si'an,et al.A Strongly Unforgeable Proxy Re-signature Scheme［J］.Computer Engineering,2014,40(11):130-134.