高效的可撤銷SM9標(biāo)識(shí)簽名算法

收稿日期：2022-02-18；修回日期：2022-03-31" 基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61872292）；青海省重點(diǎn)研發(fā)計(jì)劃資助項(xiàng)目（2020-SF-139）；青海省基礎(chǔ)研究計(jì)劃資助項(xiàng)目（2020-ZJ-701）

作者簡(jiǎn)介：張博鑫（1996-），男，陜西咸陽(yáng)人，碩士，主要研究方向?yàn)楣€密碼學(xué)；耿生玲（1970-），女（藏族），青海都蘭人，教授，副院長(zhǎng)，博士，主要研究方向?yàn)槲锫?lián)網(wǎng)、大數(shù)據(jù)、數(shù)據(jù)挖掘；秦寶東（1982-），男（通信作者），江蘇徐州人，教授，碩導(dǎo)，博士，主要研究方向?yàn)楣€密碼學(xué)基礎(chǔ)理論及應(yīng)用（qinbaodong@xupt.edu.cn）．

摘 要：SM9-IBS是我國(guó)在2016年公布的一種標(biāo)識(shí)簽名算法行業(yè)標(biāo)準(zhǔn)。標(biāo)識(shí)簽名算法雖然降低了系統(tǒng)管理用戶公鑰的復(fù)雜性，但是卻存在密鑰撤銷的難題，此外SM9的特殊結(jié)構(gòu)使得已有技術(shù)無(wú)法完全適用。為此，提出了一種可撤銷SM9標(biāo)識(shí)簽名算法，可快速實(shí)現(xiàn)對(duì)用戶簽名權(quán)限的撤銷和更新操作。該算法引入一棵完全子樹(shù)，密鑰中心借助該樹(shù)為每個(gè)合法用戶生成臨時(shí)簽名密鑰，只有使用該密鑰生成的簽名才可以通過(guò)簽名驗(yàn)證。在安全性方面，該算法在隨機(jī)預(yù)言機(jī)模型中被證明在適應(yīng)性選擇消息和標(biāo)識(shí)攻擊模型下滿足存在性不可偽造；在效率方面，該方案在密鑰更新階段當(dāng)系統(tǒng)用戶數(shù)量較大、被撤銷用戶數(shù)量較少時(shí)，密鑰中心更新用戶簽名密鑰的時(shí)間開(kāi)銷遠(yuǎn)小于Boneh等人的更新技術(shù)。

關(guān)鍵詞：標(biāo)識(shí)密碼系統(tǒng)；SM9簽名算法；密鑰撤銷；完全子樹(shù)

中圖分類號(hào)：TP393.04"" 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2022）09-043-2837-06

doi：10.19734/j.issn.1001-3695.2022.02.0073

Efficient revocable SM9 identity-based signature algorithm

Zhang Boxin1，Geng Shengling2，Qin Baodong1

（1.School of Cyberspace Security，Xi’an University of Posts amp; Telecommunications，Xi’an 710121，China；2.College of Computer，Qinghai Normal University，Xining 810008，China）

Abstract：SM9-IBS is an industry standard for identity-based signature（IBS） algorithms issued by China in 2016.Although the IBS algorithms can be reduce the complexity of management of user keys，they have the problem of key revocation.In addition，the existing technologies aren’t fully applicable to SM9-IBS due to its special algebraic structure of users’ secret keys.Therefore，this paper proposed an efficient revocable SM9 identity-based signature（shorted as CS-SM9-RIBS） algorithm，which could quickly revoke and update the user’s signature authority.This algorithm introduced a complete subtree，which was used by the key generation center（KGC） generated temporary signature keys for each legitimate user，so that only the signature ge-nerated by this key could pass the signature verification.In terms of security，the new algorithm was proven to be existentially unforgeable under adaptive chosen message and identity attacks in the random oracle model.In terms of efficiency，when the number of users in the system was large and the number of revoked users was small in the key update stage，the time cost of the KGC to update the user’s signature key was much smaller than Boneh et al ’s update technology.

Key words：identity-based cryptosystem；SM9 signature algorithm；key revocation；complete subtree

0 引言

1984年，Shamir［1］首次提出了標(biāo)識(shí)密碼（identity-based cryptosystem）的概念，包括標(biāo)識(shí)加密算法（identity-based encryption，IBE）和標(biāo)識(shí)簽名算法（identity-based signature，IBS）。它可以采用用戶的唯一標(biāo)識(shí)，如身份證號(hào)、手機(jī)號(hào)、電子郵件地址等作為用戶公鑰，由密鑰中心根據(jù)系統(tǒng)密鑰以及用戶標(biāo)識(shí)生成相應(yīng)的用戶私鑰。與傳統(tǒng)公鑰密碼算法相比，標(biāo)識(shí)密碼算法簡(jiǎn)化了PKI/CA應(yīng)用中的證書分發(fā)和公鑰交換過(guò)程，降低了密鑰和證書管理的復(fù)雜性。2000年，Sakai等人［2］發(fā)表了一篇使用橢圓曲線對(duì)提出的基于身份的密鑰共享方案。直到2001年，Boneh和Cocks等人［3，4］才分別給出首個(gè)標(biāo)識(shí)加密算法的構(gòu)造。隨后，美國(guó)、英國(guó)和日本開(kāi)始設(shè)計(jì)相應(yīng)的算法［5～8］。

中國(guó)國(guó)家密碼學(xué)管理局于2008年正式發(fā)布了SM9［9］商用標(biāo)識(shí)密碼算法，并在2016年3月28日發(fā)布并實(shí)施了SM9標(biāo)識(shí)密碼算法標(biāo)準(zhǔn)。SM9系列算法包括密鑰交換、簽名以及加密三種，其中簽名算法與加密算法分別已于2018年11月和2021年2月被納入國(guó)際標(biāo)準(zhǔn)［10，11］。SM9因其結(jié)構(gòu)簡(jiǎn)單、功耗低等優(yōu)點(diǎn)，在密碼技術(shù)和網(wǎng)絡(luò)空間安全領(lǐng)域愈來(lái)愈受到廣泛的應(yīng)用與發(fā)展［12～16］。雖然標(biāo)識(shí)密碼體系簡(jiǎn)化了用戶公鑰管理環(huán)節(jié)，但是包括SM9在內(nèi)的標(biāo)識(shí)密碼算法并沒(méi)有提供用戶密鑰撤銷機(jī)制，一旦用戶私鑰泄露，用戶標(biāo)識(shí)就需作廢無(wú)法繼續(xù)使用，否則攻擊者就會(huì)使用泄露的密鑰訪問(wèn)用戶所有的密文或者代表用戶簽署任何文獻(xiàn)。針對(duì)標(biāo)識(shí)密碼系統(tǒng)的密鑰泄露問(wèn)題，Boneh等人［3］提出利用身份標(biāo)識(shí)級(jí)聯(lián)時(shí)間戳作為用戶臨時(shí)身份，如ID‖2022.01，密鑰中心定期將相應(yīng)的密鑰發(fā)送給未被撤銷的用戶。該方法具有通用性，適用于任意標(biāo)識(shí)密碼系統(tǒng)，但是密鑰中心更新密鑰的復(fù)雜度與系統(tǒng)用戶數(shù)量呈線性增長(zhǎng)，為O（N-R），其中N是系統(tǒng)用戶數(shù)量，R是被撤銷用戶數(shù)量。此外，該方法需要安全信道傳輸用戶的密鑰。Boldyreva等人［17］提出第一個(gè)高效的可撤銷IBE方案，該方案為每個(gè)用戶預(yù)分配一組長(zhǎng)期密鑰并利用完全子樹(shù)覆蓋技術(shù)實(shí)現(xiàn)用戶臨時(shí)密鑰的安全更新，從而使密鑰更新的復(fù)雜度從線性降至O（R log（N/R）），且無(wú)須安全信道傳輸更新密鑰。近年來(lái)，一些學(xué)者從適應(yīng)性身份安全性［18］、臨時(shí)密鑰泄露攻擊［19］、更新密鑰的復(fù)雜性［20］、抗量子計(jì)算攻擊［21，22］、云計(jì)算輔助撤銷［23～25］等方面，提出了一系列可撤銷的標(biāo)識(shí)密碼方案。這些方法主要利用完全子樹(shù)（complete subtree，CS）覆蓋技術(shù)或子集合差分（subset difference，SD）技術(shù)確定更新節(jié)點(diǎn)數(shù)量，從而降低更新密鑰的復(fù)雜性。同時(shí)，利用主密鑰與用戶密鑰之間存在的同態(tài)性質(zhì)，計(jì)算各個(gè)更新節(jié)點(diǎn)的更新密鑰。然而，SM9“指數(shù)倒置”的特殊代數(shù)結(jié)構(gòu)，使得構(gòu)造上述方法無(wú)法直接用于SM9標(biāo)識(shí)密碼系統(tǒng)。2019年，Ma等人［26］利用完全子樹(shù)覆蓋技術(shù)提出一種構(gòu)造可撤銷標(biāo)識(shí)加密方案的通用方法。與文獻(xiàn)［3］中的通用方法相比，該方法將更新密鑰的復(fù)雜度從O（N-R）降至O（R log（N/R）），但是密文長(zhǎng)度從O（1）擴(kuò)展到了O（log N），或者依賴基于身份的廣播加密。將該方法直接應(yīng)用到SM9上，密文數(shù)量至少為O（log N），效率較低。截至目前，筆者還沒(méi)有發(fā)現(xiàn)針對(duì)SM9簽名算法的高效密鑰撤銷機(jī)制的研究。

