高效的可撤銷SM9標識簽名算法

收稿日期：2022-02-18；修回日期：2022-03-31" 基金項目：國家自然科學基金資助項目（61872292）；青海省重點研發計劃資助項目（2020-SF-139）；青海省基礎研究計劃資助項目（2020-ZJ-701）

作者簡介：張博鑫（1996-），男，陜西咸陽人，碩士，主要研究方向為公鑰密碼學；耿生玲（1970-），女（藏族），青海都蘭人，教授，副院長，博士，主要研究方向為物聯網、大數據、數據挖掘；秦寶東（1982-），男（通信作者），江蘇徐州人，教授，碩導，博士，主要研究方向為公鑰密碼學基礎理論及應用（qinbaodong@xupt.edu.cn）．

摘 要：SM9-IBS是我國在2016年公布的一種標識簽名算法行業標準。標識簽名算法雖然降低了系統管理用戶公鑰的復雜性，但是卻存在密鑰撤銷的難題，此外SM9的特殊結構使得已有技術無法完全適用。為此，提出了一種可撤銷SM9標識簽名算法，可快速實現對用戶簽名權限的撤銷和更新操作。該算法引入一棵完全子樹，密鑰中心借助該樹為每個合法用戶生成臨時簽名密鑰，只有使用該密鑰生成的簽名才可以通過簽名驗證。在安全性方面，該算法在隨機預言機模型中被證明在適應性選擇消息和標識攻擊模型下滿足存在性不可偽造；在效率方面，該方案在密鑰更新階段當系統用戶數量較大、被撤銷用戶數量較少時，密鑰中心更新用戶簽名密鑰的時間開銷遠小于Boneh等人的更新技術。

關鍵詞：標識密碼系統；SM9簽名算法；密鑰撤銷；完全子樹

中圖分類號：TP393.04"" 文獻標志碼：A

文章編號：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］首次提出了標識密碼（identity-based cryptosystem）的概念，包括標識加密算法（identity-based encryption，IBE）和標識簽名算法（identity-based signature，IBS）。它可以采用用戶的唯一標識，如身份證號、手機號、電子郵件地址等作為用戶公鑰，由密鑰中心根據系統密鑰以及用戶標識生成相應的用戶私鑰。與傳統公鑰密碼算法相比，標識密碼算法簡化了PKI/CA應用中的證書分發和公鑰交換過程，降低了密鑰和證書管理的復雜性。2000年，Sakai等人［2］發表了一篇使用橢圓曲線對提出的基于身份的密鑰共享方案。直到2001年，Boneh和Cocks等人［3，4］才分別給出首個標識加密算法的構造。隨后，美國、英國和日本開始設計相應的算法［5～8］。

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

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

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

1 基礎知識

1.1 符號說明

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

1.2 雙線性映射

令Euclid Math OnePAp（1λ）表示一個雙線性對群生成算法，輸入1λ為安全參數，輸出為（e，Euclid Math TwoGAp1，Euclid Math TwoGAp2，Euclid Math TwoGApT，p，g，h），其中Euclid Math TwoGAp1、Euclid Math TwoGAp2和Euclid Math TwoGApT是階為素數p的循環群，映射e：Euclid Math TwoGAp1×Euclid Math TwoGAp2→Euclid Math TwoGApT為雙線性對，g和h分別是Euclid Math TwoGAp1和Euclid Math TwoGAp2的生成元。一個雙線性映射應該滿足以下性質：a）雙線性性，對于任意的α，β∈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）可計算性，對于任意的g和h，存在有效多項式時間算法計算e（g，h）。

1.3 困難問題假設

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

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

1.4 SM9-IBS標識簽名算法

SM9標識簽名算法（簡稱SM9-IBS算法）包括四個（概率）多項式時間算法：

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

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

msk=s（2）

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

b）用戶密鑰提取SM9.Extract（msk，id）。對于身份標識為id的用戶，密鑰生成中心為用戶計算簽名私鑰為

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

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

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

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

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

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

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

2 CS-SM9-RIBS標識簽名算法

2.1 RIBS的定義

圖1給出了可撤銷標識數字簽名算法的系統模型，它包含以下四個實體：

a）密鑰中心（KGC），主要負責產生系統主公鑰mpk和主私鑰msk，為身份標識為id的用戶生成長期簽名密鑰dsid，生成更新密鑰集合ukt，維護用戶撤銷列表RL及一個與所有用戶身份標識id對應的身份二叉樹tree。

