面向物聯(lián)網(wǎng)搜索的數(shù)據(jù)隱私保護研究綜述

王佳慧，劉川意，方濱興

（1. 北京郵電大學(xué)計算機學(xué)院，北京 100876；2. 哈爾濱工業(yè)大學(xué)深圳研究生院，廣東 深圳 518055；3. 東莞電子科技大學(xué)電子信息工程研究院，廣東 東莞 523000）

面向物聯(lián)網(wǎng)搜索的數(shù)據(jù)隱私保護研究綜述

王佳慧1,2，劉川意2,3，方濱興2,3

（1. 北京郵電大學(xué)計算機學(xué)院，北京 100876；2. 哈爾濱工業(yè)大學(xué)深圳研究生院，廣東 深圳 518055；3. 東莞電子科技大學(xué)電子信息工程研究院，廣東 東莞 523000）

隨著物聯(lián)網(wǎng)和云計算、大數(shù)據(jù)技術(shù)的飛速發(fā)展和廣泛應(yīng)用，迫切需要實時、快速、精準(zhǔn)地搜索現(xiàn)實世界中物理實體等相關(guān)信息，使物聯(lián)網(wǎng)搜索引擎應(yīng)運而生。然而，由于物聯(lián)網(wǎng)搜索引擎的開放性，使在互聯(lián)網(wǎng)搜索領(lǐng)域就已經(jīng)存在的數(shù)據(jù)隱私問題變得更加突出。闡述了物聯(lián)網(wǎng)搜索隱私保護的研究背景和挑戰(zhàn)，提出了面向物聯(lián)網(wǎng)搜索的數(shù)據(jù)隱私保護框架及相關(guān)技術(shù)。綜述了近年來提出的、適用于物聯(lián)網(wǎng)搜索的數(shù)據(jù)隱私保護技術(shù)的研究背景、最新研究進展以及主要研究方向，最后，指出了一些重要研究方向，為未來研究工作指明方向。

物聯(lián)網(wǎng)搜索；隱私保護；屬性加密；密文搜索；隱藏隨機訪問模式

1 引言

在擁有海量實體的物聯(lián)網(wǎng)[1]中，人們越來越需要實時、快速、精準(zhǔn)地搜索現(xiàn)實世界中物理實體等相關(guān)信息，如附近哪里有無煙、環(huán)境好的咖啡廳、從家到機場的道路哪條是最暢通的等，由此，面向物聯(lián)網(wǎng)的數(shù)據(jù)搜索引擎應(yīng)運而生。由瑞士蘇黎世聯(lián)邦理工大學(xué)、德國呂貝克大學(xué)以及德國都科摩通信實驗室設(shè)計的Dyser[2]是一個物聯(lián)網(wǎng)實時搜索引擎，不僅支持物理實體靜態(tài)信息的搜索，還能根據(jù)用戶指定的當(dāng)前狀態(tài)實時搜索物理實體。Shodan[3]是提供在線設(shè)備的物聯(lián)網(wǎng)搜索引擎，只要輸入搜索關(guān)鍵字，就可以找到全世界與互聯(lián)網(wǎng)相連的網(wǎng)絡(luò)攝像頭、路由器、信號燈、核電站、冰箱、醫(yī)療設(shè)備等包含信息漏洞的設(shè)備。然而這些原型系統(tǒng)都只支持物聯(lián)網(wǎng)的特定搜索條件和場景的搜索，還無法真正解決目前全球化的物聯(lián)網(wǎng)搜索問題，而且這些解決方案也未得到業(yè)界的一致認同和實際的廣泛應(yīng)用。

真正意義上全球化的物聯(lián)網(wǎng)搜索是指根據(jù)一定的策略和方法從物聯(lián)網(wǎng)上實時、快速、精準(zhǔn)地獲取各種物理實體、人物、信息等，并對這些對象進行高效的組織和管理，從而為用戶提供各類搜索服務(wù)，返回滿足其搜索請求的信息。盡管目前物聯(lián)網(wǎng)搜索仍處于萌芽狀態(tài)，由此帶來的數(shù)據(jù)隱私問題卻已經(jīng)不容忽視。韓國產(chǎn)業(yè)研究院認為，2020年因物聯(lián)網(wǎng)安全隱私問題導(dǎo)致的經(jīng)濟損失將達到180億美元注1物聯(lián)網(wǎng)的致命弱點（經(jīng)濟觀察網(wǎng)），http://www.eeo.com.cn/2016/0317/284248.shtml。。由于物聯(lián)網(wǎng)搜索的應(yīng)用領(lǐng)域廣泛，包括國民經(jīng)濟和社會發(fā)展各個領(lǐng)域，所以其隱私泄露不僅包含傳統(tǒng)的網(wǎng)絡(luò)虛擬空間，還將進一步侵犯到實體生活當(dāng)中，除了經(jīng)濟損失外，個人的生命安全以及國家基礎(chǔ)設(shè)施也都將受到極大的威脅。由于物聯(lián)網(wǎng)搜索對象和搜索空間的廣泛性、搜索數(shù)據(jù)的高度動態(tài)性、搜索內(nèi)容的高度時空性、搜索語言的復(fù)雜性等特點，使物聯(lián)網(wǎng)搜索的數(shù)據(jù)隱私保護面臨更大的安全挑戰(zhàn)?？梢哉f數(shù)據(jù)隱私保護是制約全球化的物聯(lián)網(wǎng)搜索發(fā)展并實際應(yīng)用于產(chǎn)業(yè)界的關(guān)鍵因素。

首先，物聯(lián)網(wǎng)搜索服務(wù)提供者后臺服務(wù)器系統(tǒng)存有大量通過攝像頭、傳感器等感知設(shè)備收集的數(shù)據(jù)信息，而由于物聯(lián)網(wǎng)搜索應(yīng)用領(lǐng)域廣泛，包括國民經(jīng)濟各行業(yè)乃至社會發(fā)展各領(lǐng)域，這些數(shù)據(jù)信息如果不加以安全隱私的規(guī)范，將成為一個龐大的盯梢系統(tǒng)。類似于“棱鏡計劃”的通過內(nèi)部數(shù)據(jù)搜索和挖掘?qū)е碌膫€人數(shù)據(jù)隱私侵犯將更加廣泛和便利。因此，物聯(lián)網(wǎng)搜索過程中的數(shù)據(jù)內(nèi)容隱私保護變得十分必要。

其次，物聯(lián)網(wǎng)搜索服務(wù)如果被攻擊者惡意利用，則可能對個人的生命安全及國家基礎(chǔ)設(shè)施構(gòu)成嚴(yán)重威脅。黑客通過物聯(lián)網(wǎng)搜索引擎可以搜索家庭中有安全漏洞的智能設(shè)備，進而控制其他安全設(shè)備，比如控制智能大門、解除監(jiān)控攝像頭的監(jiān)視功能等。通過物聯(lián)網(wǎng)搜索有安全漏洞的智能兒童鞋、智能手環(huán)等，可以查看孩子的地理位置和行為軌跡，如果被別有用心地利用，則可能對兒童安全構(gòu)成更大的威脅。國際黑客安保論壇上曾經(jīng)展示過現(xiàn)場破解醫(yī)療設(shè)備，并遠程遙控糖尿病患者用的胰島素泵和心臟病患者用的心跳器。而網(wǎng)站的研究者曾使用 Shodan定位到了核電站的指揮和控制系統(tǒng)及一個粒子回旋加速器。由于物聯(lián)網(wǎng)搜索引擎的存在，所有與物聯(lián)網(wǎng)相連的實體，包括智能家庭、智能汽車、智能城市等顯得更加不安全和脆弱。因此，如何確保物聯(lián)網(wǎng)搜索服務(wù)不被別有用心的攻擊者利用也是一個很大的挑戰(zhàn)。

再次，通過物聯(lián)網(wǎng)搜索引擎可以對用戶訪問模式等數(shù)據(jù)進行深度挖掘，使物聯(lián)網(wǎng)搜索引擎對用戶的行為、愛好更加了解，對敏感數(shù)據(jù)和隱私信息構(gòu)成威脅。Pinkas和 Reinman[4]指出，服務(wù)器通過分析用戶的訪問模式，再結(jié)合一定的背景知識，可以推斷出用戶的部分隱私信息。如果服務(wù)器監(jiān)測到用戶進行特定的數(shù)據(jù)訪問序列(u1, u2, u3)后，都會進行一次股票交易操作，那么當(dāng)用戶再次發(fā)起相同或相似的訪問序列時，即使這些信息是加密的，服務(wù)器也可以以極高的概率推測出用戶接下來要進行一次股票交易，進而推斷出這些訪問序列的內(nèi)容。因此，隱藏訪問模式對保護物聯(lián)網(wǎng)搜索用戶隱私起到很重要的作用。

