基于橢圓曲線加密的多關鍵詞可搜索加密方案

(1.山東師范大學 信息科學與工程學院，山東 濟南 250358； 2.山東師范大學 山東省分布式計算機軟件新技術重點實驗室，山東 濟南 250014)

近年來，云計算技術不斷發展形成的第三代信息技術深刻影響著人們的生產和生活方式，該技術的發展為學術界、互聯網行業和全球經濟的發展提供了重要機會。在這個信息大爆炸的時代，用戶利用網絡進行資源共享，在共享資源的過程中，用戶將數據資源上傳至云服務器，共享數據的安全性成為一大隱患，因此，對用戶上傳的數據進行隱私保護性研究具有非常重要的意義。用戶將數據文件上傳至云服務器之前，對隱私數據進行適當加密，有助于保護合法訪問和數據隱私，但是這種加密機制給數據高效利用和搜索帶來了挑戰。加密數據的另一個問題是為合法數據用戶提供無障礙訪問。大多數情況下，數據用戶只想檢索特定會話的幾個特定數據文件，為了確保用戶的需求，最常用的方法是提供基于關鍵詞的可搜索機制。到目前為止，為了實現對數據文件檢索的高效性、安全性以及低開銷，國內外許多云計算數據安全領域的專家在可搜索加密方案中對模型和算法進行了大量的研究和改進[1-3]。當用戶下載數據文件時，為了迅速找到相關文件，系統就會使用關鍵詞搜索方式來尋找數據文件。

傳統的單一關鍵詞可搜索加密方案是建立一個加密的可搜索索引，使相關內容被隱藏，當用戶搜索文件時，首先提交需要查詢的文件的關鍵詞，然后系統根據該關鍵詞形成相關的查詢門限，根據查詢門限來遍歷文檔，返回最佳結果。2000年，Song等[4]在可搜索加密方案中加入對稱密鑰思想，該方案利用單一關鍵詞進行遍歷文檔，耗費時間長，效率低。2003年，Goh[5]在搜索方案中加入布隆過濾器對數據文檔建立索引，攻擊者很難獲得已加密密文的具體內容；但是，由于它對關鍵詞進行檢索時需要對每個文件進行計算與判斷，因此，在判斷過程中存在正向誤檢概率，導致檢索時間增加。2006年，Curtmola等[6]在可搜索加密方案建立索引過程中使用倒排索引的方式，該方案在搜索過程中能夠同時實現搜索的精確性和有效性，但也存在問題，如系統無法對已經搜索過的關鍵詞進行相關性評估。2007年，Boneh等[7]在基于可搜索加密方案的基礎上加入了公鑰密碼系統(public key cryptosystems,PKC)，在該方案中，擁有公鑰的用戶將加密數據文件上傳至云服務器，加密是為了保護數據文件的安全性，只有擁有私鑰授權的合法用戶才能夠訪問服務器，使用數據資源。2009年，Zerr等[8]提出了基于秩序保留映射的相關性分數的訓練和預采樣，每當需要插入不同的分數時，該映射面臨分數變換函數的重建問題。由于有助于加快查詢執行速度，因此高效檢索與給定查詢最相關的前k個文檔(top-k)成為標準的信息檢索方法，即使對大型索引也是如此。信息過載是搜索方案帶來的一個主要問題，而top-k方法就是通過處理僅限于高排名和最相關的文檔來減少信息過載。2010年，Pang等[9]提出了一種基于向量模型的安全搜索方案，該方案中加入了訪問控制技術的思想，但是，該技術的加入使用戶在計算方面增加一定的開銷，同時，用戶在使用查詢關鍵詞進行遍歷文件時，隱私信息也容易泄露。2011年，Cao等[10]提出一種云環境下對多關鍵詞進行排序的密文排序檢索方案，該方案在計算關鍵詞與文檔相似性方面使用了“內積相似性”的計算方法，該方法簡化了計算過程，提高了計算效率，并使用基于安全k近鄰分類(k-nearest neighbor classification,KNN)查詢技術對關鍵詞進行相關度排序。2012年，Chen等[11]使用雙線性配對思想對多關鍵詞檢索方案進行改進，但是，該方案中配對的方式會導致服務器和用戶計算成本較高。2014年，Sun等[12]提出了基于關鍵詞分數的多關鍵詞搜索方案，為了提高搜索效率，該方案將樹的索引結構和多維算法相結合，使得實際搜索效率遠優于線性搜索。2015年，陸海虹等[13]提出了安全云環境中基于最小哈希函數的多關鍵詞檢索方案，該方案根據數據所有者生成并外包給云服務器的加密可檢索索引進行加密云檢索。2017年，王愷璇等[14]在密文檢索方案中加入用布隆過濾器和位置敏感哈希函數技術，提出一種針對模糊的多關鍵詞的密文搜索方案，能夠有效地實現多關鍵詞的密文模糊搜索。

