基于邊緣計算的支持多密鑰的加密圖像檢索

李穎瑩，馬建峰，苗銀賓

（1.西安電子科技大學網絡與信息安全學院，陜西 西安 710071；2.陜西省網絡與系統安全重點實驗室，陜西 西安 710071）

1 引言

隨著圖像設備如數碼相機、智能手機迅速更新換代，以及各種圖像應用層出不窮，圖像數據呈爆炸式增長趨勢，大大增加了用戶本地數據計算和存儲負擔。資源受限的用戶借助云計算服務將數據外包至云服務器。但是在萬物互聯的時代，僅依靠以云計算為代表的集中式計算模式不足以支持海量數據處理，不能有效解決服務負載、傳輸帶寬等問題，無法滿足數據實時性處理需求。因此，以邊緣計算為代表的分布式計算模式應運而生，為海量移動設備提供最近端服務，相比以云計算為代表的集中式計算模式節省了大量計算、傳輸和存儲成本。但另一方面，外包至邊緣計算節點的圖像數據由于脫離了用戶的實際掌控而面臨隱私泄露問題。為此，用戶將加密后的圖像數據外包至邊緣計算節點。盡管加密算法能在一定程度上保證圖像數據安全，但會影響圖像檢索在密文上的應用。

傳統的明文圖像檢索主要采用基于文本的圖像檢索（TBIR,text-based image retrieval）和基于內容的圖像檢索（CBIR,content-based image retrieval）2 種方法。其中，基于文本的圖像檢索方法是用文本對圖像進行人工標記，受人為主觀影響導致查詢準確率低?；趦热莸膱D像檢索方法用圖像本身的顏色、紋理和形狀信息客觀描述圖像內容，大大提高了查詢準確率。目前，如何在密文上應用明文CBIR 技術是加密圖像檢索研究的重點之一。Lu 等[1-2]提出基于CBIR 的加密圖像檢索方案，并用同態加密算法保護圖像特征向量；Zhang 等[3]利用同態加密和屬性基加密技術實現大規模加密圖像檢索；Xia 等[4]基于詞袋模型和地球移動距離設計了一個安全CBIR 方案。盡管基于同態加密和可搜索加密技術可以實現加密圖像檢索[5-7]，但是如果將這些支持單密鑰的傳統圖像檢索方案直接應用到實際多密鑰場景中，查詢用戶必須生成多個陷門。例如，在電子醫療系統中，醫生想要查詢其他3 個醫院的醫療圖像庫。如圖1(a)所示，這3 個醫院的醫療圖像庫由各自密鑰加密，通過系統認證的醫生需要發送3 個查詢請求才能達到檢索目的。當系統中醫院數目增多時，醫生實現檢索目的所需的計算開銷和通信開銷隨之增多。如果醫生只需要生成一個查詢請求就可以檢索其他所有醫院的醫療圖像庫，如圖1(b)所示，用戶只需生成一個查詢陷門即可查詢不同密鑰加密的圖像集，這將大大減小用戶的計算與通信開銷。

然而，已有的加密圖像檢索方案[1-2,4-12]大多不支持多密鑰加密圖像檢索，僅有的支持多密鑰加密圖像檢索的方案[3,13]由于涉及復雜的安全多方計算和同態加密技術，導致實用性受到影響。因此，需要設計一種支持多密鑰的加密圖像檢索方案，解決以下關鍵問題：1)所有外包至邊緣服務器的數據都應進行加密，使服務器無法根據密文獲取明文相關信息；2)每個圖像查詢用戶應該以盡可能低的開銷查詢不同密鑰加密的圖像，以便實現云端數據共享；3)檢索結果應滿足查詢要求，檢索時間應滿足實時性需求，以保證方案的準確性和高效性。

圖1 方案背景比較

為解決以上問題，本文基于局部敏感哈希算法、安全近鄰算法及代理重加密等技術提出了基于邊緣計算的支持多密鑰的加密圖像檢索方案。局部敏感哈希算法在生成索引時將相似圖像映射到同一個桶中，能有效減小圖像檢索時間，保證方案的高效性。安全近鄰算法利用隨機向量分裂和可逆矩陣加密向量，可快速實現圖像相似度的安全計算，保證方案的安全性和準確性。代理重加密技術能夠幫助代理服務器進行不同加密密鑰密文之間的轉換，將擁有者加密的密文轉換成查詢用戶可解密的形式，以此減少多擁有者/多密鑰場景下查詢用戶的開銷。邊緣計算具有低時延、高可用、高實時的優勢，能克服云計算模式中因數據遷移、網絡傳輸造成過多帶寬資源消耗的不足，為用戶提供高質量服務。本文基于這些算法和技術提出基于邊緣計算的、支持多密鑰的加密圖像檢索方案，其具有以下特點。

