一種MIBS方案的分析與改進

摘要：魏松杰等人提出一種基于安全仲裁SEM（security mediator）的mIBS（identity based signature）方案，利用SEM節(jié)點實現(xiàn)用戶身份實時撤銷。mIBS方案中，SEM持有部分用戶私鑰，與簽名者共同完成簽名。對mIBS方案進行了安全性分析，發(fā)現(xiàn)該方案存在嚴重安全缺陷，并給出一個具體的攻擊實例。在攻擊實例中，簽名者通過與SEM的一次正常簽名交互，竊取SEM持有的部分私鑰，進而繞開SEM單獨實施簽名，使得SEM失效。提出一種改進的mIBS方案（記為mIBSG），對SEM持有的部分私鑰增加了隨機性保護。進一步，建立了mIBS方案安全模型mEUF-CMIA（existential unforgeability under adaptive chosen message and identity attacks），重點討論了其敵手模型。除傳統(tǒng)IBS敵手外，mEUF-CMIA模型定義第二種類型敵手模擬一個惡意但合法的簽名者，通過訪問隨機預言機，在沒有SEM參與的情況下獨立產(chǎn)生簽名。在mEUF-CMIA模型下，mIBSG方案的不可偽造性被歸約為求解循環(huán)群上的CDH問題。對比分析表明，mIBSG方案以較小的計算代價實現(xiàn)了可證明安全性。mIBSG方案可用于構建基于IBC的跨域認證系統(tǒng)。

關鍵詞：基于身份密碼學； 數(shù)字簽名； 計算Diffie-Hellman問題； 隨機預言機模型

中圖分類號：TP309文獻標志碼：A文章編號：1001-3695（2022）10-040-3136-05

doi： 10.19734/j.issn.1001-3695.2022.03.0130

Analysis and improvement of mIBS scheme

Chen Ming， Leng Jianhua

（School of Mathematics amp; Computer Science， Yichun University， Yichun Jiangxi 336000， China）

Abstract：

Wei Songjie et al. proposed an identity-based signature scheme （mIBS）， and used a security mediator （SEM） node to realize real-time revocation of entity identity in the mIBS scheme. The SEM held a part of the signature key， and gene-rated a signature by working collaboratively with a signer. This paper analyzed the security of the mIBS scheme， found it had serious security flaws， and presented a specific attack instance. In the attack instance， a signer could stole the key held by the SEM through once normal signature interaction with a SEM， and then bypassed the SEM to implement a signature independently. This paper proposed an improved signature scheme （mIBSG）. The mIBSG scheme remedied the security flaws of the original scheme by randomizing the private key held by the SEM. Further， this paper established a security model for mIBS scheme， named mEUF-CMIA， and defined a new type of adversary that simulated malicious but legitimate signers. The new adversary had the power to generate a forged signature independently through asking random oracles. Based on the new security model， this paper deduced the unforgeability of the mIBSG scheme as solving the CDH problem on a cyclic group. Comparative analysis show that the mIBSG scheme achieves provable security with a small calculate efficiency loss. The mIBSG scheme can be used to build an IBC-based cross-domain authentication system.

Key words：identity based cryptography; digital signature; computational Diffie-Hellman problem; random oracle model

0引言

基于身份密碼學［1］ （identity based cryptography，IBC）是由Shamir在CRYPTO’84會議上首次提出。IBC系統(tǒng)將用戶標識作為用戶公鑰，用戶私鑰由KGC（key generation center）利用其主密鑰生成并與用戶標識關聯(lián)。IBC系統(tǒng)無須建立復雜的PKI （public key infrastructure），避免了公鑰證書管理的沉重負擔。直到2001年，Boneh等人［2］基于雙線性映射理論提出一種有效的IBE（identity-based encryption）方案。隨后，IBC的研究成為一個熱點。2007年，RFC 5091［3］草案將Boneh-Franklin［2］算法推薦為基于身份加密標準，標志著IBC體制的標準化工作正式開啟。2020年，隨著《信息安全技術SM9標識密碼算法第1部分：總則》［4］和《信息安全技術SM9標識密碼算法第2部分：算法》［5］獲得批準，SM9正式成為IBC算法國家標準，并逐步進入行業(yè)應用階段。