本文針對上述物聯(lián)網(wǎng)搜索數(shù)據(jù)隱私保護面臨的安全挑戰(zhàn)，提出面向物聯(lián)網(wǎng)搜索的數(shù)據(jù)隱私保護框架，并在此基礎(chǔ)上對現(xiàn)有的適用于物聯(lián)網(wǎng)搜索隱私保護相關(guān)關(guān)鍵技術(shù)的國內(nèi)外研究進展進行綜述。最后給出了未來工作展望。

需要特別說明的是本文主要關(guān)注適用于物聯(lián)網(wǎng)搜索的數(shù)據(jù)隱私保護，同時又不影響搜索服務(wù)質(zhì)量的技術(shù)。而基于數(shù)據(jù)失真的技術(shù)和基于限制發(fā)布的技術(shù)都存在一定程度的信息丟失，因此不在本文的研究范疇。

2 物聯(lián)網(wǎng)搜索隱私保護框架

典型的物聯(lián)網(wǎng)搜索協(xié)議包括3個參與者：數(shù)據(jù)擁有者、數(shù)據(jù)搜索者和物聯(lián)網(wǎng)搜索服務(wù)提供者。其中，數(shù)據(jù)搜索者也可能是數(shù)據(jù)擁有者本身。數(shù)據(jù)擁有者是指上傳物理實體相關(guān)信息資源的個體或機構(gòu)，數(shù)據(jù)搜索者是指使用物聯(lián)網(wǎng)搜索服務(wù)的個體或機構(gòu)，物聯(lián)網(wǎng)搜索服務(wù)提供者是指提供物聯(lián)網(wǎng)搜索服務(wù)的提供商及后臺系統(tǒng)。要想實現(xiàn)面向物聯(lián)網(wǎng)搜索的數(shù)據(jù)隱私保護，就需要從3個參與者著手，采用隱私保護技術(shù)加以限制。

面向物聯(lián)網(wǎng)搜索的數(shù)據(jù)隱私保護框架如圖1所示，通過數(shù)據(jù)擁有者加密上傳到物聯(lián)網(wǎng)搜索服務(wù)提供者中的數(shù)據(jù)和數(shù)據(jù)搜索者加密搜索請求以及密文搜索方案來確保物聯(lián)網(wǎng)搜索服務(wù)提供者無法對其后臺系統(tǒng)中的數(shù)據(jù)進行窺探；通過細粒度的訪問控制來確保物聯(lián)網(wǎng)搜索服務(wù)不被濫用；通過隱藏用戶訪問模式來避免深度數(shù)據(jù)隱私挖掘。

后續(xù)依次對適用于物聯(lián)網(wǎng)搜索的隱私保護技術(shù)：基于數(shù)據(jù)加密的搜索技術(shù)、基于屬性加密的訪問控制以及隱藏訪問模式技術(shù)的研究進展進行綜述。

3 基于密文搜索的隱私保護技術(shù)

3.1 總述

密文搜索技術(shù)使物聯(lián)網(wǎng)搜索服務(wù)提供者在返回滿足用戶搜索請求數(shù)據(jù)的同時，無法得知數(shù)據(jù)的內(nèi)容。如圖2所示，基于數(shù)據(jù)加密的搜索技術(shù)分為2個階段：系統(tǒng)初始化階段和搜索階段。系統(tǒng)初始化階段包括系統(tǒng)初始化算法和數(shù)據(jù)加密算法。系統(tǒng)初始化算法由數(shù)據(jù)擁有者運行，用來生成系統(tǒng)的公開參數(shù)和數(shù)據(jù)擁有者的私鑰?；诜菍ΨQ密鑰的密文搜索算法，公開參數(shù)也包括數(shù)據(jù)擁有者的公鑰。數(shù)據(jù)加密算法由數(shù)據(jù)擁有者運行，用來生成加密的可搜索的數(shù)據(jù)結(jié)構(gòu)（EDB，encryption database）和加密后的文件。在基于索引的方案中，還包括生成加密后的索引。

圖1 物聯(lián)網(wǎng)搜索隱私保護框架

圖2 基于密文搜索的物聯(lián)網(wǎng)隱私保護

在搜索階段，數(shù)據(jù)搜索者要求物聯(lián)網(wǎng)搜索服務(wù)提供者返回和某個指定搜索條件相關(guān)的所有加密文件，主要包括陷門生成算法和數(shù)據(jù)搜索算法。當(dāng)數(shù)據(jù)搜索者搜索數(shù)據(jù)時，首先向數(shù)據(jù)擁有者提交搜索請求，然后數(shù)據(jù)擁有者運行陷門生成算法生成陷門，陷門包含搜索條件信息但不能泄露搜索條件的任何信息。物聯(lián)網(wǎng)搜索服務(wù)提供者運行數(shù)據(jù)搜索算法利用該陷門和EDB，逐一驗證密文或索引是否滿足指定的搜索條件，并返回相應(yīng)的密文或者索引給數(shù)據(jù)搜索者。最后，數(shù)據(jù)搜索者使用密鑰解密密文獲得搜索結(jié)果。

如果物聯(lián)網(wǎng)搜索服務(wù)提供者后臺系統(tǒng)存儲的數(shù)據(jù)都以密文的形式存在，就可以很大程度上避免數(shù)據(jù)擁有者的隱私泄露，除非使用的加密算法遭到攻擊。然而在這種情況下，必須保證物聯(lián)網(wǎng)搜索服務(wù)的可用性和效率，所以基于密文搜索的隱私保護技術(shù)的關(guān)鍵在于確保數(shù)據(jù)隱私的同時，設(shè)計安全、運行效率高且允許對數(shù)據(jù)進行復(fù)雜搜索的密文搜索算法。物聯(lián)網(wǎng)密文搜索方案應(yīng)該滿足2個基本要求：方案生成的加密EDB不應(yīng)該泄露用戶DB的任何信息；用戶生成的陷門不應(yīng)該泄露有關(guān)搜索條件的任何信息給服務(wù)提供者。

3.2 現(xiàn)有密文搜索方案分類

現(xiàn)有的密文搜索方案依據(jù)采用的加密算法分為基于對稱密鑰的密文搜索（SSE，searchable symmetric encryption）方案和基于非對稱密鑰的密文搜索（PEKS，public encryption keyword search）方案。

3.2.1 SSE方案

依據(jù)構(gòu)建策略，SSE主要分為基于順序掃描的方案和基于安全索引的方案。其中，后者分為基于正向索引和基于反向索引構(gòu)建的方案。

基于順序掃描的SSE方案由Song等[5]于2000年首次提出，該方案把明文劃分為“單詞”并對其加密，然后當(dāng)用戶提交搜索請求時，通過對整個密文文件順序掃描，比較密文單詞和待檢索關(guān)鍵字，返回包含關(guān)鍵字的密文文件。優(yōu)點在于支持對文件中任意單詞的搜索，缺點在于搜索時需要服務(wù)器遍歷整個文件，因此效率極低，也使其無法應(yīng)用在實際場景中，且該方案無法抵抗對密文的頻率分析攻擊。

Goh[6]提出了基于安全正向索引的SSE方案，搜索時由服務(wù)器對每個文件的安全索引進行關(guān)鍵字匹配搜索。優(yōu)點在于，相比Song[5]的方案，該方案能以較高效率支持用戶的關(guān)鍵字搜索。但是由于構(gòu)建索引所使用的 Bloom Filter本身存在正向誤檢概率，使搜索結(jié)果不完全正確，可能給用戶帶來一些額外的帶寬開銷和計算開銷。該方案的安全性達到選擇關(guān)鍵詞攻擊下的不可區(qū)分性安全目標(biāo)IND-CKA。

Chang等[7]的方案避免了Goh方案的正向誤檢概率，使用倒排索引構(gòu)建方法，其抗選擇關(guān)鍵字攻擊能力也比Goh方案強，可以抗自適應(yīng)選擇關(guān)鍵字攻擊。Curtmola等[8]進一步改進并明確定義了SSE方案的安全性，提出在自適應(yīng)和非自適應(yīng)模型下達到不可區(qū)分性安全的SSE-1和SSE-2方案。該方案也是采用倒排索引構(gòu)建，搜索操作只需要 O(1)時間，然而文件的添加和刪除操作需要重新構(gòu)建索引，時間開銷大。