1)多密鑰場景。提出了一種多密鑰場景下的加密圖像檢索方案，查詢用戶僅需生成一個查詢陷門即可對不同密鑰加密的圖像進行檢索，比傳統方案更實用，用戶計算負擔更小。

2)訪問控制。實現了對圖像查詢用戶的訪問控制，邊緣服務器重加密圖像加密密鑰后，用戶只能用合法分配的私鑰解密。密鑰中心為每個查詢用戶分發不同的私鑰，即使其他用戶竊取查詢結果，也不能解密出明文。

3)高安全性。在用圖像特征向量的內積表示圖像之間的相似度時，所提方案在特征向量中加入了冗余項，以此提高了服務器端相似度計算的安全性。

2 相關工作

密文檢索主要涉及文本領域和圖像領域。關于文本檢索的多密鑰場景，Yin 等[14]利用隨機密鑰為不同數據建立索引，同時用戶選擇其他隨機密鑰生成陷門而不影響密文匹配，減少了密鑰管理復雜度，但不支持細粒度訪問控制。Sun 等[15]利用屬性基加密和代理重加密技術設計了支持細粒度訪問控制的密文檢索方案，且支持數據用戶的屬性撤銷，避免了用戶與擁有者直接交互。不同于密鑰和數據一一對應，Miao等[16]針對共享型數據的多密鑰場景，利用多重簽名技術提出了高效可驗證的關鍵字檢索方案，可抵抗選擇關鍵字攻擊，后來又擴展到連接多關鍵字模型[17]，提出既支持連接多關鍵字又可進行結果驗證的高效檢索方案，能夠抵抗離線關鍵字猜測攻擊。

上述方案都是針對文本檢索的研究，圖像不像文本那樣可用關鍵字進行準確唯一標記，從而導致基于關鍵字的密文檢索方案無法直接應用于圖像領域。Lu 等[1]提出了基于CBIR 的加密圖像檢索方案，允許圖像進行相似性匹配，但是沒有考慮明文圖像和加密圖像之間的距離變化。針對這一問題，Lu 等[8]采用了保序加密和Min-hash 方案，但是該方案局限于用視覺單詞描述圖像特征。Zhang 等[9]利用同態加密性質解決了距離變化問題，并用歐氏距離作為圖像相似性度量，然而同態的使用大大增加了方案計算開銷。為減小計算開銷，Xia 等[10]基于圖像的全局特征利用局部敏感哈希算法構建索引，實現了高效的加密圖像檢索。Yuan 等[11]基于多項式性質提出了支持訪問控制的加密圖像檢索方案，并設計了安全k-means 外包算法。

盡管以上方案實現了加密圖像檢索，甚至具有高效率和訪問控制功能，但是這些方案均針對單密鑰場景，無法滿足實際需求中的多密鑰場景。Liang等[12]針對多個查詢用戶設計了多密鑰非對稱內積加密算法，為不同查詢用戶分發不同密鑰，同時利用全局優化和高斯分布提高密鑰安全性和空間利用率，但是該方案不支持在多個密鑰加密的圖像集上檢索。Shen 等[13]和Zhang 等[3]分別利用安全多方計算和多密鑰同態加密提出了支持多擁有者-多用戶的加密圖像檢索方案，盡管前者通過簡化歐氏距離計算方法，后者借助并行計算模式來減小計算開銷，但方案的實用性仍受計算和通信開銷影響。為減小開銷，王祥宇等[18]通過設計輕量級密鑰轉換協議來實現多用戶加密圖像檢索方案。此外，文獻[19-21]提出了多密鑰背景下的可搜索加密方案，但是尚未實現圖像檢索。

針對已有方案絕大多數不支持多密鑰加密的圖像檢索或者多密鑰加密的圖像檢索方案效率較低的問題，本文結合局部敏感哈希算法、安全近鄰算法和代理重加密技術，利用邊緣計算模式數據就近處理原則，提出基于邊緣計算的支持多密鑰的圖像檢索方案。表1 給出了本文方案與其他方案的比較。從表1 可以看出，本文方案能同時滿足多密鑰場景、訪問控制、已知背景攻擊安全和高效率這4 個要求。

