支持等式測試及密碼逆向防火墻的SM9 標識加密方案

熊 虎 林 燁 姚 婷

（電子科技大學信息與軟件工程學院 成都 610054）

（網絡與數據安全四川省重點實驗室（電子科技大學） 成都 610054）

（xionghu.uestc@gmail.com）

云計算的快速發展帶動了云存儲的普及，越來越多的用戶和企業選擇將數據存儲在云服務器中[1].云服務器通常由不可信第三方維護和管理，存在諸多安全隱患.如果將數據直接存儲在云端，可能會使數據被未授權實體訪問，從而導致隱私泄露.一種保護數據隱私和實現安全數據共享的方式是采用公鑰加密算法將數據加密后再存儲到云服務器[2]，但這種方式極大地阻礙了數據的可用性.當用戶對存儲在云服務器的加密數據進行搜索時，最直接的方法是將所有加密數據下載到本地后執行解密再對明文信息進行搜索，顯然這種方法極其繁瑣且低效.

為了解決數據機密性和可搜索性之間的矛盾，Boneh 等人[3]提出了支持關鍵詞檢索的公鑰加密的概念.在PKEKS 系統中，發送者利用接收者的公鑰和關鍵詞生成關鍵詞密文，并附在對應的文件密文后上傳到云服務器.接收者可以利用自己的私鑰和關鍵詞生成陷門上傳至云服務器，隨后云服務器利用陷門對關鍵詞密文執行檢索以判斷關鍵詞密文是否包含陷門中嵌入的關鍵詞.由于在檢測過程中云服務器無法獲取密文對應的關鍵詞信息以及接收者私鑰.大量的PKEKS 方案被提出以進一步提升公鑰可搜索加密的安全性[4-5]、效率[6-7]和功能[8].盡管PKEKS 支持對于密文的搜索功能，但其存在功能上的限制：無法對不同公鑰加密的2 條信息進行檢索.同時還存在著嚴重的安全隱患：關鍵詞空間遠小于密鑰空間，攻擊者可以借此實施關鍵詞猜測攻擊.

為了解決上述問題，Yang 等人[9]在2010 年提出了支持等式測試的公鑰加密（public-key encryption with equality test,PKEET）方案.PKEET 允許任何用戶對不同公鑰加密生成的密文進行對比以判斷其中是否包含相同的明文.由于對比的密文空間遠大于密鑰空間，關鍵詞猜測攻擊無法對PKEET 系統生效.受Yang 等人[9]的啟發，國內外學者圍繞PKEET 的授權測試[10-11]、通用構造[12]和應用場景（無證書[13]、簽密[14]、異構[15]）等展開大量研究，一系列具有等式測試功能的加密方案被陸續提出.在傳統支持等式測試的公鑰加密方案中，公鑰是一個不可讀的字符串，需要公鑰基礎設施[16]（public key infrastructure,PK?）系統來簽發公鑰證書以綁定用戶的身份與公鑰.公鑰證書包括用戶的身份信息、權威機構的簽名和各種參數，以結構化數據的形式存儲.這種復雜且昂貴的證書管理方式在實際應用場景中帶來了棘手的證書管理問題.基于此，Ma[17]受標識密碼體制思想啟發[18]，構造了支持等式測試的標識加密（identity-based encryption with equality test，?BEET）體制.在?BEET 中，用戶的公鑰根據其身份信息生成，而用戶的私鑰由私鑰生成中心（private key generator，PKG）構建.

目前已有的?BEET 方案雖然避免了證書管理的問題，卻存在著嚴重的安全隱患：大部分?BEET 方案都難以抵抗滲透攻擊.斯諾登事件表明[19]，攻擊者可以在正常使用條件下秘密設置后門以泄露用戶隱私.受此啟發，Bellare 等人[20]提出的算法篡改攻擊（algorithm-substitution attacks，ASA）表明攻擊者可以非法占據用戶的個人設備來篡改加密算法，從被篡改的密文中獲取明文信息.具體來說，Bellare 等人[20]構建了顛覆加密（subverting encryption）框架，對ASA的受害者實施?V 篡改攻擊（?V-replacement attacks）和偏密文攻擊（the biased-ciphertext attack）.攻擊者利用顛覆密鑰篡改隨機化輸入?V，繼而跟蹤篡改密文以獲取明文.目前大量的無狀態隨機化密碼算法被證明幾乎無法抵抗這類ASA.因此，一旦用戶遭遇ASA，云服務器上的所有加密數據都有被泄露的風險.考慮到ASA 的危害性，密碼逆向防火墻（cryptographic reverse firewalls，CRF）的概念由Mironov 等人[21]在斯諾登事件之后提出.CRF 可以被認為是部署在用戶與外部世界的一個實體，通過重隨機化用戶發送和接收的信息將其映射到與原始輸出相同的空間中，達到抵抗隱私泄露的作用.CRF 具有3 個性質：維持功能性、保留安全性和抵抗滲透性.到目前為止，CRF 已被成功應用于密鑰協商協議[22]、基于屬性的加密體制[23]和基于簽名的不經意電子信封[24].將CRF 部署在云服務器與用戶之間，分別負責用戶密文與陷門的重隨機化.由于用戶輸出的是重隨機化結果，即便算法遭到篡改，用戶隱私也不會泄露.基于此，有必要為?BEET 構建CRF.

