基于秘密共享的同態加密圖像可逆信息隱藏算法

周 能， 張敏情， 劉蒙蒙

(武警工程大學密碼工程學院，網絡與信息安全武警部隊重點實驗室，西安 710086)

可逆信息隱藏作為一種維護網絡空間安全的重要技術手段，在網絡安全通信、數字版權保護等領域發揮著重要作用。Shi等[1]較為完整地總結了過去二十年可逆信息隱藏算法的發展歷程，可逆信息隱藏主要有無損壓縮、差值擴展和直方圖平移。可逆信息隱藏本身比較復雜，需要確保載體的可恢復性，以及嵌入信息的完整提取，而加密域可逆信息隱藏又需要進一步處理好解密和提取信息之間的關系。Zhang[2]首次提出密文圖像可逆信息隱藏算法，該算法用流密碼加密圖像，類似的算法還有文獻[3-5]。雖然流加密的計算復雜度低、加解密速度快，但是有密鑰傳遞、密鑰管理等方面的問題。Chen等[6]首次提出了基于公鑰密碼的加密域可逆信息隱藏，利用公鑰密碼的特點克服對稱加密需要安全通道事先傳遞密鑰的缺點，該算法將1 bit信息嵌入到一對相鄰加密像素中，根據Paillier密碼體制加密的同態特性，接收端通過比較所有的解密像素對獲得秘密信息，后來繼續進行研究創新的主要文獻有[7-9]。利用公鑰密碼可以大大減少密鑰量，且無須事先傳遞密鑰，可是也帶來了較大的密文擴展，且計算復雜度高。比較好的方法是對密文冗余進行重量化與再編碼嵌入秘密信息，相關文獻有[10-12]。

與上述文獻中的方法不同，Wu等[13]首次利用Shamir(k,n)門限秘密共享設計了加密域可逆信息隱藏算法。該算法利用秘密共享將原始圖像加密成n份，分別發送給n位不同的數據嵌入者，數據嵌入者通過在密文上進行差值擴展或差值直方圖平移操作嵌入信息，接收者得到少于k份時無法恢復原始圖像。實際上，文獻[13]的方法將一個像素加密成了n份，那么一個密文像素就擴展成8nbits。而Chen等[14]利用的是多秘密共享加法同態的特點結合差值擴展算法[15]進行信息嵌入，該算法將像素值作為多項式的系數而不是多項式的常數項，因而降低了算法的時間復雜度。本文在Chen算法的基礎上應用了Shamir(k,n)門限秘密共享的優點，首先用Shamir秘密共享體制把圖像加密成n份，并分發給n個不同的存儲和處理中心；每個存儲和處理中心執行同樣的嵌入策略，即利用Shamir秘密共享體制的加法同態特性嵌入信息；當持有k份額，就可以完成原始圖像的可逆恢復。

1 Shamir門限秘密共享體制的構造

Shamir提出了一種基于多項式的拉格朗日插值公式的門限秘密共享方案[16]。

設q是素數的冪，ID是有限域GF(q)的本原元，共享的秘密是D∈GF(q)，隨機選取GF(q)上的k-1次多項式f(x)，使得：

f(x)=D+a1x+a2x2+…+ak-1xk-1

(1)

假設n個參與者能夠正確提供k個份額Di(i=1,2,…,k)，則根據拉格朗日插值公式得到

(2)

則f(x)的常數項，即秘密D=f(0)，并且每個參與者IDi都可利用自己掌握的份額Di來驗證所求得的f(x)是否正確，從而能夠發現其他參與者可能存在的欺騙行為。

當份額數量r

2 基于秘密共享的同態加密圖像可逆信息隱藏算法

秘密共享可作為一種保護圖像隱私的加密方法，以Shamir(3, 5)門限秘密共享為例研究本文算法的實現，圖1顯示了秘密共享在用戶和云端之間的應用流程。用戶利用身份IDi(i=1,2,…,5)將原始圖像加密成5份密文圖像，然后把這5份密文圖像分別上傳給不同的存儲和處理中心，此外，用戶需要將身份ID1～ID5通過安全的方式分別發送給5個不同的存儲和處理中心，即存儲和處理中心1擁有ID1，存儲和處理中心2擁有ID2，…，存儲和處理中心5擁有ID5。這樣存儲和處理中心就能夠用身份對要嵌入的數據進行加密，而后應用Shamir門限秘密共享的加法同態進行信息嵌入。最后，合法的接收者只要有3個以上的份額就可正確解密。