表1 本文方案與其他方案的比較

3 預備知識

本文方案主要運用基于雙線性對的代理重加密技術解決多密鑰轉換問題，應用局部敏感哈希算法提高檢索速度，其中哈希函數屬于p穩態局部敏感哈希函數。本節分別介紹代理重加密和局部敏感哈希的相關定義。

定義1雙線性對[22]。設G,GT是2 個階為素數p的乘法循環群，g是G的一個生成元。雙線性對e:G×G→GT有以下性質。

1)可計算性。存在一個有效算法可計算e。

2)雙線性。對任意u,v∈G和a,b∈Zp，都有e(ua,vb)=e(u,v)ab。

3)非退化性。e(g,g)≠ 1。

定義2代理重加密[23]。一個代理重加密方案由算法KeyGen、ReKey、Encrypt、ReEncrypt、Decrypt構成。

1)(pki,ski)←KeyGen(1κ)。輸入安全參數κ，為用戶i輸出公私鑰對(pki,ski)。

2)rkA→B←ReKey(pkA,skA,pkB,skB)。輸 入Alice 的公私鑰對(pkA,skA)和Bob 的公私鑰對(pkB,skB)，輸出代理重加密密鑰rkA→B，其中，Alice為委托者，Bob 為被委托者。

3)ci←Encrypt(pki,m)。輸入用戶i的公鑰pki和消息m，輸出密文ci。

4)cB←ReEncrypt(rkA→B,cA)。輸入代理重加密密鑰rkA→B和Alice 的密文cA，輸出Bob 可解密的密文cB。

5)m←Decrypt(ski,ci)。輸入用戶i的公鑰ski和密文ci，輸出消息m或錯誤符號⊥表示ci不合法。

定義3p穩態局部敏感哈希[24-25]。給定距離R、cR，概率值P1、P2，其中c＞ 1，P1＞P2，稱函數族H 是(R,cR,P1,P2)敏感。對任意2 個d維向量u,v∈Rd和任意函數h∈H。

此處，函數h為p穩態局部敏感哈希函數，形如，其中，a是每維服從p穩態分布的d維向量，b是一個服從[0,r)均勻分布的實數，r是一個常數。

4 系統模型、威脅模型及安全目標

4.1 系統模型

本文方案包括4 個實體，即密鑰生成中心、圖像擁有者、圖像查詢用戶和邊緣服務器，系統模型如圖2 所示。完全可信的密鑰生成中心負責系統初始化和密鑰分配，圖像擁有者將加密圖像、加密密鑰密文和加密索引上傳到邊緣服務器存儲，查詢用戶將查詢陷門發送給邊緣服務器，邊緣服務器則根據陷門匹配加密索引獲取候選圖像集列表，然后重加密候選圖像集對應的密鑰密文，最后將密鑰和候選圖像集作為檢索結果返回給查詢用戶。

圖2 系統模型

1)密鑰生成中心。為圖像擁有者和查詢用戶生成密鑰。如圖2 中①所示。

2)圖像擁有者。加密圖像集和圖像加密密鑰，計算轉換密鑰，構建加密索引，最后將加密圖像、加密密鑰密文和加密索引上傳給邊緣服務器。如圖2 中②所示。

3)圖像查詢用戶。加密查詢圖像的特征向量，生成查詢陷門發送給邊緣服務器。如圖2 中③所示。

4)邊緣服務器。根據查詢用戶發送的陷門和擁有者發送的加密圖像、加密索引進行查詢，對圖像加密密鑰進行重加密，最后將搜索結果和重加密密鑰密文返回給用戶。如圖2 中④～⑨所示。另外，圖2 中⑩表示沒有密鑰的非法用戶即使竊取檢索結果也不能解密出明文。

4.2 威脅模型

在本文方案中，假設邊緣服務器是半可信的，即服務器會誠實且正確地執行協議，同時也會積極獲取加密圖像的明文信息。此外，假設圖像擁有者和查詢用戶是可信的，且查詢用戶和服務器之間不會相互合作。根據服務器可獲得的知識將攻擊模型總結為以下2 種。

已知密文攻擊模型[26]。服務器只知道從圖像擁有者端外包而來的加密圖像集和加密索引以及來自圖像查詢用戶的查詢陷門。