然而，IBC機制在擁有諸多優(yōu)點的同時，也存在密鑰托管、信任域網(wǎng)絡規(guī)模較小等缺點。部分研究提出無證書［6，7］或自證書［8，9］等方案以解決IBC中的密鑰托管問題；另一些研究則借鑒PKI、區(qū)塊鏈等技術和方法以擴大IBC域的網(wǎng)絡覆蓋范圍［10～12］。區(qū)塊鏈技術具有去中心化和數(shù)據(jù)不易被竄改等優(yōu)點，利用區(qū)塊鏈技術構建去中心化的信任域，可以確?？缬蛘J證模型內(nèi)第三方服務器的可信性。近來，多位研究者提出基于區(qū)塊鏈技術的跨域認證模型和方案。馬曉婷等人［11］基于國密SM9，采用區(qū)塊鏈技術構建了PKI 與 IBC 聯(lián)盟鏈模型，及其該模型下的跨域認證方案；黃穗等人［13］也提出了基于區(qū)塊鏈的跨域認證模型，通過智能合約在區(qū)塊鏈上構造布谷鳥過濾器，解決大規(guī)模證書查詢請求的性能問題；魏欣等人［14］結合區(qū)塊鏈與邊緣計算思想，構建了一種適用于物聯(lián)網(wǎng)的跨域認證架構，通過引入邊緣網(wǎng)關屏蔽物聯(lián)網(wǎng)的底層異構性，增強節(jié)點隱私保護；張亞兵等人［15］提出多層區(qū)塊鏈的跨域認證方案，引入委托權益證明來評估節(jié)點的可信度，解決跨域訪問時存在的多個管理域相互信任問題；魏松杰等人［12］提出一種基于IBC和區(qū)塊鏈的跨域認證協(xié)議，定義了基于仲裁的IBC域結構，并提出基于仲裁的身份簽名mIBS和認證方案。在基本IBC系統(tǒng)基礎上，mIBS方案中引入安全仲裁SEM （security mediator）具體實施對用戶標識和密鑰的撤銷與核驗。但是，魏松杰等人［12］對mIBS方案的安全性分析比較簡單，沒有定義合理的安全模型，存在嚴重的安全缺陷。

本文的主要工作包括三個方面：a）對魏松杰等人［12］提出的mIBS方案進行了全面的安全性分析。與傳統(tǒng)的基于身份簽名方案不同，mIBS方案存在兩類敵手，除傳統(tǒng)敵手外，一個惡意的簽名者也能對算法形成攻擊，本文給出了一個針對mIBS方案的攻擊實例，簽名者通過與SEM的一次正常交互，獲取了SEM持有的部分私鑰，進而可以繞開SEM，實施獨立的簽名認證；b）提出了改進的mIBS方案，記為mIBSG方案，改進方案主要針對mIBS方案的缺陷進行了算法增強；c）以EUF-CMIA （existential unforgeability under adaptive chosen message and identity attacks）模型［16］為基礎，定義了mIBS方案的安全模型，對兩類敵手的行為進行了形式化定義。然后，采用新的模型對mIBSG方案進行了安全歸約，將mIBSG方案的安全性歸約為求解定義在循環(huán)群上的CDH（computational Diffie-Hellman）問題。對比分析表明，改進方案以較小的計算代價實現(xiàn)了方案的可證明安全性。

1背景知識

本章簡要介紹相關的數(shù)學背景知識，詳細內(nèi)容可以參考文獻［17］。

1）雙線性映射給定安全參數(shù)λ，初始化產(chǎn)生階為大素數(shù)pgt;p（2λ）的循環(huán)群（G1，+）和（G2，×），令P為G1的生成元，如果給定的映射e： G1×G1→G2滿足下列性質(zhì)，則 e是從G1到G2的一個雙線性映射。

a）雙線性。給定U，V∈G1和任意的a，b∈Euclid ExtrabBpp，有e（Ua，Vb）=e（U，V）ab。

b）非退化性。e（P，P）≠1。

c）可計算性。給定U，V∈G1，能有效計算e（U，V）。

2）CDH問題對于任意未知的a，b∈Euclid ExtrabBpp，給定P，aP，bP∈G1，求解abP。

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

本文研究的算法以CDH假設為基礎。

2mIBS方案分析

本章首先簡要回顧文獻［12］提出的mIBS方案，然后對其安全性進行分析，提出有效的攻擊實例。

2.1mIBS方案介紹

文獻［12］提出一種基于IBC和區(qū)塊鏈的跨域認證協(xié)議，并且提出一種mIBS方案用于在跨域認證中對信息服務實體ISE進行認證。為了解決基于身份密碼系統(tǒng)中對實體身份的撤銷等有效管理，在mIBS方案中引入安全仲裁，其系統(tǒng)框架如圖1所示。

在圖1所示的IBC系統(tǒng)中，密鑰生成中心KGC為用戶生成兩部分的私鑰，其中一部分發(fā)回給用戶，而另一部分私鑰發(fā)送給SEM。當用戶需要進行簽名的時候，首先向SEM申請簽名信令，然后根據(jù)SEM返回的簽名信令生成完整的簽名。具體步驟簡單描述如下：

Setup。給定系統(tǒng)參數(shù)（λ，p，P，G1，G2，e）如第1章所述，然后選擇密碼哈希函數(shù)H1：{0，1}→G1和H2：{0，1}×G2→Euclid ExtrabBpp，其中：G1和G2分別表示G1/{0}和G2/{1}。KGC隨機選擇s∈［1，p－1］作為系統(tǒng)主密鑰，計算Ppub=［s］P∈G1作為系統(tǒng)主公鑰，其中，［s］表示取整運算。KGC秘密保存系統(tǒng)主密鑰s，并公開系統(tǒng)參數(shù)pp=（λ，p，P，G1，G2，e，Ppub，H1，H2）。

KeyGen。用戶提交身份標識ID∈{0，1}，KGC首先計算PID=H1（ID）∈G1，dID=［s］PID∈G1，然后隨機選擇sID∈［1，p－1］并計算duserID=［sID］PID，dSEMID=dID－duserID=［s－sID］PID。KGC將duserID通過安全信道發(fā)送給用戶，將dSEMID通過安全信道發(fā)送給SEM。

Sign。按如下步驟計算消息簽名：

