標準模型下可證明安全的基于身份多代理簽名

陳　明　　　袁少良

(宜春學院數學與計算機科學學院　江西宜春　336000)

?

標準模型下可證明安全的基于身份多代理簽名

陳明袁少良

(宜春學院數學與計算機科學學院江西宜春336000)

(chenming9824@aliyun.com)

基于身份多代理簽名的2類主要形式化安全模型分別存在敵手攻擊目標不準確和敵手分類不完備的問題，而且，目前仍缺乏真正可證明安全的有效方案.融合現有安全模型，重新定義了基于身份多代理簽名的標準安全模型.新模型立足于改進現有模型存在的問題，采用更加完備的敵手分類標準，形式化定義各類敵手的行為和攻擊目標，采用簡單清晰的證明結構.在新安全模型框架下，提出一種基于身份的多代理簽名方案，其安全性被規約為多項式時間敵手求解CDH問題.此外，著重分析了最近提出的一種基于身份多代理簽名方案及其安全模型，指出其中的3個主要缺陷.對比分析表明，新的安全模型更加完備，新提出的多代理簽名是一種真正的、在標準模型下可證明安全的基于身份密碼方案.

多代理簽名；基于身份密碼學；雙線性映射；計算Diffie-Hellman問題；標準模型

代理簽名(proxysignature)是指原始簽名者將自身的簽名權限授予代理簽名者，然后由代理簽名者代表原始簽名者實施簽名的一種簽名算法.自1996年Mambo等人[1]提出代理簽名概念以來，其他研究者相繼提出代理簽名的多個變種，包括：多代理簽名(multi-proxysignature)、代理多簽名(proxymulti-signature)、多代理多簽名(multi-proxymulti-signature)、代理盲簽名(proxyblindsignature)和代理環簽名(proxyringsignature)等[2-8].代理簽名及其變形在電子商務和電子政務等領域有重要的研究和應用價值.

從授權方式來看，代理簽名主要分為：完全代理、部分代理和基于授權書的代理.代理授權書由原始簽名者和代理簽名者共同協商，并由原始簽名者實施代理授權簽名.授權書內容主要包含：原始簽名者和代理簽名者身份、代理權適用范圍描述和有效期限等信息.基于授權書的代理簽名能夠實現原始簽名者和代理簽名者身份的可鑒別性、(原始簽名者)授權和(代理簽名者)代理行為的不可否認、以及防止代理權被濫用等安全屬性[9-11].比較而言，不采用授權書的代理簽名方案存在一些固有的局限性[9-11]，目前的研究重點都集中在基于授權書的代理簽名方案.

基于身份密碼學(identity-basedcryptography，IBC)[12-13]是一種將用戶身份標識(ID)作為用戶公鑰的非對稱密碼體制.在IBC中，可信的密鑰生成中心(privatekeygeneration，PKG)根據用戶ID使用其主密鑰為用戶生成長期私鑰，但不產生公鑰證書，無需公鑰基礎設施支持，從而減輕了用戶密鑰管理負擔.Zhang等人[14]將IBC與代理簽名相結合提出基于身份的代理簽名方案.基于身份的代理簽名方案繼承了IBC算法的優點，不需要構建公鑰基礎設施，易于實現，已成為本領域研究的一個新熱點.

針對電子商務的特殊應用需求，Hwang等人[2]提出多代理簽名概念，由1個原始簽名者將他的簽名權授予n(>1)個代理簽名者，然后由n個代理簽名者共同代表原始簽名者實施簽名.考慮如下場景：當公司首席執行官正在長途飛行，但有一份緊急文件需要立即簽署，此時，公司各部門經理可以行使事先被授予的代理簽名權共同代表首席執行官簽署該文件.可見，多代理簽名方案具有實際的應用價值.

一些研究者相繼提出多個IBMPS(identity-basedmulti-proxysignature)方案[15-21].Chen等人[15]、Li等人[16]、Mishra等人[19]提出的IBMPS方案沒有定義有效的形式化安全模型.Cao等人[17]、Sahu等人[20]分別提出一種IBMPS方案，并在隨機預言模型下證明了方案的安全性.但是，Xiong等人[18]、Asaar等人[22]分別指出Cao等人[17]的方案和Sahu等人[20]的方案存在安全缺陷.最近，谷科等人[21]提出一種標準模型下的IBMPS方案(記為Gu-IBMPS).標準模型不依賴于現實世界無法實現的隨機預言假設[23]，比隨機預言模型具有更強的安全規約.但是，Gu-IBMPS方案及其安全模型存在幾個缺陷(詳細分析見本文2.2節)，不具有可證明安全性.就目前掌握的文獻來看，還沒有一種IBMPS方案真正實現了可證明安全性.

在代理簽名的安全模型方面，Boldyreva等人[24]首先提出一個可證安全模型，并將幾種代理簽名機制的安全性規約為基本的計算復雜性假設.隨后，Wang等人[25]、Cao等人[17]沿用了Boldyreva模型，并將該模型擴展到(基于身份的)多代理簽名方案.但是Boldyreva模型證明結構復雜，且不完備，正如Schuldt等人[26]所指出的那樣，該模型沒有將代理授權簽名作為安全游戲模擬的對象.最近，在早期工作的基礎上，Boldyreva等人[11]進一步歸納總結了相關研究[26-27]，改進了其安全模型，包括：明確地定義了代理簽名的各項安全屬性；引入自我代理(self-delegation)[27]擴展了敵手類型，并對敵手行為進行了形式化定義；明確區分一般代理和基于授權書的代理簽名及其安全模型.此外，Huang等人[28]也提出一種代理簽名安全模型.Yu等人[29]，Liu等人[30]、Sun等人[31]分別將Huang模型擴展到多代理簽名和代理多簽名領域.與Boldyreva模型不同，Huang等人的模型及其擴展[28-31]強調代理授權簽名在多代理簽名安全模型中的重要作用，定義了代理授權簽名詢問，定義了3種類型的敵手，明確指出其定義的第2類敵手[30-31]的主要攻擊目標是偽造代理授權簽名.但是，該模型沒有涵蓋原始簽名者的自我代理情形.谷科等人[21]引用了Boldyreva模型[11]，并基于Paterson等人[32]的標準簽名模型，定義了多代理簽名的標準模型.但是，該模型[21]顯然沒有注意到代理授權簽名在多代理簽名安全模型中的作用，存在缺陷，不能有效模擬針對代理授權簽名的攻擊行為.因此，盡管Gu-IBMPS方案在其安全模型下可證明安全，仍然受到其定義的第4類敵手的偽造攻擊.詳細分析見本文2.2節.