已知背景攻擊模型[27]。與已知密文攻擊模型相比，服務器擁有更多背景知識，如額外獲得一些查詢陷門對應的明文、圖像明文等。

4.3 安全目標

基于4.2 節定義的威脅模型，本文安全目標主要是防止半可信服務器從圖像密文集、索引集、密鑰密文集、陷門和內積計算結果中獲取有效信息。

1)圖像隱私。服務器從加密圖像集中不能解密明文圖像，也不能獲取明文圖像相關信息。

2)索引隱私。服務器不能解密加密索引表，更不能解密索引表中的特征向量。

3)密鑰隱私。服務器在進行重加密操作時，不能獲取擁有者和查詢用戶的私鑰，也不能解密圖像加密密鑰。

4)陷門隱私。服務器根據陷門無法得知查詢圖像的明文信息，也不能判斷陷門之間的關系。

5)內積計算隱私。服務器從加密向量內積計算結果中無法知道明文向量內積值，同時應用統計分析也不能獲取任何明文信息。

5 支持多密鑰的加密圖像檢索方案

由于不同擁有者的圖像加密密鑰不同，致使查詢用戶不能用同一個陷門查詢圖像集。如果將支持單密鑰的傳統圖像檢索方案直接應用于實際多密鑰場景，會為用戶帶來額外開銷；而且傳統云計算模式在數據存儲、傳輸方面消耗大量帶寬資源，無法滿足實時處理數據的需求。為解決這些問題，本節提出基于邊緣計算的支持多密鑰的加密圖像檢索方案。方案利用代理重加密技術實現圖像加密密鑰的密文轉換，應用局部敏感哈希算法提高檢索速度，再用安全近鄰算法提高檢索精度和安全性，基于邊緣計算模式節約數據在服務器和終端設備之間的傳輸鏈路資源。

5.1 方案定義

在對本文方案進行詳細描述之前，給出方案定義。首先，定義方案中用到的符號，如表2 所示。

表2 符號定義

其次，定義本文方案主要包含的7 種算法。

1)(G,Γ,k,sk,pk)←KeyGen(1κ)。給定安全參數κ，密鑰生成中心輸出系統參數G 和Γ、圖像加密密鑰k、私鑰sk 和公鑰pk。

2)C←ImgEnc(k,M)。圖像擁有者用加密密鑰k加密明文圖像M，輸出密文圖像C。

3)Λ←KeyTrans(k,pk,sk)。圖像擁有者將圖像加密密鑰k加密成k′，并生成轉換密鑰TKUID，輸出重加密密鑰Λ。

4)I←IndexGen(Γ,M)。圖像擁有者用參數Γ對明文圖像M的特征向量進行預處理并加密特征向量，輸出加密索引I。

5)TD ←TrapdoorGen(Γ,mq)。圖像查詢用戶利用參數Γ對查詢圖像mq的特征向量進行預處理并加密特征向量，輸出查詢陷門TD。

6)R←Search(C,Λ,I,TD)。邊緣服務器根據查詢陷門TD 匹配索引集I，在圖像密文集C中搜索符合查詢要求的密文，將密文結果對應的擁有者密鑰k′重加密成，輸出檢索結果R。

7)M′←ImgDec(R,sk)。圖像查詢用戶用自己的私鑰sk 解密出圖像加密密鑰，進一步解密出明文圖像。

5.2 方案描述

本節從7 個階段描述本文方案的具體步驟，即密鑰生成階段KeyGen、圖像加密階段ImgEnc、密鑰轉換階段KeyTrans、索引生成階段IndexGen、陷門生成階段TrapdoorGen、檢索階段Search 和圖像解密階段ImgDec。其中，除密鑰生成階段外其他6個階段流程如圖3 所示。

5.2.1 密鑰生成階段

(G,Γ,k,sk,pk)←KeyGen(1κ)。密鑰生成中心輸入參數κ，輸出雙線性對參數和秘密參數，其中，s為一個d+1 維隨機二值向量，A1和A2為2個(d+1)×(d+1)維隨機可逆矩陣，為λ個哈希函數，為局部敏感哈希函數族，為L個哈希表的加密函數。密鑰生成中心為擁有者分配圖像加密密鑰和公私鑰對(sko,pko)，滿足，為u個用戶分配公私鑰對，身份為UID 的用戶分配到公私鑰對，滿足。需要說明圖像擁有者知道查詢用戶的公私鑰。