另外，目前?BEET 都是基于國外密碼算法設計且存在計算與通信開銷大的問題，還沒有出現支持國產商用密碼算法的高效等式測試方案.SM9 作為一種具有效率優勢的雙線性對標識密碼算法（identitybased cryptographic algorithm），可以良好地拓展至?BEET 領域中.2016 年我國國家密碼管理局正式發布SM9 密碼算法，其相關標準為“GM/T 0044—2016 SM9 標識密碼算法”.SM9 標識密碼算法主要包括4個部分：數字簽名算法、密鑰交換協議、密鑰封裝機制和標識加密算法.其中SM9 標識加密算法于2021年正式成為國標（?SO/?EC 18 033-5:2015/AMD 1:2021）.雖然SM9 在密碼技術和網絡安全領域占據越來越重要的地位，但關于SM9 在云環境安全下的研究卻寥寥無幾.因此，為了實現我國密碼算法國產自主，提高其在信息安全領域的核心競爭力，亟需推進國密算法在云計算場景中的研究應用.基于此，本文提出了一種支持等式測試并具有密碼逆向防火墻的SM9標識加密方案（SM9 identity-based encryption scheme with equality test and cryptographic reverse firewalls，SM9-?BEET-CRF）.本文的貢獻有3 點：

1）本文將SM9 標識加密算法應用于等式測試這一密碼學原語，提出了支持等式測試的SM9 標識密碼方案（SM9 identity-based encryption scheme with equality test，SM9-?BEET）.利用SM9 是標識密碼算法這一性質，避免了傳統等式測試算法中證書管理的問題.與傳統?BEET 方案相比，具有更強的安全性和計算開銷的優勢.同時，豐富國產商用密碼算法在云計算領域的研究.

2）解決傳統?BEET 體制難以抵抗滲透攻擊的問題.本文將CRF 部署在用戶與云服務器之間的上行信道，分別實現用戶密文、陷門的重隨機化.攻擊者即使非法占據用戶設備，由于其輸出結果要經過CRF 的處理，無法造成明文信息泄露.

3）本文實現了形式化的安全性證明.嚴謹的安全性分析證明其滿足選擇密文攻擊下的不可區分性（?ND-CCA）和選擇密文攻擊下的單向性（OW-CCA）.CRF 的設置使其具備抵抗算法篡改攻擊的能力.經過大量的實驗仿真證明，SM9-?BEET-CRF 在計算與通信開銷上具有一定的優勢，適用于云計算場景.相關工作有：

1）支持等式測試的公鑰加密體制.支持等式測試的公鑰加密方案首先由Yang 等人[9]在2010 年提出.該方案允許任何用戶對不同公鑰加密的密文進行比較，解決了關鍵詞檢索公鑰加密方案的局限性.接下來，Tang[25]為PKEET 提出了具有細粒度的授權機制，以確保只有被授權的用戶才有能力執行等式測試.此外，Tang[10]提出了混合粒度授權的支持等式測試的公鑰加密方案（all-or-nothing PKE-ET，AoNPKE-ET）來實現粗細粒度授權.然而，在實際中云服務器與用戶需要交互來授權，導致了方案的不可拓展性.為應對這一挑戰，Tang[26]和Ma[11]分別提出了帶有靈活授權機制的等式測試方案，其基本思想是用戶單獨對云服務器進行授權.為了解決PKEET 中的密鑰管理問題，Ma[17]將標識加密體制集成到PKEET 中，提出一種?BEET 方案.Qu 等人[13]提出的無證書等式測試加密方案（certificateless-based encryption with equality test，CLEET），旨在同時避免密鑰托管和證書管理的問題.Wang 等人[14]將簽密的概念引入等式測試中，有效降低了計算和通信開銷.Xiong等人[15]提出的異構簽密等式測試方案（heterogeneous signcryption scheme with equality test，HSC-ET），則實現了?BE 與PKE 的異構等式測試系統.目前已有的PKEET 體制難以抵抗滲透攻擊.

2）密碼逆向防火墻.斯諾登事件爆發后，為了保護用戶隱私和維持密碼方案安全性，Mironov 等人[21]提出CRF 的概念.CRF 位于用戶計算機與外部世界之間，通過修改用戶設備輸入和輸出，為受到篡改算法攻擊的用戶提供安全保護.2016 年，Dodis 等人[22]設計了一種具有逆向防火墻的消息傳輸協議，縮短公鑰交換輪數至4 輪.同年，Chen 等人[24]基于可延展的平滑映射哈希函數（smooth projective Hash function，SPHF）為多個密碼協議設計了CRF 框架.2018 年，Ma 等人[23]將逆向防火墻的概念引入屬性基加密體制，提出了一種基于密文在線/離線屬性的加密算法.2019 年，Zhou 等人[27]提出具有逆向防火墻的標識加密體制（identity-based encryption with cryptographic reverse firewalls，?BE-CRF），為?BE 設計了2 種CRF方案.目前還不存在具有逆向防火墻的PKEET 方案.

1 基礎知識

1.1 非對稱雙線性對

給定3 個循環群G1,G2,GT，它們的階均為素數N，P1為G1的生成元，P2為G2的生成元，存在非對稱雙線性對e:G1×G2→GT，滿足3 個條件：

1）雙線性.對任意P∈G1,Q∈G2,a,b∈ZN，有e([a]P,[b]Q)=e(P,Q)ab.

2）非退化性.e(P1,P2)≠1.

3）可計算性.對任意P∈G1,Q∈G2,存在有效 的算法計算e(P,Q).

1.2 BDH 假設

BDH 假設首先由Boneh 等人[28]在對稱雙線性配對中提出，然后被拓展到非對稱雙線性對中.本文使用Boyen 等人[29]在非對稱雙線性對中推廣的BDH假設.

