云存儲中基于屬性的關鍵詞搜索加密方案研究

朱智強，蘇航，孫磊，李作輝

?

云存儲中基于屬性的關鍵詞搜索加密方案研究

朱智強，蘇航，孫磊，李作輝

（信息工程大學三院，河南鄭州 450000）

為保證云端敏感數據安全性的同時提高數據共享效率，提出了一種安全、靈活、高效的基于屬性的關鍵詞搜索加密方案。方案中設計了一種需要數據擁有者私鑰參與的索引生成機制抵抗關鍵詞猜測攻擊，基于線性秘密共享訪問結構描述用戶的搜索權限，支持一對多應用場景，借鑒連接子集關鍵詞搜索技術和在線/離線思想提高搜索的靈活性和效率。理論分析與實驗評估結果表明，該方案具有較高的效率。

可搜索加密；關鍵詞猜測攻擊；連接關鍵詞；在線/離線

1 引言

隨著云存儲技術迅猛發展，越來越多的企業和個人選擇在云端存儲和共享數據，但由于云端數據使用權和管理權的分離，數據擁有者通常會加密敏感數據以確保其在云端的安全性，這造成了數據可供檢索的語義和統計特性丟失，導致云服務提供商無法為用戶提供數據搜索服務，極大地降低了云端數據的共享效率。公鑰可搜索加密技術（PKES, public key encryption with keyword search）的出現為解決上述問題提供了解決方案，該技術確保只有合法用戶具備執行關鍵詞搜索的能力，搜索過程不會影響數據安全性。

近年來，公鑰可搜索加密技術得到廣泛研究和快速發展[1]，為適用于云存儲環境，公鑰可搜索加密方案需要滿足下述特性。一是抵抗內部、外部關鍵詞猜測攻擊。由于可搜索加密方案具有一致性，并且關鍵詞空間具有低熵性，關鍵詞猜測攻擊（KGA, keyword guessing attack）（攻擊者通過收集陷門信息，利用系統中的公開信息生成多個包含不同關鍵詞的索引，進而推導出陷門中包含的關鍵詞信息）往往十分有效。二是支持多用戶共享檢索。云端數據共享的參與者往往是多個數據擁有者與數據使用者，為適用于云存儲，要求可搜索加密方案支持一對多的應用場景。三是支持連接關鍵詞搜索。數據使用者通常需要查找多個關鍵詞以實現文件的精確定位，為支持靈活的搜索操作，要求可搜索加密方案支持連接關鍵詞搜索。四是用戶計算開銷較低。當前大量移動終端參與云端數據共享，為支持運算能力、電池容量受限的移動終端，要求方案減少搜索過程中用戶的計算復雜度。

1.1 相關工作

為有效地支持云存儲中的一對多應用場景，Zheng等[2]和Sun等[3]結合屬性基加密（ABE, attribute-based encryption）技術與可搜索加密（SE, searchable encryption）技術，提出基于屬性的關鍵詞搜索方案（ABKS, attribute-based keyword search），既支持密文數據的細粒度訪問控制，又能提供對密文數據的快速檢索，有效提高了云端密文數據的共享效率。

KGA最早由Byun等[4]提出，根據攻擊者所處位置的不同，可分為內部KGA和外部KGA[5]，前者主要由PEKS系統中的惡意搜索服務器發起；后者由除搜索服務器外的其他敵手發起。Wang等[6]提出了一種可抵抗內部和外部KGA的搜索方法，即指定多個搜索服務器共同參與搜索過程，但仍無法抵抗多搜索服務器的共謀攻擊。Li等[7]提出了一種基于混沌映射的抵抗內外KGA的搜索方法，但要求數據擁有者實時在線，以便與數據使用者共享會話密鑰。林鵬等[8]通過指定搜索服務器，提出了一種可抵抗外部KGA的ABKS方案，但方案假設搜索服務器是完全可信的，無法抵抗內部KGA。Chen等[9]提出一種基于雙搜索服務器的PEKS方案，通過將測試任務交給相互獨立的前端和后端服務器處理，實現同時抵抗內部和外部KGA，但該方案的構造基于同態加密，計算復雜度較高。Qiu等[10]基于隱藏訪問結構的CP-ABE方案，提出了一個抵抗內部KGA和外部KGA的ABKS方案，但需采用受限的“多值與門”作為訪問結構，并且存在與文獻[7]相似的問題，即要求數據擁有者實時在線。

