基于翻轉操作的(2, n)異或圖像分存方案

歐鍛灝， 吳小天， 程斌宜， 孫 偉,3

(1. 中山大學信息科學與技術學院，廣東 廣州 510006；2. 中山大學軟件學院，廣東 廣州 510006；3. 中國科學院信息工程研究所信息安全國家重點實驗室，北京 100093)

基于翻轉操作的(2, n)異或圖像分存方案

歐鍛灝1， 吳小天1， 程斌宜2， 孫 偉2,3

(1. 中山大學信息科學與技術學院，廣東 廣州 510006；2. 中山大學軟件學院，廣東 廣州 510006；3. 中國科學院信息工程研究所信息安全國家重點實驗室，北京 100093)

通過翻轉操作來構造圖像分存方案的新方法。所構造的分存方案將秘密圖像以一種無需任何密碼學知識的安全方式進行編碼，且無需額外地隱藏處理過程就能生成有意義的分存圖像。該分存方案沒有像素膨脹，且不需要設計碼本。秘密黑色像素的重構是完美的，所有的秘密黑色像素都能夠被精準地恢復。首先利用翻轉操作構造一個有意義的(2, 2)方案，繼而擴展出一個有意義的(2, n)方案。理論證明和實驗結果表明了提出的分存方案正確和有效。

秘密圖像分存；翻轉操作；有意義的分存圖像；完全性黑的；異或操作

Blakley[1]和 Shamir[2]于 1979年提出了將一個秘密分成幾份的秘密分存方法。在該分存方法中，除非收集到足夠多的分存份額，否則任何人都不可能得到秘密信息。視覺密碼 (visual cryptography,VC)[3]是一種特殊的秘密分存，它將一幅秘密圖像進行編碼，生成幾幅隨機的圖像。在(k, n)VC方案中，疊加k幅或者更多的隨機分存圖像可以顯示出秘密圖像的信息。但是，k–1或者更少隨機圖像將無法得到秘密圖像的任何信息。VC不同于一般的圖像加密方法[4-5]，它增加了秘密的冗余，降低了秘密圖像丟失的風險性。由于視覺密碼方案具有解碼簡單快速的優點，許多學者對其進行了廣泛地研究[6-8]。不幸的是，由于疊加操作解密的緣故，產生的分存圖像和重構圖像在視覺效果上都不盡如人意。此外，在疊加解密過程中，還遭遇像素對齊的問題。這些問題導致視覺密碼在應用上的局限性。

為了解決傳統 VC中低視覺效果和像素對齊的問題，一種利用“異或”操作取代“疊加”操作來解密圖像的分存方案[9-10]產生了。相比之下，基于“異或”操作的分存方案解決了像素膨脹，低視覺效果和像素對齊等問題。但是，目前大多數基于異或操作的分存方案所產生的分存圖像是一個無意義的、隨機圖像。產生有意義的分存圖像對分存圖像的管理上具有很大的意義，所以大多數學者致力于研究有意義的圖像分存方案[6,11-12]。

本文構造了一個能夠產生有意義分存圖像的、基于翻轉操作的(2, n)異或圖像分存方案，并可利用異或操作代替“疊加”操作對秘密圖像進行解密。本文方案滿足秘密分存概念中的安全性和對比度的條件，而且具有無碼本和無像素膨脹的優點。除此之外，本文所提出的圖像分存方案還具有如下優點：

(1) 可以直接產生有意義分存圖像，且不需任何額外的隱藏處理過程。

(2) 獲取更好視覺效果的恢復圖像和分存圖像，且解決了像素對齊的問題。

(3) 黑色像素的重構是完美的，這意味著所有秘密黑色像素能夠被精準恢復。

(4) 大量的形式化證明驗證了本文分存方案的正確性。

1 相關工作

VC是秘密分存概念在數字圖像上的應用。VC將秘密圖像以一種無需任何密碼學知識的安全方式進行編碼。在傳統的視覺方案中，解密的基本操作是“或”操作。使用“或”操作進行解密雖然簡單、快捷，但經常遇到視覺質量差、像素對齊、需要碼本以及像素膨脹等問題。為了解決上述問題，另一種基于異或的圖像分存方案產生了，它同樣將秘密圖像以一種安全方式進行編碼。與VC方案不同的是，異或圖像分存方案將使用“異或”操作來代替“疊加”操作對秘密圖像進行解密。

