高效的在線/離線代理重簽名方案

楊小東 王彩芬

(西北師范大學數學與信息科學學院 蘭州 730070)

1 引言

數字簽名在保證數據的機密性、完整性和不可否認性等方面起著極為重要的作用，被廣泛用于設計電子支付、電子投標、電子拍賣、電子彩票和電子投票等應用協議，是安全電子商務和安全電子政務的關鍵技術之一。根據實際應用背景的需要，人們提出了諸多特殊的數字簽名方案，代理簽名就是其中的一種。代理簽名將簽名者的某些權利委托給可靠的代理者，讓代理者代表簽名者行使相應的簽名權利。但在代理簽名中，委托者必須高度信任代理者。

為了分散代理者的簽名權利，文獻[1]提出了代理重簽名的概念。在代理重簽名中，一個擁有重簽名密鑰的半可信代理者(semi-trusted proxy)將受托者(delegatee)的簽名(也稱原始簽名)轉換為委托者(delegator)對同一消息的簽名(也稱重簽名)，但這個代理者不能單獨生成受托者或委托者的任何原始簽名。所謂半可信，指的是僅僅相信這個代理者一定會按方案進行簽名的轉換。代理重簽名在簡化證書管理、管理群簽名、提供遍歷的路徑證明、構造審查系統和數字版權管理系統等方面有廣泛的應用前景[2]。

在線/離線簽名[3]是把數字簽名分成兩個階段的簽名方式，它是為了提高簽名方案的效率而提出來的一種解決方案。第1階段是離線階段，在未知簽名消息的情況下進行簽名預計算。由于此階段有足夠的時間，因而離線階段簽名算法并不影響消息的簽名速度；第2階段是在線階段，這是在消息出現后開始的，由于離線階段已做了預計算，所以此階段簽名速度非常快。在線/離線簽名在現實中有廣泛的應用，如智能卡等。

在已有的代理重簽名方案中[1,2,4-7]，重簽名生成算法中有冪指數運算，嚴重影響了代理重簽名方案的簽名效率。為了改善代理重簽名的性能，本文基于變色龍哈希函數提出了一個在線/離線代理重簽名方案。該方案將代理重簽名的特性與在線/離線簽名的特性進行了有效融合，能將已有的任意一個代理重簽名方案轉換為一個高效的在線/離線代理重簽名方案。在線/離線代理重簽名大大提高了代理重簽名的實時性和安全性，可應用在重簽名時間受限或重簽名設備計算能力有限的場合，如無線傳感器網絡、無線路由器協議、PDA等。如果是時間受限，在空閑時間進行離線階段的運算，將計算結果保存，預備用于在線階段的重簽名運算；如果是設備的計算能力有限，讓具有較強計算能力的設備進行離線階段的計算，將計算結果存儲在計算能力有限的設備上，用于在線階段進行重簽名。代理重簽名是近年來密碼學研究的一個熱點，主要集中于研究代理重簽名[1,2,4-7]、盲代理重簽名[8]、無證書代理重簽名[9]和門限代理重簽名[10]等，但關于在線/離線代理重簽名的公開文獻幾乎沒有。

2 預備知識

2.1 橢圓曲線離散對數假設

選擇大素數t,E(Ft)是定義在有限域Ft上的一個橢圓曲線，#E(Ft)是E(Ft)中點的數目。點P∈E(Ft),P的階為素數q，這里q|#E(Ft)。G是P生成的一個q階循環群。橢圓曲線離散對數問題(ECDLP)：給定 (P,P1)∈E(Ft)，尋找一個整數a∈Zq，使得在G中有P1=aP。

定義 1(橢圓曲線離散對數假設)如果沒有一個概率多項式時間算法在時間T內以至少ε的概率解決群G上的橢圓曲線離散對數問題，則稱群G上的(T,ε)-ECDLP假設成立。

2.2 變色龍哈希函數

變色龍哈希函數CH(?,?)是一種特殊的哈希函數[3]，擁有一個門限密鑰TK和一個公鑰HK，并且滿足以下性質：