a）給定消息m∈{0，1}，用戶隨機選擇P1∈G1和k∈Euclid ExtrabBpp，計算q=e（kP1，P），g=H2（m，q）和Suser=kP1+gduserID，向SEM發(fā)送簽名信令請求（ID，q，g，Suser）。

b）SEM收到（ID，q，g，Suser）后，首先檢索用戶ID，若該身份已被撤銷則停止，否則計算SSEM=gdSEMID和Sm=Suser+SSEM，然后計算PID=H1（ID）和q′=e（Sm，P）·e（PID，－Ppub）g；判斷q′=q是否成立，若成立則發(fā)送SSEM給用戶。

c）用戶收到SSEM后，按b）的方式計算Sm和q′，若q′=q成立則輸出簽名（ID，m，g，Sm），否則重新申請簽名信令。

Verify。對簽名（ID，m，g，Sm）的驗證。首先按照Sign算法中b）的方式計算q′，然后計算g′=H2（m，q′），如果g′=g成立，則接受簽名。

2.2mIBS方案安全性分析

文獻［12］對mIBS方案進行了簡單的安全性分析，沒有建立完整的安全模型。由于mIBS方案中引入SEM實體，并且將用戶的私鑰分成了兩個部分，所以，針對IBS方案的EUF-CMIA模型［16］在本方案中不完全適用。本節(jié)將提出一種針對mIBS方案的新攻擊方法。

首先，原方案中存在一定的計算錯誤概率。具體來說，在簽名驗證計算式gduserID+gdSEMID=g（［sID］+［s－sID］）PID中，等式（［sID］+［s－sID］）=［s］并不一定成立。這會使得用戶的私鑰無效。

由于真實密碼算法的密鑰非常大，這里以小的模數(shù)p=23來舉例說明，即：s，sID∈［1，22］。

根據(jù)Setup和KeyGen算法，假設KGC隨機選擇s=10.3，sID=5.7，以上下取整為例，則［s］=［10.3］=10，［sID］=［5.7］=6，［s-sID］= ［10.3-5.7］=［4.6］=5，那么：（［sID］+［s-sID］） =11≠［s］。如果采用上取整或下取整也存在類似情況。簡單估算，上述錯誤概率接近1/2。一種改進方法是：在KeyGen算法中，對（［sID］+［s－sID］）=［s］進行驗算，如果等式成立則輸出私鑰，如果不成立，則重新選擇私鑰，使得等式成立。更一般的解決方案是：主密鑰s和用戶秘密sID從Euclid ExtrabBpp中隨機選擇。

另外，文獻［12］將對SSEM=g（s－sID）PID的攻擊歸約為求解離散對數(shù)問題，即求解（s－sID）。這一歸約路徑是錯誤的，因為SEM持有的部分私鑰是（s－sID）PID∈G*1，而不是（s－sID）。所以，攻擊者只需要獲得（s－sID）PID就可以偽造任何的簽名信令S′SEM=g′（s－sID）PID，使得g′≠g且S′SEM≠SSEM。進而，簽名者可以繞開SEM，實施獨立的簽名，使得SEM無效，具體簽名過程簡單描述如下。這里忽略上述計算錯誤，即假定用戶的私鑰是有效的，滿足等式（［sID］+［s－sID］）=［s］成立的條件。

a）簽名者從SEM收到一個有效的SSEM=g（s－sID）PID后，首先求g關于mod p的乘法逆元g－1∈Euclid ExtrabBpp，即g－1g≡1mod p。由于p為素數(shù)，所以一定存在g－1∈Euclid ExtrabBpp，且多項式時間可計算。然后，計算dSEMID=g－1SSEM=g－1g（s－sID）PID=（s－sID）PID。注意，為了描述簡潔，在非必要的場景下，文中關于循環(huán)群上的運算表達式省略了mod p運算。

b）給定消息m′∈{0，1}，簽名者隨機選擇P′1∈G1和k′∈Euclid ExtrabBpp，計算q′=e（k′P′1，P），g′=H2（m′，q′）和S′user=k′P′1+g′duserID，然后計算S′SEM=g′dSEMID和S′m=S′user+S′SEM，輸出簽名（ID，q′，g′，S′m）。

可以驗證：

e（S′m，P）×e（PID，－Ppub）g′=

e（k′P′1+g′duserID+g′dSEMID，P）×e（PID，－Ppub）g′=（1）

e（k′P′1，P）×e（［s］PID，P）g′×e（PID，［s］P）－g′=e（k′P′1，P）=q′

可見，由于簽名者獲得了SEM持有的部分私鑰，可以獨立實施對任意消息的簽名，攻擊成立。

3改進的mIBS方案及其安全性分析

本章首先對原有mIBS方案進行改進，記為mIBSG，然后討論其安全模型，并對改進方案進行安全性分析。

3.1mIBS方案改進

考慮2.2節(jié)中對mIBS方案的偽造攻擊。攻擊形成的關鍵原因是在SEM簽署的簽名信令SSEM=gdSEMID中缺少對部分私鑰dSEMID的隨機性保護，導致惡意的簽名者通過一次確定的簽名過程直接恢復出SEM持有的部分私鑰dSEMID。因此，本文的改進方案在原方案的基礎上，在Sign算法中添加對dSEMID的隨機性保護，具體描述如下。

