一種基于云存儲的多服務器多關鍵詞可搜索加密方案

黃海平 杜建澎 戴 華 王汝傳

?

一種基于云存儲的多服務器多關鍵詞可搜索加密方案

黃海平*①②杜建澎①②戴 華①王汝傳①②

①(南京郵電大學計算機學院 南京 210003)②(江蘇省無線傳感網高技術研究重點實驗室 南京 210003)

在可搜索加密的云服務中，數據擁有者往往更希望將數據文件以密文的形式分別存儲到多個云服務器，從而提高授權用戶對云端數據的檢索效率以及對大型數據的處理能力。基于此，該文提出一種基于云存儲的多服務器多關鍵詞多用戶可搜索加密方案，該方案被證明是IND-CKA(adaptive Chosen Keyword Attack)安全的，且同時具備關鍵詞陷門的安全性。相對于單服務器可搜索加密，該方案在保證數據機密性的前提下能夠對其進行高效檢索，并能夠在關鍵字索引中不完全包含所檢索的多個關鍵詞或者不存在某個文件包含所有被檢索的多個關鍵詞的情況下，更精確地進行檢索。

可搜索加密；云存儲；多服務器；多關鍵詞

1 引言

隨著云計算技術的發展，云服務商為人們提供了更高效和更快捷的文件存儲和處理服務，因此，越來越多的用戶將他們的數據存儲在云端。然而，用戶在享受便捷的云存儲服務的同時，也在擔心存儲在云端的私密數據得不到安全保障。常見的解決方法是使用可搜索加密技術，Song等人[1]最早提出的不可信賴服務器問題，該問題基于密文掃描思想和對稱密鑰機制提出了第1個SSE(Symmetric Searchable Encryption)方案，命名為SWP方案。

Boneh等人[2]最早提出PEKS(Public Key Encryption with Keyword Search)的概念，并基于BF-IBE加密方案(Boneh和Franklin設計出的IBE方案)構造了第1個基于公鑰的可搜索加密方案BDOP-PEKS[3]。近年來，提出了各種類型的SSE[4,5]方案和PEKS[6,7]方案。其中，文獻[4]基于索引思想提出了Z-IDX方案，每個文件使用布隆過濾器作為索引結構，每個文件所包含的關鍵詞被映射為碼字并存儲在該文件的索引中，通過運算布隆過濾器，就能判定某關鍵字是否存在于密文文件中；文獻[6]定義了一種安全模型，在具有惡意服務器和惡意接收者的內部攻擊環境下，提出了dPEKS方案(PEKS scheme with designated server)，在隨機語言機模型下被證明是安全的，并且能夠抵御關鍵字猜測攻擊。

與單用戶模型相比，在實際的云存儲環境中，多用戶模型下的可搜索加密(Multi-User Searchable Encryption, MUSE)是更具實用性的應用。多個授權用戶可共享外包至云服務器的文件，其經典方案包括在文獻[8,9]中。其中，文獻[8]基于一般訪問結構提出一種多用戶可搜索加密方案，該方案中任何用戶都可以向外包數據庫添加加密數據，且任何授權用戶都可以檢索并解密接收到的密文；文獻[9]基于混合結構提出一個實現關鍵字精確檢索和細粒度訪問控制加密數據的可搜索加密系統，然而該方案允許服務器獲得關鍵詞信息，有較高的安全風險。因此，在MUSE模型中，現存的主要問題是如何控制哪個用戶可以訪問哪些文件。

文獻[10]提出了一種密鑰融合的可搜索加密(Key-Aggregate Searchable Encryption, KASE)方案，該方案不同于以往方案中數據所有者需要向用戶分發大量密鑰，它只需要向授權用戶分配一個密鑰就能進行加密和檢索等操作。文獻[11]基于身份加密機制設計了一種新的公鑰可搜索加密方案，加密方通過傳給服務器一個密鑰，使得服務器僅能識別加密方期望服務器識別的關鍵詞而無法獲得更多的信息。然而上述兩個方案均只支持單關鍵詞檢索。

