高效隱私保護(hù)的多用戶(hù)圖像外包檢索方案

王祥宇，馬建峰，苗銀賓

（1. 西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院，陜西 西安 710071；2. 陜西省網(wǎng)絡(luò)與系統(tǒng)安全重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710071）

1 引言

隨著數(shù)碼相機(jī)、智能手機(jī)、醫(yī)療影像設(shè)備等成像設(shè)備的發(fā)展，圖像數(shù)量呈爆炸性增長(zhǎng)。從大規(guī)模圖像數(shù)據(jù)集中檢索特定的圖像在疾病檢測(cè)與診斷[1]、網(wǎng)上購(gòu)物和社交網(wǎng)絡(luò)[2]等許多實(shí)踐領(lǐng)域受到越來(lái)越多的關(guān)注。

但是，每個(gè)圖像由成千上萬(wàn)個(gè)特征點(diǎn)組成，大規(guī)模圖像檢索業(yè)務(wù)給許多公共服務(wù)組織或公司帶來(lái)巨大的資源消耗。例如，即使患者已經(jīng)離開(kāi)，醫(yī)院也需要存儲(chǔ)患者的所有醫(yī)療圖像；社交媒體平臺(tái)需要將所有用戶(hù)的照片存儲(chǔ)在他們的相冊(cè)中。隨著云計(jì)算的發(fā)展，許多企業(yè)和組織目前更愿意在公有云平臺(tái)上托管他們的數(shù)據(jù)和服務(wù)，這樣既可以節(jié)省基礎(chǔ)設(shè)施投入，也能更好地提供服務(wù)。但是，由于許多圖像中包含敏感信息，將圖像直接外包給公有云可能會(huì)導(dǎo)致隱私泄露甚至引起法律糾紛[3]。

為了解決這一問(wèn)題，Shashank等[4]提出了一種基于內(nèi)容的圖像檢索（CBIR, content-based image retrieval）方案，該方案保護(hù)了查詢(xún)圖像的隱私，但是圖像數(shù)據(jù)集是未加密的，導(dǎo)致數(shù)據(jù)集內(nèi)容直接暴露給云服務(wù)器。為此，Lu等[5]首次在加密圖像域上構(gòu)建了隱私保護(hù)的CBIR方案。該方案通過(guò)提取視覺(jué)詞匯來(lái)表示圖像，使用Jaccard相似度來(lái)評(píng)估2個(gè)圖像之間的相似性，并采用保序加密和最小散列算法來(lái)保護(hù)視覺(jué)詞的信息，但該方案僅適用于視覺(jué)詞表示的圖像檢索算法，其準(zhǔn)確度比基于Fisher向量的圖像檢索算法低 20%以上[6-7]。盡管基于同態(tài)加密的方案可以保證檢索準(zhǔn)確度，但是通常會(huì)產(chǎn)生很大的時(shí)間和存儲(chǔ)開(kāi)銷(xiāo)[8-10]。為了實(shí)現(xiàn)高效準(zhǔn)確的CBIR方案，Xia等[11]一方面采用安全k近鄰（kNN，k-nearest neighbors）算法[12]來(lái)保護(hù)特征向量，使云服務(wù)器能夠高效地對(duì)檢索結(jié)果進(jìn)行排序；另一方面在犧牲檢索準(zhǔn)確度的前提下使用局部敏感散列建立雙層索引來(lái)提高檢索效率。Yuan等[13]同樣使用安全kNN算法來(lái)保護(hù)Fisher向量[6-7]，并通過(guò)K-means聚類(lèi)算法提高大規(guī)模數(shù)據(jù)檢索效率，該方案對(duì)加密圖像的檢索效率和準(zhǔn)確率接近明文圖像檢索的性能。但是，由于安全kNN算法使用對(duì)稱(chēng)密鑰加密，在多用戶(hù)場(chǎng)景下，各個(gè)用戶(hù)可以相互解密查詢(xún)請(qǐng)求，這帶來(lái)了極大的隱私泄露威脅。為此，Zhang等[14]使用一種多級(jí)同態(tài)加密協(xié)議設(shè)計(jì)了一個(gè)支持多用戶(hù)的圖像檢索系統(tǒng)，每個(gè)用戶(hù)使用不同的私鑰加密查詢(xún)請(qǐng)求，保證了隱私性，但是該方案帶來(lái)了巨大的通信開(kāi)銷(xiāo)和計(jì)算開(kāi)銷(xiāo)。