可見，可證明安全的基于身份多代理簽名及其安全模型還有待進一步研究，這是本文研究的動機.

本文研究了基于身份的多代理簽名及其安全模型，主要在2方面做出一定貢獻：

1) 在總結、融合現有安全模型的基礎上，定義了基于身份多代理簽名的標準安全模型.本文安全模型基本沿用了Huang模型的證明結構，定義了代理授權簽名詢問，能有效模擬針對代理授權簽名的攻擊行為，同時引用了Boldyreva模型的敵手類型(增加了自我代理情形的形式化模擬)，形式化定義了各類敵手的行為.與現有2類主要安全模型比較，本文安全模型證明結構更清晰，各類敵手攻擊目標更明確，敵手類型涵蓋更全面.并且，本文標準安全模型只需稍加擴展，可用于基于身份的(多)代理(多)簽名方案形式化分析.

2) 本文提出一種真正在標準模型下可證明安全的基于身份多代理簽名方案.相較現有方案，本文方案不僅安全性更強，而且計算開銷更低.此外，本文還詳細分析了Gu-IBMPS方案及其安全模型存在的主要缺陷.

1　背景知識

1.1雙線性映射與困難數學問題

這里簡要闡述與本文相關的基本數學理論：雙線性映射理論及存在的困難數學問題和假設.詳細內容請參考文獻[13,32].

雙線性映射.給定大素數p，階為p的循環群G1和G2，g是G1的1個生成元，如果e：G1×G1→G2是從G1到G2的1個有效的雙線性映射，那么滿足以下條件.

1)雙線性：給定u，v∈G1和任意的a，b∈p，滿足e(ua，vb)=e(u，v)a b；

2)非退化性：e(g，g)≠1；

3)可計算性：給定任意的u，v∈G1，存在多項式時間算法能成功計算e(u，v).

CDH(computationalDiffie-Hellman)問題.對于任意未知的a，b∈p，給定g，ga，gb∈G1，求解ga b.

CDH假設.如果不存在多項式時間算法在時間t內以至少ε的概率求解CDH問題，那么稱(ε，t)-CDH假設在G1上成立.

1.2基于身份多代理簽名模型

IBMPS方案由系統建立(Setup)、用戶私鑰產生(KeyGen)、基于身份簽名(IB-Sign)及驗證(IBS-Verify)、代理授權簽名(DelegateGen)及驗證(DelegateVer)、多代理簽名(MProxySign)及驗證(MProxyVerify)八個算法組成.

Setup算法由PKG執行，輸入安全參數k，輸出系統公開參數params和PKG主密鑰msk.

KeyGen算法由PKG執行，輸入params，IDu，msk，輸出用戶私鑰sku.

IB-Sign算法作為DelegateGen和MProxySign算法基礎，輸入params，簽名者身份IDu及其私鑰sku，簽名消息m，輸出簽名σIBS.

IBS-Verify算法作為DelegateVer和MProxyVerify算法基礎，輸入params，IDu，m，σIBS，輸出T表示接受簽名或⊥表示簽名無效.

DelegateVer算法由每位代理者分別執行，輸入params，IDo，w，δ，輸出T表示代理授權簽名有效或⊥表示代理授權簽名無效.

1.3基于身份多代理簽名安全模型

本文在Paterson等人[32]的標準簽名模型基礎上，融合Boldyreva模型[11]和Huang模型及其擴展[28-31]，定義了基于身份多代理簽名的標準安全模型.

(多)代理簽名方案應滿足的主要安全屬性包括[2,10-11]：不可偽造性(unforgeability)、不可否認性(undeniability)、身份可鑒別性(identifiability)、可驗證性(verifiability)和防止濫用性(preventionofmisuse).

文獻[11，26，28-30]的分析表明，采用代理授權書的(多)代理簽名方案若能實現不可偽造性，那么必然滿足身份的可鑒別性、不可否認性和防止濫用性.基于此，本文重點討論IBMPS方案的可驗證性和自適應選擇消息攻擊下的不可偽造性(existentialunforgeabilityunderadaptivechosenmessageattack，EUF-CMA).

下面回顧現有模型定義的敵手類型.

谷科等人[21]將Boldyreva等人[11]定義的4種類型敵手擴展到多代理簽名集合，描述如下：

第1種類型敵手(無代理情況，本文用A1表示)用于模擬標準簽名方案的安全性，被允許詢問用戶私鑰(除了不被敵手所控制的用戶ID*)和簽名預言機，以及創建新用戶.

第2種類型敵手(自我代理情況，本文用A2表示)不控制原始簽名者和代理簽名者，此一情形下，原始簽名者和所有代理簽名者均是同一用戶ID*.

第3種類型敵手(授權代理情況，本文用A3表示)控制了原始簽名者和至多n-1個代理簽名者.

第4種類型敵手(被代理情況，本文用A4表示)控制了所有n個代理簽名者，但不控制原始簽名者.

