高效的可驗證無證書可搜索加密方案

崔新華，田有亮，張起嘉

（1.公共大數據國家重點實驗室，貴州 貴陽 550025；2.貴州大學計算機科學與技術學院，貴州 貴陽 550025；3.貴州師范大學經濟與管理學院，貴州 貴陽 550025；4.貴州大學密碼學與數據安全研究所，貴州 貴陽 550025）

0 引言

隨著云計算技術的快速發展，為了滿足用戶日益增長的需求，互聯網設備產生的數據量飛速增長。越來越多的企業與個人選擇將數據存放在云服務器中，以緩解本地存儲帶來的壓力。然而，當數據被上傳至云服務器后，數據擁有者便失去了對數據的控制。特別是當數據中包含敏感信息時，數據擁有者難以對敏感信息提供安全保護。為了避免云服務器侵犯敏感數據的隱私性，需要將文件加密后再上傳。然而，加密會導致數據之間的關聯性被破壞，給文件檢索帶來了困難。為了解決云服務器對密文實現高效檢索的問題，可搜索加密[1]成為最受研究者關注的方法之一。

現有的可搜索加密方案中，公鑰可搜索加密（PEKS）[2-3]相比于對稱可搜索加密（SSE,symmetric searchable encryption）[4-5]更適用于云存儲環境中的文件共享等場景，因此成為一個重要的研究熱點。PEKS 引入了非對稱的搜索陷門，以關鍵詞密文與搜索陷門能否匹配作為搜索成功的判斷依據。具體來說，數據擁有者首先需要依次對準備上傳的文件提取關鍵詞，然后利用文件接收者的公鑰計算生成關鍵詞密文。接下來，數據擁有者將數據文件加密，再將文件密文與關鍵詞密文相連接，形成密文索引并一同上傳至云服務器中進行存儲。數據用戶在對目標文件發起搜索前，首先需要確定目標文件的關鍵詞，并使用私鑰生成搜索陷門，然后作為搜索請求發送給云服務器。云服務器接收到搜索請求后，對密文索引進行匹配測試，最后將匹配到的密文作為搜索結果返回給數據用戶。在此期間，不可信的云服務器雖然執行存儲與匹配任務，卻無法得知任何關于數據文件的信息。

然而，在現實環境中云服務器可能會因為經濟利益或黑客攻擊等因素，惡意地發動選擇性轉發攻擊[6]，即只返回部分搜索結果給用戶。而在目前大多數的PEKS 方案中，用戶缺乏搜索結果的驗證機制，無法檢測返回的搜索結果是否完整或是否已經被惡意篡改。為了抵抗惡意云服務的攻擊，可驗證性[7-9]為用戶提供了搜索結果的審查機制，成為研究目標之一。Sun 等[10]提出了一種可驗證的多關鍵詞可搜索加密方案。該方案采用基于樹的數據結構作為索引，以實現搜索結果的完整性驗證。Wang 等[11]結合布隆過濾器（BF,Bloom filter）、Merkle 哈希樹（MHT,Merkle hash tree）等數據結構，提出了一種外包數據庫的審計協議。然而，該協議只能實現靜態審計，無法適用于云計算中的動態更新場景。隨后，大量支持動態更新的可驗證的可搜索加密方案被提出[6,12-13]。然而，這些方案在更新過程中帶來的計算開銷與通信開銷較大，有待進一步降低。因此，對搜索結果實現高效驗證與密文的高效更新仍是亟待解決的難題。