基于以上對可搜索加密方法的研究，本文中對關鍵詞可搜索加密技術進行改進，利用橢圓曲線加密(elliptic curve cryptography,ECC)的思想和多關鍵詞可搜索加密方案相結合的方法，將ECC算法用于可搜索的索引，對關鍵詞進行加密、編碼以及解密處理。使用詞頻-逆文檔頻率計算公式對關鍵詞與數據文檔相關性進行相關性分數計算，系統根據相關性分數可以選擇出最符合用戶查詢的數據文件。另外，索引結構使用倒排序索引結構，用以提高數據文件關鍵詞的遍歷速度。

1 基本知識

1.1 橢圓曲線加密機制

Diffie和Hellman于1973年引入的公鑰加密技術為密碼學領域帶來了一場動態革命，這一巨大的發展緩解了對稱密鑰密碼的密鑰分配問題，例如利用Rivest-Shamir-Adleman(RSA)公鑰加密算法定義整數分解問題，將公鑰密碼體制和橢圓曲線思想相結合解決離散對數問題。1985年，Koblitz和Miller在橢圓曲線和密碼學的基礎上，提出了將二者相結合的橢圓曲線密碼學模型，在此之前，專家Lenstra提出橢圓曲線大數分解模型，Goldwasser和Kilian提出素性檢驗的思想。橢圓曲線密碼學模型的提出使得數學與密碼學相結合的理念得到巨大的發展。該模型的思想是由線域上的橢圓曲線構成的群來代替公鑰密碼體制中有線域乘法群，從而獲得加入橢圓曲線思想的公鑰密碼體制。橢圓曲線密碼學的安全性基于陷門功能，其中假設找到關于公知基點的隨機橢圓曲線元素的離散對數是不可行的，這被稱為橢圓曲線離散對數問題(elliptic curve discrete logarithm problem,ECDLP)，其被認為在計算上是不可行的。與其他方案相比，ECC機制具有更多動態可用性，可用于消息加密、描述、密鑰交換以及數字簽名。與RSA算法相比，ECC算法的優勢在于密鑰小，可以使用相當小的密鑰來獲得相同的安全標簽。橢圓曲線Diffie-Hellman(elliptic curve Diffie-Hellman,ECDH)算法是廣泛使用的密鑰協商算法，并且在許多國際標準中有詳細說明。基于消息的ECC算法顯然涉及發送方執行短暫靜態ECDH密鑰協議，然后使用生成的共享密鑰和對稱加密算法對數據加密，因此，橢圓曲線集成加密方案(elliptic curve integrated encryption scheme,ECIES)是目前加密方法中是最流行的方案。ECC算法能夠用于身份驗證、數字簽名驗證、安全密鑰交換和加密，在本文中僅用于關鍵詞的加密和解密。

1.2 加性同態加密

同態加密是一種主要用來解決數學難題的計算復雜性理論的密碼學技術。輸入數據A，系統對數據A進行同態加密處理，將處理完畢得到的數據輸出，得到A′，系統對加密的數據A′進行解密操作，得到解密數據，解密得到的數據結果與用同一方法處理未加密的原始數據得到的輸出結果是一樣的。同態性被廣泛地分類為多種類型，廣義上稱為加性同態、乘法同態、線性同態、指數同態、有針對性的同態和完全同態。定義1對加法同態做了簡單的介紹。

定義1加性同態加密。

如果存在有效算法?，E(x+y)=E(x)?E(y)或者x+y=D(E(x)?E(y))成立，則該方案是加性同態加密。

本文中將加性同態加密屬性用于可搜索加密方案，對獲取每個文件關鍵詞進行編碼以及加密處理，使其更加安全，數據用戶根據加性同態性質能夠獲得真實值并選擇正確的文件。

1.3 詞頻-逆文檔頻率

1.4 倒排序索引結構