圖1 秘密共享在用戶和云端之間的應用Fig.1 Application of secret sharing between users and cloud

算法中，密文圖像分別由不同的存儲和處理中心保管，部分存儲和處理中心被人為攻擊破壞或自身故障不會泄露密文圖像。假設攻擊者Adversary無法獲得2個以上的份額，那么算法就是安全的。

2.1 算法框架

以一對像素為例來演示總體框架，設有限域的大小為251，即q=251，圖2所示為基于秘密共享的同態加密圖像可逆信息隱藏算法流程圖。圖像所有者首先按照差值擴展的方法預處理原始像素對，然后用秘密共享加密得到5對密文像素，最后將5對密文像素分別上傳給5個不同的存儲和處理中心；數據嵌入者將要嵌入的信息1轉成(1, 0)，而后按照同樣的方式加密得到密文信息，接著將密文信息與密文像素相加得到攜密密文像素，實際上5個存儲和處理中心執行同樣的嵌入策略；合法的接收者獲得3個以上的份額就可以重構拉格朗日插值多項式正確解密并提取嵌入的信息。

圖2 所提算法流程圖(以t=2，即一對像素為例)Fig.2 The sketch of the proposed algorithm(take t=2 as an example, which is a pair of pixels)

2.2 算法過程

2.2.1 密鑰生成

2.2.2 圖像加密

(1)生成t個2次多項式用于加密圖像fi(x)=r2i-1x2+r2ix+pi(mod251),i∈[1,t]。

2.2.3 信息嵌入

2.2.4 解密并提取信息

2.2.5 舉例說明算法具體過程

數據嵌入者實際上是5個存儲和處理中心，它們執行同樣的嵌入策略。都是將秘密信息m=1擴展為一對(1, 0)，然后利用和圖像所有者同樣的方式得到密文信息(18, 12)、(54, 30)、(112, 54)、(189, 84)和(35, 120)。5個存儲和處理中心分別將密文信息與密文像素相加得到攜密密文像素(139, 122)、(212, 158)、(76, 206)、(230, 15)和(173, 87)。

接收者獲得3份攜密密文像素就可以重構拉格朗日插值多項式，計算攜密明文像素為(105, 98)，根據差值擴展的性質，因為(105+98)mod2=1，所以提取秘密信息為1，最后恢復原始像素值為(103, 100)。

2.3 邊信息處理

在可逆信息隱藏中，邊信息在可逆恢復過程中十分重要，因而采用標準的邊信息處理方式。本文算法有兩處產生邊信息。

(1) 差值擴展產生不可嵌入位置：當像素對(x′i,y′i)中任一像素不在圖像灰度[0, 255]的范圍內，標記為不可嵌入位置。

可用位圖的方法，即式(3)來標記這些不可嵌入位置：

(3)

圖像中的不可嵌入位置是少數，即位圖中1是少數，大多數是0，這樣可以將位圖壓縮后作為邊信息嵌入到圖像中。圖像所有者按下列步驟處理圖像。

(1)將圖像分為兩部分，并得到邊信息，記為I。

(2)利用秘密共享加密圖像第一部分的像素，并將密文像素最低有效位(least significant bit, LSB)標記為L。

(3)將邊信息I通過直接替換圖像第一部分LSB的方式進行嵌入。

(4)將L按照本文算法嵌入圖像的第二部分。

數據嵌入者收到密文圖像后，可得到邊信息I，然后在圖像的第二部分嵌入秘密信息S。通常約定圖像的第1行嵌入I、第2行和第3行嵌入L、其余部分嵌入S。這樣就可以知道嵌入的起點和終點，至此完成了邊信息的處理。

3 仿真實驗與理論分析

為測試本文算法性能，選用USC-SIPI圖像庫中大小為512×512的6幅標準測試灰度圖像，如圖3所示，并用MATLAB R2015b編程進行仿真實驗。

圖3 標準測試圖像Fig.3 Standard test images

3.1 嵌入率和峰值信噪比分析