為了實(shí)現(xiàn)一個(gè)高效隱私保護(hù)的多用戶(hù)圖像檢索方案，需要解決以下關(guān)鍵挑戰(zhàn)：1）所有圖像特征向量都應(yīng)加密，檢索過(guò)程應(yīng)以非交互方式完成，所有存儲(chǔ)和大部分計(jì)算應(yīng)外包給公有云平臺(tái)，且要求公有云平臺(tái)無(wú)法獲取圖像、特征向量和檢索結(jié)果的隱私信息；2）每個(gè)用戶(hù)應(yīng)該持有不同的加密密鑰，這樣即使用戶(hù)的請(qǐng)求被截取了，也無(wú)法獲得請(qǐng)求內(nèi)容；3）每個(gè)用戶(hù)要能夠?qū)υ贫舜鎯?chǔ)的所有圖像進(jìn)行檢索，以便滿(mǎn)足大規(guī)模數(shù)據(jù)共享的需求。

本文提出的方案很好地滿(mǎn)足了以上需求，表 1顯示了本文的方案與文獻(xiàn)[13-14]方案的對(duì)比情況?？梢钥吹?，與這種方案相比，本文的方案具有更低的存儲(chǔ)要求和計(jì)算量，同時(shí)還能滿(mǎn)足多用戶(hù)需求。

表1 3種方案的開(kāi)銷(xiāo)對(duì)比

2 系統(tǒng)模型、安全威脅模型及設(shè)計(jì)目標(biāo)

2.1 系統(tǒng)模型

如圖1所示，所提方案主要考慮5個(gè)實(shí)體：云服務(wù)器（CS，cloud server）、數(shù)據(jù)擁有者（DO，data owner）、檢索用戶(hù)（SU，search user）、密鑰轉(zhuǎn)換中心（KCC, key conversion center）和可信代理（TA,trusted agent）。

圖1 系統(tǒng)模型

1）DO是圖像數(shù)據(jù)的擁有者，在外包圖像之前先把圖像特征提取出來(lái)構(gòu)建加密檢索索引，然后把密文索引和使用對(duì)稱(chēng)加密算法（如AES）加密的圖像一起提交到CS。

2）CS擁有大量的存儲(chǔ)空間和計(jì)算資源，為用戶(hù)提供存儲(chǔ)和計(jì)算服務(wù)。

3）SU根據(jù)所需檢索的圖像內(nèi)容生成檢索請(qǐng)求提交給KCC，并從CS得到檢索結(jié)果。

4）KCC是獨(dú)立的第三方，擁有一定的計(jì)算能力，為其他實(shí)體提供密鑰轉(zhuǎn)換服務(wù)，包括索引和查詢(xún)請(qǐng)求的轉(zhuǎn)換。

5）TA是可信的第三方，給系統(tǒng)中的各個(gè)實(shí)體分配密鑰。

2.2 安全威脅模型

在提出的方案中，CS和KCC是“好奇而誠(chéng)實(shí)”的，即CS和KCC將遵循給定的協(xié)議來(lái)執(zhí)行服務(wù)，但它可能會(huì)分析用戶(hù)的數(shù)據(jù)以獲取額外的敏感信息。DO和SU被認(rèn)為是誠(chéng)實(shí)的，并且不會(huì)與CS及KCC“勾結(jié)”。KCC是獨(dú)立的第三方，其不會(huì)與任何一方“合謀”。這些假設(shè)與大多數(shù)關(guān)注公共云中加密數(shù)據(jù)檢索的現(xiàn)有相關(guān)工作一致[12-15]。根據(jù)云服務(wù)器的可用信息，在數(shù)據(jù)的隱私保護(hù)方面考慮以下 2種威脅模型。

