基于國密SM9 的可搜索加密方案

張超，彭長根，3，丁紅發，許德權

（1.貴州大學計算機科學與技術學院 公共大數據國家重點實驗室，貴陽 550025；2.貴州大學 密碼學與數據安全研究所，貴陽 550025；3.貴州大學 貴州省大數據產業應用發展研究院，貴陽 550025；4.貴州財經大學 信息學院，貴陽 550025）

0 概述

云存儲技術的快速發展使得人們存儲、管理大量數據更加便捷，但是數據面臨泄露風險。為保護云服務器中的數據隱私，云存儲技術通常對原始數據進行加密，把加密后的密文數據上傳至云服務器，但是會給使用數據的用戶帶來不便。例如，當用戶需要檢索數據時，需要將全部密文數據下載到本地，在本地解密之后再執行檢索操作。為更好地解決云數據的安全問題，可搜索加密（Searchable Encryption，SE）技術應運而生，并得到研究人員的廣泛關注。SE 技術允許云服務器在密文場景下進行安全檢索，并將滿足檢索條件的密文數據返回給用戶，最后由用戶在本地將檢索結果解密，從而獲得自己需要的明文數據。

本文結合SM9 算法構造基于身份的可搜索加密方案。根據非對稱雙線性對的特性，同時結合SM9加密算法的密鑰形式，設計相應的索引生成算法、陷門生成算法和服務器檢索匹配算法。基于可證明安全理論，驗證該方案在隨機諭言模型下滿足密文不可區分性和陷門不可區分性。

1 相關工作

文獻［1］首次提出對稱可搜索加密（Symmetric Searchable Encryption，SSE）的概念，解決在密文環境下的搜索難題，實現了在對稱密碼體制下密文的搜索。文獻［2］基于布隆過濾器（Bloom Filter，BF）［3］設計滿足安全索引的SSE 方案，將檢索的時間復雜度改進為與文檔的數目呈線性關系。SSE 的計算效率較高，適用于大部分第三方存儲。文獻［4］提出公鑰可搜索加密（Public-key Encryption with Keyword Search，PEKS）方案，并基于文獻［5］利用雙線性對設計一個具體構造，適用于復雜的加密環境。PEKS 不用在發送者與接收者之間建立安全信道，因其實用性較強，而得到快速發展，其中基于身份加密的可搜索加密減少了建立和維護公鑰基礎設施（Public Key Infrastructure，PKI）的開銷，因此成為該領域的研究熱點。

文獻［6］提出帶關鍵字搜索的基于身份加密（Identity-Based Encryption with Keyword Search，IBEKS）方案，并給出一般化的轉換方法，將任意的選擇明文攻擊模式下不可區分安全且匿名的IBE 方案轉換為選擇明文攻擊模式下不可區分安全的PEKS 方案。文獻［7］提出一種基于身份的關鍵字搜索加密方案，不需要安全通道，但要求服務器是可信的。文獻［8］提出帶關鍵字搜索的閾值公鑰加密（Threshold Public-key Encryption with Keyword Search，TPEKS）和帶分布式私鑰生成器的基于身份匿名加密。文獻［9］提出模糊關鍵詞檢索，可以防范內部敵手和外部敵手的關鍵詞猜測攻擊。文獻［10］提出指定服務器的帶關鍵字搜索的基于身份加密方案，該方案不需要額外的安全信道。文獻［11］對可搜索加密進行探討和總結。文獻［12］提出一種具有隱藏結構的可搜索公鑰密文（Searchable Public-key Ciphertexts with Hidden Structure，SPCHS），提高了關鍵字搜索效率。文獻［13］對加密數據的關鍵字搜索技術進行研究，并對他們的效率和安全性進行分析。文獻［14］提出基于公鑰并且帶身份驗證功能的PEAKS 方案。文獻［15］結合格理論提出一種基于身份的可搜索加密方案，可以抵抗量子計算機的攻擊。文獻［16］設計基于身份的關鍵詞可搜索加密的廣播加密方案，以防范內部敵手的攻擊。文獻［17］提出基于身份的指定服務器用于加密郵件的可搜索認證加密方案。文獻［18］提出支持代理重加密的基于身份可搜索加密方案，支持搜索權限的高效共享。文獻［19］提出基于身份的動態可搜索加密方案，可以刪除指定身份的文件。文獻［20］提出在電子郵件系統中指定服務器的關鍵字搜索加密方案。文獻［21］提出一種基于生物識別身份的多關鍵字搜索（Biometric Identity-Based Multi-Keyword Search，BIBMKS）機制。文獻［22］提出身份認證權威輔助的基于身份可搜索加密，在保持效率和安全性的同時，減少存儲空間的開銷。

