一種強不可偽造代理重簽名方案

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

一種強不可偽造代理重簽名方案

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

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

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

雙向代理重簽名;強不可偽造性;可證明安全;計算性Diffie-Hellman假設;標準模型

1 概述

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

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

本文在文獻［10］方案的基礎上,利用基于密鑰的目標抗碰撞(Target Collision Resistant,TCR)雜湊函數［13］,提出一個具有強不可偽造性的雙向代理重簽名方案。

2 預備知識

2.1 計算性Diffie-Hellman問題

設G1是階為素數p的循環群,g是G1的生成元,計算性 Diffie-Hellman(Computational Diffie-Hellman,CDH)問題為:已知(g,ga,gb)∈G31,計算gab∈G1,其中,a,b∈RZp。

定義1 CDH假設

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

2.2 TCR雜湊函數

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

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

(2)挑戰者隨機選取k∈K,并將k發送給攻擊者;

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

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

3 本文簽名方案

3.1 方案描述

利用TCR雜湊函數,構造一個雙向代理重簽名方案,具體描述如下:

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

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

1)代理者選取一個隨機數r0∈,將r0發送給受托者;

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

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

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

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

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

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

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

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

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

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

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

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

2)驗證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)的正確性驗證過程如下:

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

對于消息M的簽名:

3.3 安全性分析

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

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

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

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

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

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

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

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

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

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

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

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

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

于是有:

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

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

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

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

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

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

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

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

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

3.4 有效性分析

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

表1 效率和安全屬性比較

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

4 結束語

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

［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］ 鄧宇喬,杜明輝,尤再來,等.一種基于標準模型的盲代理重簽名方案［J］.電子與信息學報,2010,32(5): 1119-1223.

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

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

［8］ 楊小東,王彩芬.前向安全的單向門限代理重簽名［J］.計算機應用,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］ 劉振華,胡予濮,張襄松.標準模型下高效的強不可偽造短簽名方案［J］.江蘇大學學報:自然科學版,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

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

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

2013-12-16

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

中文引用格式:楊小東,李春梅,周思安,等.一種強不可偽造代理重簽名方案［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.