基于多線性映射的可搜索加密方案

馮金明 田有亮 劉田天

摘 要：可搜索加密技術(shù)為云環(huán)境下數(shù)據(jù)的使用提供了技術(shù)支持，針對可搜索的關(guān)鍵字?jǐn)?shù)量及用戶模式提出了一種基于多線性映射的可搜索加密方案。首先，提出了基于多線性映射的可搜索加密方案，多線性映射提高了方案的安全性，加強(qiáng)了數(shù)據(jù)擁有者的權(quán)限，使得數(shù)據(jù)擁有者可以靈活地增加和刪除用戶。其次，利用消息認(rèn)證碼技術(shù)驗(yàn)證數(shù)據(jù)的完整性，提高了存儲數(shù)據(jù)的安全性。最后，在標(biāo)準(zhǔn)模型下證明方案是滿足選擇明文攻擊下不可區(qū)分安全，且方案安全性歸約于多線性計(jì)算Diffie-Hellman（MCDH）問題。此外，與相關(guān)方案進(jìn)行了性能分析，分析結(jié)果表明該方案的安全性高。

關(guān)鍵詞：云計(jì)算；可搜索加密；多線性映射；可證明安全

中圖分類號：TP309.7

文獻(xiàn)標(biāo)識碼： A

伴隨著網(wǎng)絡(luò)技術(shù)的迅速發(fā)展，云計(jì)算在近些年也快速興起，越來越多的企業(yè)、政府公共領(lǐng)域和個人開始使用云相關(guān)的技術(shù)[1]。如何解決數(shù)據(jù)加密和數(shù)據(jù)搜索之間的沖突已經(jīng)成為亟需解決的重要問題[2]。為了有效的搜索數(shù)據(jù)，需要一個可以直接作用于加密數(shù)據(jù)的搜索機(jī)制[3]，可搜索加密因此而誕生。其目標(biāo)就是在不影響數(shù)據(jù)檢索功能的條件下，保護(hù)用戶外包數(shù)據(jù)的安全與查詢隱私[4]。

可搜索加密的概念是由SONG等[5]在2000年首次提出，其指出用戶將自己的加密數(shù)據(jù)存儲到不可信的云服務(wù)器上，在給定關(guān)鍵詞陷門信息的情況下，服務(wù)器可以為用戶搜索包含特定關(guān)鍵詞的加密文件，而不能獲得關(guān)于明文的信息。2003年，GOH[6]提出了一種新方案，該方案利用Bloom過濾器來建立文件索引，以達(dá)到降低開銷的目的。2004年，DAN等[7]提出了基于關(guān)鍵詞的可搜索加密算法，開啟了密文搜索的新紀(jì)元。2005年，CHANG等[8]利用隨機(jī)比特建立關(guān)鍵字的索引，并在搜索時通過恢復(fù)索引的部分信息來匹配關(guān)鍵字。2006年，CURTMOLA等[9]提出了在整個文件集合上建立加密關(guān)鍵字的Hash索引，搜索令牌由關(guān)鍵字陷門和文件擁有者的身份信息組成，從而通過關(guān)鍵字陷門與關(guān)鍵字密文的匹配來產(chǎn)生搜索結(jié)果。此后，可搜索加密機(jī)制的研究迅速發(fā)展。2010年，LI等[10]提出了模糊關(guān)鍵字搜索方案，使用編輯距離來定義關(guān)鍵字的相似度，并且提出了基于克和基于通配符的兩種模糊集的構(gòu)造方法。2011年，CHAI等[11]提出了一個可驗(yàn)證的對稱可搜索加密方案，他們在其方案中使用了一種更強(qiáng)的安全模型——半可信但好奇的服務(wù)器，在這種模型下，服務(wù)器為了節(jié)省自己的帶寬及計(jì)算量不一定按照協(xié)議執(zhí)行操作，從而可能只是執(zhí)行部分搜索操作或者返回部分搜索結(jié)果。2012年，WANG等[12]進(jìn)一步研究了模糊關(guān)鍵字的搜索方案，并且給出了關(guān)于方案的安全性證明；SUN等[13]提出了可驗(yàn)證的多關(guān)鍵詞排序搜索方案。此外，RHEE等[14]于2013年提出多線性映射的概念，并利用多線性映射構(gòu)造了無需隨機(jī)預(yù)言機(jī)下的聚合和可驗(yàn)證的加密簽名方案。隨后，GARG等[15]將橢圓曲線對拓展到多線性映射上，首次在理想格上構(gòu)造了一個實(shí)用的多線性映射。2014年，張敏情等[16]基于多線性映射與強(qiáng)不可偽造簽名提出一種可公開驗(yàn)證加密方案，該方案是選擇密文安全的，與基于雙線性對構(gòu)造的方案相比具有明顯優(yōu)勢。2015年，于志敏等[17]利用多線性映射構(gòu)造了一種環(huán)簽密廣播方案，各個環(huán)成員代表環(huán)群體匿名簽密并廣播給接收者，從而實(shí)現(xiàn)兩個用戶群之間環(huán)簽密通信的功能。2017年，彭巧等[18]利用多線性映射構(gòu)造了一種信息率可以達(dá)到m/（m+1）的秘密共享方案。從而發(fā)現(xiàn)多線性映射是構(gòu)造加密和簽名方案的一種非常實(shí)用的工具。因此，將多線性映射應(yīng)用到可搜索加密方案的構(gòu)造具有很好的前景。

