林 楠,費益軍,王宇飛,彭凝多
(1.國家電網(wǎng)公司信息通信分公司,北京100761;2.國家電網(wǎng)公司江蘇省電力公司,南京210024;3.南京南瑞集團公司北京中電普華信息技術有限公司,北京100192;4.電子科技大學計算機科學與工程學院,成都611731)
云環(huán)境下一種排序非對稱的可搜索加密方案
林 楠1,費益軍2,王宇飛3,彭凝多4
(1.國家電網(wǎng)公司信息通信分公司,北京100761;2.國家電網(wǎng)公司江蘇省電力公司,南京210024;3.南京南瑞集團公司北京中電普華信息技術有限公司,北京100192;4.電子科技大學計算機科學與工程學院,成都611731)
可搜索加密算法的基本功能之一是對搜索結果進行排序并返回最佳匹配文件。為使該功能在非對稱可搜索加密算法中實現(xiàn),將非對稱加密結構轉(zhuǎn)換為對稱加密結構,并結合保序加密算法,提出一種在非對稱可搜索加密算法上實現(xiàn)排序查詢功能的方案,進行混合加密密文的檢索。實驗結果表明,與傳統(tǒng)的只支持對稱可搜索加密結構排序方法相比,該方法支持非對稱加密,具有較好的檢索效率,并且應用性強。
可搜索加密;排序加密;保序加密;云存儲;非對稱加密
云存儲為用戶提供了彈性、高可靠、易使用與價格便宜的數(shù)據(jù)存儲服務。隨著云計算的發(fā)展,該類數(shù)據(jù)外包方式受到越來越廣泛的應用[1-2]。然而,數(shù)據(jù)外包存在著天然的安全隱患,因為敏感的數(shù)據(jù)(例如用戶的隱私數(shù)據(jù)、商業(yè)數(shù)據(jù)等)如果放在云上,云服務提供商將能夠直接讀取與使用該數(shù)據(jù),從而導致可能侵犯用戶的隱私與破壞數(shù)據(jù)的安全[3-5]。對大多數(shù)人而言,假定云服務提供商是“絕對可信”是不可能的,因此需要從技術層面為用戶提供隱私與數(shù)據(jù)保護,且在安全性保證的前提下盡可能保障用戶的正常操作功能(例如用關鍵字檢索文件)。目前,用戶隱私的保護與用戶數(shù)據(jù)的安全也成為了制約數(shù)據(jù)外包模式是否能被更廣泛應用的瓶頸。
可搜索加密技術是一種在不影響數(shù)據(jù)檢索功能的條件下,保護用戶數(shù)據(jù)安全與查詢隱私的重要技術手段。對稱可搜索加密方案(Symmetric Searchable Encryption,SSE)[6-10]基于對稱加密技術,加密者可以對遠程密文進行安全的檢索?;诠€機制的非對稱可搜索加密方案(Asymmetric Search-able Encryption,ASE)[11-13]是可搜索加密算法中的另一類加密方案,其應用更靈活,適用面更廣泛,因此在近幾年得到了較快發(fā)展,其應用場景為:數(shù)據(jù)外包者使用公鑰加密數(shù)據(jù)放在云端,用戶使用私鑰生成安全的查詢并提交給服務器,最后服務器返回滿足條件的相應文件。而在所有的過程中,服務器無法得知外包的數(shù)據(jù)內(nèi)容與用戶查詢的內(nèi)容信息。
支持對返回的文件按關鍵字匹配度進行排序,是可搜索加密算法中的標準應用之一。文獻[14]在對稱加密的結構中設置了關鍵字相關性,且為了保證安全進行了隨機化,使得可以近似地返回最相關的文檔。文獻[15]將相關性用保序加密(Order Preserving Encryption,OPE)算法加密,使得可以精確返回最相關的文檔。文獻[16]基于兩輪協(xié)議,在第一輪操作中返回加密的相關性,這樣用戶可以自行選擇最佳匹配文檔。然而,這一系列的方案均基于對稱加密技術。如何在非對稱加密應用場景中,用戶用私鑰生成的令牌來排序用公鑰生成的相關性(此處安全前提是公鑰生成的相關性無法直接排序,否則會泄漏加密的文件信息)成為一個挑戰(zhàn)性的難題。
本文基于非對稱加密結構到對稱加密結構的轉(zhuǎn)化思路,并結合基于對稱加密的保序加密算法,以實現(xiàn)排序查詢功能在非對稱可搜索加密算法中的應用。
排序查詢功能指所有匹配的文檔會根據(jù)一個標準進行排序,最終僅返回給用戶最相關的k個文檔。該功能的查詢SQL格式為“ORDERED BY‘keyword'”。文獻[15]介紹了一種相關性評分的計算方法,并提出了基于保序加密算法(OPE)的分數(shù)大小比較方案。采用同樣的保序加密算法為基礎,排序功能組件可以先記錄加密的相關分數(shù),并構造一個索引記錄“令牌,分數(shù)”數(shù)據(jù)對,從而使得功能組件可以在計算時間復雜度為O(1)的條件下獲取分數(shù)并比較大小進行排序。
為了存儲索引記錄,本文采用基于稀疏矩陣的間接尋址方案[17]構造一個2維索引表A,記錄數(shù)據(jù)對<關鍵字,相關性分數(shù)>。所有數(shù)據(jù)均加密。當查詢時,服務器查找所有匹配文檔的相關性分數(shù),并找出最佳k個文檔。為了安全地使用保序加密算法,加密數(shù)據(jù)前需要一個預處理過程。構造一個保序加密表(OPE Table)來預處理所有的明文,并按如下步驟存儲加密的相關性分數(shù):
(1)給定一個文檔集D=(d1,d2,…,dn),對文檔集中的每一個文檔dk(1≤k≤n)掃描其中的ok個關鍵字W。對于dk中的每一個關鍵字,根據(jù)關鍵字出現(xiàn)的頻率計算相關性分數(shù)(1≤i≤ok),并記錄一個對應于dk的ok×3矩陣。該矩陣的第i行記錄,其中,為第1個在文檔中出現(xiàn)的位置。
(2)對于所有文檔,配置OPE加密的數(shù)據(jù)量N= o1+o2+…+on,編號依次為s1,s2,…,sN。對每一個數(shù)據(jù)sj(1≤j≤N),其保序加密結果為ej。將之前的矩陣轉(zhuǎn)換成為一個保序加密表,表的第i行記錄,其中,是的保序加密結果。
(3)對于一個文檔,至多包含|d|/2+1個關鍵字(注意每個關鍵字后包含一個分隔符,否則該關鍵字無法被識別)。因此,索引表在最后填充到|d|/ 2+1個數(shù)據(jù)項,從而保障文檔內(nèi)容與數(shù)據(jù)項數(shù)量無關。
為了應用非對稱可搜索加密算法的相關功能,這里引用非對稱可搜索加密算法的部分內(nèi)容如下:
定義s←PEKS(Kpub,w)為非對稱可搜索加密算法中的可搜索結構的構造子算法。輸入公鑰Kpub與一個關鍵字w,輸出可搜索結構s。算法由用戶執(zhí)行,生成的可搜索結構s鏈接到加密的消息(單個文檔)后提交給服務器。
定義c←Enc(Kpub,d)為非對稱可搜索加密算法中的文檔加密子算法。輸入公鑰Kpub與消息d(單個文檔),輸出密文c。算法由數(shù)據(jù)發(fā)送者執(zhí)行,密文c連同多個可搜索結構發(fā)送給服務器。
定義一個哈希函數(shù):fh:{0,1}*→{0,1}l,其中,l為映射的長度(根據(jù)選擇的哈希函數(shù))。例如,如果采用MD5作為fh,則l為128 bit。
可排序非對稱可搜索加密算法包括構造算法Build與過濾算法Filter兩部分,分別用于加密時的功能結構的構造與檢索時的文件查詢,具體方案如算法所示。
算法 可排序加密查詢的構造與過濾算法
算法Build的主要流程是從文檔中抽取關鍵字,并基于保序加密方案,結合非對稱可搜索加密算法的數(shù)據(jù)結構,構造索引表。算法Filter的主要流程是根據(jù)每個加密文檔對應的加密索引表,對查詢結果進行排序,并返回排序結果,從而返回最匹配用查詢的文檔。
非正式而言,排序查詢功能的安全性保障模型為:給定2個大小相同的文檔集D1與D2。挑戰(zhàn)者隨機投擲一個公平的硬幣b并用LSE加密Db(密文的順序需要隨機化)。敵手可以查詢一個關鍵字并獲得排序的文檔子集,但無法分辨挑戰(zhàn)者是從哪個文檔集中選擇的子集。
基于文獻[8]提出的抗非自適應選擇關鍵字攻擊模型,并結合文獻[18]提出的保序概念(這里定義為可排序),正式定義抗非自適應選擇排序攻擊安全模型如下。
定義(抗非自適應選擇排序攻擊) 令∑為排序查詢功能組件,k∈?為安全參數(shù)。考慮以下的概率實驗,其中,A為敵手,Sim為模擬器:
(1)Real∑,A(k):挑戰(zhàn)者執(zhí)行密鑰生成算法Gen(1k)產(chǎn)生密鑰K。敵手產(chǎn)生一個文檔集D=(d1,d2,…,dn)(每個文檔的大小固定),從挑戰(zhàn)者處接收到加密的文檔C=(c1,c2,…,cn)與功能結構L=(L1,L2,…,Ln)(隨機順序)。敵手提交一個查詢w,其中,w∈d1∩d2∩…∩dn,并從挑戰(zhàn)者處接收到映射v。最終,A返回一個值b(1或0)作為實驗的輸出。
(2)Simulate∑,A,Sim(k):給定文檔數(shù)量n,每個文檔的大小與映射的大小,Sim生成C*,L*, v*并發(fā)送結果給敵手A。最終,A返回一個值b(1或0)作為實驗的輸出。
稱排序查詢功能組件是CRKA安全的,當且僅當對于所有多項式時間敵手A,存在一個模擬器Sim滿足:|Pr[Real∑,A(k)=1]-Pr[Simulate∑,A,Sim(k)= 1]|≤negl(k)其概率取決于密鑰生成算法Gen(1k)。
定理 如果LSE的接口具有CPA安全性,底層封裝的OPE算法具有POPF-CCA安全性,則排序查詢功能組件具有CRKA安全性。
證明:模擬器以如下方式產(chǎn)生C*,L*,v*:對于C*,模擬器產(chǎn)生n個隨機字符串,每個字符串大小為。對于L*,令m=|d|/2+1,模擬器產(chǎn)生m個隨機字符串V*=,每個字符串長度為。模擬器構造一個m×n矩陣,其中,每個元素為一個隨機數(shù)。則對每一個文檔而言,模擬器產(chǎn)生索引項=。對于v*,模擬器隨機選擇。
現(xiàn)在證明沒有一個多項式分辨器可以分辨(C,L,v)與(C*,L*,v*)。由于密鑰K對于敵手是保密的,因此接口的CPA安全性直接保障C與C*間不可分辨。同時,該安全性保障v與v*間也不可分辨。當接收到v=vi∈V或后,敵手可以調(diào)用Filter(C,L,v)或者Filter(C*,L*,v*)來獲取r1= L1[vi]=e1,e2,…,rn=Ln[vi]=en或者得到。POPFCCA安全性保障集合(r1,r2,…,rn)與集合間不可分辨,即敵手無法分辨OPE的加密結果與一個隨機保序函數(shù)的輸出結果。由此,L與L*間不可分辨。
算法由C++語言編碼,并在一臺虛擬機上運行。虛擬機的配置為64位的雙核2.1 GHz CPU,4 GB內(nèi)存,運行Centos操作系統(tǒng)。每一個文檔設置為固定的10 KB,其內(nèi)容為從一個字典隨機抽取的單詞組合。查詢也是隨機關鍵字(數(shù)量也是隨機的)。過濾算法的運行結果如圖1所示。
圖1 文檔檢索執(zhí)行效率
從圖1中可以看出,可排序的非對稱可搜索加密方案運行效率較高,其根本原因是在加密時將非對稱加密結構間接轉(zhuǎn)化成了對稱加密結構,從而實現(xiàn)了傳統(tǒng)僅在對稱加密算法中支持的功能,并且達到了和對稱可搜索加密算法等同的效率。令n表示需要進一步過濾的文檔數(shù)量。對于排序查詢,其主要的操作為從索引表中獲得相關性分數(shù),該表由稀疏矩陣的間接地址技術維護(壓縮存儲),因此總查詢時間復雜度為O(n)。另外需要從最終結果中比較分數(shù),選擇出最佳k個匹配的文檔,其總計算復雜度為O(n)。由于該索引的壓縮方案并不是唯一的,這里增加非壓縮的索引方案,以此作為檢索時間的下限作為參考。
本文提出了一種在非對稱可搜索加密算法上實現(xiàn)排序查詢功能的方案,彌補了非對稱可搜索加密算法功能較單一的不足。此外該方案本質(zhì)上是對稱加密算法在非對稱加密結構中的混合應用,因此可以擴展到其他基于對稱加密的數(shù)據(jù)結構上,從而豐富非對稱可搜索加密方案的功能與應用。
[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].軟件學報,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.
編輯 索書志
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
林 楠,費益軍,王宇飛,等.云環(huán)境下一種排序非對稱的可搜索加密方案[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
四川省科技支撐計劃基金資助項目(2013JQ0005,2014JY0010)。
林 楠(1987-),男,碩士,主研方向:信息安全,云計算;費益軍、王宇飛,碩士;彭凝多,博士研究生。
2014-11-17
2014-12-04 E-m ail:freedom.w ind@163.com