圖3 方案執行流程

5.2.2 圖像加密階段

C←ImgEnc(k,M)。圖像擁有者利用圖像加密密鑰ki將明文圖像集Mi加密成密文圖像集Ci，將w個不同密鑰加密的密文圖像集發送給邊緣服務器存儲。

5.2.3 密鑰轉換階段

Λ←KeyTrans(k,pk,sk)。圖像擁有者首先將圖像加密密鑰ki加密成，其中，εi為隨機數，F為雙線性對，即F=e(g,g)。接著為UID 的用戶計算轉換密鑰，則ki對應的重加密密鑰為。最后，w個重加密密鑰組成發送給邊緣服務器。

5.2.4 索引生成階段

I←IndexGen(Γ,M)。索引生成階段分兩步完成，第一步為生成未加密的索引表，第二步為加密索引表。

1)生成未加密的索引表。對于圖像集Mi中每幅圖像mi,t，先提取特征向量，其中t∈[1,ni]，ni為Mi所含圖像總數。然后將λ個哈希函數h1,h2,…,hλ作用于向量fi,t，得到λ個哈希值。接著將L個ψ(?)作用于fi,t，構造L個哈希表，即為未加密索引表，表中每個桶的值為，其中j∈[1,L]，b∈[1,Ni,j]，Ni,j為第j個哈希表中桶的數目。如表3 所示，圖像mi,t的特征向量fi,t和其相應圖像信息標識符ID(mi,t)共同存儲在哈希表中。第j個表有Ni,j個哈希桶，同一個哈希桶中的圖像是相似的。

2)加密索引表。用函數?(?)加密桶值，用文獻[28]中安全近鄰算法加密特征向量。具體地，將d維圖像特征向量擴展成維向量，再根據隨機二值向量s將分裂成兩部分。分裂規則為，對于時，有；否則，為隨機賦予正值，使其滿足。接著用隨機可逆矩陣和分別乘，可得加密后的特征向量。表4 給出加密后的第j個哈希表。L個加密后的哈希表構成索引表Ii。擁有者將w個Mi生成的索引表發送給邊緣服務器。

表3 第j個哈希表

表4 加密后的第j個哈希表

5.2.5 陷門生成階段

TD ←TrapdoorGen(Γ,mq)。與索引生成階段類似，查詢用戶首先提取查詢圖像mq的特征向量，然后用ψj(?)計算桶值BKTj，，用?(?)加密桶值為。接著用戶將fq擴展為，對于l∈[1,d+1]，若，則為隨機賦予正值，使其滿足；否則，。再隨機選取正數δ∈R+，用分別乘以，得到加密查詢向量。最后和用戶身份UID 組成陷門,UID}發送給邊緣服務器，由邊緣服務器進行檢索。

5.2.6 檢索階段

R←Search(C,Λ,I,TD)。檢索階段分兩步完成，第一步為計算相似度，第二步為重加密密鑰。

1)計算相似度。邊緣服務器接收到查詢陷門TD 后，首先在索引表里找到與陷門桶值相同的桶，桶里面的圖像即為候選圖像集。然后計算候選圖像集的特征向量與查詢圖像特征向量之間的內積值，計算過程如式(1)所示。

邊緣服務器依次計算候選列表中每幅圖像mi,t與查詢圖像mq的內積值，根據內積值大小排序選出前r個最相似的加密圖像。

2)重加密密鑰。邊緣服務器根據r個加密圖像對應的密鑰密文及用戶身份UID 對應的轉換密鑰TKUID計算，計算過程如式(2)所示。

邊緣服務器將r個加密圖像和對應的重加密密鑰作為檢索結果返回給查詢用戶。

5.2.7 圖像解密階段

M'←ImgDec(R,sk)。收到檢索結果的查詢用戶用其合法私鑰skUID計算加密密鑰，如式(3)所示。

得到圖像加密密鑰ki，用來解密出相應明文圖像。若用戶無合法私鑰skUID，則不能解密重加密密鑰密文，更不能解密圖像密文。

本節介紹的方案主要利用代理重加密技術完成密鑰轉換，借助局部敏感哈希算法提高檢索效率，應用安全近鄰算法計算內積提高檢索精度，其中內積計算方法只能保證唯密文安全，不可抵抗已知背景攻擊。如若敵手獲得一組明密文對(f,f′)和一組陷門明密文對，以及明文圖像子集P，計算內積，由此獲得隨機數δ取值，進而可判斷檢索結果中其他圖像與查詢圖像明文之間的關系。針對這一問題，下面對此方案（基礎方案）做出改進，使其能夠抵抗已知背景攻擊。