3.2.2 PEKS方案

Boneh等[9]提出了PEKS方案，并基于雙線性對給出了幾種構(gòu)造方案。Abdalla等[10]進一步提出PEKS方案的完整定義，同時給出了基于身份匿名方案構(gòu)造 PEKS的流程。文獻[11～13]針對文獻[9]方案需要使用安全通道的問題，分別設(shè)計了在隨機預(yù)言模型下[11,12]和標(biāo)準(zhǔn)模型下[13]不需要安全通道的PEKS方案。文獻[13,14]提出了基于身份加密方案的PEKS方案。

3.3 目前研究方向

目前，基于數(shù)據(jù)加密的搜索技術(shù)的主要研究方向有3個方面。

1) 支持搜索方式的擴展。以上所述方案大多只支持單一關(guān)鍵字搜索，而后續(xù)的很多方案對搜索方式進一步擴展，包括支持多關(guān)鍵字搜索[15～20]、子集搜索[21]、模糊搜索[17,18,22～24]、排序搜索[19,20,25]、范圍查詢[26]的方案。這些擴展都是基于關(guān)鍵字搜索的方式，而物聯(lián)網(wǎng)搜索方式更加復(fù)雜，因此，亟需構(gòu)建支持復(fù)雜搜索方式的密文搜索方案。

2) 支持對服務(wù)器存儲的密文文件的動態(tài)添加、更新或刪除[27～31]。如何設(shè)計高效的支持?jǐn)?shù)據(jù)實時更新的密文搜索方案，適應(yīng)物聯(lián)網(wǎng)搜索數(shù)據(jù)的高度動態(tài)性，是一個非常大的挑戰(zhàn)。

3) 搜索效率的提升，此方面主要是通過減少雙線性對使用的頻率或者使用其他技術(shù)替代雙線性對來構(gòu)造密文搜索方案[32,33]?？偟膩砜?，SSE搜索效率高，但同PEKS相比，靈活性和可擴展性較低，不適用于物聯(lián)網(wǎng)搜索場景。而PEKS現(xiàn)有方案大多使用雙線性對操作，使搜索效率大大降低。因此，研究適用于物聯(lián)網(wǎng)搜索的高效密文搜索方案及其重要。

4 基于訪問控制的數(shù)據(jù)隱私保護技術(shù)

4.1 總述

訪問控制可以避免濫用物聯(lián)網(wǎng)搜索服務(wù)導(dǎo)致的隱私泄露。傳統(tǒng)的訪問控制模型假設(shè)用戶和服務(wù)器處于同一個信任域中，大多假設(shè)服務(wù)提供者是可信的，由服務(wù)提供者來進行授權(quán)，訪問控制粒度也比較粗，無法為訪問控制策略提供豐富的語義支持，因而并不適用物聯(lián)網(wǎng)搜索大規(guī)模的、復(fù)雜的、動態(tài)的、多安全域的訪問控制。而基于屬性加密（ABE，attribute based encryption）的方案能確保物聯(lián)網(wǎng)搜索服務(wù)提供者只允許具有特定屬性的用戶搜索其需要的實體相關(guān)信息。

ABE方案首先由 Sahai 和 Waters提出[34]，最初是為了改善基于生物信息的身份加密系統(tǒng)的容錯性能。采用（t，n）門限訪問結(jié)構(gòu)，分別提出了適用于小規(guī)模屬性全集和大規(guī)模屬性全集的方案，并給出了在選擇身份安全模型下的安全性證明。ABE方案通常包括3個參與者，屬性權(quán)威、數(shù)據(jù)擁有者和數(shù)據(jù)使用者。屬性權(quán)威主要用來生成密鑰和驗證數(shù)據(jù)使用者屬性或者策略。如圖3所示，ABE方案分為4個階段，初始化階段、密鑰生成階段、加密階段和解密階段。在加密階段，屬性權(quán)威生成一對主私鑰和公鑰，隨后把公鑰分發(fā)給數(shù)據(jù)擁有者和數(shù)據(jù)使用者。在密鑰生成階段，屬性權(quán)威基于數(shù)據(jù)使用者的請求生成私鑰并發(fā)送給數(shù)據(jù)使用者。而加密算法和解密算法由數(shù)據(jù)擁有者和數(shù)據(jù)使用者分別運行。

命題2.5 設(shè)是偽BCI-代數(shù)X的猶豫模糊濾子，則存在X的猶豫模糊反群濾子使得對任意γ ∈ P([0,1]),有 ?

圖3 ABE方案

4.2 現(xiàn)有ABE方案分類

ABE方案依據(jù)訪問策略的實現(xiàn)方式不同分為2類[34]，基于屬性的密鑰策略加密方案（KP-ABE，key policy attribute based encryption）和基于屬性的密文策略加密方案（CP-ABE，ciphertext policy attribute based encryption）。兩者的主要區(qū)別在于訪問策略關(guān)聯(lián)的載體不同，前者是密鑰和訪問策略相關(guān)聯(lián)，后者則是密文和訪問策略相關(guān)聯(lián)。CP-ABE的解密算法通常包括2個階段，將訪問策略轉(zhuǎn)化成訪問樹和將訪問樹嵌入數(shù)據(jù)中并加密。而且，由于ABE方案相對于對稱加密方案來說開銷非常大，因此，通常的做法都是使用 ABE方案來加密對稱密鑰，如高級加密（AES，advanced encryption standard）協(xié)議密鑰，然后使用AES協(xié)議來加密實際數(shù)據(jù)。由于 CP-ABE中數(shù)據(jù)擁有者擁有訪問策略制定的權(quán)力，一個密文可以由多個不同的密鑰進行解密，訪問控制策略改變時只需根據(jù)新的訪問控制策略重新加密密文，密鑰管理開銷較小等特點，更適用于物聯(lián)網(wǎng)搜索場景下的基于訪問控制的隱私保護。

4.2.1 KP-ABE方案

Goyal等[35]通過引入訪問樹結(jié)構(gòu)，提出了一個細粒度訪問控制的KP-ABE 方案。該方案可以支持任意單調(diào)的包含與門、或門以及門限門的訪問控制公式，增強了策略的邏輯表達能力，并證明了在選擇身份安全模型下的安全性。Ostrovsky[36]方案支持非門，完善了文獻[35]中訪問策略的邏輯表達能力，構(gòu)成了一個完整的邏輯表達系統(tǒng)，且支持非單調(diào)的訪問結(jié)構(gòu)。Lewko等[37]進一步改進了Ostrovsky的方案，實現(xiàn)了高效的用戶權(quán)限撤銷。以上CP-ABE方案中密文大小隨密文屬性數(shù)目線性增長，Attrapadung等[38]使密文大小為常數(shù)級，但卻導(dǎo)致了密鑰大小為屬性數(shù)目的平方級。

4.2.2 CP-ABE方案

Bethencourt等[39]提出了訪問結(jié)構(gòu)為單調(diào)訪問樹的 CP-ABE方案。Cheung等[40]提出了一種可證安全的CP-ABE方案，并證明了標(biāo)準(zhǔn)模型下的安全性，但其訪問策略僅支持與門，密文和密鑰大小隨屬性線性增長。Goyal[41]和Liang[42]都采用了有界樹作為訪問結(jié)構(gòu)。文獻[41]在標(biāo)準(zhǔn)模型下證明了其安全性，支持任何訪問控制公式，改進了文獻[39]方案只支持單調(diào)的訪問結(jié)構(gòu)和安全性證明是基于雙線性群模型的不足。Ibraimi等[43]使用通用訪問樹構(gòu)造了CP-ABE方案，降低了開銷，對于資源有限的設(shè)備是很有意義的。2013年，Waters等[44]提出了具有完全表達能力的CP-ABE方案，但是安全性證明是在群通用模型下完成的。Lewko等[45]利用文獻[44]中的編碼技術(shù)提出了達到適應(yīng)性攻擊安全的 ABE方案，但是其實際性能相比文獻[44]有所降低。以上方案都是基于雙線性對構(gòu)造的，Zhang等[46]提出了基于n元格構(gòu)造的支持與門的CP-ABE方案，盡管其性能不高，但是其對于不使用雙線性對相關(guān)假設(shè)來構(gòu)造ABE方案是有意義的。