1）已知密文模型。CS只能訪(fǎng)問(wèn)所有加密的圖像，加密的可檢索索引和加密的檢索請(qǐng)求。CS不能對(duì)圖像數(shù)據(jù)集進(jìn)行學(xué)習(xí)，可檢索索引中的特征向量信息對(duì)CS也是保密的。

2）已知背景模型。在這個(gè)更強(qiáng)的威脅模型中，CS擁有已知密文模型中的所有信息[12-15]。另外，CS可以提取數(shù)據(jù)集中特定加密圖像的統(tǒng)計(jì)信息，如檢索頻率，甚至可以獲知數(shù)據(jù)集中的一些圖像，但是不知道圖像的明文-密文對(duì)。

2.3 設(shè)計(jì)目標(biāo)

1）高效性。系統(tǒng)必須滿(mǎn)足高效性，即具備很低的通信和計(jì)算開(kāi)銷(xiāo)，同時(shí)具有高準(zhǔn)確度。

2）多用戶(hù)。系統(tǒng)必須支持多個(gè)用戶(hù)同時(shí)對(duì)云服務(wù)器的圖像集進(jìn)行安全檢索，即在檢索過(guò)程中，用戶(hù)無(wú)法獲取其他用戶(hù)的請(qǐng)求信息，也無(wú)法獲得索引內(nèi)容。但是，用戶(hù)可以對(duì)CS上的所有圖像進(jìn)行檢索，這使本文方案可以實(shí)現(xiàn)大規(guī)模多源數(shù)據(jù)共享。

3）隱私保護(hù)。為了保證用戶(hù)數(shù)據(jù)的隱私不被泄露給云服務(wù)器，必須滿(mǎn)足下列隱私需求。

① 圖像安全性：提出的方案必須保證原始圖像數(shù)據(jù)集對(duì)CS保持機(jī)密，同時(shí)對(duì)SU是可用的。這可以使用對(duì)稱(chēng)加密（即AES等）來(lái)解決，下文中不再敘述。

② 索引和請(qǐng)求機(jī)密性：必須保證CS不能通過(guò)索引或請(qǐng)求來(lái)推斷出圖像的內(nèi)容注1本文不考慮訪(fǎng)問(wèn)權(quán)限的控制問(wèn)題，即假設(shè)對(duì)于所有檢索到的結(jié)果，SU都可以解密。訪(fǎng)問(wèn)控制可以通過(guò)基于屬性的加密技術(shù)在所提方案上進(jìn)行擴(kuò)展。。

③ 查詢(xún)請(qǐng)求的不可鏈接性：在檢索過(guò)程中，攻擊者不應(yīng)該能夠判斷2個(gè)或多個(gè)檢索是否來(lái)自同一個(gè)檢索請(qǐng)求。

3 圖像檢索方案設(shè)計(jì)

本節(jié)首先提出一種高效的單用戶(hù)圖像檢索方案。隨后，為了支持多用戶(hù)圖像檢索，提出了一個(gè)多用戶(hù)密鑰轉(zhuǎn)換協(xié)議，從而實(shí)現(xiàn)多用戶(hù)圖像檢索。表2定義了要使用到的符號(hào)，另外定義2個(gè)描述符。

表2 符號(hào)含義

定義 1對(duì)任意表示最接近x的整數(shù)，

定義2對(duì)任意向量/矩陣表示其中元素絕對(duì)值的最大值。

3.1 單用戶(hù)圖像檢索方案