峰值信噪比(peak signal-to-noise ratio, PSNR)通常被用來評價載體圖像質量，根據人類視覺系統的特點，通常認為PSNR>35 dB時，人眼覺察不到圖像有明顯的失真，PSNR可由式(4)計算。

(4)

式(4)中：MSE(mean square error)是原圖像和嵌入信息后圖像之間的均方誤差，可由式(5)計算：

(5)

式(5)中：MN是圖像大小；p(i,j)表示原圖像的像素；c(i,j)表示嵌入信息后圖像的像素。

圖4給出了6幅標準測試圖像在不同嵌入率(embedding rate, ER)下的PSNR，本文算法的嵌入率由式(6)得到。

圖4 所提算法的性能Fig.4 Performance of the proposed algorithm

(6)

式(6)中：L表示圖像像素個數；N表示圖像中不可嵌入的像素個數。圖5給出了不同算法對Lena圖進行實驗的數據對比。表1列出了6幅標準測試圖像不可嵌入像素個數以及最大嵌入率。

表1 最大嵌入率

圖5 Lena圖像性能對比Fig.5 Comparisons on Lena

因為文獻[4]采用加密前預留空間的策略進行信息嵌入，有效降低了直接解密圖像的失真，所以其PSNR要高于本文算法；文獻[8]將Paillier公鑰加密和濕紙編碼相結合進行兩次信息嵌入，當嵌入率較低時，其算法性能要稍優于本文算法，但是隨著嵌入容量的增加，兩次信息嵌入給圖像帶來的失真也越來越大，從而導致PSNR下降較快；文獻[9]同樣在加密前預留了部分位平面數據，而后利用Paillier的同態加法在鏡像密文組的目標像素上嵌入信息，可是該算法構造鏡像密文組的方法給圖像造成的失真較大，因而本文算法的PSNR要高于文獻[9]；文獻[14]和本文算法都是結合差值擴展算法進行信息嵌入提取，所以算法性能較為接近。

圖6給出了利用本文算法對Lena圖像進行加密得到的加密圖像份額、直接解密后的攜密明文圖像和無損恢復的圖像。嵌入容量為130 989 bits，直接解密圖的PSNR為33.151 dB。

圖6 Lena測試圖像及加密圖像Fig.6 The testing Lena image and encrypted images

3.2 算法綜合性能分析

當前，加密域可逆信息隱藏中利用最為廣泛的加密方式是流加密和Paillier公鑰加密，為了對比分析的全面性，選擇采用流加密和Paillier公鑰加密的兩種典型加密域可逆信息隱藏算法與文獻[14]、本文算法進行性能對比分析。

時間復雜度：利用流密碼加密和解密一個像素的時間復雜度是O(1)；利用Paillier公鑰密碼加密和解密一個像素的時間復雜度是O(n3)；利用秘密共享加密和解密一個像素的時間復雜度分別是O(n)和O(nlog2n)。

數據擴展：數據擴展是指原始圖像在加密后有較大的密文擴展。利用流密碼的算法沒有數據擴展，如文獻[4]，所以數據擴展為1；利用Paillier公鑰密碼的算法數據擴展較大，如文獻[8-9]，灰度圖像的像素值是8 bits，如果使用512 bits的密鑰，密文像素值為1 024 bits，所以數據擴展為128；雖然文獻[14]利用的是多秘密共享加密，但是將8 bits的灰度圖像仍然加密成8 bits的密文圖像，所以數據擴展同樣為1，因而在恢復原始像素時并未體現出秘密共享的特性；本文算法利用的是Shamir(3, 5)門限秘密共享，把1個像素加密成5個密文像素，所以數據擴展為5，雖然數據擴展比文獻[14]要高，但是任意3個密文像素都能夠恢復出原始像素，體現出了秘密共享的思想。表2給出了所提算法與相關算法的特征比較。

表2 所提算法與相關算法的特征比較

4 結論

本文算法利用Shamir秘密共享體制加密圖像，而后利用其滿足的加法同態特性進行信息嵌入，通過對算法的理論分析與仿真實驗得到以下結論。

(1)利用秘密共享加密圖像達到了分散風險和容忍入侵的目的，與此同時，利用的差值擴展算法嵌入率高且能夠實現完全可逆。

(2)本文算法的時間復雜度要比利用Paillier公鑰密碼加密圖像的時間復雜度低，且數據擴展小。