針對(duì)標(biāo)識(shí)加密算法，Ma等人［26］提出的更新密鑰的主要思想是：通過(guò)引入一棵完全子樹(shù)，將用戶的身份標(biāo)識(shí)與該樹(shù)葉子節(jié)點(diǎn)一一對(duì)應(yīng)。在更新密鑰時(shí)，利用完全子樹(shù)覆蓋技術(shù)確定僅覆蓋未被撤銷用戶的最小節(jié)點(diǎn)集合，再利用時(shí)間戳級(jí)聯(lián)更新節(jié)點(diǎn)信息作為更新標(biāo)識(shí)，計(jì)算出更新密鑰集合。在加密時(shí)，由于發(fā)送者需要將時(shí)間戳與接收者身份標(biāo)識(shí)對(duì)應(yīng)的葉子節(jié)點(diǎn)到根節(jié)點(diǎn)路徑上的所有節(jié)點(diǎn)信息級(jí)聯(lián)作為臨時(shí)身份標(biāo)識(shí)用于加密消息，從而使得密文數(shù)量至少為O（log N）。受此思想的啟發(fā)，針對(duì)SM9標(biāo)識(shí)簽名算法，可以采用同樣的更新密鑰的策略并利用長(zhǎng)期密鑰和更新密鑰生成消息的兩份簽名。但是，用戶在驗(yàn)證簽名的合法性時(shí)，除了利用簽名者的身份標(biāo)識(shí)進(jìn)行一次驗(yàn)簽外，還要利用至少O（log N）個(gè)臨時(shí)標(biāo)識(shí)進(jìn)行驗(yàn)簽，從而使得簽名驗(yàn)證算法的效率較低。為了解決該問(wèn)題，本文在簽名時(shí)，將使用的更新密鑰的節(jié)點(diǎn)信息嵌入到簽名中，用戶首先驗(yàn)證嵌入的節(jié)點(diǎn)信息是否在用戶路徑上，再使用該節(jié)點(diǎn)信息（作為臨時(shí)標(biāo)識(shí)）驗(yàn)證簽名的合法性，從而使得驗(yàn)簽次數(shù)降至兩次。

本文提出了一種可撤銷SM9標(biāo)識(shí)簽名算法（簡(jiǎn)稱CS-SM9-RIBS），它利用完全子樹(shù)實(shí)現(xiàn)在SM9標(biāo)識(shí)簽名算法中對(duì)用戶密鑰的撤銷和更新機(jī)制。在該算法中，密鑰中心會(huì)根據(jù)用戶的身份生成一個(gè)長(zhǎng)期簽名密鑰，根據(jù)更新節(jié)點(diǎn)集合生成更新密鑰并發(fā)送給用戶，使得只有未被撤銷的用戶才能合成一個(gè)合法的臨時(shí)簽名密鑰用于簽名消息。與文獻(xiàn)［3］的方案（簡(jiǎn)稱BF-SM9-RIBS）相比，該方案無(wú)須數(shù)據(jù)發(fā)送者和服務(wù)器之間建立一條安全信道，并且更新密鑰的數(shù)量也大大降低，從O（N-R）降至O（R log（N/R））。通過(guò)實(shí)驗(yàn)分析表明，當(dāng)系統(tǒng)用戶數(shù)量為N=213=8 192、被撤銷用戶數(shù)量R∈［0，100］時(shí)，BF-SM9-RIBS方案密鑰更新的時(shí)間約為45 s，而CS-SM9-RIBS方案所需要時(shí)間在15 s以下。

1 基礎(chǔ)知識(shí)

1.1 符號(hào)說(shuō)明

在本文中，A‖B表示將兩個(gè)比特串A和B進(jìn)行級(jí)聯(lián)。若S是一個(gè)算法，則s←S表示執(zhí)行算法S輸出的結(jié)果為s；若S是一個(gè)集合，則s←S表示從集合S中以均勻隨機(jī)分布選取一個(gè)元素s。在SM9算法中：a）Hv為輸入為任意比特串，輸出為v bit的密碼雜湊函數(shù)；b）H2RF（Hv，Z，p）為輸入為密碼雜湊函數(shù)Hv、比特串Z和整數(shù)p，輸出為整數(shù)h∈［1，p-1］的密碼函數(shù)。

1.2 雙線性映射

令Euclid Math OnePAp（1λ）表示一個(gè)雙線性對(duì)群生成算法，輸入1λ為安全參數(shù)，輸出為（e，Euclid Math TwoGAp1，Euclid Math TwoGAp2，Euclid Math TwoGApT，p，g，h），其中Euclid Math TwoGAp1、Euclid Math TwoGAp2和Euclid Math TwoGApT是階為素?cái)?shù)p的循環(huán)群，映射e：Euclid Math TwoGAp1×Euclid Math TwoGAp2→Euclid Math TwoGApT為雙線性對(duì)，g和h分別是Euclid Math TwoGAp1和Euclid Math TwoGAp2的生成元。一個(gè)雙線性映射應(yīng)該滿足以下性質(zhì)：a）雙線性性，對(duì)于任意的α，β∈Euclid Math TwoZApp，有e（gα，hβ）=e（g，h）αβ；b）非退化性，g1∈Euclid Math TwoGAp1，g2∈Euclid Math TwoGAp2滿足e（g1，g2）≠1Euclid Math TwoGApT；c）可計(jì)算性，對(duì)于任意的g和h，存在有效多項(xiàng)式時(shí)間算法計(jì)算e（g，h）。

1.3 困難問(wèn)題假設(shè)

本節(jié)主要介紹SM9簽名算法滿足適應(yīng)性選擇消息和標(biāo)識(shí)攻擊下的存在性不可偽造攻擊安全性（existentially unforgeable against adaptive chosen message and identity attacks，簡(jiǎn)稱EU-CMIA安全性）依賴的q-SDH問(wèn)題（q-strong Diffie-Hellman）［27］。令e：Euclid Math TwoGAp1×Euclid Math TwoGAp2→Euclid Math TwoGApT為一個(gè)雙線性映射，g和h分別是Euclid Math TwoGAp1和Euclid Math TwoGAp2的生成元，群Euclid Math TwoGAp1、Euclid Math TwoGAp2和Euclid Math TwoGApT的階為p，則基于雙線性群的q-SDH問(wèn)題的定義如下：

