隱私保護的圖像內容檢索技術研究綜述

吳穎，李璇,2,3，金彪，金榕榕

隱私保護的圖像內容檢索技術研究綜述

吳穎1，李璇1,2,3，金彪1，金榕榕1

（1. 福建師范大學數學與信息學院，福建 福州 350100；2. 福建省網絡安全與密碼技術重點實驗室，福建 福州 350100；3. 數字福建大數據安全技術研究所，福建 福州 350100）

隨著智能設備與社交媒體的廣泛普及，圖片數據的數量急劇增長，數據擁有者將本地數據外包至云平臺，在云服務器上實現數據的存儲、分享和檢索。然而，圖像數據含有大量有關用戶的敏感信息，外部攻擊者和不完全可信的云服務器都試圖獲取原始圖像的內容，窺探用戶隱私，造成嚴重的隱私泄露風險?；仡櫫私陙黼[私保護需求下圖像內容檢索技術的研究進展，總結了應用于該技術的圖像加密算法，包括同態加密、隨機化加密和比較加密，圍繞這3種密碼技術，詳細分析和比較了典型的解決方案，并介紹了索引構造的改進策略。最后，總結和展望了未來的研究趨勢。

隱私保護；圖像內容檢索；可搜索加密；云計算安全

1 引言

隨著云計算技術的發展和大數據信息時代的到來，越來越多的數據擁有者選擇將本地設備上的數據外包給云服務器，以減少本地存儲資源和計算資源的消耗[1]。一些主流的社交網絡（如Facebook和Flickr等運營商）也利用用戶上傳的數據實現行為廣告、用戶偏好分析等目的[2]。由于互聯網上存在大量惡意用戶，同時“誠實但好奇”的云服務提供商也并不完全可信，導致外包數據的隱私性和安全性引發了人們的擔憂[3]。近年來，數據隱私成為業內用戶和研究者普遍關注的問題，隱私保護計算成為信息安全領域和其他相關領域的熱門研究方向，廣泛應用于生物信息識別[4]、醫療診斷[5]、監控視頻匹配[6]等多個領域。

為了防止隱私泄露，數據加密技術被廣泛應用于外包數據的隱私保護計算。用戶可以選擇在本地端對涉及隱私的數據進行加密后上傳云端，然后由云服務器在密文上實現更新、搜索和計算等操作。隱私保護的圖像內容檢索（PPCBIR， privacy-preserving content based image retrieval）是隱私保護計算的一個重要方向，能夠幫助用戶實現外包圖像的安全檢索。隨著各大社交網絡、云存儲應用的流行，每天有數以億計的數字圖像被上傳和存儲。基于內容的圖像檢索（CBIR，content based image retrieval）可以幫助人們從互聯網海量的圖像中迅速找到自己感興趣的圖像。CBIR把檢索的關鍵放在圖像內容自身的特征，對圖像進行分析，建立圖像特征描述符并存入圖像特征庫，當用戶提供查詢圖像的特征向量時，云端通過計算特征向量與圖像特征庫中各個特征的相似度，按照相似性大小進行排序后輸出檢索結果[7]。由于圖像數據可能含有大量有關用戶的敏感信息（如人臉、家庭環境等），為了避免個人隱私泄露，用戶可以在上傳敏感圖像前對其加密，但加密操作會導致明文領域的CBIR技術不再可用。為了解決這個問題，近年來研究者提出了許多PPCBIR方案，在不向云服務器透露敏感信息的情況下，支持加密域上的圖像內容檢索。

2 隱私保護的圖像內容檢索

2.1 PPCBIR方案的實體

PPCBIR方案一般涉及3類實體：圖像所有者、圖像查詢者以及云服務器。

圖像所有者：提取待上傳圖像的特征向量，構造安全的可搜索索引，用密鑰將圖像特征加密成密文，并將密文特征和安全索引外包給云服務器。部分方案中，圖像所有者還承擔授權查詢用戶和制定訪問策略的任務。

圖像查詢者：由圖像所有者授權可在云服務器檢索其上傳圖像的合法用戶。在請求檢索圖像時，圖像查詢者提取查詢圖像的特征，并加密成密文，將密文特征作為查詢陷門提交給云服務器。在接收到查詢結果后，使用圖像所有者共享的密鑰對其解密。

云服務器：存儲密文圖像特征和安全索引，并處理來自圖像查詢者的檢索請求，按照訪問策略執行檢索任務。面對受保護的大規模多媒體數據時，云服務器應具有對受保護數據進行搜索和計算的能力。

2.2 PPCBIR方案的關鍵環節

實現PPCBIR方案的關鍵環節有兩點：圖像特征的保護和密文域的相似性度量。

1) 圖像特征的保護

該環節需要提取原始圖像特征，使用密碼算法對特征加密保護，并保證經過加密處理的圖像特征描述符可以用于后續的檢索操作。圖像特征包括全局特征和局部特征。全局特征是從整體上描述一幅圖像，包括顏色直方圖[8]、形狀特征[9]和紋理特征[10-11]等信息。局部圖像特征是用帶權重的局部特征向量集合表示一幅圖像，較為常用的局部圖像特征提取算法有尺度不變特征變換[12]（SIFT，scale-invariant feature transform）、局部聚合向量[13]（VLAD，vector of locally aggregated descriptors）、局部二值模式[14]（LBP，local binary patterns）等。提取特征之后，為了提高檢索效率，通常使用視覺詞袋[15]（BoVW，bag of visual-words）、局部敏感哈希[16]（LSH，locality- sensitive hashing）、主成分分析[17-18]（PCA，principal component analysis）等技術對提取的特征進行降維。

原始圖像特征可以在明文上提取，也可以在密文上提取。明文上提取特征的過程較為簡單，由用戶在本地獨立從原始圖像上提取特征。但當提取圖像特征的計算量較大時，由于終端用戶的資源有限，用戶會考慮將此過程中復雜的計算部分外包給云服務器處理，由雙方協作完成圖像特征的提取。考慮到云端是“誠實但好奇”的，用于計算特征的外包數據需進行保護，以避免泄露圖像或特征的內容，因此提出了密文域的特征提取算法[19-23]。在圖像特征提取完成后，用戶對特征加密，并將其發送給云服務器，以用于后續基于密文特征的檢索。