定義1. 平均透光率：對于大小為H×W的二進制圖像I中的一個像素p，p為白色的概率表示為Prob(p=1)，p的透光率記為T(p)。當p為白色像素時，p的透光率為T(p)=1；反之，當p為黑色像素時，p的透光率為T(p)=0。那么，圖像I的平均透光率可以定義為：

定義2. 區域表達：令A(1)(或A(0))表示圖像A中的所有白色(黑色)區域，其中 A=A( 1) ∪A(0)且A( 1) ∩ A(0)=?。B[A(1)](或B[A(0)])表示A中所有白色(黑色)像素在圖像B中的相應區域。

定義3. 恢復圖像對比度：為了評估由R{⊕,1,··,n}= R1⊕···⊕ Rn所得恢復圖像的視覺質量，相較于初始秘密圖像S，恢復圖像對比度定義為：

其中，R1,… ,Rn表示分存圖，⊕表示異或運算。

定義4. (分存圖像對比度)相對于初始載體圖像C，分存圖像R的對比度可定義為：

2 異或圖像分存方案

本小節首先利用翻轉操作構造一個有意義的(2, 2)異或圖像分存方案；隨后，將(2, 2)方案通過擴展得到一個有意義的(2, n)異或圖像分存方案。同時，還可提供形式化證明來驗證異或圖像分存方案的有效性。

2.1 有意義的(2, 2)異或圖像分存方案

算法1給出了基于翻轉操作的(2, 2)異或圖像分存方案的構造過程。

算法 1. 無意義的(2, 2)異或圖像分存方案的構造。

輸入：二進制圖像S和載體圖像C，S和C的大小均為H×W。

輸出：兩個大小為H×W的分存圖像R1和R2。

步驟1. 對分存圖像R1和R2進行初始化，得到：

以下將根據秘密圖像S的像素值，對這兩幅初始化后的分存圖像中的像素值執行翻轉操作，具體描述如下。

步驟2. 對秘密圖像上的每一位置(i, j)，根據 S( i, j)值的不同，將對初始像素 R1( i, j)和 R2( i, j)采取不同的翻轉策略。

步驟3. 當 S( i, j)= 0時，以 1/2的概率對 R1( i, j)和R2( i, j)同時進行翻轉。

步驟4. 當 S( i, j)= 1時，以相等的1/2概率從 R1( i, j)和R2( i, j)中隨機選擇一個，并進行翻轉，而未選中的那個則保持不變。

步驟 5. 重復步驟 2~4直到所有秘密像素均被處理完畢，即可輸出分存圖像R1和R2。

注意：算法 1在無需碼本和像素膨脹的情況下，通過翻轉操作來實現異或圖像分存方案。但是，由算法 1所生成的分存圖像是一個隨機的、無意義的圖像。為了生成有意義的分存圖像，可在算法1的基礎上引入一個概率參數β，以此來構造一個有意義的(2, 2)異或圖像分存方案，具體描述見算法2。

算法 2. 有意義的(2, 2)異或圖像分存方案的構造。

輸入：大小為H×W的秘密圖像S，大小為H×W的載體圖像C，和概率參數β(0 ＜ β＜1)。

輸出：兩個大小為H×W的有意義分存圖像R1和R2。

步驟1. 對于秘密圖像S上的每一位置(i, j)，將按照以下步驟來生成分存像素值 R1( i, j)和 R2( i, j)。

步驟2. 隨機生成一個比特d，它為1的概率是β，為0的概率是1 - β。

步驟3. 當 d=1時，利用算法1生成兩個分存像素值，即：

步驟4. 當 d= 0時，用 C( i, j)直接賦值給兩個分存像素值，即：

步驟 5. 重復步驟 1~4直到所有秘密像素均被處理完畢，即可輸出有意義的分存圖像R1和R2。

定理1. 設R1和R2為帶參數β的算法2所生成的分存圖像。算法2是一個有意義(2, 2)異或圖像分存方案的有效構造方法，其應滿足如下條件：

·安全性：每個分存圖像都不能給出秘密圖像的任何信息： T( Rk[ S (0)]) =T( Rk[ S (1)])，其中，k=1,2。

·有意義：每個分存圖像都是一幅類似載體圖像的有意義圖像：T( Rk( C (1))) ＞T( Rk( C(0)))，其中，k=1,2。

·對比度：兩個分存圖像的異或結果R{⊕,1,2}= R1⊕ R2能恢復出秘密信息：

且異或結果不會得到載體圖像的任何信息：