1）BDH 問 題.給 定 (P1,P2,[a]P1,[a]P2,[b]Pi,[c]Pj)，其中i,j∈{1,2}，計算e(P1,P2)abc是困難的.

2）BDH 假設.給定一個BDH 問題實例，不存在一個PPT 攻擊者 A具有不可忽略的優勢計算出e(P1,P2)abc.其中 A的優勢被定義為

1.3 密碼逆向防火墻（CRF）

CRF 位于用戶計算機與外部實體之間，只能修改用戶的輸入輸出消息.對于用戶而言，他們并不知道CRF 的存在.

CRF 是一種具有狀態的算法 W，它以當前狀態和消息作為輸入，輸出更新后的狀態和消息.對于初始狀態為 σ的參與方P=(receive,next,output)和逆向防火墻 W，它們的組成被定義為

當組成方 W?P參與協議時，W的狀態被初始化為系統公開參數params，如果 W是與參與方P共同組成的，則我們稱 W為參與方P的逆向防火墻.

顯然，參與方P希望獲得管理并部署多臺防火墻的權力.這種多個防火墻的組合(W?W?…?W?P)只會增強系統的安全性，而不會破壞其初始協議的功能.

定義1.CRF 具有維持功能性.對任意逆向防火墻 W與參與方P，令當任意多項式邊界k≥2 時，令在k≥1的協議P 中，如果維持了參與方Pi的功能 F，也就是說當時，CRF 具有維持功能性.

定義2.CRF 具有保留安全性.對滿足安全性 S，功能 F 的協議 P 與逆向防火墻 W：

定義3.CRF 具有抵抗滲透性.CRF 具有阻止參與方P對消息篡改泄露的能力.使用Mironov 等人[21]定義的泄露游戲LEAK(P,P,J,W,λ)，如圖1 所示：P代表密碼協議，P為協議正常參與方，J代表被敵手控制的協議參與方，W為逆向防火墻，λ表示系統參數代表被敵手控制的協議參與方，為協議運行后的狀態，敵手在游戲LEAK中的優勢被定義為

Fig.1 ?llustration of LEAK圖1 LEAK 示意圖

與定義2 相同，本文主要討論CRF 對于不破壞協議功能的ASA 安全性.

2 方案定義

本節我們給出了本文方案的系統模型SMP-?BEETCRF、形式化定義，并且通過考慮3 種不同的敵手來定義安全模型.

2.1 系統模型

系統模型如圖2 所示，在SM9-?BEET-CRF 中，存在5 種實體.

Fig.2 ?llustration of SM9-?BEET-CRF圖2 SM9-?BEET-CRF 示意圖

1）數據上傳者.生成密文并將其上傳到云服務器的實體.

2）數據接收者.可以從云服務器下載密文并解密，或者可以委托云服務器執行等式測試的實體.

3）云服務器.存儲密文，在收到用戶請求后可以執行等式測試但無法解密的實體.

4）密鑰生成中心（KGC）.為用戶秘密地生成并且分配密鑰的實體.

5）密碼逆向防火墻（CRF）.部署在用戶（數據上傳者和數據接收者）與云服務器的上行信道中，重隨機化用戶密文與陷門，再發送給云服務器的實體.

KGC 初始化系統，根據用戶的身份來生成其私鑰，并秘密傳輸給用戶.數據上傳者計算接收者的公鑰來生成密文，然后上傳到云服務器.密文在上傳過程中會受到CRF 的重隨機化處理，而數據上傳者并不知道有這個過程.在任何時候，數據接收者都可以從云服務器下載密文，并使用KGC 生成的私鑰來解密數據.當接收者想要測試其存儲在云服務器的密文時，可以利用自己的私鑰計算出陷門并將其發送給云服務器進行測試，但是并沒有給云服務器提供解密的能力.陷門在上傳過程中會受到CRF 的重隨機化處理，而數據接收者不會知道有這個過程.

2.2 形式化定義

SM9-?BEET-CRF 方案由8 個算法組成.

1）系統建立Setup.輸入安全參數k，KGC 運行該算法并生成系統公開參數params和系統主密鑰，包括消息空間.

2）私鑰提取KeyExtract.輸入系統公開參數params、用戶ID以及主私鑰s，KGC 運行該算法生成用戶身份所對應的私鑰d.

3）陷門生成Trapdoor.輸入用戶ID以及用戶私鑰d，輸出對應的陷門td.

4）加密Encrypt.輸入明文M和用戶ID，輸出密文C.

5）重隨機化密文ReEncrypt.輸入密文C，CRF 運行該算法輸出對應的重隨機化密文C′.

6）密文解密Decrypt.輸入密文C、用戶ID和用戶私鑰d，解密輸出明文M.

7）重隨機化陷門ReTrapdoor.輸入陷門td，CRF運行該算法輸出對應的重隨機化陷門td′.

8）等式測試Test.分別輸入IDA對應的密文CA和陷門tdA，IDB對應的密文CB和陷門tdB，云服務器執行等式測試，若CA和CB的內容為相同的明文，則輸出1，否則輸出0.

根據?BEET 的安全模型，SM9-?BEET 需要考慮3 種類型的敵手.

1）Ⅰ型敵手.這類敵手沒有目標用戶的陷門，不能執行等式測試，其目的是在2 個挑戰密文中做區分.我們針對這種類型的敵手定義了?BE-?ND-CCA安全游戲Game 1.

安全游戲Game 1 中讓 A1表示Ⅰ型敵手，挑戰者C 與 A1按如下順序進行游戲：

①系統建立Setup.挑戰者 C執行系統建立Setup算法生成系統參數params和主私鑰對.C保存主私鑰對并將params發送給 A1.