2) 密文域的相似性度量

相似性度量是PPCBIR實現圖像檢索的重要環節，通過實現密文之間的相似度比較，從而完成密文圖像的檢索。由于數據加密后往往打亂了原始明文的統計特性，密文域上的相似性度量較為困難，設計時需綜合考慮數據加密和特征提取這兩個環節所使用算法的特點，設計出能夠在加密域上實現的相似性度量方案，以實現密文之間的相似度計算和排序。常用的距離計算有歐式距離、L1距離、漢明距離等，為了得到相似性的排名結果，還可以利用最高有效位（MSB most significant bit）、安全KNN[24]（secure K-nearest neighbor）、安全多方計算（secure multi-party computation，SMC）等算法進行度量。

由于密文距離計算的復雜度較高，如果采用對查詢圖像和數據庫中圖像兩兩之間計算密文距離，會造成極低的檢索效率。要提高密文圖像的檢索效率，還需要設計有效的索引結構和檢索優化方案。

當有權限的圖像查詢用戶發送查詢請求和查詢門限給云服務器后，云端在不知道原始圖像特征內容的情況下，在密文上執行檢索操作，并將得到的查詢結果返回給用戶。

PPCBIR方案的基本步驟如圖1所示。表1列出了典型PPCBIR方案的關鍵環節。

3 PPCBIR的數據加密技術

數據加密是實現PPCBIR的關鍵技術環節，通過隱藏數據語義內容，實現保護數據隱私的目的[25]。在隱私保護的圖像檢索中，為了不向云服務器泄露敏感信息，用戶需要在將圖像上傳至云服務器前加密圖像特征。

為了達到PPCBIR中圖像檢索的需求，需要尋求合適的加密方式，使密文能夠被處理，且保證密文下的操作結果近似等于明文下的操作結果。在PPCBIR的研究中，常用的加密技術包括同態加密（HE，homomorphic encryption）、隨機化加密和比較加密。下面具體介紹這3種密碼算法的原理，并簡要說明其在PPCBIR中的應用。

圖1 PPCBIR技術框架

表1 典型PPCBIR方案的關鍵環節

3.1 同態加密

同態加密算法允許在密文域上對加密數據進行計算，計算過程不會泄露數據的原始內容[26]。持有密鑰的用戶對密文計算結果解密后，可以直接得到明文上的相應計算結果。同態加密分為部分同態加密（SHE ，somewhat homomorphic encryption）和全同態加密（FHE，fully homomorphic encryption）。部分同態加密包括加法同態和乘法同態，分別支持密文域上的明文加法計算和明文乘法計算，經典算法有RSA、ElGamal、Paillier同態加密等[27]。全同態加密可以同時支持密文域的加法和乘法計算，從而滿足密文域的任何計算需求，但其復雜度高和資源消耗很大。所以隱私保護計算的研究者目前更多將精力放在SHE的應用上，SHE也被廣泛用于隱私保護的圖像處理[28-29]。

Paillier加密[29]是隱私保護圖像處理中最常使用的加法同態加密算法，其加解密過程如下。

加密算法：對數據進行加密

是明文，是密文，是用戶隨機選擇的整數。

解密算法：

隱私保護的圖像內容檢索中，由于涉及密文域上圖像相似度的度量計算，同態加密算法的性質能夠為其提供很好的技術支持。使用同態加密算法加密初始圖像或圖像特征，再利用其支持密文域加法和數乘的特性，實現密文域上的有效檢索[30-34]。

3.2 隨機化加密

隨機化加密的原理是在原始數據中增加隨機噪聲或者對其進行隨機變換，使數據使用者無法從隨機化干擾后的數據中獲得原始數據的詳細內容。隨機化加密效率高，適用于數據量大、冗余度高的圖像數據加密[35-36]。

近年來，一些研究者將隨機化加密方法應用于PPCBIR中[37-38]。由于隨機數加密的安全性源于其對明文統計特性的破壞，如何在密文域上完成明文圖像的相似性度量，構建有效的PPCBIR方案，是面臨的主要挑戰。目前，基于隨機化加密的PPCBIR方案中，主要思想是將需要保護的圖像或其特征看作多維的向量，對向量的多個分量分別進行加密處理，定義合適的向量距離，使數據加密前后的距離保持不變，從而通過計算加密后的索引向量與待查詢向量之間的距離，完成密文域上的相似度排序，實現圖像檢索。下面簡要介紹基于隨機矩陣變換的隨機化加密算法[38]。

這種安全轉換方法可以防止特征向量的信息泄露，同時支持相似度計算，被廣泛應用于隱私保護下的安全距離度量工作[39]。

3.3 比較加密

基于請求的比較加密（request-based comparable encryption）是一種對稱加密算法，具有如下性質：當且僅當給定一個與明文相關聯的令牌時，該機制允許將加密后的密文與其他密文進行比較。比較加密是Furukawa等[40-41]基于原有的保序加密（OPE，order-preserving encryption）做出的改進算法。

Agrawal等[42]提出的OPE算法，特點在于在密文上保留了明文的原有順序，對于一些涉及順序信息的查詢操作，可以直接應用于加密數據，且加密后不會影響系統查詢、更新等功能[43-46]。對OPE的相關研究[47-48]中發現，OPE存在這樣的問題：如果某個范圍內的所有數據都被一個OPE加密，那么攻擊者很有可能通過獲取密文的順序得到原始的信息。Furukawa等[40-41]針對OPE存在的這一問題，提出了一種基于請求的比較加密。它不僅可以實現密文下的數值比較，也能保證數值的安全。Furukawa在文獻[41]中提出了改進方案，減少了密文的長度。之后Chen等[49]提出了一種基于滑動窗口的方法，使比較加密的效率得到提高。下面簡要介紹基于請求的比較加密。