大多數PEKS 方案都是基于證書或基于身份的公鑰密碼，存在證書管理以及密鑰托管問題。為了解決該問題，Peng 等[14]提出了第一個基于無證書的公鑰可搜索加密（CLPEKS,certificateless public key encryption with keyword search）方案，該方案將無證書的公鑰密碼引入PEKS 中，為傳統的PEKS 方案提升了抗惡意用戶與半誠實的密鑰生成中心的安全性。此后，大量的研究人員對基于無證書的PEKS 方案進行了研究[15-18]。Zheng 等[19]提出了一個不需要用戶執行對運算的無證書可搜索加密方案，該方案顯著降低了用戶的計算量，提升了方案的實用性。Miao 等[20]實現了一種基于無證書的可驗證的多關鍵詞可搜索加密方案，該方案不僅基于Zheng 等[19]方案實現了無證書加密，還將云審計與可搜索加密相結合，采用可信的第三方審計服務器協助用戶對搜索結果進行驗證。田有亮等[21]在Miao 等[20]方案的基礎上提出了一種基于改進Merkle 樹認證方法的可驗證多關鍵詞可搜索加密方案，與之前的方案相比，該方案將驗證過程中的計算開銷由經典MHT 的O(n)降低到O(logn)，實現了高效驗證與更新。然而，經過本文分析，該方案存在明顯的安全性缺陷，無法達到文中聲稱的安全要求。張鍵紅等[6]提出了一種高效、可驗證的多關鍵詞搜索加密方案，該方案不僅能夠支持多關鍵詞搜索，還實現了搜索模式的隱私性和文件的前向安全。

為了實現安全高效可驗證的密文檢索，同時滿足無證書公鑰加密環境中的安全性，本文提出了一種高效的可驗證無證書可搜索加密方案。本文的主要貢獻如下。

1) 首先，對文獻[21]方案進行了安全性分析，指出了其既不能滿足密文的選擇明文攻擊的不可區分（IND-CPA）安全，也不能滿足適用于可搜索加密的選擇關鍵詞攻擊的不可區分（IND-CKA）安全。然后，給出了2 種具體的攻擊，即外部攻擊者發動的密文猜測攻擊，以及惡意用戶發動的在線關鍵詞猜測攻擊。

2) 提出了一種高效的基于無證書的可搜索加密方案。在隨機預言機模型下，基于判定性線性（DLIN,decisional linear）假設與計算性DH（co-CDH,co-computational Diffie-Hellman）假設，證明了所提方案滿足選擇關鍵詞攻擊下的不可區分性與簽名的不可偽造性。

3) 通過結合改進的MHT 與無證書簽名，實現了高效可驗證性與高效動態更新，通過實驗與其他現有主流方案進行對比，分析表明了所提方案在計算效率方面與通信效率方面均優于其他相關方案，具有更高的實用價值。

1 基礎知識

本節首先介紹了雙線性對的概念和本文用到困難假設，然后給出了無證書可搜索加密方案的形式化定義和相關的安全模型。

1.1 雙線性對

設λ為安全參數，p為與λ相關的大素數，G1、G2和GT為3 個階為p的乘法循環群。

定義1雙線性映射。若映射e:G1×G2→GT滿足以下3 個條件，則該映射為一個雙線性映射。

1) 雙線性：對于任意元素g1∈G1,g2∈G2和a,b∈Zp，均有

2) 非退化性：至少存在元素g1∈G1和g2∈G2，滿足e(g1,g2) ≠ 1。

3) 可計算性：對于任意元素g1∈G1和g2∈G2，均有多項式時間算法計算e(g1,g2)。

根據群G1與G2的不同關系，雙線性映射可分為2 類。若G1=G2，則該雙線性映射為Type-1 類型；若G1≠G2，且G1與G2之間存在一個同構映射?，使?(G2)→G1，則該雙線性映射為Type-2 類型。

1.2 困難假設

1.3 Merkle 哈希樹

經典Merkle 哈希樹是一種二叉樹數據結構，將數據分成若干個塊，然后對每個塊計算哈希值，作為葉子節點。輸入相鄰的2 個葉子節點的哈希值，再計算生成一個新的哈希值，作為這2 個葉子節點的父節點。遞歸進行該操作，直到得到一個根節點，它可以確保所有節點的完整性，因此可以作為整個數據的哈希值。Garg 等[22]提出了一種基于相對索引和時間戳的Merkle 哈希樹，通過修改搜索算法實現了高效動態更新。

