一種無(wú)安全信道的模糊關(guān)鍵字搜索加密方案

曹永明

(河海大學(xué)計(jì)算機(jī)與信息學(xué)院,江蘇 南京 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)鍵字搜索的容錯(cuò)能力。

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

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

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

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

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

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

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

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

1 雙線性對(duì)

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

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

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

2 方案構(gòu)造

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

1)Setup(k)。產(chǎn)生素?cái)?shù)階群q≥2k的2個(gè)組g1=

和g2，P是g1的一個(gè)隨機(jī)生成器，雙線性對(duì)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)建一一對(duì)應(yīng)的索引，使用通配符技術(shù)建立模糊關(guān)鍵字索引集合Swi,d。集合Swi,d中的元素是使用通配符表示的關(guān)鍵字，通配符的個(gè)數(shù)就是編輯距離的大小。在加密算法中，數(shù)據(jù)擁有者對(duì)w′i∈Swi,d進(jìn)行加密。

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

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

3 安全性分析

3.1 正確性分析

下面是驗(yàn)證過(guò)程的正確性：

在本文方案的驗(yàn)證階段，首先計(jì)算k的值：

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

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

(1)

然后計(jì)算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′，則搜索驗(yàn)證通過(guò)，服務(wù)器將返回含有待搜索模糊關(guān)鍵字的索引文件。

3.2 安全性分析

定義1BDH問(wèn)題。

定義2BDH假設(shè)。

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

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

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

4 性能分析

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

表1 各方案的特征對(duì)比

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

表2 本文方案與其他方案效率對(duì)比

方案加密階段和驗(yàn)證階段的效率對(duì)比如圖2和圖3所示。

圖2 加密算法計(jì)算效率對(duì)比

圖3 驗(yàn)證算法計(jì)算效率對(duì)比

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

5 結(jié)束語(yǔ)

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