在圖像檢索方案中，使用主成分分析（PCA，principal components analysis）[15]算法對(duì)圖像的Fisher矢量[6-7]進(jìn)行降維，作為相似度匹配的依據(jù)，并使用歐式距離來(lái)衡量相似度。為了實(shí)現(xiàn)數(shù)據(jù)隱私保護(hù)，引入了隱私保護(hù)的歐氏距離比較技術(shù)[16]。通過(guò)該技術(shù)，可以以一種安全的方式比較2個(gè)加密向量與同一向量之間歐氏距離的大小。該技術(shù)的細(xì)節(jié)在圖像檢索方案中進(jìn)行介紹。

單用戶(hù)圖像檢索方案主要包括4個(gè)算法：密鑰生成（KeyGen）、索引生成（IndexBuild）、查詢(xún)生成（QueryGen）和圖像檢索（ImSearch），具體如下。

1）KeyGen算法。TA隨機(jī)選擇一個(gè)2m×2m的可逆矩陣M，并生成加密密鑰 S K={M，M-1}，然后通過(guò)安全信道將SK分發(fā)給DO和SU，其中M-1為M的逆矩陣。

2）IndexBuild算法。首先，對(duì)于每一個(gè)圖像，DO首先提取出特征向量將其使用同樣比例→化為整數(shù)（例如，同時(shí)乘以10 000）。然后，DO將擴(kuò)展為2m維，如式（1）所示。

其中，α1, α2,…,αm-1∈?p是由DO隨機(jī)選擇的整數(shù)，整數(shù)p代→表數(shù)值范圍。完成擴(kuò)展之后，DO對(duì)每一個(gè)索引進(jìn)行加密，如式（2）所示。

新增長(zhǎng)點(diǎn)是發(fā)展新經(jīng)濟(jì)培育新動(dòng)能、激發(fā)新活力過(guò)程中的主要著力點(diǎn)是支撐經(jīng)濟(jì)的高成長(zhǎng)性領(lǐng)域。近年來(lái)，新能源汽車(chē)、無(wú)人駕駛等研究、生產(chǎn)實(shí)現(xiàn)“爆炸式”增長(zhǎng)，是汽車(chē)行業(yè)的新增長(zhǎng)點(diǎn)，也帶動(dòng)了相關(guān)技術(shù)、產(chǎn)業(yè)鏈相關(guān)行業(yè)的發(fā)展，孕育產(chǎn)生巨大的新動(dòng)能。“大眾創(chuàng)業(yè)、萬(wàn)眾創(chuàng)新”帶動(dòng)新經(jīng)濟(jì)蓬勃發(fā)展，引領(lǐng)服務(wù)業(yè)、高新技術(shù)產(chǎn)業(yè)、中小微企業(yè)和民營(yíng)企業(yè)等釋放新動(dòng)能。此外，還有共享單車(chē)、網(wǎng)絡(luò)零售、跨境電商等新業(yè)態(tài)新模式，通過(guò)新技術(shù)的應(yīng)用，形成新增長(zhǎng)點(diǎn)，帶來(lái)新動(dòng)能。

為了在多用戶(hù)圖像檢索場(chǎng)景下滿(mǎn)足用戶(hù)隱私需求，要保證不同的DO/SU無(wú)法解析其他DO/SU的索引內(nèi)容/查詢(xún)內(nèi)容，因此他們持有的密鑰應(yīng)該不同。與此同時(shí)，要保證每一個(gè)SU能夠?qū)S中存儲(chǔ)的所有索引進(jìn)行檢索。由于使用對(duì)稱(chēng)加密方案，CS接收到的查詢(xún)與索引必須使用相同密鑰加密才能完成歐式距離比較。為了滿(mǎn)足以上需求，設(shè)計(jì)了一個(gè)多用戶(hù)密鑰轉(zhuǎn)換協(xié)議。

3.2 多用戶(hù)密鑰轉(zhuǎn)換協(xié)議

3.2.1 密鑰分配