2004年，Golle等[11]首次提出支持連接關鍵詞搜索的可搜索加密方案，但由于指定了關鍵詞域且關鍵詞位置固定，搜索的靈活性較差。Zhang等[12]基于多項式函數理論，提出一種支持連接子集關鍵詞公鑰可搜索加密（PECSK, public key encryption with conjunctive-subset keywords search）方案，支持動態關鍵詞域。基于PECSK方案的思想，Yang等[13]提出一種適用于E-Health云系統的支持多關鍵詞連接搜索的PEKS方案。宋衍等[14]提出了一種支持關鍵詞任意連接的ABKS方案，可靈活地支持一對多應用場景中的多關鍵詞搜索。

隨著移動設備的普及，Dong等[15]參考Hohenberger等[16]提出的在線/離線屬性基加密方案，將索引算法和陷門算法分為2個階段，并在離線階段完成大部分的運算工作，有效降低在線階段的計算負擔。陳冬冬等[17]通過引入在線/離線技術和外包解密技術，設計了一種高效的可搜索加密方案，但對方案的安全性沒有進行形式化證明。

針對公鑰可搜索加密技術中支持一對多應用場景、抵抗內部外部KGA、支持連接關鍵詞搜索和在線/離線問題，學術界展開了大量研究，但現有的方案不能同時解決上述問題。

1.2 本文主要工作

本文首次提出一種適應于云端數據共享的安全、高效、靈活的ABKS方案——O2ABCSKS (online/offline attribute based conjunctive-subset keywords search)，方案具有以下4點優勢。

1) 抵抗內部KGA：設計了一種需要數據擁有者私鑰參與的索引生成機制，排除了惡意搜索服務器構造偽造索引的可能。

2) 支持一對多應用場景：采用具有強表達力的線性秘密共享（LSSS, linear secret sharing scheme）訪問結構描述用戶的搜索權限，支持一對多的應用場景。

3) 搜索靈活性較高：支持連接關鍵詞搜索，提供靈活的多關鍵詞搜索功能。

4) 用戶計算開銷低：較其他訪問結構，采用LSSS訪問結構系統開銷有所增加，為降低用戶端的開銷，引入離線在線思想，將索引和陷門算法分為在線和離線2個階段執行。離線階段中索引和陷門算法使用的關鍵詞、屬性列表或訪問結構等信息未知，該階段承擔算法中大部分的計算量；在線階段已知關鍵詞、屬性列表或訪問結構等信息后，僅需少量計算即可完成索引和陷門算法。離線階段可在設備空閑時執行，大大降低了在線階段的運算量。

2 預備知識

2.1 雙線性映射及困難性假設

定義1 雙線性映射。

定義2-DPBDHE（-decisional parallel bilinear Diffie-Hellman exponent assumption）假設[18]。

定義3 DDDH（divisible decisional Diffie- Hellman assumption）假設[19]。

2.2 線性秘密共享方案

定義4 線性秘密共享方案[18]。

3 算法定義及安全模型

3.1 系統模型

系統中有4類實體：云服務提供商（CSP, cloud service provider）、授權機構（AA, authorized authority）、數據擁有者（DO, data owner）以及數據使用者（DU, data user）。

1) 云服務提供商

CSP為系統中的用戶提供數據存儲、關鍵詞搜索等服務。在本文方案中，CSP是“誠實但具有好奇心的”，CSP會如實執行既定的操作，但它也可能攻擊云端存儲的數據以獲取其中的信息。

2) 授權機構

AA負責系統建立、用戶密鑰等生成工作，是系統中唯一的可信第三方。

3) 數據擁有者

