一種適用于彩色圖像的秘密共享方案

劉 麗，王安紅，劉文杰，王鋼飛

(太原科技大學電子信息工程學院，太原 030024)

秘密共享是現代密碼學領域中的一個很重要的分支，它對信息和數據的安全存儲、傳輸以及合法利用都有著十分重要的作用。1979年Shamir提出了(k，n)門限秘密共享方案[1]，將一個主秘密拆分成n個子秘密分發給n個不同的參與者保管，只有收集到其中任意k個或k個以上的子秘密才能夠恢復出主秘密，而任何少于個參與者的集合都無法得到主秘密。通過這種方式，可以分散責任，保證了秘密信息的安全性。

1994年文獻[2]將秘密共享的思想應用于圖像領域，提出了一種新的圖像秘密共享方案，其基本思想:將原秘密圖像S分割成n幅影子圖像，分發給n個不同的接收者。

(1)任意的k(k≤n)幅或多于幅影子圖像的組合均可以恢復原秘密圖像S.

(2)任意(k－1)幅或少于k幅影子圖像的組合均不能恢復原秘密圖像S.

然而，這一方案的缺點是影子圖像的尺寸比原秘密圖像大，且恢復出的圖像失真。這一缺點的存在違背了圖像秘密共享方案的初衷，對秘密數據的存儲、傳輸及利用都帶來了很大的阻礙。因此，圖像秘密共享要求圖像質量得到保證的前提下，影子圖像尺寸越小越好。

基于(k，n)門限方案，文獻[3]利用(k－1)階Lagrange插值多項式對原秘密圖像進行共享，將像素的灰度值作為多項式的系數，從而使得影子圖像的大小變為原圖像的1/k，且恢復的效果更好。但是由于相鄰像素之間存在強相關性，導致生成的影子圖像中存在少許的暗影輪廓，甚至在重構時少于個接收者也可能恢復原秘密圖像。文獻[4]在文獻[3]的基礎上，引入了Huffman壓縮編碼，進一步減小了影子圖像的尺寸。文獻[5]針對圖像秘密共享前需要置亂的問題，提出了一種免置亂的秘密共享方案，即保證了影子圖像的尺寸為原圖像的1/k，也有效降低了算法的復雜度。為了進一步提高算法的安全性，文獻[6-8]提出了安全的可驗證的秘密共享方案，這些方案彌補了參與者之間欺騙的安全缺陷，同時又減小了算法的計算量。然而，以上方案均是針對灰度圖像進行處理，彩色圖像的數據量是灰度圖像的3倍。因此，對于數據量龐大的彩色圖像，以上方案就不能使用了。

針對以上問題，提出了一種適用于彩色圖像的秘密共享方案，首先分析彩色圖像的R，G，B三個位平面以便對彩色圖像進行壓縮，然后利用Shamir的(k，n)門限思想將壓縮的彩色圖像分為n個影子圖像，最后通過收集到的k個不同接收者的影子圖像恢復原秘密彩色圖像。實驗表明所提方案不僅有效地減小了影子圖像的尺寸、降低了計算復雜度，而且極大程度減少了相鄰像素之間的相關性，提高了原秘密圖像的安全性。

1 本文的方案

本文的方案由兩個關鍵部分組成:GSBTC壓縮編碼和Shamir的(k，n)門限方案。如圖1所示。

圖1 秘密圖像共享(2，4)門限方案示意圖Fig.1 Sketch map of secret image sharing(2，4)threshold scheme

1.1 GSBTC 壓縮編碼

在圖像秘密共享之前，首先采用GSBTC對彩色圖像進行壓縮。GSBTC(Gradual search algorithm for one single bitmap BTC)[9]，即單一位平面的逐級搜索算法，該算法基于傳統的BTC(Block Truncation Coding)編碼算法，針對彩色圖像的三基色分量，分別確定各分量的位平面，并采用逐位比較的方法來確定三基色分量的公共平面，從而達到壓縮的目的。具體步驟如下:

步驟1:將原秘密彩色圖像S分成4×4大小且無重疊的塊，提取各塊的R，G，B三基色分量，對每一個分量作傳統的BTC編碼，記錄每一個分量中0組和1 組像素的均值，即(R0，R1)，(G0，G1)，(B0.B1)，以及每一個分量的位平面 BR，BG，BB.

步驟2:公共平面BC的確定(該步驟基于圖像塊完成)。