b）數據簽名者（DS），主要負責計算原始消息M的數字簽名結果σ。

c）存儲服務器（SS），主要負責存儲用戶的簽名。

d）簽名驗證者（SV），主要負責對接收到的簽名σ進行合法性驗證。

定義2 RIBS的定義。一個RIBS算法包含系統參數生成算法、用戶注冊算法、未撤銷用戶的更新節點生成算法、更新密鑰生成算法、臨時簽名密鑰生成算法、簽名算法、驗證算法和用戶撤銷算法八個（概率）多項式時間算法，具體如下：

a）系統參數生成Setup（1λ）。該算法由密鑰中心負責執行，它的輸入為安全參數λ，輸出為系統的主公鑰mpk和主私鑰msk。此外，密鑰中心維護一個初始化為空集的撤銷列表RL，以及一個與所有用戶身份標識id對應的滿二叉樹tree。

b）用戶注冊Regist（msk，id）。該算法由密鑰生成中心負責執行，它的輸入為系統的主私鑰和用戶的身份標識id，將用戶的身份標識id加入到tree，并輸出用戶的長期簽名密鑰dsid。

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

d）更新密鑰UpdateK（msk，t，KUNodes）。該算法由密鑰中心執行，輸入為系統主私鑰msk、時間t以及未撤銷結集合KUNodes，輸出為更新密鑰集合ukt，并通過公開信道廣播給系統用戶。

e）臨時簽名密鑰生成TempK（dsid，ukt）。該算法由數據簽名者執行，它輸入用戶的長期簽名密鑰dsid和更新密鑰集合ukt，若該用戶未被撤銷，則算法輸出為用戶的臨時簽名密鑰tsdid，t（該簽名密鑰不僅包含了用戶的身份id和更新時間t，同時也包含了對應的更新節點信息θ）。

f）簽名Sign（tsdid，t，M）。該算法由數據簽名者執行，它的輸入為原始消息M、用戶臨時簽名密鑰tsdid，t，計算出消息M的簽名σ，該簽名包含了時間周期和更新節點信息。最后，將消息和簽名（M，σ）一同發送給存儲服務器進行儲存。

g）驗證Verify（id，M，σ）。該算法由簽名驗證者執行，算法的輸入為簽名者的身份標識id、消息M和簽名σ，輸出簽名的驗證結果，若簽名合法，則輸出1，否則輸出0。

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

2.2 安全模型

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

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

a）系統建立。挑戰者通過運行系統參數生成算法Setup（1λ），生成系統主公鑰mpk和主私鑰msk，并初始化一個空的密鑰撤銷列表RL和一個滿二叉樹tree，挑戰者將系統公鑰mpk發送給攻擊者。

b）詢問。攻擊者可以適應性地進行以下詢問，詢問的次數為多項式次。

（a）用戶長期簽名密鑰詢問。挑戰者初始化一個空集合L1，當攻擊者詢問身份標識為id的用戶長期簽名密鑰時，挑戰者通過執行用戶注冊算法Regist（msk，id）生成密鑰dsid并返回給攻擊者；同時，挑戰者將身份標識id添加到集合L1中。

（b）更新密鑰詢問。當攻擊者詢問t時刻的更新密鑰時，挑戰者首先執行更新節點生成算法KUNode（tree，RL，t）得到t時刻的更新節點集合KUNodes；然后執行更新密鑰生成算法UpdateK（msk，t，KUNodes）得到t時刻的更新密鑰集合ukt，并將它返回給攻擊者。

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

（d）用戶撤銷詢問。當攻擊者詢問t時刻的標識為id的用戶撤銷時，挑戰者將（t，id）添加到用戶撤銷列表RL中。

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

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

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

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

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

2.3 算法設計

本節利用完全子樹覆蓋技術設計一種可撤銷SM9標識簽名算法（記做CS-SM9-RIBS）。具體構造如下：

a）系統參數生成Setup（1λ）。在輸入安全參數1λ后，生成系統參數的過程如下：

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

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

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

（b）輸出系統的主公鑰mpk和主私鑰msk如下：

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

msk=s（7）

b）用戶注冊Register（msk，id）。密鑰中心在收到身份標識為id的用戶注冊請求后，為用戶注冊生成一個長期簽名密鑰的過程如下：

