馬小龍，谷利澤，崔巍，楊義先，胡正名

（1.北京郵電大學(xué) 網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室信息安全中心，北京100876；2. 北京郵電大學(xué) 網(wǎng)絡(luò)與信息攻防技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室， 北京100876；3. 北京郵電大學(xué) 災(zāi)備技術(shù)國(guó)家工程實(shí)驗(yàn)室，北京100876；4. 科學(xué)技術(shù)部 信息中心，北京 100862）

1 引言

傳遞簽名的概念最早是由Rivest在2000年提出的，2002年，Micali和Rivest在文獻(xiàn)[1]中正式提出了傳遞簽名的概念, 主要用于對(duì)具有傳遞性的二元關(guān)系進(jìn)行高效簽名。Micali-Revist 傳遞簽名原語(yǔ)是一個(gè)原型系統(tǒng)，考慮了簽名值被傳遞的問(wèn)題，并且抓住了傳遞簽名的最基本語(yǔ)義。簽名的傳遞代表的是二元關(guān)系的傳遞，因而傳遞簽名在與傳遞信息認(rèn)證有關(guān)的多個(gè)領(lǐng)域都有重要應(yīng)用。

傳遞簽名提出后，許多研究人員對(duì)其進(jìn)行了深入的研究，經(jīng)過(guò)Micali、Rivest、Bellare等密碼學(xué)家的努力，現(xiàn)在人們已經(jīng)知道了如何基于大整數(shù)分解難題（IFP，integer factoring problem）[2,3]、離散對(duì)數(shù)難題（DLP，discrete logarithm problem）以及與雙線性配對(duì)（bilinear pairings）有關(guān)的密碼學(xué)難題假設(shè)[4]來(lái)實(shí)現(xiàn)傳遞簽名。Gregory在他的論文中提出了一個(gè)基于RSA的新方案并詳細(xì)闡述了構(gòu)成傳遞簽名的各個(gè)要素。在此基礎(chǔ)上，Shahandashti于2005年提出了基于雙線性配對(duì)的傳遞簽名并給出了方案的安全性證明，同年黃振杰[5]和Kuwakado[6～9]等人在現(xiàn)有的方案的基礎(chǔ)上同時(shí)提出了有向傳遞簽名，此后王勵(lì)成[10]在辮子群下實(shí)現(xiàn)了一個(gè)新的傳遞簽名方案。現(xiàn)有的傳遞簽名方案主要基于數(shù)字證書，并沒(méi)有提出有效的基于身份的數(shù)字簽名方案，本文使用雙線性配對(duì)并結(jié)合傳遞簽名的特點(diǎn)設(shè)計(jì)了第一個(gè)基于身份的傳遞簽名，并給出了基于標(biāo)準(zhǔn)模型下的證明。

第2節(jié)簡(jiǎn)要描述所需的背景知識(shí)，在第3節(jié)介紹傳遞簽名方案，第4節(jié)給出簽名方案的證明，最后是結(jié)束語(yǔ)。

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

本文需要的基礎(chǔ)知識(shí)主要包括：圖的傳遞閉包，雙線性配對(duì)的基礎(chǔ)知識(shí)和復(fù)雜性假設(shè)。

2.1 圖的傳遞閉包

定義1 圖G=(V, E)的傳遞閉包G*=(V*,E*)滿足以下條件：V*=V且邊(i, j)∈E*當(dāng)且僅當(dāng)中有一條從i至j的通路。圖G=(V, E)的傳遞簡(jiǎn)約G′=(V′, E′)是和G有相同的傳遞閉包的圖中邊數(shù)最少的圖，圖的傳遞簡(jiǎn)約可以根據(jù)文獻(xiàn)[11]有效求得。

2.2 雙線性配對(duì)

定義2 令G1和G2分別為階為q的加法群和乘法群并且P∈G1，P為G1的生成元。一個(gè)雙線性映射e: G1×G1→G2具有以下性質(zhì)。

1) 雙線性: 對(duì)于任意的(P, Q)∈G1×G1和a, b∈Zp滿足e( aP, bQ)=e( P, Q)ab。

2) 非退化性：存在(P, Q)∈G1×G1使得e( P, Q)≠I，其中I為G2中單位元。

3) 可計(jì)算性：存在有效的多項(xiàng)式時(shí)間算法計(jì)算e( P, Q)，其中P、Q∈G1。

其中e為橢圓曲線上Weil或者Tate配對(duì)[12]，該配對(duì)被用于建立一個(gè)雙線性映射。

2.3 復(fù)雜性假設(shè)

