曹永明

(河海大學計算機與信息學院,江蘇 南京 211100)

0 引 言

隨著可搜索公鑰加密[1]技術(shù)的不斷發(fā)展，用戶獲得了在加密數(shù)據(jù)上檢索數(shù)據(jù)的能力,很多帶關(guān)鍵字搜索的公鑰加密(Public key Encryption with Keyword Search, PEKS)方案也被相繼提出[2-3]。目前，大多數(shù)PEKS方案的主要缺陷是僅僅支持精確的關(guān)鍵字檢索，不具備一定的關(guān)鍵字搜索的容錯能力。

可搜索加密技術(shù)已經(jīng)得到了廣泛的研究?？伤阉骷用艿牡谝粋€構(gòu)造是由Song等人[4]提出的。為了實現(xiàn)更高的效率，Chang等人[5]和Curtmola等人[6]都提出了基于“索引”的方法，為整個數(shù)據(jù)文件集合建立一個哈希索引表。在每個索引表中，都包含一個關(guān)鍵字的陷門和一個加密文件的標識符集合，這些數(shù)據(jù)標識符與數(shù)據(jù)文件中包含的關(guān)鍵字相對應(yīng)。

2004年，Boneh等人[7]首次提出了帶關(guān)鍵字搜索的公鑰加密。在文獻[7]的基礎(chǔ)上，Waters等人[8]提出了一個加密日志的關(guān)鍵字搜索方案，讓用戶可以對已經(jīng)加密的信息進行審查。

由于PEKS方案無法支持模糊關(guān)鍵字搜索，Li等人[9]第一次提出模糊關(guān)鍵字檢索的方案。該方案中的模糊關(guān)鍵字集合采用通配符技術(shù)進行構(gòu)造。當用戶進行查詢時，用查詢的關(guān)鍵字與關(guān)鍵字集合進行匹配，將可能包含查詢關(guān)鍵字的文件集合返回。2011年，字典型模糊關(guān)鍵字集合由Liu等人[10]提出，雖然這種方法使得模糊關(guān)鍵字的數(shù)量得到了降低，但同時也降低了查詢的準確率。Wang等人[11]在2012年進一步研究了模糊關(guān)鍵字檢索方案，將樹結(jié)構(gòu)應(yīng)用到關(guān)鍵字索引結(jié)構(gòu)中，并且給出了安全性驗證。Chuah等人[12]提出了支持多關(guān)鍵字的模糊搜索模型，該模型中加入了分層樹的結(jié)構(gòu)，使得關(guān)鍵字搜索的效率更高。該方案還可以對文件集合和索引進行更新，但是由于該方案基于布隆過濾器，所以無法進行刪除操作，并且查詢準確性無法得到保障。在2013年，Zhou等人[13]和Wang等人[14]分別提出了不同的模糊關(guān)鍵字搜索方法，其中文獻[13]給出了可排序模糊關(guān)鍵字搜索方案，文獻[14]提出了一種可驗證的模糊關(guān)鍵字搜索方案。在2015年，Wang等人[15]提出了一種基于非雙線性對的模糊關(guān)鍵字搜索方案，在2017年，Zhu等人[16]在模糊關(guān)鍵字的基礎(chǔ)上又添加了訪問控制的功能，將模糊關(guān)鍵字加密搜索的應(yīng)用場景再一次進行了拓寬。

文獻[17]方案的PEKS是不可區(qū)分的，因此該方案可能會受到關(guān)鍵字選擇攻擊。為了信息傳輸?shù)陌踩?，Boneh等人[7]提出了一種無安全信道的公鑰加密搜索方案。該方案僅支持精確的關(guān)鍵字搜索，在文獻[1,17]研究的基礎(chǔ)上，本文提出一種無安全信道的模糊關(guān)鍵字搜索方案，如圖1所示。

圖1 本文方案架構(gòu)圖

本文方案主要包括6個構(gòu)造步驟，前3個步驟是由第三方可信機構(gòu)執(zhí)行，產(chǎn)生公共參數(shù)、服務(wù)器公私鑰和數(shù)據(jù)擁有者的公私鑰。數(shù)據(jù)擁有者執(zhí)行加密算法，將數(shù)據(jù)文件加密，將密文和加密數(shù)據(jù)上傳到服務(wù)器中保存。

用戶進行關(guān)鍵字搜索時，將包含關(guān)鍵字的陷門發(fā)送給服務(wù)器，服務(wù)器執(zhí)行測試算法，將搜索結(jié)果返回給用戶，且不泄露任何關(guān)鍵字信息。

本文方案不僅支持模糊關(guān)鍵字搜索，且不需要安全信道進行數(shù)據(jù)傳輸,這大大提高了系統(tǒng)的可用性與安全性。

1 雙線性對

設(shè)G1和G2是定義在相同的素數(shù)階p上的乘法循環(huán)群，g是G1的生成元。雙線性映射：e:G1×G1=G2，有以下性質(zhì)：

2)可計算性：對于?U,V∈G1，能夠有效地計算e(U,V)。