6 改進方案

為使本文方案能夠抵抗已知背景攻擊，對相似度計算方法進行改進，在特征向量中添加部分冗余項，其他步驟不變。雖然添加冗余項會影響檢索精度，但為提高安全性，本文方案可以適當妥協。下面對需改動的階段進行說明，對無影響的ImgEnc、KeyTrans 和ImgDec 階段不予說明。

KeyGen將d+1維隨機二值向量s擴充成d+α+1維，(d+1)×(d+1)維隨機可逆矩陣A1和A2也擴充成(d+α+1)×(d+α+1)維，另外增加α維隨機向量η組成冗余項。其余參數不變。

I ndexGen 針對特征向量加密過程，將d維特征向量擴展成d+α+1維向量，其中。隨機分裂和矩陣加密步驟與基礎方案一致，得出加密后的向量。

TrapdoorGen針對查詢圖像qm的特征向量加密過程，將d維特征向量擴展成，其中β為α維的隨機二值向量。后續隨機分裂和矩陣加密步驟與基礎方案一致，得到加密后的查詢向量。

Search向量內積計算形式變化為

由式(4)可以看出，改進方案中內積計算結果比基礎方案多出了冗余項βηT。這將提高內積計算結果的安全性，7.1 節會給出具體分析。

7 方案分析

本節將分析所提方案的安全性及理論性，同時使用真實數據集進行實際性能測試。

7.1 安全性分析

本文方案能夠達到所提的安全目標，具體分析如下。

1)圖像隱私。本文采用傳統對稱密鑰加密算法加密圖像，圖像隱私的安全性依賴于加密算法，安全的加密算法能有效防止圖像隱私泄露。

3)密鑰隱私。雖然服務器根據重加密密鑰可以控制查詢用戶的訪問，但是從中解密出圖像擁有者私鑰sko和圖像查詢用戶私鑰skUID依賴于離散對數困難問題的解決。沒有skUID的服務器無法從計算結果FεiskUID中獲得圖像加密密鑰k。同樣，沒有被授權的用戶因為沒有合法的公私鑰也無法解密出圖像加密密鑰。

4)陷門隱私。與索引隱私相同，只要不泄露隨機向量s和隨機矩陣A1、A2，查詢向量就不會被泄露。另外，隨機數δ的引入保證了陷門之間沒有關聯，使邊緣服務器無法通過陷門判斷每次查詢圖像是否相同。

5)內積計算隱私。雖然邊緣服務器根據計算結果可知圖像間的相似度，但是由于δ和βηT的存在無法恢復出圖像之間的距離。另外，為體現冗余項的干擾作用，2 個冗余項βηT有相同取值的可能性應小于，即對每一個fi,t，βηT至少有2γ個不同取值。而βηT的總數不大于，其中|β|為β中1出現的次數。當值最大。即，當α=2γ，|β|=γ時，有，因此每個fi,t至少含有2γ個冗余項，每個fq從中隨機選取一半的冗余項。為盡可能不影響排序結果的精確性，βηT應服從正態分布。令隨機向量η的每一維ηi服從均勻分布，可知均值和方差分別為μ′和。根據中心極限定理，對于γ個獨立同分布隨機變量ηi，其和近似服從正態分布。令，也就是，有βηT服從正態分布N(μ,σ2)。此時，方案的精確性和安全性隨σ2變化而變化，σ2越大，安全性越高，精確度越低；σ2越小，安全性越低，精確度越高。更具體的證明可參考文獻[29]。此外，根據內積計算形式，可以證明在已知背景攻擊模型下對于多項式時間敵手，加密圖像集和查詢陷門是安全的。

定理1對于多項式時間敵手，內積計算在已知背景攻擊模型下可保證加密圖像集和陷門安全。

在已知背景攻擊模型中，敵手可接觸加密圖像集、加密索引表和陷門集，獲取其他背景知識，如一組明密文對和陷門明密文對，以及明文圖像子集。假設敵手為，其中，為加密向量集，為陷門集，為明文向量集，為一組明密文對，為一組陷門明密文對。需要說明的是，即使敵手知道加密特征向量集C，也無法知道P中明文特征向量對應的密文形式，更無法得知P和C之間的對應關系。