可見，4種類型的敵手都實現了能力最大化，他們控制了除挑戰用戶ID*以外的所有用戶，并且還被賦予創建新用戶的能力.我們將在下面的安全模型中形式化定義每一類敵手的行為.

Gu-IBMPS模型允許敵手(主要指A2A3A4)提交“代理簽名私鑰詢問”和(多代理)“簽名詢問”，沒有定義“用戶私鑰詢問”和“代理授權簽名詢問”.該安全模型并不完備，不能有效模擬A4的攻擊能力(詳細分析見本文2.2節).A4控制了所有代理簽名者，不控制原始簽名者，從A4的視角來看，如果能偽造原始簽名者的有效代理授權簽名，那么利用他所控制的代理簽名者可以產生合法的多代理簽名.由此推論：A4的主要攻擊目標是偽造(不被控制的)原始簽名者ID*對特定授權書w*的有效代理授權簽名.

此外，Huang等人[28]模型也定義了3種類型的敵手，Yu等人[29]、Liu等人[30]將其擴展到多代理簽名集合.其中，第1類敵手不控制任何的合法用戶，僅能取得系統公開參數和用戶身份(公鑰)；第2類敵手等同于本文的A4；第3類敵手則等同于本文的A3.可以看出，該模型定義的第23類敵手蘊含了第1類敵手，因而在其證明過程中通常省略了第1類敵手[29-30].然而，Huang等人及其擴展模型[28-31]并不考慮標準簽名(A1)和自我代理情況(A2).

本文整合上述研究，定義敵手A∈{A2，A3，A4}與挑戰者B之間的游戲(IBMPS-EUF-CMAgame)模擬IBMPS方案的不可偽造性.由于A1敵手用于模擬標準簽名方案的安全性，本文的標準簽名直接采用Paterson簽名機制[32]，并且該簽名機制在標準模型下被證明滿足IBS-EUF-CMA安全，因此本文安全模型省略了A1敵手.此外，文獻[11]描述了一種可能的攻擊行為：敵手通過詢問標準簽名預言機(而非“代理授權簽名”預言機)取得代理授權簽名.同時，該文也給出一種相應的解決方案，即：為不同的預言機詢問分配標簽.為了簡化證明過程，本文模型忽略這一可能的攻擊行為.

關于IBMPS-EUF-CMAgame的描述如下：

1) 系統建立：B執行系統建立算法，輸出系統公共參數params，并發送給A.

2) 詢問：A自適應地執行多項式時間的詢問.

①KeyGen詢問：A提交1個用戶身份u，B返回簽名者私鑰sku；

下面對3種敵手的行為進行說明.

定義1. 如果不存在概率多項式時間敵手A，在時間t內以至少ε的概率贏得IBMPS-EUF-CMAgame，則IBMPS方案滿足(ε，t，qe，qd，qs)-IBMPS-EUF-CMA安全.這里，A最多執行了qe次KeyGen詢問、qd次DelegateGen詢問和qs次MProxySign詢問.

2　多代理簽名方案的密碼學分析

2.1基于身份多代理簽名方案描述

最近，谷科等人[21]提出一種基于身份的多(群)代理簽名方案Gu-IBMPS，簡要描述如下.

1)Setup：PKG執行Setup算法，產生并發布公共參數params={G1，G2，e，g，g1，τ′，I，m′，M}.其中，e：G1×G1→G2是滿足定義的雙線性映射；g是G1的生成元；g1，τ′，m′∈G1由PKG隨機選擇；I=(τi)，M=(mi)是由PKG選擇的長度分別為nu，nm的向量，并且向量I，M的元素τi和mi也是群G1上的元素.此外，PKG選擇3個抗碰撞的Hash函數H：{0，1}*→p，Hu：{0，1}*→{0，1}nu和Hm：{0，1}*→{0，1}nm，生成用戶公共參數列表UPK_List用于發布注冊用戶生成的公共參數，初始值為空.

2)KeyGen：提交用戶身份ui，ui為長度是nu的二進制串，PKG隨機選擇xi，ri∈p，產生用戶私鑰為).其中，Vi?{1，2,…，nu}表示ui中比特值等于1的位置d的集合.同時產生用戶公鑰參數pki=gxi.

3)UPK_List：PKG通過安全信道發送私鑰ski給用戶ui，并將公鑰參數pki發布到UPK_List.ui按照下列等式驗證私鑰ski的正確性：

4)MDelegate：u1為原始簽名者，對于每個代理者uj，j∈{2，3,…，n，n+1}，u1隨機選擇sj∈p，計算.其中，w1為授權書.令δ1,j,3=sk1,2=gr1，δ1,j,4=w1，則uj的代理授權簽名δj=(δ1,j,1，δ1,j,2，δ1,j,3，δ1,j,4).

6)MProxySign：n個代理簽名者代表u1按如下步驟對消息m進行簽名.

① 每個代理者uj隨機選擇λj∈p，計算:，令σ1,j,3=psk1,j,2，σ1,j,4=psk1,j,4，輸出部分代理簽名pσ1,j=(σ1,j,1，σ1,j,2，σ1,j,3，σ1,j,4).

② 存在1個代理者up(p∈{2，3,…，n，n+1})收集所有代理者的部分代理簽名，并按照下列等式驗證每個部分代理簽名的正確性:

如果存在某個部分代理簽名無效則拒絕代理簽名，否則計算：

令σ1,1,3=psk1,p,3=gr1，生成長度為n+1的元組σ1,3=(σ1,j,3)，j∈{1，2,…，n，n+1}.最后，輸出多代理簽名(w1，pσ1=(σ1,1，σ1,2，σ1,3，σ1,4)).