比較加密算法由4個部分組成：參數生成、數據加密、令牌生成和數據比較。

2) 數據加密：給定參數、主密鑰和明文，輸出密文。

3) 令牌生成：給定參數，主密鑰和明文，輸出令牌。

4) 數據比較：給定參數、兩個待比較密文、、和令牌，輸出結果為?1、1或0。

則認為比較加密滿足完整性。

Zou等[50]把比較加密用于圖像特征的加密和比較中，主要思想是使用比較加密算法對原始圖像及由特征向量生成的索引進行加密處理，原始圖像特征得到保護，通過得出密文域上的順序信息以實現密文比較，比Lu等[51]基于OPE的方案具有更高的安全性。

4 基于同態加密的HE-PPCBIR方案

在PPCBIR領域中，許多研究者利用同態加密的特性設計了密文圖像上的檢索方案。本節介紹基于同態加密的PPCBIR（HE-PPCBIR）研究成果。

4.1 基于同態加密的特征提取

特征提取是PPCBIR的第一步，在實際操作過程中，往往面對多維度的圖像數據庫，當圖像特征的提取過程較為復雜時，由于用戶能夠利用的本地計算資源有限，龐大的計算任務給終端用戶帶來沉重的負擔。許多研究者把圖像特征提取的任務外包給云服務器，要求云服務器在不知道圖像數據原始內容的情況下，也能進行特征提取的計算。

尺度不變特征變換（SIFT，scale-invariant feature transform）[12]是一種用于檢測和描述圖像局部特征的常用算法，其特征具有尺度旋轉不變性，在計算機視覺和模式識別領域被廣泛應用。Hsu等[19]討論了安全SIFT外包問題，首次利用同態加密的Paillier算法研究了加密域中隱私保護的SIFT，方案允許只對部分涉及隱私的區域進行加密。然而，Hsu的解決方案在計算上難以處理，在加密數據比較中引入了非常大的計算復雜度，每個比較都需要遍歷任意兩個閾值之間一半的純文本空間；另外，從隱私的角度來看，如果通過選擇較小的明文域來降低比較協議的復雜性，則會破壞安全性，是不安全的。針對Hsu等提供的思路，一些研究者在處理安全SIFT外包問題上做出了許多拓展。Wang等[20]考慮了基于形狀特征提取的安全性和隱私保護的SIFT外包計算問題，分別采用同態加密和Yao混淆電路協議[52]提出了兩種不同安全級別的方法；Li等[21]分析了系統抵抗惡意攻擊的能力，因為高級的惡意攻擊會在尺度空間中破壞圖像特征，發現使用凸松弛方法可以有效地去除SIFT的關鍵點，同時為了隱藏去除SIFT關鍵點的痕跡，將大量的偽SIFT關鍵點注入之前經過處理的圖像中，使失真最小化。

以往的解決方案都存在一個共同的局限性：為了對密文進行操作，不小心破壞了原SIFT特征的頑健性和特殊性；無法進行很好的圖像相似度匹配；缺乏對原始圖像特征提取算法關鍵特征的保存進行全面的分析和評價。

4.2 基于同態加密的安全圖像檢索

本節介紹基于同態加密的HE-PPCBIR方案，從特征信息和算法兩個層面對各方案進行綜述，并比較分析其特點。

Lu等[30]在研究綜述中總結了HE-PPCBIR的相關工作，給出了一種基于加性同態加密的PPCBIR方案。圖像擁有者使用加法同態加密算法對圖像特征進行保護后，上傳至云服務器的加密圖像特征庫。圖像查詢者在檢索圖像時，可以根據不同的安全需求，選擇將查詢圖像特征以密文或者明文形式上傳給云服務器：以密文形式查詢時，查詢用戶需要參與圖像特征相似度的安全計算過程；以明文形式查詢時，用戶無須參與，最后在結果中加入噪聲，以提高安全性。方案雖然可行，但犧牲了搜索精度，且大大增加了用戶的計算和存儲開銷，不適合于實際應用。同時，該文介紹了采用完全同態加密方法，服務器可以直接在密文上計算查詢圖像特征和圖像庫中加密特征之間的相似度距離，無須用戶直接參與。但該方法的計算量很大，在距離排序時，為了避免距離大小信息的泄露，也需要用戶的參與進行解密和排序。

Lu[30]和Zhang[31]都使用了同態加密技術加密特征向量，直接在密文域上計算特征之間的相似度距離，在檢索過程能夠達到較高的安全性，但二者都需要用戶與服務器的頻繁交互，且同態加密計算復雜，不可避免地造成了繁重的計算和通信開銷。Bellafqira等[32]在避免客戶和服務器之間交互的方向上減小通信開銷，他們在工作中使用了Paillier加密圖像，并在加密域上提取基于小波變換的全局圖像特征，安全CBIR的計算[33]都由云服務器執行，避免了客戶和服務器之間的額外通信，但檢索效率和精度不高。之后Bellafqira等[34]對該工作進行了擴展，提出了計算加密離散小波變換（SDWT，secure image discrete wavelet transform）的方法，利用兩個云服務器進行共享加密的直方圖計算，與文獻[32]方案相較，安全性和檢索精度上都有提升，但同態加密和特征提取過程產生的計算問題仍沒有得到解決。

Zhang等[56]的多層級同態加密方案（PIC）考慮了多用戶場景下PPCBIR中密鑰的分發和管理。方案中引入了密鑰代理（KA），首先由一個完全可信的密鑰發布中心（TP）隨機選擇密鑰，拆分密鑰后分配給用戶，加密時，從用戶到KA再到云服務器進行分級加密，在每一級加密過程中，利用該級對應的密鑰更新獲得的密文。為加快搜索進程，方案中還設計了MapReduce框架，通過將搜索過程設計為一級搜索和二級搜索，通過任意數量的mappers和一個reducer可以完成在簇中找到KNN的搜索。特征向量和查詢向量的密文分配給mappers進行同態操作和密鑰修改以生成距離密文。然后，這些內容被發送到KA方的reducer進行解密并對距離排名。該方案較好地保護了密鑰的安全，避免了用戶和云服務器之間的直接交互，但一定程度上產生了額外的計算開銷。Shen等[57]針對現有的大多數PPCBIR方案只針對一個圖像擁有者的局限性，設計了一種可支持多個圖像共享用戶的安全檢索模型。在特征的加密環節采用Jung等[58]提供的計算協議，可以在半誠實的模型下有效保護數據隱私。