定義1 q-SDH問(wèn)題。已知q+2個(gè)群元素（g，h，ha，ha2，…，haq）∈Euclid Math TwoGAp1×Euclid Math TwoGApq+12，其中a未知，找到一個(gè)二元組（c，g1（c+a）），其中c∈Euclid Math TwoZApp。若q-SDH問(wèn)題在多項(xiàng)式時(shí)間內(nèi)可解的概率是可忽略的，則稱q-SDH假設(shè)成立。

1.4 SM9-IBS標(biāo)識(shí)簽名算法

SM9標(biāo)識(shí)簽名算法（簡(jiǎn)稱SM9-IBS算法）包括四個(gè)（概率）多項(xiàng)式時(shí)間算法：

a）系統(tǒng)參數(shù)生成SM9.Setup（1λv）。輸入安全參數(shù)1λ，密鑰中心首先運(yùn)行算法Euclid Math OnePAp（1λ）生成一個(gè)雙線性對(duì)配對(duì)群Euclid Math OneGAp=（e，Euclid Math TwoGAp1，Euclid Math TwoGAp2，Euclid Math TwoGApT，p，g，h）；然后，選取隨機(jī)數(shù)s∈Euclid Math TwoZApp，計(jì)算Ppub-s=gs和u=e（g，h）s。則系統(tǒng)的主公鑰和主私鑰分別為

mpk=（Euclid Math OneGAp，Ppub-s，u，H（id），hid）（1）

msk=s（2）

其中：H（id）是密碼函數(shù)H2RF（Hv，id，p）；hid=3。假設(shè)系統(tǒng)的主公鑰作為其他算法的默認(rèn)輸入，可省略不寫。

b）用戶密鑰提取SM9.Extract（msk，id）。對(duì)于身份標(biāo)識(shí)為id的用戶，密鑰生成中心為用戶計(jì)算簽名私鑰為

dsid=gsH1（id‖hid，N）+s（3）

則簽名者公鑰為id，私鑰為dsid。

c）簽名生成SM9.Sign（dsid，M）。身份標(biāo)識(shí)為id的簽名者對(duì)消息M進(jìn)行簽名，簽名過(guò)程如下：（a）計(jì)算w=ur，其中r為隨機(jī)數(shù)且滿足r∈Euclid Math TwoZApp；（b）計(jì)算h=H2RF（Hv，M‖w，p）；（c）計(jì)算l=（r-h） mod p，若l=0，則返回步驟（b）；（d）計(jì)算S=dslid。則簽名者對(duì)消息的簽名結(jié)果為σ=（h，S）。

d）驗(yàn)證SM9.Verify（id，M′，σ′）。驗(yàn)證者在收到簽名者的身份標(biāo)識(shí)id、消息M′和簽名結(jié)果σ′=（h′，S′）后，執(zhí)行以下步驟進(jìn)行簽名驗(yàn)證：（a）計(jì)算t=uh′；（b）計(jì)算P=hH（id）·Ppub-s；（c）計(jì)算w′=α·t，其中α=e（S′，P）；（d）計(jì)算h2=H2RF（Hv，M′‖w′，p）；（e）若h2=h′，則驗(yàn)簽通過(guò)，否則驗(yàn)簽失敗。

注釋1 為了提高簽名和驗(yàn)證算法的效率，可以將原始SM9-IBS算法中計(jì)算的固定值u=e（g，Ppub-s）放到系統(tǒng)公鑰中，從而使得簽名和驗(yàn)證算法都減少一次雙線性配對(duì)運(yùn)算，而系統(tǒng)公鑰將增加一個(gè)群Euclid Math TwoGApT上的元素。

在標(biāo)識(shí)簽名算法中，適應(yīng)性選擇消息和標(biāo)識(shí)攻擊下的存在性不可偽造EU-CMIA安全模型的定義與傳統(tǒng)簽名算法的安全模型定義類似，除了頻繁的詢問(wèn)外，允許攻擊者選擇任意標(biāo)識(shí)并獲取相應(yīng)的簽名密鑰，以及任意消息并獲取簽名結(jié)果，具體參見(jiàn)文獻(xiàn)［27］。在該模型下，有以下結(jié)論：

定理1 SM9-IBS的安全性［27］。在隨機(jī)預(yù)言機(jī)模型下，如果q-SDH問(wèn)題是困難的，則SM9-IBS滿足EU-CMIA安全性。

2 CS-SM9-RIBS標(biāo)識(shí)簽名算法

2.1 RIBS的定義

圖1給出了可撤銷標(biāo)識(shí)數(shù)字簽名算法的系統(tǒng)模型，它包含以下四個(gè)實(shí)體：

a）密鑰中心（KGC），主要負(fù)責(zé)產(chǎn)生系統(tǒng)主公鑰mpk和主私鑰msk，為身份標(biāo)識(shí)為id的用戶生成長(zhǎng)期簽名密鑰dsid，生成更新密鑰集合ukt，維護(hù)用戶撤銷列表RL及一個(gè)與所有用戶身份標(biāo)識(shí)id對(duì)應(yīng)的身份二叉樹(shù)tree。

b）數(shù)據(jù)簽名者（DS），主要負(fù)責(zé)計(jì)算原始消息M的數(shù)字簽名結(jié)果σ。

c）存儲(chǔ)服務(wù)器（SS），主要負(fù)責(zé)存儲(chǔ)用戶的簽名。

d）簽名驗(yàn)證者（SV），主要負(fù)責(zé)對(duì)接收到的簽名σ進(jìn)行合法性驗(yàn)證。

定義2 RIBS的定義。一個(gè)RIBS算法包含系統(tǒng)參數(shù)生成算法、用戶注冊(cè)算法、未撤銷用戶的更新節(jié)點(diǎn)生成算法、更新密鑰生成算法、臨時(shí)簽名密鑰生成算法、簽名算法、驗(yàn)證算法和用戶撤銷算法八個(gè)（概率）多項(xiàng)式時(shí)間算法，具體如下：

a）系統(tǒng)參數(shù)生成Setup（1λ）。該算法由密鑰中心負(fù)責(zé)執(zhí)行，它的輸入為安全參數(shù)λ，輸出為系統(tǒng)的主公鑰mpk和主私鑰msk。此外，密鑰中心維護(hù)一個(gè)初始化為空集的撤銷列表RL，以及一個(gè)與所有用戶身份標(biāo)識(shí)id對(duì)應(yīng)的滿二叉樹(shù)tree。

b）用戶注冊(cè)Regist（msk，id）。該算法由密鑰生成中心負(fù)責(zé)執(zhí)行，它的輸入為系統(tǒng)的主私鑰和用戶的身份標(biāo)識(shí)id，將用戶的身份標(biāo)識(shí)id加入到tree，并輸出用戶的長(zhǎng)期簽名密鑰dsid。

c）更新節(jié)點(diǎn)KUNode（tree，RL，t）。該算法由密鑰中心執(zhí)行，它輸入身份二叉樹(shù)tree、撤銷列表RL和時(shí)間t，輸出所有需要生成更新密鑰的節(jié)點(diǎn)集合KUNodes。

d）更新密鑰UpdateK（msk，t，KUNodes）。該算法由密鑰中心執(zhí)行，輸入為系統(tǒng)主私鑰msk、時(shí)間t以及未撤銷結(jié)集合KUNodes，輸出為更新密鑰集合ukt，并通過(guò)公開(kāi)信道廣播給系統(tǒng)用戶。

e）臨時(shí)簽名密鑰生成TempK（dsid，ukt）。該算法由數(shù)據(jù)簽名者執(zhí)行，它輸入用戶的長(zhǎng)期簽名密鑰dsid和更新密鑰集合ukt，若該用戶未被撤銷，則算法輸出為用戶的臨時(shí)簽名密鑰tsdid，t（該簽名密鑰不僅包含了用戶的身份id和更新時(shí)間t，同時(shí)也包含了對(duì)應(yīng)的更新節(jié)點(diǎn)信息θ）。