本文針對大數(shù)據(jù)環(huán)境下數(shù)據(jù)加密搜索機(jī)制提出了一種解決方案。

（1）提出了一種基于多線性映射的可搜索加密方案。相比于傳統(tǒng)的可搜索加密方案，該方案在大數(shù)據(jù)環(huán)境下具有更大的應(yīng)用場景。

（2）動態(tài)權(quán)限分配。由數(shù)據(jù)擁有者自己定義自身的文檔權(quán)限，可以進(jìn)行實(shí)時更新，只需將對應(yīng)的權(quán)限發(fā)送給服務(wù)器，而不需要重新上傳索引表。進(jìn)一步解決了多用戶將數(shù)據(jù)共享在云端的安全問題。

（3）本方案支持多個數(shù)據(jù)共享者及數(shù)據(jù)擁有者，避免了傳統(tǒng)的單用戶對資源共享的限制，使方案更具有實(shí)用性。

（4）支持多關(guān)鍵詞查詢服務(wù)，可以更全面的返回用戶需要的文件。

1 基礎(chǔ)知識

1.1 消息認(rèn)證碼

定義1 消息認(rèn)證碼是指消息被一密鑰控制的公開函數(shù)所作用后產(chǎn)生的，用作認(rèn)證符的，固定長度的數(shù)值，也被稱為密碼校驗(yàn)和。

假設(shè)通信雙方A與B擁有一個共享密鑰K，用戶A想給用戶B發(fā)送的消息為M，則用戶A先計(jì)算MAC=CK（M），其中CK（·）是密鑰控制的公開函數(shù)，然后用戶A給用戶B發(fā)送M‖MAC，B收到A發(fā)送的消息后也做與A相同的操作得到一新的MAC，然后比較兩個MAC，就可以知道信息有沒有被篡改。

MAC函數(shù)與加密算法類似，差別主要在于MAC函數(shù)具有不可逆性，因此不易被攻破。

1.2 多線性映射

BONEH等在2003年提出了多線性映射[19]的概念，多線性映射是對雙線性映射的推廣。相對于雙線性映射，多線性映射將更多的循環(huán)群關(guān)聯(lián)到目標(biāo)循環(huán)群。

2 基于多線性映射的可搜索加密方案

2.1 方案描述

在基于多線性映射的可搜索加密方案中，包含以下三個實(shí)體：云服務(wù)器（CSP）、數(shù)據(jù)擁有者（Data Owner）及數(shù)據(jù)使用者（Data Users）。本文提出的方案模型如圖1所示。

其中，云服務(wù)器是誠實(shí)但好奇的。一方面，服務(wù)器會誠實(shí)地執(zhí)行與用戶之間的協(xié)議；另一方面，服務(wù)器會通過交互過程獲得用戶的額外信息。在本方案中，每個用戶既可以是數(shù)據(jù)擁有者，也可以是數(shù)據(jù)使用者。任何用戶都可以向數(shù)據(jù)庫上傳添加自己的加密數(shù)據(jù)，且任何授權(quán)的用戶都可以檢索并解密接受需要的密文。