(1)有效性：給定公鑰HK，一個消息m和一個隨機數r，存在一個多項式時間算法計算CHHK(m,r)。

(2)抗碰撞性：輸入公鑰 HK，不存在任何一個概率多項式時間算法以一個不可忽略的概率輸出(m1,r1)和 (m2,r2)，使得m1≠m2且 C HHK(m1,r1)=CHHK(m2,r2)。

(3)門限碰撞：給定門限密鑰 TK，公鑰 HK，兩個不同的消息 (m1,m2)和一個隨機數r1，一定存在一個概率多項式時間算法輸出一個值r2，使得CHHK(m1,r1)=CHHK(m2,r2)；如果r1服從均勻分布，則r2服從的分布與均勻分布在計算上是不可區分的。

2.3 基于橢圓曲線離散對數假設的變色龍哈希函數

基于橢圓曲線離散對數假設，構造一個變色龍哈希函數，利用它構造在線/離線代理重簽名方案。選擇大素數t,E(Ft)是定義在有限域Ft上的一個橢圓曲線，#E(Ft)是E(Ft)中點的數目。點P∈E(Ft),P的階為素數q，這里q|#E(Ft)。G是P生成的一個循環群。定義一個安全的哈希函數f：Zq×G→Zq。具體描述如下：

(1)門限密鑰生成算法：選擇兩個隨機數k,x∈Zq，計算Y=xP,K=kP，則門限密鑰TK=(k,x)，公鑰HK=(K,Y)。

(2)哈希函數生成算法：對于公鑰HK=(K,Y)，構造變色龍哈希函數CHHK：Zq×Zq→G，定義為CH(m,r)=f(m,K)P+rY。

定理1CH(m,r)=f(m,K)P+rY是一個基于橢圓曲線離散對數假設的變色龍哈希函數。

證明下面證明CH(m,r)=f(m,K)P+rY滿足變色龍哈希函數的性質：

(1)有效性 給定公鑰HK=(K,Y)，一個消息m∈Zq和一個隨機數r∈Zq，在多項式時間內能計算出CH(m,r)=f(m,K)P+rY。

(2)抗碰撞性 給定公鑰HK=(K,Y)，假設存在一個概率多項式時間算法以一個不可忽略的概率輸出 (m1,r1)和 (m2,r2)，使得 C H(m1,r1)=CH(m2,r2)且m1≠m2，則在多項式時間內能計算出Y的離散對數x。即f(m1,K)P+r1xP=f(m2,K)P+r2xP。

于是有

因為橢圓曲線離散對數是個困難問題，而上述結論與橢圓曲線離散對數假設相矛盾，所以這個概率多項式時間算法不存在。即變色龍哈希函數滿足抗碰撞性。

(3)門限碰撞 給定公鑰HK=(K,Y)，門限密鑰TK=(k,x)，兩個不同的消息 (m1,m2)和一個隨機數r1，尋找r2使得 C H(m1,r1)=CH(m2,r2)。可通過下式在多項式時間內計算出r2，

如果r1在Zq中服從均勻分布，那么r2在Zq中也服從均勻分布。 證畢

3 在線/離線代理重簽名的形式化定義

定義 2 (代理重簽名)一個代理重簽名方案PRS=(KeyGen,ReKey,Sign,ReSign,Verify)由以下5個算法組成[2]：

(1)KeyGen是密鑰生成算法：輸入一個安全參數1k，輸出系統參數和用戶的公私鑰對(pk,sk)。

(2)ReKey是重簽名密鑰生成算法：輸入一個受托者的公私鑰對(pkA,skA)和一個委托者的公私鑰對(pkB,skB)，輸出一個重簽名密鑰rkA→B。代理者使用rkA→B可將受托者的簽名轉換為委托者的簽名。

(3)Sign是簽名生成算法：輸入一個消息m和一個私鑰sk，輸出一個消息m的簽名σ。可用對應的公鑰pk來驗證簽名σ的合法性。

