云環(huán)境下一種排序非對(duì)稱(chēng)的可搜索加密方案

林 楠，費(fèi)益軍，王宇飛，彭凝多

（1.國(guó)家電網(wǎng)公司信息通信分公司，北京100761；2.國(guó)家電網(wǎng)公司江蘇省電力公司，南京210024；3.南京南瑞集團(tuán)公司北京中電普華信息技術(shù)有限公司，北京100192；4.電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，成都611731）

云環(huán)境下一種排序非對(duì)稱(chēng)的可搜索加密方案

林 楠1，費(fèi)益軍2，王宇飛3，彭凝多4

（1.國(guó)家電網(wǎng)公司信息通信分公司，北京100761；2.國(guó)家電網(wǎng)公司江蘇省電力公司，南京210024；3.南京南瑞集團(tuán)公司北京中電普華信息技術(shù)有限公司，北京100192；4.電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，成都611731）

可搜索加密算法的基本功能之一是對(duì)搜索結(jié)果進(jìn)行排序并返回最佳匹配文件。為使該功能在非對(duì)稱(chēng)可搜索加密算法中實(shí)現(xiàn)，將非對(duì)稱(chēng)加密結(jié)構(gòu)轉(zhuǎn)換為對(duì)稱(chēng)加密結(jié)構(gòu)，并結(jié)合保序加密算法，提出一種在非對(duì)稱(chēng)可搜索加密算法上實(shí)現(xiàn)排序查詢(xún)功能的方案，進(jìn)行混合加密密文的檢索。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的只支持對(duì)稱(chēng)可搜索加密結(jié)構(gòu)排序方法相比，該方法支持非對(duì)稱(chēng)加密，具有較好的檢索效率，并且應(yīng)用性強(qiáng)。

可搜索加密；排序加密；保序加密；云存儲(chǔ)；非對(duì)稱(chēng)加密

1 概述

云存儲(chǔ)為用戶(hù)提供了彈性、高可靠、易使用與價(jià)格便宜的數(shù)據(jù)存儲(chǔ)服務(wù)。隨著云計(jì)算的發(fā)展，該類(lèi)數(shù)據(jù)外包方式受到越來(lái)越廣泛的應(yīng)用［1-2］。然而，數(shù)據(jù)外包存在著天然的安全隱患，因?yàn)槊舾械臄?shù)據(jù)（例如用戶(hù)的隱私數(shù)據(jù)、商業(yè)數(shù)據(jù)等）如果放在云上，云服務(wù)提供商將能夠直接讀取與使用該數(shù)據(jù)，從而導(dǎo)致可能侵犯用戶(hù)的隱私與破壞數(shù)據(jù)的安全［3-5］。對(duì)大多數(shù)人而言，假定云服務(wù)提供商是“絕對(duì)可信”是不可能的，因此需要從技術(shù)層面為用戶(hù)提供隱私與數(shù)據(jù)保護(hù)，且在安全性保證的前提下盡可能保障用戶(hù)的正常操作功能（例如用關(guān)鍵字檢索文件）。目前，用戶(hù)隱私的保護(hù)與用戶(hù)數(shù)據(jù)的安全也成為了制約數(shù)據(jù)外包模式是否能被更廣泛應(yīng)用的瓶頸。

可搜索加密技術(shù)是一種在不影響數(shù)據(jù)檢索功能的條件下，保護(hù)用戶(hù)數(shù)據(jù)安全與查詢(xún)隱私的重要技術(shù)手段。對(duì)稱(chēng)可搜索加密方案（Symmetric Searchable Encryption，SSE）［6-10］基于對(duì)稱(chēng)加密技術(shù)，加密者可以對(duì)遠(yuǎn)程密文進(jìn)行安全的檢索。基于公鑰機(jī)制的非對(duì)稱(chēng)可搜索加密方案（Asymmetric Search-able Encryption，ASE）［11-13］是可搜索加密算法中的另一類(lèi)加密方案，其應(yīng)用更靈活，適用面更廣泛，因此在近幾年得到了較快發(fā)展，其應(yīng)用場(chǎng)景為：數(shù)據(jù)外包者使用公鑰加密數(shù)據(jù)放在云端，用戶(hù)使用私鑰生成安全的查詢(xún)并提交給服務(wù)器，最后服務(wù)器返回滿(mǎn)足條件的相應(yīng)文件。而在所有的過(guò)程中，服務(wù)器無(wú)法得知外包的數(shù)據(jù)內(nèi)容與用戶(hù)查詢(xún)的內(nèi)容信息。