本文方案的安全性被歸約到CDH[13]問(wèn)題上，即在群G中計(jì)算Diffie-Hellman問(wèn)題是困難的，將CDH問(wèn)題定義如下。

定義3 給定一個(gè)群G其次數(shù)為p生成元為P，任選a、b∈RZp并且aP、bP∈G，則給定aP、bP∈G計(jì)算abP在概率多項(xiàng)式時(shí)間是困難的。

定義4 假定在群G中CDH問(wèn)題對(duì)于任意有效算法以時(shí)間t和概率ε保證其不被攻破。

3 基于身份的傳遞簽名方案

根據(jù)Paterson和Waters[14]的思想，本文提出一個(gè)新的傳遞簽名方案。該方案包括系統(tǒng)參數(shù)生成、私鑰生成、簽名、驗(yàn)證、邊簽名、邊驗(yàn)證、傳遞組合幾個(gè)步驟, 并且簽名生成方可以通過(guò)使用簽署消息的隨機(jī)數(shù)rm∈R來(lái)構(gòu)造身份選項(xiàng)。此外，若消息空間的無(wú)限制可將消息M串聯(lián)時(shí)間戳γ2使消息M′=M‖γ2，所以攻擊者就不能簡(jiǎn)單的通過(guò)重放攻擊對(duì)簽名進(jìn)行偽造。下面考慮該簽名的基本構(gòu)造，由以下的多項(xiàng)式時(shí)間算法組成。

系統(tǒng)參數(shù) 給定參數(shù)k, PKG選擇線性映射群(G1, G2)，并且(G1,+)和(G2,·)的次數(shù)均為p(p＞2k )構(gòu)造線性配對(duì)e: G1×G1→G2，其中P是G1中的生成元。PKG隨機(jī)選擇α∈RZp, 計(jì)算P1=αP并任選擇bP=P2∈G1。PKG從G1中選擇元素u′和m′，并生成長(zhǎng)度分別為nu和nm的2個(gè)向量U=(ui)、M=(mi)，其中u1, u2,…,unu和m1, m2,…,mnm均為G1中的元素。公開(kāi)參數(shù)為Pparam=(G1, G2, P, P1, P2,U,M,u′, m′)，PKG的私鑰是αP2。在這里假設(shè)消息的長(zhǎng)度和身份的長(zhǎng)度分別為nm和nu。

私鑰 令uI為長(zhǎng)度為nu的比特字符串并作為圖G=(V, E)節(jié)點(diǎn)I的身份，其中ui為uI的第i bit，并定義U?{1,…,nu}當(dāng)且僅當(dāng)u[ i]=1。為構(gòu)建用戶私鑰PKG隨機(jī)選擇ru∈Zq，計(jì)算ruP的散列值hu=H( ruP)=H( S2)，并生成節(jié)點(diǎn)I的私鑰：

簽名 當(dāng)簽名人對(duì)消息M=(m1, m2,…,mnm)進(jìn)行簽名時(shí)，隨機(jī)選擇rm∈Zq并計(jì)算：S1=sku+rm，S2=ruP，S3=rmP。其中，σ=(S1, S2,S3)是對(duì)消息M的簽名。

邊簽名 給定傳遞邊(i, j)∈E，通過(guò)下式計(jì)算傳遞邊簽名。

邊驗(yàn)證 如果等式邊簽名ijσ當(dāng)執(zhí)行下式正確時(shí)，邊簽名驗(yàn)證成功。

傳遞組合 若有向圖G=(V, E)中存在(i, j, k,σij,σjk)可計(jì)算傳遞簽名為σik=σij-σjk。這里，假定i＜j＜k。正確性: 計(jì)算SK=SI-σik?？芍?，與標(biāo)準(zhǔn)簽名生成的結(jié)果相同并確定其正確性。

4 安全性證明

在基于RSA的方案中Micali和Rivest提出了基本的傳遞簽名方案，Bellare在該方案的基礎(chǔ)上給出了一個(gè)的簡(jiǎn)要證明。此后Gregory將上述方案進(jìn)行匯總，提出了一個(gè)詳盡的隨機(jī)預(yù)言模型的證明方法。Shahandashti雖提出了一個(gè)雙線性配對(duì)的傳遞簽名方案，但該方案是基于證書的，同時(shí)也給出了相應(yīng)的證明。本文以Paterson和Waters的安全性為基礎(chǔ)，通過(guò)采用標(biāo)準(zhǔn)模型的證明方法對(duì)傳遞簽名的基本簽名方案和可傳遞性進(jìn)行證明。