(1)對比 BR，BG，BB這三個平面，若相應位置的值相等，則將該值放入公共平面BC的相應位置中;若不相等，則公共平面BC中相應位置處置空值，即:

其中ri為圖像塊中第i個像素R分量在BTC編碼后的位平面值，gi，bi類似。

(2)使用公式(2)和(3)計算公共平面BC的均方誤差MSE，BC中空值的部分可忽略不計。

其中，xi=(xRi，xGi，xBi) 為像素值，p，q 分別為BC中0和1的個數。

(3)搜索BC中的第一個空值，分別用BR，BG，BB面中相應位置的值替換，并利用公式(2)和(3)重新計算 MSE，分別記為 newMSER，newMSEG，newMSEB(注意，此時p，q的值會發生變換)。

(4) 比較 newMSER、newMSEG、newMSEB值，選擇其中最小值為newMSE，并用該分量位平面中相應位置的值替代公共平面BC中對應位置的空值。

(5)重復步驟(2)-(4)，直到塊中所有的空值都被替代。

至此，塊的公共平面BC被確定。

步驟3:重復步驟1和步驟2，直到原秘密彩色圖像S中所有的塊均被處理完畢。

記錄每一個塊的(R0，R1)，(G0，G1)，(B0，B1)以及公共平面BC.

1.2 影子圖像的產生

為了減小相鄰像素之間的相關性，提高圖像的安全性，本文采取了以下方案:首先對公共平面BC做50次迭代的Arnold置亂處理，將置亂后的矩陣存入矩陣中，然后對 (R0，R1)，(G0，G1)，(B0，B1)和利用Shamir(k，n)門限方案進行秘密共享，分割出影子圖像。

步驟1:將4×4的矩陣E轉換為2×8的矩陣E'，將矩陣E'按行轉換成十進制數(d0，d1);

步驟 2:計算每一塊的 (R0，R1)，(G0，G1)，(B0，B1)，(d0，d1) 的值，依次放入集合 P 中。

步驟3:從集合P中順序選取k個未被共享的元素作為公式(5)的k個系數，

其中 a0，a1，…ak－1是 k 個系數，j∈[1，s]，且

其中，b為原秘密圖像的分塊數，4×4為分塊的尺寸，s為影子圖像中像素個數。這里注意，對(R0，R1)，(G0，G1)，(B0，B1) 分別量化為 2 個字節，而BC占用2字節。

步驟 4:取 x=1，2…n，分別計算出 fj(1)，fj(2)，…fj(n)，并依次順序賦給幅影子圖像矩陣。

步驟5:重復步驟3和步驟4，直到集合P中所有的元素均被處理完畢。將n幅影子圖像順序發給n個接收者。

1.3 圖像的重構

在接收端，k個接收者提供合法的影子圖像，并通過以下方法重構出原始的秘密圖像。

(1)從k幅合法的影子圖像矩陣中分別提取出第一個未被處理的像素灰度值，{f1(i1)，f1(i2)，…，f1(ik)};

(2) 用 k 個點{(i1，f1(i1))，(i2，f1(i2))，…，(ik，f1(ik))}通過拉格朗日插值多項式構造k－1階多項式，

并提取多項式的系數;

(3)重復(1)和(2)直到影子圖像中所有的像素點都被處理完畢，依次記錄多項式的系數，恢復集合P.

(4)將(d0，d1)轉換為二進制，并恢復為4×4的公共平面矩陣E。

(5)做Arnold置亂的逆處理，恢復塊的公共位平面BC.

(6)用 (R0，R1)，(G0，G1)，(B0，B1) 和 BC做BTC的解碼，得到原秘密彩色圖像S.

2 實驗結果與性能分析

根據本文方案，使用Matlab7.0環境做了以下兩組實驗。

實驗一:選取尺寸為512×512的Lena.bmp作為原秘密彩色圖像 S，實現(2，4)門限分割方案。如圖2所示。

圖2 (2，4)門限方案Fig 2 (2，4)threshold scheme

圖2中，(a)為原秘密彩色圖像S;(b)是由4幅影子圖像中第一和第三幅圖像組合恢復后的秘密彩色圖像，其峰值信噪比PSNR=30.1dB;(c)-(f)為4幅影子圖像，其尺寸為256×256，是原秘密彩色圖像的1/4.