相較于單關鍵詞檢索，Golle等人[12]最早研究多關鍵詞檢索(Multi-Keyword Searchable Encryption, MKSE)問題，并提出GSW-1方案。近幾年的MKSE方案有文獻[13-15]。其中，文獻[13]基于代理重加密提出指定檢驗者的RE-DPECK方案，能夠抵御關鍵詞猜測攻擊，且可使用代理檢索功能。文獻[14]首次提出非結構化文本的多關鍵詞可搜索加密方案，其無需指定關鍵詞的位置，但每次搜索均針對文件中的所有關鍵詞，而不是有選擇地進行；文獻[15]基于特定樹形索引結構設計“貪心深度優先搜索”算法提供高效的多關鍵詞排序檢索，使文件的刪除和插入更加靈活。然而，現有的MKSE方案大多集中于“邏輯與”連接詞。

出于安全性和效能的考慮，大數據的擁有者更加期望能將海量數據分開存儲到多個云服務器，這對于單服務器模型提出了巨大的挑戰。因此，如何在多服務器模型中實現多授權用戶使用不同的多關鍵字進行密文檢索，同時保障安全和隱私成為本文要解決的關鍵性問題。針對此，本文方案的主要貢獻可闡述如下：

(1) 提出了一種多服務器可搜索加密方案，使得多個服務器可以并行執行密文檢索的任務。相比單服務器模型，提高了對大型數據的處理能力和用戶存儲在云端的數據的安全性。

(2) 提供更精確的檢索服務，在關鍵字索引中不完全包含所檢索的多個關鍵詞或者不存在某個文件包含所有被檢索的多個關鍵詞的情況下，仍然能夠為用戶檢索到正確的數據。

(3) 更靈活地控制用戶對密文文件的訪問權限，不同用戶對于同一文件的訪問權限不相同，并支持動態更新用戶的訪問權限，進一步解決了多用戶在云端共享數據的安全問題。

2 準備工作

2.1 系統模型

如圖1所示，本文的系統模型包括4個部分：數據擁有者、授權用戶、云端服務器和服務器。其中，數據擁有者是數據的加密方，他將數據加密后上傳至云端，并且可以授權用戶擁有檢索的權限；用戶獲得授權后可根據選定的關鍵詞從云端檢索相應的密文文件；云端服務器專用于存儲數據擁有者加密后上傳的關鍵詞索引，同時為用戶提供部分檢索服務；為各云存儲服務商提供的服務器，用來存儲數據擁有者上傳的密文文件和服務器重加密后的密文索引，同時提供部分檢索服務。

此處，我們假設云存儲服務器是誠實且好奇的，服務器會正確的執行檢索操作并且返回全部檢索結果，但無時無刻均想獲取數據隱私。假設云端服務器有個用戶擁有訪問權限，即，被加密并上傳云端的文件有個，即。文件上傳服務器之前，數據擁有者首先需要為創建其關鍵詞索引，從而方便密文檢索，假設文件的關鍵詞為，這些關鍵詞分別來自中的文件，數據擁有者將加密后的索引發送給服務器，加密后的按照某種規則等分為份分別發送給服務器；服務器對索引進行重加密后，將生成的文件關鍵詞索引結構(如圖2)再發送給。

圖1 多服務器可搜索加密系統模型

2.2 安全性定義

系統安全性定義為：在知道索引和關鍵詞陷門的前提下，云端服務器無法獲得索引中關鍵詞的其它任何信息，即服務器無法利用關鍵詞()的陷門構造出一個新的關鍵詞的陷門；另外，即使服務器可以欺騙授權用戶為其生成任何關鍵詞的陷門，此安全性也成立，稱為自適應選擇關鍵詞攻擊下的不可區分性(IND-CKA)[4]。