由于同態加密算法本身具有較高的計算復雜度，現有的大部分基于同態的圖像安全檢索方案雖然可以滿足更高級別的安全需求，但繁重的計算通信開銷問題依然是今后相關研究中所面臨的關鍵問題。

5 基于隨機化加密的RE-PPCBIR方案

隨機化加密是通過對原始數據加入隨機擾動或者進行隨機變換，以隱蔽數據的原始信息，但并非完全抹去數據內容，數據使用者依然可以使用處理后的數據進行后續的操作。在基于隨機化加密的PPCBIR方案（RE-PPCBIR）中，利用隨機化加密的性質對圖像特征進行保護，并在加密過程中保留計算特征相似度時需要的信息。本節介紹近年來RE-PPCBIR的研究成果。

在設計RE-PPCBIR方案時，不同的圖像視覺特征可以采取不同的隨機化方法，以達到更好的特征保護效果。圖像的視覺特征包括全局特征和局部特征。全局圖像特征是從整體上描述一幅圖像，提取全局特征的過程是基于區域或整個圖像執行的，利用顏色、形狀、紋理和空間布局等信息獲取圖像描述符，通過全局描述符的比較進行圖像檢索。局部圖像特征是用帶權重的局部特征向量集合表示一幅圖像，較為常用的局部圖像特征提取算法有SIFT[12]、VLAD[13]、LBP[14]等?；谌痔卣鞯膱D像檢索操作方便，計算開銷較小，但檢索精度不高?；诰植刻卣鞯膱D像檢索在計算上較為復雜，但往往具有更好的頑健性及更高的檢索精度。

本節從隨機化加密圖像特征的角度，分別對Lu等提出的3種特征保護方案[37]、IES-CBIR方案[59]、DCT系數隨機置亂方案[60-62]以及基于安全KNN算法[24]的RE-PPCBIR方案[63-66]的加密過程進行綜述。

Lu等[37]提出的PPCBIR方案利用隨機數加密技術，引入了3種距離保持機制對圖像視覺特征進行加密，目的是保持圖像特征加密前后的近相似性，這3種機制分別為：位平面隨機化、隨機投影和隨機化一元編碼。

1) 位平面隨機化

位平面隨機化先將特征向量的所有分量值二進制化，再對同一層位平面采用流密碼與偽隨機序列異或，最后計算相對應的密文位平面之間的漢明距離，來衡量圖像特征的相似性。

2) 隨機投影

然后計算密文特征向量()與()之間的歐氏距離，即

3) 隨機化一元編碼

隨機化一元編碼的基本思想是使用流密碼異或加密和置亂加密技術隱藏原始特征向量的信息，再將加密后的向量隨機投影到低維空間。由于加密過程使用相同的密鑰，加密前后的漢明距離保持不變，通過計算低維空間上向量之間的漢明距離，可以實現加密域上的圖像檢索。

Lu等[37]提出的3種方法操作簡單，適用于密文域圖像檢索工作中對大部分特征向量的保護和相似性的計算。方案存在一些缺陷：①其安全性僅針對視覺特征，未能描述在半誠實的云環境下的抗攻擊能力；②面對海量且高維的圖像庫圖像，其產生的巨額計算和通信成本不容忽視，檢索效率低。Ferreira等[59]針對顏色信息和紋理信息設計了一種可以支持CBIR的特征保護方案IES-CBIR。在IES-CBIR檢索方案中，用戶對顏色信息進行確定性加密，同時對紋理信息進行概率加密，加密顏色特征以提高安全性，加密紋理特征以實現圖像的安全檢索，這樣分開加密可以避免用戶的直接干預，使密文圖像檢索的整個過程在云服務器上執行。

IES-CBIR的檢索過程為：首先，服務器對每個加密圖像和HSV（hue saturation value）顏色通道構建一個表示圖像的顏色直方圖（每個圖像產生3個直方圖）；然后，服務器從授權用戶接收查詢請求的陷門，提取其特征向量，通過直方圖交集比較數據庫中個最相似的圖像；最后，查詢用戶接收到來自服務器的排序結果，使用圖像所有者授權的解密密鑰恢復出原始圖像信息。

Lu[37]和Ferreira[59]等的RE-PPCBIR方案存在同樣的問題：①原始圖像的加密獨立于特征的提取和加密，很容易給用戶帶來額外的計算成本，不適用于海量的高維圖像數據庫；②加密算法都是針對圖像像素的置亂或位移等操作，不能保證JPEG文件大小的保存和格式的兼容性。

為了克服這些局限性，近年來，有一些研究者針對JPEG圖像，利用加密前后DCT系數直方圖的不變性，提出了基于隨機化加密的JPEG加密圖像檢索方案。Cheng等[60]采取DCT系數隨機置亂[61]的方法加密JPEG圖像，由于DCT系數包含了圖像的特征信息，在加密域上保留其分布特性，可以實現相似圖像的安全檢索。下面簡要描述DCT系數隨機置亂的過程。

在圖像檢索階段，服務提供者利用DCT系數直方圖不變性，計算出每個分量各個頻率位置上的DCT系數直方圖，再對3個分量加權距離排名得到搜索結果。該方案不需要特征的提取和加密，一定程度上減少了服務器的計算負擔。方案的缺陷在于：加密后的圖像文件大小增加，另外增加了服務器的存儲和通信成本，此外，明文圖像的信息是部分可見的，在安全性方面存在威脅。韓威等[62]的方案中也研究了基于DCT系數的JPEG加密圖像檢索。與Cheng[60]的方案不同的是，韓威的方案需要云服務器在圖像密文上提取DCT系數差分特征以及LBP（local binary patterns）特征，比較特征距離確定圖像的相似度，不過由于DCT變換消除了圖像的冗余信息，提取特征的過程較為簡單，減少了用戶與云服務器的交互，但是泄露部分明文信息，安全威脅仍然存在。