從圖2可以看出，本方案分割后的影子圖像沒有了原彩色圖像的色彩、輪廓和暗影。GSBTC壓縮編碼屬有損壓縮，但是恢復后的彩色圖像的PSNR=30.1dB.可見，本方案在保證原秘密彩色圖像質量的前提下，將影子圖像的尺寸縮減到原圖像的1/4，同時，在信道中傳輸的影子圖像的數據量是原秘密圖像的1/2(每幅影子圖像僅需要傳輸彩色圖像塊的(R0，R1)，(G0，G1)，(B0，B1)和 BC的部分信息，分別對應2字節的量化比特，因此數據量是彩色圖像的1/6k)。

實驗二:選取尺寸為512×512像素的baboon.bmp作為原秘密彩色圖像S，實現(8，10)門限分割方案。如圖3所示。

圖3 (8，10)門限方案Fig 3 (8，10)threshold scheme

圖3中，(a)是原秘密彩色圖像S;(b)是由8幅影子圖像:(c)、(d)、(f)、(g)、(h)、(j)、(k)和(l)組合恢復的秘密彩色圖像，其PSNR=22.8dB;(c)-(l)為10幅影子圖像，影子圖像的尺寸為128×128，是原秘密彩色圖像的1/16.

實驗二進一步驗證了本方案的可行性。由圖3可以得出，恢復后彩色圖像的質量并未受到很大的影響，影子圖像的尺寸縮減到原圖的1/16，而在信道中傳輸的影子圖像的數據量是原秘密圖像的1/48.

影子圖像產生的過程中，方程(6)中的k值越大，相應的s個數就越少，影子圖像的尺寸也就越小。可見，影子圖像的數量越多，圖像的尺寸就會越小，用于信道中傳輸的影子圖像的數據量也就越小。

為了進一步說明實驗結論的正確性，本文在相同的環境下對不同尺寸的圖像做了大量的實驗，實驗結果如表1所示。

表1 Shamir門限方案產生的影子圖像尺寸對照表Tab.1 The size of shadow image produced by Shamir threshold scheme

表中，T表示原始秘密圖像的尺寸(像素點)，k表示Shamir門限方案中的門限值。為了使產生的影子圖像整齊，k通常取2的整數次冪。通過表1中的數據可以看出，影子圖像的尺寸僅為原圖像的1/2k大小，明顯小于原秘密圖像，而送入信道中傳輸的影子圖像的數據量也僅為原秘密圖像的1/6k.

3 結束語

本文提出了一種有效的適用于彩色圖像的秘密共享方案。彩色圖像恢復時，只要任何k幅影子圖像即可恢復原秘密彩色圖像，而任何少于k幅的影子圖像則無法得到關于原圖像的任何信息。通過大量的實驗數據表明，影子圖像的尺寸僅為原圖像的1/2k，且送入信道中傳輸的影子圖像的數據量也僅為原秘密圖像的1/6k.因此，在實際的應用中，本文方案不僅能大量節省圖像的存儲空間，同時也能縮減圖像的傳輸時間。然而，由于GSBTC壓縮算法屬于有損壓縮，在對圖像精度要求較高的醫療或軍事領域內，該方案就不能適用了。

[1]SHAMIR A.How to Share a Secret[J].Communications of ACM，1979，24(11):612-613.

[2]NAOR M，SHAMIR A.Visual Cryptography[C]//Proc.Of Advances in Ctyptology-EUROCRYPT`94.Berlin，Germany:Springer，1995:1-12.

[3]THIEN C，LIN J.Secret Image Sharing[J].Computer Graphics，2002，26(1):765-770.

[4]WANG R Z，SU C H.Secret Image sharing with smaller shadow images[J].Pattern Recognition Letters，2006，27(6):551-555.

[5]周清雷，郭銳.高效免置亂的圖像秘密共享方案[J].計算機工程，2010，36(9):126-128.

[6]白曉，余梅生.基于證書的可驗證多秘密共享方案[J].計算機工程與應用，2009，45(7):127-128.

[7]候整風，韓江洪.防欺騙(t，n)秘密共享模式研究[J].浙江大學學報:理學版，2007，34(6):633-635.

[8]LI B.A reliable(k，n)image sharing scheme[C]//Proc.Of DASC`06.Indianapolis，USA:2006:31-36.

[9]CHANG C C，WU M N.An algorithm for color image compression based on common bit map block truncation coding[C]//Joint Conference on Information Sciences，2002:964-967.