7)MProxyVerify：收到對消息m的多代理簽名(w1，pσ1=(σ1,1，σ1,2，σ1,3，σ1,4))，按如下計算進行驗證

如果相等則接受多代理簽名，否則拒絕.

2.2Gu-IBMPS方案分析

基于Boldyreva模型[11]，文獻[21]定義了多代理簽名的敵手類型及形式化安全模型，并以此模型分析了Gu-IBMPS方案的安全性，認為該方案滿足選擇消息攻擊下的不可偽造性.但是，本文分析發現，Gu-IBMPS方案及其安全模型存在3個缺陷.

1)Gu-IBMPS方案被稱為基于身份的多代理簽名，并不恰當.基于身份的簽名方案需要在用戶私鑰產生階段(即KeyGen算法)，將PKG的主密鑰和用戶身份嵌入到用戶的私鑰中，然后在簽名驗證階段使用PKG的公鑰和用戶身份進行驗證(具體算法過程可參考文獻[13，32]).也就是說，基于身份的簽名機制是將簽名結果與PKG的主密鑰和用戶身份產生密碼學關聯，不使用公鑰證書.反觀Gu-IBMPS方案，PKG沒有主密鑰，用戶私鑰雖由PKG產生，但與PKG公鑰不存在可驗證的密碼學關聯關系，僅通過公告板UPK_List發布用戶公開密鑰參數.同時，Gu-IBMPS方案也沒有使用公鑰證書保障用戶密鑰的可信性.在現實世界中，這樣的密碼系統不完備，需要額外的密鑰保障機制保護用戶的公鑰參數不被篡改.可見，Gu-IBMPS方案不是真正意義上的基于身份密碼方案.

2)Gu-IBMPS方案不滿足不可偽造性.我們首先回顧第4類攻擊者A4(見文獻[21]第2節情況4)：“敵手控制n+1個用戶中的至多n個用戶；該n個用戶偽造1個在沒有獲得用戶u*的授權下假裝用戶u*授權的多代理簽名”.根據描述，敵手控制了除原始簽名者u*以外的所有n個代理簽名者(A4可以訪問所有代理簽名者的私鑰)，那么A4需要獲得u*的可驗證正確的代理授權簽名，就能成功偽造多代理簽名.因此，A4的目標是偽造u*的代理授權簽名.下面給出攻擊實例演示A4如何偽造u*的授權簽名.

A4可以收集n份不同的由u*簽署的代理授權簽名，為每個代理簽名者偽造1份各不相同的代理授權簽名(n個不同的sj，但A4不需要知道sj).在真實的攻擊環境下，由于代理授權簽名在公開信道上發送，攻擊者收集代理授權簽名是容易實現的.由于A4控制了所有n個代理簽名者，A4能夠按照Gu-IBMPS方案的MProxyKeyGen和MProxySign算法為每個代理簽名者產生代理簽名密鑰并進行多代理簽名.

因此，在第4類攻擊者A4存在的情況下，Gu-IBMPS方案不滿足不可偽造性.

形成上述攻擊的原因是：Gu-IBMPS方案沒有注意到MDelegate算法的本質是原始簽名者對代理授權書w的簽名，因而沒有采用標準的Paterson簽名[32]機制進行代理授權簽名，而且在其后的安全性證明過程中缺乏對“攻擊者偽造代理授權簽名”這一攻擊場景的形式化分析.

3)Gu-IBMPS方案的安全模型存在缺陷，不能完全模擬真實的攻擊場景.正如前一點指出的，Gu-IBMPS模型忽略了“攻擊者偽造代理授權簽名”這一攻擊場景，敵手不能詢問代理授權簽名.在真實環境下，代理授權簽名通常在公開信道上發送，敵手能比較容易地竊取該授權簽名.Schuldt等人[26]就曾指出，Boldyreva模型沒有將代理授權簽名作為安全游戲模擬要素.同樣地，衍生自Boldyreva模型的Gu-IBMPS模型也沒有定義代理授權簽名詢問，敵手不能詢問(不被敵手控制的)用戶u*對非特定授權書w(≠w*)的代理授權簽名(上述攻擊證明這一詢問是必要的)，削弱了敵手的能力.通過以上分析可以看出，Gu-IBMPS模型沿襲了Boldyreva模型的固有缺陷，不能完備地模擬真實的攻擊場景.

3　改進的基于身份多代理簽名方案

本文提出一種標準模型下可證明安全的基于身份多代理簽名方案，改進了Gu-IBMPS方案的2個缺陷：1)本文方案擴展于Paterson[32]簽名機制，采用Paterson簽名及驗證算法作為其標準簽名及驗證算法，是一種真正意義上的標準模型下的IBMPS機制；2)本文方案的DelegateGen和DelegateVer算法將代理授權書w作為被簽名消息，采用Paterson簽名機制進行代理授權簽名和驗證，防止了代理授權簽名偽造攻擊.本文方案描述如下：

1)Setup：輸入安全參數k，PKG執行Setup算法，產生滿足定義的雙線性映射e：G1×G1→G2，g是G1的生成元；PKG隨機選擇α∈p和g2∈G1，計算g1=gα，Q=e(g1，g2)，將(g1，g2，Q)作為PKG公鑰，然后計算作為其主密鑰；PKG隨機選擇u′，w′，m′∈G1，選擇長度分別為nu，nw和nm的向量U=(ui)，W=(wi)，M=(mi)，向量中的元素滿足ui，wi，mi∈G1；選擇抗碰撞的Hash函數H1：{0，1}*→{0，1}nw，H2：{0，1}*→{0，1}nm分別用于將授權書和待簽名消息映射到大小為nw位和nm位的消息空間.PKG發布公共參數params={G1，G2，e，g，g1，g2，Q，u′，U，w′，W，m′，M，H1，H2}.本文方案要求用戶的身份ID統一為nu位二進制串.