3)非退化性：?U,V∈G1，有e(U,V)≠1。

2 方案構(gòu)造

本文方案的具體構(gòu)造如下：

1)Setup(k)。產(chǎn)生素數(shù)階群q≥2k的2個組g1=

和g2，P是g1的一個隨機生成器，雙線性對e:g1×g1=g2。指定哈希函數(shù)h1:{0,1}*→g1，h2:g2→{0,1}k。返回cp=(q,g1,g2,e,P,h1,h2,Kw)。其中Kw表示關(guān)鍵字空間的描述。

編輯距離為d，數(shù)據(jù)發(fā)送者為關(guān)鍵字wi構(gòu)建一一對應(yīng)的索引，使用通配符技術(shù)建立模糊關(guān)鍵字索引集合Swi,d。集合Swi,d中的元素是使用通配符表示的關(guān)鍵字，通配符的個數(shù)就是編輯距離的大小。在加密算法中，數(shù)據(jù)擁有者對w′i∈Swi,d進行加密。

5)Trapdoor(cp,skServ,w′)。Tw′=ah1(w′)，輸出Tw′作為陷門。

6)Test(cp,Tw′,pkSender,M)。如果計算h2(e(BQP-1+Tw′,U))=V成立，則輸出“正確”，表示匹配成功,返回文件索引f；如果不成立則返回“錯誤”。

3 安全性分析

3.1 正確性分析

下面是驗證過程的正確性：

在本文方案的驗證階段，首先計算k的值：

k=(e(Q,B)e(h1(w′i),A))x

=e(xQ,bP)e(xh1(w′i),aP)

(1)

然后計算e(BQP-1+Tw′,U)的值，即：

e(BQP-1+Tw′,U)=e(BQP-1,U)e(Tw′,U)

=e(xQ,bP)e(xh1(w′),aP)

(2)

如果式(1)和式(2)中的w′i=w′，則搜索驗證通過，服務(wù)器將返回含有待搜索模糊關(guān)鍵字的索引文件。

3.2 安全性分析

定義1BDH問題。

定義2BDH假設(shè)。

本文方案的密文不可偽造是基于BDH的困難性問題。在本文方案的Encrypt算法中，將(aP,bP)嵌入到公鑰中，并且對于帶加密的關(guān)鍵字，使用服務(wù)器公鑰和發(fā)送者的公鑰進行加密運算。由于HASH函數(shù)h2的不可逆性，將隨機數(shù)x嵌入到加密密文中，因此，攻擊者無法對密文進行偽造。

本文方案的陷門滿足陷門不可偽造安全性。陷門的安全使得外部攻擊者對搜索信息一無所知。因為待搜索的關(guān)鍵字嵌入在了HASH函數(shù)h1(w′)中。將h1(w′)和服務(wù)器私鑰a相結(jié)合可得陷門Tw′=ah1(w′)。由于外部攻擊者無法獲得服務(wù)器的私鑰，因此外部攻擊者無法對陷門進行偽造，實現(xiàn)了陷門的不可偽造性。

本文方案在進行密文傳輸時不需要額外的安全信道來保證信息的安全性。將服務(wù)器私鑰和陷門算法相結(jié)合，即使外部攻擊者截取了陷門Tw′，但是無法獲取到服務(wù)器的私鑰，因此外部攻擊者無法獲得陷門與關(guān)鍵字之間的對應(yīng)關(guān)系，對于陷門中的內(nèi)容一無所知，因此確保了陷門在公共信道上傳輸?shù)陌踩浴?/p>

4 性能分析

將本文方案與之前的方案進行對比，結(jié)果如表1所示。

表1 各方案的特征對比

通過對比發(fā)現(xiàn)，本文方案和文獻[19]方案在功能和安全性上有著相同的特性，下面將本文方案與其他2種方案的效率進行對比。在算法執(zhí)行過程中，主要運算有指數(shù)運算、雙線性對運算和乘法操作，其中雙線性對運算的代價較高。本文使用tP、tE和tM分別表示指數(shù)操作、雙線性映射和乘法操作,效率對比如表2所示。

表2 本文方案與其他方案效率對比

方案加密階段和驗證階段的效率對比如圖2和圖3所示。

圖2 加密算法計算效率對比

圖3 驗證算法計算效率對比

通過分析表明，本文方案在具有相同功能的方案中具有優(yōu)秀的性能表現(xiàn)。在測試和解密階段，本文方案也擁有較為明顯的效率優(yōu)勢。

5 結(jié)束語

本文提出了一種無安全信道的模糊關(guān)鍵字加密搜索方案，并驗證了該方案的安全性。針對大多數(shù)可搜索加密方案需要安全信道的缺點，本文提出的方案不需要安全信道的特點大大增加了系統(tǒng)的使用場景，在效率分析階段，本文對比了具有相同功能的無安全信道的模糊關(guān)鍵字加密搜索方案，通過對比發(fā)現(xiàn)，在具有相同功能的方案之中，本文方案有著更高的執(zhí)行效率。