倒排序索引結構主要用于位置的定位。該索引結構中保存著某一單詞在一組文檔中的位置信息，因此在文檔檢索系統中得到廣泛的應用。在文檔檢索系統中，根據倒排序索引結構能夠迅速找到包含所查詢關鍵詞的相關文檔列表。倒排索引結構由“詞典”和“倒排文件”2個部分組成。文檔集合中出現過的所有單詞所形成的集合即“詞典”，“詞典”索引項中不僅僅包含單詞的相關信息，還包含指向“倒排列表”的指針。文檔中出現的所有單詞放在列表中，形成倒排列表，該表按一定的順序存放在某個文件中，形成倒排文件。倒排索引項主要由以下幾部分組成：某一個文檔的信息，例如文檔的編號(FiID)；文檔中某一個單詞出現在該文檔中的頻率(TF)；該單詞在文檔中的位置信息(Loc)等。倒排列表就是由這些包含相關信息的倒排項組成。在用戶下載文件過程遍歷索引結構時，首先查找到索引項，根據索引項中的關鍵詞位置的信息找到相關文件中的記錄，倒排文件根據關鍵詞建立索引形成倒排表，利用倒排表進行關鍵詞的搜索遍歷。在任何復雜的布爾詢問過程中，倒排序索引結構只需要訪問一次，訪問后即可得到肯定或否定的回答，因此，它的文檔檢索效率比較高。圖1所示為傳統的倒排索引結構。

圖1 傳統的倒排序索引結構

在可搜索加密過程中，用戶將數據文件上傳至云服務器便于其他用戶共享，其他用戶在下載資源的過程中容易造成數據泄露，受到非法用戶攻擊。為了更加安全地保護數據資源以及實現更加安全的高效密文檢索方案，本文中在傳統的倒排序索引結構上進行改進，利用ECC算法生成的關鍵詞點進行加密后(加密曲線點-文件)作為倒排序索引結構“關鍵詞-文件”的結構，用加密得到的密文邏輯指針、密態邏輯地址，替換原來索引結構中的邏輯指針和邏輯地址，形成安全的倒排序索引結構，如圖2所示。

圖2 安全的倒排序索引結構

2 方案設計

2.1 方案模型

系統參與者包括3個主體，即數據擁有者、數據用戶和云服務器，模型圖如圖3所示。

1)數據擁有者。數據擁有者被視為數據集的主要貢獻者和控制者，負責通過云服務器外包數據，以方便使用相應的合法數據。數據擁有者對關鍵詞進行處理，利用橢圓曲線的思想，將關鍵詞集合加載在曲線上形成曲線點，并對其進行加密。在可搜索加密方案中，數據擁有者使用加密關鍵詞集合創建倒排序索引結構，并將加密的數據文件、索引結構等相關信息上傳至云端服務器。

2)數據用戶。數據用戶接收數據擁有者共享的關鍵詞、對稱密鑰和其他參數。數據用戶生成對所需關鍵詞的請求，并將查詢向量發送給云服務器，在接收到返回值后對其進行解碼并選擇所需文件，數據用戶用相應的對稱密鑰解密。

3)云服務器。云服務器提供數據托管服務，并存儲從數據擁有者外包的加密數據和索引，為數據用戶提供相應關鍵詞陷門請求的搜索服務。本文中所提方案傾向于在云服務器端保持最大可能地處理和計算，以使其適合數據用戶，并希望保持最少的計算開銷。

圖3 方案模型

2.2 可搜索加密過程

基本的可搜索加密過程主要有4個步驟，即參數生成、索引建立、陷門生成以及檢索查詢。

1)參數生成。在可搜索加密過程中，數據擁有者根據選擇的加密方案產生相關密鑰，該密鑰用于對文件、可搜索索引以及檢索請求的加解密。

2)索引建立。多個數據文件形成文件集合C，數據擁有者從中提取關鍵詞，形成關鍵詞集合W，利用關鍵詞集合生成可搜索索引I，選擇加密算法，將索引I加密形成更加安全的索引結構I′，最后將安全索引I′與加密的數據文件集合上傳至云端服務器。

3)陷門生成。數據用戶在使用云端文件時，首先獲得數據擁有者的授權，根據查詢關鍵詞w生成檢索請求Q，并根據該檢索請求生成與安全索引兼容的陷門T進行檢索。