基于安全KNN[24]的檢索方法也是目前圖像安全檢索常用方法，使用數據隨機化將圖像特征加密后，可以支持在密文特征上計算特征之間相似度的KNN排名。在構建PPCBIR結構時采用安全KNN算法，可以很好地達到特征保護和相似度度量的目的。安全KNN算法的原理是使用隨機矩陣對特征向量進行乘法變換，并通過計算加密域上索引向量與查詢向量間的“內積相似度”，完成原始數據的相似度比較，實現安全KNN算法。下面簡單介紹安全KNN算法的過程。

加密特征向量的過程如下。

計算密文相似度的過程為

Huang等[63]使用VLAD作為圖像描述符[13]，采用基于投影的雙線性二進制碼（BPBC，bilinear projection-based binary codes）將VLAD轉化為低維的二進制碼，結合了安全KNN方案計算查詢特征向量與圖像庫中圖像特征的相似性。Huang等[64]也采用PCA[17-18]降低特征維度，計算出PoV的值表示特征向量，以此掩蓋特征數據的真實信息。在查詢完成后設計了關聯反饋的機制，通過查詢用戶與云服務器的交互，在云服務器中訓練SVM分類器，以達到更高的檢索性能。為了防止不可信云服務器在反饋機制中學習到用戶的查詢意圖，查詢用戶需要在上傳之前引入混淆類別，雖然一定程度上可以干擾云服務器的判斷，但用戶在選擇混淆類的過程中已經不可避免地向云服務器透露了一些敏感信息，因此該方案關聯反饋機制的安全性還有待進一步優化。

6 基于比較加密的CE-PPCBIR方案

比較加密是一種對稱加密算法，允許密文之間進行大小的比較，可用于構建PPCBIR方案，實現密文域的相似度度量。與同態加密相比，比較加密的計算和檢索開銷較小。本節對基于比較加密的PPCBIR方案（CE-PPCBIR）進行介紹。

Lu等[51]提出了基于OPE的PPCBIR方案。方案采用詞袋模型構建索引，使用視覺詞匯表示特征，訓練視覺單詞表，再使用分層聚類的方法生成詞匯樹，構建出倒排索引。圖像所有者提取一幅圖像的特征向量后，對其做OPE加密，將加密的倒排索引和密文圖像發送給云服務器。云服務器接收到來自圖像查詢者的查詢請求后，通過計算兩組視覺詞匯之間的Jaccard距離評價圖像的相似度。由于OPE會泄露詞頻之間的大小關系，敵手很容易通過密文的大小關系推斷出明文數值的所在范圍，因此在實際應用中的安全性不高。

Zou等[50]使用比較加密設計了PPCBIR方案。該方案使用LSH構建圖像的樹索引結構，索引結構通過比較加密保護，利用比較加密的性質實現密文域的相似度計算。下面詳細介紹Zou等[50]的CE-PPCBIR方案，以說明比較加密在安全圖像檢索中的應用。

使用比較加密算法對基于LSH構建的樹狀索引加密時，分為生成令牌（Gentoken）和生成密文（GenCiph）兩個步驟進行。

第個特征向量的第維加密為

加密后的特征向量為

該方案比基于OPE的PPCBIR安全性更高，一方面，敵手通過密文向量的模值推斷出每一維向量值的概率可以忽略不計；另一方面，云服務器不知道標簽token的值，避免了“誠實且好奇”的云端自行比較圖像庫的圖像，導致對用戶隱私造成威脅。方案的局限性在于需要圖像所有者、查詢用戶和云服務器的頻繁交互，其應用場景受到限制。

7 PPCBIR的索引結構優化

為了提高PPCBIR方案的檢索效率，研究者開始關注PPCBIR索引結構的優化問題。

一些研究人員提出了基于局部敏感哈希LSH[16]的PPCBIR方案。LSH算法是一種針對海量高維數據的快速最近鄰查找算法，基本思想是：原始數據空間中的兩個相鄰的數據點通過相同的LSH函數進行映射或投影變換后，在新的空間中仍保持相鄰（即被映射到同一個桶內）的概率很大，同時，不相鄰的數據點被映射到同一個桶的概率很小。研究者利用LSH的特性，將經過隨機化處理后的特征映射到低維的空間，使在低維空間的特征也能保持原有的相似程度。利用散列后的特征向量構建的安全索引，可以使存儲資源得到有效利用，同時，由于將原本高維空間的數據比較轉化為低維空間的數據比較，大大提高了檢索效率。

在安全索引的構建中，為了提高相似圖像的碰撞概率，還建立了多張散列表，對于一個查詢請求，從所有的散列表中找到對應的散列桶，然后逐一比較查詢圖像與散列桶中圖像集圖像間的相似度。

Zhu等[66]設計了兩個階段的PPCBIR結構框架，支持全局特征和局部特征的搜索：第一階段利用LSH對圖像數據庫進行預過濾，縮小搜索范圍；第二階段設計了安全線性規劃轉換（SLP，secure linear programming），可以實現密文下的EMD距離度量，方案的局限性在于局部特征的維度較大，在得到相對精確的搜索結果的同時，犧牲了大量的時間成本。Xia等[67]基于上述LSH安全索引構造方式，設計了Two-Layer-Index雙層索引結構，索引的頂層是利用基于穩定分布的LSH構建的散列表，作為預篩選層，底層是One-One Map一對一索引，用于對與查詢圖像的相似度計算和得分排名，雙層索引結構使檢索效率得到顯著提升。方案的不足之處在于：①為了達到更高的檢索效率，犧牲了一定的準確度；②圖像的相似度信息被泄露。例如，構建預篩選層的同時，云服務器很容易判斷出同一散列桶中的圖像是相似的。在Xia等的另外一項工作[68]中，在PPCBIR中考慮了不誠實用戶的問題，首次構建了密文域上的水印協議。水印與圖像查詢用戶關聯且唯一，可被追蹤，能夠阻止授權查詢用戶對檢索圖像的非法復制和分發。方案存在一些方面需要改進：①該水印協議未能達到理想的頑健性；②一個小的參數會導致可用的水印數量被限制。