DO可加密數據，生成關鍵詞索引，并將其數據密文及關鍵詞索引上傳至云端。

圖1 工作流程

4) 數據使用者

DU可向CSP請求關鍵詞搜索服務，并從CSP處獲取搜索結果。

在云存儲環境中，使用本方案進行數據共享的工作流程如圖1所示。

1) AA建立系統。

2) DO在AA處注冊，AA生成用戶密鑰并發送給DO。

3) DO加密待上傳云端的數據，在數據中挑選關鍵詞并生成關鍵詞索引。

4) DO將密文及索引上傳至云端。CSP存儲密文及相應的關鍵詞索引。

5) DU在AA處注冊。AA生成用戶密鑰并發送給DU。

6) DU選取待搜索數據集合及待搜索關鍵詞，生成搜索陷門。

7) DU將搜索陷門上傳至搜索服務器，搜索服務器執行搜索操作并將結果發送給DU。

8) DU解密密文數據得到明文。

3.2 算法定義

定義5 本文提出的方案包括7個算法，算法定義如下。

3.3 安全模型

定義6 索引保密性。

考慮數據擁有者存儲在云端數據的安全性，保證索引不會泄露其為數據選取的關鍵詞信息，方案需要達到選擇關鍵詞明文攻擊的不可區分性安全(IND-CKA)。攻擊者和挑戰者之間在選擇模型下的攻擊游戲定義如下。

系統建立：挑戰者C運行系統建立算法，生成系統公開參數以及主密鑰，將公開參數其發送給敵手A，并秘密地保存主密鑰。

階段1 A對下述預言機進行多項式次數的詢問，C按照下述方法回答A的查詢。

定義7 陷門保密性。

考慮數據使用者搜索過程的安全性，保證其生成的陷門不會泄露當前搜索關鍵詞信息，方案需要達到選擇關鍵詞明文攻擊的不可區分性安全。攻擊者和挑戰者之間在選擇模型下的攻擊游戲定義如下。

系統建立：挑戰者C運行系統建立算法，生成系統公開參數以及主密鑰，將公開參數發送給敵手A，秘密地保存主密鑰。

4 O2ABCSKS方案

ABKS方案的主要應用場景如下[18]：為提高數據共享效率，數據擁有者為其數據挑選關鍵詞，并生成關鍵詞索引，使預期的接收者可以安全高效地實施密文搜索。因此，在實際搜索過程中，數據使用者獲取數據擁有者的公鑰信息是可行的。基于上述分析，本文構造了一種可抵抗內部KGA和外部KGA的索引生成機制，該機制的實施方法如下。授權機構在用戶注冊時為用戶產生包括一個公私鑰對在內的搜索密鑰；數據擁有者生成索引時使用自己私鑰簽名生成的關鍵詞索引；而數據使用者在搜索過程中指定待搜索數據集的數據擁有者，并使用該數據擁有者的公鑰加密搜索陷門。

基于上述索引生成機制，構造用來對O2ABCSKS方案發起KGA的偽造索引，需要數據擁有者的私鑰。對于外部關鍵詞猜測攻擊，發起KGA的敵手為惡意用戶，它可截獲陷門信息，但是它無法從中猜測出指定的待搜索數據集的數據擁有者，因此無法構造可有效發起攻擊的偽造索引。對于內部關鍵詞猜測攻擊，發起KGA的敵手為惡意搜索服務器，它可截取陷門信息，并通過執行搜索算法可猜測出陷門中指定的數據擁有者信息以及執行算法過程中產生的中間參數，但是除非搜索服務器可攻破離散對數假設，否則無法獲取數據擁有者的私鑰，因此也無法構造可有效進行KGA的偽造索引。

4.1 具體構造

方案中使用的部分符號描述如表1所示。

表1 符號定義

此階段由于需加密的數據集是未知的，數據擁有者無法精確地選定關鍵詞以及訪問結構，數據屬性按照下述步驟執行該算法。

4.2 算法一致性

若數據使用者的屬性集滿足數據擁有者制定的訪問結構，則