(4)ReSign是重簽名生成算法：輸入一個重簽名密鑰rkA→B，一個消息m，一個公鑰pkA和一個簽名σA，該算法首先驗證σA的合法性，若Verify (pkA,m,σA)=1，則輸出一個對應于公鑰pkB的消息m的簽名σB；否則，輸出⊥。

(5)Verify是簽名驗證算法：輸入一個消息m，一個公鑰pk和一個簽名σ，如果σ是對應于公鑰pk的消息m的合法簽名，輸出1；否則，輸出0。

Ateniese和Hobenberger定義了代理重簽名的安全模型[2]：外部安全和內部安全。外部安全性可使用戶免受來自系統外部的攻擊者的惡意攻擊，而內部安全性主要考慮來自系統內部的攻擊，如代理者發起的攻擊或他與委托雙方中其中一方的合謀攻擊。如果沒有一個攻擊者在多項式時間內以不可忽略的優勢偽造PRS方案的合法簽名，則稱PRS方案在適應性選擇消息攻擊下是不可偽造的[2,4]。

定義 3(在線/離線代理重簽名)一個在線/離線代理重簽名方案 OPRS=(RekeyOn/Off,ReSignOn/Off,Ver)由以下3個算法組成：

(1)RekeyOn/Off是重簽名密鑰生成算法：輸入一個安全參數1k，輸出系統參數params、用戶的公私鑰對(pk,sk)和代理者的重簽名密鑰rkA→B。

(2)ReSignOn/Off是重簽名生成算法：該算法分以下兩個階段進行：

(a)離線階段：輸入私鑰和重簽名密鑰，輸出狀態信息Ki。

(b)在線階段：輸入一個消息m，一個公鑰pkA，消息m的簽名ρA，狀態信息Ki和私鑰，首先驗證ρA的合法性，若Verify (pkA,m,ρA)=1，則輸出一個對應于公鑰pkB的消息m的重簽名ρB；否則，輸出⊥。

(3)Ver是簽名驗證算法：輸入一個消息m，一個公鑰pk和一個簽名ρ，如果ρ是對應于公鑰pk的消息m的合法簽名，輸出1；否則，輸出0。

攻擊模型：采用在靜態攻陷模式下挑戰者C和攻擊者A之間的游戲來定義在線/離線代理重簽名的安全性模型。攻擊者A在游戲開始前必須確定已被攻陷的用戶，攻擊游戲分3個階段進行。首先是建立階段，挑戰者C生成系統參數 params，并將params發送給攻擊者A。其次是查詢階段，攻擊者A可以適應性地向挑戰者C進行用戶的公鑰/私鑰詢問、重簽名密鑰詢問、簽名詢問和重簽名詢問，挑戰者C通過相應的預言機(密鑰預言機、重簽名密鑰預言機、原始簽名預言機和重簽名預言機)響應攻擊者所發起的各種詢問請求，并將詢問結果返回給攻擊者A。這個階段的安全性定義與一般的代理重簽名的安全性定義[2,4]基本相同。最后是偽造階段，攻擊者A輸出一個偽造，即一個消息/簽名對。

如果攻擊者A能生成一個新消息m的合法簽名，那么我們就說攻擊者A偽造成功。攻擊者A在上面游戲中的優勢可以定義AdvA=Pr[A succeeds]，這個概率完全取決于挑戰者A和攻擊者C之間的拋幣概率。

定義 4(不可偽造性)如果沒有一個攻擊者在多項式時間內以不可忽略的優勢贏得上述游戲，那么稱在線/離線代理重簽名方案 OPRS在適應性選擇消息攻擊下能抵抗存在性偽造。

基于變色龍函數構造的在線/離線代理重簽名方案，其安全性可歸約為所關聯的代理重簽名的安全性或變色龍函數的安全性。如果攻擊者輸出一個在線/離線代理重簽名的偽造，則可利用這個偽造構造一個所關聯的代理重簽名的偽造或找到變色龍函數的一個碰撞。因此，只要所基于的代理重簽名方案是安全的且變色龍哈希函數具有抗碰撞性，則相應的在線/離線代理重簽名方案也是安全的。

