王祥宇,馬建峰,苗銀賓
(1. 西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院,陜西 西安 710071;2. 陜西省網(wǎng)絡(luò)與系統(tǒng)安全重點(diǎn)實驗室,陜西 西安 710071)
隨著數(shù)碼相機(jī)、智能手機(jī)、醫(yī)療影像設(shè)備等成像設(shè)備的發(fā)展,圖像數(shù)量呈爆炸性增長。從大規(guī)模圖像數(shù)據(jù)集中檢索特定的圖像在疾病檢測與診斷[1]、網(wǎng)上購物和社交網(wǎng)絡(luò)[2]等許多實踐領(lǐng)域受到越來越多的關(guān)注。
但是,每個圖像由成千上萬個特征點(diǎn)組成,大規(guī)模圖像檢索業(yè)務(wù)給許多公共服務(wù)組織或公司帶來巨大的資源消耗。例如,即使患者已經(jīng)離開,醫(yī)院也需要存儲患者的所有醫(yī)療圖像;社交媒體平臺需要將所有用戶的照片存儲在他們的相冊中。隨著云計算的發(fā)展,許多企業(yè)和組織目前更愿意在公有云平臺上托管他們的數(shù)據(jù)和服務(wù),這樣既可以節(jié)省基礎(chǔ)設(shè)施投入,也能更好地提供服務(wù)。但是,由于許多圖像中包含敏感信息,將圖像直接外包給公有云可能會導(dǎo)致隱私泄露甚至引起法律糾紛[3]。
為了解決這一問題,Shashank等[4]提出了一種基于內(nèi)容的圖像檢索(CBIR, content-based image retrieval)方案,該方案保護(hù)了查詢圖像的隱私,但是圖像數(shù)據(jù)集是未加密的,導(dǎo)致數(shù)據(jù)集內(nèi)容直接暴露給云服務(wù)器。為此,Lu等[5]首次在加密圖像域上構(gòu)建了隱私保護(hù)的CBIR方案。該方案通過提取視覺詞匯來表示圖像,使用Jaccard相似度來評估2個圖像之間的相似性,并采用保序加密和最小散列算法來保護(hù)視覺詞的信息,但該方案僅適用于視覺詞表示的圖像檢索算法,其準(zhǔn)確度比基于Fisher向量的圖像檢索算法低 20%以上[6-7]。盡管基于同態(tài)加密的方案可以保證檢索準(zhǔn)確度,但是通常會產(chǎn)生很大的時間和存儲開銷[8-10]。為了實現(xiàn)高效準(zhǔn)確的CBIR方案,Xia等[11]一方面采用安全k近鄰(kNN,k-nearest neighbors)算法[12]來保護(hù)特征向量,使云服務(wù)器能夠高效地對檢索結(jié)果進(jìn)行排序;另一方面在犧牲檢索準(zhǔn)確度的前提下使用局部敏感散列建立雙層索引來提高檢索效率。Yuan等[13]同樣使用安全kNN算法來保護(hù)Fisher向量[6-7],并通過K-means聚類算法提高大規(guī)模數(shù)據(jù)檢索效率,該方案對加密圖像的檢索效率和準(zhǔn)確率接近明文圖像檢索的性能。但是,由于安全kNN算法使用對稱密鑰加密,在多用戶場景下,各個用戶可以相互解密查詢請求,這帶來了極大的隱私泄露威脅。為此,Zhang等[14]使用一種多級同態(tài)加密協(xié)議設(shè)計了一個支持多用戶的圖像檢索系統(tǒng),每個用戶使用不同的私鑰加密查詢請求,保證了隱私性,但是該方案帶來了巨大的通信開銷和計算開銷。
為了實現(xiàn)一個高效隱私保護(hù)的多用戶圖像檢索方案,需要解決以下關(guān)鍵挑戰(zhàn):1)所有圖像特征向量都應(yīng)加密,檢索過程應(yīng)以非交互方式完成,所有存儲和大部分計算應(yīng)外包給公有云平臺,且要求公有云平臺無法獲取圖像、特征向量和檢索結(jié)果的隱私信息;2)每個用戶應(yīng)該持有不同的加密密鑰,這樣即使用戶的請求被截取了,也無法獲得請求內(nèi)容;3)每個用戶要能夠?qū)υ贫舜鎯Φ乃袌D像進(jìn)行檢索,以便滿足大規(guī)模數(shù)據(jù)共享的需求。
本文提出的方案很好地滿足了以上需求,表 1顯示了本文的方案與文獻(xiàn)[13-14]方案的對比情況??梢钥吹?,與這種方案相比,本文的方案具有更低的存儲要求和計算量,同時還能滿足多用戶需求。
表1 3種方案的開銷對比
如圖1所示,所提方案主要考慮5個實體:云服務(wù)器(CS,cloud server)、數(shù)據(jù)擁有者(DO,data owner)、檢索用戶(SU,search user)、密鑰轉(zhuǎn)換中心(KCC, key conversion center)和可信代理(TA,trusted agent)。
圖1 系統(tǒng)模型
1)DO是圖像數(shù)據(jù)的擁有者,在外包圖像之前先把圖像特征提取出來構(gòu)建加密檢索索引,然后把密文索引和使用對稱加密算法(如AES)加密的圖像一起提交到CS。
2)CS擁有大量的存儲空間和計算資源,為用戶提供存儲和計算服務(wù)。
3)SU根據(jù)所需檢索的圖像內(nèi)容生成檢索請求提交給KCC,并從CS得到檢索結(jié)果。
4)KCC是獨(dú)立的第三方,擁有一定的計算能力,為其他實體提供密鑰轉(zhuǎn)換服務(wù),包括索引和查詢請求的轉(zhuǎn)換。
5)TA是可信的第三方,給系統(tǒng)中的各個實體分配密鑰。
在提出的方案中,CS和KCC是“好奇而誠實”的,即CS和KCC將遵循給定的協(xié)議來執(zhí)行服務(wù),但它可能會分析用戶的數(shù)據(jù)以獲取額外的敏感信息。DO和SU被認(rèn)為是誠實的,并且不會與CS及KCC“勾結(jié)”。KCC是獨(dú)立的第三方,其不會與任何一方“合謀”。這些假設(shè)與大多數(shù)關(guān)注公共云中加密數(shù)據(jù)檢索的現(xiàn)有相關(guān)工作一致[12-15]。根據(jù)云服務(wù)器的可用信息,在數(shù)據(jù)的隱私保護(hù)方面考慮以下 2種威脅模型。
1)已知密文模型。CS只能訪問所有加密的圖像,加密的可檢索索引和加密的檢索請求。CS不能對圖像數(shù)據(jù)集進(jìn)行學(xué)習(xí),可檢索索引中的特征向量信息對CS也是保密的。
2)已知背景模型。在這個更強(qiáng)的威脅模型中,CS擁有已知密文模型中的所有信息[12-15]。另外,CS可以提取數(shù)據(jù)集中特定加密圖像的統(tǒng)計信息,如檢索頻率,甚至可以獲知數(shù)據(jù)集中的一些圖像,但是不知道圖像的明文-密文對。
1)高效性。系統(tǒng)必須滿足高效性,即具備很低的通信和計算開銷,同時具有高準(zhǔn)確度。
2)多用戶。系統(tǒng)必須支持多個用戶同時對云服務(wù)器的圖像集進(jìn)行安全檢索,即在檢索過程中,用戶無法獲取其他用戶的請求信息,也無法獲得索引內(nèi)容。但是,用戶可以對CS上的所有圖像進(jìn)行檢索,這使本文方案可以實現(xiàn)大規(guī)模多源數(shù)據(jù)共享。
3)隱私保護(hù)。為了保證用戶數(shù)據(jù)的隱私不被泄露給云服務(wù)器,必須滿足下列隱私需求。
① 圖像安全性:提出的方案必須保證原始圖像數(shù)據(jù)集對CS保持機(jī)密,同時對SU是可用的。這可以使用對稱加密(即AES等)來解決,下文中不再敘述。
② 索引和請求機(jī)密性:必須保證CS不能通過索引或請求來推斷出圖像的內(nèi)容注1本文不考慮訪問權(quán)限的控制問題,即假設(shè)對于所有檢索到的結(jié)果,SU都可以解密。訪問控制可以通過基于屬性的加密技術(shù)在所提方案上進(jìn)行擴(kuò)展。。
③ 查詢請求的不可鏈接性:在檢索過程中,攻擊者不應(yīng)該能夠判斷2個或多個檢索是否來自同一個檢索請求。
本節(jié)首先提出一種高效的單用戶圖像檢索方案。隨后,為了支持多用戶圖像檢索,提出了一個多用戶密鑰轉(zhuǎn)換協(xié)議,從而實現(xiàn)多用戶圖像檢索。表2定義了要使用到的符號,另外定義2個描述符。
表2 符號含義
定義 1對任意表示最接近x的整數(shù),
定義2對任意向量/矩陣表示其中元素絕對值的最大值。
在圖像檢索方案中,使用主成分分析(PCA,principal components analysis)[15]算法對圖像的Fisher矢量[6-7]進(jìn)行降維,作為相似度匹配的依據(jù),并使用歐式距離來衡量相似度。為了實現(xiàn)數(shù)據(jù)隱私保護(hù),引入了隱私保護(hù)的歐氏距離比較技術(shù)[16]。通過該技術(shù),可以以一種安全的方式比較2個加密向量與同一向量之間歐氏距離的大小。該技術(shù)的細(xì)節(jié)在圖像檢索方案中進(jìn)行介紹。
單用戶圖像檢索方案主要包括4個算法:密鑰生成(KeyGen)、索引生成(IndexBuild)、查詢生成(QueryGen)和圖像檢索(ImSearch),具體如下。
1)KeyGen算法。TA隨機(jī)選擇一個2m×2m的可逆矩陣M,并生成加密密鑰 S K={M,M-1},然后通過安全信道將SK分發(fā)給DO和SU,其中M-1為M的逆矩陣。
2)IndexBuild算法。首先,對于每一個圖像,DO首先提取出特征向量將其使用同樣比例→化為整數(shù)(例如,同時乘以10 000)。然后,DO將擴(kuò)展為2m維,如式(1)所示。
其中,α1, α2,…,αm-1∈?p是由DO隨機(jī)選擇的整數(shù),整數(shù)p代→表數(shù)值范圍。完成擴(kuò)展之后,DO對每一個索引進(jìn)行加密,如式(2)所示。
新增長點(diǎn)是發(fā)展新經(jīng)濟(jì)培育新動能、激發(fā)新活力過程中的主要著力點(diǎn)是支撐經(jīng)濟(jì)的高成長性領(lǐng)域。近年來,新能源汽車、無人駕駛等研究、生產(chǎn)實現(xiàn)“爆炸式”增長,是汽車行業(yè)的新增長點(diǎn),也帶動了相關(guān)技術(shù)、產(chǎn)業(yè)鏈相關(guān)行業(yè)的發(fā)展,孕育產(chǎn)生巨大的新動能。“大眾創(chuàng)業(yè)、萬眾創(chuàng)新”帶動新經(jīng)濟(jì)蓬勃發(fā)展,引領(lǐng)服務(wù)業(yè)、高新技術(shù)產(chǎn)業(yè)、中小微企業(yè)和民營企業(yè)等釋放新動能。此外,還有共享單車、網(wǎng)絡(luò)零售、跨境電商等新業(yè)態(tài)新模式,通過新技術(shù)的應(yīng)用,形成新增長點(diǎn),帶來新動能。
為了在多用戶圖像檢索場景下滿足用戶隱私需求,要保證不同的DO/SU無法解析其他DO/SU的索引內(nèi)容/查詢內(nèi)容,因此他們持有的密鑰應(yīng)該不同。與此同時,要保證每一個SU能夠?qū)S中存儲的所有索引進(jìn)行檢索。由于使用對稱加密方案,CS接收到的查詢與索引必須使用相同密鑰加密才能完成歐式距離比較。為了滿足以上需求,設(shè)計了一個多用戶密鑰轉(zhuǎn)換協(xié)議。
3.2.1 密鑰分配
首先,TA隨機(jī)選擇一個2m×2m的可逆矩陣M,則加密密鑰SK={M,M-1},其中M-1為M的逆矩陣。對于每一個數(shù)據(jù)擁有者DOi,生成用戶密鑰MOi以及轉(zhuǎn)換密鑰M'Oi,滿足M=MOi M'Oi。同樣地,對于每一個檢索用戶SUi,生成用戶密鑰MUi以及轉(zhuǎn)換密鑰M'Ui,滿足M-1=M'UiMUi。通過安全信道,將MOi、MUi分發(fā)給對應(yīng)的DOi、SUi,將轉(zhuǎn)換密鑰M'Oi、M'Ui分發(fā)給密鑰轉(zhuǎn)換中心KCC。
3.2.2 密鑰轉(zhuǎn)換協(xié)議
圖2 密鑰轉(zhuǎn)換協(xié)議
轉(zhuǎn)換完成后,KCC把轉(zhuǎn)換后的密文索引發(fā)送給CS 。
本節(jié)對提出方案的安全性進(jìn)行分析。首先,定義并證明本文所使用加密方案的安全性;然后,根據(jù)第3節(jié)中提出的隱私需求對本文的圖像檢索方案進(jìn)行安全性分析;最后,分析多用戶密鑰轉(zhuǎn)換協(xié)議的安全性。
本文提出的圖像檢索系統(tǒng)中使用的加密方案由 Yuan等[16]基于誤差學(xué)習(xí)(LWE,learning with error)問題[17]提出,安全性已經(jīng)得到證明。下面簡要回顧該方案的安全性證明,以便進(jìn)行后續(xù)的方案安全性分析。
定義3LWE問題:給定一個維數(shù)m≥2,模上的概率分布χ。給定的任意多個抽樣
其中,誤差εi∈χ。以不可忽略的概率恢復(fù)矢量在計算上是不可行的。
推論1若LWE問題是困難的,則對于一個敵手來說,從本文使用的加密方案加密的或中恢復(fù)明文在計算上是不可行的。
證明在本文的加密方案中,每一個索引的加密方式為
由于索引和請求的加密方式類似,因此簡便起見,只使用來進(jìn)行證明。在都是都是2m維的向量,他們與M的乘積可以認(rèn)為是4m2次2m維的向量內(nèi)積
1)已知密文模型。在這個模型下,由于 CS只能得到加密索引和加密請求的訪問權(quán),根據(jù)推論 1,CS從其中恢復(fù)明文是計算不可行的。
2)已知背景模型。Yao等[18]對安全kNN這類歐式距離保持算法提出了線性分析攻擊。該攻擊能夠成功的前提是CS要獲得足夠多的明-密文對。在已知背景模型下,CS雖然能獲得一些明文圖像樣本,但他并不知道明-密文對。即使CS獲得一些圖像的明文密文對,本文中使用的特征提取算法參數(shù)及PCA的降維參數(shù)是不公開的,因此CS無法從圖像中得出對應(yīng)的特征向量,因此無法完成線性分析攻擊。
下面根據(jù)3.3節(jié)提出的隱私保護(hù)需求從三方面對圖像檢索方案進(jìn)行分析。
1)圖像安全性:本文提出的方案中,原始圖像數(shù)據(jù)集是使用AES進(jìn)行加密的,故圖像的安全性可以得到很好的保證。
在多用戶密鑰轉(zhuǎn)換協(xié)議中,加密密鑰SK被分解成用戶密鑰和轉(zhuǎn)換密鑰,分別分配給 DO/SU和KCC。在本文方案中,KCC與系統(tǒng)中的其他實體是不共謀的,所以DO/SU和KCC都無法獲得SK。這樣,在索引生成/查詢生成階段,DO/SU使用用戶密鑰對數(shù)據(jù)進(jìn)行加密,每個由于用戶密鑰是相互獨(dú)立的,即使用戶截獲了其他人的檢索索引也無法將其解密從而獲得原始數(shù)據(jù)。另外,KCC只有轉(zhuǎn)換密鑰,同樣無法解密用戶的索引/查詢請求。最后,由于CS存儲的索引和收到的查詢請求都是用SK加密的,因此CS可以對所有圖像進(jìn)行檢索,滿足功能需求。
本節(jié)對提出的多用戶圖像外包檢索方案的性能進(jìn)行分析。為了對方案性能進(jìn)行仿真,本文使用Python實現(xiàn)了本文提出的方案。為了更好地進(jìn)行性能比較,同樣用Python實現(xiàn)了SEIS[11]作為對比方案。測試環(huán)境為Ubuntu 16.04 LTS 操作系統(tǒng),3.3 GHz Intel Core(TM)處理器,4 GB RAM。本文使用著名的INRIA Holidays數(shù)據(jù)集[15]進(jìn)行準(zhǔn)確度測試,該數(shù)據(jù)集同樣用于很多其他圖像檢索工作的仿真[6-7,11,14]。這里設(shè)提取的Fisher向量的維度為4 096。
為了驗證方案的檢索準(zhǔn)確度,選擇了文獻(xiàn)[18-19]這2個明文圖像檢索方案和SEIS作為對比方案。這里采用的準(zhǔn)確度測試指標(biāo)為應(yīng)用廣泛的平均精度(MAP,mean average precision)[19]。
圖3 不同特征維度下檢索準(zhǔn)確度對比
從圖 3可以看出,本文方案與文獻(xiàn)[18-19]這2種明文方案的準(zhǔn)確度接近。由于本文方案與SEIS采用相同的特征向量提取方式,因此準(zhǔn)確度相同。可以看到,當(dāng)特征向量維度小于512時,準(zhǔn)確度增長明顯,特征向量維度大于512時,準(zhǔn)確度趨于平緩。因此,推薦使用大于512的特征向量維度。
本文方案的存儲開銷以及通信開銷與已有方案的對比如表3所示。
表3 存儲和通信開銷對比
1)存儲開銷:定義|e|為索引或查詢向量中元素的位寬,一般為64 bit。假設(shè)有n個圖像存儲在云服務(wù)器中,每個圖像的索引向量為m維。在本文提出的方案中,每個索引向量會被擴(kuò)展為 2m維向量并加密,由于多密鑰方案并沒有對云端存儲的索引做改變,所以單用戶和多用戶方案的索引存儲開銷均為2mn|e|。而在SEIS方案中,每個索引向量除了被擴(kuò)展為2m維向量,在加密過程中還被分裂成2個,因此存儲開銷為4mn|e|。
2)通信開銷:在單用戶和多用戶方案中,檢索請求都被加密為2m維向量。不同的是,單用戶方案的請求直接發(fā)送到CS進(jìn)行檢索;而多用戶方案中的請求需要先發(fā)送到 KCC進(jìn)行密鑰轉(zhuǎn)換,然后再發(fā)送給 CS。因此,單用戶方案的通信開銷為2mn|e|,而多用戶方案為4mn|e|。由于SEIS方案中每個查詢請求被加密為2個2m維向量,所以SEIS方案的通信開銷為4mn|e|。
綜上所述,本文提出的2種方案存儲開銷均優(yōu)于SEIS,只有SEIS的一半。單用戶方案的通信開銷為SEIS的一半,多用戶方案的通信開銷與SEIS相同。
本節(jié)對比本文提出的方案和 SEIS的各個算法的算法復(fù)雜度,然后對它們的運(yùn)行時間進(jìn)行仿真。為了方便描述,使用 DOT2m來定義2個2m維向量的內(nèi)積操作,即:給定2個向量和它們之間的一個內(nèi)積操作為由于計算開銷與 DOT操作相比十2m分微小,忽略單個的加法操作和取模操作。為了實現(xiàn)滿足多用戶檢索需求,在單用戶方案基礎(chǔ)上加入了密鑰轉(zhuǎn)換協(xié)議,為了更好地比較單用戶與多用戶方案的計算開銷,使用KeyTrans算法來指代密鑰轉(zhuǎn)換過程。
計算復(fù)雜度對比如表4所示。在本文的方案中,IndexBuild過程的算法復(fù)雜度為 2mnDOT2m,如式(2)所示,在加密過程中每個索引向量都需要內(nèi)積一個2m×2m矩陣,這相當(dāng)于進(jìn)行了 2mDOT2m操作,那么加密n個索引花費(fèi) 2mnDOT2m操作。在 SEIS中,每個索引向量首先被分裂成2個向量,然后2個向量分別內(nèi)積2m×2m矩陣進(jìn)行加密,因此加密n個索引花費(fèi) 4mnDOT2m操作。如式(4)所示,QueryGen過程中的加密方式與IndexBuild中類似,單用戶方案需要 2mDOT2m操作來進(jìn)行查詢加密,而SEIS需要 4mDOT2m操作。值得注意的是,為了實現(xiàn)滿足多用戶檢索需求,多用戶方案加入了KeyTrans過程。如式(9)和式(11)所示,每轉(zhuǎn)換一個索引(查詢)該算法執(zhí)行 2mDOT2m操作,因此多用戶方案同樣需要 4mDOT2m操作。ImSearch過程中,如式(5)所示,CS使用查詢向量→對每一個索引)進(jìn)行內(nèi)積操作,在本文方案中,算法復(fù)雜度為nDOT2m操作。由于在加密時進(jìn)行了向量分裂,SEIS的算法復(fù)雜度為 2nDOT2m。
表4 計算復(fù)雜度對比
圖4繪制了特征維數(shù)從128到4 096,圖像數(shù)量為20 000時,IndexBuild算法的運(yùn)行時間??梢钥吹?,所有方案的運(yùn)行時間都隨著維度的增長而增長。單用戶方案運(yùn)行時間約為SEIS的一半,多用戶方案運(yùn)行時間與SEIS類似,這與理論分析一致。從圖 5可以看出,當(dāng)特征向量維度為 512時,各種方案IndexBuild的運(yùn)行時間隨著圖像數(shù)量的增加線性增長。其中,單用戶方案的運(yùn)行時間約為SEIS的一半,多用戶方案運(yùn)行時間與SEIS類似。
圖4 不同特征維度下IndexBuild運(yùn)行時間
圖6繪制了特征向量維度從128到4 096時,QueryGen算法的運(yùn)行時間。從圖中可以看到,所有方案的運(yùn)行時間都隨著維度的增長而增長。本文的單用戶方案運(yùn)行時間約為SEIS的一半,多用戶方案運(yùn)行時間與SEIS類似,查詢生成時間小于150 ms,可以滿足高效性需求。
圖5 不同圖像數(shù)量下IndexBuild運(yùn)行時間
圖6 不同特征維度下QueryGen運(yùn)行時間
從圖7可以看出,當(dāng)特征向量維度為512時,各種方案 ImSearch的運(yùn)行時間隨著圖像數(shù)量的增加線性增長。與IndexBuild一樣,單用戶方案的運(yùn)行時間約為SEIS的一半。因為密鑰轉(zhuǎn)換導(dǎo)致的時間消耗,多用戶方案運(yùn)行時間與 SEIS類似,對10萬個圖像的檢索時間不到200 ms。
圖7 不同圖像數(shù)量下ImSearch運(yùn)行時間
圖8繪制了特征維數(shù)從128到4 096,圖像數(shù)量為10 000時,ImSearch算法的運(yùn)行時間??梢钥吹?,所有方案的運(yùn)行時間都隨著維度的增長而增長。單用戶方案運(yùn)行時間約為 SEIS的一半,多用戶方案運(yùn)行時間與SEIS類似。
圖8 不同特征維度下ImSearch運(yùn)行時間
為了高效地解決多用戶圖像檢索系統(tǒng)的隱私保護(hù)問題,本文首先提出了一種高效隱私保護(hù)的單用戶圖像檢索方案。該方案可以達(dá)到與明文方案接近的檢索準(zhǔn)確度,與 SEIS相比,其存儲開銷、通信開銷和計算開銷均降低了一半。另外,為了滿足多用戶圖像檢索需求,本文提出了一個多用戶密鑰轉(zhuǎn)換協(xié)議。通過該協(xié)議,數(shù)據(jù)擁有者或檢索用戶可以使用自己獨(dú)有的密鑰加密檢索索引或請求,保證了索引或請求的隱私性。同時,檢索用戶可以對云服務(wù)器上的所有圖像進(jìn)行檢索,保證了大規(guī)模多源數(shù)據(jù)的共享。嚴(yán)格的安全性分析表明本文方案可以滿足用戶隱私保護(hù)需求?;谡鎸崝?shù)據(jù)集上的實驗驗證了本文方案的高效性,使用本文提出的方案對10萬張圖像進(jìn)行檢索的時間不到200 ms。因此,本文所提方案在實際的多用戶場景中是可行的和高效的。