面向云存儲的帶關鍵詞搜索的公鑰加密方案

郭麗峰 李智豪 胡 磊

1(山西大學計算機與信息技術學院 太原 030006)2(山西大學大數據科學與產業研究院 太原 030006)3(信息安全國家重點實驗室(中國科學院信息工程研究所) 北京 100093)

云存儲由于其低成本、具有無限數據存儲空間的特點，已受到廣泛重視和應用.用戶可以將大量數據存儲在云服務器上.但是云服務器并不完全可信，為了保證用戶數據的安全，用戶的敏感數據通常需要加密后再存儲在云服務器上.但是在傳統的密文存儲和查詢服務中，由于云服務器沒有檢索功能，不能根據用戶需求查找數據.帶關鍵詞搜索的公鑰加密體制解決了在云服務器不可信的條件下加密數據檢索的問題.其主要思想是：發送者首先分別加密數據和關鍵詞上傳至云服務器；然后接收者發送一個由關鍵詞生成的陷門給云服務器；最后云服務器執行關鍵詞密文和陷門的匹配算法.云服務器判斷密文和陷門是否包含相同的關鍵字，若是則將密文數據發送給接收方，此過程云服務器不能獲得關鍵詞和明文數據的任何信息.

Boneh等人[1]在2004年首次提出了帶關鍵詞搜索的公鑰加密方案(public key encryption with keyword search， PEKS)(下文中的公鑰加密算法記為PEKS)，該方案是通過基于身份的加密方案(identity-based encryption， IBE)[2]所構造，其基本思想是：將PEKS中的關鍵詞w替代IBE中用戶的身份ID，將PEKS中接收者給服務器的陷門替代IBE用戶的私鑰，所以要求基于身份的加密方案必須具有匿名性才能轉換成帶關鍵詞搜索的公鑰加密方案.文獻[1]在接收者給云服務器傳輸陷門時，需要安全信道，導致昂貴的開銷，而且方案的安全性是在隨機預言模型(random oracle model， RO)下進行證明的.Baek等人[3]提出了無安全信道的可搜索加密方案(secure channel free PEKS， SCF-PEKS)，其方法是通過引入云服務器的公私鑰對來消除安全信道，只有指定的服務器才能夠對關鍵詞密文與陷門進行匹配.但是其方案也是在隨機預言模型下進行的安全性證明，而且在安全性證明中當云服務器為攻擊者時，云服務器的公私鑰對卻由模擬器來產生，這樣不符合實際要求，因為在公鑰加密體制中，公私鑰對應該由自己產生，而不應該由第三方產生.此后Rhee等人[4-5]加強了Baek等人的安全模型，即攻擊者的公私鑰對由其自己產生，這樣符合實際情況，并提出了一系列指定檢驗者的關鍵詞搜索方案(designated tester PEKS， dPEKS)，但是這些方案也是在隨機預言模型下可證明安全且不能抵制選擇密文攻擊.Fang等人[6]利用Gentry[7]的基于身份加密方案構造了標準模型下的帶關鍵詞搜索方案.隨后在文獻[8]中，通過引入一次性強簽名方案，能夠抵制選擇關鍵詞和密文攻擊.但文獻[8]在安全性證明中，敵手的公私鑰對也是由模擬器來產生.

2006年Byun等人[9]首次提出外部的離線關鍵詞猜測攻擊(resist external keyword guessing attack, REKGA)的概念，并對文獻[1，10]的PEKS方案進行了離線關鍵詞猜測攻擊;Jeong等人[11]指出:滿足一致性的PEKS方案一定不能夠抵制關鍵詞猜測攻擊;在文獻[12]的安全性證明中，指出僅當敵手能得到陷門且自己能進行驗證的前提下，該結論才成立，所以得出滿足一致性的PEKS方案一定不能夠抵制內部關鍵詞猜測攻擊，因為對于服務器來說，既能得到陷門又能自己進行陷門和關鍵詞密文的匹配驗證;Rhee等人[4]提出了陷門不可區分性的概念，并證明陷門不可區分性是抵抗外部關鍵詞猜測攻擊的充分條件，并提出了一個具體的方案抵制外部離線關鍵詞猜測攻擊;Guo等人[13]和Fang等人[8]構造出一個可抵抗外部敵手進行關鍵詞猜測攻擊的方案，并在標準模型下證明方案的安全性，但文獻[8，13]都不能抵制內部服務器進行離線關鍵詞猜測攻擊.