Attrapapdung等[47]將KP-ABE方案和CP-ABE方案組合，提出了雙策略 ABE方案。它也可以根據(jù)實際需要轉(zhuǎn)換成單個策略的 KP-ABE方案或CP-ABE方案，并基于判定雙線性 Diffie-Hellman指數(shù)困難問題證明了安全性。

4.3 目前研究方向

目前，ABE 的主要研究方向有4個方面。

1) 支持多個密鑰授權(quán)中心（KDC）的ABE方案[48～53]，與只支持單個KDC的ABE方案相比，其允許多個獨立的 KDC對屬性和分發(fā)的密鑰進行監(jiān)督，分散了 KDC的權(quán)利，更適合于物聯(lián)網(wǎng)搜索對象和搜索空間廣泛性的實際應(yīng)用場景。

2) 支持靈活的細粒度的訪問控制策略表示的ABE方案[54]，主要研究如何支持策略屬性的靈活變更、用戶屬性的靈活變更，密鑰管理如何更好地支持策略屬性和用戶屬性發(fā)生變更以及如何設(shè)計更為細粒度的訪問控制。

4) 基于屬性的訪問控制和密文搜索相結(jié)合[60～63]。Sun 等[60]和 Han 等[61]分別提出了基于屬性的密文搜索方案（ABEKS，attribute based encryption with keyword search），其都是基于關(guān)鍵字密文搜索，搜索的范圍相對于密文內(nèi)容搜索存在較大的局限性，無法滿足密文信息的搜索需求，且泄露了包含搜索關(guān)鍵詞的文件數(shù)量，其使用 KP-ABE的特性也不適用于物聯(lián)網(wǎng)搜索場景。相比文獻[61]，Kaci等[63]的方案只需解密授權(quán)訪問的密文，效率大為提升，同時避免了泄露包含搜索關(guān)鍵字的文件數(shù)量，并在文獻[62]中進一步改進，使用KP-ABE和CP-ABE這2種策略完成訪問控制，使用高性能計算來加速搜索效率。ABEKS對于物聯(lián)網(wǎng)搜索數(shù)據(jù)隱私保護來說是值得研究的方向。

5 基于隱藏訪問模式的隱私保護技術(shù)

5.1 總述

密文搜索技術(shù)可以確保物聯(lián)網(wǎng)搜索服務(wù)提供者返回給用戶請求的搜索數(shù)據(jù)內(nèi)容的機密性，很大程度上保證了用戶數(shù)據(jù)信息的隱私性，但是卻無法確保用戶訪問模式的機密性，而訪問模式通常也蘊含了用戶的隱私信息，已成為泄露用戶隱私的一種潛在途徑。文獻[64]指出，用戶的訪問模式會泄露加密文件的信息，基于頻率統(tǒng)計的攻擊方式，利用訪問模式成功地推斷出關(guān)于一個加密郵件庫搜索的概率大約為 80%。文獻[65]指出可以通過訪問模式獲得用戶隱私信息。由此可見，在物聯(lián)網(wǎng)搜索中，隱藏用戶的訪問模式對于保護用戶數(shù)據(jù)隱私是十分必要的。

隱私信息檢索（PIR，private information retrieval）[66]和隱藏隨機訪問模式（ORAM，oblivious random access machine）技術(shù)是隱藏訪問模式最主要的2種方法。PIR協(xié)議將用戶的查詢請求通過一個矩陣變換構(gòu)造出N?1個與其不可區(qū)分的偽查詢，使攻擊者對用戶的真實意圖無法準(zhǔn)確把握，從而實現(xiàn)在數(shù)據(jù)搜索平臺上用戶訪問模式的匿名?；谛畔⒗碚摰腜IR協(xié)議需要假設(shè)服務(wù)器非合謀，因此不適用物聯(lián)網(wǎng)搜索應(yīng)用場景；而基于計算理論的PIR協(xié)議服務(wù)提供者通常需要做大量復(fù)雜的運算，開銷很大，目前在物聯(lián)網(wǎng)搜索的數(shù)據(jù)隱私保護中主要用于和ORAM方案相結(jié)合[67,68]。

ORAM技術(shù)最早由Goldreich和Ostrovsky[69]提出，為了保護軟件版權(quán)和防止非法復(fù)制。ORAM 的目標(biāo)在于用戶從服務(wù)器讀取或向服務(wù)器寫入數(shù)據(jù)的同時，使服務(wù)器無法推測其真實的數(shù)據(jù)訪問模式。將 ORAM應(yīng)用于物聯(lián)網(wǎng)搜索服務(wù)當(dāng)中，可以使用戶使用物聯(lián)網(wǎng)搜索服務(wù)同時，確保物聯(lián)網(wǎng)服務(wù)提供者甚至惡意的攻擊者無法獲得其用戶搜索結(jié)果的相關(guān)信息和用戶的訪問模式信息。

如圖4所示，ORAM通過對數(shù)據(jù)進行冗余讀/寫操作和動態(tài)改變數(shù)據(jù)存儲位置的方式來隱藏訪問模式。每次訪問請求都需經(jīng)過冗余處理成一系列讀寫操作，使除數(shù)據(jù)訪問者之外的服務(wù)器和攻擊者都無法區(qū)分訪問請求。而每次訪問請求執(zhí)行之后，都會動態(tài)改變數(shù)據(jù)存儲的位置。一個典型的ORAM方案包含2個參與者：數(shù)據(jù)訪問者和服務(wù)器。設(shè)計一個ORAM（setup、read、write）方案需要考慮3個子協(xié)議：系統(tǒng)建立協(xié)議、讀協(xié)議、寫協(xié)議。在系統(tǒng)建立階段，需要設(shè)計服務(wù)器和用戶端的數(shù)據(jù)結(jié)構(gòu)，ORAM方案構(gòu)造服務(wù)器存儲的數(shù)據(jù)結(jié)構(gòu)，初始化數(shù)據(jù)結(jié)構(gòu)，生成密鑰。讀/寫協(xié)議在用戶執(zhí)行虛擬IO數(shù)據(jù)塊的讀/寫操作時觸發(fā)。由于ORAM必須使服務(wù)器不能區(qū)分用戶是在執(zhí)行讀操作還是寫操作，讀協(xié)議和寫協(xié)議通常實現(xiàn)相同。在大部分ORAM方案中，讀協(xié)議和寫協(xié)議用同一個算法描述。因此ORAM方案通常包含2個算法協(xié)議，即系統(tǒng)建立算法和訪問算法，分別用setup和access（operation，address，value）表示。為了達到訪問后的隱藏性，還可能包含一個洗牌（shuffle）算法。將ORAM方案和密文搜索方案相結(jié)合，可以直接用讀和寫協(xié)議來模擬順序搜索算法中的搜索操作，也可以通過構(gòu)造2個ORAM結(jié)構(gòu)分別支持對索引和文件集的隱藏訪問模式搜索。

圖4 ORAM方案

5.2 現(xiàn)有ORAM方案分類

根據(jù)服務(wù)器端是否需要進行讀寫之外的其他操作，將ORAM方案分為經(jīng)典ORAM方案和現(xiàn)代ORAM方案。而后者由于可以利用物聯(lián)網(wǎng)搜索后臺強大的計算能力，因此更適用。

5.2.1 經(jīng)典ORAM方案

經(jīng)典ORAM方案主要包括平方根ORAM方案[69]、分層ORAM方案[69]和樹ORAM方案[70]。其中，分層方案也可以看作是平方根方案的改進，僅是采用分層方法代替平方根中的緩存。而樹方法可以看作是分層方案的分層改進，通過將重組開銷分配到每次數(shù)據(jù)訪問操作，降低了洗牌操作帶來的最差情況下的開銷。

1) 平方根ORAM方案

平方根ORAM方案由Goldreich和Ostrovsky[69]提出。數(shù)據(jù)存儲結(jié)構(gòu)如圖5所示，N為實際數(shù)據(jù)單元的總個數(shù)，將服務(wù)器所需的存儲空間分為2個部分，分別記為main_part和shelter，其中，main_part包含一個由N個真實數(shù)據(jù)D1,…,DN和個虛擬數(shù)據(jù)元素M1, M2, …,M組成的偽隨機排列，shelter用來存儲最近個查詢結(jié)果。分?jǐn)傂阅転镺(log2N)，最壞情況下的性能為O(N)。

圖5 平方根ORAM數(shù)據(jù)存儲結(jié)構(gòu)

2) 分層ORAM方案