證明. 算法2中，針對每一秘密像素S(i, j)，以β的概率執行步驟3，以1–β的概率執行步驟4。執行步驟3時，無論秘密像素為1或0，分存像素R1( i, j)和 R2( i, j)均以1/2的概率進行翻轉，因此，Pro b( Rk( i, j) =1|S( i, j) =0)= Pro b( Rk( i, j) =1|S( i, j)=1) (k = 1,2)。執行步驟 4時，分存像素 R1( i, j)和R2( i, j)的值與秘密像素的值無關。所以，可以得到 ：Pr ob( Rk( i, j) = 1|S( i, j) =0) = Pr ob( Rk( i, j )= 1|S( i, j)= 1)(k = 1,2)。由定義 1、2可知，T( Rk[ S (0)]) =T( Rk[ S(1)])(k = 1,2)。綜上可得，任一分存圖像均不會給出秘密圖像的任何信息。

當載體圖像像素 C( i, j)= 0(或 C( i, j) = 1)時，相應的分存像素 R1( i, j)和 R2( i, j)的平均透光率為由0 ＜ β＜1可知，因此，T( Rk(i, j)[C( i, j) =1]) ＞ T( Rk(i, j)[C( i, j ) =0]) (k = 1,2)， 又 由 定 義 1、2 得 出 ，T( Rk[ C (1)]) ＞T( Rk[ C(0)])。綜上可得，每個分存圖像都是類似于載體圖像的有意義的圖像。

以概率β執行步驟3時，若 S( i, j)= 1，則由兩個分存像素所得的異或結果的平均透光率為1，反之，若S(i,j)=0，則相應的平均透光率為0。因此：

以概率1- β執行步驟 4時，由兩個分存像素所得的異或結果的平均透光率為T ((R1(i, j) ⊕R2(i, j ))[S ( i, j) =1]) = T ((R1(i, j )⊕R2( i, j) )[S( i, j) = 0])，這是因為兩個分存像素是相同的，且獨立于秘密像素。基于上述分析，進行加權計算即可得到： T ((R1( i, j) ⊕R2( i, j) )[S( i, j) =1])＞T ((R1( i, j) ⊕ R2( i, j )) [S( i, j)= 0])。由定義1、2可知， T((R1⊕ R2)[S (1)]) ＞T((R1⊕ R2)[S(0)])。因此，兩個分存圖像的異或結果可以恢復出秘密圖像信息。

由算法2的描述可知，針對每個秘密像素S(i,j)，每幅載體圖像的像素C(i,j)均以β/2的概率進行翻轉。所以得到：

定理2. 設R1和R2為帶概率參數β的算法2所生成的分存圖像，則兩個分存圖像異或結果的對比度為：xorα β= 。

證明. 當兩個分存像素由算法2的步驟3生成，若秘密像素為1，則相應異或結果的透光率為1，反之，若秘密像素為0，則相應透光率也為0。由定理 1的證明可得，如果兩個分存像素是由算法2的步驟4所生成，則無論秘密像素為1還是0，其異或結果的透光率恒為0。又因為執行步驟3的概率為 β，執行步驟 4的概率為 1–β，可得如下兩點：

(1) 異或結果相對應于秘密圖像白色區域的平均透光率為：

(2) 異或結果相對應于秘密圖像黑色區域的平均透光率為：

由定義3，兩個分存像素異或結果的對比度計算如下：

定理3. Rk(k=1,2)是由帶概率參數β的算法2所生成的分存圖像，其對比度為：

證明. 如果分存像素由算法2的步驟3所生成，當相應的載體圖像像素為1(或0)時，其平均透光率為1/2(或1/2)。如果分存像素由算法2的步驟 4所生成，當相應載體圖像像素為 1(或 0)時，其平均透光率為 1(或 0)。因為執行步驟 3的概率為β，執行步驟4的概率為1–β，可得如下兩點：

(1) 分存圖像相對應載體圖像白色區域的平均透光率為：

(2) 分存圖像相對應載體圖像黑色區域的平均透光率為：

由定義4可得，分存像素Rk的對比度計算公式為：

2.2 有意義的(2, n)異或圖像分存方案

若將(2，2)方案擴展得到(2, n)異或圖像分存方案。值得注意的是，擴展所得的(2, n)異或圖像分存方案的解碼過程與傳統的(2, n)方案有些不同。在傳統的(2, n)方案中，當分存圖像數量 2k＞ 時，k個分存都將用于解碼秘密圖像。而在擴展所得的(2, n)方案中，只需要其中的任意兩個分存圖像來解碼。