上述方案為達到一定的安全級別，多是基于安全參數較大的對稱雙線性對，且在方案中多次使用雙線性對運算，導致方案的計算效率降低。因此，通過優化方案設計，提高可搜索加密方案的檢索效率和安全性成為研究熱點。

從國家信息安全方面考慮，發展我國自己的加密算法勢在必行。2016 年，基于身份的SM9 密碼算法為國家商用密碼行業標準（GM/T 0044—2016），并于2018 年11 月被納入國際標準。SM9 密碼算法的密鑰長度為256 bit，采用運算速度快、安全性能高的R-ate 雙線性對［23］，可以有效減少Miller 算法循環次數，提高計算效率。近年來，SM9 密碼算法作為基于身份的密碼算法，受到越來越多的關注。

SM9 密碼算法使用安全參數較小的非對稱雙線性對，用戶的公私鑰分別在兩個循環群中產生，而現有的可搜索加密方案大多通過安全參數較大的對稱雙線性對來實現，計算效率相對較低［24］。由于用戶密鑰的形式不同，因此現有的可搜索加密方案并不能很好地與SM9 密碼算法相結合。

SM9 密碼算法在郵件系統、數據安全傳輸協議、物聯網安全平臺等場景中都有重要的應用，但由于缺少適應性強的可搜索加密方案，用戶難以對這些加密數據進行檢索，導致這些系統中的加密數據可用性較低。此外，通過為每個用戶提供一對額外的密鑰，以實現可搜索加密，但繁瑣的操作流程會給用戶的使用帶來不便。為解決該問題，結合以上對SM9 密碼算法的分析，本文設計基于SM9 密碼算法的可搜索加密（SM9-based Searchable Encryption，SM9SE）方案。方案中用戶的公私鑰對分別在不同的子群中生成，其形式與SM9 密碼算法的密鑰對一致，因此用戶可以用同一對密鑰完成數據的加解密和密文檢索操作，并且使用系統參數相對較小的非對稱雙線性對運算，從而提高計算效率。

2 基礎知識

2.1 雙線性對

假設n為正整數，(G1,+)和(G2,+)是兩個n階加法循環群，其零元分別記作O1和O2。又設(GT,g)為n階乘法循環群，其單位元記為1T。假設在群G1，G2，GT上計算離散對數是困難的。

2.2 基于雙線性對的困難性問題及假設

DBDH 假設：對于任何一個概率多項式時間敵手A，解決DBDH 問題的概率都是可忽略的，即Pr[0 ←A(Y)|β=0]-Pr[0 ←A(Y)|β=1]是可忽略的。

3 方案構造與安全模型

3.1 方案構造

本文方案使用的橢圓曲線及曲線參數與SM9 加密算法中所使用的參數一致。

本文SM9SE 方案由系統參數初始化算法、密鑰生成算法、索引生成算法、陷門生成算法和檢索匹配算法構成。

1）系統參數初始化算法SysSetup(λ)，輸入安全參數λ以生成一個基于循環群上的雙線性對映射(G1?G2)→GT，其中群G1、G2和GT的階為大素數q。PKG 隨機選擇整數s?[1,q-1]作為系統主密鑰保密存儲，然后計算系統公鑰Ppub=sP1，P1為循環群G1的生成元，P2為循環群G2的生成元。此外，PKG 選擇三個哈希函數。系統主密鑰對為(s,Ppub)，系統公共參數為

2）密鑰生成算法UserKeyGen(ID,s)，對于用戶A的唯一身份標識IDA，以及系統主私鑰s，PKG 在有限域FN上計算t1=H1(IDA)+s。若t1=0 則重新計算系統主密鑰并更新已有用戶的私鑰，否則計算t2=s×

用戶私鑰dA=[t2]P2，用戶公鑰的計算方法為QA=[H1(IDA)]P1+Ppub=[t1]P1。

3）索引生成算法BuildIndex(IDR,w)，對于接收者R 的唯一身份標識IDR以及關鍵字w。該算法隨機選擇r?[1,q-1]，計算并生成關鍵字對應的密文索引I=(I1,I2,I3)，并將其發送給服務器。其中

4）陷門生成算法Trapdoor(w′,dR)，文件接收者R運行該算法以生成檢索陷門，輸入要搜索的關鍵字w′和其私鑰dR。該算法選擇隨機數t?[1,q-1]，然后計算陷門信息T=(T1,T2)，并將其發送給服務器，其中T1=[t]Ppub，T2=[H2(w′)-t]?dR，并且H2(w′)-t≠0，否則重新選取t。

