云存儲的多關(guān)鍵字公鑰加密搜索

向 軍，陳志華

（湖北民族學(xué)院 信息工程學(xué)院，湖北 恩施 445000）

0 引 言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，基于互聯(lián)網(wǎng)技術(shù)的云計算應(yīng)運而生。云計算是一種按需服務(wù)、擴展性強、使用方便的網(wǎng)絡(luò)服務(wù)，是一種分布式計算形式。云存儲技術(shù)由于具有成本低、容量大、擴容即時、訪問透明等優(yōu)點，受到很多用戶的親睞。越來越多的用戶傾向于依賴云計算服務(wù)商提供的安全服務(wù)來確保他們的信息安全，安全隱憂隨之而來：一種是來自外部黑客的攻擊導(dǎo)致服務(wù)器信息泄露；另一種是內(nèi)部人員在獲得了足夠高的權(quán)限時，可以繞開數(shù)據(jù)的安全訪問控制策略，直接獲取數(shù)據(jù)。為解決數(shù)據(jù)隱私保護問題，采用用戶數(shù)據(jù)加密是較常見的解決方法，數(shù)據(jù)加密后再將其保存在服務(wù)器中。當(dāng)存儲在云端的加密數(shù)據(jù)形成規(guī)模之后，對加密數(shù)據(jù)的檢索成為迫切需要解決的問題[1]。文獻(xiàn)[2]提出一種使用流密碼對關(guān)鍵字集進(jìn)行加密和解密的方法，一次一密的使用方式對統(tǒng)計分析攻擊具有很強的抵御力，不足之處在于搜索量比較大時，由于要逐次匹配密文信息，效率低。文獻(xiàn)[3]中提出采用安全索引方法，該方法可以克服用簡單索引算法導(dǎo)致的密文易受統(tǒng)計攻擊的缺陷，但是需要大量的密鑰序列，檢索次數(shù)變多時，計算復(fù)雜度線性增加。文獻(xiàn)[4]中提出一種關(guān)鍵字隱私保護的排序搜索算法，此算法思想是：當(dāng)查詢返回多個加密文檔時，先對加密文檔排序，然后再將查詢中的最相關(guān)文檔顯示給用戶。此算法不適用于多關(guān)鍵字查詢。文獻(xiàn)[5]提出基于關(guān)鍵字的公鑰加密搜索算法，數(shù)據(jù)發(fā)送方使用數(shù)據(jù)接收者的公鑰加密數(shù)據(jù)建立索引，發(fā)送到云端服務(wù)器，數(shù)據(jù)接收方使用自己的私鑰完成搜索過程。但是目前的方案比較復(fù)雜，而且針對的一般是單關(guān)鍵字，適合多關(guān)鍵字的解決方案不完善，本文主要研究的是多關(guān)鍵字的公鑰加密搜索方案。

1 基于關(guān)鍵字的公鑰加密搜索方案

基于關(guān)鍵字的公鑰加密搜索方案中的信息或文檔的發(fā)送方可以是任何人，但是接收方必須使用自己的私鑰才能完成搜索。該方案包括三個實體：

1）發(fā)送方：使用對稱或非對稱加密算法加密文檔，然后使用接收方的公鑰加密關(guān)鍵字集合來建立索引。

2）接收方：數(shù)據(jù)的接收者，也是搜索者，使用關(guān)鍵字陷門在服務(wù)器上完成搜索。

3）服務(wù)器：數(shù)據(jù)的存儲地點，在接收者提供陷門時，進(jìn)行關(guān)鍵字搜索匹配，匹配成功，返還加密數(shù)據(jù)給接收者；反之，不返還數(shù)據(jù)。

Boneh提出的PEKS方案中還包括密鑰生成函數(shù)、加密函數(shù)、陷門函數(shù)、測試函數(shù)。主要步驟如下：

1）接收者選取安全參數(shù)k生成自己的公私密鑰對（pk,sk），然后公布自己的公鑰pk。

2）發(fā)送者將要發(fā)送的文檔分為兩個部分：文檔數(shù)據(jù)和關(guān)鍵字集合，首先使用對稱或非對稱的加密方案加密文檔，然后使用接收者的公鑰加密關(guān)鍵字集合，將文檔密文和關(guān)鍵字集合密文一起發(fā)送到服務(wù)器。

3）接收者進(jìn)行搜索時，選擇關(guān)鍵字以及自己的私鑰，生成陷門，發(fā)送到服務(wù)器。

4）服務(wù)器測試函數(shù)匹配陷門，成功返還包含關(guān)鍵字密文文檔給用戶，反之返還無關(guān)鍵字密文文檔。

5）接收者解密密文文檔，獲得文檔信息。

可搜索公鑰加密方案主要分為：單關(guān)鍵字可搜索加密方案、多關(guān)鍵字可搜索加密方案。文獻(xiàn)[6]關(guān)注的是大量關(guān)鍵字搜索時的情形，線性索引結(jié)構(gòu)在搜索時，作者通過把關(guān)鍵字通過哈希值劃分到同一鏈表，在搜索時知道關(guān)鍵字分組，就能實現(xiàn)加速搜索的目的。文獻(xiàn)[7]使用橢圓曲線加密體制對關(guān)鍵字集合進(jìn)行加密，可以實現(xiàn)多關(guān)鍵字搜索，關(guān)鍵字必須是有序的，而且接收方在搜索時輸入的關(guān)鍵字順序必須和發(fā)送方順序?qū)?yīng)，同時在發(fā)送方產(chǎn)生的隨機數(shù)服務(wù)器是不知道的，本文搜索的關(guān)鍵字順序不需要和文本關(guān)鍵字順序一樣。