f）簽名Sign（tsdid，t，M）。該算法由數(shù)據(jù)簽名者執(zhí)行，它的輸入為原始消息M、用戶臨時(shí)簽名密鑰tsdid，t，計(jì)算出消息M的簽名σ，該簽名包含了時(shí)間周期和更新節(jié)點(diǎn)信息。最后，將消息和簽名（M，σ）一同發(fā)送給存儲(chǔ)服務(wù)器進(jìn)行儲(chǔ)存。

g）驗(yàn)證Verify（id，M，σ）。該算法由簽名驗(yàn)證者執(zhí)行，算法的輸入為簽名者的身份標(biāo)識(shí)id、消息M和簽名σ，輸出簽名的驗(yàn)證結(jié)果，若簽名合法，則輸出1，否則輸出0。

h）用戶撤銷Revoke（id，t，RL）。該算法由密鑰中心執(zhí)行，它的輸入為被撤銷的用戶身份標(biāo)識(shí)id、時(shí)間周期t和用戶撤銷列表RL，密鑰中心將（t，id）加入撤銷列表，返回更新后的撤銷列表RL。

2.2 安全模型

為刻畫方案具有密鑰撤銷機(jī)制，通過(guò)攻擊者與挑戰(zhàn)者的游戲描述適應(yīng)性選擇消息和標(biāo)識(shí)攻擊下的存在性不可偽造攻擊（EU-CMIA安全性）。在該模型中，攻擊者可以詢問(wèn)任意用戶的長(zhǎng)期簽名密鑰，當(dāng)某一用戶的簽名密鑰泄露（被攻擊者詢問(wèn)）并在t時(shí)刻被密鑰中心撤銷時(shí)，方案的安全性能夠保證在t*≥t時(shí)刻，攻擊者無(wú)法生成該用戶的一個(gè)合法簽名。

定義3 RIBS的EU-CMIA安全性。假設(shè)A是任意一個(gè)概率多項(xiàng)式時(shí)間攻擊者，C是一個(gè)挑戰(zhàn)者。定義RIBS的安全性游戲ExpEU-CMIARIBS，A（1λ）如下：

a）系統(tǒng)建立。挑戰(zhàn)者通過(guò)運(yùn)行系統(tǒng)參數(shù)生成算法Setup（1λ），生成系統(tǒng)主公鑰mpk和主私鑰msk，并初始化一個(gè)空的密鑰撤銷列表RL和一個(gè)滿二叉樹(shù)tree，挑戰(zhàn)者將系統(tǒng)公鑰mpk發(fā)送給攻擊者。

b）詢問(wèn)。攻擊者可以適應(yīng)性地進(jìn)行以下詢問(wèn)，詢問(wèn)的次數(shù)為多項(xiàng)式次。

（a）用戶長(zhǎng)期簽名密鑰詢問(wèn)。挑戰(zhàn)者初始化一個(gè)空集合L1，當(dāng)攻擊者詢問(wèn)身份標(biāo)識(shí)為id的用戶長(zhǎng)期簽名密鑰時(shí)，挑戰(zhàn)者通過(guò)執(zhí)行用戶注冊(cè)算法Regist（msk，id）生成密鑰dsid并返回給攻擊者；同時(shí)，挑戰(zhàn)者將身份標(biāo)識(shí)id添加到集合L1中。

（b）更新密鑰詢問(wèn)。當(dāng)攻擊者詢問(wèn)t時(shí)刻的更新密鑰時(shí)，挑戰(zhàn)者首先執(zhí)行更新節(jié)點(diǎn)生成算法KUNode（tree，RL，t）得到t時(shí)刻的更新節(jié)點(diǎn)集合KUNodes；然后執(zhí)行更新密鑰生成算法UpdateK（msk，t，KUNodes）得到t時(shí)刻的更新密鑰集合ukt，并將它返回給攻擊者。

（c）簽名詢問(wèn)。挑戰(zhàn)者初始化一個(gè)空集合L2，當(dāng)攻擊者詢問(wèn)消息M在身份標(biāo)識(shí)為id和時(shí)刻t下的簽名時(shí)，挑戰(zhàn)者先利用該用戶id的長(zhǎng)期簽名密鑰dsid和t時(shí)刻的更新密鑰集合ukt，通過(guò)臨時(shí)簽名密鑰生成算法生成該用戶的臨時(shí)簽名密鑰tsdid，t；然后，利用簽名算法Sign（tsdid，t，M）生成消息M的簽名σ，并將該簽名返回給攻擊者；同時(shí)，挑戰(zhàn)者將元素（id，t，M）添加到集合L2中。

（d）用戶撤銷詢問(wèn)。當(dāng)攻擊者詢問(wèn)t時(shí)刻的標(biāo)識(shí)為id的用戶撤銷時(shí)，挑戰(zhàn)者將（t，id）添加到用戶撤銷列表RL中。

c）偽造。攻擊者返回一個(gè)偽造的簽名信息（M*，σ*）以及身份標(biāo)識(shí)id*和時(shí)間t*，并滿足以下限制條件：（a）若用戶在t*或之前時(shí)刻未撤銷，即不存在t≤t*，使得（t，id*）∈RL，則攻擊者不能訪問(wèn)身份標(biāo)識(shí)id*的長(zhǎng)期簽名密鑰，即id*L1并且（id*，t*，M*）L2；（b）若用戶在t*或之前時(shí)刻已撤銷，即存在t≤t*，使得（t，id*）∈RL，則攻擊者可以詢問(wèn)身份標(biāo)識(shí)id*的長(zhǎng)期簽名密鑰，即id*∈L1。

d）輸出。若攻擊者偽造的簽名信息滿足限制條件，并能通過(guò)簽名驗(yàn)證算法，則表示攻擊者偽造成功，挑戰(zhàn)者返回1；否則返回0。

在上述游戲中，A成功的概率定義為

Pr［A成功］=Pr［ExpEU-CMARIBS，A（1λ）=1］（4）

如果A成功的概率（關(guān)于安全參數(shù)1λ）是可忽略的，則稱RIBS算法是EU-CMIA安全的。

2.3 算法設(shè)計(jì)

本節(jié)利用完全子樹(shù)覆蓋技術(shù)設(shè)計(jì)一種可撤銷SM9標(biāo)識(shí)簽名算法（記做CS-SM9-RIBS）。具體構(gòu)造如下：

a）系統(tǒng)參數(shù)生成Setup（1λ）。在輸入安全參數(shù)1λ后，生成系統(tǒng)參數(shù)的過(guò)程如下：

（a）密鑰中心運(yùn)行算法Euclid Math OnePAp（1λ）生成一個(gè)雙線性配對(duì)群Euclid Math OneGAp=（e，Euclid Math TwoGAp1，Euclid Math TwoGAp2，Euclid Math TwoGApT，p，g，h），密鑰中心選擇一個(gè)隨機(jī)元素s∈Euclid Math TwoZApp，并計(jì)算

Ppub-s=hs和u=e（g，Ppub-s）（5）

令H（id）=H2RF（Hv，id，p）、hid=3。假設(shè)每個(gè)用戶的身份標(biāo)識(shí)長(zhǎng)度為n bit，則密鑰中心初始化一棵高度為n+1的滿二叉樹(shù)tree以及一個(gè)空的用戶撤銷列表RL。

（b）輸出系統(tǒng)的主公鑰mpk和主私鑰msk如下：

mpk=（Euclid Math OneGAp，Ppub-s，u，H（·），hid）（6）

msk=s（7）