5）檢索匹配算法Test(I,T)，由服務器執行，給定安全密文索引I=(I1,I2,I3)和陷門T=(T1,T2)，服務器執行該算法來判斷接收到的陷門信息與其存儲的關鍵詞密文索引信息是否能正確匹配。如果匹配，則返回密文文件，若則匹配成功。

3.2 安全模型

本節通過以下兩個游戲來刻畫本文方案在面對內部敵手的離線關鍵詞猜測攻擊（Keyword Guessing Attack，KGA）時的語義安全。由于內部敵手所獲取的信息大于等于任意外部敵手所能獲取的信息，因此不再考慮外部敵手。這兩個游戲均由敵手A 和挑戰者B 交互完成。游戲1 是密文不可區分性游戲，游戲2 是陷門不可區分性游戲。

3.2.1 密文不可區分性游戲

在密文不可區分性游戲中，假設半誠實服務器就是敵手A，它會誠實執行用戶預設的操作，但是會嘗試獲取用戶數據的信息。密文不可區分性旨在防止敵手分辨出某個給定的密文是從兩個選定的關鍵詞（由敵手自己選定）中的哪一個加密而來，即密文不可區分性可以保證服務器在沒有獲得用戶授權的情況下無法私自對密文進行檢索操作。

1）初始化。挑戰者B 生成系統的公共參數Params 和主私鑰s，以及各個用戶的私鑰，然后將系統的公共參數Params 發送給敵手A。

2）詢問階段1。敵手A 可以適應性地向如下的隨機諭言機進行多項式時間次的詢問，以獲得用戶的私鑰、密文索引和陷門密文信息。其中，“適應性”是指敵手A 每次的詢問都會根據當前已知的信息來決定應該詢問的信息。挑戰者B 運行隨機諭言機，并按如下規則返回詢問結果：（1）Hash 諭言機OH，對于給定的輸入值，給敵手A 返回其哈希值；（2）密鑰諭言機OE，對于指定的用戶，給敵手A 返回該用戶的密鑰；（3）索引諭言機OC，給定關鍵詞及接收方ID，給敵手A 返回其對應的密文索引；（4）陷門諭言機OT，給定一個關鍵詞，計算并給敵手A 返回其對應的陷門。

3）挑戰。敵手A 向挑戰者B 聲明一個發送者的身份標識ID*，并將其作為挑戰，然后選擇兩個長度相等的挑戰關鍵字(w0,w1)。挑戰者B 隨機選擇β?{0,1}，根據選擇結果，運行索引生成算法BuildIndex(IDR,wβ)，生成密文索引Iβ，并將其發送給敵手A。

4）詢問階段2。敵手A 繼續向各個隨機諭言機進行詢問，該階段的詢問與詢問階段1 相同。

5）猜測。敵手A 輸出一個字節β′?{0,1}作為對關鍵字wβ的猜測，假如β=β′，則敵手A 贏得游戲。前提是敵手沒有詢問過ID*對應的私鑰，也沒有詢問過與身份ID*對應的關鍵字w0和w1的陷門密文信息及索引密文信息。

敵手A 在該游戲中的優勢定義為：

3.2.2 陷門不可區分性游戲

與游戲1 相似，游戲2 仍然假設半誠實服務器是敵手A。陷門不可區分性旨在防止敵手A 從一個給定的陷門信息中獲取其對應關鍵詞的信息。陷門不可區分性保證即使是服務器本身，也無法生成針對某接收者的有效密文。

1）初始化。與游戲1 的初始化相同。

2）詢問階段1。與游戲1 的詢間階段1 相同。

3）挑戰。敵手A 向挑戰者B 聲明一個發送者的身份標識ID*作為挑戰，并選擇兩個長度相等的挑戰關鍵字(w0,w1)，挑戰者B 隨機選擇β?（0,1），并根據選擇結果，運行陷門生成算法Trapdoor(wβ,dR)，生成陷門Tβ，并將其發送給敵手A。

4）詢問階段2。與游戲1 中的詢問階段2 相同。

5）猜測。敵手A 輸出一個字節β′?（0,1），作為對關鍵字wβ的猜測，假如β=β′，則敵手A 贏得游戲。限制條件與游戲1 相同。

敵手A 在該游戲中的優勢定義為：

4 方案分析與證明

4.1 正確性分析

本文根據雙線性對的性質來驗證本文方案的正確性。