支持對(duì)返回的文件按關(guān)鍵字匹配度進(jìn)行排序，是可搜索加密算法中的標(biāo)準(zhǔn)應(yīng)用之一。文獻(xiàn)［14］在對(duì)稱(chēng)加密的結(jié)構(gòu)中設(shè)置了關(guān)鍵字相關(guān)性，且為了保證安全進(jìn)行了隨機(jī)化，使得可以近似地返回最相關(guān)的文檔。文獻(xiàn)［15］將相關(guān)性用保序加密（Order Preserving Encryption，OPE）算法加密，使得可以精確返回最相關(guān)的文檔。文獻(xiàn)［16］基于兩輪協(xié)議，在第一輪操作中返回加密的相關(guān)性，這樣用戶(hù)可以自行選擇最佳匹配文檔。然而，這一系列的方案均基于對(duì)稱(chēng)加密技術(shù)。如何在非對(duì)稱(chēng)加密應(yīng)用場(chǎng)景中，用戶(hù)用私鑰生成的令牌來(lái)排序用公鑰生成的相關(guān)性（此處安全前提是公鑰生成的相關(guān)性無(wú)法直接排序，否則會(huì)泄漏加密的文件信息）成為一個(gè)挑戰(zhàn)性的難題。

本文基于非對(duì)稱(chēng)加密結(jié)構(gòu)到對(duì)稱(chēng)加密結(jié)構(gòu)的轉(zhuǎn)化思路，并結(jié)合基于對(duì)稱(chēng)加密的保序加密算法，以實(shí)現(xiàn)排序查詢(xún)功能在非對(duì)稱(chēng)可搜索加密算法中的應(yīng)用。

2 方案構(gòu)造

排序查詢(xún)功能指所有匹配的文檔會(huì)根據(jù)一個(gè)標(biāo)準(zhǔn)進(jìn)行排序，最終僅返回給用戶(hù)最相關(guān)的k個(gè)文檔。該功能的查詢(xún)SQL格式為“ORDERED BY‘keyword'”。文獻(xiàn)［15］介紹了一種相關(guān)性評(píng)分的計(jì)算方法，并提出了基于保序加密算法（OPE）的分?jǐn)?shù)大小比較方案。采用同樣的保序加密算法為基礎(chǔ)，排序功能組件可以先記錄加密的相關(guān)分?jǐn)?shù)，并構(gòu)造一個(gè)索引記錄“令牌，分?jǐn)?shù)”數(shù)據(jù)對(duì)，從而使得功能組件可以在計(jì)算時(shí)間復(fù)雜度為O（1）的條件下獲取分?jǐn)?shù)并比較大小進(jìn)行排序。

為了存儲(chǔ)索引記錄，本文采用基于稀疏矩陣的間接尋址方案［17］構(gòu)造一個(gè)2維索引表A，記錄數(shù)據(jù)對(duì)＜關(guān)鍵字，相關(guān)性分?jǐn)?shù)＞。所有數(shù)據(jù)均加密。當(dāng)查詢(xún)時(shí)，服務(wù)器查找所有匹配文檔的相關(guān)性分?jǐn)?shù)，并找出最佳k個(gè)文檔。為了安全地使用保序加密算法，加密數(shù)據(jù)前需要一個(gè)預(yù)處理過(guò)程。構(gòu)造一個(gè)保序加密表（OPE Table）來(lái)預(yù)處理所有的明文，并按如下步驟存儲(chǔ)加密的相關(guān)性分?jǐn)?shù)：

