面向物聯網搜索的數據隱私保護研究綜述

王佳慧，劉川意，方濱興

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

面向物聯網搜索的數據隱私保護研究綜述

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

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

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

物聯網搜索；隱私保護；屬性加密；密文搜索；隱藏隨機訪問模式

1 引言

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

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

首先，物聯網搜索服務提供者后臺服務器系統存有大量通過攝像頭、傳感器等感知設備收集的數據信息，而由于物聯網搜索應用領域廣泛，包括國民經濟各行業乃至社會發展各領域，這些數據信息如果不加以安全隱私的規范，將成為一個龐大的盯梢系統。類似于“棱鏡計劃”的通過內部數據搜索和挖掘導致的個人數據隱私侵犯將更加廣泛和便利。因此，物聯網搜索過程中的數據內容隱私保護變得十分必要。

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

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

本文針對上述物聯網搜索數據隱私保護面臨的安全挑戰，提出面向物聯網搜索的數據隱私保護框架，并在此基礎上對現有的適用于物聯網搜索隱私保護相關關鍵技術的國內外研究進展進行綜述。最后給出了未來工作展望。

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

2 物聯網搜索隱私保護框架

典型的物聯網搜索協議包括3個參與者：數據擁有者、數據搜索者和物聯網搜索服務提供者。其中，數據搜索者也可能是數據擁有者本身。數據擁有者是指上傳物理實體相關信息資源的個體或機構，數據搜索者是指使用物聯網搜索服務的個體或機構，物聯網搜索服務提供者是指提供物聯網搜索服務的提供商及后臺系統。要想實現面向物聯網搜索的數據隱私保護，就需要從3個參與者著手，采用隱私保護技術加以限制。

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

后續依次對適用于物聯網搜索的隱私保護技術：基于數據加密的搜索技術、基于屬性加密的訪問控制以及隱藏訪問模式技術的研究進展進行綜述。

3 基于密文搜索的隱私保護技術

3.1 總述

密文搜索技術使物聯網搜索服務提供者在返回滿足用戶搜索請求數據的同時，無法得知數據的內容。如圖2所示，基于數據加密的搜索技術分為2個階段：系統初始化階段和搜索階段。系統初始化階段包括系統初始化算法和數據加密算法。系統初始化算法由數據擁有者運行，用來生成系統的公開參數和數據擁有者的私鑰。基于非對稱密鑰的密文搜索算法，公開參數也包括數據擁有者的公鑰。數據加密算法由數據擁有者運行，用來生成加密的可搜索的數據結構（EDB，encryption database）和加密后的文件。在基于索引的方案中，還包括生成加密后的索引。

圖1 物聯網搜索隱私保護框架

圖2 基于密文搜索的物聯網隱私保護

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

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

3.2 現有密文搜索方案分類

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

3.2.1 SSE方案

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

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

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

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

3.2.2 PEKS方案

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

3.3 目前研究方向

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

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

2) 支持對服務器存儲的密文文件的動態添加、更新或刪除[27～31]。如何設計高效的支持數據實時更新的密文搜索方案，適應物聯網搜索數據的高度動態性，是一個非常大的挑戰。

3) 搜索效率的提升，此方面主要是通過減少雙線性對使用的頻率或者使用其他技術替代雙線性對來構造密文搜索方案[32,33]。總的來看，SSE搜索效率高，但同PEKS相比，靈活性和可擴展性較低，不適用于物聯網搜索場景。而PEKS現有方案大多使用雙線性對操作，使搜索效率大大降低。因此，研究適用于物聯網搜索的高效密文搜索方案及其重要。

4 基于訪問控制的數據隱私保護技術

4.1 總述

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

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

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

圖3 ABE方案

4.2 現有ABE方案分類

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

4.2.1 KP-ABE方案

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

4.2.2 CP-ABE方案

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

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

4.3 目前研究方向

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

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

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

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