若數據使用者選取的關鍵詞都在數據擁有者設置的關鍵詞集合內，則

故本方案滿足計算一致性。

5 方案分析

5.1 安全性證明

定理1 若-DPBDHE假設成立，則方案滿足索引保密性。

定理2 若DDDH假設成立，則方案滿足陷門保密性。

初始化：挑戰者C將DDDH數組發送給仿真器∑。

因此，A在安全性游戲中的優勢是可忽略的。

5.2 理論分析

Sun等[3]、林鵬等[8]、宋衍等[14]以及Qiu等[10]提出的方案是近年來較為著名的ABKS方案，本節從功能和效率方面將本文提出的方案與上述方案進行對比。

功能對比如表2所示，本文提出的方案采用的是LSSS訪問結構，具有較好的表達能力，而文獻[3]與文獻[10]中的方案采用AND訪問結構，表達能力較弱；本文方案與文獻[14]的方案支持連接關鍵詞搜索，具有較高的靈活性；本文中的方案與文獻[10]方案可抵抗外部與內部KGA，具有較高的安全性。

表2 功能對比結果

表3 效率對比結果

5.3 實驗評估

本文通過實驗對本文提出的算法與文獻[14]中的算法進行進一步的性能評估。實驗的硬件環境為Intel Core i5，2.4 GHz處理器，操作系統為環境為64 bit Ubuntu操作系統。實驗基于Charm架構，選用MNT224橢圓曲線。

圖2 屬性數量對運行時間的影響

圖3 關鍵詞數量對運行時間的影響

6 結束語

本文針對關鍵詞猜測攻擊、連接關鍵詞搜索以及效率問題，提出一種適合云存儲環境的基于屬性的關鍵詞搜索方案，該方案可抵抗內部和外部關鍵詞猜測攻擊，采用具有強表達力的LSSS訪問結構，支持連接關鍵詞搜索，支持在線/離線。理論分析和實驗評估表明，本文提出的方案是實用、安全且高效的。下一步將在此方案的基礎上，對搜索結果的可驗證性以及方案的效率進行研究，使方案更加實用。

[1] 李經緯, 賈春福, 劉哲理, 等. 可搜索加密技術研究綜述[J]. 軟件學報, 2015, 26(1):109-128.

LI J W, JIA C F, LIU Z L, et al. Survey on the searchable encryption [J]. Journal of Software, 2015, 26(1): 109-128.

[2] ZHENG Q, XU S, ATENIESE G. VABKS: verifiable attribute- based keyword search over outsourced encrypted data[C]//IEEE Conference on Computer Communications. 2014: 522-530.

[3] SUN W, YU S, LOU W, et al. Protecting your right: attribute-based keyword search with fine-grained owner-enforced search authorization in the cloud[C]//IEEE Conference on Computer Communications. 2014: 226-234.

[4] JIN W B, RHEE H S, PARK H, et al. Off-line keyword guessing attacks on recent keyword search schemes over encrypted data[C]//The Third VLDB Workshop Secure Data Management. 2006: 75-83.

[5] FANG L, SUSILO W, GE C, et al. Public key encryption with keyword search secure against keyword guessing attacks without random oracle[J]. Information Sciences an International Journal, 2013, 238(7): 221-241.

[6] WANG C H, TU T Y. Keyword search encryption scheme resistant against keyword-guessing attack by the untrusted server[J]. Journal of Shanghai Jiaotong University (Science), 2014, 19(4): 440-442.

[7] LI C T, LEE C W, SHEN J J. An extended chaotic maps-based keyword search scheme over encrypted data resist outside and inside keyword guessing attacks in cloud storage services[J]. Nonlinear Dynamics, 2015, 80(3): 1601-1611.

[8] 林鵬, 江頡, 陳鐵明. 云環境下關鍵詞搜索加密算法研究[J]. 通信學報, 2015, 36(s1):259-265.

LIN P, JIANG J, CHEN T M. Application of keyword searchable encryption in cloud[J]. Journal of Communications, 2015, 36 (s1): 259-265.