2.2 方案構(gòu)造

一個基于多線性映射的可搜索加密方案由系統(tǒng)建立、數(shù)據(jù)加密上傳、增刪權(quán)限、陷門生成、數(shù)據(jù)查詢、驗(yàn)證、數(shù)據(jù)下載解密等7個算法構(gòu)成。

（5）加密文檔Encrypt（Fi）。 具體實(shí)施過程：

數(shù)據(jù)擁有者選擇一種安全的對稱加密方案SKE，該對稱加密方案的加解密密鑰為K，將加解密算法公開，任何授權(quán)的用戶均可以使用此加密方案加密自己的數(shù)據(jù)，數(shù)據(jù)使用者也可以使用約定的密鑰生成陷門，從而向服務(wù)器發(fā)送搜索請求，最終解密服務(wù)器返回的數(shù)據(jù)。

3 方案分析

3.1 正確性分析

3.1.1 協(xié)商共享密鑰的正確性

3.1.2 解密算法的正確性

3.2 安全性分析

從表1可以看到，本方案與其他方案相比具有以下優(yōu)勢：首先，本方案以多線性映射為工具，提高了方案的安全性；其次，本方案能夠滿足對搜索結(jié)果的可驗(yàn)證性，以防止存儲的數(shù)據(jù)被服務(wù)器篡改；另外，本方案可以支持多用戶，數(shù)據(jù)擁有者不僅可以靈活地刪除失去權(quán)限的用戶，還能重新添加新增的授權(quán)用戶；最后，與其他方案相比，本方案能夠支持多關(guān)鍵字檢索，為用戶的搜索提供更便捷、高效的服務(wù)。

4 結(jié)語

基于多線性映射的MCDH問題，本文提出了一種標(biāo)準(zhǔn)模型下選擇明文攻擊安全的可搜索加密方案。 一方面，利用多線性映射提高了數(shù)據(jù)擁有者的權(quán)限，使得數(shù)據(jù)擁有者可以動態(tài)地分配權(quán)限；另一方面，方案能夠?qū)崿F(xiàn)多關(guān)鍵詞查詢，通過支持多用戶的搜索，提高數(shù)據(jù)共享的效率。最后，通過安全性與效率分析，該方案的數(shù)據(jù)擁有者對數(shù)據(jù)的管理權(quán)限得到了顯著地提高，有助于存儲數(shù)據(jù)的安全性，能滿足云存儲環(huán)境中數(shù)據(jù)的安全、高效和可驗(yàn)證的要求。下一步還需要深入研究大數(shù)據(jù)環(huán)境下支持模糊查詢的可搜索加密方案，通過構(gòu)造模糊集以實(shí)現(xiàn)關(guān)鍵字的模糊查詢，擴(kuò)大搜索范圍。

參考文獻(xiàn)：

[1]劉全明， 趙寶， 高富強(qiáng).基于屬性的可搜索加密方案[J].山西大學(xué)學(xué)報（自然科學(xué)版）， 2016， 39（4）：593-600.

[2]程小燕.具有關(guān)鍵字搜索性質(zhì)的云存儲加密方案[J].聊城大學(xué)學(xué)報（自然科學(xué)版）， 2014， 27（2）：92-94.

[3]楊旸， 楊書略， 蔡圣暐，等.排序可驗(yàn)證的語義模糊可搜索加密方案[J].四川大學(xué)學(xué)報（工程科學(xué)版）， 2017， 49（4）：119-128.

[4]鐘晗， 郭飛.基于詞嵌入的云存儲可搜索加密方案[J].重慶師范大學(xué)學(xué)報（自然科學(xué)版）， 2017（4）：70-74.

[5]SONG D， WAGNER D， PERRIG A. Practical techniques for searches on encrypted data[C]//Procceeding of the IEEE Symposium on Security and Privacy. Berkeley：IEEE Press， 2000：44-55.