證明圖像向量之間的相似度可由式(5)度量。

其中，δ和Tβη均未知，且加密后的特征向量不會泄露明文特征向量信息，即使已知明文向量集P，敵手在多項式時間內也無法暴力破解。因此在已知背景攻擊模型下，敵手無法獲得加密數據集和陷門的明文形式。

證畢。

需要說明的是，為了實現高效加密圖像檢索方案，有必要泄露最少的信息給邊緣服務器。例如邊緣服務器很容易知道在同一個哈希桶中的圖像是相似的，同樣也知道檢索結果里的圖像是相似的。如果想要避免這些信息泄露，可以采用文獻[30]中的方案。但考慮到其復雜度過高，效率低下，且遠未達到實用程度，本文暫不解決這些問題。

7.2 性能分析

下面分別從理論和實際性能2 個方面與文獻[13]方案（MIPP,multiple image owners with privacy protection）對比，論證本文方案（基礎方案、改進方案）的可行性。理論分析涉及計算開銷和存儲開銷。實際性能主要對KeyGen、KeyTrans、IndexGen、Search 這4 個階段以及檢索精度進行仿真實驗。

7.2.1 計算開銷分析

表5 給出了3 種方案的理論計算開銷對比。本文主要考慮了幾種比較耗時的密碼運算，即群Zp指數運算、群G指數運算、群GT指數運算、雙線性對運算E、哈希運算H、矩陣運算M′、M′以及MIPP 中群指數運算Gq和加法運算。另外，圖像加解密采用傳統對稱加解密算法，在此不予分析。

表5 中，w表示圖像擁有者個數，d表示提取出的特征向量維數，d′表示基礎方案中加密特征向量維數，d′表示改進方案中加密特征向量維數，n表示圖像總數，L表示哈希表個數，λ表示哈希函數個數，r′表示檢索結果中來自不同密鑰加密的圖像種類，符號“—”表示不存在。

由表5 可看出，在KeyGen 階段，密鑰生成時間隨圖像加密密鑰個數增加而增加，方案改進前后向量維數增多使密鑰生成時間也增多。在KeyTrans階段，密鑰轉換時間受密鑰個數影響，密鑰個數越多，密鑰轉換時間越多。但方案改進前后，該階段計算開銷保持一致。在IndexGen 階段，索引生成時間與圖像總數呈正相關，特別是改進方案中矩陣維數增加，因此改進方案的索引生成時間比基礎方案多。在TrapdoorGen 階段，考慮一個用戶的一次查詢，陷門生成時間主要受矩陣計算、哈希計算以及特征向量維數影響。在Search 階段，計算開銷主要受向量維數或加密密鑰個數影響。根據以上幾個階段的分析，改進方案比基礎方案計算開銷增大或者保持一致，主要是因為特征向量維數增大，但以此為代價可換來安全性的提高。由于MIPP 沒有進行密鑰轉換，因此只列出了其他4 個階段。可以看出，MIPP 每個階段的計算開銷與群指數運算密切相關，而本文方案只有2 個階段的開銷受群指數運算影響。

7.2.2 存儲開銷分析

表6 中，w表示圖像擁有者個數，d表示提取出的特征向量維數，d′表示基礎方案中加密特征向量維數，d′′表示改進方案中加密特征向量維數，n表示圖像總數，L表示哈希表個數，符號“—”表示不存在。

表5 3 種方案的理論計算開銷對比

表6 3 種方案的理論存儲開銷對比

由表6 可以看出，在KeyGen 階段，需要存儲公私鑰、圖像加密密鑰以及系統秘密參數。假設用戶個數為1，存儲開銷隨圖像擁有者個數和特征向量維數增加而增加。在KeyTrans 階段，存儲開銷隨圖像擁有者個數增長而增長。該階段存儲開銷在方案改進前后不變。在IndexGen 階段，索引存儲開銷和圖像總數呈正相關。當給定圖像個數時，圖像特征向量的維數會影響索引存儲開銷。在TrapdoorGen 階段，考慮一個用戶的一次查詢，陷門存儲開銷主要受向量維數影響。根據以上4 個階段的存儲開銷分析可以看出，改進方案比基礎方案的存儲開銷大是由特征向量維數增加造成的，但增加的維數與圖像明文特征向量維數對比可以忽略。與MIPP 對比，本文方案存儲開銷受較多因素影響，但從后續實驗可看出本文方案存儲開銷是可接受的。