分層ORAM方案由Goldreich和Ostrovsky[69]提出。數(shù)據(jù)存儲結(jié)構(gòu)如圖6所示，由一個多層的桶式散列表[H1,H2,…,Hn]組成，其中，n=O(logN)，Hi層由 2i個桶組成，每個桶包含的數(shù)據(jù)單元個數(shù)為O(logN)，Hi和一個普通散列函數(shù) hi相關(guān)聯(lián)。數(shù)據(jù)單元的位置由 HLocation=hi(v)決定，將虛擬地址映射到散列表。分?jǐn)傞_銷最優(yōu)為O(log3N)，但隱藏的常數(shù)比較大，至少為 6 100，最壞情況下開銷為O(Nlog2N)。相比平方根算法，分?jǐn)傂阅苡兴岣撸亲顗那闆r的性能和服務(wù)器存儲復(fù)雜度都有所增加。

圖6 分層ORAM數(shù)據(jù)存儲結(jié)構(gòu)

Williams等[71]首次在 ORAM 實用性方面做出探索，通過增加用戶端存儲開銷來改進洗牌階段的隱藏歸并算法，使用戶端存儲開銷增加到 O()的情況下，分?jǐn)傞_銷降低到O(log2N)。文獻[72]進一步改進了分層算法，通過在每一分層引入加密Bloom過濾器[72]檢測數(shù)據(jù)元素是否存在該層，使分?jǐn)傞_銷降低為O(log N log log N)。

Pinkas[4]指出文獻[72]的實際開銷要高得多，并使用Cuckoo散列[74]來構(gòu)造ORAM，在不增加用戶端存儲開銷的情況下使分?jǐn)傞_銷降低到O(log2N)，最差情況下的開銷為O(N log N)。

文獻[75,76]的 GM、KLO12[77]、GMOT12[78]指出PR模型由于使用Cuckoo散列函數(shù)不夠嚴(yán)謹(jǐn)，在某些情況下，服務(wù)器能以高概率獲知用戶的訪問模式。并給出了解決方案。GMOT11a[79]將開銷進一步分?jǐn)?，使最壞情況下的開銷等于分?jǐn)傞_銷。

文獻[80]提出了一種平方根和分層方法混合的構(gòu)造方法，允許各層洗牌操作和虛擬 IO操作并發(fā)執(zhí)行。且第一次對在線開銷和離線開銷做出定義，在分?jǐn)傞_銷為O(N)的情況下，使在線開銷為O(1)。

文獻[81]把服務(wù)器端的ORAM分區(qū)劃分為若干小ORAM分區(qū)，并采用背景淘汰算法將洗牌操作均攤到每次用戶訪問操作中，使分?jǐn)傞_銷在20～35，而用戶的存儲空間僅是存儲空間大小的0.01%～0.3%。

3) 樹ORAM

前述方案洗牌階段是算法的瓶頸，客戶在訪問服務(wù)器時會因洗牌而阻塞。為了避免洗牌過程，Shi等[70]提出了基于二叉樹構(gòu)造的 ORAM 方案，使算法的復(fù)雜度和效率都大大提升。在該方案中，服務(wù)器端的數(shù)據(jù)存儲結(jié)構(gòu)如圖7所示，二叉樹的每個節(jié)點都是一個數(shù)據(jù)桶，每個數(shù)據(jù)桶都是一個完整的ORAM，包含O(log N)個數(shù)據(jù)塊。用戶端的數(shù)據(jù)存儲結(jié)構(gòu)為一個索引表，標(biāo)明數(shù)據(jù)塊到葉子節(jié)點的映射。當(dāng)用戶進行數(shù)據(jù)訪問時，用戶從索引表中查找該數(shù)據(jù)塊對應(yīng)的葉子節(jié)點，進而獲得一條包含該數(shù)據(jù)塊的從葉子節(jié)點到根節(jié)點的路徑，服務(wù)器依次返回該路徑上所有節(jié)點的每個桶的所有數(shù)據(jù)塊。然后用戶通過解密數(shù)據(jù)塊，可以獲得想要訪問的數(shù)據(jù)內(nèi)容。在用戶訪問數(shù)據(jù)之后，為了保證服務(wù)器端數(shù)據(jù)存儲的隨機性，用戶將要訪問的數(shù)據(jù)塊重新加密，并更新索引表，以新的路徑存儲到服務(wù)器。最優(yōu)性能可以達到分?jǐn)傞_銷和最壞情況下的開銷均為O(log2N)。

圖7 樹ORAM存儲結(jié)構(gòu)

Path ORAM基于二叉樹的思想，把基于樹的方法和分區(qū)思想[82]相結(jié)合，使分?jǐn)傞_銷最優(yōu)為O(log N)，但沒有對安全性進行形式化證明。后期有很多方案對Path ORAM 改進，并給出形式化的安全證明[70,83]。MMBC14[84]討論了如何使樹ORAM可變尺寸。文獻[83,85～88]都基于樹做了一些簡化和改進。

5.2.2 現(xiàn)代ORAM方案

經(jīng)典的 ORAM 方案在計算算法復(fù)雜性時不考慮加解密數(shù)據(jù)的復(fù)雜性。而加解密操作都由用戶完成，因此保證了數(shù)據(jù)的安全性，數(shù)據(jù)加解密操作的數(shù)量不僅會增加用戶的負擔(dān)，服務(wù)提供者也無法發(fā)揮高性能搜索的好處，尤其對于物聯(lián)網(wǎng)搜索應(yīng)用，后臺系統(tǒng)通常是基于云計算的平臺，其具有強大的計算能力。而分?jǐn)傞_銷是衡量 ORAM 性能的一個最重要因素，現(xiàn)代 ORAM 方案通過利用服務(wù)端強大的計算能力打破了 Goloreich等[69]對分?jǐn)傞_銷的限制，可以將分?jǐn)傞_銷降低到常數(shù)級。由于服務(wù)器執(zhí)行額外操作，就必須考慮服務(wù)器是否按預(yù)定方式執(zhí)行，這使威脅模型變?yōu)閻阂饽Ｐ?。根?jù)服務(wù)器執(zhí)行的額外操作種類分為2類。

1) 矩陣乘或者XOR操作

Stefanov[82]使用服務(wù)器執(zhí)行矩陣乘操作來降低分?jǐn)傞_銷，最優(yōu)性能是分?jǐn)傞_銷為 20～35倍。Oblivistore[89]改進了文獻[82]，通過并行執(zhí)行讀寫操作和隱藏調(diào)度算法使分?jǐn)傞_銷進一步降低到18～26倍。Burst ORAM[90]改進了Oblivistore，通過優(yōu)先執(zhí)行在線IO降低了用戶請求的在線開銷。Ring ORAM[91]吸取了SSS和Path ORAM的技術(shù)，通過調(diào)節(jié)參數(shù)使其既適用于用戶存儲開銷小的應(yīng)用，又適用于用戶存儲開銷大的應(yīng)用。SR-ORAM[92]將交互復(fù)雜度降低到O(1)。

2) 加同態(tài)或者全同態(tài)

Path-PIR[68]、OS-PIR[67]、KT-ORAM[93]允許服務(wù)器使用加同態(tài)加密。Path-PIR把基于樹的ORAM和PIR相結(jié)合，但沒有明確說明在惡意模型下的安全性。KT-ORAM使用多叉樹來替代二叉樹，進一步降低了分?jǐn)傞_銷。OS-PIR進一步改進了Oblivistore，將其與 PIR結(jié)合，使分?jǐn)傞_銷是Oblivistore的一半。將PIR作為一個黑盒子使用，因此可以使用任何PIR方案。

VOS[94]、O-ORAM[81]、Onion-ORAM[95]、C-ORAM[96]服務(wù)器執(zhí)行全同態(tài)加密或者 Somewhat同態(tài)加密操作。O-ORAM使用多叉樹，只在半誠實模型下安全。VOS使在數(shù)據(jù)塊大小較大的情況下，分?jǐn)傞_銷為常數(shù)級，服務(wù)器增加的開銷為多項式對數(shù)級，交互輪數(shù)復(fù)雜度為常數(shù)級。Onion-ORAM達到了最優(yōu)常數(shù)級分?jǐn)傞_銷和交互輪數(shù)復(fù)雜度。C-ORAM在Onion-ORAM的基礎(chǔ)上，優(yōu)化了淘汰算法，進一步減少了服務(wù)器端的計算開銷，放寬了Onion-ORAM對數(shù)據(jù)塊大小的限制，從O(log6N)到O(log4N)，但是只分析了半誠實模型下的安全。

5.3 目前研究方向