定義2假設在本文方案中所有密文索引和陷門都是按照正確的步驟生成，且在傳輸過程中未遭到惡意攻擊，數據沒有被篡改。方案正確性是指當用戶向服務器發送包含關鍵詞w′的檢索陷門時，服務器運行檢索匹配算法，以正確匹配到包含該關鍵詞的密文索引，從而返回包含該關鍵詞的密文文件。

假設用戶ID′的公私鑰對為用戶ID′為關鍵詞w′生成的陷門[H2(w′)-t′]?d′)。當服務器運行檢索匹配算法并逐個對比密文索引，由雙線性對的性質可知：

則服務器可以正確匹配到密文索引，正確性成立。

4.2 安全性證明

本文SM9SE 方案在隨機諭言模型下滿足適應性密文不可區分性以及適應性陷門不可區分性。具體證明過程如下：

證明若挑戰者B 解決一個DBDH 實例元組Y=(G1,G2,GT,q,P1,[x]P1,[y]P1,P2,[y]P2,[z]P2,Z)，則挑戰者B 按如下過程與敵手A 進行密文不可區分性游戲。

2）詢問階段1。敵手A 適應性地詢問由挑戰者B模擬的隨機諭言機，假設敵手A 不會對同一個隨機諭言機進行相同詢問，并且在向H1詢問ID 值之前不會對ID 做任何計算。隨機諭言機主要有以下6 個：

4）詢問階段2。與詢問階段1 相同。

證明當敵手A2和挑戰者B 進行密文不可區分性游戲時，在挑戰階段，敵手A2可將挑戰者B 返回的挑戰密文發送給敵手A1，若敵手A1猜測的結果為敵手A2挑選的關鍵詞之一，則敵手A2向挑戰者B 輸出對應的結果作為猜測，否則隨機輸出猜測結果。可知敵手A2的優勢為：

該證明與定理1 矛盾。因此，如果DBDH 假設成立，則不存在敵手能以不可忽略的優勢對SM9SE方案發起離線關鍵詞猜測攻擊。

5 仿真實驗與分析

5.1 效率分析

本文將SM9SE 方案與其他現有的基于身份可搜索加密方案進行對比分析。本文在同一標準下將EdIBEKS方案［10］、PEAKS方案［14］以及dIBAEKS 方案［17］進行效率分析。基于文獻［25］中的定義，表1定義了若干不同符號及其換算方法。

表1 符號定義與換算Table 1 Symbol definition and conversion

EdIBEKS方案、PEAKS 方案以及dIBAEKS 方案所有的運算都建立在對稱雙線性對上，使用的曲線為嵌入度2，以1 024 bit 的大素數p為階的超奇異橢圓曲線E(Fp)：y2=x3+x。本文方案的運算建立在非對稱雙線性對上，使用的曲線為嵌入度12，階為256 bit 的大素數p的BN 曲線E：y2=x3+5。以上選擇參數能夠確保所有方案都可以實現與2 048 bit 的RSA 密鑰相當的安全級別。表2 表示不同方案的安全性假設、安全級別及其參數大小，以及本文方案與其他基于身份可搜索加密方案中用戶執行一次索引生成算法、陷門生成算法和服務器執行一次檢索匹配算法所需要執行的操作，其中忽略了方案中都存在的哈希函數運算。當計算橢圓曲線上的雙線性對時，曲線的嵌入次數越多，計算越復雜，因此安全性也更高。相比其他方案采用嵌入度為2 的超奇異橢圓曲線，本文方案采用嵌入度為12 的BN 曲線，因此本文方案的安全性優于其他方案。由于BN 曲線的雙線性對具有友好性［26］，在BN 曲線上計算雙線性對更加高效。從表2 可以看出，本文SM9SE 方案在保證計算效率的前提下，采用更小的安全參數實現與其他方案同等的安全級別，并且在索引生成算法上的效率優于其他三個方案，在陷門生成算法上的效率優于PEAKS 方案和dIBAEKS 方案，與EdIBEKS方案持平，都需要一次雙線性對運算。由于本文方案采用參數更小的BN 曲線，因此計算效率會更高，檢索匹配算法的效率優于EdIBEKS 方案和dIBAEKS 方案，與PEAKS 方案持平，都需要兩次雙線性對運算和一次橢圓曲線標量點乘法運算。由于本文方案采用參數更小的BN 曲線，因此計算效率會更高。因此，本文方案的總體性能優于其他方案。

表2 不同方案的計算效率與安全性對比Table 2 Computational efficiency and security comparison among different schemes