定理1 Paterson的方案以(ε′,t′, qe′, qs′ )不可偽造，那么上述基于身份的傳遞簽名方案以(t, qe, qs, qts)歸約為Paterson的方案并保證其不可偽造性，qe, qs, qts分別表示進(jìn)行提取查詢、邊簽名查詢和傳遞邊組合查詢的次數(shù)。其中

證明 假定存在(t, qe, qs, qts)的敵手A，能夠構(gòu)造出概率多項(xiàng)式時(shí)間的子查詢算法B以不超過(guò)ε′′的概率來(lái)偽造一個(gè)Paterson的簽名。

算法B被給定Paterson簽名的系統(tǒng)參數(shù)Pparam=(G1, G2, P, P1, P2, U′, M′, u′, m′)，其中U′和M′是長(zhǎng)度分別為nu和nm的2個(gè)向量U′=(ui)、M′=(mi)，其中u′, u1, u2,…,unu和m′, m1, m2,…,mnm均為G1中的元素。

私鑰提取查詢：當(dāng)攻擊者A詢問(wèn)身份Ii（1≤i≤qe）的私鑰時(shí)，算法B詢問(wèn)自己的私鑰提取預(yù)言機(jī)，并將返回的身份Ii的私鑰發(fā)送給攻擊者A。

邊簽名查詢：當(dāng)攻擊者A詢問(wèn)傳遞邊(i, j)∈E的邊簽名時(shí)，算法B向自己的標(biāo)準(zhǔn)簽名查詢進(jìn)行詢問(wèn)，得到對(duì)消息MI和MJ的簽名SI=(SI1,SI2,SI3)和SJ=(SJ1,SJ2,SJ3)，然后算法B計(jì)算邊簽名：σij=SI1-SJ1

傳遞邊組合查詢：攻擊者A對(duì)基于身份I和邊簽名σij,σjk進(jìn)行傳遞邊組合查詢。算法B向自己的邊簽名查詢進(jìn)行詢問(wèn)，得到邊簽名σij、σjk，并計(jì)算σik=σij-σjk，算法B把得到的簽名σik作為傳遞邊的組合返回給攻擊者A。

算法B的時(shí)間分析如下：B的運(yùn)行時(shí)間等于攻擊者A的偽造時(shí)間加上回答qe次提取查詢的時(shí)間，qs次邊簽名查詢的時(shí)間，qts次傳遞組合查詢的時(shí)間。提取查詢和可驗(yàn)證加密簽名查詢的時(shí)間復(fù)雜度為O(1)，仲裁查詢的時(shí)間復(fù)雜度為O( nu+nm)，由此可得：t′=t+O( qe+qs+(nu+nm)qts)。

定理2 如果攻擊者在時(shí)間t內(nèi)，進(jìn)行qe次提取查詢，qs次邊簽名查詢，qts次傳遞組合查詢，并且成功攻破傳遞性的概率至少是ε，那么就能夠以(ε′,t′)攻破CDH問(wèn)題。其中，

ρ為群加法運(yùn)算所需要的時(shí)間，τ為群標(biāo)量乘運(yùn)算所需要的時(shí)間。

證明 假設(shè)存在(ε,t, qe, qs, qts)攻擊者A，使用攻擊者A構(gòu)造一個(gè)概率多項(xiàng)式時(shí)間算法B，他能以至少ε′的概率和最多t′的時(shí)間來(lái)解決CDH問(wèn)題。

將群G1和生成元P及aP, bP發(fā)送給算法B，為了能夠使用攻擊者A去計(jì)算CDH難題abP，算法B要向攻擊者A模擬一個(gè)挑戰(zhàn)者，算法B的模擬如下。

系統(tǒng)參數(shù)生成 對(duì)于給定的qe,qs,qts,nu和nm，算法B令lu=2(qe+qs+qts)， lm=2(qs+qts)，隨機(jī)選擇整數(shù)ku和km，且0≤ku≤nu，0≤km≤nm，算法B假設(shè)lu( nu+1)＜p，lm(nm+1)＜p。B選擇整數(shù)x′∈RZlu和長(zhǎng)度為nu的向量X=(xi)，其中xi∈RZlu(i=1,…,nu)。同理，隨機(jī)選擇z′∈RZlm和長(zhǎng)度為nm的向量Z=(zj)，其中zj∈RZlu(j=1,…,nm)。算法B同樣選擇整數(shù)y′, w′∈Zp和2個(gè)長(zhǎng)度分別為nu和nm的向量Y=(yi)，W=(wj)，其中，yi, wj∈RZp，i=1,…,nu，j=1,…,nm。

為分析簡(jiǎn)便，定義如下兩組函數(shù)分別用來(lái)表示身份u和消息m：

