基于同態(tài)加密的圖像特征提取

常 亮（北方工業(yè)大學(xué) 信息學(xué)院，北京 100144）

0 引言

隨著數(shù)字時(shí)代的到來，圖像的數(shù)量急劇増長(zhǎng)，使對(duì)大規(guī)模圖像數(shù)據(jù)進(jìn)行存儲(chǔ)成為一個(gè)迫切需要解決的問題。得益于計(jì)算機(jī)技術(shù)的迅猛發(fā)展，云存儲(chǔ)技術(shù)的出現(xiàn)，用戶可選擇將大規(guī)模圖像數(shù)據(jù)外包到云端進(jìn)行存儲(chǔ)。這樣不僅能減輕用戶的存儲(chǔ)和管理負(fù)擔(dān)，還可以為用戶的數(shù)據(jù)訪問提供便捷服務(wù)。然而，作為一個(gè)第三方存儲(chǔ)服務(wù)提供商，云服務(wù)器不是完全可信的[1]。圖像內(nèi)容中的一些敏感信息可能會(huì)泄露給云服務(wù)器，造成用戶的隱私泄露。為了保護(hù)圖像數(shù)據(jù)隱私，防止圖像被非法訪問。用戶必須在圖像外包以前對(duì)圖像進(jìn)行加密，然后再將加密后圖像上傳到云端[3]。使用圖像時(shí)，用戶需要先從云端將圖像下載到本地，然后解密后才能使用。當(dāng)圖像數(shù)據(jù)的規(guī)模很大時(shí)，這種“加密上傳、下載解密”的使用方式將會(huì)變得非常低效，這也違背云計(jì)算所倡導(dǎo)的數(shù)據(jù)便捷使用的初衷。所以對(duì)加密域的圖像進(jìn)行檢索就變得非常重要，而在此之中，對(duì)加密圖像進(jìn)行特征提取則是重中之重。如何對(duì)加密域的圖像進(jìn)行處理、提取特征，并且不會(huì)使第三方獲得所提取到的關(guān)鍵點(diǎn)，使對(duì)加密域內(nèi)的圖像進(jìn)行處理這項(xiàng)工作具有重要的意義[7-10]。

現(xiàn)有的大多數(shù)方案采用Paillier加密來實(shí)現(xiàn)，然而Paillier加密具有計(jì)算量大、效率低等問題。為了解決該問題，本文利用對(duì)稱同態(tài)加密算法來對(duì)圖像進(jìn)行加密，并基于密文域來實(shí)現(xiàn)圖像的特征提取。它不僅保證外包圖像的隱私安全，也保證了圖像特征提取時(shí)的隱私。

1 對(duì)稱同態(tài)加密算法的構(gòu)造

1.1 對(duì)稱同態(tài)加密算法

現(xiàn)有在密文域上對(duì)圖像特征進(jìn)行提取的方案大多數(shù)采用Paillier加密來實(shí)現(xiàn)，然而Paillier加密具有計(jì)算量大、效率低等問題，而對(duì)稱加密具有計(jì)算量小、加密速度快、效率高等特點(diǎn)。為此，本文將構(gòu)造一種新的對(duì)稱同態(tài)加密算法用來對(duì)圖像進(jìn)行處理。其算法流程如下：

1）密鑰生成

KeyGen(x)→(key,p)該密鑰生成算法是一個(gè)概率算法。其中，p，q是大的素?cái)?shù)且p＞＞q，b是一個(gè)隨機(jī)整數(shù)。

2）加密

E(m,w,a)=(awq+bm)modp加密算法也是一個(gè)概率算法，用來對(duì)消息m進(jìn)行加密。其中，a是一個(gè)小正整數(shù)，w是一個(gè)大的隨機(jī)整數(shù)，m為輸入的明文。

3）解密

D(key,c)=(cmodp)×q-1×b-1解密算法是一個(gè)確定性算法，c為所需的密文。

1.2 同態(tài)性證明

設(shè)c1，c2分別是明文i1和i2的密文，w1和w2是兩個(gè)正的隨機(jī)整數(shù)，a1和a2是兩個(gè)正的小隨機(jī)整數(shù)，p和q是兩個(gè)大的素?cái)?shù)并且p＞＞q，c1=(a1w1q+bi1)modp，c2=(a2w2q+bi2)modp。

同態(tài)加性證明：

上述的同態(tài)加法、同態(tài)減法這些操作表明：此加密算法可以對(duì)存儲(chǔ)在云上的密文數(shù)據(jù)進(jìn)行操作。

1.3 密鑰空間分析

在本文中，密鑰長(zhǎng)度為150位，密鑰空間約為2150位，密鑰大小為2150的加密圖像不易受到暴力破解的影響。因此，這個(gè)密鑰大小就足夠了。在實(shí)現(xiàn)過程中，密鑰的位數(shù)可以增加。然而，這樣做可能會(huì)導(dǎo)致系統(tǒng)的速度降低，對(duì)硬件的要求也會(huì)變高。

圖1 用戶與云端交互模型Fig.1 User cloud interaction model

2 同態(tài)加密的圖像特征提取

2.1 用戶與云端交互模型

如圖1所示，在此模型中，服務(wù)器端由兩個(gè)服務(wù)器組成，一個(gè)為主服務(wù)器S1，一個(gè)為輔服務(wù)器S2。首先，在用戶端，用戶加密圖像image→Ie，生成密鑰對(duì)(key,p)，并將密鑰q分解為q1和q2，即q=q1*q2，并將它們分別發(fā)送給服務(wù)器端S1和S2。之后，由S1和S2聯(lián)合計(jì)算得到圖像的特征。最后，由服務(wù)器端將得到的結(jié)果發(fā)送給用戶端，用戶用密鑰解密即可得到結(jié)果。