2013年Yau等人[14]提出文獻[12]不能抵制內部離線關鍵詞猜測攻擊，即當服務器是攻擊者的情況下的攻擊，其基本思路是服務器自己猜測一些關鍵詞，然后進行加密，由于服務器能夠得到陷門并且通過陷門進行檢驗，從而得出陷門包含了哪個關鍵詞;文獻[14]指出:相似于文獻[12]的PEKS方案構造都不能抵制上述攻擊,文獻[14]還提出了一種在線關鍵字猜測攻擊類型(online keyword guessing attack， OKGA)，這種類型的敵手是一個外部攻擊者，敵手可以對所有可能的關鍵詞w都配對一個虛假的明文數據m′，并將它們加密上傳至云服務器，并對服務器和目標接收者的通信進行監聽.一旦服務器將包含明文數據m′的加密文檔發送給接收者，攻擊者會知道接收者的陷門包含哪個關鍵詞.

為了抵制內部(即服務器)離線關鍵詞猜測攻擊，Shao等人[15]在Fang等人[8]的基礎上引入了發送者的身份，通過確定性RSA算法對發送者身份進行簽名，當服務器自己產生關鍵詞密文時，卻不能進行匹配測試.文獻[15]聲稱其方案能夠抵抗內部關鍵詞猜測攻擊，但文獻[16]指出，該方案中的服務器必須誠實地進行測試，但事實上，服務器可以是惡意的，同時Lu等人[16]指出文獻[8]不能抵制外部離線關鍵詞猜測攻擊，但服務器必須提供在線服務.文獻[16]在文獻[8]的基礎上提出一個能抵制內部離線關鍵詞猜測攻擊的PEKS方案，而且該方案在標準模型下可抵制選擇密文攻擊.2017年Huang等人[17]在對關鍵詞加密時引入發送者的私鑰，實現公鑰認證加密功能，從而抵制內部離線關鍵詞猜測攻擊，但是這個方案的陷門是固定的，且被指出不滿足密文不可區分性[18].Li等人[19]引入了權威機構對用戶進行授權認證，并產生對應的身份私鑰，隨后用戶用其私鑰對關鍵詞密文進行認證加密，但該方案仍舊是在隨機預言模型下進行的安全性證明.Lu等人[20]采用簽密的思想來抵制內部離線關鍵詞猜測攻擊，即在產生關鍵詞密文的過程中，使用發送者的私鑰，由于除了發送者，任何人不知道發送者的私鑰，敵手不能產生合法的關鍵詞密文來匹配任何關鍵詞陷門.這種構造方式的局限性是，當接收者產生關鍵詞陷門時，必須要涉及到發送者的公鑰或身份，所以相當于接收者事先委派了發送者，這樣會影響實際使用效果.使用這種技巧使得方案抵制內部關鍵詞猜測攻擊有文獻[17-22].文獻[23]通過將密文隨機化來抵制外部在線和離線關鍵詞猜測攻擊.文獻[20]指出構造具有任何搜索功能，而不受接收者委派，但是還能夠抵制各種關鍵詞猜測攻擊的PEKS方案是一個公開問題.

最近文獻[24]闡述了基于對稱密碼學和基于公鑰密碼學而構造的可搜索加密機制的不同特點，分析了可搜索加密機制在支持單詞搜索、連接關鍵詞搜索和復雜邏輯結構搜索語句的研究進展;文獻[25]首先介紹了關于可搜索加密的理論研究進展情況，最后指出了關于可搜索加密應用的公開問題和未來發展趨勢;文獻[26-28]都對可搜索加密進行了綜述性的總結，文獻[27]提出一種多用戶的可搜索方案，用戶按照自己的意愿設置訪問權限，不需要1個可信的用戶搜索中心，弱化了可信第三方的功能.

綜上所述，從6個方面對PEKS的安全模型進行總結：

1) 陷門是否通過公開信道傳輸.通過引入服務器的公私鑰對，使得在檢驗中必須使用服務器的私鑰才能檢驗，從而使得陷門可以在公開信道傳輸.

2) 是否在標準模型下進行安全性證明.因為隨機預言模型下進行的安全性證明只是一種啟發式證明，所以在標準模型下可證明方案的安全性是加密方案證明的終極目標.

3) 是否抵制適應性選擇關鍵詞攻擊.從2方面考慮：敵手為惡意的服務器或惡意的接收者.

4) 是否抵制關鍵字猜測攻擊.從3種情況考慮：外部離線關鍵詞猜測攻擊、外部在線關鍵詞猜測攻擊、內部離線關鍵詞猜測攻擊.

5) 在安全性證明中，敵手的私鑰是否必須由挑戰者來產生.實際情況是敵手自己產生私鑰，但在很多方案中，由于模擬器要利用敵手的私鑰，所以敵手的私鑰由模擬器來產生，不符合實際情況.

6) 是否抵制適應性選擇密文攻擊.已有的方案通過引入一次性強不可偽造簽名方案抵制適應性選擇關鍵詞攻擊.這樣使得所構造的方案效率較低.通過直接構造來抵制適應性選擇關鍵詞攻擊成為公開問題.