②階段1.A1可以自適應地執行查詢：

i）公鑰查詢.當接收到身份為IDi的公鑰詢問時，C 通過運用主私鑰對計算，生成公鑰Qi并發送給 A1.

ii）私鑰查詢.當接收到身份為IDi的公鑰詢問時，C 通過執行私鑰提取算法KeyExtract生成私鑰di并發送給 A1.

iii）解密查詢.當接收到身份為IDi以及密文C的密鑰解密詢問時，C執行密文解密算法Decrypt生成明文M并返回給 A1.

③挑戰.敵手 A1將身份ID*以及消息（二者長度相同）發送給 C，且在階段1，ID*對應的私鑰沒有被詢問到，則 C隨機選取 ρ ∈{0,1}，并且計算C*=Encrypt(Mρ,d*,ID*) 并發送給 A1.

④階段2.A1像在階段1 一樣發出詢問，但是ID*對應的私鑰以及密文C*不可以被詢問到.

⑤猜測.A1輸出 ρ′∈{0,1}.

定義4.如果對于任意多項式時間攻擊者 A1，在?ND-CCA游戲中的優勢都是可忽略的，則SM9-?BEET 方案是滿足?BE?ND-CCA 安全的.

2）Ⅱ型敵手.這類敵手擁有目標用戶密文的陷門，因此可以執行挑戰密文的等式測試，其目的是為了揭示挑戰密文對應的消息.我們針對這種類型的敵手定義了?BE-OW-CCA 安全游戲Game 2.

安全游戲Game 2 中讓 A2表示Ⅱ型敵手，挑戰者C 與 A2按如下順序進行游戲：

①系統建立Setup.挑戰者 C執行系統建立Setup算法生成系統參數params和主私鑰對.C保存主私鑰對并將params發送給 A2.

②階段1.A2可以自適應地執行查詢：

i）公鑰查詢.當接收到身份為IDi的公鑰詢問時，C 通過運用主私鑰對計算，生成公鑰Qi并發送給 A2.

ii）私鑰查詢.當接收到身份為IDi的公鑰詢問時，C通過執行私鑰提取算法KeyExtract生成私鑰di并發送給 A2.

iii）陷門查詢.當接收到身份為IDi的陷門詢問時，C 通過執行陷門生成算法Trapdoor生成陷門tdi并發送給 A2.

iv）解密查詢.當接收受到身份為IDi以及密文C的密鑰解密詢問時，C執行密文解密算法Decrypt生成明文M并返回給 A2.

③挑戰.敵手 A2將身份ID*發送給 C，且在階段1，ID*對應的私鑰沒有被詢問到.則 C隨機選取消息M*，計 算C*=Encrypt(M*,d*,ID*) 并發送給 A2.

④階段2.A2像在階段1 一樣發出詢問，但是ID*對應的私鑰、陷門以及密文C*不可以被詢問到.

⑤猜測.A2輸出M′.

定義5.如果對于任意多項式時間攻擊者 A2，在?BE-OW-CCA游戲中的優勢都是可忽略的，則SM9-?BEET 方案是滿足?BE-OW-CCA 安全的.

為證明CRF 的部署帶來的ASA 安全性，SM9-?BEET-CRF 還需考慮Ⅲ型敵手.

3）Ⅲ型敵手.其具備ASA 能力，在保持算法功能不變的前提下，可以替換除了CRF 重隨機化以外的算法，然后對系統發起攻擊.針對這種類型的敵手，我們可以證明CRF 的部署沒有改變原SM9-?BEET的功能與安全性，同時增強了ASA 安全性.基于此，我們定義了ASA 安全游戲Game 3.

安全游戲Game 3 中讓 A3表示Ⅲ型敵手，挑戰者C 與 A3按如下順序進行游戲.

①篡改階段.A3選擇一些篡改的算法Setup*，KeyExtract*，Encrypt*，Decrypt*，Trapdoor*，Test*發送給 C，C收到后用篡改算法來替換自己的原始算法.

②系統建立Setup.挑戰者 C執行系統建立Setup*算法生成系統參數params和主私鑰對.C保存主私鑰對并將params發送給 A3.

③階段1.A3可以自適應地執行查詢：

i）公鑰查詢.當接受到身份為IDi的公鑰詢問時，C通過運用主私鑰對計算，生成公鑰Qi并發送給 A3.

ii）私鑰查詢.當接受到身份為IDi的公鑰詢問時，C執行私鑰提取算法KeyExtract*生成私鑰di并發送給 A3.

iii）陷門查詢.當接受到身份為IDi的陷門詢問時，C執行陷門生成算法Trapdoor*生成陷門tdi，然后運行陷門重隨機化算法ReTrapdoor生成陷門tdi的重隨機化陷門并發送給 A3.

iv）解密查詢.當接受到身份為IDi以及密文C的密鑰解密詢問時，C執行密文解密算法Decrypt*生成明文并返回給 A3.

④挑戰.敵手 A3將身份ID*以及 消息（二者長度相同）發送給 C，且在階段1，ID*對應的私鑰沒有被詢 問到，則 C 隨機 選取ρ ∈{0,1}，并且計 算C*=Encrypt*(Mρ,d*,ID*)，然后再計算C*′=ReEncrypt(C*)并發送給 A3.

⑤階段2.A3像在階段1 一樣發出詢問，但是ID*對應的私鑰以及密文不可以被詢問到.

⑥猜測.A3輸出 ρ′∈{0,1}.

定義6.如果對于任意多項式時間攻擊者 A3，在ASA 游戲中的優勢都是可忽略的，則SM9-?BEET-CRF 方案是滿足ASA安全的.