算法 3. 有意義的(2, n)異或圖像分存方案的構造。

輸入：大小均為H×W的秘密圖像S和載體圖像C，參數β(0 1)β≤ ≤ 。

輸出：n個大小為H×W的有意義分存圖像R1,…,Rn。

步驟1. 對于秘密圖像S上的每一像素S(i,j)，將按照以下步驟生成相應的分存像素值。

步驟2. 生成一個比特d，它為1的概率是β，為0的概率是1–β。

步驟3. 當 1d=時，首先將n個分存像素初始化為載體圖像像素C(i,j)，即：

隨后，對這n個像素進行翻轉操作。當S(i,j)=0時，以1/n的等概率對n個分存像素同時進行翻轉；當S(i,j)=1時，將以1/n的等概率隨機選擇其中一個分存像素進行翻轉，而其余n-1個分存像素保持不變。

步驟4. 當 0d= 時，直接令n個分存像素值等于C(i,j):

步驟 5. 重復步驟 1~4直到所有秘密像素全部處理完畢時，便可得到n個有意義的分存圖像R1,…,Rn。

為了得到一個有意義的(2, n)異或圖像分存方案，參數n和β應滿足如下條件：

同樣地，用類似證明算法 2的分析方法，可以證明算法3的正確性。并且可以得到算法3所產生的分存圖像的對比度為：同時，可以得到任意兩個分存圖像異或結果的對比度為：

3 實驗結果及討論

3.1 可行性

本小節通過以下實驗來驗證異或分存方案的可行性。第一個實驗是由算法2生成的(2，2)方案，其中參數β=0.5，圖像大小為512×512，實驗的結果見圖1。由圖觀察可得，每一幅有意義的分存圖像均不能給出秘密圖像的任意信息。但是，兩幅分存圖像的異或結果可以恢復秘密圖像信息。

圖1 算法2在(2, 2)方案的實驗結果(β=0.5,圖像大小512×512)

另一個實驗是由算法3所生成的(2，3)異或圖像分存方案，其中參數 n = 3,β = 0.75，見圖2。同樣的，生成的分存圖像無法得到秘密圖像的任意信息。但是，任意兩幅分存圖像的異或結果可以恢復出秘密圖像的信息。

圖2 算法3在(2, 3)方案下的實驗結果(參數n = 3，β = 0.75時，圖像大小為512×512)

3.2 理論結果的正確性

在上節中，可以得到有意義的(2, n)異或圖像分存方案的理論對比度計算如下：

為檢驗以上對比度的正確性，需計算實驗 2中(2，3)方案的實驗對比度，見表 1。觀察表 1，針對每幅分存圖像 Ri，可以得到T( Ri[ S (1)]) ≈ T( Ri[ S(0)])且 T( Ri[ C (1)])＞ T( Ri[ C (0)])。這表明，分存圖像是類似載體圖像 C的有意義圖像，但其不會得到秘密圖像 S的任何信息，滿足了安全性和有意義的兩個條件。用 Rx⊕ Ry來表示任意兩幅分存圖像 Rx和 Ry的異或結果，可以得到：

T((Rx⊕Ry)[C (1)]) ≈ T((Rx⊕ Ry)[C(0)])。這說明了任意兩個分存圖像的異或結果可以恢復出秘密圖像卻不會攜帶任何載體圖像的信息，滿足了對比度的條件。此外，不難發現 T((Rx⊕ Ry)[S(0)])恒等于0，這說明了黑色像素的重構是完美的。同時，根據等式(1)和(2)，可以計算在(2, 3)實驗中恢復圖像和分存圖像的理論對比度分別為0.5和0.4。表1表明理論對比度和實驗對比度的結果幾乎是完全一致的。

3.3 方案比較

將本文的異或圖像分存方案與相關分存方案進行比較，見表2。本文中異或圖像分存方案的主要優點，總結如下：

表1 (2,3)實驗中恢復圖像和分存圖像的實驗對比度

表2 本文方案與其他相關分存方案的特征比較

(1) 能夠生成有意義的分存圖像，且無需額外的隱藏處理過程。

(2) 秘密黑色像素的重構是完美的，有利于肉眼識別秘密圖像。

(3) 與疊加的VC方案相比，可獲得更好視覺效果的恢復圖像和分存圖像。

(4) 無需碼本和無像素膨脹。

4 總 結