目前，有些方案的分?jǐn)傞_銷已經(jīng)達到了常數(shù)級，但并不是所有達到常數(shù)級的方案都可以在實際中應(yīng)用，仍然有一些限制，比如對數(shù)據(jù)分塊大小的限制，數(shù)據(jù)塊大小較小時，實踐性能比較差。這就使 ORAM 方案還無法完全應(yīng)用于通常意義上的物聯(lián)網(wǎng)搜索。然而，這些方案仍然是有意義的。且在具體應(yīng)用中需對安全和效率做出均衡，是否需要達到隱藏訪問模式這樣的高安全保障也要視具體場景而言。

ORAM目前主要研究方向包括：使用并行算法來降低分?jǐn)傞_銷；使用服務(wù)器端運算來降低用戶端開銷和分?jǐn)傞_銷；構(gòu)建不需要額外假設(shè)或者不需要FHE可驗證的ORAM方案。

6 結(jié)束語

從物聯(lián)網(wǎng)搜索服務(wù)提供者可能發(fā)生的數(shù)據(jù)窺探、攻擊者濫用搜索服務(wù)、結(jié)合搜索訪問模式挖掘用戶數(shù)據(jù)導(dǎo)致的數(shù)據(jù)隱私泄露等角度出發(fā)，梳理了當(dāng)前適用于物聯(lián)網(wǎng)搜索數(shù)據(jù)隱私保護相關(guān)關(guān)鍵技術(shù)。但總體上說，當(dāng)前國內(nèi)外針對物聯(lián)網(wǎng)搜索數(shù)據(jù)隱私保護的相關(guān)研究和進展還不充分，還存在許多問題，有待進一步研究。

1) 在物聯(lián)網(wǎng)搜索服務(wù)使用權(quán)限方面，研究適用于物聯(lián)網(wǎng)搜索的訪問控制和授權(quán)機制，從物聯(lián)網(wǎng)搜索服務(wù)用戶的身份、行為、興趣、位置、敏感度、時空等維度，結(jié)合物聯(lián)網(wǎng)搜索服務(wù)的搜索種類，綜合考慮設(shè)計動態(tài)、細粒度的訪問控制機制，同時保證必要的追責(zé)，才能確保用戶可以放心地使用物聯(lián)網(wǎng)搜索服務(wù)。同時亟需建立隱私度量模型，量化隱私與服務(wù)的平衡，從而為物聯(lián)網(wǎng)搜索訪問控制模型決策提供支撐。

2) 現(xiàn)有的隱私保護技術(shù)或者支持靜態(tài)數(shù)據(jù)集，或者支持動態(tài)數(shù)據(jù)集的效率不高。而在物聯(lián)網(wǎng)搜索場景中，數(shù)據(jù)無時無刻不在變化，包括數(shù)據(jù)表現(xiàn)形式的改變、屬性的增減、新數(shù)據(jù)加入、舊數(shù)據(jù)刪除等，怎樣在物聯(lián)網(wǎng)搜索復(fù)雜的應(yīng)用環(huán)境中同時實現(xiàn)對動態(tài)數(shù)據(jù)的搜索和隱私保護，是一個更具挑戰(zhàn)的難題。

3) 現(xiàn)有的支持搜索的隱私保護技術(shù)，搜索的條件主要是基于關(guān)鍵字的搜索，因此，研究支持物聯(lián)網(wǎng)復(fù)雜搜索條件的隱私保護模型和應(yīng)用或?qū)?fù)雜搜索條件合理轉(zhuǎn)換成基于關(guān)鍵字的搜索十分必要。

4) 研究將基于數(shù)據(jù)加密的搜索技術(shù)和基于屬性加密的訪問控制技術(shù)有機結(jié)合，使數(shù)據(jù)擁有者能在最大限度地控制數(shù)據(jù)使用權(quán)的同時，實現(xiàn)物聯(lián)網(wǎng)搜索的數(shù)據(jù)隱私保護。

5) 對于使用ORAM技術(shù)來隱藏物聯(lián)網(wǎng)搜索模式，主要關(guān)注分?jǐn)傂阅?、交互式?fù)雜度、用戶端開銷幾個重要性能衡量指標(biāo)，因此，研究構(gòu)造這幾個性能指標(biāo)均衡的 ORAM 方案對于保護物聯(lián)網(wǎng)搜索數(shù)據(jù)隱私是非常重要的研究方向。

只有綜合考慮上述幾個方面，形成整體的解決方案，才能有效保護物聯(lián)網(wǎng)搜索數(shù)據(jù)擁有者和數(shù)據(jù)搜索者的權(quán)益和隱私，促進物聯(lián)網(wǎng)搜索服務(wù)的有序健康發(fā)展。

[1] ATZORI L, IERA A, MORABITO G. The internet of things: a survey[J]. Computer Networks, 2010, 54(15): 2787-2805.

[2] OSTERMAIER B, ROMER K, MATTERN, et al．A real-time search engine for the web of things[C]//Internet of Things. Tokyo, Japan,2010:1-8.

[3] BODENHEIM R, BUTTS J, DUNLAP S. Evaluation of the ability of the Shodan search engine to identify Internet-facing industrial control devices[J]. International Journal of Critical Infrastructure Protection,2014, 7(2): 114-123.

[4] PINKAS B, REINMAN T. Oblivious RAM revisited[C]//International Cryptology Conference. California, USA, 2010:502-519.

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

[6] GOH E. Secure indexes[R]. IACR ePrint Cryptography Archive, 2003.http://eprint.iacr.org/2003/216.

[7] CHANG Y, MITZENMACHER M. Privacy preserving keyword searches on remote encrypted data[C]//The Applied Cryptography and Network Security. New York, USA, 2005:442-455.

[8] CURTMOLA R, GARAY J, KAMARA S, et al. Searchable symmetric encryption: Improved definitions and efficient constructions[C]//The 13th ACM Conference on Computer and Communications Security(CCS 2006). New York, USA, 2006:79-88.

[9] BONEH D, CRESCENZO G D, OSTROVSKY R. Public key encryption with keyword search[C]//EUROCRYP’04. Interlaken, Switzerland,2004:71-82.

[10] ABDALLA M, BELLARE M, CATALANO D. Searchable encryption revisited: consistency properties, relation to anonymous IBE, and extensions[C]//CRYPTO’05. California, USA, 2005:350-391.

[11] BAEK J, SAFAVI-NAINI R, SUSILO W. Public key encryption with keyword search revisited[C]//The International Conference on Computational Science and Applications (ICCSA 2008). Perugia, Italy,2008:1249-1259.

[12] RHEE H S, PARK J H, SUSILO W, et al. Improved searchable public key encryption with designated tester[C]//Symposium on Information,Computer and Communications Security(ASIACCS 2009). New York,USA, 2009:376-379.

[13] FANG L, SUSILO W, GE C, et al. A secure channel free public key encryption with keyword search scheme without random oracle[C]//The Cryptology and Network Security (CANS 2009). Ishikawa,Japan, 2009:248-258.

[14] KERSCHBAUM F, SORNIOTTI A. Searchable encryption for outsourced data analytics[C]//The 7th European Conference on Public Key Infrastructures, Services and Applications (EuroPKI'10). Athens,Greece, 2010:61-76.

[15] CAO N, WANG C, REN K. Privacy-preserving multi-keyword ranked search over encrypted cloud data[C]//IEEE INFOCOM. Shanghai,China, 2011:222-233.

[16] SUN W, WANG B, CAO N. Verifiable privacy-preserving multi-keyword text search in the cloud supporting similarity-based ranking[C]//ACM ASIACCS. Hangzhou, China, 2013:3025-3035.

[17] CHUAH M, HU W. Privacy-aware bedtree based solution for fuzzy multi-keyword search over encrypted data[C]//International Conference on Distributed Computing Systems Workshops. Minnesota, USA,2011:273-281.

[18] WANG B, YU S, LOU W. Privacy-preserving multi-keyword fuzzy search over encrypted data in the cloud[C]//IEEE INFOCOM. Toronto,Canada, 2014:2112-2120.

[19] MASHAURI D, LI R, HAN H. Adaptive multi-keyword ranked search over encrypted cloud data[C]//International Conference, Collaborate Computing 2015. Wuhan, China, 2015:829-837.

[20] SUN X, WANG X, XIA Z. Dynamic multi-keyword top-k ranked search over encrypted cloud data[J]. International Journal of Security and its Applications, 2014,8(1):319-332.

