指定使用者的多服務器多關鍵字可搜索加密方案

竇鳳鴿，曹素珍，馬佳佳，丁曉暉，王彩芬

（1.西北師范大學 計算機科學與工程學院，蘭州 730070；2.深圳技術大學 大數據與互聯網學院，廣東 深圳 518118）

0 概述

隨著云計算技術［1-2］的發展，越來越多的用戶將數據存儲在云上，由于云服務器不能保證數據的安全以及用戶的私密性，因此將數據加密后再發送到云［3］成為數據屬主（Data Owner，DO）普遍采用的方法，但是該過程中數據使用者將面臨密文搜索的難題［4-5］。為解決該問題，2000 年SONG 等［6］提出一種可搜索加密技術。

2004 年，BONEH 等［7］提出首個基于關鍵字搜索的公鑰加密方案，該方案在通信過程中需要安全通道，導致通信代價較大。2020 年，RHEE 等［8］提出指定測試者的可搜索公鑰加密方案，其在隨機預言機模型下證明了陷門的不可區分性是抗關鍵字猜測攻擊（Keyword Guessing Attack，KGA）的充分條件。2014 年，PENG 等［9］提出帶有關鍵字搜索的無證書公鑰加密方案，但該方案存在內部關鍵字猜測攻擊（Inside Keyword Guessing Attack，IKGA）問 題。2017 年，HUANG 等［10］提出基于關鍵字搜索的公鑰認證可搜索加密方案，該方案可以對數據屬主的身份進行認證。2018 年，MA 等［11］提出工業物聯網環境下無證書可搜索加密方案，但其不能抵抗IKGA。2020 年，YANG 等［12］對文獻［11］方案進行改進，改進后的方案可抵抗IKGA，但其只支持單關鍵字搜索。2019 年，WANG 等［13］設計的抗IKGA 的 可搜索 加密方案中以非確定性算法生成搜索陷門，使得方案滿足陷門不可區分性和密文不可區分性，但其存在證書管理問題。2019 年，LU 等［14］提出的無證書公鑰可搜索加密方案解決了證書管理問題且能抵抗IKGA，但其只支持單關鍵字搜索。文獻［15-16］中無雙線性對的可搜索加密方案均提高了計算效率，但都不能支持多關鍵字搜索，且文獻［16］方案存在證書管理及密鑰托管問題。2020 年，CHI 等［17］提出的云輔助醫療物聯網下的公鑰認證可搜索加密方案僅支持單關鍵字搜索。文獻［18］中基于身份的動態可搜索加密方案存在密鑰托管問題。可以看出，上述方案都是基于單關鍵字搜索而設計的。2020 年，LUO等［19］提出的基于連接關鍵字的實用化可搜索加密方案，解決了搜索結果不精確的問題，但其存在證書管理及密鑰托管問題。上述所提方案都是基于單服務器所設計，存儲和搜索都在一個服務器上完成，且沒有對數據使用者身份的合法性進行驗證。

針對上述方案單關鍵字搜索結果不精確和單服務器檢索效率低等問題，本文提出一種基于無證書且指定使用者的多服務器多關鍵字可搜索加密方案。該方案使用多服務器來降低服務器負荷，采用多關鍵字技術使得搜索結果更精確。利用搜索服務器（Search Server，SS）對用戶身份的合法性進行驗證，通過用戶身份及搜索服務器私鑰來驗證用戶是否為指定使用者，若身份合法，則存儲服務器（Cloud Server，CS）根據關鍵字返回相應密文，數據使用者使用私鑰解密密文以獲得明文。

1 預備知識

1.1 雙線性映射

假設q是一個大素數，G1和G2是2 個階為q的循環群。若映射e：G1×G1→G2滿足以下屬性，則稱其為雙線性映射［20］：

1.2 困難問題假設

計算的雙線性Diffie-Hellman（Computational Bilinear Diffie-Hellman，CBDH）問題［21］定義為：給定雙線性對e：G1×G1→G2，四元組（g，ga，gb，gc）∈G1，其中為未知數，則計算e（g，g）abc是困難的。

2 加密方案框架

2.1 系統模型

本文所提方案包含5 個不同的實體，分別為密鑰生成中心（Key Generation Center，KGC）、存儲服務器、搜索服務器、數據屬主、數據用戶（Data User，DU），系統模型如圖1 所示。

圖1 本文方案系統模型Fig.1 The system model of the scheme in this paper

5 個實體的具體功能如下：

1）KGC：生成系統的公共參數以及數據屬主、數據用戶、搜索服務器的部分私鑰。

2）數據屬主：首先將文檔集密文C={C1,C2,…,Cn}和相對應的文件索引集I={I1,I2,…,In}上傳到存儲服務器，其次將關鍵字密文和對應的文件索引集I={I1,I2,…,In}上傳到搜索服務器。

3）數據用戶：生成搜索陷門TW并發送給搜索服務器進行驗證搜索，同時對搜索結果進行解密。

4）存儲服務器：存儲數據屬主上傳的文檔密文和對應的文件索引集。

5）搜索服務器：對數據用戶的身份進行驗證，若為指定使用者，則根據數據用戶發送的搜索陷門TW′和數據屬主上傳的密文CW進行驗證，若驗證成功，將對應的（文件索引Ii(1≤i≤n)，用戶身份ID）發送給存儲服務器，存儲服務器返回對應的密文給數據用戶；否則，說明數據用戶不是指定使用者，向其返回終止符“⊥”。

2.2 形式化定義

在形式上，本文所提方案由以下7 個算法組成：

2.3 安全模型

由于本文方案是在無證書密碼體制下所提出的，因此應考慮2 個不同類型的敵手：