3 具體方案

本文方案由8 個算法組成，具體構造過程介紹如下.

1）系統建立Setup.

②KGC 隨機選取s,s′∈[1,N-1]作為主私鑰對(s,s′)，并計算主公鑰Ppub1=[s]P1，Ppub2=[s′]P1.

③獲取KGC公布的5個哈希函數：H1:{0,1}*→H2:GT→G2，H3:G1→{0,1}*，H4:{0,1}*→G2，H5:GT→{0,1}*.

④使用SM9 規定的密鑰派生函數KDF(Z,klen)，輸入比特串Z、非負整數klen，輸出長度為klen的密鑰數據比特串K.

⑤消息認證碼函數MAC(K2,Z).輸入為比特長度K2_len的密鑰K2，比特串消息Z.其作用是防止消息數據Z被非法篡改.

⑥拓展歐幾里得函數EUC(r).輸入r∈[1,N-1]，運行拓展歐幾里得算法計算輸出r的逆元.

2）私鑰提取KeyExtract.輸入系統公開參數params、用戶身份IDA和主私鑰對s，KGC 按①～③方式生成IDA的私鑰dA：

①在有限域FN上計算t1=H1(IDA)+s，若t1=0則需要重新產生主私鑰；

③然后計算dA=(dA1,dA2)，此處的 (s,s′)是主私鑰對，即

3）陷門生成Tra pdoor.輸入用戶身份IDA，私鑰dA.輸出陷門

4）加密Encrypt.輸入系統公開參數params、用戶身份IDA，運算生成用戶公鑰QA.對于消息長度為mlen比特的比特串M∈{0,1}*，mlen為密鑰K1的比特長度，K2_len為MAC(K2,Z) 中密鑰K2的比特長度，過程運算有：

5）重隨機化密文ReEncrypt.CRF 收到密文C=(C1,C2,C3,C4,C5,C6) 后，隨機選取r3∈[1,N-1]，然后計算C的重隨機化密文C′=(C1,C2,C3,C4,C5,[r3]C6)，并發送給云服務器.

6）解密Decrypt.輸入私鑰dA=(dA1,dA2) 和用戶身份IDA.

7）重隨機化陷門ReTrapdoor.輸入陷門td，CRF運行EUC(r3) 生成r3的逆元r4∈[1,N-1]，計算td的重隨機化陷門

③若e(Cα,5,Xβ)=e(Cβ,5,Xα)，則Mα=Mβ.

4 安全性分析

4.1 SM9-IBEET 正確性分析

本節首先對SM9-?BEET 進行正確性分析.

1）驗證密文解密過程的正確性

采用用戶私鑰d以及密文消息C=(C1,C2,C3,C4,C5,C6)來驗證：

2）計算消息認證碼函數

若u=C3,α，則消息認證完整性的結果通過，解密結果正確，輸出明文

3）驗證等式測試計算結果的正確性

第1 層計算的安全性如下所示，采用用戶的陷門以及部分密文驗證：

第2 層計算的正確性分析如下所示，帶入第1 層中計算的中間結果：

若Mα=Mβ，則等式測試的結果成立.

4.2 SM9-IBEET 安全性證明

定理1.假定嵌入的BDH 困難問題是不可破解的猜想成立，則表示本文提出的支持等式測試的SM9 算法是?BE-?ND-CCA 安全的.

證明.假設存在無法獲取目標用戶陷門且不能任意執行等式測試的Ⅰ型敵手 A1，其攻擊目的是破壞所提方案的語義安全，也即在安全游戲中對挑戰密文進行區分.如果敵手 A1可以成功破壞本文方案，則存在挑戰者 C能夠以不可忽略的優勢解決BDH 困難問題.給定 (P1,P2,[a]P1,[a]P2,[b]P1,[c]P1)，其中a,b,c∈C 的目標是計算出e(P1,P2)abc.C 與 A1的挑戰過程有7 個.

1）初始化.

C保存表格 LH1,LH2LH3,LH4,LH5,LKDF，初始化內容為空，用來模擬隨機預言機〈H1,H2,H3,H4,H5,KDF〉.設置空列表 LK來保存公鑰查詢的結果.

2）敵手 A1向 C 提出6 個詢問.

①H1-query.在任何時刻 A1可以詢問隨機預言機 H1，為了回答這些詢問，C 保存表格用來存取元 組 〈IDi,Ni〉，當接收到身份為IDi的 H1查詢時，C查找IDi對應的數值Ni，用H1(IDi)=Ni返回給 A1，并將〈IDi,Ni〉 添加到中.

②H2-query.在任何時刻 A1可以詢問隨機預言機 H2，為了回答這些詢問，C 保存表格用來存取元組 〈σ,?〉，C按2 個步驟回應：

i）如果詢問的IDi已經出現在的元組 〈σ,?〉中，C 用 ?來回復.

ii）否則，C隨機選取 σ ∈GT,? ∈G1，并將元組〈σ,?〉 插入中，然后用 ? 來回復 A1.

③H3-query.在任何時刻 A1可以詢問隨機預言機 H3，為了回答這些詢問，C 保存表格用來存取元組 〈C1,h3〉，如果詢問的C1存在 LH3中，返回h3給 A1；否則，C隨機選取h3∈{0,1}*并添加表項 〈C1,h3〉 到中，并返回h3給 A1.

④H4-query.在任何時刻 A1可以詢問隨機預言機 H4，為了回答這些詢問，C 保存表格用來存取元組 〈M,h4〉，如果詢問的M存在中，返回h4給 A1；否則，C隨機選取h4∈G1并 添加表項〈M,h4〉 到中，返回h4給 A1.