5.2 仿真結果分析

本文對EdIBEKS、PEAKS、dIBAEKS 和SM9SE方案進行仿真實驗，在2.40 GHz 的4 核64 位Intel?CoreTMi5-10200H 處理 器、8 GB 內存（RAM）、Windows 10 操作系統的實驗環境進行實驗，以myeclipse 10 作為實驗平臺、Java 作為實驗編程語言，對各方案的索引生成算法、陷門生成算法和匹配檢索算法進行模擬運行。本文首先使用不同長度的關鍵詞對各個方案進行模擬運行，以分析關鍵詞長度對各方案效率的影響，然后分別抽取Enron 郵件數據集中的部分數據和Kaggle 郵件數據集中的部分數據作為測試輸入，使用不同數量的關鍵詞進行對比實驗。關鍵詞長度對各方案的算法運行時間的影響如圖1 所示。

圖1 關鍵詞長度對各方案中算法運行時間的影響Fig.1 Influence of keyword length on the running time of algorithms in each schemes

從圖1 可以看出，關鍵詞長度對各算法運行效率的影響較小（關鍵詞長度影響哈希函數運行時間，但哈希運算速度極快），略受各算法所選擇的隨機數影響，但總體運行時間較為平穩。

圖2 表示各個方案中索引生成算法的運行時間，其中橫坐標是關鍵詞的個數，縱坐標為建立索引所需要的時間。從圖2 可以看出，SM9SE 方案在索引生成算法上的運行效率優于其他三種方案。SM9SE 方案生成一個密文索引的平均時間在8 ms左右，而其他方案的密文索引時間則在35～68 ms 之間。因此，本文方案在索引生成算法上的效率相比其他三種方案提高了77%以上。

圖2 索引生成算法的運行時間對比Fig.2 Comparison of running time of index generation algorithms

圖3 表示在各個方案中陷門生成算法的運行時間對比，其中橫坐標是關鍵詞的個數，縱坐標為生成檢索陷門所需要的時間。從圖3 可以看出，SM9SE 方案在陷門生成算法上的運行效率也優于其他三種方案。其他三種方案生成一個陷門的運行時間平均為30～53 ms 之間，而SM9SE 方案生成一個陷門的平均時間在25 ms 左右，效率提高了16.67%以上。

圖3 陷門生成算法的運行時間對比Fig.3 Comparison of running time of trapdoor generation algorithms

圖4 表示在各個方案中檢索匹配算法所運行的時間，其中橫坐標是密文索引的個數，縱坐標為所有密文索引的運行時間。從圖4 可以看出：SM9SE 方案單次檢索匹配算法的平均運行時間為18 ms 左右；dIBAEKS 方案的單次檢索匹配算法的平均運行時間為53 ms 左右；PEAKS 方案和EdIBEKS 方案的單次檢索匹配算法的平均運行時間在25～45 ms 之間。因此，SM9SE 方案的檢索匹配算法運行效率相對其他三種方案提高了28%以上。

圖4 檢索匹配算法的運行時間對比Fig.4 Comparison of running time of retrieval matching algorithms

圖5表示在不同方案中各個算法的平均運行時間。從圖5 可以看出，本文方案執行一次索引生成算法、陷門生成算法和檢索匹配算法的全過程所需要的平均時間總和為52 ms，其他三種方案則在105～168 ms之間。相比其他三種方案，本文方案的總體效率提高了50.4%以上。

圖5 各個算法的平均運行時間對比Fig.5 Comparison of average running time of each algorithms

6 結束語

針對現有基于身份的可搜索加密方案計算效率低、與SM9 密碼算法難以結合等問題，本文提出一種基于SM9 密碼算法的可搜索加密方案。根據非對稱雙線性對的性質，結合SM9 加密算法的密鑰形式，設計索引生成算法、陷門生成算法和服務器檢索匹配算法，并驗證方案的正確性和安全性。該方案在隨機諭言模型下滿足適應性密文不可區分性和適應性陷門不可區分性。仿真結果表明，相比EdIBEKS、PEAKS、dIBAEKS 方案，本文方案具有較高的計算效率，能夠實現可搜索加密與國家商用密碼算法SM9 的結合，并擴展了SM9 密碼算法的應用。下一步將在本文方案中增加指定身份檢索、身份驗證等更靈活的功能，使其適用于較復雜的應用場景。此外，還將在安全索引中嵌入數據發送者的私鑰，并在陷門中嵌入發送者的公鑰，通過設計相應的匹配算法實現精確檢索目標文件的功能。