[21] BONEH D, WATERS B. Conjunctive, subset, and range queries on encrypted data[C]//Proceedings of TCC. New South Wales, Australia,2007:535-554.

[22] SUN W, WANG B, CAO N. Verifiable privacy-preserving multi-keyword text search in the cloud supporting similarity-based ranking[J]. IEEE Transactions on Parallel and Distributed Systems,2014, 25(11): 3025-3035.

[23] LI J, WANG Q, WANG C. Fuzzy keyword search over encrypted data in cloud computing[C]//IEEE INFOCOM. CA, USA, 2010:1-5.

[24] MARK G, BROST G. K-word proximity search on encrypted data[C]//The 30th International Conference on Advanced Information Networking and Applications Workshops. Crans-Montana, Switzerland, 2016:365-372.

[25] WANG C, CAO N, REN K. Enabling secure and efficient ranked keyword search over outsourced cloud data[J]. IEEE Transactions on Parallel and Distributed Systems (TPDS), 2011,23(8):1467-1749.

[26] SHI E, BETHENCOURT V, CHAN H. Multi-dimensional range query over encrypted data[C]//IEEE Symposium on Security and Privacy.California, USA, 2007:350-364.

[27] KAMARA S, PAPAMANTHOU C. Parallel and dynamic searchable symmetric encryption[C]//Financial Cryptography and Data Security(FC). Okinawa, Japan, 2013:258-274.

[28] KAMARA S, PAPAMANTHOU C, ROEDER T. Dynamic searchable symmetric encryption[C]//CCS. Vienna, Austria, 2012:775-780.

[29] STEFANOV E, PAPAMANTHOU C, SHI E. Practical dynamic searchable encryption with small leakage[C]//NDSS. California, USA,2014:256-272.

[30] CASH D, JAEGER J, JARECKI S, et al. Dynamic searchable encryption in very large databases: data structures and implementation[C]//Network and Distributed System Security Symposium(NDSS). California, USA, 2014:171-182.

[31] NAVEED M, PRABHAKARAN M, GUNTER C. Dynamic search-able encryption via blind storage[C]//IEEE Symposium on Security and Privacy. CA, USA, 2014:639-654.

[32] DI CRESCENZO G, SARASWAT V. Public key encryption with searchable keywords based on Jacobi symbols[C]//INDOCRYPT 2007.Chennai, India, 2007:282-296.

[33] LAI X, LU R, FOXTON K. An efficient searchable encryption scheme and its application in network forensics[C]//E-Forensics. Shanghai,China, 2010:66-78.

[34] SAHAI A, WATERS B. Fuzzy identity based encryption[C]//EUROCRYPT. Sofia, Bulgaria, 2005:674-651.

[35] GOYAL V, PANDEY O, SAHAI A. Attribute-based encryption for fine-grained access control of encrypted data[C]//The 13th ACM Conference on Computer and Communications Security (CCS). VA, USA,2006:89-98.

[36] OSTROVSKY R, SAHAI A, WATERS B. Attribute-based encryption with non-monotonic access structures[C]//14th ACM Conference on Computer and Communications Security. New York, USA, 2007:521-527.

[37] LEWKO A, SANAIS A, WATERS B. Revocation systems with very small private keys[C]//The IEEE Symposium on Security and Privacy(SP). California, USA, 2010:273-285.

[38] ATTRAPADUNG N, LIBERT B, PANAFIEU DE. Expressive key policy attribute-based encryption with constant-size ciphertexts[C]//Public Key Cryptography(PKC). Taormina, Italy, 2011:521-527.

[39] BETHENCOURT J, SAHAI A, WATERS B. Ciphertext-policy attribute-based encryption[C]//The IEEE Symposium on Security and Privacy. California, USA, 2007:90-108.

[40] CHEUNG L, NEWPORT C. Provably secure ciphertext policy ABE[C]//The 14th ACM Conference on Computer and Communications Security (CCS). New York, USA, 2007:321-324.

[41] GOYAL V, JAIN A, PANDEY O. Bounded ciphertext policy attribute based encryption[C]//International Colloquium on Automata, Languages and Programming(ICALP). Reykjavik, Iceland, 2008: 579-591.

[42] LIANG X, CAO Z, LIN H, et al. Provably secure and efficient bounded ciphertext policy attribute based encryption[C]//The 4th International Symposium on ACM Symposium on Information, Computer and Communications Security (ASIACCS). Sydney, Australia,2009:343-352.

[43] IBRAIMI L, TANG Q, HARTEL P. Efficient and provable secure ciphertext-policy attribute-based encryption schemes[C]//Information Security Practice and Experience (ISPEC). Xi'an, China, 2009:1-12.

[44] WATERS B. Ciphertext-policy attribute-based encryption: An expressive, efficient, and provably secure realization[C]//The 14th International Conference on Practice and Theory in Public Key Cryptography.Taormina, Italy, 2011:53-70.

[45] LEWKO A, OKAMOTO T, SAHAI A. Fully secure functional encryption: attribute-based encryption and (hierarchical)inner product encryption[C]//EUROCRYPT. Monaco and Nice, French Riviera,2010:33-41.

[46] ZHANG J, ZHANG Z F. A ciphertext policy attribute based encryption scheme without pairings[C]//Information Security and Cryptology(ISC). Beijing, China, 2012:324-340.

[47] ATTRAPADUNG N, IMAI H. Dual-policy attribute based encryption[C]//Applied Cryptography and Network Security. Paris-Rocquencourt,France, 2009:168-185.

[48] CHASE M. Multi-authority attribute based encryption[C]//TCC. Amsterdam, The Netherlands, 2007:333-340.

[49] BO?OVIC V, SOCEK D, STEINWANDT R. Multiauthority attribute-based encryption with honest-but-curious central authority[J].International Journal of Computer Mathematics. 2012, 89(3):268-283.

[50] CHASE M, CHOW S. Improving privacy and security in multi-authority attribute-based encryption[C]//The 16th ACM Conference on Computer and Communications Security (CCS). Chicago,USA, 2009:121-130.

[51] LEWKO A, WATERS B. Decentralizing attribute-based encryption[C]//EUROCRYPT 2011. Tallinn , Estonia, 2011:568-588.

[52] LIU Z, CAO Z, HUANG Q. Fully secure multi-authority ciphertext-policy attribute-based encryption without random oracles[C]//The European Symposium on Research in Computer Security (ESORICS).Leuven, Belgium, 2011:380-384.

[53] HAN J, SUSILO W, MU Y. Privacy-preserving decentralized key-policy attribute-based encryption[J]. IEEE Transactions on Parallel and Distributed Systems. 2012, 23(11):2150-2162.

[54] YU S, WANG C, REN K. Achieving secure, scalable, and fine-grained data access control in cloud computing[C]//IEEE INFOCOM. CA,USA, 2010:1-9.

[55] YU SC, REN K, LOU W J. Defending against key abuse attacks in KP-ABE enabled broadcast systems[C]//Security and Privacy in Communication Networks. Athens, Greece, 2009:56-74.

[56] WANG Y, CHEN K, LONG Y. Accountable authority key policy attribute-based encryption[J]. Science China: Information Sciences.2012, 55(7):1631-1638.

[57] LI J, REN K, KIM K. A2BE: accountable attribute-based encryption for abuse free access control[R]. Cryptology ePrint Archive, 2009.

[58] LI J, REN K, ZHU B. Privacy-aware attribute based encryption with user accountability[C]//12th International Conference. Pisa, Italy,2009.

[59] LI J, HUANG Q, CHEN X. Multi-authority ciphertext-policy attribute-based encryption with accountability[C]//The 6th International Symposium on Information, Computer and Communications Security(ASIACCS). Hong Kong, China, 2011:223-228.

[60] SUN W, YU S, LOU V. Protecting your right: attribute-based keyword with fine-grained owner enforced search authorization in the cloud[C]//IEEE INFOCOM. Toronto, Canada, 2014:1187-1198.

[61] HAN F, QIN J, ZHAO H. A general transformation from KP-ABE to searchable encryption[J]. Future Generation Computer Systems. 2014,30: 107-115.

[62] BOUABANATEBIBEL T, KACI A. Parallel search over encrypted data under attribute based encryption on the cloud computing[J].Computers amp; Security, 2015, 54(c):77-91.

[63] KACI A, BOUABANA-TEBIBEL T. Access control reinforcement over searchable encryption[C]//The 15th IEEE International Conference on Information Reuse and Integration. San Francisco, USA, 2014:130-137.