定義2 選擇關鍵詞攻擊IND-CKA： 挑戰者C和攻擊者A之間的安全性游戲如下：

挑戰前查詢：攻擊者A向挑戰者C自適應地選擇多項式個關鍵詞的密文索引。

挑戰后查詢：挑戰者A向攻擊者C適應性地選擇查詢關鍵詞的密文索引，但不能查詢關鍵詞,的密文索引，查詢次數為的多項式次，其中為安全參數。

本方案的安全性證明是基于確定性Diffe- Hellman問題(DDHP)，定義如下：

定義4 確定性Diffe-Hellman問題(DDHP)假設：是由生成的階為的循環群，給定和，其中, DDHP問題就是判斷是否等于。

定義5 自適應DDH假設：對于任意概率多項式時間的攻擊者A，存在一個可忽略函數滿足,是安全參數，則說明群中的DDHP是困難的。

3 多服務器模型下多關鍵詞可搜索加密方案

3.1 數據結構

本文中多用戶可搜索加密方案所用到的數據結構如下：

表1 用戶表

(2)文件訪問權限表：數據擁有者通過表1中的用戶屬性和表2所示的文件訪問權限表中的文件屬性來控制用戶對文件的訪問權限，其中是事先設定好的某個值。如果用戶要檢索文件，我們首先找到文件訪問權限表中的項和用戶表中的項，然后對比擁有的屬性和訪問需要的屬性，計算兩者交集()的屬性個數，如果大于某個設定的值，即，說明有權訪問；否則無權訪問。

表2 文件訪問權限表

圖2 文件關鍵詞索引結構

3.2 算法描述

多服務器模型下多用戶多關鍵詞可搜索加密方案包括以下8個步驟：

4 安全和效率分析

4.1 方案的安全性分析

定理1 上述方案滿足完備性。

定理2 如果DDH假設成立，那么不存在一個攻擊者可以選擇關鍵詞攻擊破壞該系統，因此上述方案是IND-CKA安全的。

挑戰后查詢：挑戰者A向攻擊者C適應性地選擇查詢關鍵詞的密文索引，但不能查詢關鍵詞,的密文索引，查詢次數為的多項式次。

另外，文件采用對稱分組加密算法(如DES)來保障機密性。關鍵詞采用偽隨機函數和隨機參數加密，由于攻擊者不知道，其即使獲得關鍵詞密文也無法得知明文的任何信息，因此生成的陷門是安全的。最后，由于文件索引和文件本身被分開存儲在服務器和中，因此服務器在圖2中分別檢索每個關鍵詞時，并不會得到比檢索結果多的額外信息(如哪些密文包含哪些關鍵詞)。此外，在算法中可設計一種安全多方計算協議，服務器將各自求得的最大度值按照此協議加密(或混淆)后再將密文傳給服務器,通過安全多方計算協議仍然能夠比較出最大值，但無法獲知各服務器傳來的具體數值，因此在多服務器模型下，用戶存儲在云端的數據比單服務器模型的安全性要更高。

4.2 方案的效率分析

(a)加密算法中對關鍵詞的加密需要一次指數運算，其它運算量與之相比可以忽略不計。這里加密關鍵字以生成關鍵字密文索引，首先，數據擁有者計算,生成關鍵字索并發送給服務器，服務器執行重加密算法對關鍵詞索引進行重加密，計算，最終生成密文索引。客戶端在關鍵字加密過程中只負責一部分計算，其余部分由服務器端進行，因此，關鍵詞加密的計算復雜度是一次指數運算。如圖3(a)所示，由實驗結果可見，關鍵詞加密時間與關鍵詞數量呈線性關系，因此，加密關鍵詞的時間消耗隨著索引中關鍵詞數量的增加呈線性增長。