改進Merkle 樹的每個節點包括2 個信息：一個是數據塊的哈希值，另一個是相對索引。與節點T關聯的相對索引是指屬于T的子樹的葉子節點的數量，葉子節點的索引值為1。例如，如果T的左右節點分別為hLeft和hRight且相對索引為iLeft和iRight，則T的哈希值為H(hLeft,hRight)，索引值為左右節點的相對索引之和 (iLeft+iRight)。根節點hRoot的生成方式為hRoot=H(hLeft,hRight,dt)，其中，時間戳dt表示Merkle 樹創建的時間，根節點只對樹中任意數據塊做出修改而更新，且只有在有效時間內才能通過驗證，因此能夠保證數據的有效性。

1.4 形式化定義

如圖1 所示，無證書可搜索加密系統模型中包含4 個不同的實體：密鑰生成中心（KGC,key generation center）、數據擁有者（DO,data owner）、數據用戶（DU,data user）以及云服務器（CSP,cloud service provider）。

圖1 系統模型

1) 密鑰生成中心。KGC 為一個半誠實的實體，負責根據安全參數生成系統主密鑰與系統公開參數，以及為每個數據擁有者與用戶生成部分私鑰。KGC 會對密文中包含的信息產生好奇，能夠利用已知的系統主密鑰等關鍵信息發動猜測攻擊，以及勾結云服務器偽造驗證信息。

2) 數據擁有者。數據擁有者為一個誠實的實體，負責生成自己的公私鑰，并使用私鑰生成驗證信息；還負責使用用戶的公鑰生成關鍵詞密文，創建密文索引，最后將密文文件、密文索引與驗證信息一同上傳至云服務器中。除此之外，數據擁有者還能夠對密文進行修改、添加、刪除等更新操作。

3) 數據用戶。數據用戶為一個可能存在惡意的實體，但不與其他實體相互勾結。數據用戶負責向云服務器提出搜索請求，以及收到結果后對結果進行驗證。惡意用戶可能偽裝成合法用戶偽造搜索陷門，也可能對驗證信息發動偽造攻擊。

4) 云服務器。云服務器為一個半誠實的實體，負責存儲數據擁有者上傳的信息、幫助數據用戶執行搜索、協助數據擁有者完成密文更新操作。在操作過程中，云服務器可能會對密文中包含的信息產生好奇。

定義4可驗證的無證書可搜索加密方案?？沈炞C的無證書可搜索加密方案通常包括以下7 個多項式時間算法。

1) Setup(λ)。該算法由KGC 執行。輸入安全參數λ，生成系統主密鑰msk，發布系統公開參數params。

2) ParKeyGen(params,msk,ID)。該算法由KGC 執行。輸入系統主密鑰msk、系統公開參數params 以及用戶ID，生成用戶的部分私鑰psk。

3) KeyGen(params,psk,ID)。該算法由用戶執行。輸入部分私鑰psk、系統公開參數params 以及用戶ID，生成用戶的私鑰skU與公鑰pkU。

4) Encrypt(params,w,Files,pkU,skO,ID)。該算法由數據擁有者執行。輸入系統公開參數params、數據擁有者私鑰skO以及數據文件Files，生成驗證信息v。然后輸入用戶公鑰pkU與關鍵詞w，生成關鍵詞密文CT。

5) Trapdoor(params,w,skU)。該算法由數據用戶執行。輸入系統公開參數params、私鑰skU、關鍵詞w，生成搜索陷門T。

6) Search(T,CT)。該算法由CSP 執行。輸入搜索陷門T和關鍵詞密文CT，由CSP 計算是否匹配，若匹配成功，則將文件密文以及相應的驗證信息返回給用戶。

7) Verify(params,v,pkO,Files)。該算法由數據用戶執行。輸入系統公開參數params、數據擁有者公鑰pkO、驗證信息v以及解密文件Files，輸出驗證結果1（成功）或0（失?。?/p>

1.5 安全模型