表1進行了總結，指出目前構造的一些PEKS方案滿足哪些安全性要求，其中一些安全性要求縮寫為：抵抗選擇關鍵詞攻擊(resist chosen keyword attack， RCKA)，分2種情況，攻擊者為服務器(server)或接收者(receiver)，抵制選擇密文攻擊(resist chosen ciphertext attack， RCCA)、抵制外部關鍵詞猜測攻擊(resist external keyword guessing attack， REKGA)、抵制內部關鍵詞猜測攻擊(resist internal keyword guessing attack， RIKGA)、認證功能(authentication Function， AF)、抵制在線關鍵字猜測攻擊(resist online keyword guessing attack，ROKGA).

Table 1 Performance Comparison of Security Model of PEKS表1 PEKS安全模型的性能對比

針對上述問題，本文的主要貢獻有3個方面：

1) 提出一種能夠抵制內部關鍵詞猜測攻擊的帶關鍵搜索的公鑰加密方案.目前使用的技巧是通過發送者在加密的同時使用了數字簽名，這樣使得內部攻擊者即服務器不能夠產生關鍵詞密文，從而抵制了內部關鍵詞猜測攻擊，相當于接收者事先需要指定密文的發送者.但是在很多實際情況下，接收者不知道發送者是誰.本文通過引入發送者和服務器的身份，并將其放在方案中算式的分母上，使得服務器無法自己產生關鍵詞密文，從而抵制內部關鍵詞猜測攻擊.

2) 由于關鍵詞密文能夠進行公開驗證其正確性，本文構造的方案能夠抵制適應性選擇密文攻擊，而且所構造的方案沒有使用額外的一次性強不可偽造簽名，從而方案的效率很高.

3) 本文的陷門是在公開信道傳輸，而且能夠抵制適應性選擇關鍵詞攻擊，且方案是在標準模型下可證明安全.

1 基礎知識

1.1 雙線性對

記G1=g表示由生成元g生成的有限群G1.輸入安全參數k，輸出雙線性映射的參數(p,g,G1,G2,e)，其中G1和G2是階為素數p的循環群，g是G1的生成元，映射e:G1×G1→G2具有3個性質：

2) 非退化性.對G1的生成元g，有e(g,g)≠1.

3) 可計算性.對于任意的g,h∈G1，存在多項式時間算法計算e(g,h).

1.2 相關的困難問題

1) 商判定雙線性Diffie-Hellman(QDBDH)假設.

2) 判定雙線性Diffie-Hellman(DBDH)假設.

3) Hash Diffie-Hellman(HDH)假設.

設hLen是一個整數且H:{0,1}*→{0,1}hLen是一個Hash函數.G1中HDH問題定義為：

沒有多項式時間算法至少以優勢ε在G1中解決HDH問題，我們稱HDH假設在G1中成立.

2 SCF-PEKS模型

2.1 SCF-PEKS系統模型

本節我們介紹SCF-PEKS模型，它是一個不需要接收者與服務器建立安全信道的帶關鍵詞搜索加密模型，系統中包含4個實體，即系統參數生成中心(system parameter generation center， SPGC)、數據發送者(data sender， DS)、數據接收者(data receiver， DR)、云服務器(cloud server， CS)，系統模型如圖1所示：

Fig. 1 System model of PEKS圖1 PEKS系統模型

1) 系統參數生成中心

系統參數生成中心是系統中唯一的可信第三方，運行Setup算法產生系統的公開參數，并把公開參數發送給系統中的其他實體.

2) 數據發送者

數據發送者收到公開參數之后，運行PEKS算法，對明文數據和關鍵詞加密并上傳至云服務器.

3) 數據接收者

數據接收者運行KeyGenR算法產生自己的公私鑰，運行dTrapdoor算法生成關鍵詞對應的陷門，并上傳至云服務器.

4) 云服務器

云服務器是一個誠實且好奇的實體，運行KeyGenS算法產生自己的公私鑰，運行是dTest算法為接收者提供搜索服務.

5) 云服務器

云服務器最后把搜索的結果返回給數據接收者.

2.2 SCF-PEKS算法定義

我們的算法只關注關鍵詞加密部分，具體為：

1)Setup(1k).該算法由系統參數生成中心執行，輸入安全參數1k，輸出公開參數params.

2)KeyGenR(params).該算法由數據接收者執行，輸入公開參數params，輸出他的公私鑰對(pkR,skR).

3)KeyGenS(params).該算法由云服務器執行，輸入公開參數params，輸出他的公私鑰對((pkS,skS)).

4)PEKS(params,pkR,pkS,IDsender,w).該算法由數據發送者執行，輸入公開參數params、接收者的公鑰pkR、服務器的公鑰pkS、發送者的身份IDsender、關鍵詞w，輸出關鍵詞的密文CT.