mIBSG方案不改變原有方案的總體框架，系統(tǒng)建立（Setup）和密鑰生成（KeyGen）與原方案基本相同。在系統(tǒng)公開參數(shù)中增加密碼哈希函數(shù)H3：Euclid ExtrabBpp×G2→Euclid ExtrabBpp；密鑰生成階段要求KGC檢驗等式（［sID］+［s－sID］）=［s］是否成立，如果不成立則重新生成密鑰，直到等式成立。簽名和簽名簽證過程如下。

Sign。按如下步驟計算消息簽名：

a）給定消息m∈{0，1}，用戶隨機選擇P1∈G1和k∈Euclid ExtrabBpp，計算q1=e（kP1，P），g=H2（m，q1）和Suser=kP1+gduserID，向SEM發(fā)送簽名信令請求（ID，q1，g，Suser）。

b）SEM收到（ID，q1，g，Suser）后，首先檢索用戶ID，若該身份已被撤銷則停止，否則隨機選擇P2∈G1，計算q2=e（P2，P），r=H3（g，q2），SSEM=r（P2+gdSEMID）和Sm=rSuser+SSEM，然后計算PID=H1（ID），并驗證等式（q1×q2）r=e（Sm，P）×e（PID，Ppub）－rg是否成立，若成立則發(fā)送（q2，SSEM）給用戶。

c）用戶收到（q2，SSEM）后，計算r=H3（g，q2），以及完整簽名Sm=rSuser+SSEM，驗證等式（q1×q2）r=e（Sm，P）×e（PID，Ppub）－rg是否成立，若成立則輸出簽名（ID，m，q1，q2，Sm），否則重新申請簽名信令。

Verify。對簽名（ID，m，q1，q2，Sm）的驗證。簽名驗證者首先計算g=H2（m，q1），r=H3（g，q2）和PID=H1（ID），然后驗證等式（q1×q2）r=e（Sm，P）×e（PID，Ppub）－rg是否成立，若成立則接受簽名。

可以驗證：

e（Sm，P）×e（PID，Ppub）－rg=

e（rkP1+rgduserID+rP2+rgdSEMID，P）×e（PID，Ppub）－rg=

e（rkP1，P）×e（rP2，P）×e（duserID+dSEMID，P）rg×e（PID，Ppub）－rg=

e（kP1，P）r×e（P2，P）r×e（［s］PID，P）rg×e（PID，［s］P）－rg=

（q1×q2）r（2）

由式（2）可得，mIBSG方案具有可驗證正確性。

mIBSG方案中，在Sign算法的步驟b），增加了隨機選擇的P2∈G1，并且利用r=H3（g，q2）將g與q2=e（P2，P）進行了綁定。由于P2是隨機的，所以從任何敵手的視角來看，q2=e（P2，P）也是隨機的。本質(zhì)上，簽名信令（q2，SSEM）是SEM采用部分私鑰dSEMID對簽名請求消息g=H2（m，q1）的簽名，主要目的是防止簽名者任意替換消息g，確保了簽名者每次簽名都必須請求SEM產(chǎn)生一個新的簽名信令。同時，由于存在新鮮且隨機的P2∈G1，任何敵手想要從SSEM=r（P2+gdSEMID）中恢復出部分私鑰dSEMID，都面臨求解CDH問題。詳細的安全性分析請見本文3.2節(jié)。

3.2mIBSG方案安全性分析

本節(jié)首先建立mIBS方案安全模型，然后對mIBSG方案進行安全性歸約。

3.2.1mIBS安全模型

下面首先回顧基本的EUF-CMIA模型［16］。

定義敵手Euclid Math OneAAp與模擬器Euclid Math OneBAp之間的EUF-CMIA游戲如下：

a）系統(tǒng)建立。Euclid Math OneBAp執(zhí)行Setup算法，公開系統(tǒng)公共參數(shù)pp，創(chuàng)建N個用戶的身份集合ID={ID1，…，IDN}，并且隨機選擇用于挑戰(zhàn)的用戶身份ID∈ID。

b）詢問。Euclid Math OneAAp自適應地執(zhí)行多項式時間有界次的詢問。

（a）KeyGen詢問。Euclid Math OneAAp提交用戶身份ID，Euclid Math OneBAp返回其私鑰skID。這里要求Euclid Math OneAAp不能詢問ID的私鑰。

（b）Sign詢問。Euclid Math OneAAp提交（ID，m），Euclid Math OneBAp返回簽名σ給Euclid Math OneAAp。

c）偽造。詢問階段結束以后，Euclid Math OneAAp輸出偽造簽名（ID*，m*，σ*）。

定義1對IBS方案=（Setup，KeyGen，Sign，Verify），敵手Euclid Math OneAAp在選擇身份攻擊下的優(yōu)勢定義為

AdvEUF-CMIAEuclid Math OneAAp=

Prpp←Setup（1λ）（ID，sk）←KeyGen（pp，ID）（m，σ）←AΟSign（·）（pp）：mm∧Verify（ID，m，σ）=1

其中：ΟSign（·）是一個簽名預言機，模擬Sign詢問；集合m存儲已完成簽名詢問的消息m及其對應的簽名應答σ。如果對于任意多項式時間敵手Euclid Math OneAAp，有AdvEUF-CMIAEuclid Math OneAAp=negl（λ）成立，則稱在選擇身份攻擊下具有不可偽造性。