[6]GOH E J.Secure indexes[C]//DIMACS Workshop on Privacy Preserving Data-Mining， USA：United Technology Corporation，2003：216-235.

[7]DANG B， CRESCENZO G D， OSTROVSKY R， et al. Public Key Encryption with Keyword Search[J]. Eurocrypt， 2004， 3027（16）：506-522.

[8]CHANG Y C， MITZENMACHER M. Privacy Preserving Keyword Searches on Remote Encrypted Data[C]//Applied Cryptography and Network Security （ACNS 2005）， Berlin：Springer-Verlag， 2005：442-455.

[9]CURTMOLA R， GARAY J， KAMARA S， et al. Searchable Symmetric Encryption： Improved Definitions and Efficient Constructions[C]//ACM Conf. Computer and Comm. Security （ACM CCS2006）， New York： ACM Digital Library， 2006：376-379.

[10]LI J， WANG Q， WANG C， et al. Fuzzy keyword search over encrypted data in cloud computing[C]//Procceeding of the 29th IEEE international Conference on Computer Communications（INFOCOM′10）， San Diego， CA， USA：IEEE Press， 2010： 441-445.

[11]CHAI Q， GONG G. Verifiable symmetric searchable encryption for semi honest but curious cloud servers[C]//Proccceeding of the IEEE Int'l Conf. on Communications. Ottawa， ON， Canada：IEEE Press， 2012：917-922.

[12]WANG C， REN K， YU S， et al. Achieving usable and privacy-assured similarity search over outsourced cloud data[C]// IEEE INFOCOM. Orlando， FL， USA： IEEE， 2012：451-459.

[13]SUN W， WANG B， CAO N， et al. Verifiable privacy preserving multi-keyword text search in the cloud supporting similarity-based ranking[J].IEEE Transactions on Parallel and Distributed Systems， 2013， 99（11）：1-11.

[14]RHEE H S， PARK J H， SUSILO W， et al. Improved Searchable Public Key Encryption with Designated Tester [C]//Proceedings of the 4th International Symposium on Information， Computer， and Communications Security. Sydney， Australia：ACM Press， 2009： 376-379.

[15]GARG S， GENTRY C， HALEVI S. Candidate Multilinear Maps from Ideal Lattices[C]// International Conference on the Theory and Applications of Cryptographic Techniques.Berlin， Heidelberg：Springer，2013：1-17.

[16]張敏情， 張騰飛， 王緒安. 基于多線性映射的可公開驗(yàn)證加密方案[J].武漢大學(xué)學(xué)報（理學(xué)版）， 2014， 60（6）： 507-512.

[17]于志敏， 景征駿， 古春生. 基于多線性映射的環(huán)簽密廣播公鑰方案[J]. 計(jì)算機(jī)科學(xué)， 2015， 42（3）： 106-110.

[18]彭巧， 田有亮. 基于多線性Diffie-Hellman問題的秘密共享方案[J].電子學(xué)報， 2017， 45（1）： 200-205.

[19]BONEH D， SILVERBERG A. Applications of multilinear forms to cryptography[J].Contemporary Mathematics， 2003， 324（1）： 71-90.

[20]ZHAO Y， CHEN X， MA H， et al. A New Trapdoor -indistinguishable Public Key Encryption with Keyword Search[J]. Journal of Wireless Mobile Networks， Ubiquitous Computing， and Dependable Applications， 2012， 3（1/ 2）： 72-81.

[21]YANG H M， XU C X， ZHAO H T. An Efficient Public Key Encryption with Keyword Scheme Not Using Pairing[C]// First International Conference on Instrumentation， Measurement， Computer， Communication and Control. Washington， DC， USA：IEEE Computer Society， 2011：900-904.

[22]LUO W， TAN J. Public Key Encryption with Keyword Search Based on Factoring [ C ]//Proceedings of CCIS' 12. Hangzhou：IEEE Press， 2012： 1245-1247.

[23]BAEK J， SAFAVINAINI R， SUSILO W. Public Key Encryption with Keyword Search Revisited[C]// Proceedings of International Conference on Computational Science and Its Applications. Perugia， Italy： Springer-Verlag， 2008： 1249-1259.

（責(zé)任編輯：周曉南）