（1）給定一個(gè)文檔集D=（d1，d2，…，dn），對(duì)文檔集中的每一個(gè)文檔dk（1≤k≤n）掃描其中的ok個(gè)關(guān)鍵字W。對(duì)于dk中的每一個(gè)關(guān)鍵字，根據(jù)關(guān)鍵字出現(xiàn)的頻率計(jì)算相關(guān)性分?jǐn)?shù)（1≤i≤ok），并記錄一個(gè)對(duì)應(yīng)于dk的ok×3矩陣。該矩陣的第i行記錄，其中，為第1個(gè)在文檔中出現(xiàn)的位置。

（2）對(duì)于所有文檔，配置OPE加密的數(shù)據(jù)量N= o1+o2+…+on，編號(hào)依次為s1，s2，…，sN。對(duì)每一個(gè)數(shù)據(jù)sj（1≤j≤N），其保序加密結(jié)果為ej。將之前的矩陣轉(zhuǎn)換成為一個(gè)保序加密表，表的第i行記錄，其中，是的保序加密結(jié)果。

（3）對(duì)于一個(gè)文檔，至多包含|d|/2+1個(gè)關(guān)鍵字（注意每個(gè)關(guān)鍵字后包含一個(gè)分隔符，否則該關(guān)鍵字無(wú)法被識(shí)別）。因此，索引表在最后填充到|d|/ 2+1個(gè)數(shù)據(jù)項(xiàng)，從而保障文檔內(nèi)容與數(shù)據(jù)項(xiàng)數(shù)量無(wú)關(guān)。

為了應(yīng)用非對(duì)稱(chēng)可搜索加密算法的相關(guān)功能，這里引用非對(duì)稱(chēng)可搜索加密算法的部分內(nèi)容如下：

定義s←PEKS（Kpub，w）為非對(duì)稱(chēng)可搜索加密算法中的可搜索結(jié)構(gòu)的構(gòu)造子算法。輸入公鑰Kpub與一個(gè)關(guān)鍵字w，輸出可搜索結(jié)構(gòu)s。算法由用戶(hù)執(zhí)行，生成的可搜索結(jié)構(gòu)s鏈接到加密的消息（單個(gè)文檔）后提交給服務(wù)器。

定義c←Enc（Kpub，d）為非對(duì)稱(chēng)可搜索加密算法中的文檔加密子算法。輸入公鑰Kpub與消息d（單個(gè)文檔），輸出密文c。算法由數(shù)據(jù)發(fā)送者執(zhí)行，密文c連同多個(gè)可搜索結(jié)構(gòu)發(fā)送給服務(wù)器。

定義一個(gè)哈希函數(shù)：fh：｛0，1｝*→｛0，1｝l，其中，l為映射的長(zhǎng)度（根據(jù)選擇的哈希函數(shù)）。例如，如果采用MD5作為fh，則l為128 bit。

可排序非對(duì)稱(chēng)可搜索加密算法包括構(gòu)造算法Build與過(guò)濾算法Filter兩部分，分別用于加密時(shí)的功能結(jié)構(gòu)的構(gòu)造與檢索時(shí)的文件查詢(xún)，具體方案如算法所示。

算法 可排序加密查詢(xún)的構(gòu)造與過(guò)濾算法

算法Build的主要流程是從文檔中抽取關(guān)鍵字，并基于保序加密方案，結(jié)合非對(duì)稱(chēng)可搜索加密算法的數(shù)據(jù)結(jié)構(gòu)，構(gòu)造索引表。算法Filter的主要流程是根據(jù)每個(gè)加密文檔對(duì)應(yīng)的加密索引表，對(duì)查詢(xún)結(jié)果進(jìn)行排序，并返回排序結(jié)果，從而返回最匹配用查詢(xún)的文檔。

3 安全性證明

非正式而言，排序查詢(xún)功能的安全性保障模型為：給定2個(gè)大小相同的文檔集D1與D2。挑戰(zhàn)者隨機(jī)投擲一個(gè)公平的硬幣b并用LSE加密Db（密文的順序需要隨機(jī)化）。敵手可以查詢(xún)一個(gè)關(guān)鍵字并獲得排序的文檔子集，但無(wú)法分辨挑戰(zhàn)者是從哪個(gè)文檔集中選擇的子集。