本文利用翻轉操作構造(2, 2)和(2, n)異或圖像分存方案。本文方案具有無需碼本和無像素膨脹的優點，并能夠在無需額外隱藏處理的情況下直接生成有意義的分存圖像，以減少方案的計算時間。在解密過程中，只需要任意兩個分存圖像進行異或操作，其異或結果對秘密黑像素的重構是精準的。由于不同的參數可以得到不同視覺效果的分存圖像和恢復圖像，所以本文方案在應用上具有一定靈活性。理論分析和實驗結果驗證了本文方案的正確性和有效性。

[1]Blakley G R. Safeguarding cryptographic keys [C]//in Proc. AFIPS 1979, National Computer Conference, 1979: 313-317.

[2]Shamir A. How to share a secret [J]. Communications of the ACM, 1979, 22(11): 612-613.

[3]Naor M, Shamir A. Visual cryptography [C]//Advances in Cryptology EUROCRYPT'94. Springer Berlin Heidelberg, 1995: 1-12.

[4]歐鍛灝, 孫 偉, 林 博. 一種新的基于可逆矩陣的具有完整性檢驗能力的圖像加密方案[J]. 圖學學報, 2012, 33(2): 89-92.

[5]易開祥, 孫 鑫. 一種基于混沌序列的圖像加密算法[J].計算機輔助設計與圖形學學報, 2000, 12(9): 672-676.

[6]Liu Feng, Wu Chuangkun. Embedded extended visual cryptography schemes [J]. IEEE Transactions on Information Forensics and Security, 2011, 6(2): 307-322.

[7]Shyu S J. Image encryption by multiple random grids [J]. Pattern Recognition, 2009, 42(7): 1582-1596.

[8]Chen T, Tsao K. Threshold visual secret sharing by random grids [J]. Journal of Systems and Software, 2011, 84(7): 1197-1208.

[9]Tuyls P, Hollmann H D, Van Lint J H, et al. Xor-based visual cryptography schemes [J]. Designs, Codes and Cryptography, 2005, 37(1): 169-186.

[10]Liu Feng, Wu Chuankun. Optimal xor based (2, n)-visual cryptography schemes [R]. IACR Cryptology ePrint Archive, 2010-10-25.

[11]歐鍛灝, 吳小天, 孫 偉, 等. 基于恢復函數和誤差擴散的灰度圖像分存方案[J]. 計算機科學, 2013, 40(2): 112-116.

[12]吳小天, 孫 偉. 基于誤差擴散的圖像分存方案[J]. 計算機應用, 2011, 31(1): 74-77.

[13]Chen Shangkuan, Lin S J. Optimal (2, n) and (2, infinity) visual secret sharing by generalized random grids [J]. Journal of Visual Communication and Image Representation, 2012, 23(4): 677-684.

A (2, n) XOR-Based Secret Image Sharing Scheme Based on Flipping Operations

Ou Duanhao1, Wu Xiaotian1, Cheng Binyi2, Sun Wei2,3
(1. School of Information Science and Technology, Sun Yat-sen University, Guangzhou Guangdong 510006, China; 2. School of Software, Sun Yat-sen University, Guangzhou Guangdong 510006, China; 3. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China)

A new method for constructing XOR-based secret image sharing scheme by flipping operations. The proposed scheme encodes a secret image in a perfect secure way without any knowledge of cryptography. The meaningful shares can be directly generated by the proposed scheme without any extra data hiding process. Meanwhile, neither pixel expansion nor extra codebook is needed in the proposed scheme. Further, the reconstruction of black pixels is perfect, which means all the revealed pixels associated to secret black pixels are always black. First, a meaningful (2, 2) XOR-based image sharing scheme is constructed by flipping operations. Subsequently, a meaningful (2, n) scheme is extended as well. Theoretical analysis and experimental results demonstrate the correctness and feasibility of the proposed scheme.

secret image sharing; flipping operation; meaningful shares; perfect black; XOR operation

TP 309.7

A

2095-302X(2015)01-0056-06

2014-08-11；定稿日期：2014-08-20

國家“973”計劃資助項目(2011CB302400)；廣東省自然科學基金資助項目(S2013010013728)

歐鍛灝(1986–)，男，廣東陸豐人，博士研究生。主要研究方向為多媒體信息安全、圖像分存。E-mail：ouduanhao@163.com

孫 偉(1972–)，男，江蘇連云港人，教授，博士。主要研究方向為信息安全、數字媒體。E-mail：sunwei@mail.sysu.edu.cn