⑤H5-query.在任何時刻 A1可以詢問隨機預言機 H5，為了回答這些詢問，C 保存表格用來存取元組 〈w,h5〉，如果詢問的w存 在中，返回h5給 A1；否 則，C隨機選取h5∈{0,1}*并添加表項 〈w,h5〉 到中，返回h5給 A1.

⑥KDF-query.在任何時刻 A1可以詢問隨機預言機 KDF，為了回答這些詢問，C 保存表格 LKDF用來存取元組 〈Z,K〉，如果詢問的Z存在于 LKDF中，返回K給 A1；否則，C 隨機選取K∈{0,1}*并添加表項〈Z,K〉 到 LKDF中，返回K給 A1.

3）公鑰查詢.當接受到身份為IDi的公鑰詢問時，C按照如下方式回應：檢查列表如果i=κ，C 放棄，否則得到H1(IDi)=Ni；計算用戶公鑰Qi=[H1(IDi)]P1+Ppub1=NiP1+(γ-Nκ)P1=(γ-τi)P1，并將Qi發送給 A1.

4）私鑰查詢.當接受到身份為IDi的私鑰詢問時，C按照如下方式回應：檢查列表，如果i=κ，C放棄；否則得到H1(IDi)=Ni，計算用戶私鑰為

并將di,1和di,2發送給 A1.

7）猜測.A1輸出 ρ′∈{0,1}.C 從隨機選取一個元組 〈σ*,?*〉，并輸出σ*=e(P1,P2)abc作為BDH 實例的解.證畢.

定理2.假定嵌入的BDH 困難問題是不可破解的猜想成立，則表示我們提出的支持等式測試的國密SM9 算法方案是?BE-OW-CCA 安全的.

證明.假定存在可以獲取目標用戶陷門且可以執行等式測試的Ⅱ型敵手 A2，其攻擊目的是為了破壞所提方案的機密性，也即揭示挑戰密文對應的消息.如果敵手 A2可以成功破壞所提方案，則存在挑戰者 C能夠以不可忽略的優勢解決BDH 困難問題.給定(P1,P2,[a]P1,[a]P2,[b]P1,[c]P1)，其中C的目標是計算出e(P1,P2)abc.C 與A2的挑戰過程有8 個.

2）敵手 A2向 C 提出6 點詢問.

①H1-query.在任何時刻 A2可以詢問隨機預言機 H1，為了回答這些詢問，C 保存表格用來存取元組 〈IDi,Ni〉，當 接收到身份為IDi的 H1查詢時，C查找IDi對應的數值Ni，用H1(IDi)=Ni返回給 A2，并將〈IDi,Ni〉 添加到中.

②H2-query.在任何時刻 A2可以詢問隨機預言機 H2，為了回答這些詢問，C 保存表格用來存取元組 〈σ,?〉，C按2 個步驟回應：

i）如果詢問的IDi已經出現在的元組 〈σ,?〉中，C 用 ?來回復.

ii）否則，C隨機選取 σ ∈GT,? ∈G1，并將元組〈σ,?〉 插入中，然后用 ? 來回復 A2.

③H3-query.在任何時刻 A2可以詢問隨機預言機 H3，為了回答這些詢問，C 保存表格用來存取元 組 〈C1,h3〉，如果詢問的C1存 在中，返回h3給 A2；否則，C隨機選取h3∈{0,1}*并添加表項 〈C1,h3〉到中，并返回h3給 A2.

④H4-query.在任何時刻 A2可以詢問隨機預言機 H4，為了回答這些詢問，C 保存表格用來存取元組 〈M,h4〉，如果詢問的M存 在中，返回h4給 A2；否則，C隨機選取h4∈G1并 添加表項〈M,h4〉 到中，返回h4給 A2.

⑤H5-query.在任何時刻 A2可以詢問隨機預言機 H5，為了回答這些詢問，C 保存表格用來存取元 組 〈w,h5〉，如果詢問的w存 在中，返回h5給 A2；否 則，C隨機選取h5∈{0,1}*并添加表項 〈w,h5〉到中，返回h5給 A2.

⑥KDF-query.在任何時刻 A2可以詢問隨機預言機 KDF，為了回答這些詢問，C 保存表格 LKDF用來存取元組 〈Z,K〉，如果詢問的Z存在于 LKDF中，返回K給 A2；否則，C 隨機選取K∈{0,1}*并添加表項〈Z,K〉 到 LKDF中，返回K給 A2.

3）公鑰查詢.當接受到身份為IDi的公鑰詢問時，C按照如下方式回應：檢查列表如果i=κ，C放棄；否則得到H1(IDi)=Ni，計算用戶公鑰

并將Qi發送給 A2.

4）私鑰查詢.當接受到身份為IDi的私鑰詢問時，C按照如下方式回應：檢查列表如果i=κ，C放棄；否則得到H1(IDi)=Ni，計算用戶私鑰

并將di,1和di,2發送給 A2.

5）陷門查詢.當接受到身份為IDi的陷門詢問時，如果i=κ，C放棄；否則計算

并將di,1和di,2發送給 A2.

4.3 ASA 安全性

ASA 安全性要求SM9-?BEET-CRF 可以抵抗Ⅲ型敵手 A3的攻擊.其中敵手 A3具備ASA 能力，在保持算法功能不變的前提下，可以替換除了CRF 重隨機化以外的算法，然后對系統發起攻擊.

定理3.SM9-?BEET-CRF 中的CRF 具有維持功能性.