2 基于多關(guān)鍵字的公鑰加密搜索改進(jìn)方案

2.1 橢圓曲線加密體制

定義Fp為一個大素數(shù)域，Ep(a,b)為在域Fp上的橢圓曲線的點集合。定義一個非奇異的橢圓曲線方程y2=(x3+ax+b)modp，這里p是素數(shù)，a，b∈Fp，它們滿足(4a3+27b2)modp≠0。橢圓曲線定義如下：Gp={(x,y):x,y∈Fp,(x,y)∈Ep(a,b)}?{O}，O點表示“無窮遠(yuǎn)點”。在橢圓曲線中，其乘法定義如下：k.p=p+p+…+p（k個p相加）。如果n.p=O，且n取滿足上述等式的最小正整數(shù)，則稱點的階為n。

2.2 方案算法實現(xiàn)

1）密鑰產(chǎn)生：選擇安全參數(shù)1k，隨機選擇一個整數(shù)a(a∈Z*p)，用戶的公私鑰分別為：pk=A=ap,sk=a（p為橢圓曲線生成元）。

2）數(shù)據(jù)加密：發(fā)送方選擇哈希函數(shù)（H1:{0,1}*→Z*p，表示將一個0，1數(shù)串映射到一個階為q的素數(shù)域上某個數(shù)的HASH函數(shù)），并利用用戶的公鑰A對關(guān)鍵字集進(jìn)行加密，算法如下：Mi=H1(Wi)P+A，1＜i＜m，算法的輸出值為：S=[M1,M2,…,MM]。

如果關(guān)鍵字Wi=W′，那么：

搜索結(jié)果矩陣，如果P出現(xiàn)的個數(shù)為n，就說明搜索的關(guān)鍵字全部在文檔關(guān)鍵字集合里面，關(guān)鍵字搜索成功，服務(wù)器返回密文文檔。接收者解密密文文檔獲得文檔信息。

2.3 安全性分析

基于橢圓曲線上的離散對數(shù)，以及單向的HASH函數(shù)構(gòu)造而成是本文方案討論的重點。通常基于橢圓曲線上離散對數(shù)構(gòu)造出來的加密算法和基于離散對數(shù)和大數(shù)因子分解理論構(gòu)造出來的相比，具有以下特點：密碼安全級別高、密鋼長度比較短、構(gòu)造算法靈活性強，從而具備比較高的安全性[7]。針對整個可搜索公鑰加密算法，本文主要從以下四個方面進(jìn)行安全性分析：

1）明文的保密性：無論查詢文檔在發(fā)送到服務(wù)器之前采用的是對稱加密算法，還是非對稱加密算法，從安全性要求做到只有接收方在服務(wù)器關(guān)鍵字成功搜索后方可看見密文。上傳和搜索的全部過程都要求查詢文檔是加密后的文檔，若沒有接收方的解密密鑰，用戶是無法獲得查詢文檔的明文信息。

2）關(guān)鍵字的保密性：方案中兩個子算法都涉及到了文檔的關(guān)鍵字，一個是數(shù)據(jù)加密階段Mi=H1(Wi)P+A，HASH函數(shù)不可逆且函數(shù)在客戶端，服務(wù)器無法推導(dǎo)關(guān)鍵字信息；另一個是陷門加密階段關(guān)鍵字都是進(jìn)行M′=(H1(W′i)+a)-1計算的，服務(wù)器無法知道待搜索關(guān)鍵字的明文信息。

3）安全隔離查詢：在服務(wù)器檢索階段，只有服務(wù)器在矩陣運算完成搜索P的數(shù)量匹配成功后，服務(wù)器才能搜索到相應(yīng)的密文，并把密文發(fā)送到接收方，在整個過程中服務(wù)器對數(shù)據(jù)庫里面的密文一無所知，數(shù)據(jù)對服務(wù)器是隔離的。

4）提供受控査詢：若無合法用戶的請求陷門，服務(wù)器無法成功搜索關(guān)鍵字的密文。也就是說，一方面接收者的私鑰對其他用戶來說是保密的，攻擊者無法偽造，對查詢關(guān)鍵字起到了控制作用；另一方面計算陷門時使用HASH函數(shù)算法，HASH函數(shù)算法嵌入在關(guān)鍵字加密算法中，對陷門生成又起到了控制作用。

3 結(jié) 語

關(guān)鍵字公鑰加密搜索方案很好地解決了密文搜索問題，但是在多關(guān)鍵字的情況下，現(xiàn)有的多關(guān)鍵字的匹配運算比較復(fù)雜，運算效率不高，在對大量文件進(jìn)行檢索時，服務(wù)器檢索效率低。本文提出了一種多關(guān)鍵字公鑰加密搜索方案，公私鑰對是基于橢圓曲線密碼體制生成，在加密關(guān)鍵字時運用了單向的哈希函數(shù)，多關(guān)鍵字匹配時不需要待搜索關(guān)鍵字和文檔關(guān)鍵字順序保持一致，計算復(fù)雜度低，保密性較強。