引理1令是一種數(shù)字簽名機制，其安全參數(shù)為λ。Euclid Math OneAAp是一個概率多項式時間圖靈機，其輸入為公開參數(shù)。Euclid Math OneAAp可以自適應地完成隨機預言機（random oracle，RO）詢問，假設Euclid Math OneAAp以概率ε（λ）輸出一個有效的簽名σ=（ID，m，q1，q2，r，g，Sm），則存在一個算法Euclid Math OneAAp′利用Euclid Math OneAAp，在多項式時間內(nèi)產(chǎn)生兩個有效的簽名σ=（ID，m，q1，q2，r，g，Sm）和σ′=（ID，m，q1，q2，r′，g′，S′m），使得r≠r′∧g≠g′成立。

引理1是數(shù)字簽名安全性證明中廣泛采用的分叉引理（forking lemma），由Pointcheva等人［18］ 首次引入。本文安全模型也引用這一引理。

根據(jù)2.2節(jié)的分析，mIBS與基本IBS方案存在較大差異，同時存在兩類敵手。第一類是傳統(tǒng)的IBS敵手，其攻擊目標是偽造完整的簽名；第二類敵手是惡意的簽名者，其攻擊目標是偽造簽名信令。因此，對mIBS方案的分析模型應對基本的EUF-CMIA模型進行調(diào)整，本文定義為mEUF-CMIA模型。

mEUF-CMIA模型的主要變化在于刻畫敵手的能力。對于第一類敵手，限制其詢問ID的完整私鑰；對于第二類敵手，允許其詢問ID的部分私鑰（duserID），而不允許其詢問ID的另一部分私鑰（dSEMID）。此外，針對兩類敵手提交的Sign詢問，模擬器Euclid Math OneBAp應答的方式也有所區(qū)別。具體內(nèi)容見3.2.2節(jié)。

3.2.2mIBSG方案安全性證明

本節(jié)對mIBSG方案進行安全性歸約，基于CDH假設，證明其在選擇身份和選擇消息攻擊下具有不可偽造性。

首先對歸約過程進行簡單的非形式化分析。給定CDH實例（P，aP，bP），令KGC的主公鑰為aP，令H1（ID）=bP（ID為挑戰(zhàn)用戶身份），則ID的私鑰為dID=duserID+dSEMID=［s］PID=abP。在mEUF-CMIA游戲中，KGC的主密鑰［s］=a是未知的，因此ID的完整私鑰dID包含了一個CDH問題的實例。通過游戲模擬，模擬器Euclid Math OneBAp利用Euclid Math OneAAp輸出ID簽名來求解該CDH問題實例。如果CDH假設成立，那么Euclid Math OneBAp成功的優(yōu)勢是可以忽略的，從而反證Euclid Math OneAAp成功偽造ID簽名的優(yōu)勢也是可以忽略的。

在基于隨機預言機的安全模型中，哈希函數(shù)通常被替換為哈希詢問，稱為哈希預言機（hash oracle）。

定理1如果CDH假設成立，那么本文mIBSG方案滿足EUF-CMIA安全。

證明假設存在多項式時間敵手Euclid Math OneAAp以不可忽略的優(yōu)勢攻破mIBSG方案，本文將構建一個算法Euclid Math OneBAp利用Euclid Math OneAAp，在多項式時間內(nèi)解決CDH問題。給定CDH實例（P，aP，bP），下面模擬Euclid Math OneBAp與Euclid Math OneAAp的mSID-EUF-CMA游戲。

a）系統(tǒng)建立。Euclid Math OneBAp運行Setup算法，產(chǎn)生系統(tǒng)公開參數(shù)pp=（λ，p，P，G1，G2，e，Ppub），創(chuàng)建N個用戶的身份集合ID={ID1，…，IDN}，并將pp和ID發(fā)送給Euclid Math OneAAp。其中，Ppub=aP，即系統(tǒng)主密鑰s=a未知。Euclid Math OneBAp隨機選擇用于挑戰(zhàn)的用戶身份ID∈ID。注意，根據(jù)隨機預言機假設，模擬過程中，用哈希詢問（H1，H2，H3）替換哈希函數(shù)（H1，H2，H3）。

b）詢問。Euclid Math OneAAp自適應地執(zhí)行多項式時間有界次的詢問。Euclid Math OneBAp維護初始為空的列表（L1，L2，L3，Lk，m）。

（a）H1詢問。Euclid Math OneAAp提交H1（IDi）詢問。如果IDi在列表L1中存在，則直接返回Pi；否則，如果IDi∈ID∧IDi≠ID，Euclid Math OneBAp隨機選擇ti∈Euclid ExtrabBpp，計算Pi=tiP，將（IDi，ti，Pi）插入集合L1；如果IDi=ID，則令Pi=bP，將（ID，⊥，Pi）插入集合L1。最后將Pi返回給Euclid Math OneAAp。

（b）H2詢問。Euclid Math OneAAp提交H2（mi，q1，i）詢問。如果（mi，q1，i）在列表L2中存在，則Euclid Math OneBAp直接返回對應的gi；否則，Euclid Math OneBAp隨機選擇gi∈Euclid ExtrabBpp，并返回給Euclid Math OneAAp，然后將（mi，q1，i，gi）插入L2。