無證書可搜索加密考慮2 種類型的敵手：Type-1類型的敵手AI代表惡意用戶，無法得知系統主密鑰msk，但可以發動公鑰替換攻擊，偽裝成一個合法用戶偽造搜索陷門或簽名；Type-2 類型的敵手AII代表誠實且好奇的KGC，能夠掌握系統主密鑰msk，以及掌握每個用戶的部分私鑰psk，但無法得知用戶私鑰，也無法偽裝成其他用戶。

本文通過以下4 個挑戰者C與敵手AI、AII之間的安全游戲來定義方案的安全模型，其中，Game1與Game2 為針對密文的IND-CKA 游戲，Game3 與Game4 為針對簽名的EUF-CMA 游戲。

Game1此處的敵手為AI。

1) 初始化。挑戰者C運行Setup 算法，設置公共參數。然后設置系統主密鑰，計算系統公鑰。最后將生成的系統公共參數與公鑰發送給敵手AI。

2) 哈希詢問。敵手AI在該階段對2 個隨機預言機分別進行多項式有限次的詢問，挑戰者C維護2 個初始為空的列表，用來記錄每次詢問。

3) 階段1。在該階段，敵手AI向挑戰者C進行多項式有界次適應性詢問，內容包含以下4 項。

①ParKeyGen 詢問。敵手AI向挑戰者C發送一個身份ID。當ID 與挑戰者身份相同時，中止游戲；否則，挑戰者C在收到ID 后，查詢哈希列表并計算部分私鑰psk，返回給敵手。

②KeyGen 詢問。敵手AI向挑戰者C發送一個身份ID。當ID 與挑戰者身份相同時，中止游戲；否則，挑戰者C執行ParKeyGen 算法，然后計算公私鑰對(sk,pk)，并返回給敵手。

③Replace-KeyGen 詢問。挑戰者C首先建立一個初始為空的列表。敵手AI隨機生成一個公鑰pk'。隨后向挑戰者C發送想要替換的身份ID 與替換公鑰pk'，挑戰者C將身份ID 對應的公鑰pk 使用pk'替換，并將其存儲在列表中。

④Trapdoor 詢問。敵手AI向挑戰者C發送一個身份ID 與一個關鍵詞w。挑戰者C首先對于ID 執行ParKeyGen 詢問與KeyGen 詢問，然后計算Trapdoor 并返回給敵手AI。

4) 挑戰。敵手AI向挑戰者C發送一個身份ID與2 個長度相同的關鍵詞w0,w1。ID 與w0,w1曾經被詢問過，則中止游戲；否則，挑戰者C隨機拋出一枚硬幣b={0,1}，計算關于ID 與wb的密文，返回給敵手。

5) 階段2。與階段1 相同，唯一的限制是敵手AI不能詢問關于挑戰密文的關鍵詞，也不能詢問挑戰者的私鑰與部分私鑰。

6) 猜測。敵手AI輸出一個比特b'={0,1}，若b'=b，則敵手獲勝。

定義5對于多項式時間內的敵手AI，贏得IND-CKA 游戲的優勢為

Game2此處的敵手為AII。Game2 與Game1相似，區別是不需要執行 ParKeyGen 詢問與Replace-KeyGen 詢問，且Setup 階段需要發送系統密鑰給敵手AII。

Game3此處的敵手為AI。

1) 初始化。挑戰者C運行Setup 算法，設置公共參數。然后設置系統主密鑰，計算系統公鑰。最后將生成的系統公共參數與公鑰發送給敵手AI。

2) 哈希詢問。敵手AI在該階段對2 個隨機預言機分別進行多項式有限次的詢問，挑戰者C維護2 個初始為空的列表，用來記錄的每次詢問。

3) 詢問階段。在該階段，敵手AI向挑戰者C進行多項式有界次適應性詢問，內容包含以下4 項。

①ParKeyGen 詢問。敵手AI向挑戰者C發送一個身份ID。當ID 與挑戰者身份相同時，中止游戲；否則，挑戰者C在收到ID 后，查詢哈希列表并計算部分私鑰psk，返回給敵手。