2.2 矩陣運(yùn)算協(xié)議

1）加密矩陣的卷積運(yùn)算(CMC)：給定一個(gè)公共矩陣B和加密矩陣A，則

2）加密矩陣的乘法運(yùn)算(CMM)：給定加密矩陣A和B，則

a） S1計(jì)算RA，RB(RAi,j,RBi,j，)，然后計(jì)算X=[A]·[RA]，Y=[B]·[RB]，X1=PDec(1)(X,b,q1)，Y1=PDec(2)(Y,b,q2)，然后將(X,Y,X1,Y1)發(fā)送給S2。

b） S2計(jì)算h=PDec(2)(X,X1,b,q2)·PDec(2)(Y,Y1,b,q2)，再將h加密為[H]給S1。

c） S1計(jì)算[A·B]=H·[RA·RB]P-1·[A]EP-PA·[B]EP-PB，其中EP為全P矩陣。

3）加密矩陣異或運(yùn)算(CMXOR)：給定[A]和[B]，計(jì)算[A⊕B]=CMM([E]·[A]P-1;[E]·[B]P-1)·CMM([A];[B])，其中E為全1矩陣。

4）加密矩陣的差值運(yùn)算(CMD)：給定兩個(gè)加密矩陣[A]和[B]返回一個(gè)密文矩陣[F]用來表示這兩個(gè)矩陣之間的差值。

a）S1計(jì)算[A']=[2A+E]=[A]2·[E]，[B']=[2B]=[B]2，其中E為全1矩陣。之后，S1選擇兩個(gè)隨機(jī)矩陣[R]，[S]，其中||R||≤||P||/4，Si,j∈{0,1}，然后計(jì)算[T]=[R·(A'-B')·S+R·(B'-A')·(E-S)]，之后將[T]和PDq(1)([T])發(fā)送到S2。

b）S2將[T]解密后得到T，如果||Ti,j||≤||P||/2，那么S2令Uij=1，否則為0。

然后S2用密鑰加密U，并把[U]發(fā)送給S1。

c）S1計(jì)算[F]=([U·S+(E-U)·(E-S)])=([U]S)·([E]·[U]P-1)E-S，若Fi,j=1，則ai,j＞bi,j，否則相反。

2.3 在加密域中對(duì)圖像的特征提取

1）首先，在用戶端生成密鑰對(duì)(key,p)，并將圖像進(jìn)行加密image→Ie，將密鑰q分為q1和q2且q=q1*q2，并將它們分別發(fā)送給服務(wù)器端S1和S2。S1收到I后，計(jì)算[D]，[D]=[(G(x,y,kσ)-G(x,y,σ))*I(x,y)] ，并生成27個(gè)相鄰矩陣。

2）S1和S2共同計(jì)算[Ui]=CMD([D];[Ai])，1≤i≤27；若Uij=1，則為潛在特征點(diǎn)。

4）S1加密Hessian矩陣[H]，設(shè)

并計(jì)算

之后由S1計(jì)算

最后，S1用密鑰加密閾值矩陣[ET]，ET是全閾值矩陣，S1和S2共同計(jì)算

S1將[F]發(fā)送給用戶，用戶用密鑰即可解密獲得特征值。

2.4 描述子的獲取

1）給定[I]，S1計(jì)算[L]，并生成4個(gè)方向的矩陣L1，L2，L3，L4。

2）S1和S2共同計(jì)算

圖2 實(shí)驗(yàn)結(jié)果Fig.2 Experimental results

表1 特征點(diǎn)匹配對(duì)比結(jié)果Table 1 Comparison results of feature point matching

3）S1和S2共同計(jì)算

對(duì)于一個(gè)4*4的子塊，最終會(huì)形成一個(gè)64維的加密矩陣[V]，用戶通過之前得到解密結(jié)果來解密[V]，便可得到描述子。[V]為被加密的特征描述子。

3 實(shí)驗(yàn)結(jié)果

本文在Intel(R)Core(TM)i7-8700CPU@3.20GHz環(huán)境下，使用Neo4j數(shù)據(jù)庫進(jìn)行實(shí)驗(yàn)，并選取了幾幅有代表圖像作為本次實(shí)驗(yàn)的結(jié)果，圖2為本次實(shí)驗(yàn)結(jié)果的示意圖，表1為選取了3組圖像的3張圖像作為本方案和原始sift方案提取出特征點(diǎn)的對(duì)比結(jié)果。

如圖2所示，該方法實(shí)現(xiàn)了安全的外包，完成了對(duì)圖像的特征提取，同時(shí)保持了關(guān)鍵點(diǎn)位置的隱私性。表1選取多幅圖像的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，表1表明：與明文域所提取出的特征相比，提取結(jié)果正確率接近90%，表明該方案具有較高的可行性。

4 總結(jié)

本文提出了在加密域內(nèi)對(duì)圖像特征提取的框架。適用于對(duì)隱私保護(hù)有需求的用戶，當(dāng)用戶將加密數(shù)據(jù)作為查詢內(nèi)容發(fā)送至服務(wù)器端，服務(wù)器則可以在接收到加密的數(shù)據(jù)時(shí)進(jìn)行運(yùn)算，最終將對(duì)應(yīng)的加密數(shù)據(jù)返回給用戶。整個(gè)過程中，服務(wù)器端以及在傳輸過程中都是加密的圖像，保護(hù)了數(shù)據(jù)隱私。