基于文獻(xiàn)［8］提出的抗非自適應(yīng)選擇關(guān)鍵字攻擊模型，并結(jié)合文獻(xiàn)［18］提出的保序概念（這里定義為可排序），正式定義抗非自適應(yīng)選擇排序攻擊安全模型如下。

定義（抗非自適應(yīng)選擇排序攻擊） 令∑為排序查詢(xún)功能組件，k∈?為安全參數(shù)。考慮以下的概率實(shí)驗(yàn)，其中，A為敵手，Sim為模擬器：

（1）Real∑，A（k）：挑戰(zhàn)者執(zhí)行密鑰生成算法Gen（1k）產(chǎn)生密鑰K。敵手產(chǎn)生一個(gè)文檔集D=（d1，d2，…，dn）（每個(gè)文檔的大小固定），從挑戰(zhàn)者處接收到加密的文檔C=（c1，c2，…，cn）與功能結(jié)構(gòu)L=（L1，L2，…，Ln）（隨機(jī)順序）。敵手提交一個(gè)查詢(xún)w，其中，w∈d1∩d2∩…∩dn，并從挑戰(zhàn)者處接收到映射v。最終，A返回一個(gè)值b（1或0）作為實(shí)驗(yàn)的輸出。

（2）Simulate∑，A，Sim（k）：給定文檔數(shù)量n，每個(gè)文檔的大小與映射的大小，Sim生成C*，L*， v*并發(fā)送結(jié)果給敵手A。最終，A返回一個(gè)值b（1或0）作為實(shí)驗(yàn)的輸出。

稱(chēng)排序查詢(xún)功能組件是CRKA安全的，當(dāng)且僅當(dāng)對(duì)于所有多項(xiàng)式時(shí)間敵手A，存在一個(gè)模擬器Sim滿(mǎn)足：|Pr［Real∑，A（k）=1］-Pr［Simulate∑，A，Sim（k）= 1］|≤negl（k）其概率取決于密鑰生成算法Gen（1k）。

定理 如果LSE的接口具有CPA安全性，底層封裝的OPE算法具有POPF-CCA安全性，則排序查詢(xún)功能組件具有CRKA安全性。

證明：模擬器以如下方式產(chǎn)生C*，L*，v*：對(duì)于C*，模擬器產(chǎn)生n個(gè)隨機(jī)字符串，每個(gè)字符串大小為。對(duì)于L*，令m=|d|/2+1，模擬器產(chǎn)生m個(gè)隨機(jī)字符串V*=，每個(gè)字符串長(zhǎng)度為。模擬器構(gòu)造一個(gè)m×n矩陣，其中，每個(gè)元素為一個(gè)隨機(jī)數(shù)。則對(duì)每一個(gè)文檔而言，模擬器產(chǎn)生索引項(xiàng)=。對(duì)于v*，模擬器隨機(jī)選擇。

現(xiàn)在證明沒(méi)有一個(gè)多項(xiàng)式分辨器可以分辨（C，L，v）與（C*，L*，v*）。由于密鑰K對(duì)于敵手是保密的，因此接口的CPA安全性直接保障C與C*間不可分辨。同時(shí)，該安全性保障v與v*間也不可分辨。當(dāng)接收到v=vi∈V或后，敵手可以調(diào)用Filter（C，L，v）或者Filter（C*，L*，v*）來(lái)獲取r1= L1［vi］=e1，e2，…，rn=Ln［vi］=en或者得到。POPFCCA安全性保障集合（r1，r2，…，rn）與集合間不可分辨，即敵手無(wú)法分辨OPE的加密結(jié)果與一個(gè)隨機(jī)保序函數(shù)的輸出結(jié)果。由此，L與L*間不可分辨。

4 性能分析

算法由C++語(yǔ)言編碼，并在一臺(tái)虛擬機(jī)上運(yùn)行。虛擬機(jī)的配置為64位的雙核2.1 GHz CPU，4 GB內(nèi)存，運(yùn)行Centos操作系統(tǒng)。每一個(gè)文檔設(shè)置為固定的10 KB，其內(nèi)容為從一個(gè)字典隨機(jī)抽取的單詞組合。查詢(xún)也是隨機(jī)關(guān)鍵字（數(shù)量也是隨機(jī)的）。過(guò)濾算法的運(yùn)行結(jié)果如圖1所示。