(b)加密算法中生成陷門需要一次哈希函數運算和一次偽隨機函數運算，相比之下，其余運算的時間消耗可忽略不計。這里要檢索的關鍵詞為，用戶首先計算，然后對每個關鍵詞計算，最后將陷門發送給服務器。因此，生成陷門的計算復雜度是一次哈希函數和一次偽隨機函數運算。本文分別針對“文件數量不同而關鍵詞數量相同”和“文件數量相同而關鍵詞數量不同”的兩種場景分別做了仿真實驗。在圖3(b)中，所生成陷門的關鍵詞序列包含10個關鍵詞，根據實驗結果可以看到關鍵詞陷門的計算量只與生成陷門的關鍵詞個數呈線性關系，因此，隨著文件數量的增加，生成陷門的關鍵詞個數并沒有增加，時間消耗基本保持一致；在圖3(c)中，生成陷門的時間消耗隨著陷門中關鍵詞數量的增加呈線性增長。

(c)加密算法中對于關鍵詞檢索需要一次指數運算，而其它運算與之相比可以忽略不計。服務器根據用戶發送過來的陷門，計算和，并將最終生成的關鍵字陷門發送給服務器。因此，關鍵詞檢索的計算復雜度是一次指數運算，并且所有計算工作全部是在服務器端進行。如圖3(d)所示，由于檢索需要匹配每個關鍵詞，實驗結果得出，文件的檢索時間與所檢索的關鍵詞數量呈線性關系，因此，關鍵詞檢索的時間消耗隨著索引中關鍵詞數量的增加呈線性增長。

圖3 算法的時間消耗性能分析

(2)性能比較： 表3列出了本文方案與其它經典方案的性能比較。由于KASE[10]和CLPEKS[11]不支持多關鍵詞檢索，因此此處僅比較生成單關鍵詞陷門的運算量。由表3可知，本文方案生成單關鍵詞陷門的效率與KASE相近，比其余方案均要高；由于本文方案提供多關鍵詞的精確檢索，因此檢索運算量較大，但如果僅檢索單個關鍵詞，本文方案的檢索量僅是指數運算，效率高于其它方案；本文方案中，對關鍵詞加密只需要次指數計算，其余計算都由存儲服務器執行，故本文方案的關鍵詞加密效率要遠高于其它方案；此外，其它方案均不支持多服務器和多用戶模型，而本文方案可將大型數據文件分割存儲在不同的云服務器，相比單服務器模型，多個服務器可并行執行密文檢索任務，提高了對大型數據文件的處理能力。

圖4(a)分別針對單服務器模型和多服務器模型進行比較，服務器數量在圖中從上往下分別為1個、10個、50個和100個；圖4(b)在不同數量文件和不同數量服務器情況下，針對服務器對密文文件的檢索效率做了實驗分析。假設文件等分存儲于每個服務器上，每個文件有20個關鍵字，用戶用于檢索的關鍵字陷門有10個關鍵字。

如圖4(a)所示，在密文文件數量相同的情況下，參與檢索的服務器數量越多，則檢索效率越高，尤其當文件數量較大時，檢索效率有較顯著提高。圖4(b)展示了5種不同數量文件的多服務器效率比較，檢索時間首先隨著參與檢索的服務器數量的增加而遞減，當服務器數量超過某個臨界值時，所需的檢索時間反而隨其數量的增加而遞增。可見，檢索時間并非總是隨著服務器數量的增加而遞減，而是有一個臨界值，因為服務器需要將服務器傳來的檢索結果進行排序，并最終選出檢索結果最優的幾個服務器。

表3 方案的效率比較

注：是文件數目；是文件的關鍵詞數量；是用戶檢索的關鍵詞數目；是群中的乘法運算；是乘法運算；是雙線性運算；是指數運算，這里。

圖4 單服務器/多服務器檢索效率

圖5 單服務器/不同分割存儲方式下多服務器檢索效率