（a）密鑰中心使用SM9的密鑰提取算法為標識id的用戶生成簽名密鑰dsid，即

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

（b）密鑰中心選擇一個與用戶身份標識匹配的葉子節點，將id添加到tree上；

（c）將用戶長期簽名密鑰dsid發送給用戶。

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

圖2和3給出了更新節點選擇算法的兩個具體示例。在該示例中，二叉樹的高度為4（用戶的身份標識長度為3 bit），加粗節點表示當前KUNodes所包含的更新節點，虛線節點表示被撤銷的用戶節點。在圖2中，無用戶被撤銷，KUNodes僅包含根節點，即{root}；在圖3中，標識id=3的用戶被撤銷，KUNodes={00，010，1}。

d）更新密鑰UpdateK（msk，t，KUNodes）。在輸入系統密鑰msk、時間t以及更新節點集合KUNodes后，密鑰中心首先計算由時間和更新節點組成的更新標識集合UID={t‖θ}θ∈KUNodes。對于集合UID中的每個標識uid=t‖θ，調用SM9的密鑰提取算法生成相應的標識密鑰，即

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

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

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

密鑰中心通過公開信道廣播給系統用戶。

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

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

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

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

（b）根據臨時簽名密鑰恢復出用戶的長期簽名密鑰dsid、更新密鑰ukt，θ以及更新節點信息θ，并令=M‖t‖θ（假設不同的消息、時間和更新節點級聯的結果不同）。

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

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

（d）以ukt，θ作為簽名密鑰再次執行SM9簽名算法，生成消息的第二部分簽名σ2=（h2，S2），即

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

（e）令σ=（σ1，σ2，t‖θ）為最終簽名發送給存儲服務器進行存儲。

g）簽名驗證Verify（id，M，σ）。在輸入簽名者的身份標識id、消息M和簽名σ后，簽名驗證過程如下：

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

（b）驗證者計算=M‖t‖θ，使用簽名者的身份標識id利用SM9簽名驗證算法對消息和簽名σ1進行驗證，驗證結果記為b1，即

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

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

（c）驗證者使用更新標識t‖θ利用SM9簽名驗證算法對消息和簽名σ2進行驗證，驗證結果記為b2，即

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

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

（d）上述驗證均通過，算法返回1。

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

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

3 安全性分析

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

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

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

b）詢問。B通過如下方式回答攻擊者的詢問：

（a）用戶長期簽名密鑰詢問。當攻擊者A詢問身份標識為id的用戶長期簽名密鑰時，B將id發送給SM9-IBS的挑戰者，從而獲取身份標識為id的密鑰dsid并將它返回給攻擊者A，同時A將（id，dsid）添加到集合L1中。

（b）更新密鑰詢問。當A詢問t時刻的更新密鑰時，B首先根據算法KUNode（tree，RL，t）計算t時刻的更新節點集合KUNodes；然后確定更新節點標識集合UID={t‖θ}θ∈KUNodes。對于集合UID中的每個標識t‖θ，B詢問SM9-IBS挑戰者，獲取該標識的密鑰dst‖θ。B將密鑰集合ukt={dst‖θ}θ∈KUNodes發送給A，同時B將所有（t‖θ，dst‖θ）添加到集合L1中。

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

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

c）偽造。當攻擊者A結束上述詢問后，輸出一個偽造的簽名信息（M*，σ*）以及挑戰身份標識id*和時間t*。

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

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

4 性能分析

目前，除了直接應用Boneh-Franklin［3］通用密鑰撤銷思想可以構造針對SM9-IBS的密鑰撤銷算法外，還沒有公開發表針對SM9-IBS的密鑰撤銷算法，但是存在一些優秀的針對其他標識身份簽名的密鑰撤銷算法，如文獻［19，28～30］。為此，本章首先從理論和實驗兩個角度分析和比較與SM9-IBS相關的密鑰撤銷算法的性能，包括本文提出的基于完全子樹密鑰撤銷技術的CS-SM9-RIBS算法、原始SM9-IBS簽名算法［9］以及應用Boneh-Franklin［3］通用密鑰撤銷技術的BF-SM9-RIBS算法；再從理論上分析本文提出的CS-SM9-RIBS算法與國際上其他可撤銷標識簽名算法的優勢。

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