b）用戶注冊(cè)Register（msk，id）。密鑰中心在收到身份標(biāo)識(shí)為id的用戶注冊(cè)請(qǐng)求后，為用戶注冊(cè)生成一個(gè)長(zhǎng)期簽名密鑰的過(guò)程如下：

（a）密鑰中心使用SM9的密鑰提取算法為標(biāo)識(shí)id的用戶生成簽名密鑰dsid，即

dsid←SM9.Extract（msk，id）（8）

（b）密鑰中心選擇一個(gè)與用戶身份標(biāo)識(shí)匹配的葉子節(jié)點(diǎn)，將id添加到tree上；

（c）將用戶長(zhǎng)期簽名密鑰dsid發(fā)送給用戶。

c）更新節(jié)點(diǎn)KUNode（tree，RL，t）。在輸入身份二叉樹(shù)tree、撤銷列表RL和時(shí)間t后，令θ為tree的非葉子節(jié)點(diǎn)，θl和θr分別為θ的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)，path（θid）為根節(jié)點(diǎn)到葉子節(jié)點(diǎn)θid路徑上所有節(jié)點(diǎn)的集合，未撤銷節(jié)點(diǎn)生成過(guò)程如下：（a）令集合X，Y=；（b）對(duì)（t′，id）∈RL且t′≤t，將path（θid）中的每一個(gè)節(jié)點(diǎn)添加到集合X中；（c）對(duì)θ∈X，如果θlX，則將θl添加到集合Y中，如果θrX，則將θr添加到集合Y中；（d）如果Y=，將根節(jié)點(diǎn)root添加到集合Y中；（e）令KUNodes=Y，輸出KUNodes。

圖2和3給出了更新節(jié)點(diǎn)選擇算法的兩個(gè)具體示例。在該示例中，二叉樹(shù)的高度為4（用戶的身份標(biāo)識(shí)長(zhǎng)度為3 bit），加粗節(jié)點(diǎn)表示當(dāng)前KUNodes所包含的更新節(jié)點(diǎn)，虛線節(jié)點(diǎn)表示被撤銷的用戶節(jié)點(diǎn)。在圖2中，無(wú)用戶被撤銷，KUNodes僅包含根節(jié)點(diǎn)，即{root}；在圖3中，標(biāo)識(shí)id=3的用戶被撤銷，KUNodes={00，010，1}。

d）更新密鑰UpdateK（msk，t，KUNodes）。在輸入系統(tǒng)密鑰msk、時(shí)間t以及更新節(jié)點(diǎn)集合KUNodes后，密鑰中心首先計(jì)算由時(shí)間和更新節(jié)點(diǎn)組成的更新標(biāo)識(shí)集合UID={t‖θ}θ∈KUNodes。對(duì)于集合UID中的每個(gè)標(biāo)識(shí)uid=t‖θ，調(diào)用SM9的密鑰提取算法生成相應(yīng)的標(biāo)識(shí)密鑰，即

dst‖θ←SM9.Extract（msk，uid）（9）

令ukt，θ=dst‖θ，則更新密鑰集合為

ukt={ukt，θ}θ∈KUNodes（10）

密鑰中心通過(guò)公開(kāi)信道廣播給系統(tǒng)用戶。

e）臨時(shí)簽名密鑰TempK（dsid，ukt）。在輸入用戶的長(zhǎng)期簽名密鑰dsid和更新密鑰集合ukt后，用戶執(zhí)行以下步驟：

（a）若該用戶未被撤銷，則用戶路徑上的節(jié)點(diǎn)集合Path（θid）與更新節(jié)點(diǎn)集合KUNodes一定存在一個(gè)且唯一的公共節(jié)點(diǎn)θ，用戶找到該節(jié)點(diǎn)對(duì)應(yīng)的更新密鑰ukt，θ，并將臨時(shí)簽名密鑰定義為tsdid，t=dsid‖ukt，θ‖θ，若該用戶已被撤銷，則不存在公共的更新節(jié)點(diǎn)θ，用戶將臨時(shí)簽名密鑰定義為終止符，即tsdid，t=⊥；（b）返回臨時(shí)簽名密鑰tsdid，t。

f）簽名Sign（tsdid，t，M）。在輸入明文消息M、用戶的臨時(shí)簽名密鑰tsdid，t后，該算法執(zhí)行過(guò)程如下：

（a）若臨時(shí)簽名密鑰tsdid，t=⊥，則用戶終止算法并返回⊥；否則執(zhí)行步驟（b）。

（b）根據(jù)臨時(shí)簽名密鑰恢復(fù)出用戶的長(zhǎng)期簽名密鑰dsid、更新密鑰ukt，θ以及更新節(jié)點(diǎn)信息θ，并令=M‖t‖θ（假設(shè)不同的消息、時(shí)間和更新節(jié)點(diǎn)級(jí)聯(lián)的結(jié)果不同）。

（c）以dsid作為簽名密鑰，執(zhí)行SM9簽名算法，生成消息的第一部分簽名σ1=（h1，S1），即

（h1，S1）←SM9.Sign（dsid，）（11）

（d）以u(píng)kt，θ作為簽名密鑰再次執(zhí)行SM9簽名算法，生成消息的第二部分簽名σ2=（h2，S2），即

（h2，S2）←SM9.Sign（ukt，θ，）（12）

（e）令σ=（σ1，σ2，t‖θ）為最終簽名發(fā)送給存儲(chǔ)服務(wù)器進(jìn)行存儲(chǔ)。

g）簽名驗(yàn)證Verify（id，M，σ）。在輸入簽名者的身份標(biāo)識(shí)id、消息M和簽名σ后，簽名驗(yàn)證過(guò)程如下：

（a）簽名驗(yàn)證者收到簽名σ=（σ1，σ2，t‖θ）后將其拆分為σ1、σ2和t‖θ三部分。驗(yàn)證者首先判斷節(jié)點(diǎn)θ是否在路徑path（θid）上，如果不在，則算法終止并返回0；否則，執(zhí)行步驟（b）。

（b）驗(yàn)證者計(jì)算=M‖t‖θ，使用簽名者的身份標(biāo)識(shí)id利用SM9簽名驗(yàn)證算法對(duì)消息和簽名σ1進(jìn)行驗(yàn)證，驗(yàn)證結(jié)果記為b1，即

b1←SM9.Verify（id，，σ1）（13）

如果b1=0，則算法終止并返回0；否則，執(zhí)行步驟（c）。

（c）驗(yàn)證者使用更新標(biāo)識(shí)t‖θ利用SM9簽名驗(yàn)證算法對(duì)消息和簽名σ2進(jìn)行驗(yàn)證，驗(yàn)證結(jié)果記為b2，即

b2←SM9.Verify（t‖θ，，σ2）（14）

如果b2=0，則算法終止并返回0；否則，執(zhí)行步驟（d）。

（d）上述驗(yàn)證均通過(guò)，算法返回1。

h）用戶撤銷Revoke（id，t，RL）。在輸入被撤銷用戶身份標(biāo)識(shí)id、時(shí)間周期t和撤銷列表RL后，若存在元素（t′，id）∈RL且t′≤t，則直接返回；否則，將（t，id）加入撤銷列表RL，返回RL∪（t，id）。

正確性 假設(shè)σ=（σ1，σ2，t‖θ）是利用簽名算法Sign（M，tsdid，t）計(jì)算的簽名。因?yàn)棣?=（h1，S1）是利用標(biāo)識(shí)為id的SM9簽名密鑰dsid對(duì)消息的簽名，根據(jù)SM9簽名算法的正確性，則驗(yàn)證算法在第（b）步輸出結(jié)果應(yīng)為b1=1；若用戶id在時(shí)刻t未被撤銷，根據(jù)更新節(jié)點(diǎn)選擇算法，用戶能夠從更新密鑰中獲取臨時(shí)簽名密鑰ukt，θ。該密鑰對(duì)應(yīng)的身份標(biāo)識(shí)為t‖θ，并且θ屬于路徑path（θid）上的點(diǎn)。因此，步驟（a）的驗(yàn)證通過(guò)。由于σ2=（h2，S2）是利用標(biāo)識(shí)為t‖θ的SM9簽名密鑰ukt，θ對(duì)消息的簽名，根據(jù)SM9簽名算法的正確性，則驗(yàn)證算法在第（c）步輸出結(jié)果應(yīng)為b2=1。綜上，CS-SM9-RIBS簽名算法滿足正確性。