1）A1（惡意的內部服務器或外部攻擊者）無法訪問KGC 的主密鑰，但能替換用戶公鑰。

2）A2（誠實但好奇的擁有主密鑰的KGC）能為用戶生成部分私鑰，但不允許替換公鑰。

本文方案的安全模型由以下游戲定義，該游戲在挑戰者C和敵手A1、A2之間分別進行：

Game：挑戰者C執行算法Setup 產生KGC 的主密鑰s和系統的公共參數params。如果敵手A=A1，則返回params；如果A=A2，則返回params 和s。

Hash 詢問：敵手A進行4 個Hash 詢問，挑戰者C返回相應的Hash 值；PartialPrivateKey 詢問：敵手A對身份IDI進行部分私鑰詢問時，挑戰者C向A返回相應的部分私鑰；Secret-Value-query 詢問：敵手A對身份IDI進行秘密值詢問時，挑戰者C計算相應的秘密值給A；PublicKey-query 詢問：敵手A對身份IDI進行公鑰詢問時，挑戰者C計算相應的公鑰給A；Reaplace-PublicKey 詢問：敵手A=A1可以替換任何用戶的公鑰；Trapdoor-query 詢問：敵手A對身份IDI的關鍵字w進行陷門詢問時，挑戰者C計算相應的陷門給A。

Challenge 階段：A輸出挑戰關鍵字(w0,w1)，挑戰者C隨機選擇b∈{0,1}，并返回密文Cwb。

More-Trapdoor 詢 問：A可以對 其他關鍵字wi進行陷門詢問，但wi?{w0,w1}。

Guess 階段：A輸出猜測值b′∈{0,1}，如果b′=b，則贏得游戲。如果A在上述游戲中獲勝的優勢AAdv=2|Pr[b=b']-1/2|是可忽略的，則稱方案是抗IKGA 語義安全的。

3 方案實現

3.1 方案的具體描述

方案的具體描述如下：

3.2 方案的正確性分析

方案的正確性分析具體如下：

4 安全性證明

定理1如果CBDH 問題是困難的，則本文方案在隨機預言機模型下抵抗關鍵字猜測攻擊是語義安全的。

定理1 由以下2 個引理可以證明：

引理1若存在敵手A1能夠在t時間內以ε的優勢攻破本文方案，則存在一個算法C能夠在O(t)時間內以的概率解決CBDH 問題。其中：q1、qP和qT分別表示對H1、PartialPrivateKey 和Trapdoor 詢問的最大查詢數。

證明已知(g,ga,gb,gc)求解e(g,g)abc為CBDH問題實例。算法C模擬游戲中的挑戰者與敵手A1進行如下交互：C輸入安全參數l執行Setup 算法生成參 數 params={G1,G2,e,q,g,PPub,H1,H2,H3,H4}，其中，PPub=ga，再隨機選擇IDI作為挑戰者身份，最后向敵手A1發送公共參數params。

引理2若存在敵手A2能夠在t時間內以ε的優勢攻破本文方案，則存在算法C能夠在O(t)時間內以的概率解決CBDH 問題。

證明已知(g,ga,gb,gc)求解e(g,g)abc為CBDH問題實例。算法C模擬游戲中的挑戰者與敵手A2進行如下交互：C輸入安全參數l執行Setup 算法生成params={G1,G2,e,q,g,PPub,H1,H2,H3,H4}。其 中，PPub=gs，設置PKIDI=ga，PKDO=gb，再隨機選擇IDI作為挑戰者身份，最后向敵手A2發送params。

5 性能分析

將本文方案與文獻［8］方案、文獻［10］方案、文獻［13］方案在計算開銷、功能及效率方面進行性能對比。其中：Tp表示雙線性對運算的運行時間；TE表示指數運算的運行時間；TM表示點乘運算的運行時間。從表1 可以看出，本文方案在關鍵字加密及搜索驗證階段的性能優于其他3 個方案，且其在支持多服務器多關鍵字搜索的同時能夠抵抗IKGA，安全性高于對比方案。

表1 4 種方案的性能對比結果Table 1 Performance comparison results of four schemes

在以筆記本電腦（Windows 7（64 位）處理器Intel?CoreTMi5CPU@2.3 GHz）為實驗平臺、Visual C++6.0 為編譯軟件的環境下，基于0.4.7 的PBC 庫，將本文方案與文獻［8］方案、文獻［10］方案的關鍵字加密及搜索驗證階段進行效率對比分析，關鍵字個數選取為［1，10，20，30，40，50］，對比結果如圖2、圖3 所示。

圖2 關鍵字加密階段的效率分析Fig.2 Efficiency analysis of keyword encryption stage

圖3 搜索驗證階段的效率分析Fig.3 Efficiency analysis of search verification stage

從圖2 可以看出，本文方案和文獻［8］方案、文獻［10］方案的運行時間在關鍵字加密階段均隨著關鍵字個數的增加而增加，但本文方案所使用時間明顯低于其他2 個方案。從圖3 可以看出，3 種方案的運行時間在搜索驗證階段均隨著查詢關鍵字個數的增加而不斷增加，即使本文方案添加了多服務器，但效率還是高于其他2 個方案。因此，本文方案在綜合性能上具有明顯優勢。

6 結束語

本文在無證書密碼體制下提出一種指定使用者的多服務器多關鍵字可搜索加密方案，該方案使用多服務器提高用戶檢索密文的速度，采用多關鍵字技術使搜索結果更加精確，搜索服務器可以驗證數據用戶身份的合法性。本文在隨機預言機模型下證明了該方案能夠抵抗內外關鍵字猜測攻擊，同時，理論分析和實驗結果表明，本文方案具有較高的運算效率。下一步將在標準模型下探索實現更加高效并指定使用者的多服務器多關鍵字可搜索加密方案。