4)檢索查詢。數據用戶將安全陷門T上傳至云服務器端，云服務器根據陷門遍歷，并返回給數據用戶相關度最高的文檔，數據用戶對文檔進行解密并使用。

2.3 具體工作過程

基于ECC算法的可搜索加密過程主要由7部分組成。

1)初始化階段。

①在所提出的方案中，數據擁有者與數據用戶共享關鍵詞、對稱密鑰、ECC密鑰和參數。ECC公鑰實際上是橢圓曲線上的點。

②數據擁有者從包含n個文件的數據集C中提取關鍵詞集合W=(w1,w2,…,wi)，并且計算每個關鍵詞的詞頻F和逆文檔頻率F′，得到相關性分數Sw，對每個數據文件設置標識符，形成文件標識符FidD=(fid1,fid2,…,fidn)。

2)對關鍵詞進行預處理，將關鍵詞編碼在橢圓曲線上。

①曲線密鑰生成。數據所有者選擇ECC參數，其中E是有限域GF(P)上的橢圓曲線，V是曲線E上的點，生成隨機安全參數λ，λ∈GF(P)。公鑰Pλ=λV，輸出私鑰λ和公鑰Pλ。

②關鍵詞消息編碼。編碼(W,PW)，將提取的關鍵詞集合W編碼到曲線E的生成點Vi上，輸出PW(PW為橢圓曲線E上的關鍵詞集合W的表示)，PW=WVi，PW∈E。

③加密關鍵詞信息點。前面已經對關鍵詞信息編碼到橢圓曲線上，為了更加安全，需要對其進行加密處理，加密過后的關鍵詞信息點更加安全。利用公鑰Pλ對PW進行加密，輸入(Pλ,PW)，輸出PS(S1,S2),PS是加密關鍵詞信息對，PS∈E。隨機選取整數d∈[1,h-1]，h是曲線上的的E順序，其中S1=dV1，S2=Pwi+Pλ，處理完畢后，返回PS(S1,S2)的加密關鍵詞信息對。

④解密。在對關鍵詞進行加密的同時還需要對關鍵詞進行解密操作。具體的解密操作為：輸入密鑰λ，加密關鍵詞信息對PS(S1,S2)，輸出PW，其中Pwi=-λS1+S2，S2=PW+dPλ，計算完畢后，返回PW。

3)索引建立。

將加密的關鍵詞信息對PS、加密得到的密文邏輯指針、密文邏輯地址以及密文倒排地址集建立倒排表，這樣加密的項保證索引結構的加密性。系統輸出倒排索引結構I，其中I=(I1,I2,…,In)。為了索引的安全性，利用公鑰Pλ對倒排序索引結構進行加密操作E(Pλ,I),形成加密索引結構I′。

4)文件加密。

5)陷門生成。

6)檢索文件。

由云端服務器執行檢索算法。服務器根據安全的加密索引結構I′，密態關鍵詞信息對PS、密態邏輯指針、密態邏輯地址以及密態倒排地址集找到對應的密文文檔M(Dwi)，根據相關性分數Sw返回合適的文檔，并將其返回給數據用戶。

7)文件解密。

由數據用戶執行密文解密算法，即輸入密鑰Ky和得到的密文文件M(Dwi)進行解密，輸出包含檢索關鍵詞wj的明文文檔Dw。

3 分析

3.1 安全性分析

1)索引和查詢機密性。該方案利用ECC算法對關鍵詞進行處理，并對其進行加密，曲線上存在許多可能性，并且返回的加密結果值永遠不會相同，該值總是出現在不同的點上，使得猜測或模式分析攻擊變得不可行，保證了其安全性。方案中使用倒排序索引結構，對倒排表中的項都進行加密處理，建立安全的倒排序索引結構，保證可搜索加密方案實施過程中的安全性。

2)ECC算法的性質決定了所有加密值都是以點對的形式出現的，這種非常隨機的點對使得它可以抵御統計分析攻擊。

3)對關鍵詞安全的加性進行證明。有關鍵詞w1、w2,在橢圓曲線E上編碼為點PW1、PW2,利用Pλ對關鍵詞Pw1、Pw2加密，形成的密態關鍵詞對PS(S1,S2)，PS(S1,S2)是編碼到橢圓曲線上的點。

(Pλ,PW1)=PS1(S1x,CS1y)，