（c）H3詢問。Euclid Math OneAAp提交H3（gi，q2，i）詢問。如果gi在列表L2中不存在，則返回⊥；否則，如果（gi，q2，i）在列表L3中存在，則Euclid Math OneBAp直接返回對應的ri；否則，Euclid Math OneBAp隨機選擇ri∈Euclid ExtrabBpp，并返回給Euclid Math OneAAp，然后將（gi，q2，i，ri）插入L3。

c）KeyGen詢問。Euclid Math OneAAp提交身份IDi。

（a）如果IDi∈ID∧IDi≠ID，且（IDi，duseri，dSEMi）在Lk中存在，Euclid Math OneBAp直接返回（duseri，dSEMi）給Euclid Math OneAAp；否則，Euclid Math OneBAp通過H1詢問得到（IDi，ti，Pi），隨機選擇si∈［1，p－1］，計算duseri=［si］Pi，dSEMi=tiPpub-［si］Pi，將（duseri，dSEMi）返回給Euclid Math OneAAp，并將（IDi，duseri，dSEMi）插入Lk?？梢则炞C：dSEMi=tiPpub－［si］Pi= （a－［si］）Pi。因此，從敵手的視角來看，KeyGen詢問輸出與真實密鑰生成算法輸出的密鑰同分布且不可區(qū)分。

（b）如果IDi=ID，Euclid Math OneBAp隨機選擇si∈［1，p－1］，令Pi=bP，計算duseri=［si］Pi，將（IDi，duseri，⊥）插入Lk。如果Euclid Math OneAAp是第一類敵手，則返回⊥；如果Euclid Math OneAAp是第二類敵手，則返回duseri給Euclid Math OneAAp。

d）Sign詢問。Euclid Math OneAAp提交Sign（IDi，mj）詢問。如果IDi的私鑰還未創(chuàng)建，則Euclid Math OneBAp首先按照KeyGen詢問的方法創(chuàng)建用戶私鑰。如果IDi∈ID∧IDi≠ID，Euclid Math OneBAp按照mIBSG方案的Sign算法計算并輸出簽名σj=（IDi，mj，q1，j，q2，j，Smj），然后將σj 插入m。如果IDi=ID，為了區(qū)分兩類敵手，本文分別構建兩種形式的Sign應答。

（a）如果Euclid Math OneAAp是第一類敵手。Euclid Math OneBAp隨機選擇P1，j∈G1和kj∈Euclid ExtrabBpp，計算q1，j=e（kjP1，j，P），通過H2（mj，q1，j）詢問獲得gj，然后計算Suser，j=kjP1，j+gjduseri，接著隨機選擇rj∈Euclid ExtrabBpp和SSEM，j∈G1，計算Sm，j=rjSuser，j+SSEM，j，令q2，j=e（Sm，j，P）r-1j×e（Pi，Ppub）-gj×q-11，j，然后將（gi，q2，i，ri）插入L3。最后，Euclid Math OneBAp將σj=（IDi，mj，q1，j，q2，j，Smj）插入m，并且返回簽名σj給Euclid Math OneAAp。

（b）如果Euclid Math OneAAp是第二類敵手。Euclid Math OneAAp提交簽名信令請求（IDi，q1，j，gj，Suser，j）。如果（q1，j，gj）在列表L2中不存在或不匹配，則Euclid Math OneBAp返回⊥；否則，Euclid Math OneBAp隨機選擇rj∈Euclid ExtrabBpp和SSEM，j∈G1，計算Sm，j=rjSuser，j+SSEM，j，令q2，j=e（Sm，j，P）r-1j×e（Pi，Ppub）－gj×q－11，j，然后將（gi，q2，i，ri）插入L3。最后，Euclid Math OneBAp將σj=（IDi，mj，q1，j，q2，j，Smj）插入m，并且返回簽名σj給Euclid Math OneAAp。

容易驗證，等式：（q1×q2）r=e（Sm，P）×e（Pi，Ppub）－rg成立。在真實簽名算法中，q2，j=e（P2，j，P）。其中，P2，j∈G1由SEM隨機選擇，且獨立于（兩類）敵手的視角，進而q2，j也獨立于敵手的視角。也就是說，從敵手的視角來看，Sign詢問的輸出與真實簽名算法的輸出同分布且不可區(qū)分。

c）偽造。詢問階段結束以后，Euclid Math OneAAp輸出偽造簽名σ= （ID，m，q1，q2，Sm）。

如果ID≠ID∨m∈m，Euclid Math OneBAp終止游戲，模擬失?。环駝t，Euclid Math OneBAp以（q1，q2）為索引查詢列表L2/L3取得（r，g），若驗證等式（q1×q2）r=e（Sm，P）×e（PID，Ppub）－rg成立，則Euclid Math OneAAp贏得游戲。如果（r，g）在L2/L3中不存在，則終止游戲，模擬失敗。也就是說，Euclid Math OneAAp必須通過哈希詢問取得（r，g），這就保證了計算順序q1→g，q2→r，從而使得敵手無法采用Sign詢問中的方法構造偽造簽名。在真實世界中，哈希預言機是不存在的，因此，Sign詢問中的簽名構造方法是無法實現(xiàn)的，這是隨機預言機模型與真實世界的主要區(qū)別。