②KeyGen 詢問。敵手AI向挑戰者C發送一個身份ID。當ID 與挑戰者身份相同時，中止游戲；否則，挑戰者C執行ParKeyGen 算法，然后計算公私鑰對(sk,pk)，并返回給敵手。

③Replace-KeyGen 詢問。挑戰者C首先建立一個初始為空的列表。敵手AI隨機生成一個公鑰pk'。隨后向挑戰者C發送想要替換的身份ID 與替換公鑰pk'，挑戰者C將身份ID 對應的公鑰pk 使用pk'替換，并將其存儲在列表中。

④Signature 詢問。敵手AI向挑戰者C發送一個身份ID 與一個消息m。挑戰者C首先對ID 執行ParKeyGen 詢問與KeyGen 詢問，然后計算簽名并返回給敵手AI。

4) 偽造。敵手AI向挑戰者C發送一個身份ID、一個關于ID 的公鑰、一個消息m*以及對應的簽名σ*。若ID 與消息m*的簽名曾經被詢問過，則中止游戲；否則，敵手AI贏得該游戲。

定義6對于多項式時間內的敵手AI，贏得EUF-CMA 游戲的優勢為

Game4此處的敵手為AII。Game4 與Game3相似，區別是不需要執行 ParKeyGen 詢問與Replace-KeyGen 詢問，且Setup 階段需要發送系統密鑰給敵手AII。

2 對文獻[21]方案的安全性分析

本節首先簡要回顧文獻[21]中的方案，然后指出其不能滿足密文不可區分性，并給出2 種具體的攻擊過程。

2.1 對文獻[21]中方案的描述

由于篇幅限制，本節只簡要描述其Setup、ParKeyGen、KeyGen、Encryption、Trapdoor Generation以及Search 算法。方案的詳細設計請參考文獻[21]。

6) Search。服務器收到搜索用戶發來的Tw后，計算并驗證式(1)是否成立。

若式(1)成立，則返回相應的密文給搜索用戶；否則，匹配失敗，終止搜索。

2.2 針對IND-CKA 的攻擊

本節通過分析證明文獻[21]方案無法達到其聲稱的IND-CKA 安全。

2) 根據挑戰階段中接收到的挑戰密文，驗證式(2)是否成立。

因此，敵手攻擊成功，同時證明該方案不滿足可搜索加密的IND-CKA 安全。

2.3 針對密文機密性的關鍵詞猜測攻擊

本節通過分析證明文獻[21]方案無法實現密文的機密性。具體來說，誠實且好奇的云服務器能夠對存儲的關鍵詞密文發動關鍵詞猜測攻擊。詳細過程如下。

對于一個包含關鍵詞集W={w1,…,wn}的密文CT，有

誠實且好奇的云服務器首先計算

假設猜測的關鍵詞集為W*，則云服務器計算

最后，驗證式(4)是否成立。

當W*=W時，則有

由于現實世界中的關鍵詞的明文空間有限，攻擊者可以通過對所有可能的關鍵詞集W*進行有限次窮舉，對式(3)進行大量計算，得到的分別使用式(4)進行對比，便可在多項式時間內成功猜測出密文CT 中所包含的關鍵詞明文信息。

因此，該方案不滿足關鍵詞密文的機密性。

3 所提方案

下面給出本文提出的高效的可驗證無證書可搜索加密方案。

3.1 系統初始化

最后，KGC 保留系統主密鑰msk={x,y}，公開系統公共參數

3.2 部分私鑰生成

給定身份ID，通過執行該算法，KGC 分別生成數據用戶與數據擁有者的部分私鑰，具體步驟如下。

1) 對于數據用戶，輸入 (msk,IDU,params)，其中，IDU為長度為lID的比特串，表示用戶的身份。KGC 隨機選擇t∈Zp，并計算

2) 對于數據擁有者，輸入 (msk,IDO,params)，其中，IDO為數據擁有者的身份。KGC 隨機選擇t′∈Zp，并計算

然后將2 個部分私鑰 pskU=(pskU,1,pskU,2)與pskO=(pskO,1,pskO,2)通過安全信道分別發送給數據用戶與數據擁有者。