下面，算法B通過(guò)計(jì)算以下等式構(gòu)造出簽名方案所需的系統(tǒng)參數(shù)：

通過(guò)這種指派，可以看出PKG的私鑰為aP2=abP，并且對(duì)于所有的身份u和消息m有以下等式成立：

將所有的系統(tǒng)參數(shù)發(fā)送給攻擊者A。

密鑰提取查詢 考慮對(duì)身份u進(jìn)行私鑰查詢，B現(xiàn)在并不知道PKG的私鑰，但可假設(shè)F( u)≠0mod p并通過(guò)任選ru∈RZp可以構(gòu)造以下私鑰：

由以上過(guò)程可以看出，對(duì)于攻擊者A來(lái)說(shuō)，由算法B偽造的私鑰與PKG產(chǎn)生的私鑰是不可區(qū)分的。此外，如果F( u)=0mod p，算法B的計(jì)算會(huì)被迫中斷。為了方便分析，在遇到F( u)=0modlu的情況時(shí)，算法B的計(jì)算就會(huì)終止。由于假設(shè)了lu( nu+1)＜p，所以能得到0≤luku≤p ，這2個(gè)公式，所以若F( u)=0modp成立就一定存在F( u)=0modlu；若F( u)≠0modlu則能導(dǎo)出F( u)≠0modp。因此，算法B對(duì)身份u的私鑰進(jìn)行偽造在以上條件下是充分的。

傳遞邊簽名查詢 給定身份uI，uJ和消息mI，mJ可查詢一個(gè)可驗(yàn)證加密簽名。

偽造 若B在上述查詢中都正確執(zhí)行，A根據(jù)給定的假設(shè)條件以至少ε的概率返回一個(gè)偽造的身份和消息⌒，并返回一個(gè)偽造的可驗(yàn)證加密邊簽名。由于簽名方案中加入了S2的散列，可能導(dǎo)致偽造過(guò)程出現(xiàn)2種可能的結(jié)果。一種結(jié)果是B偽造出與原先設(shè)定的身份一致的偽造結(jié)果，另一種是偽造出與方案不一致的身份但改身份與原始簽名中部分相等。下面分別討論這2種情況。

1) 輸出與原始簽名身份uJ一致的偽造簽名。存在當(dāng)子查詢B計(jì)算：

根據(jù)上述構(gòu)造解決了CDH困難問(wèn)題，其身份部分分離的結(jié)果能夠與偽造的任意頂點(diǎn)結(jié)合，生成新的偽造邊簽名σik′。

2) 輸出與原始簽名節(jié)點(diǎn)uJ不一致的偽造簽名，但部分計(jì)算結(jié)果相同。計(jì)算：

證明分析：若A可以生成一個(gè)偽造傳遞邊簽名，子查詢B在不改變邊簽名取值的情況下，通過(guò)變換構(gòu)造一個(gè)新的Paterson簽名方案，并計(jì)算出傳遞邊簽名，解決了CDH困難問(wèn)題。

復(fù)雜度分析：通過(guò)上述的構(gòu)造，可以計(jì)算出子查詢B不被中斷并退出構(gòu)造的概率。分析B不被中斷的概率為：

在構(gòu)造過(guò)程中，如果使得模擬完成并且在中間過(guò)程不發(fā)生終止，需要滿足以下3個(gè)條件：

① 對(duì)身份u的密鑰提取查詢都有F( u)=0modlu；

② 對(duì)于所有攻擊者A進(jìn)行邊簽名查詢的身份和消息對(duì)(uI, mI)和(uJ,mJ)，等式F( u)≠0modlu與K( m)≠0modlm至少要有一個(gè)成立；

③ 對(duì)于攻擊者A所產(chǎn)生有效簽名的身份和消息對(duì)(u*, m*)，等式F( u*)=0modlu成立，并且等式K( m*)=0modlm也成立。

將上述分析表示成概率公式為

可以看出函數(shù)F與K是互不相容事件，所以可以將上式分開(kāi)進(jìn)行計(jì)算。根據(jù)以上的假設(shè)條件，當(dāng)lu( nu+1)＜p由F( uI)=0modp?F( uI)=0mod lu。計(jì)算概率：

還可以得到下式：

由于身份u1, u2代入F中是不同的2個(gè)函數(shù)值，其結(jié)果也不相同。所以條件概率中任意必然是互不相容的。在這里認(rèn)為事件 A 和i事件對(duì)于任何身份都是獨(dú)立的，并且有，因此可以進(jìn)行如下計(jì)算：

在證明開(kāi)始時(shí)，設(shè)置 lu= 2 (qe+ qs+ qts)，因此有：

