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

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

0 引言

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

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

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

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

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

1）密鑰生成

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

2）加密

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

3）解密

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

1.2 同態(tài)性證明

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

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

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

1.3 密鑰空間分析

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

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

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

2.1 用戶與云端交互模型

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

2.2 矩陣運算協(xié)議

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

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

a） S1計算RA，RB(RAi,j,RBi,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計算h=PDec(2)(X,X1,b,q2)·PDec(2)(Y,Y1,b,q2)，再將h加密為[H]給S1。

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

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

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

a）S1計算[A']=[2A+E]=[A]2·[E]，[B']=[2B]=[B]2，其中E為全1矩陣。之后，S1選擇兩個隨機矩陣[R]，[S]，其中||R||≤||P||/4，Si,j∈{0,1}，然后計算[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計算[F]=([U·S+(E-U)·(E-S)])=([U]S)·([E]·[U]P-1)E-S，若Fi,j=1，則ai,j＞bi,j，否則相反。

2.3 在加密域中對圖像的特征提取

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

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

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

并計算

之后由S1計算

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

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

2.4 描述子的獲取

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

2）S1和S2共同計算

圖2 實驗結(jié)果Fig.2 Experimental results

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

3）S1和S2共同計算

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

3 實驗結(jié)果

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

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

4 總結(jié)

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