圖1 文檔檢索執(zhí)行效率

從圖1中可以看出，可排序的非對(duì)稱(chēng)可搜索加密方案運(yùn)行效率較高，其根本原因是在加密時(shí)將非對(duì)稱(chēng)加密結(jié)構(gòu)間接轉(zhuǎn)化成了對(duì)稱(chēng)加密結(jié)構(gòu)，從而實(shí)現(xiàn)了傳統(tǒng)僅在對(duì)稱(chēng)加密算法中支持的功能，并且達(dá)到了和對(duì)稱(chēng)可搜索加密算法等同的效率。令n表示需要進(jìn)一步過(guò)濾的文檔數(shù)量。對(duì)于排序查詢(xún)，其主要的操作為從索引表中獲得相關(guān)性分?jǐn)?shù)，該表由稀疏矩陣的間接地址技術(shù)維護(hù)（壓縮存儲(chǔ)），因此總查詢(xún)時(shí)間復(fù)雜度為O（n）。另外需要從最終結(jié)果中比較分?jǐn)?shù)，選擇出最佳k個(gè)匹配的文檔，其總計(jì)算復(fù)雜度為O（n）。由于該索引的壓縮方案并不是唯一的，這里增加非壓縮的索引方案，以此作為檢索時(shí)間的下限作為參考。

5 結(jié)束語(yǔ)

本文提出了一種在非對(duì)稱(chēng)可搜索加密算法上實(shí)現(xiàn)排序查詢(xún)功能的方案，彌補(bǔ)了非對(duì)稱(chēng)可搜索加密算法功能較單一的不足。此外該方案本質(zhì)上是對(duì)稱(chēng)加密算法在非對(duì)稱(chēng)加密結(jié)構(gòu)中的混合應(yīng)用，因此可以擴(kuò)展到其他基于對(duì)稱(chēng)加密的數(shù)據(jù)結(jié)構(gòu)上，從而豐富非對(duì)稱(chēng)可搜索加密方案的功能與應(yīng)用。

［1］ Fox A，Griffith R，Joseph A，et al.Above the Clouds：A Berkeley View of Cloud Computing［D］.Berkeley，USA：Department of Electrical Engineering and Computing Sciences，University of California，2009.

［2］ Chakraborty R，Ram ireddy S，Raghu T S，et al.The Information Assurance Practices of Cloud Computing Vendors［J］.IT Professional，2010，12（4）：29-37.

［3］ Takabi H，Joshi B D，Ahn G J.Security and Privacy Challenges in Cloud Computing Environments［J］.IEEE Security&Privacy，2010，8（6）：24-31.

［4］ Subashini S，Kavitha V.A Survey on Security Issues in Service Delivery Models of Cloud Computing［J］. Journal of Network and Computing Applications，2011，34（1）：1-11.

［5］ Popovic K，Hocenski Z.Cloud Computing Security Issues and Challenges［C］//Proceedings of IEEE MIPRO'10.Washington D.C.，USA：IEEE Press，2010：344-349.

［6］ Song D X，Wagner D，Perrig A.Practical Techniques for Searches on Encrypted Data［C］//Proceedings of IEEE Symposium on Security and Privacy.Washington D.C.，USA：IEEE Press，2000：44-55.

［7］ 沈志榮，薛 巍，舒繼武.可搜索加密機(jī)制研究與進(jìn)展［J］.軟件學(xué)報(bào)，2014，25（4）：880-895.

［8］ Curtm ola R，Garay J，Kamara S，et al.Searchable Symmetric Encryption：Improved Definitions and Efficient Constructions［C］//Proceedings of the 13th ACM Conference on Computing and Communications Security.New Yrok，USA：ACM Press，2006：79-88.

［9］ Kamara S，Papamanthou C，Roeder T.CS2：A Searchable Cryptographic Cloud Storage System，TechReport：MSRTR-2011-58［R］.Redmond，USA：Microsoft Research，2011.

［10］ Chase M，Kamara S.Structured Encryption and Controlled Disclosure［C］//Proceedings of ASIACRYPT'10. Berlin，Germany：Springer，2010：577-594.