這樣

在B能夠正常進(jìn)行查詢的情況下，敵手A以至少ε的概率對(duì)該協(xié)議進(jìn)行偽造，其子查詢B能夠計(jì)算出CDH問(wèn)題。通過(guò)上述分析在給定敵手A的時(shí)間復(fù)雜度為t的情況下，子查詢B的時(shí)間復(fù)雜度為：

通過(guò)以上分析，定理證明完畢。

5 結(jié)束語(yǔ)

傳遞簽名是近年來(lái)提出的用于對(duì)傳遞二元關(guān)系進(jìn)行簽名的簽名方案，已有的為數(shù)不多的傳遞簽名方案都缺乏可證安全或僅在隨機(jī)預(yù)言模型中是可證安全的。本文根據(jù) CDH問(wèn)題構(gòu)造了一個(gè)基于身份的傳遞簽名方案，并在標(biāo)準(zhǔn)模型下對(duì)其安全性進(jìn)行了證明。這種基于身份的二元關(guān)系認(rèn)證具有重要的現(xiàn)實(shí)意義，它可以將傳統(tǒng)的單點(diǎn)認(rèn)證擴(kuò)展到對(duì)2個(gè)認(rèn)證主體之間某種“關(guān)系”進(jìn)行認(rèn)證。如果將這種“關(guān)系”進(jìn)行形式化即可以組成一個(gè)可傳遞的關(guān)系網(wǎng)絡(luò)，其中信任管理網(wǎng)絡(luò)就是一種重要的應(yīng)用。但本文提出的方案適用于無(wú)向網(wǎng)絡(luò)，而實(shí)際應(yīng)用中“關(guān)系”有可能是矢量，因此還需要將方案向有向傳遞簽名進(jìn)行擴(kuò)展。

[1] MICAILI S, RIVEST R L. Transitive signaure schemes[A]. CT-RSA 2002(LNCS 2271)[C]. Springer-Verlag, 2002. 236-243.

[2] BELLARE M, NEVEN G. Transitive signatures based on factoring and RSA[A]. ASIACRYPT 2002(LNCS 2501)[C]. Springer-Verlag,2002. 397-414.

[3] BELLARE M, NEVEN G. Transitive signatures: new schemes and proofs [J]. IEEE Transactions on Information Theory, 2005, 51(6):2133-2151.

[4] SHAHANDASHTI S F, SALMASIZADEH M, MOHAJERI J. A provably secure short transitive signature scheme from bilinear group Pairs[A]. SCN 2004(LNCS 3352)[C]. Springer-Verlag, 2005.60-76.

[5] 黃振杰, 郝艷華, 王育民等. 一個(gè)高效的有向傳遞簽名方案[J]. 電子學(xué)報(bào), 2005,33(8):1497-1501.HUANG Z J, HAO Y H, WANG Y M, et al. Efficient directed transitive signature scheme[J]. Acta Electronica Sinica2005, 33(8):1497-1501.

[6] KUWAKADO H, TANAKA H. Transitive signature scheme for directed trees[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2003,E86-A(5): 1120- 1126.

[7] YI X, TAN C H, OKAMOTO E. Security of Kuwakado-Tanaka transitive signature scheme for directed trees[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,2004, E87-A(4): 955-957.

[8] YI X. Directed transitive signature scheme[A]. CT-RSA 2007(LNCS 4377)[C]. Springer-Verlag, 2007. 129–144.

[9] MA C, WU P, GU G. A new method for the design of stateless transitive signature schemes[A]. APWeb 2006(LNCS 3842)[C]. Springer-Verlag, 2006. 897-904.

[10] WANG L C, CAO Z F, ZHENG S H, et al. Transitive signature from braid groups[A]. IndoCrypt 2007(LNCS 4859)[C]. Springer-Verlag,2007. 183-196.

[11] AHO A V, GAREY M R, ULLMAN J. The transitive reduction of adirected graph[J]. SIAM Journal of Computing , 1972, 1(2): 131-137.

[12] BONEH D, LYNN B, SHACHAM H. Short signature from the Weil pairing[J]. Journal of Cryptology, 2004, 17(4): 297-319.

[13] HERRANZ J, LAGUILLAUMIE F. Blind ring signatures secure under the chosen-target-CDH assumption[A]. ISC 2006(LNCS 4176)[C].Springer-Verlag, 2006. 117-130.

[14] LU S, OSTROVSKY R, SAHAI A, et al. Sequential aggregate signturesand multisignatures without random oracles[A]. Eurocrypt 2006(LNCS 4004)[C], Springer-Verlag, 2006. 465-485.