3.3 公私鑰生成

3.4 密文生成

首先，數據擁有者對數據文件進行提取關鍵詞處理。對于包含相同關鍵詞集W={w1,…,wn}的文件fi，數據擁有者使用對稱加密算法（如SM4）對其進行加密處理，生成數據文件密文c={c1,…,cq}。

其次，計算每個密文ci的哈希值hi，再將每個文件的哈希值作為葉子節點，每個葉子節點作為哈希函數H3的輸入，迭代生成MHT。其中，根節點為一個n位長的序列。由左右葉子節點與系統時間戳dt共同計算生成。系統時間戳dt表示一個有效時間段（如一天、一周或一個月），若時間段有效，則系統生成的時間戳相同。數據擁有者輸入自己的身份IDO、私鑰skO、公鑰p kO，生成根節點的簽名

最后，數據擁有者將{CW,v,c} 一同上傳至云服務器中進行存儲，其中，CW=(C1,C2,C3)。

3.5 陷門生成

3.6 密文搜索

云服務器收到用戶發送的搜索陷門Tw'后，將其與存儲的關鍵詞密文Cw進行匹配，計算并判斷式(6)是否成立。

若式(6)成立，則說明關鍵詞密文與陷門匹配一致，將數據文件密文c={c1,…,cq}以及相應的驗證信息v=(hRoot,σ1,σ2)返回給用戶。

3.7 結果驗證

3.8 動態更新

當數據擁有者希望對存儲在云服務器上的文件進行修改或添加時，首先向服務器認證自己的身份。當身份驗證通過后，通過以下方式對文件進行更新。

圖2 原始密文MHT

圖3 數據添加過程

圖4 數據刪除過程

4 方案分析

本節針對所提方案的正確性與安全性給出了具體的證明。

4.1 正確性分析

在搜索階段，為了保證方案中的云服務器能夠嚴格地對關鍵詞密文與搜索陷門進行匹配，對于式(6)，有

在結果驗證階段，為了保證搜索結果的正確性與完備性，對于式(7)，有

方案的正確性證畢。

4.2 安全性分析

本節通過定理1～定理3，證明了所提方案在CDH 假設與DLIN 假設下能夠抵抗無證書環境中Type-1 與Type-2 這2 種類型的敵手的攻擊，實現選擇關鍵詞攻擊下的IND-CKA 安全，并且滿足簽名的EUF-CMA 安全。

定理1若DLIN 問題是困難的，則所提方案在隨機預言機模型下能夠滿足IND-CKA 安全。

階段1。在該階段，敵手AI向B進行多項式有界次適應性詢問，內容包含以下4 項。

最后將pskj返回給敵手。該pskj于敵手視角中為合法部分私鑰。由于一個合法psk 需要滿足以下關系

敵手在收到pskj后，可以利用已知信息對pskj進行如下驗證

猜測。敵手AI輸出一個比特 {0,1}b′=。若b′=b，則敵手在該游戲獲勝，同時B輸出b*。

當敵手AI在游戲中獲勝時，若B在以上模擬游戲中不退出，則需要以下3 個條件同時滿足。

1) 敵手AI沒有在 ParKeyGen 詢問與PrivateKey 詢問階段向B發送過身份IDi*。

2) 敵手AI沒有在陷門詢問階段向B同時發送過身份IDi*與σi=1的消息Mj*。

3) 敵手AI在挑戰階段必須發送的是身份IDi*與σi=1的消息Mj*。

則B在以上條件下利用AI的攻擊成功解決DLIN 問題的優勢為

引理1 證畢。

引理2在隨機預言機模型下，若存在一個Type-2 類型的敵手AII，能夠以不可忽略的優勢ε攻破所提方案的IND-CKA 安全性，則能夠構造一個算法B，利用敵手A的能力以不可忽略的優勢求解DLIN 問題。

證明引理2 的證明與引理1 采用的思路相似，區別是Type-2 類型的敵手AII能夠得知系統主密鑰msk，因此需要將DLIN 問題的元素隱藏在用戶公鑰pkj中，而非系統公鑰中。為節省篇幅，此處不再展開詳細證明。