在BF-SM9-RIBS算法中，用戶只需要保存每個周期的臨時密鑰，而無長期密鑰，每個周期的臨時簽名密鑰由密鑰中心臨時生成的更新密鑰構成。更新用戶簽名密鑰的策略是將用戶的身份標識id與時間周期t級聯的結果id‖t作為當前時刻簽名的簽名公鑰，并將相應的私鑰通過安全信道發送給對應的未撤銷用戶。因此，更新用戶密鑰的復雜度為O（N-R），與系統用戶數量呈線性增長。對于本文算法，采用完全子樹技術更新用戶密鑰，在平均情況下更新密鑰的數量僅為O（R log（N/R））且可以在公開信道上進行傳輸。

從表1中可以看出，BF-SM9-RIBS和CS-SM9-RIBS兩種算法都支持用戶密鑰撤銷功能，同時保留了原始SM9-IBS算法的系統參數。在BF-SM9-RIBS算法中，用戶無須存儲長期簽名密鑰并且臨時簽名密鑰僅為一個群元素；在CS-SM9-RIBS算法中，用戶需要存儲一個長期簽名密鑰，盡管臨時簽名密鑰包含兩個群元素，但是它包括了用戶的長期簽名密鑰，無須額外空間存儲該群元素。在簽名大小、簽名時間和驗證時間方面，本文的CS-SM9-RIBS算法是原始SM9-IBS算法的兩倍，這是因為前者為了實現用戶密鑰的撤銷功能增加了一個額外的簽名操作。BF-SM9-RIBS算法在參數大小和計算效率方面與原始SM9-IBS算法幾乎一樣，但是該算法的密鑰更新復雜度非常高且不支持公開信道傳播更新密鑰。

本文在同一環境下對各算法進行了仿真實現，并測試了平均執行時間。編程測試環境為2.4 GHz Intel i5-9300H CPU、16.0 GB內存、Windows 10家庭中文版操作系統。

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

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

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

從圖4可以看出，當系統用戶數量較大、被撤銷用戶數量較少時，密鑰中心利用完全子樹技術更新用戶簽名密鑰的時間開銷要遠遠小于Boneh和Franklin的直接密鑰更新技術。

最后從理論上比較CS-SM9-RIBS算法與國際上針對其他標識簽名的密鑰撤銷算法［19，28～30］的性能，進一步說明CS-SM9-IBS可撤銷標識簽名算法的優勢，結果如表3所示。在這些算法中，除了文獻［30］基于三線性映射群外，其他算法都是基于標準的雙線映射群設計的。在表3中，除了文獻［30］外，其他文獻中的符號含義與表1中的符號一致。對于文獻［30］，Euclid Math TwoGAp2表示三線性映射中的一個階為素數p的群，而E和P分別表示三線性映射中的群元素指數運算和配對運算。

從表3可以看出，CS-SM9-RIBS算法的臨時簽名密鑰和簽名大小比其他方案小。簽名時間相較文獻［29］多一次指數運算，但是文獻［29］的更新密鑰時間與系統用戶數量呈線性增長；文獻［30］的更新密鑰僅與被撤銷用戶數量相關，但是該方案依賴三線性映射，沒有雙線性映射的理論基礎成熟。總體而言，本文提出的CS-SM9-RIBS可撤銷標識簽名算法的性能優勢更明顯。

5 結束語

針對SM9標識簽名算法存在的密鑰撤銷問題，本文提出了一種可撤銷SM9標識簽名算法，通過一棵完全子樹的輔助可以實現對用戶權限的控制，從而實現密鑰的撤銷和更新機制。通過理論分析和實驗表明，該方案相比于BF-SM9-RIBS算法在更新密鑰方面具有一定的優勢。在后續的工作中，存在以下問題值得進一步研究：該方案相比于BF-SM9-RIBS算法，在簽名和驗簽階段多消耗一倍的時間，可進一步研究耗時更少的SM9標識簽名算法的密鑰撤銷機制。

參考文獻：

［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，Franklin 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算法的移動互聯網身份認證方案研究［J］.信息網絡安全，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］姚英英，常曉林，甄平.基于區塊鏈的去中心化身份認證及密鑰管理方案［J］.網絡空間安全，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］馬曉婷，馬文平，劉小雪.基于區塊鏈技術的跨域認證方案［J］.電子學報，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］賴建昌，黃欣沂，何德彪，等.國密SM9數字簽名和密鑰封裝算法的安全性分析［J］.中國科學：信息科學，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.