4 在線/離線代理重簽名方案

基于變色龍哈希函數CH(m,r)=f(m,K)P+rY，本文提出了一個在線/離線代理重簽名方案。該方案可將已有的任意一個代理重簽名方案[1,2,5-8]轉換為一個相應的在線/離線代理重簽名方案，用PRS表示這些方案中的任意一個代理重簽名方案。選擇大素數t,E(Ft)是定義在有限域Ft上的一個橢圓曲線，#E(Ft)是E(Ft)中點的數目。P∈E(Ft),P的階為素數q,q|#E(Ft)。G是P生成的一個循環群。簽名的消息mi∈Zq，可通過哈希函數g：{0,1}*→Zq延伸簽名消息空間。選擇安全的哈希函數f：Zq×G→Zq。

4.1 方案描述

假定PRS=(KeyGen,ReKey,Sign,ReSign,Verify)是一個安全的代理重簽名方案[2,5-8]，則相應的在線/離線代理重簽名方案 OPRS=(RekeyOn/Off,ReSignOn/Off,Ver)由以下3個算法組成：

(1)RekeyOn/Off：主要生成系統參數、用戶的公私鑰對和重簽名密鑰，具體描述如下：

(a)輸入安全參數1k，運行PRS的KeyGen算法生成系統參數params和用戶的公私鑰對(pk,sk)。

(b)輸入受托者的公私鑰對(pkA,skA)和委托者的公私鑰對(pkB,skB)，運行PRS的ReKey算法生成重簽名密鑰rkA→B。

(c)選擇一個隨機數x∈Zq，計算Y=xP,X=x-1，則TK=x,HK=Y。

(d)選擇一個隨機數k*∈Zq，計算h=k*Y。

(e)運行PRS的Sign算法生成受托者對h的原始簽名σA。即代理者請求受托者生成h的原始簽名σA，但代理者不知道受托者的私鑰skA的任何信息。

(f)運行PRS的ReSign算法生成委托者對h的重簽名σB。即代理者使用rkA→B將受托者對h的簽名σA轉換為委托者對h的重簽名σB。

公開參數(params,pkA,pkB,E(Ft),G,t,q,f,g,CH(?,?),σA,σB,Y,h)，代理者的重簽名密鑰是(rkA→B,x,X,k*)。

(2)ReSignOn/Off：給定一個重簽名密鑰(rk,x,X,k*)，代理者進行如下操作：A→B

(a)離線階段：

(i)選擇一個隨機數ki∈Zq，計算Ki=ki P；

(ii)保存狀態信息Ki。

(b)在線階段：輸入一個待簽名的消息mi∈Zq，一個公鑰pkA和消息mi的簽名ρAi，代理者進行如下操作：

(i)提取狀態信息Ki；

(ii)計算ri=k*-f(mi,Ki)X(modq)；

(iii)委托者對消息mi的重簽名ρB=(ri,Ki,σB,ρAi)；因為σB作為公開參數發布，所以mi的重簽名實際上是ρB=(ri,Ki,ρAi)。

(3)Ver：輸入一個消息mi，委托者的公鑰pkB和一個簽名ρB=(ri,Ki,ρAi)，為了驗證ρB是對應于公鑰pkB的消息mi的有效簽名，進行如下操作：

(a)計算CH(mi,ri)=f(mi,Ki)P+riY；

(b)運行PRS的Verify算法，如果Verify (pkA,mi,ρAi)=1 且 Verify(pkB,CH(mi,ri),σB)=1，那么ρB是委托者對消息mi的合法重簽名，輸出1；否則，輸出0。

4.2 正確性分析

因為σB是PRS中委托者對h的有效重簽名，所以σB也是 PRS中委托者對CH(mi,ri)的合法重簽名。

4.3 安全性分析

定理2 在隨機預言模型下，如果循環群G上的(T,ε)-ECDLP假設成立，代理重簽名方案PRS=(KeyGen,ReKey,Sign,ReSign,Verify)在適應性選擇消息攻擊下是不可偽造的，那么本文所提的在線/離線代理重簽名方案 OPRS=(RekeyOn/Off,ReSignOn/Off,Ver)在適應性選擇消息攻擊下也是不可偽造的。