因此，從上述實驗可知，在確保服務器數量不超過臨界值的情況下，多服務器模型在對密文文件進行檢索時，其效率會隨著參與檢索的服務器數量的增加而有較顯著的提高，尤其是在文件數量巨大的情況下，檢索效率的提高更為顯著。

在多服務器模型中，圖5(a)至圖5(c)中分別有10個、50個和100個服務器同時進行并行檢索(均未超過服務器數量的門限)，文件可能隨機分別存儲于這些服務器(MSRD)，或者等分存儲于這些服務器(MSUD)，圖5中所示均為10次實驗的平均值。由實驗結果可知，隨著存儲于服務器上文件數量的增加，多服務器檢索比單服務器(SS)檢索更有優勢，且隨著服務器數量的增加，檢索效率也有較顯著的提升；相比于單服務器模型，多服務器模型對文件檢索的開銷明顯減少。同時，由于所有服務器并行檢索，檢索的最大時間由花費檢索時間最長的那個服務器所決定，而服務器上存儲的文件越多則所需檢索的時間越多，因此，文件等分存儲的方式往往比隨機存儲的方式擁有更高的檢索效率。

5 結束語

本文提出了一種基于云存儲的多服務器多關鍵詞可搜索加密方案，可在多個服務器相互不知道檢索結果的情況下，共同完成檢索任務，并將最終的檢索結果返回給用戶。該方案能夠更精確地進行檢索，并且被證明是IND-CKA安全的，同時也證明了關鍵詞陷門的安全性。此外，該方案可以更靈活地控制用戶對密文文件的訪問權限。

然而，本文方案仍存在一些問題有待解決：例如本文假設服務器是誠實且好奇的，但在惡意服務器模型中，如何分辨服務器返回的檢索結果是否真實，具有很大的挑戰性。此外，一個不誠實的授權用戶會導致許多安全隱患，他可能把檢索返回并解密的文件發送給沒有權限的其他用戶，甚至將密鑰信息發送給他人，從而導致數據隱私的泄露和其它的安全隱患。在未來的工作中，我們將嘗試改進本文的可搜索加密方案，從而克服這些難題。

[1] SONG X D, WAGNER D, and PERRIG A. Practical techniques for searches on encrypted data[C]. IEEE Symposium on Security and Privacy, Berkeley, USA, 2000: 44-55.

[2] BONEH D and FRANKLIN M. Identity-based encryption from the weil pairing[C]. Advances in Cryptology-CRYPTO 2001-21st Annual International Cryptology Conference, California, USA, 2001: 213-229.

[3] BONEH D, CRESCENZO G, OSTROVSKY R,. Public key encryption with keyword search[C]. Proceedings of EUROCRYPT 2004, Interlaken, Switzerland, 2004: 506-522.

[4] GOH E. Secure indexes[OL]. http://crypto.stanford.edu/ ~eujin/papers/secureindex, 2003.

[5] KAMARA S, PAPAMANTHOU C, and ROEDER T. Dynamic searchable symmetric encryption[C]. CCS 2012 19th ACM Conference on Computer and Communications Security, Raleigh, USA, 2012: 965-976.

[6] RHEE H S, PARK J H, SUSILO W,. Improved searchable public key encryption with designated tester[C]. ASIACCS’09 Proceedings of the 4th International Symposium on Information, Computer, and Communications Security, Sydney, Australia, 2009: 376-379.

[7] HU C and LIU P. A secure searchable public key encryption scheme with a designated tester against keyword guessing attacks and its extension[C]. Communications in Computer and Information Science, Jinan, China, 2011: 131-136.

[8] ZIRTOL KOBRA AMIRI, NOROOZI MAHNAZ, and ESLAMI ZIBA. Multi-user searchable encryption scheme with general access structure[C]. 2015 2nd International Conference on Knowledge-Based Engineering and Innovation (KBEI), Tehran, Iran, 2015: 399-404.