7.2.3 實際性能

為測試本文方案的實際性能，基于Corel100 數據集[31]，從每一類中分別取20、40、60、80、100幅圖像組成2 000、4 000、6 000、8 000、10 000 幅圖像，并提取圖像的CLD 特征[32]。實驗環境為PC機（i5-4590 主頻3.3 GHz，內存為4 GB，操作系統為Win7 64b），實驗工具采用Python2.7。圖4～圖8展示了本文方案在KeyGen、KeyTrans、IndexGen、Search 這4 個階段以及檢索精度上與MIPP 的比較。由于本文著重研究加密圖像檢索方法，而不是圖像加密方法，且陷門生成本質上為索引生成n=1 的情況，因此文中沒有測試 ImgEnc、ImgDec 和TrapdoorGen 這3 個階段的開銷。

在KeyGen 階段，假設一個擁有者對應一個加密密鑰，從圖4(a)可看出，MIPP 的時間開銷增幅最大?；A方案和改進方案的時間開銷非常接近，說明特征向量維數變化對時間開銷影響很小。特別地，當用戶個數分別為1 和10 時，改進方案生成50 個密鑰所需時間分別為1.7 s 和1.9 s 左右。圖4(b)中本文方案存儲開銷增長緩慢。特別地，當用戶個數分別為1 和10 時，改進方案生成50 個密鑰所需存儲空間分別為243 KB 和251 KB 左右。雖然維數增多導致開銷增長，但同時也提高了方案的安全性。

圖4 KeyGen 階段

圖5 KeyTrans 階段

在KeyTrans 階段，僅考慮本文方案開銷，如圖5所示，特征向量維數變化不影響基礎方案和改進方案的開銷。隨著用戶數增加，需要的轉換密鑰相應增加。特別地，當用戶個數分別為1 和10 時，轉換50 個密鑰所需時間分別為8 s 和68 s 左右，所需存儲空間分別為160 KB 和1 400 KB 左右。為實現多密鑰場景，密鑰轉換時間和存儲開銷隨密鑰個數增多是不可避免的。但這只是一次性操作，相比于圖像加密所帶來的巨額開銷是可接受的。

在IndexGen 階段，如圖6 所示，時間開銷和存儲開銷隨圖像總數增多而增加。本文方案索引生成時間開銷明顯少于MIPP，存儲開銷增加是因為存儲了加密向量。方案改進前后增長趨勢接近，說明向量維數增加帶來的影響很小。特別地，當圖像總數為10 000 幅時，方案改進前后生成索引所需時間分別約為117 ms 和123 ms，所需存儲空間分別約為10.5 MB 和11.5 MB。

圖6 IndexGen 階段

在Search 階段，僅考慮檢索時間開銷，如圖7所示。方案改進前后的時間開銷很接近，說明向量維數變化不會明顯影響檢索時間。隨圖像總數增加，檢索時間增長趨勢不明顯，這是因為局部敏感哈希有效縮短了檢索時間。隨著擁有者數量增多，導致服務器需要做更多的密鑰轉換，本文方案時間開銷多于MIPP。盡管如此，本文方案在多密鑰場景下搜索10 000 幅圖像僅耗時0.26 s，這是可接受的。

圖7 Search 階段

圖8 檢索精度

綜上所述，雖然本文方案時間開銷和存儲開銷受圖像加密密鑰個數和用戶個數影響較大，但是對于實現多密鑰場景來說，這是不可避免的。同時，為了提高方案安全性，加入冗余項之后的改進方案比基礎方案性能稍有惡化，但是依然在可接受的范圍內。因此，本文方案在實際應用中是可行的。

8 結束語

本文針對邊緣計算環境下的圖像隱私安全問題，借助于邊緣計算低時延、高可用、高實時的優勢，設計了一種支持多密鑰的加密圖像檢索方案。應用局部敏感哈希算法對圖像進行了預處理，提高了檢索速度。利用安全近鄰算法加密圖像特征，使邊緣服務器可以直接計算圖像之間的相似度并排序，提高了檢索精度。同時利用代理重加密技術進行密鑰轉換，管理用戶訪問不同加密密鑰加密的圖像集。方案分析表明，本文方案達到了安全目標，可抵抗已知背景攻擊，并且在實際應用中是可行的。進一步研究工作將會結合實際需求對方案的查詢功能進行擴展。