首先，TA隨機(jī)選擇一個(gè)2m×2m的可逆矩陣M，則加密密鑰SK={M，M-1}，其中M-1為M的逆矩陣。對(duì)于每一個(gè)數(shù)據(jù)擁有者DOi，生成用戶(hù)密鑰MOi以及轉(zhuǎn)換密鑰M'Oi，滿(mǎn)足M=MOi M'Oi。同樣地，對(duì)于每一個(gè)檢索用戶(hù)SUi，生成用戶(hù)密鑰MUi以及轉(zhuǎn)換密鑰M'Ui，滿(mǎn)足M-1=M'UiMUi。通過(guò)安全信道，將MOi、MUi分發(fā)給對(duì)應(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 。

4 方案安全性分析

本節(jié)對(duì)提出方案的安全性進(jìn)行分析。首先，定義并證明本文所使用加密方案的安全性；然后，根據(jù)第3節(jié)中提出的隱私需求對(duì)本文的圖像檢索方案進(jìn)行安全性分析；最后，分析多用戶(hù)密鑰轉(zhuǎn)換協(xié)議的安全性。

4.1 安全性定義

本文提出的圖像檢索系統(tǒng)中使用的加密方案由 Yuan等[16]基于誤差學(xué)習(xí)（LWE，learning with error）問(wèn)題[17]提出，安全性已經(jīng)得到證明。下面簡(jiǎn)要回顧該方案的安全性證明，以便進(jìn)行后續(xù)的方案安全性分析。

定義3LWE問(wèn)題：給定一個(gè)維數(shù)m≥2，模上的概率分布χ。給定的任意多個(gè)抽樣

其中，誤差εi∈χ。以不可忽略的概率恢復(fù)矢量在計(jì)算上是不可行的。

推論1若LWE問(wèn)題是困難的，則對(duì)于一個(gè)敵手來(lái)說(shuō)，從本文使用的加密方案加密的或中恢復(fù)明文在計(jì)算上是不可行的。

證明在本文的加密方案中，每一個(gè)索引的加密方式為

由于索引和請(qǐng)求的加密方式類(lèi)似，因此簡(jiǎn)便起見(jiàn)，只使用來(lái)進(jìn)行證明。在都是都是2m維的向量，他們與M的乘積可以認(rèn)為是4m2次2m維的向量?jī)?nèi)積

1）已知密文模型。在這個(gè)模型下，由于 CS只能得到加密索引和加密請(qǐng)求的訪(fǎng)問(wèn)權(quán)，根據(jù)推論 1，CS從其中恢復(fù)明文是計(jì)算不可行的。

2）已知背景模型。Yao等[18]對(duì)安全kNN這類(lèi)歐式距離保持算法提出了線(xiàn)性分析攻擊。該攻擊能夠成功的前提是CS要獲得足夠多的明-密文對(duì)。在已知背景模型下，CS雖然能獲得一些明文圖像樣本，但他并不知道明-密文對(duì)。即使CS獲得一些圖像的明文密文對(duì)，本文中使用的特征提取算法參數(shù)及PCA的降維參數(shù)是不公開(kāi)的，因此CS無(wú)法從圖像中得出對(duì)應(yīng)的特征向量，因此無(wú)法完成線(xiàn)性分析攻擊。

4.2 圖像檢索方案安全性

下面根據(jù)3.3節(jié)提出的隱私保護(hù)需求從三方面對(duì)圖像檢索方案進(jìn)行分析。

1）圖像安全性：本文提出的方案中，原始圖像數(shù)據(jù)集是使用AES進(jìn)行加密的，故圖像的安全性可以得到很好的保證。

4.3 多用戶(hù)密鑰轉(zhuǎn)換協(xié)議安全性