2)KeyGen：提交用戶身份ui.用μi?{1，2,…，nu}表示ui中位值為1的位置d的集合.PKG隨機選擇ri∈p，計算用戶私鑰).PKG通過安全信道將ski發送給ui.收到ski后，ui計算等式是否成立來驗證私鑰的正確性.如果驗證等式成立，則接受ski作為自己的私鑰；否則，重新申請私鑰.

3)IB-SignIBS-Verify：本文方案采用Paterson簽名機制作為標準簽名及驗證算法，具體請參考文獻[32].

6)MProxySign：多代理簽名算法分為2步.第1步由每個代理者產生部分代理簽名；第2步由1個代理者up(p∈{2，3,…，n，n+1})收集所有部分代理簽名生成最終的多代理簽名.輸入代理授權簽名δ、原始代理簽名者身份ui(i∈{1，2,…，n+1})、代理授權書w、消息m，按如下步驟執行：

① 每個uj(j∈{2，3,…，n+1})選擇tj∈p，計算，令σj,3=skj,2，輸出部分代理簽名pσj=(σj,1，σj,2，σj,3).其中，θ?{1，2,…，nm}表示H2(m)中位值為1的位置i的集合.

注意，為了降低多代理簽名聚合者up的計算開銷，本文方案取消了up分別去驗證其他代理者的部分代理簽名pσj，up只需按照下面的MProxyVerify算法驗證最終多代理簽名的有效性.我們將在4.3節討論這樣的改進是否會影響算法的安全性.

7)MProxyVerify：收到對消息m的多代理簽名(w，σ1，σ2，σ3，σ4)，驗證者計算下列等式進行驗證：

如果上式成立則接受多代理簽名，否則拒絕.

4　改進方案分析

4.1正確性分析

本文方案的正確性由下列等式證明：

(1)

式(1)表明用戶私鑰驗證有效.

(2)

式(2)表明代理授權簽名及其驗證有效.

(3)

式(3)表明多代理簽名及其驗證有效.

由式(1)～(3)可驗證本文提出的多代理簽名算法滿足正確性和可驗證性.

4.2安全性分析

根據本文1.3節定義的安全模型，IBMPS方案存在4種類型敵手.對于敵手A1，Paterson簽名[32]機制已被證明滿足IBS-EUF-CMA安全，本文不再贅述.下面討論本文IBMPS方案在敵手A∈{A2，A3，A4}攻擊下的安全性.

定理1. 令ρ，τ分別表示G1上的乘法運算和指數運算時間，假設A最多執行了qe次KeyGen詢問、qd次DelegateGen詢問和qs次MProxySign詢問，如果(ε′，t′)-CDH假設成立，則本文提出的IBMPS機制滿足(ε，t，qe，qd，qs)-IBMPS-EUF-CMA安全.這里，ε′≥ε[64qs(qd+qs)(qe+qd+qs)(nu+1)(nw+1)(nm+1)]，t′>t+O((qenu+qd(nu+nw)+qs(nu+nw+nm))ρ+(qe+qd+qs)τ).

與文獻[32]的定理1類似，以下證明過程將本文IBMPS機制的不可偽造性規約為求解CDH問題.

證明. 假設存在(ε，t，qe，qd，qs)-forger敵手A，我們將構建1個算法B,利用A在時間t′內以至少ε′的概率解決CDH問題.下面模擬B與A的游戲.

1) 系統建立：B設置lu=2qe，lw=2(qe+qd)，lm=2(qe+qd+qs)，隨機選擇整數ku，km，kw，滿足條件0≤ku≤nu，0≤km≤nm，0≤kw≤nw.對于給定的(qe，qd，qs，nu，nm，nw)，我們假設有：lu(nu+1)

這里，μ ，θ，? 含義與第3節相同.然后，B構建公共參數：g1=ga，g2=gb，Q=e(g1,g2)；

B選擇安全的Hash函數H1，H2，將公共參數{G1，G2，e，g，g1，g2，Q，u′，U，m′，M，w′，W，H1，H2}發給A.這里，U=(ui)，M=(mj)，W=(wt).與文獻[32]相同，存在等式：

2) 詢問：A自適應地執行多項式時間的詢問.

①KeyGen詢問.收到該詢問，如果F(u)=0modlu，那么B終止游戲；否則F(u)≠0modlu，B隨機選擇ru∈p，計算用戶私鑰：sku=(sku,1，sku,2)=，返回給A.

根據文獻[32]定理1的論述，存在等式：

與文獻[32]保持一致，為了便于分析，本文模型也規定：當F(u)=0modlu時，B強制終止A的詢問.根據文獻[32]定理1的推論，由F(u)=0modp可推導F(u)=0modlu；由F(u)≠0modlu可推導F(u)≠0modp.也就是說，挑戰用戶u*的身份必然滿足條件：F(u*)=0modlu.該條件確保敵手A不能詢問u*的私鑰.我們將(F(u)=0modlu∧F(u)≠0modp)定義為小概率事件.與文獻[32]保持一致，同時也為了便于分析，本文也忽略這一小概率事件.

注意，為了保持用戶身份與密鑰的一致性，B需要存儲已創建的用戶私鑰，以備查詢，并且在以下各詢問中，除挑戰用戶u*外，其他用戶必須先創建私鑰.

最后，B輸出(δ1，δ2，δ3)作為代理授權簽名.

可以驗證，從A的視角來看，輸出結果是1個有效的代理授權簽名.

lm(ξ=H2(m))，B終止游戲，否則選擇rk，tk∈p，計算：

下面分3種情況討論B對CDH問題的回答.

作為對CDH問題的回答.