3 安全性分析

定理2 CS-SM9-RIBS的安全性。假設(shè)A是任意一個(gè)概率多項(xiàng)式時(shí)間算法，∏是一個(gè)CS-SM9-RIBS簽名算法。若A能夠以概率εΠ成功攻擊∏的EU-CMIA安全性，那么存在另一個(gè)概率多項(xiàng)式時(shí)間算法B，以相同的概率成功偽造原始SM9-IBS的一個(gè)簽名。

證明 利用算法A作為子程序，構(gòu)造一個(gè)仿真算法B在EU-CMIA模型下偽造SM9-IBS簽名算法的簽名。仿真算法B按照如下方式模擬攻擊者A在游戲ExpEU-CMIARIBS，A（1λ）中的環(huán)境：

a）系統(tǒng)建立。仿真算法B首先詢問(wèn)SM9-IBS的挑戰(zhàn)者，獲取SM9-IBS的一個(gè)挑戰(zhàn)主公鑰mpk，包括雙線性對(duì)配對(duì)群Euclid Math OneGAp=（e，Euclid Math TwoGAp1，Euclid Math TwoGAp2，Euclid Math TwoGApT，p，g，h），公鑰元素Ppub-s、u和密碼函數(shù)H（id）及其標(biāo)識(shí)hid。B將主公鑰mpk發(fā)送給攻擊者A，同時(shí)B初始化一個(gè)空的密鑰撤銷列表RL、一棵滿二叉樹(shù)tree以及兩個(gè)空集合L1和L2。

b）詢問(wèn)。B通過(guò)如下方式回答攻擊者的詢問(wèn)：

（a）用戶長(zhǎng)期簽名密鑰詢問(wèn)。當(dāng)攻擊者A詢問(wèn)身份標(biāo)識(shí)為id的用戶長(zhǎng)期簽名密鑰時(shí)，B將id發(fā)送給SM9-IBS的挑戰(zhàn)者，從而獲取身份標(biāo)識(shí)為id的密鑰dsid并將它返回給攻擊者A，同時(shí)A將（id，dsid）添加到集合L1中。

（b）更新密鑰詢問(wèn)。當(dāng)A詢問(wèn)t時(shí)刻的更新密鑰時(shí)，B首先根據(jù)算法KUNode（tree，RL，t）計(jì)算t時(shí)刻的更新節(jié)點(diǎn)集合KUNodes；然后確定更新節(jié)點(diǎn)標(biāo)識(shí)集合UID={t‖θ}θ∈KUNodes。對(duì)于集合UID中的每個(gè)標(biāo)識(shí)t‖θ，B詢問(wèn)SM9-IBS挑戰(zhàn)者，獲取該標(biāo)識(shí)的密鑰dst‖θ。B將密鑰集合ukt={dst‖θ}θ∈KUNodes發(fā)送給A，同時(shí)B將所有（t‖θ，dst‖θ）添加到集合L1中。

（c）簽名詢問(wèn)。當(dāng)A詢問(wèn)消息M在身份標(biāo)識(shí)為id和時(shí)刻t下的簽名時(shí)，仿真算法B首先查找集合L1中是否存在以t‖θ為標(biāo)識(shí)的密鑰dst‖θ，其中θ必須在路徑path（θid）上（注：假設(shè)A總是可以先詢問(wèn)t時(shí)刻的更新密鑰），若不存在，則B直接返回⊥給A（表示在該時(shí)刻id已被撤銷）；否則，B利用密鑰dst‖θ對(duì)消息=M‖t‖θ進(jìn)行簽名，得到第二部分簽名σ2=（h2，S2）。接下來(lái)，B查找集合L1中是否存在以id為標(biāo)識(shí)的密鑰dsid，若存在，則B利用密鑰dsid對(duì)消息=M‖t‖θ進(jìn)行簽名，得到第一部分簽名σ1=（h1，S1）；若不存在，B將消息以及（身份）標(biāo)識(shí)t‖θ發(fā)送給SM9-IBS的挑戰(zhàn)者，獲得消息在（身份）標(biāo)識(shí)t‖θ密鑰下的簽名σ2=（h2，S2）。最后，B將簽名σ=（σ1，σ2，t‖θ）發(fā)送給A，同時(shí)B將信息（id，t，M）添加到集合L2中。

（d）用戶撤銷詢問(wèn)。當(dāng)A在t時(shí)刻以身份標(biāo)識(shí)id詢問(wèn)撤銷列表時(shí)， B首先查找集合RL是否存在元素（t′，id），其中t′≤t，若存在，則返回原撤銷列表RL；否則返回RL∪（t，id）。

c）偽造。當(dāng)攻擊者A結(jié)束上述詢問(wèn)后，輸出一個(gè)偽造的簽名信息（M*，σ*）以及挑戰(zhàn)身份標(biāo)識(shí)id*和時(shí)間t*。

d）輸出。若（M*，σ*）是一個(gè)合法的CS-SM9-RIBS簽名，其中σ*=（σ*1，σ*2，t*‖θ*），則該簽名必須通過(guò)簽名驗(yàn)證算法。特別地，θ*必須是用戶路徑，則B定義消息M*=M*‖t*‖θ*，并按如下方式返回消息M*的一個(gè)偽造SM9-IBS簽名σ*：（a）若（id*，·）L1，表明A從未詢問(wèn)過(guò)身份標(biāo)識(shí)為id*的密鑰，則B輸出偽造簽名σ*=σ*1；（b）若存在（id*，·）∈L1，則表明A詢問(wèn)過(guò)身份標(biāo)識(shí)id*的密鑰。根據(jù)游戲規(guī)則，該用戶必須在t*之前的某時(shí)刻t被撤銷，即（t，id*）∈RL。根據(jù)更新節(jié)點(diǎn)生成算法，在t*時(shí)刻，算法KUNode（tree，RL，t*）輸出的更新節(jié)點(diǎn)集合KUNodes肯定不包含挑戰(zhàn)用戶路徑path（θid*）上的節(jié)點(diǎn)θ*，因此在整個(gè)游戲過(guò)程中，B從未詢問(wèn)過(guò)標(biāo)識(shí)為t*‖θ*的密鑰及其簽名。此時(shí)，B輸出偽造簽名σ*=σ*2。

通過(guò)上述分析，B能夠完美地仿真A在CS-SM9-RIBS中的游戲環(huán)境，同時(shí)，若攻擊者能夠成功偽造一個(gè)CS-SM9-RIBS簽名，則仿真算法以相同的概率偽造一個(gè)SM9-IBS簽名。

4 性能分析

目前，除了直接應(yīng)用Boneh-Franklin［3］通用密鑰撤銷思想可以構(gòu)造針對(duì)SM9-IBS的密鑰撤銷算法外，還沒(méi)有公開(kāi)發(fā)表針對(duì)SM9-IBS的密鑰撤銷算法，但是存在一些優(yōu)秀的針對(duì)其他標(biāo)識(shí)身份簽名的密鑰撤銷算法，如文獻(xiàn)［19，28～30］。為此，本章首先從理論和實(shí)驗(yàn)兩個(gè)角度分析和比較與SM9-IBS相關(guān)的密鑰撤銷算法的性能，包括本文提出的基于完全子樹(shù)密鑰撤銷技術(shù)的CS-SM9-RIBS算法、原始SM9-IBS簽名算法［9］以及應(yīng)用Boneh-Franklin［3］通用密鑰撤銷技術(shù)的BF-SM9-RIBS算法；再?gòu)睦碚撋戏治霰疚奶岢龅腃S-SM9-RIBS算法與國(guó)際上其他可撤銷標(biāo)識(shí)簽名算法的優(yōu)勢(shì)。