需要注意的是，Type-2 類型的敵手AII不能進行replace-public-key 詢問。由于Type-2 類型的敵手擁有msk，因此也不需要進行ParKeyGen 詢問。在挑戰階段，限制AII不能得知目標身份的私鑰

定理2若co-CDH 問題是困難的，則所提方案在隨機預言機模型下能夠滿足EUF-CMA 安全。

引理3在隨機預言機模型下，若存在一個Type-1 類型的敵手AI，能夠以不可忽略的優勢ε攻破所提方案的EUF-CMA 安全性，則能夠構造一個算法B，利用敵手AI的能力以不可忽略的優勢求解co-CDH 問題。

若B在以上模擬游戲中不退出，則需要以下3 個條件同時滿足。

引理3 證畢。

若B在以上模擬游戲中不退出，則需要以下3 個條件同時滿足。

1) 敵手AII沒有在PrivateKey 詢問階段向B發送過身份IDi*。

2) 敵手AII沒有在簽名詢問階段向B同時發送過身份IDi*與消息Mj*。

3) 敵手AII在偽造階段必須發送的是關于身份IDi*與消息Mj*的簽名。則B在以上條件下利用AII偽造的簽名成功解決co-CDH 問題的概率為

引理4 證畢。

5 性能分析

為了展示所提方案在效率方面的優勢，本節對其與4 種對比方案進行了理論性能分析，4 種對比方案分別為高被引的文獻[19]、文獻[20]、文獻[21]以及最新的文獻[6]。最后，將所提方案與4 種對比方案進行了實現，通過實驗對比，驗證了理論分析的結果。參數含義如表1 所示。

表1 參數含義

5.1 理論分析

在通信開銷方面，文獻[19]在密文生成階段的通信開銷為4 096 bit，且不提供可驗證性。文獻[6]在密文階段的通信開銷為7 168 bit，其中驗證信息為2 048 bit。文獻[20]在密文生成階段的通信開銷為5 120 bit，其中包含的關鍵詞密文為4 096 bit，驗證信息為1 024 bit。由于基于相同的思想，文獻[21]在密文生成階段的通信開銷同樣為5 120 bit。而所提方案在該階段僅需生成密文為2 226 bit 長度、驗證信息為1 272 bit 長度的無證書簽名。由于所提方案采用的群滿足Type-2 類型的雙線性對，因此在滿足相同的安全等級的同時，群中元素的長度要短于另外3 種方案中的群元素。通過比較可知，所提方案在密文生成階段的通信開銷明顯低于其他對比方案。

在用戶執行的陷門生成階段，文獻[19]、文獻[21]、文獻[20]、文獻[6]的通信開銷分別為4 096 bit、4 096 bit、5 120 bit、2 048 bit，而所提方案僅需1 590 bit，明顯優于這4 種方案。表2 展示了幾種方案的通信開銷。

表2 通信開銷

表3 展示了幾種方案的計算開銷。為便于展示，省略了耗時較短的乘法運算與整數群哈希運算，僅展示對計算開銷影響較大的7 種運算（如表1 所示）。由表3 可知，所提方案在涉及計算資源受限的終端用戶的密鑰生成、密文生成階段的計算效率顯著高于其他方案，在陷門生成階段的計算效率雖與文獻[6]持平，但明顯高于其他方案。在涉及數據擁有者與云服務器的密文搜索階段與結果階段的計算開銷也低于其他4 種方案。

表3 計算開銷

5.2 實驗分析