[64] ISLAM M, KUZU M, KANTARCIOGLU M. Access pattern disclosure on searchable encryption: ramification, attack and mitigation[C]//Network and Distributed System Security Symposium (NDSS). California, USA, 2012:56-78.

[65] ZHUANG X, ZHANG T, PANDE S. HIDE: an infrastructure for efficiently protecting information leakage on the address bus[C]//Proceedings of the 11th ASPLOS. Boston, USA, 2004:72-84.

[66] CHOR B, GOLDREICH O, KUSHILEVITZ E. Private information retrieval[C]//IEEE Symposium on Foundations of Computer Science.Milwaukee, USA, 1995:141-151.

[67] DAUTRICH J, RAVISHANKAR C. Combining ORAM with PIR to minimize bandwidth costs[C]//CODASPY. TX, USA, 2015:289-296.

[68] MAYBERRY T, BLASS E, CHAN A. Efficient private file retrieval by combining ORAM and PIR[C]//NDSS. California, USA, 2014:123-131.

[69] GOLDREICH O，OSTROVSKY R. Software protection and simulation on oblivious RAMs[J]. Journal of the ACM (JACM),1996, 43(3):431-473.

[70] SHI E, CHAN T H H, STEFANOV E. Oblivious RAM with O((log n)3)worst-case[C]//17th International Conference on the Theory and Application of Cryptology and Information Security. Seoul, South Korea, 2011:95-100.

[71] WILLIAMS P, SION R. Usable PIR[C]//NDSS.CA, USA, 2008:22-34.

[72] WILLIAMS P, SION R, CARBUNAR B. Building castles out of mud:practical access pattern privacy and correctness on untrusted storage[C]//CCS. Alexandria, USA, 2008:139-148.

[73] BLOOM B. Space/time trade-offs in hash coding with allowable errors[J]. Communications of the ACM,1970,13(7):422-426.

[74] PAGH R, RODLER F F. Cuckoo hashing[J]. Journal of Algorithms,2004, 51(2):122-144.

[75] GOODRICH M T, MITZENMACHER M. Mapreduce parallel cuckoo hashing and oblivious ram simulations[J]. Clinical Orthopaedics and Related Research, 2010, 1007(1259):576-587.

[76] GOODRICH M, MITZENMACHER M. Privacy-preserving access of outsourced data via oblivious RAM simulation[C]//International Colloquium on Automata, Languages and Programming. Zurich, Switzerland, 2011:576-587.

[77] KUSHILEVITZ E, LU S, OSTROVSKY R. On the (in) security of hash-based oblivious RAM and a new balancing scheme[C]//The 23th Annual ACM-SIAM symposium on Discrete Algorithms. Philadelphia(SIAM). Kyoto, Japan, 2012:383-392.

[78] GOODRICH MT, MITZENMACHER M, OHRIMENKO O. Privacy-preserving group data access via stateless oblivious RAM simulation[C]//The 23th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia(SIAM). Kyoto, Japan, 2012:151-162

[79] GOODRICH M T, MITZENMACHER M，OHRIMENKO O.Oblivious RAM simulation with efficient worst-case access overhead[C]//The 3rd ACM Workshop on Cloud Computing Security Workshop(CCSW). Chicago, USA, 2011:99-108.

[80] BONEH D, MAZIERES D, POPA R A. Remote oblivious storage：making oblivious RAM practical[R]. http://dspace.mit.edu/handle/1721.1/62006. Technical Report (2011).

[81] GENTRY C, GOLDMAN K, HALEVI S. Optimizing ORAM and Using It Efficiently for Secure Computation[C]//PETS. Bloomington,USA, 2013:1-18.

[82] STEFANOV E，SHI E, SONG D. Towards practical Oblivious RAM[C]//NDSS. California, USA, 2012:203-214.

[83] CHUNG K, LIU Z, PASS R. Statistically-secure ORAM with ? (log2n)overhead[C]//ASIACRYPT. 2014:62-81.

[84] MOATAZ T, MAYBERRY T, BLASS EO. Resizable tree-based oblivious RAM[C]//19th International Conference(FC). San Juan,Puerto Rico, 2015:147-167.

[85] CHUNG K M, PASS R. A simple ORAM[EB/OL]. Cryptology ePrint Archive, 2013. http://eprint.iacr.org/2013/243.

[86] MARC SA. Toward efficient data access privacy in the cloud[J].Communications Magazine, IEEE, 2013,51(11):39-45.

[87] BOYLE E, CHUNG K M, PASS R. Oblivious parallel RAM[EB/OL].Cryptology ePrint Archive, 2014. http://eprint.iacr.org/2014/594.

[88] MOATAZ T, BLASS E O, NOUBIR G. Recursive trees for practical ORAM[R]. Cryptology ePrint Archive, 2014.

[89] STEFANOV E, SHI E. ObliviStore: High performance oblivious cloud storage[C]//IEEE Symposium on Security and Privacy. CA, USA,2013: 253-267.

[90] DAUTRICH J, STEFANOV E, SHI E. Burst ORAM: minimizing ORAM response times for bursty access patterns[C]//USENIX Security. San Diego, USA, 2014:58-69.

[91] REN L, FLETCHER CW, KWON A. Ring ORAM: closing the gap between small and large client storage oblivious RAM[EB/OL]. IACR Cryptology ePrint Archive, 2014: 997.

[92] WILLIAMS P, SION R. Single round access privacy on outsourced storage[C]//The 2012 ACM conference on Computer and Communications Security. NC, USA, 2012:293-304.

[93] ZHANG J, MA Q, ZHANG W. KT-oram: a bandwidth-effcient oram built on k-ary tree of pir nodes[R]. http://eprint.iacr.org/2014/624

[94] APON D, KATZ J , SHI E. Verifiable oblivious storage[C]//PKC.Buenos Aires, Argentina, 2014:131-148.

[95] DEVADAS S, MARTEN VAN D, CHRISTOPHER W. Onion ORAM:a constant bandwidth and constant client storage ORAM (without FHE or SWHE)[EB/OL]. Cryptology ePrint Archive, 2015

[96] MOATAZ T, MAYBERRY T, BLASS E. Constant communication ORAM with small blocksize[C]// ACM Sigsac Conference on Computer and Communications Security. Denver, Colorado, US, 2015:862-873.

Survey on data preserving for the search of internet of things

WANG Jia-hui1,2, LIU Chuan-yi2,3, FANG Bin-xing2,3
(1. School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China;2. Harbin Institute of Technology(Shenzhen), Shenzhen 518055, China;3. Electronic and Information Engineering Institute, Dongguan University of Electronic Science and Technology, Dongguan 523000, China)

With the rapid development of the internet of things(IoT) technology and big data technology, the search engine for internet of things become a hot research topic. However, because of the openness of the search of IoT, the privacy in traditional internet search area become more prominent and face more challenges. Firstly, the research background and challenges of privacy preservation for search of IoT were described. Secondly, the framework of data privacy preservation for search of IoT were presented and several main research domain in this framework were described.Thirdly, several privacy preservation technology appropriated for search of IoT were described in detail, including the background, recent research work, main research directions. Finally, the current problems and important research field for future were presented.

search for internet of things, privacy preservation, attribute based encryption, searchable encryption, oblivious random access machine

s: The National High Technology Research and Development Program of China (863 Program)(No.2015AA016001), Production-Study-Research Cooperation Project in Guangdong Province (No.2016B090921001), Innovation Project in Shandong Province (No.2014ZZCX03411)

TP309

A

10.11959/j.issn.1000-436x.2016186

2016-05-05；

2016-06-15

國家高技術(shù)研究發(fā)展計劃（“863”計劃）基金資助項目（No.2015AA016001）；廣東省產(chǎn)學(xué)研合作基金資助項目（No.2016B090921001）；山東省自主創(chuàng)新及成果轉(zhuǎn)化專項基金資助項目（No.2014ZZCX03411）

王佳慧（1983-），女，山西大同人，北京郵電大學(xué)博士生，主要研究方向為云計算與云安全、數(shù)據(jù)安全與數(shù)據(jù)保護等。

劉川意（1982-），男，四川樂山人，哈爾濱工業(yè)大學(xué)副教授，主要研究方向為云計算、數(shù)據(jù)安全與數(shù)據(jù)保護、網(wǎng)絡(luò)存儲、可信計算等。

方濱興（1960-），男，江西萬年人，中國工程院院士，北京郵電大學(xué)教授、博士生導(dǎo)師，主要研究方向為信息與網(wǎng)絡(luò)安全、內(nèi)容安全等。