證明假設A是在線/離線代理重簽名方案OPRS的一個攻擊者，OPRS的挑戰者將公開參數(params,pkA,pkB,E(Ft),G,t,q,f,g,C H(?,?))發送給A。qS表示A詢問簽名預言機(包括原始簽名預言機和重簽名預言機)的最大次數，qf表示A詢問哈希函數預言機的最大次數。假設(mi,Ki)是A第i次詢問哈希函數預言機的輸入，預言機返回相應的哈希函數值ei;mj是A第j次詢問簽名預言機的輸入，預言機返回相應的簽名攻擊者A在適應性選擇消息攻擊下在時間T內以不可忽略的概率ε成功偽造OPRS的一個簽名(m,r,K,ρA)，即

給定系統參數(params,pkA,pkB,E(Ft),G,t,q,f,g,CH(?,?))，定義一個概率多項式時間算法B，利用攻擊者A的偽造解決一個橢圓曲線離散對數問題的實例。假設B收到的橢圓曲線離散對數問題實例是(P,aP)∈G,B的目標是確定aP的離散對數a∈Zq。B進行如下的操作：

(1)選擇一個隨機數b∈Zq，令Y=aP，計算h=bY=abP；運行PRS的Sign算法生成h的原始簽名σA；運行PRS的ReSign算法生成h的重簽名σB；公開(σA,σB,Y,h)。

(2)維持一個列表，記為f-list，初始值為空。對于A的第i次哈希函數值詢問(mi,Ki),B首先檢查列表f-list中是否存在(mi,Ki)，如果存在，返回ei；否則，從Zq中隨機選取ei，將(mi,Ki,ei)添加到f-list中并返回ei。

(3)對于A的第j(1 ≤j≤qS)次簽名詢問mj,B首先檢查列表f-list中是否存在若存在，則計算否則，從Z中隨機q選取)，計算加到f-list中。然后詢問簽名預言機獲得受托者對消息mj的原始簽名。最后B返回消息mj的簽名

挑戰者B返回給攻擊者A關于mi的簽名與攻擊者A詢問OPRS的簽名預言機獲得的簽名，在計算上是不可區分的。最后，攻擊者A以大于等于ε的概率輸出 OPRS的一個偽造(m,r,K,ρA)，這里h=f(m,K)P+rY,m≠mi,i=1,…,qS。 根 據Forking引理[9]，假設對于不同的哈希函數值f(m,K)和f'(m,K)，攻擊者A輸出同一消息m的兩個合法的 OPRS簽名(m,r,K,ρA)和(m,r',K,ρA)，其中h=f(m,K)P+rY,h=f'(m,K)P+r'Y，存在下面的等式：

于是，攻擊者B以大于等于ε的概率解決了橢圓曲線離散對數問題的一個實例(P,aP)∈G。如果循環群G上的(T,ε)-ECDLP假設成立，那么本文所提的在線/離線代理重簽名方案 OPRS=(RekeyOn/Off,ReSignOn/Off,Ver)在適應性選擇消息攻擊下是不可偽造的。 證畢

4.4 有效性分析

在本文所提的在線/離線代理重簽名方案中，重簽名密鑰生成算法的運算主要包括兩次橢圓曲線點乘計算，一次代理重簽名方案中的密鑰生成算法的執行，一次重簽名密鑰生成算法的執行，一次簽名算法的執行和一次重簽名算法的執行。由于σB和h是公開參數，σB是h的合法重簽名，于是只需驗證CH(mi,ri)=f(mi,Ki)P+riY=h，所以簽名驗證算法Ver的運算實際上是一次變色龍哈希函數值的計算和兩次代理重簽名方案中的簽名驗證算法 Verify的執行。離線階段重簽名算法是一次橢圓曲線點乘運算。在線階段的重簽名算法是尋找變色龍哈希函數的一次碰撞，而尋找這樣的一次碰撞僅需要一次模乘法算法和一次模減法運算。由于消息mi的重簽名ρB=(ri,Ki,ρAi)，所以本方案與大部分代理重簽名方案[6,7,10]的重簽名長度基本相同。