在多用戶(hù)密鑰轉(zhuǎn)換協(xié)議中，加密密鑰SK被分解成用戶(hù)密鑰和轉(zhuǎn)換密鑰，分別分配給 DO/SU和KCC。在本文方案中，KCC與系統(tǒng)中的其他實(shí)體是不共謀的，所以DO/SU和KCC都無(wú)法獲得SK。這樣，在索引生成/查詢(xún)生成階段，DO/SU使用用戶(hù)密鑰對(duì)數(shù)據(jù)進(jìn)行加密，每個(gè)由于用戶(hù)密鑰是相互獨(dú)立的，即使用戶(hù)截獲了其他人的檢索索引也無(wú)法將其解密從而獲得原始數(shù)據(jù)。另外，KCC只有轉(zhuǎn)換密鑰，同樣無(wú)法解密用戶(hù)的索引/查詢(xún)請(qǐng)求。最后，由于CS存儲(chǔ)的索引和收到的查詢(xún)請(qǐng)求都是用SK加密的，因此CS可以對(duì)所有圖像進(jìn)行檢索，滿(mǎn)足功能需求。

5 方案性能分析

本節(jié)對(duì)提出的多用戶(hù)圖像外包檢索方案的性能進(jìn)行分析。為了對(duì)方案性能進(jìn)行仿真，本文使用Python實(shí)現(xiàn)了本文提出的方案。為了更好地進(jìn)行性能比較，同樣用Python實(shí)現(xiàn)了SEIS[11]作為對(duì)比方案。測(cè)試環(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)確度測(cè)試，該數(shù)據(jù)集同樣用于很多其他圖像檢索工作的仿真[6-7,11,14]。這里設(shè)提取的Fisher向量的維度為4 096。

5.1 檢索準(zhǔn)確度

為了驗(yàn)證方案的檢索準(zhǔn)確度，選擇了文獻(xiàn)[18-19]這2個(gè)明文圖像檢索方案和SEIS作為對(duì)比方案。這里采用的準(zhǔn)確度測(cè)試指標(biāo)為應(yīng)用廣泛的平均精度（MAP，mean average precision）[19]。

圖3 不同特征維度下檢索準(zhǔn)確度對(duì)比

從圖 3可以看出，本文方案與文獻(xiàn)[18-19]這2種明文方案的準(zhǔn)確度接近。由于本文方案與SEIS采用相同的特征向量提取方式，因此準(zhǔn)確度相同?？梢钥吹?，當(dāng)特征向量維度小于512時(shí)，準(zhǔn)確度增長(zhǎng)明顯，特征向量維度大于512時(shí)，準(zhǔn)確度趨于平緩。因此，推薦使用大于512的特征向量維度。

5.2 存儲(chǔ)和通信開(kāi)銷(xiāo)分析

本文方案的存儲(chǔ)開(kāi)銷(xiāo)以及通信開(kāi)銷(xiāo)與已有方案的對(duì)比如表3所示。

表3 存儲(chǔ)和通信開(kāi)銷(xiāo)對(duì)比

1）存儲(chǔ)開(kāi)銷(xiāo)：定義|e|為索引或查詢(xún)向量中元素的位寬，一般為64 bit。假設(shè)有n個(gè)圖像存儲(chǔ)在云服務(wù)器中，每個(gè)圖像的索引向量為m維。在本文提出的方案中，每個(gè)索引向量會(huì)被擴(kuò)展為 2m維向量并加密，由于多密鑰方案并沒(méi)有對(duì)云端存儲(chǔ)的索引做改變，所以單用戶(hù)和多用戶(hù)方案的索引存儲(chǔ)開(kāi)銷(xiāo)均為2mn|e|。而在SEIS方案中，每個(gè)索引向量除了被擴(kuò)展為2m維向量，在加密過(guò)程中還被分裂成2個(gè)，因此存儲(chǔ)開(kāi)銷(xiāo)為4mn|e|。

2）通信開(kāi)銷(xiāo)：在單用戶(hù)和多用戶(hù)方案中，檢索請(qǐng)求都被加密為2m維向量。不同的是，單用戶(hù)方案的請(qǐng)求直接發(fā)送到CS進(jìn)行檢索；而多用戶(hù)方案中的請(qǐng)求需要先發(fā)送到 KCC進(jìn)行密鑰轉(zhuǎn)換，然后再發(fā)送給 CS。因此，單用戶(hù)方案的通信開(kāi)銷(xiāo)為2mn|e|，而多用戶(hù)方案為4mn|e|。由于SEIS方案中每個(gè)查詢(xún)請(qǐng)求被加密為2個(gè)2m維向量，所以SEIS方案的通信開(kāi)銷(xiāo)為4mn|e|。