8 結束語

隱私保護的圖像內容檢索技術PPCBIR為圖像數據的外包存儲和檢索中存在的隱私問題提供了解決辦法，密文檢索策略在“誠實但好奇”云服務器環境下能夠得到廣泛應用。本文圍繞PPCBIR的主要技術和關鍵環節，對該領域近年來的研究成果進行了綜述，在關鍵密碼技術方面，總結了應用于PPCBIR的圖像加密算法（包括同態加密、隨機化加密和比較加密）。按照使用的密碼技術不同，分類回顧了近年PPCBIR的研究進展，并介紹了為提高檢索效率采用的檢索結構優化方案。

結合當前PPCBIR的研究進展，未來對PPCBIR研究的重點如下。

1) 大數據環境下，從海量的圖像數據中快速且準確地挖掘出用戶所需信息的相關工作，已經成為當前的研究熱點。而加密域圖像檢索的研究還處于起步階段，面對大規模的圖像數據庫，如何在隱私保護的前提下實現有效甚至高效的大規模圖像檢索，是未來PPCBIR面臨的挑戰。

2) 加密技術是實現圖像數據隱私保護的主要解決手段，但基于對稱密碼模型中可能存在密鑰泄露的問題，且尚未有方案考慮到圖像用戶自身攜帶惡意信息的情況。當圖像查詢用戶的查詢請求中攜帶惡意內容時，云服務器需要考慮如何識別和攔截。同時，設計面向數據檢索的輕量級圖像加密算法，減少資源有限的客戶端的計算量，也是當前的迫切需求。

3) 圖像特征的有效程度會影響最終的檢索性能，在提取圖像特征時需要考慮特征維度大小對檢索性能的影響。針對多維的圖像特征計算，設計更加安全、高效的輕量級搜索模式，也是未來重要的研究方向。

[1] KAMARA S, LAUTER K. Cryptographic cloud storage[C]// International Conference on Financial Cryptography and Data Security, Berlin: Springer Berlin Heidelberg, 2010.136-149.

[2] LEON P, UR B, SHAY R, et al. Why Johnny can't opt out: a usability evaluation of tools to limit online behavioral advertising[C]//Sigchi Conference on Human Factors in Computing Systems, 2012:589-598.

[3] NAIMIA I, WESTREICH D J. Big data: a revolution that will transform how we live, work, and think[J]. Mathematics & Computer Education, 2014, 47(17):181-183.

[4] LAGENDIJK R L, BARNI M. Encrypted signal processing for privacy protection: conveying the utility of homomorphic encryption and multiparty computation[J]. IEEE Signal Processing Magazine, 2013, 30(1):82-105.

[5] RUPA C. Privacy preservation of ROI of medical image using squint pixel and PLSB hiding technique[C]//International Conference on Virtual System & Multimedia. IEEE, 2017:1-5.

[6] DUFAUX F. Video scrambling for privacy protection in video surveillance - recent results and validation framework[J]. Proceedings of SPIE-The International Society for Optical Engineering, 2011, 8063:307-314.

[7] GUDIVADA V N, RAGHAVAN V V. Content based image retrieval systems[J]. Computer, 1995, 28(9):18-22.

[8] SMITH J R, CHANG S F. Tools and techniques for color image retrieval[J]. Proc. of SPIE(The International Society for Optical Engineering) 1996, 2670:32-42.

[9] JAIN A K, VAILAYA A. Image retrieval using color and shape[J]. Pattern Recognition, 1996, 29(8):1233-1244.