Ateniese等人[2]指出代理重簽名方案BBS是不安全的。在BBS方案中，任何人都能通過原始簽名和重簽名計算出重簽名密鑰并且成為惡意代理者；進一步，委托者(或受托者)可以從重簽名密鑰計算出受托者(或委托者)的私鑰，所以本方案不與 BBS方案進行簽名效率的比較。一旦簽名消息到來時，在線階段生成實際消息的重簽名，因此在線/離線代理重簽名方案的重簽名效率只考慮在線階段。將已有的代理重簽名方案和本方案的重簽名算法進行簽名效率比較，其結果見表1。

表1 重簽名算法的性能比較

從表1中可以看出，在本文所提的在線/離線代理重簽名方案中，在線重簽名算法僅需要1次模減法運算和1次模乘法運算；當簽名消息到來時，能在很短的時間生成消息的重簽名。而模減法運算和模乘法運算相對于模冪運算和配對運算而言，其計算量是可以忽略不計的。所以，本文所提的在線/離線代理重簽名方案大大改善了代理重簽名方案的性能，更適用于網絡安全應用。

5 結束語

結合門限代理重簽名與變色龍哈希函數，本文提出了一個在線/離線代理重簽名方案，該方案能將任意一個安全的代理重簽名方案轉換為一個相應的在線/離線代理重簽名方案。在隨機預言模型下證明了該方案在適應性選擇消息攻擊下是不可偽造的，并與已有的代理重簽名方案進行了性能比較，其結果表明本方案重簽名效率更高，僅需要1個模減法運算和1個模乘法運算就能生成消息的重簽名，具有一定的實用性。將來的工作是設計在標準模型下可證安全的在線/離線代理重簽名方案。

[1]Blaze M,Bleumer G,and Strauss M.Divertible protocols and atomic proxy cryptography[C].Proceedings of EUROCRYPT’98,Helsinki,Finland,May 31-June 4,1998：127-144.

[2]Ateniese G and Hohenberger S.Proxy re-signatures：new definitions,algorithms,and applications[C].Proceedings of the 12th ACM CCS,Alexandria,USA,Nov.7-11,2005：310-319.

[3]Chen X,Zhang F,Tian H,et al..Efficient generic on-line/off-line signatures without key exposure[C].Proceedings of ACNS 2007,Zhuhai,China,June 5-8,2007：18-30.

[4]Shao J,Feng M,Zhu B,et al..The security model of unidirectional proxy re-signature with private re-signature key[C].Proceedings of the 15th Australasian Conference on Information Security and Privacy,Sydney,Australia,July 5-7,2010：216-232.

[5]Shao J,Cao Z,Wang L,et al..Proxy re-signature schemes without random oracles[C].Proceedings of INDO-CRYPT 2007,Chennai,India,Dec.9-13,2007：197-209.

[6]Sherman C and Raphael P.Proxy re-signatures in the standard model[C].Proceedings of the 11th International Conference on Information Security,Taibei,China,Sept.15-18,2008：260-276.

[7]Benoit L and Damien V.Multi-use unidirectional proxy re-signatures[C].Proceedings of the 15th ACM Conference on Computer and Communications Security,Alexandria,USA,Oct.27-31,2008：511-520.

[8]Kiate K,Ikkwon Y,and Secogan L.Remark on shao et al'.s bidirectional proxy re-signature scheme in indocrypt'07[J].International Journal of Network Security,2009,9(1)：8-11.

[9]David P and Jacques S.Security arguments for digital signatures and blind signatures[J].Journal of Cryptology,2000,13(3)：361-369.

[10]Deng Y,Du M,and You Z,et al..A blind proxy re-signatures scheme based on standard model[J].Journal of Electronics＆Information Technology,2010,32(5)：1119-1223.