證明.維持功能性要求CRF 不影響原協議的功能與安全性，當數據上傳者將密文與陷門經由CRF上傳至云服務器后，可以得到與原協議相同的功能與安全強度.

數據上傳者運行加密算法Encrypt生成密文C=(C1,C2,C3,C4,C5,C6)并發送給CRF.CRF 重隨機化密文后得到C′=(C1,C2,C3,C4,C5,[r3]C6)，并將其上傳至云服務器.

當數據接收者需要解密時，從云服務器上下載密文，此時不需要經過CRF.解密過程的正確性通過用戶私鑰d以及密文消息來驗證：

u=為 KDF 函數結果右邊的K2_len比特）.

若u=C3,α，則消息認證完整性的結果通過，解密結果正確，輸出明文解密過程不受影響.

當數據接收者需要執行等式測試時，運行Trapdoor算法生成陷門td并發送給CRF.CRF 重隨機化陷門后得到并將td′上傳至云服務器.接下來驗證等式測試計算結果的正確性.

1）第1 層計算的安全性采用用戶的陷門以及部分密文驗證：

2）第2 層計算的正確性分析帶入第1 層中計算的中間結果：

若Mα=Mβ，則等式測試的結果成立.證畢.

定理4.SM9-?BEET-CRF 中 的CRF 具有弱保留安全性和預防泄露性.

證明.假定存在可以替換除CRF 重隨機化以外算法的Ⅲ型敵手 A3，其攻擊目的是破壞所提方案的機密性，也即通過篡改原始算法來泄露隱私信息.如果 A3可以成功破壞所提方案，使用篡改算法Setup*，KeyExtract*，Encrypt*，Decrypt*，Trapdoor*，Test*來替換原始算法.我們則將通過SM9-?BEET-CRF 的安全性游戲和原SM9-?BEET 安全性游戲的不可區分性，來證明CRF 滿足弱保留安全性和預防泄露性.本文考慮3 種安全游戲：

1）安全游戲Game 1.與第2 節中定義的Game 3相同.

2）安全游戲Game 2.與Game 1 的其他部分都相同，除了在陷門查詢階段，C用于生成陷門的算法為Trapdoor，而不是先執行Trapdoor*算法再執行ReTrapdoor算法.

3）安全游戲Game 3.與Game 2 的其他部分都相同，除了挑戰階段，C用于生成密文的算法為Encrypt，而不是先執行Encrypt*算法再執行ReEncrypt算法.事實上，Game 3 就是原基礎方案SM9-?BEET 的安全性游戲.

現在我們證明，Game 1 和Game 2，Game 2 和Game 3 分別具有不可區分性.

Game 1 和Game 2 之間，對于任何篡改算法Trapdoor*，其生成的陷門td′在經由CRF 的重隨機化算法ReTrapdoor后，由于數據的可延展性，td′會重新分布，被映射到與原始Trapdoor相同的輸出空間中.也就是說，即使敵手篡改了Trapdoor算法的實現，它也難以區分td′是由Trapdoor算法產生，還是由先執行Trapdoor*算法再執行ReTrapdoor產生.因此，Game 1 和Game 2 之間具有不可區分性.

Game 2 和Game 3 之間，對于任何篡改算法Encrypt*，其生成的密文C′在經由CRF 的重隨機化算法ReEncrypt后，由于數據的可延展性，C′會重新分布，被映射到與原始密文相同的輸出空間中.也就是說，即使敵手篡改了Encrypt算法的實現，它也難以區分C′由Encrypt算法產生，還是是由先執行Encrypt*算法再執行ReEncrypt產生.因此，Game 2 和Game 3之間具有不可區分性.

綜上所述，Game 1 與Game 3 具有不可區分性，SM9-?BEET-CRF 滿足與原方案相同的?BE-?ND-CCA安全性與?BE-OW-CCA 安全性.這種選擇密文攻擊下的不可區分性表明云服務器與用戶之間的CRF 具有弱保留安全性，Game 1，Game 2，Game 3 之間的不可區分性證明CRF 有弱抵抗滲透性.證畢.

5 方案對比

在本節中主要從計算開銷、通信開銷、安全性等方面對本文方案（SM9-?BEET-CRF）與其他等式測試的公鑰加密方案和支持關鍵詞檢索的公鑰加密文獻[4,6,11,13,15,17]進行比較.其中，文獻[4]為具有前向安全性的公鑰可搜索加密方案（FS-PKSE）；文獻[6]為帶有關鍵字搜索的公鑰認證加密方案（PAEKS）；文獻[11]為具有靈活授權機制的公鑰加密等式測試方案（PKEET-FA）；文獻[13]為支持等式測試的無證書公鑰加密方案（CLE-PKEET）；文獻[15]為支持等式測試的異構簽密方案（HSC-ET）；文獻[17]為支持等式測試標識加密方案（?BEET）.

為評估方案性能，將本文方案與其他方案在相同的環境下逐一對比，該環境配置的處理器為?ntel?Core? i7-8750H，內存為16 GB（RAM），在VMware軟件的虛擬機上運行，在PBC（pairing-based cryptography library）庫中實現雙線性對的接口，實現了雙線性對公鑰密碼體制的有效仿真，達到了1 024 b RSA 安全.

使用SM9 定義256 b 的BN 曲線，橢圓曲線方程為y2=x3+b來生成映射e:G1×G2→GT，嵌入次數為12，根據SM9 的參數配置PBC 庫中對應的算法，進行多次模擬后取平均值，與之前的文獻進行了對比，其中涉及的符號定義和密碼算法的執行時間定義分別如表1 和表2 所示.