5)dTrapdoor(params,pkS,skR,IDserver,w).算法由數據接收者執行，輸入公開參數params、接收者的私鑰skR、服務器的公鑰pkS、服務器的身份IDserver、關鍵詞w，輸出關鍵詞的陷門Tw.

6)dTest(params,CT,Tw,skS,pkR,IDsender,IDserver).該算法由云服務器執行，輸入關鍵詞的密文CT和陷門Tw、接收者的公鑰pkR、服務器的私鑰skS、發送者的身份IDsender、服務器的身份IDserver，輸出是否匹配成功.

2.3 SCF-PEKS安全模型

3 SCF-PEKS方案

3.1 SCF-PEKS方案的構造

本節提出了一個不僅可以抵抗內部關鍵詞猜測攻擊而且能夠抵抗適應性選擇關鍵詞密文攻擊的方案，具體算法為：

4)PEKS(params,pkR,pkS,IDsender,w).輸入公開參數params，接收者的公鑰pkR，服務器的公鑰pkS，發送者的身份IDsender，關鍵字w，發送者計算關鍵詞的密文為：

③ 輸出關鍵詞密文CT=(s′,C1,C2,C3,C4)并發送給服務器.

6)dTest(params,CT,Tw,skS,pkR,IDsender,IDserver).該算法由云服務器執行，輸入關鍵詞的密文CT和陷門Tw，接收者的公鑰pkR，服務器的私鑰skS=xS，發送者的身份IDsender，服務器的身份IDserver.服務器首先計算h′=H2(C1,C2,C3)，判斷e(C1,(uh′vs′d))=e(pkR,C4)是否相等.若不相等則匹配失敗，終止該算法.

3.2 計算正確性與一致性分析

1) 正確性.正確的關鍵詞密文CT必須與正確關鍵詞陷門Tw匹配，服務器才能測試成功.在dTest算法中，有：

因此:

dTest(params,CT,Tw,skS,pkR,
IDsender,IDserver)=“yes”.

H1[(e(C1,T′xS)C2)]≠C3.

4 SCF-PEKS安全性分析

定理1.假設QDBDH和DBDH問題是困難問題，我們的方案在標準模型下是可證明安全的.

引理1.假設QDBDH問題是困難問題，我們的方案在標準模型下能夠抵抗選擇關鍵詞和密文攻擊(chosen keyword and ciphertext attack， CKCA).

C*1=gx*R=(ga)x*R(1a)=(Ax*R)r*=p，
C2=QxS(wδ×α0×IDsender+β)=

e(pkS,B)(wδ×α0×IDsender+β)a=
e(pkS,Bwδ×α0×IDsenderBβ)=

C*3=H1(QxS(wδ×α0))=H1(e(pkS,g(wδ×α0))ba)=
H1(e(pkS,B(wδ×α0))r*)，
C*4=g(α1h′*+α2s′*+α3)=(Aα1h′*+α2s′*+α3)r*=
(gxuh′*+xvs′*×Aα1h′*×Aα2s′*×Aα3)r*=
((gxu×Aα1)h′*(gxv×Aα2)s′*Aα3)r*=(uh′*vs′*d)r*，

因為Q在G2是獨立且均勻分布的，所以挑戰密文CT*也獨立于δ.

Pr[Abort]至少為因此

證畢.

引理2.假設DBDH問題是困難問題，我們的方案在標準模型下能夠抵抗選擇關鍵詞攻擊(chosen keyword attack， CKA).

證畢.

定理2.假設HDH問題是困難問題，我們的方案在標準模型下能夠抵抗離線關鍵詞猜測攻擊(off-line keyword guessing attack， KGA).

T*1=B=gr′*,

證畢.

5 SCF-PEKS性能對比

Table 2 Efficiency Comparisons of Different Schemes表2不同方案的效率對比

Fig. 2 Computation cost of PEKS圖2 加密關鍵字的計算代價

Fig. 3 Computation cost of trapdoor圖3 陷門產生的計算代價

Fig. 4 Computation cost of test圖4 匹配的計算代價

Table 3 Performance Comparison of Security Model Between Ours Scheme and Other Two Schemes表3 本文方案和其他2種方案安全模型的性能對比

6 總結與展望

本文構造了一個高效率的帶關鍵詞搜索公鑰加密方案，該方案能夠抵制內部、外部離線關鍵詞猜測攻擊，而且在不使用安全信道的前提下可抵制適應性選擇密文攻擊.但本文的不足是，在安全性證明中敵手的私鑰由模擬器來產生.下一步的工作是構造一個更符合實際應用的帶關鍵詞搜索的公鑰加密方案.