如果游戲沒有終止，且Euclid Math OneAAp贏得游戲。根據(jù)分叉引理［18］，Euclid Math OneBAp可以構造算法Euclid Math OneAAp′，利用Euclid Math OneAAp產(chǎn)生另一有效簽名（ID，m，q1，q2，r′，g′，S′m），r≠r′∧g≠g′。可以驗證：

Sm=rkP1+rP2+rg（duserID+dSEMID）=

r（kP1+P2）+rg（abP）（3）

S′m=r′kP1+r′P2+r′g′（duserID+dSEMID）=

r′（kP1+P2）+r′g′（abP）（4）

根據(jù)式（3）（4），Euclid Math OneBAp計算：

abP=（g′-g*）-1（r′-1S′m-r*-1S*m）（5）

作為對CDH問題的回答。

令Euclid Math OneAAp贏得游戲的優(yōu)勢為AdvmSID-EUF-CMAEuclid Math OneAAp=ε，那么Euclid Math OneBAp贏得CDH挑戰(zhàn)的優(yōu)勢為：ε′=ε+negl（λ）。

根據(jù)CDH假設，如果Euclid Math OneBAp贏得CDH挑戰(zhàn)的優(yōu)勢ε′是可忽略的，那么Euclid Math OneAAp贏得游戲的優(yōu)勢也是可忽略的。

證畢。

4對比分析

在安全性方面，本文mIBSG方案實現(xiàn)了在隨機預言機模型下的可證明安全。mIBS方案［12］則存在安全缺陷，簽名者可以繞開SEM獨立實施簽名，違背了mIBS方案的設計初衷。

計算開銷方面，mIBSG方案與原方案的對比如表1所示。表中列舉了主要的計算開銷，其中，P表示雙線性對運算，H表示哈希運算，M表示群G1/G2上的乘法運算，A表示群G1/G2上的加法運算，E表示群G2上的指數(shù)運算。在群G1上和群G2上的乘法（加法）運算時間差別不大，因此合并計算。

從各類計算開銷來看，簽名者增加（2M+1E+1H3），SEM增加（1P+2M+1A+1E+1H2），驗證者則增加（1M+1E+1H3）。根據(jù)文獻［12］給出的實驗環(huán)境和實驗數(shù)據(jù)：一次雙線性對運算時間約等于1.112 ms，一次G1/G2上的乘法運算時間約等于0.407 ms，一次G1/G2上的加法運算時間約等于0.003 ms，一次G2上的指數(shù)運算時間約等于0.131 ms。而哈希函數(shù)的計算時間相較來說則更低，可以忽略不計。因此，從時間開銷上來說，增加較多的是SEM，總的計算時間約為5.232 ms，增加約2.06 ms。

5結束語

魏松杰等人［12］提出一種mIBS方案，引入安全仲裁SEM對IBC域中用戶身份進行撤銷管理和核驗。但是，分析發(fā)現(xiàn)，該方案存在嚴重安全缺陷，簽名者可利用與SEM的一次正常交互，獲取SEM持有的部分私鑰。本文提出改進的mIBSG方案，并建立了安全模型。新安全模型在傳統(tǒng)SID-EUF-CMA模型的基礎上定義了兩類敵手，分別模擬外部攻擊者和惡意的簽名者。在新的安全模型下，mIBSG方案的不可偽造性被歸約為求解循環(huán)群上的CDH問題，實現(xiàn)了可證明安全性。

總體來看，mIBS算法效率不具有比較優(yōu)勢，后續(xù)優(yōu)化研究可以從以下兩方面展開。第一，實際應用中，網(wǎng)絡延遲所消耗的時間遠遠大于節(jié)點計算時間，可以考慮降低每次簽名的平均網(wǎng)絡延遲，提高簽名方案的整體效率。在文獻［12］的跨域認證系統(tǒng)中，mIBS方案主要用于信息服務實體ISE的簽名認證。對ISE來說，短時間內(nèi)多次簽名是比較常見的，每一次簽名就申請一次簽名信令在實際應用中沒有必要，既增加了SEM的負載也增加了方案的總體網(wǎng)絡延遲。因此，在mIBSG方案的基礎上，研究實現(xiàn)多次簽名共享一個簽名信令機制，可以降低每次簽名的平均網(wǎng)絡延遲，降低SEM的總體負載，提高簽名的整體效率。第二，引入SEM進行身份實時撤銷開銷巨大，可以考慮采用自證書模式，借鑒PKI方案的思想，構建更加優(yōu)化的跨域認證結構模型。

參考文獻：

［1］Shamir A. Identity-based cryptosystems and signature schemes ［C］// Proc of the 4th Annual International Cryptology Conference. Berlin： Springer，1985： 47-53.

［2］Boneh D，F(xiàn)ranklin M. Identity-based encryption from the Weil pairing ［C］// Proc of the 21st Annual International Cryptology Conference. Berlin： Springer，2001： 213-229.

［3］Boyen X，Martin L. Identity-based cryptography standard （IBCS） #1： supersingular curve implementations of the BF and BB1 cryptosystems ［EB/OL］. （2007） ［2022-01-29］. http：//www.ietf.org/rfc/rfc5091.txt.