實驗設備為樹莓派4B，處理器為四核ARM Cortex-A72，內存為2 GB，操作系統為Raspberry Pi OS。使用C 語言作為編程語言，調用PBC 密碼庫實現群元素運算。本文實驗采用PBC 庫推薦的Type-A 曲線實現滿足對稱雙線性映射的群，群中所有元素均采樣自Type-A 曲線上的點，用于構建文獻[19]、文獻[20]、文獻[21]、文獻[6]方案中的實驗。同時，為了達到與Type-A 曲線近似的安全位數，實驗采用了D159 曲線實現滿足所提方案的非對稱雙線性映射的群G1、G2。同理，G1、G2群中的元素均由D159 曲線上的點構成。實驗設置在G、G1、G2群中元素的安全性一致的條件下（即攻擊者破解離散對數問題的代價相同），從構建的群中選取參數，實現方案中的算法與功能，衡量不同方案的時間開銷。Type-A 曲線與D159曲線的詳細實驗參數與樹莓派運行benchmark 的時間如表4 所示。

表4 實驗參數

實驗分別模擬實現了KGC 的初始化與部分私鑰生成算法、數據擁有者執行的密鑰生成算法與加密算法、云服務器執行的搜索算法以及用戶執行的密鑰生成算法與陷門算法。實驗中各算法執行100 次，然后記錄各方案的單次運行平均耗時。

在關鍵詞密文生成階段，4 種對比方案為了實現關鍵詞不可區分性，分別采用了9 次、11 次、11 次、8 次群G中的指數運算，且文獻[20]中包含了1 次map to point 運算、文獻[6]中包含了1 次map to point運算和2 次對運算。而所提方案實現相同的安全特性僅需4 次G1群中的指數運算和1 次map to point運算。根據圖5 中的實驗結果可知，所提方案的計算開銷為 49.403 ms，分別低于文獻[19]的60.534 ms、文獻[20]的88.266 ms、文獻[21]的73.986 ms 和文獻[6]的86.390 ms。對比實驗結果表明，所提方案在密文生成算法上的計算效率優于其他4 種方案。

圖5 關鍵詞密文生成階段的計算開銷

終端用戶負責執行陷門生成算法，其計算開銷如圖6 所示。4 種對比方案在該階段為了生成與密文相匹配的陷門，同時保障陷門內關鍵詞的機密性，文獻[19]、文獻[20]和文獻[21]均需要用戶執行10 次群G中的指數運算，計算開銷較大。由于文獻[6]優化了陷門生成算法，僅需執行3 次群G中的指數運算，大幅降低了計算量。在所提方案中，用戶需要執行1 次G1群中的指數運算和3 次G2群中的指數運算。然而，由表4 可知，所提方案采用了帶有Type-2 類型pairing 特性的曲線，其G2群中的指數運算開銷要顯著低于其他方案的指數運算開銷，因此計算效率依然優于文獻[6]。由圖6 可知，所提方案的計算效率不僅優于文獻[6]，更較文獻[19]、文獻[20]、文獻[21]提升了77.68%，具有明顯優勢。

圖6 陷門生成階段的計算開銷

用戶總負載記錄了在方案實現的全部過程中用戶端花費的全部計算開銷。文獻[19]由于不支持搜索結果的公開驗證性，因此用戶總計算開銷低于文獻[20]、文獻[21]、文獻[6]。而文獻[20]、文獻[21]的算法設計導致2 種方案中用戶的計算開銷（如表3所示）相近。文獻[6]雖然優化了陷門生成算法和驗證算法，其密文生成算法涉及了多種耗時的運算，但計算效率仍低于所提方案。由圖7 可知，所提方案不僅實現了搜索結果的公開驗證性，還采用了更少的指數運算次數，以及計算開銷更低的曲線，因此效率顯著高于其他方案，更能適用于如智能手機等資源有限的終端設備，具有較高的實用價值。

圖7 用戶總負載

6 結束語

本文首先對可驗證的無證書可搜索加密進行了研究，指出了文獻[21]方案存在安全缺陷，無法抵抗惡意用戶的猜測攻擊。然后，結合無證書加密、無證書簽名與改進的Merkle Tree 方法，提出了一種高效的可驗證無證書可搜索加密方案。與現有的無證書可搜索加密方案相比，所提方案既實現了搜索結果的可驗證性，又能滿足無證書場景中的安全性，同時，所提方案具有更高的計算效率與更小的通信開銷，在結合云計算的實際應用場景中具備更強的實用性。