表1從參數(shù)大小、算法時(shí)間及安全性等理論角度對(duì)上述與SM9-IBS相關(guān)的三個(gè)算法的性能進(jìn)行總結(jié)與比較。在這些算法中，選擇使用對(duì)稱雙線性配對(duì)，即e：Euclid Math TwoGAp×Euclid Math TwoGAp→Euclid Math TwoGApT，其中群的階為素?cái)?shù)p。表1中，N和R分別表示系統(tǒng)用戶數(shù)量和被撤銷用戶的數(shù)量；E和P分別表示一次群元素的指數(shù)運(yùn)算和配對(duì)運(yùn)算。在比較各算法所需運(yùn)算操作次數(shù)時(shí)，忽略了除指數(shù)運(yùn)算和配對(duì)運(yùn)算之外的其他操作。表中符號(hào)“-”表示該項(xiàng)不存在，“0”表示該項(xiàng)幾乎不需要任何操作。

在BF-SM9-RIBS算法中，用戶只需要保存每個(gè)周期的臨時(shí)密鑰，而無(wú)長(zhǎng)期密鑰，每個(gè)周期的臨時(shí)簽名密鑰由密鑰中心臨時(shí)生成的更新密鑰構(gòu)成。更新用戶簽名密鑰的策略是將用戶的身份標(biāo)識(shí)id與時(shí)間周期t級(jí)聯(lián)的結(jié)果id‖t作為當(dāng)前時(shí)刻簽名的簽名公鑰，并將相應(yīng)的私鑰通過(guò)安全信道發(fā)送給對(duì)應(yīng)的未撤銷用戶。因此，更新用戶密鑰的復(fù)雜度為O（N-R），與系統(tǒng)用戶數(shù)量呈線性增長(zhǎng)。對(duì)于本文算法，采用完全子樹(shù)技術(shù)更新用戶密鑰，在平均情況下更新密鑰的數(shù)量?jī)H為O（R log（N/R））且可以在公開(kāi)信道上進(jìn)行傳輸。

從表1中可以看出，BF-SM9-RIBS和CS-SM9-RIBS兩種算法都支持用戶密鑰撤銷功能，同時(shí)保留了原始SM9-IBS算法的系統(tǒng)參數(shù)。在BF-SM9-RIBS算法中，用戶無(wú)須存儲(chǔ)長(zhǎng)期簽名密鑰并且臨時(shí)簽名密鑰僅為一個(gè)群元素；在CS-SM9-RIBS算法中，用戶需要存儲(chǔ)一個(gè)長(zhǎng)期簽名密鑰，盡管臨時(shí)簽名密鑰包含兩個(gè)群元素，但是它包括了用戶的長(zhǎng)期簽名密鑰，無(wú)須額外空間存儲(chǔ)該群元素。在簽名大小、簽名時(shí)間和驗(yàn)證時(shí)間方面，本文的CS-SM9-RIBS算法是原始SM9-IBS算法的兩倍，這是因?yàn)榍罢邽榱藢?shí)現(xiàn)用戶密鑰的撤銷功能增加了一個(gè)額外的簽名操作。BF-SM9-RIBS算法在參數(shù)大小和計(jì)算效率方面與原始SM9-IBS算法幾乎一樣，但是該算法的密鑰更新復(fù)雜度非常高且不支持公開(kāi)信道傳播更新密鑰。

本文在同一環(huán)境下對(duì)各算法進(jìn)行了仿真實(shí)現(xiàn)，并測(cè)試了平均執(zhí)行時(shí)間。編程測(cè)試環(huán)境為2.4 GHz Intel i5-9300H CPU、16.0 GB內(nèi)存、Windows 10家庭中文版操作系統(tǒng)。

本文采用JPBC庫(kù)對(duì)上述三種SM9簽名算法進(jìn)行仿真實(shí)現(xiàn)，選取的橢圓曲線類型為type-F。表2列出了主要算法運(yùn)行一次的平均時(shí)間、未考慮用戶撤銷等幾乎不耗時(shí)的算法以及僅需要在系統(tǒng)建立時(shí)運(yùn)行一次的系統(tǒng)參數(shù)生成算法。測(cè)試的算法主要包括生成長(zhǎng)期簽名密鑰的用戶注冊(cè)（或密鑰提取）算法、密鑰更新算法（包括更新節(jié)點(diǎn)選取算法）、臨時(shí)簽名密鑰生成算法、簽名算法和驗(yàn)證算法。對(duì)于更新密鑰生成算法，運(yùn)行時(shí)間不僅與系統(tǒng)用戶數(shù)量相關(guān)，而且與更新節(jié)點(diǎn)集合的大小相關(guān)。而更新節(jié)點(diǎn)集合的大小又與被撤銷用戶的數(shù)量及其在二叉樹(shù)中的位置相關(guān)。為了簡(jiǎn)化分析，表2僅考慮系統(tǒng)中有100個(gè)用戶且無(wú)用戶被撤銷的情況。根據(jù)理論分析，BF-SM9-RIBS算法需要生成100個(gè)更新密鑰，而本文算法僅需要生成一個(gè)更新密鑰。

從表2可以看出，BF-SM9-RIBS算法生成更新密鑰的時(shí)間較慢，而本文的密鑰更新算法很快。

為了更加清晰地比較CS-SM9-RIBS與BF-SM9-RIBS算法更新用戶密鑰的性能差異，測(cè)試方案設(shè)計(jì)如下：初始化系統(tǒng)用戶數(shù)量N的上限為8 192（即tree高為14），被撤銷用戶的數(shù)量R從0增加到100，且隨機(jī)選取被撤銷用戶的位置。圖4展示當(dāng)R取不同值時(shí)更新密鑰生成算法的時(shí)間開(kāi)銷。

從圖4可以看出，當(dāng)系統(tǒng)用戶數(shù)量較大、被撤銷用戶數(shù)量較少時(shí)，密鑰中心利用完全子樹(shù)技術(shù)更新用戶簽名密鑰的時(shí)間開(kāi)銷要遠(yuǎn)遠(yuǎn)小于Boneh和Franklin的直接密鑰更新技術(shù)。

最后從理論上比較CS-SM9-RIBS算法與國(guó)際上針對(duì)其他標(biāo)識(shí)簽名的密鑰撤銷算法［19，28～30］的性能，進(jìn)一步說(shuō)明CS-SM9-IBS可撤銷標(biāo)識(shí)簽名算法的優(yōu)勢(shì)，結(jié)果如表3所示。在這些算法中，除了文獻(xiàn)［30］基于三線性映射群外，其他算法都是基于標(biāo)準(zhǔn)的雙線映射群設(shè)計(jì)的。在表3中，除了文獻(xiàn)［30］外，其他文獻(xiàn)中的符號(hào)含義與表1中的符號(hào)一致。對(duì)于文獻(xiàn)［30］，Euclid Math TwoGAp2表示三線性映射中的一個(gè)階為素?cái)?shù)p的群，而E和P分別表示三線性映射中的群元素指數(shù)運(yùn)算和配對(duì)運(yùn)算。

從表3可以看出，CS-SM9-RIBS算法的臨時(shí)簽名密鑰和簽名大小比其他方案小。簽名時(shí)間相較文獻(xiàn)［29］多一次指數(shù)運(yùn)算，但是文獻(xiàn)［29］的更新密鑰時(shí)間與系統(tǒng)用戶數(shù)量呈線性增長(zhǎng)；文獻(xiàn)［30］的更新密鑰僅與被撤銷用戶數(shù)量相關(guān)，但是該方案依賴三線性映射，沒(méi)有雙線性映射的理論基礎(chǔ)成熟。總體而言，本文提出的CS-SM9-RIBS可撤銷標(biāo)識(shí)簽名算法的性能優(yōu)勢(shì)更明顯。

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

