指定使用者的多服務(wù)器多關(guān)鍵字可搜索加密方案

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

（1.西北師范大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，蘭州 730070；2.深圳技術(shù)大學(xué) 大數(shù)據(jù)與互聯(lián)網(wǎng)學(xué)院，廣東 深圳 518118）

0 概述

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

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

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

1 預(yù)備知識(shí)

1.1 雙線性映射

假設(shè)q是一個(gè)大素?cái)?shù)，G1和G2是2 個(gè)階為q的循環(huán)群。若映射e：G1×G1→G2滿足以下屬性，則稱其為雙線性映射［20］：

1.2 困難問題假設(shè)

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

2 加密方案框架

2.1 系統(tǒng)模型

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

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

5 個(gè)實(shí)體的具體功能如下：

1）KGC：生成系統(tǒng)的公共參數(shù)以及數(shù)據(jù)屬主、數(shù)據(jù)用戶、搜索服務(wù)器的部分私鑰。

2）數(shù)據(jù)屬主：首先將文檔集密文C={C1,C2,…,Cn}和相對(duì)應(yīng)的文件索引集I={I1,I2,…,In}上傳到存儲(chǔ)服務(wù)器，其次將關(guān)鍵字密文和對(duì)應(yīng)的文件索引集I={I1,I2,…,In}上傳到搜索服務(wù)器。

3）數(shù)據(jù)用戶：生成搜索陷門TW并發(fā)送給搜索服務(wù)器進(jìn)行驗(yàn)證搜索，同時(shí)對(duì)搜索結(jié)果進(jìn)行解密。

4）存儲(chǔ)服務(wù)器：存儲(chǔ)數(shù)據(jù)屬主上傳的文檔密文和對(duì)應(yīng)的文件索引集。

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

2.2 形式化定義

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

2.3 安全模型

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

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

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

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

Game：挑戰(zhàn)者C執(zhí)行算法Setup 產(chǎn)生KGC 的主密鑰s和系統(tǒng)的公共參數(shù)params。如果敵手A=A1，則返回params；如果A=A2，則返回params 和s。

Hash 詢問：敵手A進(jìn)行4 個(gè)Hash 詢問，挑戰(zhàn)者C返回相應(yīng)的Hash 值；PartialPrivateKey 詢問：敵手A對(duì)身份IDI進(jìn)行部分私鑰詢問時(shí)，挑戰(zhàn)者C向A返回相應(yīng)的部分私鑰；Secret-Value-query 詢問：敵手A對(duì)身份IDI進(jìn)行秘密值詢問時(shí)，挑戰(zhàn)者C計(jì)算相應(yīng)的秘密值給A；PublicKey-query 詢問：敵手A對(duì)身份IDI進(jìn)行公鑰詢問時(shí)，挑戰(zhàn)者C計(jì)算相應(yīng)的公鑰給A；Reaplace-PublicKey 詢問：敵手A=A1可以替換任何用戶的公鑰；Trapdoor-query 詢問：敵手A對(duì)身份IDI的關(guān)鍵字w進(jìn)行陷門詢問時(shí)，挑戰(zhàn)者C計(jì)算相應(yīng)的陷門給A。

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

More-Trapdoor 詢 問：A可以對(duì) 其他關(guān)鍵字wi進(jìn)行陷門詢問，但wi?{w0,w1}。

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

3 方案實(shí)現(xiàn)

3.1 方案的具體描述

方案的具體描述如下：

3.2 方案的正確性分析

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

4 安全性證明

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

定理1 由以下2 個(gè)引理可以證明：

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

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

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

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

5 性能分析

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

表1 4 種方案的性能對(duì)比結(jié)果Table 1 Performance comparison results of four schemes

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

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

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

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

6 結(jié)束語

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