[9] CHEN R, MU Y, YANG G, et al. Dual-server public-key encryption with keyword search for secure cloud storage[J]. IEEE Transactions on Information Forensics & Security, 2016, 11(4):789-798.

[10] QIU S, LIU J, SHI Y, et al. Hidden policy ciphertext-policy attribute-based encryption with keyword search against keyword guessing attack[J]. Science China Information Sciences, 2017, 60(5).

[11] GOLLE P, STADDON J, WATERS B. Secure conjunctive keyword search over encrypted data[C]//The Second International Conference on Applied Cryptography and Network Security(ACNS 2004). 2004: 31-45.

[12] ZHANG B, ZHANG F. An efficient public key encryption with conjunctive subset keywords search[J]. Journal of Network & Computer Applications, 2011, 34(1): 262-267.

[13] YANG Y, MA M. Conjunctive keyword search with designated tester and timing enabled proxy re-encryption function for e-health clouds[J]. IEEE Transactions on Information Forensics & Security, 2016, 11(4):746-759.

[14] 宋衍, 韓臻, 陳棟, 等. 支持關鍵詞任意連接搜索的屬性加密方案[J]. 通信學報, 2016, 37(8):77-85.

SONG Y, HAN Z, CHEN D, et al. Attribute-based encryption supporting arbitrary conjunctive key word search[J]. Journal of Communications, 2016, 37(8):77-85.

[15] DONG Q, GUAN Z, CHEN Z. Attribute-based keyword search efficiency enhancement via an online/offline approach[C]//The International Conference on Parallel and Distributed Systems. 2015: 298-305.

[16] HOHENBERGER S, WATERS B. Online/offline attribute-based encryption[C]//Public Key Cryptography (PKC 2014). 2014: 293-310.

[17] 陳冬冬, 曹珍富, 董曉蕾. 在線/離線密文策略屬性基可搜索加密[J]. 計算機研究與發展, 2016, 53(10):2365-2375.

CHEN D D, CAO Z F, DONG X L. Online/offline ciphertext policy attribute-base searchable encryption[J]. Journal of Computer Research and Development, 2016, 53 (10): 2365-2375.

[18] WATERS B. Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization[C]//Public Key Cryptography(PKC 2011). 2011: 53-70.

[19] WU Y, LU X, SU J, et al. An efficient searchable encryption against keyword guessing attacks for sharable electronic medical records in cloud-based system[J]. Journal of Medical Systems, 2016, 40(12): 258.

Research on attribute-based encryption with keyword search for cloud storage

ZHU Zhi-qiang, SU Hang, SUN Lei, LI Zuo-hui

(The Third Party, Information Engineering University, Zhengzhou 450000, China)

To safeguard the sensitive data stored on the cloud and promote the efficiency of data sharing simultaneously, a secure flexible and efficient attribute-based encryption scheme with keyword search is proposed, which designs an index generation mechanism that requires the private key of data owner to resist the keyword guessing attack, supports one-to-many application scenarios based on the linear secret shared access structure, introduces the conjunctive subset keyword search technique and online/offline technique to improve search flexibility and efficiency. Theoretical analysis and experimental evaluation show that the proposed scheme enjoys high efficiency.

searchable encryption, keyword guessing attack, conjunctive keyword, online/offline

TP311

A

10.11959/j.issn.2096-109x.2017.00214

朱智強（1961-），河南駐馬店人，博士，信息工程大學教授，主要研究方向為信息安全。

蘇航（1994-），女，湖北隨州人，信息工程大學碩士生，主要研究方向為信息安全。

孫磊（1973-），河南洛陽人，博士，信息工程大學研究員，主要研究方向為信息安全。

李作輝（1981-），湖南衡陽人，博士，信息工程大學副研究員，主要研究方向為公鑰密碼。

2017-08-25；

2017-10-19。

蘇航，suhang_039@163.com

國家重點研發計劃基金資助項目（No.2016YFB0501900）

The National Key R&D Program of China (No.2016YFB0501900)