[9] LI J, LI J, CHEN X,. Privacy-Preserving data utilization in hybrid clouds[J]., 2014, 30(1): 98-106. doi: 10.1016/j.future.2013.06.011.

[10] CUI B, LIU Z, and WANG L. Key-Aggregate Searchable Encryption (KASE) for group data sharing via cloud storage[J]., 2015, 65(8): 2374-2385. doi: 10.1109/TC.2015.2389959.

[11] PENG Yanguo, CUI Jiangtao, PENG Changgen,. Certificateless public key encryption with keyword search[J]., 2014, 11(11): 100-113. doi: 10.1109 /CC.2014.7004528.

[12] GOLLE P, STADDON J, and WATERS B. Secure conjunctive keyword search over encrypted data[C]. International Conference on Applied Cryptography and Network Security, Huangshan, China, 2004: 31-45.

[13] YANG Yang, MA Maode, and LIN Bogang. Proxy re-encryption conjunctive keyword search against keyword guessing attack[C]. Computing, Communications and IT Applications Conference (ComComAp), Hong Kong, China, 2013: 125-130.

[14] KERSCHBAUM F. Secure conjunctive keyword searches for unstructured text[C]. International Conference on Network and System Security, Milan, Italia, 2011: 285-289.

[15] XIA Zhihua, WANG Xinhui, SUN Xingming,. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data[J]., 2016, 27(2): 340-352. doi: 10.1109/ TPDS.2015.2401003.

Multi-sever Multi-keyword Searchable Encryption Scheme Based on Cloud Storage

HUANG Haiping①②DU Jianpeng①②DAI Hua①WANG Ruchuan①②

①(,,210003,)②(,210003,)

In the searchable encryption services provided by cloud severs, data owners expect that their data files can be partitioned and stored to multiple cloud severs with the form of ciphertext, so as to improve the searching efficiency of authorized users and the processing ability of big data. For this issue, a multi-sever multi-keyword searchable encryption scheme is proposed based on cloud storage, and the proposed scheme is proved to be IND-CKA (adaptive Chosen Keyword Attack) secure coexisting with the secure trapdoor. Compared with the single sever searchable encryption, the proposed scheme can not only guarantee the data security, but also provide more accurate retrieval service when the keyword index or any one file does not contain all of the searching keywords.

Searchable encryption; Cloud storage; Multi-sever; Multi-keyword

TP393

A

1009-5896(2017)02-0389-08

10.11999/JEIT160338

2016-04-07；改回日期：2016-09-01；

2016-11-14

黃海平 hhp@njupt.edu.cn

國家自然科學基金(61373017, 61373138, 61300240, 61672297)，國家博士后基金(2015M570468, 2016T90485)，江蘇省自然科學基金(BK20151511)，江蘇省六大人才高峰項目(DZXX- 017)，江蘇省無線傳感網高技術研究重點實驗室基金(WSNLBZY 201516)，江蘇省研究生培養創新工程項目(KYLX15_0853)

The National Natural Science Foundation of China (61373017, 61373138, 61300240, 61672297), The National Postdoctoral Foundation of China (2015M570468, 2016T90485), The Natural Science Foundation of Jiangsu Province (BK20151511), The Six Major Talent Peak Foundation in Jiangsu Province (DZXX-017), The High Technology Research Key Laboratory of Wireless Sensor Network Foundation of Jiangsu Province (WSNLBZY 201516), The Graduate Education Innovation Project of Jiangsu Province (KYLX15_0853)

黃海平： 男，1981年生，教授，研究方向為信息網絡安全和數據隱私保護技術.

杜建澎： 男，1989年生，碩士生，研究方向為信息網絡安全和數據隱私保護技術.

戴 華： 男，1982年生，副教授，研究方向為信息網絡安全和數據隱私保護技術.

王汝傳： 男，1943年生，教授，研究方向為計算機軟件、信息安全和無線傳感器網絡技術等.