[10] DUNN D, HIGGINS W E, WAKELEY J. Texture segmentation using 2D Gabor elementary functions[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1994, 16(2):0-149.

[11] MANJUNATH B S, MA W Y. Texture features for browsing and retrieval of image data[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996, 18(8):837-842.

[12] LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[13] JEGOU H, DOUZE M, SCHMID C, et al. Aggregating local descriptors into a compact image representation[C]//IEEE Conference on Computer Vision and Pattern Recognition. 2010: 3304-3311.

[14] YANG B, CHEN S. A comparative study on local binary pattern (LBP) based face recognition: LBP histogram versus LBP image[J]. Neurocomputing, 2013, 120(10):365-379.

[15] SHEKHAR R, JAWAHAR C V. Word image retrieval using bag of visual words[C]//IAPR International Workshop on Document Analysis Systems. 2012: 297-301.

[16] DATAR M, IMMORLICA N, INDYK P, et al. Locality-sensitive hashing scheme based on p-stable distributions[C]//Twentieth Symposium on Computational Geometry, ACM, 2004:253-262.

[17] TIPPING M E, BISHOP C M. Probabilistic principal component analysis[J]. Journal of the Royal Statistical Society Series B (Statistical Methodology), 1999, 61(3):611-622.

[18] JOLLIFFE I T. Principal component analysis[J]. Journal of Marketing Research, 2002, 87(100):513.

[19] HSU C Y, LU C S, PEI S C. Image feature extraction in encrypted domain with privacy-preserving SIFT[J]. IEEE Trans Image Processing, 2012, 21(11):4593-4607.

[20] WANG S M, NASSAR M, ATALLAH M, et al. Secure and private outsourcing of shape-based feature extraction[M]. Information and Communications Security. Springer International Publishing, 2013: 90-99.

[21] LI Y M, ZHOU J T, CHENG A, et al. SIFT keypoint removal and injection via convex relaxation[J]. IEEE Transactions on Information Forensics &Security, 2016, 11(8):1722-1735.

[22] WANG Q, HU S S, REN K, et al. Catch me in the dark: effective privacy-preserving outsourcing of feature extractions over image data[C]//IEEE International Conference on Computer Communications(INFOCOM). 2016:1-9.

[23] HU S S, WANG Q, WANG J J, et al. SecSIFT: privacy-preserving outsourcing computation of feature extractions over encrypted image data[J]. IEEE Transactions on Image Processing, 2016, 25(7):3411-3425.

[24] WONG W K, CHEUNG D W, KAO B, et al. Secure KNN computation on encrypted databases[C]//ACM Sigmod International Conference on Management of Data. 2009:139-152.

[25] 卓力, 龍海霞, 彭遠帆,等. 加密域圖像處理綜述[J]. 北京工業大學學報, 2016, 42(2):174-183.

ZHUO L, LONG H X, PENG Y F, et al. Image processing in encrypted domain: a comprehensive survey[J]. Journal of Beijing University of Technology, 2016, 42(2):174-183.

[26] FONTAINE C, GALAND F. A survey of homomorphic encryption for nonspecialists[J]. Eurasip Journal on Information Security, 2007, 2007(1):1-10.

[27] PAILLIER P, POINTCHEVAL D. Efficient public-key cryptosystems provably secure against active adversaries[C]//International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology. Springer-Verlag, 1999:165-179

[28] MATTON S, MOURET G, BOCQUET R, et al. Sub-image homomorphic filtering technique for improving facial identification under difficult illumination conditions[C]//International Conference on Systems, Signals & Image Processing, Iwssip, 2006: 439-473.

[29] LI L, EL-LATIF A A, NIU X. Elliptic curve elgamal based homomorphic image encryption scheme for sharing secret images[J]. Signal Processing, 2012, 92(4):1069-1078.

[30] LU W J, VARNA A L, WU M. Confidentiality-preserving image search: a comparative study between homomorphic encryption and distance-preserving randomization[J]. IEEE Access, 2014, 2: 125-141.

[31] ZHANG Y, ZHUO L, PENG Y, et al. A secure image retrieval method based on homomorphic encryption for cloud computing[C]//International Conference on Digital Signal Processing. IEEE, 2014:269-274.

[32] BELLAFQIRA R, COATRIEUX G, BOUSLIMI D, et al. Content-based image retrieval in homomorphic encryption domain.[C]//International Conference of the IEEE Engineering in Medicine and Biology Society. IEEE, 2015:2944-2947.

[33] QUELLEC G , LAMARD M , CAZUGUEL G , et al. Wavelet optimization for content-based image retrieval in medical databases.[J]. Medical Image Analysis, 2010, 14(2):227-241.

[34] BELLAFQIRA R, COATRIEUX G, BOUSLIMI D, et al. An end to end secure CBIR over encrypted medical database[C]// Engineering in Medicine and Biology Society. IEEE, 2016:2537.

[35] AHMED E D H, KALASH H M, ALLAH O S F. An efficient chaos-based feedback stream cipher (ECBFSC) for image encryption and decryption[J]. Informatica, 2007, 31(1):121-129.

[36] TONG X J, CUI M G. Feedback image encryption algorithm with compound chaotic stream cipher based on perturbation[J]. Science China(Information Sciences), 2010, 53(1):191-202.

[37] LU W J, VARNA A L, SWAMINATHAN A, et al. Secure image retrieval through feature protection.[C]//IEEE International Conference on Acoustics, Speech and Signal Processing. IEEE, 2009:1533-1536.

[38] XIA Z H, ZHU Y, SUN X, et al. A similarity search scheme over encrypted cloud images based on secure transformation[J]. International Journal of Future Generation Communication & Networking, 2013, 6(6):71-80.

[39] XIA Z H, XIONG N N, VASILAKOS A V, et al. EPCBIR: An efficient and privacy-preserving content-based image retrieval scheme in cloud computing[J]. Information Sciences, 2017, 387:195-204.

[40] FURUKAWA J. Request-based comparable encryption[C]// European Symposium on Research in Computer Security. Springer Berlin Heidelberg, 2013:129-146

[41] FURUKAWA J. Short comparable encryption[C]//International Conference on Cryptology and Network Security. Springer, Cham, 2014:337-352.

[42] AGRAWAL R, KIERNAN J, SRIKANT R, et al. Order preserving encryption for numeric data[C]//ACM SIGMOD IntConf on Management of Data. 2004:563-574.

[43] LEE S, PARK T J, LEE D, et al. Chaotic order preserving encryption for efficient and secure queries on databases[J]. IEICE Transactions on Information and Systems, 2009, 92(11):2207-2217.

[44] BOLDYREVA A, CHENETTE N, LEE Y, et al. Order-preserving symmetric encryption[C]//International Conference on Advances in Cryptology-eurocrypt, 2009:224-241.

[45] LIU D X, WANG S L. Nonlinear order preserving index for encrypted database query in service cloud environments[J]. Concurrency & Computation Practice & Experience, 2013, 25(13): 1967-1984.

[46] GAO Y Q, MIAO M X, WANG J F, et al. Secure approximate nearest neighbor search over encrypted data[C]//IntConf on Broadband & Wireless Computing. IEEE, 2015:578-583.

[47] POPA R A, REDFIELD C M S, ZELDOVICH N, et al. CryptDB: protecting confidentiality with encrypted query processing[C]// ACM Symposium on Operating Systems Principles 2011, Cascais, Portugal, DBLP, 2011:85-100.

[48] TANG Q. Privacy preserving mapping schemes supporting comparison[C]//2010 ACM Workshop on Cloud Computing Security Workshop. 2010:53-58.

[49] CHEN P, YE J, CHEN X F. Efficient request-based comparable encryption scheme based on sliding window method[J]. Soft Computing, 2016, 20(11):4589-4596.

[50] ZOU Q, WANG J F, YE J, et al. Efficient and secure encrypted image search in mobile cloud computing[J]. Soft Computing, 2017, 21(11): 2959-2969.

[51] LU W J, SWARMINATHAN A, VARNA A, et al. Enabling search over encrypted multimedia databases[C]//Media Forensics and Security. International Society for Optics and Photonics, 2009: 725411-725418.

[52] YAO A C. How to generate and exchange secrets[C]//Foundations of Computer Science, Symposium on. IEEE, 2008:162-167.

[53] 申立艷, 陳小軍, 時金橋,等. 隱私保護集合交集計算技術研究綜述[J].計算機研究與發展, 2017, 54(10):2153-2169.

SHEN L Y, CHEN X J, SHI J Q, et al. Survey on private preserving set intersection technology[J]. Journal of Computer Research and Development, 2017, 54(10):2153-2169.

[54] LINDELL Y, PINKAS B. A proof of security of yao’s protocol for two-party computation[J]. Journal of Cryptology, 2009, 22(2): 161-188.

[55] HUANG Y, EVANS D, KATZ J, et al. Faster secure two-party computation using garbled circuits[C]//Usenix Conference on Security. USENIX Association, 2011:35-35.

[56] ZHANG L, JUNG T, FENG P, et al. PIC: enable large-scale privacy preserving content-based image search on cloud[C]// International Conference on Parallel Processing. IEEE, 2015:1-1.

[57] SHEN M, CHENG G, ZHE L, et al. Content-based multi-source encrypted image retrieval in clouds with privacy preservation[J]. Future Generation Computer Systems, 2018:1-13.

[58] JUNG T, LI X Y, WAN M. Collusion-tolerable privacy-preserving sum and product calculation without secure channel[J]. 2015, 12(1):45-57.

[59] FERREIRA B, RODRIGUES J, LEITAO J, et al. Towards an image encryption scheme with content-based image retrieval properties[J]. Lecture Notes in Computer Science, 2015: 311-318.

[60] CHENG H, ZHANG X, YU J, et al. Encrypted JPEG image retrieval using block-wise feature comparison[J]. Journal of Visual Communication & Image Representation, 2016, 40:111-117.

[61] CHENG H, ZHANG X, YU J. AC-coefficient histogram-based retrieval for encrypted JPEG images[J]. Multimedia Tools and Applications, 2015, 75(21):13791-13803.

[62] 韓威, 申銘, 徐彥彥,等. 一種云環境下JPEG圖像的安全檢索方法[J].計算機應用研究, 2017(4):1239-1243.

HAN W, SHEN M, XU Y Y, et al. Secure JPEG image retrieval method under cloud environment[J]. Application Research of Computers,2017(4):1239-1243.

[63] HUANG K, XU M, FU S J, et al. Efficient privacy-preserving content-based image retrieval in the cloud[C]//International Conference on Web-Age Information Management. Springer Inter-national Publishing, 2016:28-39.

[64] HUANG Y, ZHANG J, PAN L, et al. Privacy protection in interactive content based image retrieval[J]. IEEE Transactions on Dependable & Secure Computing, 2018:1-1.

[65] ZHU Y, SUN X M, XIA Z H, et al. Enabling similarity search over encrypted images in cloud[J]. Information Technology Journal, 2014, 13(5):824-831.

[66] ZHU Y, SUN X M, XIA Z H, et al. Secure similarity search over encrypted cloud images[J]. International Journal of Security & Its Applications, 2015, 9(8): 1-14.

[67] XIA Z H, ZHU Y, SUN X M, et al. Towards privacy-preserving content-based image retrieval in cloud computing[J]. IEEE Transactions on Cloud Computing, 2015, 6(1): 276-286.

[68] XIA Z H, WANG X H, ZHANG L G, et al. A privacy-preserving and copy-deterrence content-based image retrieval scheme in cloud computing[J]. IEEE Transactions on Information Forensics & Security, 2016, 11(11):2594-2608.

Survey on the privacy-preserving content based image retrieval

WU Ying1, LI Xuan1,2,3, JIN Biao1, JIN Rongrong1

1. College of Mathematics and Informatics, Fujian Normal University, Fujian 350100, China 2. Fujian Provincial Key Lab of Network Security & Cryptology, Fujian 350100, China 3. Digital Fujian Big Data Security Technology Institute, Fujian 350100, China

With the widespread popularity of smart devices and social media, the number of image data is exponentially increasing. The data owners tend to outsource the local data to the cloud servers, where data is stored, shared and retrieved. However, the content of users’ image data contains a lot of sensitive information, which may be exposed to the attackers and the incomplete trusted cloud servers, resulting in a serious risk of privacy leakage to users. The research progress of the content-based image retrieval technology under the privacy-preserving in recent years were reviewed, and the key image cryptographic technology were summarized, including homomorphic encryption, randomized encryption and comparative encryption. Around these techniques, the typical solutions are analyzed and compared in detail, and the improvement strategies of index construction are introduced. Finally, the future research directions are discussed.

privacy-preserving, content-based image retrieval, symmetric searchable encryption, cloud computing security

TP391.41

A

吳穎（1995? ），女，福建漳州人，福建師范大學碩士生，主要研究方向為隱私保護。

李璇（1984? ），女，湖北黃石人，博士，福建師范大學副教授，主要研究方向為云數據安全與隱私保護。

金彪（1985? ），男，安徽六安人，博士，福建師范大學講師，主要研究方向為信息安全。

金榕榕（1998? ），女，江西南昌人，主要研究方向為計算機視覺和圖像處理。

2018?12?11；

2019?01?08

李璇，jessieli24@163.com

國家自然科學基金資助項目（No.61872090，No.61872086）；福建省自然科學基金資助項目（No.2017J05099）

10.11959/j.issn.2096?109x.2019035

s: The National Natural Science Foundation of China (No.61872090, No.61872086), The Natural Science Foundation of Fujian Province (No.2017J05099)

吳穎, 李璇, 金彪, 等. 隱私保護的圖像內容檢索技術研究綜述[J]. 網絡與信息安全學報, 2019, 5(4): 14-28.

WU Y, LI X, JIN B, et al. Survey on the privacy-preserving content based image retrieval[J]. Chinese Journal of Network and Information Security, 2019, 5(4): 14-28.