證明：加密時，對關鍵詞PW1、PW2分別加密得到

(Pλ,PW2)=PS2(S2x,CS2y)，

式中

S1x=d1V,CS1y=PW1+d1Pλ,

S2x=d2V,CS2y=PW2+d2Pλ，

其中d1、d2是對應生成的隨機數。

有加性同態解密公式

(PS1+PS2)=PW1+PW2，

利用該公式可以證明關鍵詞解密的正確性，證明過程如下：

PS1+PS2=(S1x,CS1y)+(S2x,CS2y)=

(d1V,PW1+d1Pλ)+(d2V,PW2+d2Pλ)=

(d1V+d2V)+(PW1+d1Pλ+PW2+d2Pλ)=

(d1+d2)V+(PW1+PW2)+(d1+d2)Pλ。

解密時，取加密后的關鍵詞對PS1+PS2、(d1+d2)V以及私鑰λ，得到(d1+d2)Vλ，其中Pλ=λV,有等式

-(d1+d2)Vλ+(PW1+PW2)+(d1+d2)Pλ=PW1+PW2，

因此,PS1+PS2=PW1+PW2。

以上分析過程證明了關鍵詞加、解密過程的正確性。

3.2 實驗分析

以下對所提出的方案進行實驗。實驗操作系統采用Linux操作系統(Ubuntu 14.04.1)，語言采用Python 2.7.3，虛擬機工作站上使用Intel i5，2.20 GHz雙核處理器和1 GB存儲器。在可搜索加密過程中，計算關鍵詞相關性分數，采用的數據集通過社交網絡應用程序接口(API)收集。數據集合有數據文件500個，包含93 572個的單詞，選取10個單詞作為搜索索引的關鍵詞。同時對關鍵詞進行加密操作，最多可以包含90個文件作為樣本。

1)ECC算法與RSA算法加密時間。計算性能是衡量一個密碼系統的重要指標。圖4所示為相同的密鑰長度下的ECC算法和RSA算法的加密時間的對比。從圖中可以看出，除了密鑰長度為1 B時兩者加密時間差不多，其他相同密鑰長度時，基于ECC算法的加密時間都明顯小于RSA算法的。

2)陷門生成時間。用戶將數據文件上傳至云服務端，通過一系列加密操作，對數據文件進行保護。

圖4 橢圓曲線加密機制與公鑰加密算法加密時間的對比

其他用戶在使用該文件時需要對數據文件進行遍歷，需要獲得合法許可才能使用。用戶在搜索文件時需要產生陷門，圖5所示為橢圓曲線加密算法與文獻[15]中的算法陷門生成時間的對比。由圖可見，隨著關鍵詞數量的增加，陷門產生的時間也隨之增加，ECC算法與文獻[15]中的算法相比較，二者陷門產生時間相差不是很大，但是也顯示出一定的優勢。

圖5 橢圓曲線加密算法與文獻[15]中的算法陷門生成時間的對比

3)檢索時間。在數據文檔遍歷過程中，隨著關鍵詞數量的增加，檢索數據文檔的時間也會隨著增加。圖6所示為傳統的倒排序索引結構與安全的倒排序索引結構檢索時間的對比。從圖中可以看出，隨著關鍵詞數量的增加，兩者的檢索時間逐漸增加。在安全的索引結構中，需要對關鍵詞進行提取以及解密等一系列操作；因此，密文檢索的時間開銷必然會增大，但是增加的幅度不是很大，對各個檢索關鍵詞都是毫秒級的。

圖6 傳統的倒排序索引結構與安全的倒排序索引結構檢索時間的對比

4 結語

為了提高數據的遍歷速度以及加強數據的安全性，本文中對關鍵詞可搜索加密技術進行改進，將ECC的思想與多關鍵詞可搜索加密方案相結合。在可搜索加密過程中用ECC算法對關鍵詞進行編碼、加密以及解密操作，使用詞頻-逆文檔頻率公式對關鍵詞進行相關性分數計算，用戶在遍歷文檔時可以根據分數獲取最符合查詢要求的文檔，使用倒排序索引結構，提高遍歷文件的速度。在Linux系統中進行實驗，并與其他算法進行對比，本文中提出的方案在關鍵詞檢索以及陷門生成效率方面有所改善，因此，本文中提出的基于ECC算法的多關鍵字可搜索加密方案在檢索文件方面具有高效性和安全性。