［11］ Boneh D，Di-Crescenzo G，Ostrovsky R，et al.Public Key Encryption with Keyword Search［C］//Proceedings of Advances in Cryptology-Eurocrypt'04.Berlin，Germ any：Springer，2004：506-522.

［12］ Abdalla M，Bellare M，Catalano D，et al.Searchable Encryption Revisited：Consistency Properties，Relation to Anonymous IBE，and Extensions［C］//Proceedings of Advances in Cryptology-CRYPTO'05.Berlin，Germany：Springer，2005：205-222.

［13］ Boneh D，Kushilevitz E，Ostrovsky R，et al.Public Key Encryption that Allows PIR Queries［C］//Proceedings of Advances in Cryptology-CRYPTO'07.Berlin，Germ any：Springer，2007：50-67.

［14］ Cao N，Wang C，Li M，et al.Privacy-preserving Multikeyword Ranked Search over Encrypted Cloud Data［J］. IEEE Transactions on Parallel and Distributed System s，2014，25（1）：222-233.

［15］ Wang C，Cao N，Li J，et al.Secure Ranked Keyword Search over Encrypted Cloud Data［C］//Proceedings of the 30th IEEE International Conference on Distributed Computing Systems.Washington D.C.，USA：IEEE Press，2010：253-262.

［16］ Swaminathan A，Mao Y，Su G M，et al.Confidentiality-preserving Rank-ordered Search［C］//Proceedings of 2007 ACM Workshop on Storage Security and Survivabi-lity.New Y rok，USA：ACM Press，2007：7-12.

［17］ Fredman M L，Komlós J，Szemerédi E.Storing a Sparse Table with O（1）Worst Case Access Time［J］.Journal of the ACM，1984，31（3）：538-544.

［18］ Boldyreva A，Chenette N，Lee Y，et al.Order-preserving Symmetric Encryption［C］//Proceedings of Advances in Cryptology-EUROCRYPT'09.Berlin，Germany：Springer，2009：224-241.

編輯 索書(shū)志

Ranked-order Asymmetric Searchable Encryption Scheme in Cloud Environment

LIN Nan1，F(xiàn)EIYijun2，WANG Yufei3，PENG Ningduo4
（1.Information&Telecommunication Branch，State Grid Corporation of China，Beijing 100761，China；
2.Jiangsu Electric Power Company，State Grid Corporation of China，Nanjing 210024，China；
3.Beijing China Power Information Technology Co.Ltd.，NARIGroup Corporation，Beijing 100192，China；
4.School of Computing Science and Engineering，University of Electronic Science and Technology of China，Chengdu 611731，China）

Ranking the search results and returning the most matched documents is an important and basic function for searchable encryption technique.In order to support such function in asymmetric searchable encryption，this paper proposes a method to transform the asymmetric structure to symmetric structure.Combining with the preserving-order encryption，searching in the mixed encrypted documents is realized.In comparison with prior works that only support symmetric encryption，the algorithm supports asymmetric encryption.Experimental results show that the new algorithm is efficient and practical.

searchable encryption；ranked-order encryption；preserving-order encryption；cloud storage；asymmetric encryption

林 楠，費(fèi)益軍，王宇飛，等.云環(huán)境下一種排序非對(duì)稱(chēng)的可搜索加密方案［J］.計(jì)算機(jī)工程，2015，41（11）：190-193.

英文引用格式：Lin Nan，F(xiàn)ei Yijun，Wang Yufei，et al.Ranked-order Asymmetric Searchable Encryption Scheme in Cloud Environment［J］.Computer Engineering，2015，41（11）：190-193.

1000-3428（2015）11-0190-04

A

TP309

10.3969/j.issn.1000-3428.2015.11.033

四川省科技支撐計(jì)劃基金資助項(xiàng)目（2013JQ0005，2014JY0010）。

林 楠（1987-），男，碩士，主研方向：信息安全，云計(jì)算；費(fèi)益軍、王宇飛，碩士；彭凝多，博士研究生。

2014-11-17

2014-12-04 E-m ail：freedom.w ind@163.com