綜上所述，本文提出的2種方案存儲(chǔ)開(kāi)銷(xiāo)均優(yōu)于SEIS，只有SEIS的一半。單用戶(hù)方案的通信開(kāi)銷(xiāo)為SEIS的一半，多用戶(hù)方案的通信開(kāi)銷(xiāo)與SEIS相同。

5.3 計(jì)算開(kāi)銷(xiāo)分析

本節(jié)對(duì)比本文提出的方案和 SEIS的各個(gè)算法的算法復(fù)雜度，然后對(duì)它們的運(yùn)行時(shí)間進(jìn)行仿真。為了方便描述，使用 DOT2m來(lái)定義2個(gè)2m維向量的內(nèi)積操作，即：給定2個(gè)向量和它們之間的一個(gè)內(nèi)積操作為由于計(jì)算開(kāi)銷(xiāo)與 DOT操作相比十2m分微小，忽略單個(gè)的加法操作和取模操作。為了實(shí)現(xiàn)滿(mǎn)足多用戶(hù)檢索需求，在單用戶(hù)方案基礎(chǔ)上加入了密鑰轉(zhuǎn)換協(xié)議，為了更好地比較單用戶(hù)與多用戶(hù)方案的計(jì)算開(kāi)銷(xiāo)，使用KeyTrans算法來(lái)指代密鑰轉(zhuǎn)換過(guò)程。

計(jì)算復(fù)雜度對(duì)比如表4所示。在本文的方案中，IndexBuild過(guò)程的算法復(fù)雜度為 2mnDOT2m，如式（2）所示，在加密過(guò)程中每個(gè)索引向量都需要內(nèi)積一個(gè)2m×2m矩陣，這相當(dāng)于進(jìn)行了 2mDOT2m操作，那么加密n個(gè)索引花費(fèi) 2mnDOT2m操作。在 SEIS中，每個(gè)索引向量首先被分裂成2個(gè)向量，然后2個(gè)向量分別內(nèi)積2m×2m矩陣進(jìn)行加密，因此加密n個(gè)索引花費(fèi) 4mnDOT2m操作。如式（4）所示，QueryGen過(guò)程中的加密方式與IndexBuild中類(lèi)似，單用戶(hù)方案需要 2mDOT2m操作來(lái)進(jìn)行查詢(xún)加密，而SEIS需要 4mDOT2m操作。值得注意的是，為了實(shí)現(xiàn)滿(mǎn)足多用戶(hù)檢索需求，多用戶(hù)方案加入了KeyTrans過(guò)程。如式（9）和式（11）所示，每轉(zhuǎn)換一個(gè)索引（查詢(xún)）該算法執(zhí)行 2mDOT2m操作，因此多用戶(hù)方案同樣需要 4mDOT2m操作。ImSearch過(guò)程中，如式（5）所示，CS使用查詢(xún)向量→對(duì)每一個(gè)索引）進(jìn)行內(nèi)積操作，在本文方案中，算法復(fù)雜度為nDOT2m操作。由于在加密時(shí)進(jìn)行了向量分裂，SEIS的算法復(fù)雜度為 2nDOT2m。

表4 計(jì)算復(fù)雜度對(duì)比

圖4繪制了特征維數(shù)從128到4 096，圖像數(shù)量為20 000時(shí)，IndexBuild算法的運(yùn)行時(shí)間。可以看到，所有方案的運(yùn)行時(shí)間都隨著維度的增長(zhǎng)而增長(zhǎng)。單用戶(hù)方案運(yùn)行時(shí)間約為SEIS的一半，多用戶(hù)方案運(yùn)行時(shí)間與SEIS類(lèi)似，這與理論分析一致。從圖 5可以看出，當(dāng)特征向量維度為 512時(shí)，各種方案IndexBuild的運(yùn)行時(shí)間隨著圖像數(shù)量的增加線(xiàn)性增長(zhǎng)。其中，單用戶(hù)方案的運(yùn)行時(shí)間約為SEIS的一半，多用戶(hù)方案運(yùn)行時(shí)間與SEIS類(lèi)似。