5 基于隱藏訪問模式的隱私保護技術

5.1 總述

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

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

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

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

圖4 ORAM方案

5.2 現有ORAM方案分類

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

5.2.1 經典ORAM方案

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

1) 平方根ORAM方案

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

圖5 平方根ORAM數據存儲結構

2) 分層ORAM方案

分層ORAM方案由Goldreich和Ostrovsky[69]提出。數據存儲結構如圖6所示，由一個多層的桶式散列表[H1,H2,…,Hn]組成，其中，n=O(logN)，Hi層由 2i個桶組成，每個桶包含的數據單元個數為O(logN)，Hi和一個普通散列函數 hi相關聯。數據單元的位置由 HLocation=hi(v)決定，將虛擬地址映射到散列表。分攤開銷最優為O(log3N)，但隱藏的常數比較大，至少為 6 100，最壞情況下開銷為O(Nlog2N)。相比平方根算法，分攤性能有所提高，但是最壞情況的性能和服務器存儲復雜度都有所增加。

圖6 分層ORAM數據存儲結構

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

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

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

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

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

3) 樹ORAM

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

圖7 樹ORAM存儲結構

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

5.2.2 現代ORAM方案

經典的 ORAM 方案在計算算法復雜性時不考慮加解密數據的復雜性。而加解密操作都由用戶完成，因此保證了數據的安全性，數據加解密操作的數量不僅會增加用戶的負擔，服務提供者也無法發揮高性能搜索的好處，尤其對于物聯網搜索應用，后臺系統通常是基于云計算的平臺，其具有強大的計算能力。而分攤開銷是衡量 ORAM 性能的一個最重要因素，現代 ORAM 方案通過利用服務端強大的計算能力打破了 Goloreich等[69]對分攤開銷的限制，可以將分攤開銷降低到常數級。由于服務器執行額外操作，就必須考慮服務器是否按預定方式執行，這使威脅模型變為惡意模型。根據服務器執行的額外操作種類分為2類。

1) 矩陣乘或者XOR操作

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

2) 加同態或者全同態

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

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

5.3 目前研究方向

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

ORAM目前主要研究方向包括：使用并行算法來降低分攤開銷；使用服務器端運算來降低用戶端開銷和分攤開銷；構建不需要額外假設或者不需要FHE可驗證的ORAM方案。

6 結束語

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

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

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

3) 現有的支持搜索的隱私保護技術，搜索的條件主要是基于關鍵字的搜索，因此，研究支持物聯網復雜搜索條件的隱私保護模型和應用或將復雜搜索條件合理轉換成基于關鍵字的搜索十分必要。

4) 研究將基于數據加密的搜索技術和基于屬性加密的訪問控制技術有機結合，使數據擁有者能在最大限度地控制數據使用權的同時，實現物聯網搜索的數據隱私保護。

5) 對于使用ORAM技術來隱藏物聯網搜索模式，主要關注分攤性能、交互式復雜度、用戶端開銷幾個重要性能衡量指標，因此，研究構造這幾個性能指標均衡的 ORAM 方案對于保護物聯網搜索數據隱私是非常重要的研究方向。

只有綜合考慮上述幾個方面，形成整體的解決方案，才能有效保護物聯網搜索數據擁有者和數據搜索者的權益和隱私，促進物聯網搜索服務的有序健康發展。

[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

國家高技術研究發展計劃（“863”計劃）基金資助項目（No.2015AA016001）；廣東省產學研合作基金資助項目（No.2016B090921001）；山東省自主創新及成果轉化專項基金資助項目（No.2014ZZCX03411）

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

劉川意（1982-），男，四川樂山人，哈爾濱工業大學副教授，主要研究方向為云計算、數據安全與數據保護、網絡存儲、可信計算等。

方濱興（1960-），男，江西萬年人，中國工程院院士，北京郵電大學教授、博士生導師，主要研究方向為信息與網絡安全、內容安全等。