2) 對于第3類敵手A3，如果({?終止游戲；否則，B計算：

作為對CDH問題的回答.

作為對CDH問題的回答.

游戲模擬到此結束.如果游戲沒有終止，我們分析B利用A求解CDH問題的概率.DelegateGen詢問分為：F(u1)≠0modlu，(F(u1)=0modlu)∧(T(ω)≠0modlw)2個部分.MProxySign詢問分為：?F(uk)≠0modlu，(?F(uk)=0modlu)∧(K(ξ)≠0modlm)2個部分.

令qu是詢問中出現的身份數量，qw是詢問中出現的授權書的數量，qm是詢問中出現的簽名消息的數量.顯然，存在不等式：qu≤qe+qd+qs，qw≤qd+qs，qm≤qs.與文獻[32]類似的，本文定義6類事件Bi，B*，Cj，C*，Dk，D*如下.

Bi：F(ui)≠0modlu.

B*：F(u*)=0modp.

Cj：T(wj)≠0modlw.

C*：T(w*)=0modp.

Dk：K(mk)≠0modlm.

D*：K(m*)=0modp.

根據文獻[32]定理1的推論，由F(u)≠0modlu可推導F(u)≠0modp；由T(w)≠0modlw可推導T(w)≠0modp；由K(m)≠0modlm可推導K(m)≠0modp.

因此，B沒有終止游戲的概率為

Pr[

因此，有：

Pr[

如果游戲沒有被終止，且A以不低于ε的概率贏得游戲，那么B以不低于ε[64qs(qd+qs)(qe+qd+qs)(nu+1)(nw+1)(nm+1)]的概率成功求解CDH問題.

從算法的時間復雜度來看，在KeyGen詢問、DelegateGen詢問和MProxySign詢問中分別執行了O(nu)，O(nu+nw)，O(nu+nw+nm)次乘法運算以及O(1)次指數運算.令ρ和τ分別表示乘法運算和指數運算時間，那么算法B的時間復雜度為：t′≥t+O((qenu+qd(nu+nw)+qs(nu+nw+nm))ρ+(qe+qd+qs)τ).

證畢.

4.3對比與分析

就目前掌握的文獻資料來看，僅有Gu-IBMPS[21]方案是標準模型下的IBMPS方案.表1從計算開銷方面對比了本文提出的多代理簽名與Gu-IBMPS方案.列舉了5種主要運算:P表示雙線性對運算，M1表示G1上的乘運算，E1表示G1上的指數運算，M2表示G2上的乘運算，E2表示G2上的指數運算.n表示代理簽名者數量，uo表示原始簽名者,up代表單個(非聚合)代理簽名者,up k代表多代理簽名聚合者,uv代表多代理簽名驗證者.

Table1　Comparison of Computing Costs表1　計算性能比較

從表1可以看出，由于本文方案取消了分別驗證每個部分代理簽名，而只驗證1次多代理簽名，大大地降低了up k的計算開銷(每一種運算約減少了n的倍數次).此外，在多代理簽名驗證階段，驗證者約減少了(n+1)次M2運算和P運算.從總的計算性能來說，本文方案具有明顯的優勢，特別是避免了up k的高計算載荷(超過6nP).

安全性方面，現有IBMPS方案要么缺乏有效的形式化安全證明，要么存在已知安全缺陷.本文2.2節也指出了Gu-IBMPS方案存在安全缺陷，特別是該方案不符合基于身份密碼方案的基本要求.本文提出了真正的標準模型下的基于身份多代理簽名方案，PKG擁有主密鑰，并且利用主密鑰和用戶身份為用戶產生私鑰，私鑰驗證、代理授權簽名驗證和多代理簽名驗證都需要輸入PKG公鑰和相應用戶的身份，符合基于身份密碼技術規范[12-13,32].其次，本文方案采用標準的Paterson簽名機制進行代理授權簽名，有效防止了攻擊者偽造授權書.安全性證明表明，本文IBMPS方案真正實現了可證明安全性.

這里簡要討論在MProxySign算法中用多代理簽名驗證替換每個部分代理簽名驗證是否會影響算法整體安全性.根據4.2節的安全性證明，多代理簽名的整體安全性能夠被規約到任意單個用戶ui(i∈(1，2，…，n，n+1))的行為.具體來說，(極端情況下，只有1個用戶u*是誠實的，不被A所控制)如果敵手A能成功偽造有效的多代理簽名，那么，A要么能偽造有效的代理授權簽名(此時，u*=u1為原始簽名者)，要么能偽造u*的部分代理簽名(此時，u*=uj，j∈{2，3，…，n，n+1}為某個代理簽名者).根據4.2節定理1的結論，針對本文提出的多代理簽名方案，這樣的敵手是不存在的.因此，本文“多代理簽名有效”這一命題蘊含了“不存在敵手能成功偽造任一未被控制用戶的部分代理簽名”這一事實.也就是說，安全性證明表明“只要有1個誠實用戶沒有參與代理簽名，多代理簽名結果都無效”.根據逆否命題，可得：“所有誠實的用戶都必須參與簽名，多代理簽名結果才有效”.因此，簽名聚合者up可以使用多代理簽名驗證替代所有部分代理簽名驗證，不會降低算法安全性.

5　結束語

本文研究了基于身份多代理簽名及其安全模型.目前，本領域主要存在2類形式化安全模型：Boldyreva模型及其衍生模型、Huang模型及其擴展模型.我們注意到，Huang模型的證明結構更簡潔明晰，對敵手行為的刻畫更準確，而Boldyreva模型定義了更加完整的敵手類型.在總結、融合這2類安全模型的基礎上，本文定義了更加完備的多代理簽名標準模型，采用了Huang模型的證明結構和Boldyreva模型的敵手類型，對各類敵手的行為進行了更加明確的形式化定義.本文定義的標準模型具有可擴展性，只需稍加擴展，可形式化分析各類(多)代理(多)簽名方案.在本文安全模型框架下，我們提出一種基于身份的多代理簽名方案.與現有方案相比，本文方案真正實現了可證明安全性，其安全性被規約為多項式時間敵手求解CDH問題.此外，本文還詳細分析了最近提出的一種基于身份多代理簽名方案及其安全模型，指出其存在的3點主要缺陷.對該文的研究，奠定了本研究的基礎.

目前，標準安全模型已成為本領域的一類重要形式化方法，由于不依賴隨機預言假設，標準模型具有比隨機預言模型更強的安全規約.但是，標準模型需要構造特殊的安全函數，算法的計算開銷通常高于隨機預言模型下的同類型算法，并且模型的適應范圍更窄.就目前掌握的文獻資料來看，Paterson簽名機制是唯一一種被廣泛引用的標準模型下可證安全的IBS方案.構建標準模型下更加安全高效的IBS方案，以及將其擴展到其他密碼技術領域(如：無證書密碼學)仍然是一項開放性的工作.

[1]MamboM,UsudaK,OkamotoE.Proxysignaturefordelegatingsigningoperation[C] //Procofthe3rdACMConfonComputerandCommunicationsSecurity.NewYork:ACM, 1996: 48-57

[2]HwangSJ,ShiCH.Asimplemulti-proxysignatureschemeforelectroniccommerce[C] //Procofthe10thNationalConfonInformationSecurity. [S.1]:ROC, 2000: 134-138

[3]YiLijiang,BaiGuoqiang,XiaoGuozhen.Proxymulti-signaturescheme：Anewtypeofproxysignaturescheme[J].ElectronicsLetters, 2000, 36(6): 527-528

[4]HwangSJ,ChenCC.Newmulti-proxymulti-signatureschemes[J].AppliedMathematicsandComputation, 2004, 147(1): 57-67

[5]JiJiahui,LiDaxing,WangMingqiang.Newproxymulti-signature,multi-proxysignatureandmulti-proxymulti-signatureschemesfrombilinearpairings[J].ChineseJournalofComputers, 2004, 27(10): 1429-1435 (inChinese)(紀家慧, 李大興, 王明強. 來自雙線性配對的新的代理多簽名、多代理簽名和多代理多簽名體制[J]. 計算機學報, 2004, 27(10): 1429-1435)

[6]LuRongxing,CaoZhenfu,ZhouYuan.Proxyblindmulti-signatureschemewithoutasecurechannel[J].AppliedMathematicsandComputation, 2005, 164(1): 179-187

[7]ZhangFangguo,Safavi-NainiR,LinCY.Newproxysignature,proxyblindsignatureandproxyringsignatureschemesfrombilinearpairing[EB//OL].IACRCryptologyePrintArchive, 2003 [2015-02-17].http://eprint.iacr.org//2003//104.pdf

[8]GuKe,JiaWeijia,JiangChunlin.Agroupproxysignatureschemebasedonsub-secretevolution[J].JournalofComputerResearchandDevelopment, 2012, 49(5): 962-973 (inChinese)

(谷科, 賈維嘉, 姜春林. 一種子秘密演化的群體代理簽名方案[J]. 計算機研究與發展, 2012, 49(5): 962-973)

[9]KimS,ParkS,WonD.Proxysignatures,revisited[G] //LNCS1334:ProcofICICS’97.Berlin:Springer, 1997: 223-232

[10]LeeB,KimH,KimK.Strongproxysignatureanditsapplications[C//OL] //ProcoftheSymponCryptographyandInformationSecurity. 2001 [2014-12-30].http://cris.joongbu.ac.kr//publication//sps-SCIS2001.pdf

[11]BoldyrevaA,PalacioA,WarinschiB.Secureproxysignatureschemesfordelegationofsigningrights[J].JournalofCryptology, 2012, 25(1): 57-115

[12]ShamirA.Identity-basedcryptosystemsandsignatureschemes[G] //LNCS196:ProcofCRYPTO1984.Berlin:Springer, 1985: 47-53

[13]BonehD,FranklinM.Identity-basedencryptionfromtheweilpairing[G] //LNCS2139:ProcoftheCRYPTO2001.Berlin:Springer, 2001: 213-229

[14]ZhangFangguo,KimK.EfficientID-basedblindsignatureandproxysignaturefrombilinearpairings[C] //Procofthe8thConfonInformationSecurityandPrivacy.Berlin:Springer, 2003: 312-323

[15]ChenXiaofeng,ZhangFangguo,KimK.ID-basedmulti-proxysignatureandblindmulti-signaturefrombilinearpairings[C//OL] //ProcofKIISC, 2003[2014-12-30].http://caislab.kaist.ac.kr//publication//paper_files//2003//CISC2003//ID-based-proxymultisignature%20and%20multiblindsig.pdf

[16]LiXiangxue,ChenKefei.ID-basedmulti-proxysignature,proxymulti-signatureandmulti-proxymulti-signatureschemesfrombilinearpairings[J].AppliedMathematicsandComputation, 2005, 169(1): 437-450

[17]CaoFeng,CaoZhenfu.Asecureidentity-basedmulti-proxysignaturescheme[J].Computers&ElectricalEngineering, 2009, 35(1): 86-95

[18]XiongHu,HuJianbin,ChenZhong,etal.Onthesecurityofanidentitybasedmulti-proxysignaturescheme[J].Computers&ElectricalEngineering, 2011, 37(2): 129-135

[19]MishraS,SahuRA,PadhyeS,etal.EfficientID-basedmulti-proxysignatureschemefrombilinearpairingbasedonk-plusproblem[G] //CCIS165:ProcofINTECH2011.Berlin:Springer, 2011: 113-122

[20]SahuRA,PadhyeS.Provablesecureidentity-basedmulti-proxysignaturescheme[J].InternationalJournalofCommunicationSystems, 2015, 28(3): 497-512

[21]GuKe,JiaWeijia,LiChaoliang,etal.Identity-basedgroupproxysignatureschemeinthestandardmodel[J].JournalofComputerResearchandDevelopment, 2013, 50(7): 1370-1386 (inChinese)

(谷科, 賈維嘉, 李超良, 等. 標準模型下基于身份的群代理簽名方案[J].計算機研究與發展, 2013, 50(7): 1370-1386)

[22]AsaarMR,SalmasizadehM,SusiloW.Securitypitfallsofaprovablysecureidentity-basedmulti-proxysignaturescheme[EB//OL].IACRCryptologyePrintArchive, 2014[2015-02-17].https://eprint.iacr.org//2014//496.pdf

[23]BellareM,RogawayP.Randomoraclesarepractical:Aparadigmfordesigningefficientprotocols[C] //Procofthe1stACMConfonComputerandCommunicationsSecurity.NewYork:ACM, 1993: 62-73

[24]BoldyrevaA,PalacioA,WarinschiB.Secureproxysignatureschemesfordelegationofsigningrights[EB//OL].IACRCryptologyePrintArchive, 2003 [2014-12-17].https://eprint.iacr.org//2003//096.pdf

[25]WangQin,CaoZhenfu,WangShengbao.Formalizedsecuritymodelofmulti-proxysignatureschemes[C] //ProcCIT’05.LosAlamitos,CA:IEEEComputerSociety, 2005: 668-672

[26]SchdultJC,MatsuuraK,PatersonKG.Proxysignaturessecureagainstproxykeyexposure[G] //LNCS4939:ProcofPKC2008.Berlin:Springer, 2008: 344-359

[27]MalkinT,ObanaS,YungM.Thehierarchyofkeyevolvingsignaturesandacharacterizationofproxysignatures[C] //ProcofCryptology-EUROCRYPT2004.Berlin:Springer, 2004: 306-322

[28]HuangXY,SusiloW,MuY,etal.Proxysignaturewithoutrandomoracles[G] //LNCS4325:Procofthe2ndIntConfonMobileAd-hocandSensorNetworks(MSN2006).Berlin:Springer, 2006: 473-484

[29]YuY,SunY,YangB,etal.Multi-proxysignaturewithoutrandomoracles[J].ChineseJournalofElectronics, 2008, 17(3): 475-480

[30]LiuZhenhua,HuYupu,ZhangXiangsong,etal.Provablysecuremulti-proxysignatureschemewithrevocationinthestandardmodel[J].ComputerCommunications, 2011, 34(3): 494-501

[31]SunYing,XuChunxiang,YuYong,etal.Improvementofaproxymulti-signatureschemewithoutrandomoracles[J].ComputerCommunications, 2011, 34(3): 257-263

[32]PatersonKG,SchuldtJCN.Efficientidentity-basedsignaturessecureinthestandardmodel[G] //LNCS4058:ProcofACISP2006.Berlin:Springer, 2006: 207-222

ChenMing,bornin1978.ReceivedhisPhDdegreefromChongqingUniversity,Chongqing,China,in2011.NowheislecturerofYichunUniversity.Hismainresearchinterestsincludeinformationsecurity,securityprotocolandformalmethods.

YuanShaoliang,bornin1976.ReceivedhisPhDdegreefromHunanNormalUniversity,Changsha,Hunan,China,in2012.NowheislecturerofYichunUniversity.Hismainresearchinterestsincludebifurcationtheory,chaostheoryandcryptography.

ProvablySecureIdentity-BasedMulti-ProxySignatureSchemeinStandardModel

ChenMingandYuanShaoliang

(College of Mathematics and Computer Science, Yichun University, Yichun, Jiangxi 336000)

Multi-proxysignatureschemesarequiteusefultoolswhileasignerrequiresdelegatinghissigningrighttoagroupofproxysigners.Therearetwomaintypesofformalsecuritymodelsofmulti-proxysignatures.However,theyhavedeficiencies,respectively.Oneofthemiscomplicated,anddoesnotmodelthechosenwarrantattacks;theothermodeldoeshavetheincompletedefinitionofadversary.Meanwhile,thereissofarnoprovablysecureidentity-basedmulti-proxysignaturescheme.Inthispaper,wegiveaformalsecuritymodeloftheidentity-basedmulti-proxysignatureschemes,andproposeanidentity-basedmulti-proxysignaturescheme.Oursecuritymodelcompensatesfordeficienciesinexistingmodels.Itdefinesmorepowerfuladversarycapacity,formalizesthebehaviorsoftheadversaries,andadoptssimpleandclearproofstructure.Theproposedidentity-basedmulti-proxysignatureschemeisbasedonthewell-studiedCDH(computationalDiffie-Hellman)assumption,andisprovenexistentiallyunforgeableagainstchosenmessagewarrantattacksinoursecuritymodel.Inaddition,wepresentthattherearethreesecurityflawsinarecentproposedidentity-basedmulti-proxysignatureschemeandinitssecuritymodel.Comparativeanalysisshowsthatthenewsecuritymodelismorecomplete,andthenewmulti-proxysignatureschemeisarealandprovablysecureidentity-basedcryptosysteminthestandardmodel.

multi-proxysignature;identity-basedcryptography;bilinearpairing;computationalDiffieHellman(DH)problem;standardmodel

2015-03-09；

2015-08-11

國家自然科學基金項目(11361067);江西省自然科學基金項目(2014ZBAB207022)

TP309

ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina(11361067)andtheNaturalScienceFoundationofJiangxiProvinceofChina(2014ZBAB207022).