Table 1 Symbols Definition表1 符號定義

Table 2 Execution Time of Cryptographic Operation表2 密碼操作的執行時間

為評估方案的通信開銷，考慮部署2 類無線傳感器節點平臺M?CAz[31]和Tmote Sky[32].其中M?CAz 配置的微控制器為ATmega128L，內存為4 KB（RAM）.Tmote Sky 配置的微控制器為MSP430，內存為10 KB（RAM）.采 用CC2420,2.4 GHz IEEE 802.15.4 作為射頻收發器標準，在 TinyOS 系統運行.使用文獻[33]的方法，在2 類傳感器節點架構體系上實現對公鑰密碼通信系統的有效仿真.

5.1 計算開銷對比

我們首先比較了不同方案，包括Enc 加密操作、Dec 解密操作和Test 等式測試操作的計算開銷.具體結果如表3 所示.

Table 3 Computation Cost Comparison of Different Schemes表3 不同方案的計算開銷對比

圖3（a）表示在模擬環境下，不同方案的加密時間隨消息數量的變化，雖然當消息數量增加到100 時，本文方案的時間開銷比文獻[4,6,11,15]大1.58 倍左右，但很明顯，與其他標識加密的等式測試的文獻[13,17]相比，本文方案的時間開銷要小得多.作為一種?BE-ET 體制，本方案在加密時間上的開銷是可以接受的.與本文方案相比，文獻[11]并沒有實現?BE體制，在實際場景中，存在著密鑰管理的問題；文獻[15]異構等式測試，只能實現PK? 端到?BE 端的測試環境，具有一定的限制；文獻[4,6]實現的可搜索加密，不能對密文解密，只支持關鍵詞搜索，無法搜索整段密文，搜索性有所降低.本文方案的等式測試功能，可以實現雙向密文的任意測試；用戶與測試者均采用標識加密的方法，避免了密鑰管理的問題；與其他標識加密的方案相比，降低了加密開銷.

Fig.3 Computation overhead comparison for different schemes圖3 不同方案的計算開銷對比

從圖3（b）可以得出，本文方案在解密過程的計算時間遠小于其他對比方案，具有解密開銷上的優勢.

從圖3（c）中得出，本文方案與文獻[13,17]在測試計算過程耗費的計算時間是相近的，文獻[4,11,15]在測試場景下耗費的時間要大于其他方案.文獻[4,6]實現的傳統可搜索加密并不能支持整段密文的測試，可以看出，本文方案在等式測試過程中耗費的時間是合理且具有一定優勢的.

5.2 通信開銷與功能對比

表4 表示的是不同方案在通信開銷與實際功能上的對比，可以看出本文方案與其他方案相比，具有更強的安全性與功能性.在實際應用場景中，本文方案實現的標識加密體制避免了證書管理的問題，大大降低在通信過程中的開銷.同時，支持等式測試的功能相比于其他可搜索加密文獻[4,6]具有更強的搜索性.CRF 的設置使得本文方案具備抵抗滲透攻擊的能力，這意味著在面對算法篡改攻擊這類威脅時本文方案提供了更高的安全性.值得注意的是，本文方案還是唯一一個支持國密SM9 算法的方案.

Table 4 Comparison of Communication Overhead and Function of Different Schemes表4 不同方案的通信開銷與功能對比

圖4 表示在模擬環境下，不同方案隨著用戶數量增加下各種通信開銷的對比.從圖4（a）（b）可以看出，本文方案享有最低的公鑰通信開銷與密文通信開銷.并且在圖4（c）中，本文方案的陷門開銷小于除了文獻[11]以外的所有方案的開銷.這是由于本文方案不僅實現了標識加密體制，在實際場景中避免了公鑰證書的通信開銷.同時還是所有文獻中唯一建立在非對稱雙線性配對基礎上的方案，這大大降低了在實際通信場景中的存儲開銷.由此可見本文方案具有通信開銷上的優勢，更適用于實際應用場景.

Fig.4 Comparison of communication overhead of different schemes圖4 不同方案通信開銷對比

總的來說，通過嚴格的實驗仿真與性能對比證明，本文方案在計算開銷與通信開銷上都具有一定的優勢.等式測試功能的引入，使本文方案具有比可搜索加密方案更強的搜索性；標識加密體制的拓展，解決了密鑰協商和證書管理的問題；逆向防火墻的部署，進一步提升了本文方案抵抗滲透攻擊與篡改攻擊的能力.本文方案不僅解決了SM9 密文難以搜索的問題，還解決了目前支持等式測試的標識加密體制下計算與通信開銷大、安全性弱的問題.同時，本文方案是國密SM9 密碼算法在云計算場景下的一次良好應用，對于推動我國密碼領域的安全研究也具有一定意義.

6 結論

針對已有?BEET 算法難抵抗滲透攻擊的問題，本文提出了一種支持等式測試并具有逆向防火墻的SM9 標識密碼方案SM9-?BEET-CRF，該方案可以運用于云服務器中加密數據的外包計算方案.本文方案在用戶與云服務器之間的上行信道分別部署了密碼逆向防火墻；形式化了本文方案的系統模型和定義，并考慮3 種不同的對手來定義安全模型；然后在BDH假設下的隨機預言機模型中證明了它的安全性；最后通過嚴格的實驗仿真和分析結果表明，本文方案比已有方法在解密與通信開銷方面具有一定的效率優勢.

作者貢獻聲明：熊虎提出了算法思路和實驗方案；林燁負責完成實驗并撰寫論文；姚婷協助完成實驗并修改論文.