圖4 不同特征維度下IndexBuild運(yùn)行時(shí)間

圖6繪制了特征向量維度從128到4 096時(shí)，QueryGen算法的運(yùn)行時(shí)間。從圖中可以看到，所有方案的運(yùn)行時(shí)間都隨著維度的增長(zhǎng)而增長(zhǎng)。本文的單用戶(hù)方案運(yùn)行時(shí)間約為SEIS的一半，多用戶(hù)方案運(yùn)行時(shí)間與SEIS類(lèi)似，查詢(xún)生成時(shí)間小于150 ms，可以滿(mǎn)足高效性需求。

圖5 不同圖像數(shù)量下IndexBuild運(yùn)行時(shí)間

圖6 不同特征維度下QueryGen運(yùn)行時(shí)間

從圖7可以看出，當(dāng)特征向量維度為512時(shí)，各種方案 ImSearch的運(yùn)行時(shí)間隨著圖像數(shù)量的增加線(xiàn)性增長(zhǎng)。與IndexBuild一樣，單用戶(hù)方案的運(yùn)行時(shí)間約為SEIS的一半。因?yàn)槊荑€轉(zhuǎn)換導(dǎo)致的時(shí)間消耗，多用戶(hù)方案運(yùn)行時(shí)間與 SEIS類(lèi)似，對(duì)10萬(wàn)個(gè)圖像的檢索時(shí)間不到200 ms。

圖7 不同圖像數(shù)量下ImSearch運(yùn)行時(shí)間

圖8繪制了特征維數(shù)從128到4 096，圖像數(shù)量為10 000時(shí)，ImSearch算法的運(yùn)行時(shí)間?？梢钥吹?，所有方案的運(yùn)行時(shí)間都隨著維度的增長(zhǎng)而增長(zhǎng)。單用戶(hù)方案運(yùn)行時(shí)間約為 SEIS的一半，多用戶(hù)方案運(yùn)行時(shí)間與SEIS類(lèi)似。

圖8 不同特征維度下ImSearch運(yùn)行時(shí)間

6 結(jié)束語(yǔ)

為了高效地解決多用戶(hù)圖像檢索系統(tǒng)的隱私保護(hù)問(wèn)題，本文首先提出了一種高效隱私保護(hù)的單用戶(hù)圖像檢索方案。該方案可以達(dá)到與明文方案接近的檢索準(zhǔn)確度，與 SEIS相比，其存儲(chǔ)開(kāi)銷(xiāo)、通信開(kāi)銷(xiāo)和計(jì)算開(kāi)銷(xiāo)均降低了一半。另外，為了滿(mǎn)足多用戶(hù)圖像檢索需求，本文提出了一個(gè)多用戶(hù)密鑰轉(zhuǎn)換協(xié)議。通過(guò)該協(xié)議，數(shù)據(jù)擁有者或檢索用戶(hù)可以使用自己獨(dú)有的密鑰加密檢索索引或請(qǐng)求，保證了索引或請(qǐng)求的隱私性。同時(shí)，檢索用戶(hù)可以對(duì)云服務(wù)器上的所有圖像進(jìn)行檢索，保證了大規(guī)模多源數(shù)據(jù)的共享。嚴(yán)格的安全性分析表明本文方案可以滿(mǎn)足用戶(hù)隱私保護(hù)需求。基于真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了本文方案的高效性，使用本文提出的方案對(duì)10萬(wàn)張圖像進(jìn)行檢索的時(shí)間不到200 ms。因此，本文所提方案在實(shí)際的多用戶(hù)場(chǎng)景中是可行的和高效的。