針對(duì)SM9標(biāo)識(shí)簽名算法存在的密鑰撤銷問(wèn)題，本文提出了一種可撤銷SM9標(biāo)識(shí)簽名算法，通過(guò)一棵完全子樹(shù)的輔助可以實(shí)現(xiàn)對(duì)用戶權(quán)限的控制，從而實(shí)現(xiàn)密鑰的撤銷和更新機(jī)制。通過(guò)理論分析和實(shí)驗(yàn)表明，該方案相比于BF-SM9-RIBS算法在更新密鑰方面具有一定的優(yōu)勢(shì)。在后續(xù)的工作中，存在以下問(wèn)題值得進(jìn)一步研究：該方案相比于BF-SM9-RIBS算法，在簽名和驗(yàn)簽階段多消耗一倍的時(shí)間，可進(jìn)一步研究耗時(shí)更少的SM9標(biāo)識(shí)簽名算法的密鑰撤銷機(jī)制。

參考文獻(xiàn)：

［1］Shamir A.Identity-based cryptosystems and signature schemes［C］//Advances in Cryptology.Berlin：Springer，1984：47-53.

［2］Sakai R，Ohgishi K，Kasahara M.Cryptosystems based on pairing［C］//Proc of the 1st International Conference on Cryptology.Berlin：Springer，2000：50-66.

［3］Boneh D，F(xiàn)ranklin M.Identity-based encryption from the Weil pairing［C］//Advances in Cryptology-CRYPTO.Berlin：Springer，2001：213-229.

［4］Cocks C.An identity-based encryption scheme based on quadratic resi-dues［C］//Proc of IMA International Conference on Cryptography and Coding.Berlin：Springer，2001：360-363.

［5］Hofheinz D，Jia Dingding，Pan Jiaxin.Identity-based encryption tightly secure under chosen-ciphertext attacks［C］//Proc of International Conference on Theory and Application of Cryptology and Information Security.Cham：Springer，2018：190-220.

［6］Langrehr R，Pan Jiaxin.Tightly secure hierarchical identity-based encryption［J］.Journal of Cryptology，2020，33（4）：1787-1821.

［7］Sahai A，Waters B.Fuzzy identity-based encryption［C］//Proc of the 11th Advances in Cryptology-Eurocrypt.Berlin：Springer，2005：457-473.

［8］Waters B.Efficient identity-based encryption without random oracles［C］//Proc of the 11th Advances in Cryptology-Eurocrypt.Berlin：Springer，2005：114-127.

［9］Cheng Zhaohui.The SM9 cryptographic schemes［EB/OL］.（2017-02-12）.https：//eprint.iacr.org/2017/117.pdf.

［10］ISO.ISO/IEC 14888-3：2018 Information technology security techniques：digital signatures with appendix，part 3：discrete logarithm based mechanisms［S］.2018.

［11］ISO.ISO/IEC 18033-5：2015/AMD 1：2021，Information technology security techniques：encryption algorithms，part 5：identity-based ciphers amendment 1：SM9 mechanism［S］.2021.

［12］Ji Honghan，Zhang Hongjie，Shao Lisong，et al.An efficient attribute-based encryption scheme based on SM9 encryption algorithm for dispatching and control cloud［J］.Connection Science，2021，33（4）：1094-1115.

［13］Mu Yongheng，Xu Haixia，Li Peili，et al.Secure two-party SM9 signing［J］.Science China Information Sciences，2020，63（8）：189101.

［14］張昱，孫光民，李煜.基于SM9算法的移動(dòng)互聯(lián)網(wǎng)身份認(rèn)證方案研究［J］.信息網(wǎng)絡(luò)安全，2021，21（4）：1-9.（Zhang Yu，Sun Guangmin，Li Yu.Research on mobile Internet authentication scheme based on SM9 algorithm［J］.Netinfo Security，2021，21（4）：1-9.）

［15］姚英英，常曉林，甄平.基于區(qū)塊鏈的去中心化身份認(rèn)證及密鑰管理方案［J］.網(wǎng)絡(luò)空間安全，2019，10（6）：33-39.（Yao Yingying，Chang Xiaolin，Zhen Ping.Decentralized identity authentication and key management scheme based on blockchain［J］.Information Security and Technology，2019，10（6）：33-39.）

［16］馬曉婷，馬文平，劉小雪.基于區(qū)塊鏈技術(shù)的跨域認(rèn)證方案［J］.電子學(xué)報(bào)，2018，46（11）：2571-2579.（Ma Xiaoting，Ma Wenping，Liu Xiaoxue.A cross domain authentication scheme based on blockchain technology［J］.Acta Electonica Sinica，2018，46（11）：2571-2579.）

［17］Boldyreva A，Goyal V，Kumar V.Identity-based encryption with efficient revocation［C］//Proc of the 15th ACM Conference on Computer and Communications Security.New York：ACM Press，2008：417-426.

［18］Libert B，Vergnaud D.Adaptive-ID secure revocable identity-based encryption［C］//Proc of Cryptographers’ Track at the RSA Confe-rence.Berlin：Springer，2009：1-15.

［19］Seo J H，Emura K.Revocable identity-based cryptosystem revisited：security models and constructions［J］.IEEE Trans on Information Forensics and Security，2014，9（7）：1193-1205.

［20］Lee K，Lee D H，Park J H.Efficient revocable identity-based encryption via subset difference methods［J］.Designs，Codes and Cryptography，2017，85（10）：39-76.

［21］Katsumata S，Matsuda T，Takayasu A.Lattice-based revocable（hierarchical） IBE with decryption key exposure resistance［J］.Theoretical Computer Science，2020，809（2）：103-136.

［22］Takayasu A，Watanabe Y.Lattice-based revocable identity-based encryption with bounded decryption key exposure resistance［C］//Proc of the 22nd Australasian Conference on Information Security and Privacy.Cham：Springer，2017：184-204.

［23］Li Jin，Li Jingwei，Chen Xiaofeng，et al.Identity-based encryption with outsourced revocation in cloud computing［J］.IEEE Trans on Computers，2013，64（2）：425-437.

［24］Qin Baodong，Deng R H，Li Yingjiu，et al.Server-aided revocable identity-based encryption［C］//Proc of the 20th European Symposium on Research in Computer Security.Cham：Springer，2015：286-304.

［25］Qin Baodong，Liu Ximeng，Wei Zhuo，et al.Space efficient revocable IBE for mobile devices in cloud computing［J］.Science China Information Sciences，2020，63（2）：article No.139110.

［26］Ma Xuecheng，Lin Dongdai.Generic constructions of revocable identity-based encryption［C］//Proc of International Conference on Information Security and Cryptology.Cham：Springer，2019：381-396.

［27］賴建昌，黃欣沂，何德彪，等.國(guó)密SM9數(shù)字簽名和密鑰封裝算法的安全性分析［J］.中國(guó)科學(xué)：信息科學(xué)，2021，51（11）：1900-1913.（Lai Jianchang，Huang Xinyi，He Debiao，et al.Security analysis of SM9 digital signature and key encapsulation［J］.Science in China：Information Sciences，2021，51（11）：1900-1913.）

［28］Wei Jianghong，Liu Wenfen，Hu Xuexia.Forward-secure identity-based signature with efficient revocation［J］.International Journal of Computer Mathematics，2017，94（7）：1390-1411.

［29］Yang Xiaodong，Ma Tingchun，Yang Ping，et al.Security analysis of a revocable and strongly unforgeable identity-based signature scheme［J］.Information Technology and Control，2018，47（3）：575-587.

［30］Zhao Jing，Wei Bin，Su Yang.Communication-efficient revocable identity-based signature from multilinear maps［J］.Journal of Ambient Intelligence and Humanized Computing，2019，10（1）：187-198.