［4］全國信息安全標準化技術委員會. GB/T 38635.1—2020，信息安全技術SM9標識密碼算法第1部分： 總則 ［S］. 北京： 國家標準化管理委員會，2020.（ National Information Security Standardization Technical Committee. GB/T 38635.1—2020，Information security technology SM9 identification encryption algorithm part 1： general ［S］. Beijing： National Standardization Administration Committee，2020）.

［5］全國信息安全標準化技術委員會. GB/T 38635.2—2020，信息安全技術SM9標識密碼算法第2部分： 算法 ［S］. 北京： 國家標準化管理委員會，2020.（ National Information Security Standardization Technical Committee. GB/T 38635.2—2020，Information security technology SM9 identification encryption algorithm part 2： algorithm ［S］. Beijing： National Standardization Administration Committee，2020.）

［6］Sattam S A，Kenneth G P. Certificateless public key cryptography ［C］// Proc of the 9th International Conference on Theory and Application of Cryptology and Information Security. Berlin： Springer，2003： 452-473.

［7］唐衛(wèi)中，張大偉，佟暉. 基于SM2的無證書盲簽名方案 ［J］. 計算機應用研究，2022，39（2）： 552-556. （Tang Weizhong，Zhang Dawei，Tong Hui. A certificateless blind signature scheme based on SM2 ［J］. Application Research of Computers，2022，39（2）： 552-556.）

［8］曾萍，陳瑞利，方勇. 基于自認證公鑰的全分布式移動Ad hoc網(wǎng)絡密鑰管理方案 ［J］. 計算機應用研究，2008，25（6）： 1779-1782. （Zeng Ping，Chen Ruili，F(xiàn)ang Yong. A fully distributed mobile Ad hoc network key management scheme based on self-authenticating public key ［J］. Application Research of Computers，2008，25（6）： 1779-1782.）

［9］Zhang Qikun，Li Yongjiao，Zhang Quanxin，et al. A self-certified cross-cluster asymmetric group key agreement for wireless sensor networks ［J］. Chinese Journal of Electronics，2019，28（2）： 280-287.

［10］羅長遠，霍士偉，邢洪智. 普適環(huán)境中基于身份的跨域認證方案 ［J］. 通信學報，2011，32（9）： 111-115，122. （Luo Changyuan，Huo Shiwei，Xing Hongzhi. Identity-based cross-domain authentication scheme in a universal environment ［J］. Journal on Communications，2011，32（9）： 111-115，122.）

［11］馬曉婷，馬文平，劉小雪. 基于區(qū)塊鏈技術的跨域認證方案 ［J］. 電子學報，2018，46（11）： 2571-2579. （Ma Xiaoting，Ma Wenping，Liu Xiaoxue. Cross-domain authentication scheme based on blockchain technology ［J］. Acta Electronica Sinica，2018，46（11）： 2571-2579.）

［12］魏松杰，李莎莎，王佳賀. 基于身份密碼系統(tǒng)和區(qū)塊鏈的跨域認證協(xié)議 ［J］. 計算機學報，2021，44（5）： 908-920. （Wei Songjie，Li Shasha，Wang Jiahe. A cross-domain authentication protocol by identity-based cryptography on consortium blockchain ［J］. Chinese Journal of Computers，2021，44（5）： 908-920.）

［13］黃穗，李健，范冰冰. IABC： 一種基于區(qū)塊鏈和布谷鳥過濾器的跨域認證方法 ［J］. 小型微型計算機系統(tǒng)，2020，41（12）： 2620-2625. （Huang Sui，Li Jian，F(xiàn)an Bingbing. IABC： a cross-domain authentication method based on blockchain and cuckoo filter ［J］. Journal of Chinese Computer Systems，2020，41（12）： 2620-2625.）

［14］魏欣，王心妍，于卓，等. 基于聯(lián)盟鏈的物聯(lián)網(wǎng)跨域認證 ［J］. 軟件學報，2021，32（8）： 2613-2628. （Wei Xin，Wang Xinyan，Yu Zuo，et al. Cross domain authentication for IoT based on permissioned blockchain ［J］. Journal of Software，2021，32（8）： 2613-2628.）

［15］張亞兵，邢鑌. 基于多層區(qū)塊鏈的跨域認證方案 ［J］. 計算機應用研究，2021，38（6）： 1637-1641. （Zhang Yabing，Xing Bin. Cross domain authentication scheme based on multilayer blockchain ［J］. Application Research of Computers，2021，38（6）： 1637-1641.）

［16］Cha J C，Cheon J H. An identity-based signature from gap Diffie-Hellman groups ［C］// Proc of the 6th International Workshop on Theory and Practice in Public Key Cryptography. Berlin： Springer，2003： 18-30.

［17］Shacham H. New Paradigms in signature schemes ［D］. Stanford，CA： Stanford University，2005.

［18］Pointcheval D，Stern J. Security arguments for digital signatures and blind signatures ［J］. Journal of Cryptology，2000，13（3）： 361-396.

收稿日期：2022-03-09；修回日期：2022-05-13基金項目：國家自然科學基金資助項目（61662083）

作者簡介：陳明（1978-），男，重慶北碚人，副教授，博士，主要研究方向為密碼學、安全協(xié)議、教育技術（chenming9824@aliyun.com）；冷建華（1978-），男，江西上高人，副教授，碩士，主要研究方向為信息安全、教育技術.