無損分享視覺密碼研究

郁濱，付正欣

(信息工程大學 電子技術學院，河南 鄭州 450004)

1 引言

視覺密碼[1](visual cryptography)是一種新的圖像分存技術，它將秘密共享和數字圖像相結合，經過 10多年的不斷豐富和發展，已經成為密碼學的一個新的研究方向，并從最初的(2, 2)方案發展成為一個相對完善的理論體系。

視覺密碼通過秘密分享算法將秘密圖像編碼成為若干個共享份，并分發給每個參與者。當參與者集合滿足約定的恢復條件時，只需將參與者的共享份直接疊加即可恢復出秘密圖像。由于視覺密碼的秘密恢復過程簡單，因此視覺密碼的研究重點主要集中于秘密分享算法。

以基矩陣為核心的秘密分享算法由 Naor和Shamir最先提出，由于其能夠保證視覺密碼方案的安全性和對比性條件，因而基矩陣的設計是視覺密碼方案的關鍵。Naor和Shamir[1]證明了(n, n)方案的最小像素擴展度為 2n-1，并給出了基矩陣的構造方法，即B0（分享白像素的基矩陣）由所有漢明重量為偶數的列向量組成，B1（分享黑像素的基矩陣）由所有漢明重量為奇數的列向量組成。Bludno等[2]證明了(2, n)門限方案的最小像素擴展度為滿足的最小 m值，在基矩陣設計時，B0由n個相同的漢明重量為 ■ m 2■的行向量組成，而 B1由 n個不同的漢明重量為 ■ m 2■的行向量組成。Droste[3]提出了ADD算子，用以在(n, n)方案基礎上動態增加列向量，可以有效地減小(k, n)門限方案的像素擴展度，同時還提出利用線性規劃的方法設計基矩陣，但由于規劃模型的解不是整數，因此并不具有實際的意義。Ateniese等[4]通過定義授權集合QualΓ和禁止集合ForbΓ，將視覺密碼由門限結構擴展到通用存取結構，并提出了2種經典的基矩陣構造方法，即基于累積矩陣方法和小方案擴展方法，廣泛地應用于通用存取結構的方案。Hajiabolhassan[5]研究了幾種特殊的通用存取結構，討論了其像素擴展度的界限，并提出了相應的基矩陣設計方法。研究表明，基矩陣的列數代表圖像面積上擴大的倍數，而以基矩陣為核心的視覺密碼方案無法達到像素擴展度的理想值“1”。

為了使像素擴展度達到理想值，部分學者提出了與基矩陣不同的秘密分享算法。Yang[6]以整幅圖像的安全性代替每個像素點的安全性，在分享像素點時隨機從基矩陣中選取一列，實現了像素的不擴展。白璟霖[7]利用隨機亂數率表示圖像的對比度，提出了一種基于隨機數的秘密分享算法，實現了像素的不擴展。Hou等[8]利用人類視覺系統的空間均衡及局部統計等特性，提出了一種多點加密法，該方法可以一次分享m個像素，使像素擴展度達到了理想值。Hsu等[9]從概率的角度研究視覺密碼方案，認為原圖像的識別可以通過黑白區域的不同灰度來實現，設計了以加密規則矩陣和概率矩陣為核心的秘密分享算法，得到了像素擴展度為1的視覺密碼方案。上述方案達到了像素擴展度的理想值，但均以原圖像的信息損失為代價，即恢復圖像不再包含原圖像的所有信息。目前尚無像素擴展度與信息損失之間關系的研究。

針對像素擴展與信息損失的問題，本文給出了無損分享的定義，指出無損分享視覺密碼的最優像素擴展度是區分無損分享與有損分享的關鍵，并設計了矩陣轉化算法和整數規劃模型，實現了一種像素優化算法，可以在保持恢復計算復雜度的條件下實現完全恢復。

2 無損分享

設 P = { 1,… ,n }表示 n個參與者的集合，2p表示P的所有子集組成的集合。記ΓQual為授權集合，ΓForb為禁止集合，其中， ΓQual?2p， ΓForb?2p，且 ΓQual∩ ΓForb＝ ? ，則(ΓQual,ΓForb)表示一個視覺密碼方案的通用存取結構。下面是以基矩陣為核心的視覺密碼方案定義。

定義1[4]( Γ ,Γ)為參與者集合P = { 1,…,n}

QualForb

的通用存取結構，稱 ( ΓQual, ΓForb,m)-VCS表示一個視覺密碼方案，其基矩陣為n×m的布爾矩陣B0和B1。當分享白(黑)像素時，選擇 B0(B1)進行隨機的列排序，以確定n個共享份中m個子像素的顏色。B0和B1滿足以下2個條件。

1) 對比性條件：對于授權子集 X ={i1, i2, … ,ip}∈ ΓQual，B0的 i1, i2, … ,ip行“或”運算得到的向量V滿足 H ( V)≤ tX-αm；B1的i1, i2, …, ip行“或”運算得到的向量 V滿足 H ( V)≥ tX，其中，H( V)表示V的漢明重量。

2) 安全性條件：對于禁止子集 X ={i1, i2, … ,if}∈ ΓForb，設 D0(D1)為 B0(B1)的 i1, i2,… ,if行構成的子矩陣，則D0=D1。

定義 2 設一個視覺密碼方案的原圖像為 S，經過秘密分享算法后得到共享份集合T，直接疊加授權子集的共享份，得到恢復圖像 S '。若存在一個函數R，滿足 S = R ( S')，則稱該視覺密碼方案是無損分享的。

定理1 滿足定義1的視覺密碼方案是無損分享的。

證明 通過計算恢復圖像 S '中 m個子像素的漢明重量并分類，可以實現原圖像S的完全恢復。設原圖像S的大小為a×b，S( i, j)對應恢復圖像中S'( m i-m + 1 ,j )到S'( mi, j)的 m 個像素，設表示 S '中 m個像素的漢明重量表示像素塊的平均漢明重量， W0表示原白像素對應像素塊的漢明重量，W1表示原黑像素對應像素塊的漢明重量，由定義1可知因此S( x, y)=即存在函數R滿足 S = R ( S')，定理1證畢。

實際上對于一個已知基矩陣的方案而言，函數R更容易設計。例如對(2, 2)方案而言，其基矩陣為疊加 2個共享份 T和

1T2得到 S '。S '中的'01'漢明重量為1，對應S的'0'；S'中的'11'漢明重量為 2，對應 S的'1'。令（i和 j表示 S的像素坐標），即可完全恢復出原圖像。

由定理1的證明和(2, 2)方案的示例可知，無損分享的視覺密碼方案在完全恢復原圖像時，需要進行abm次加法和ab次取整，其計算復雜度與傳統的直接疊加相同，均為 O (1 )。因此無損分享視覺密碼既繼承了恢復簡單的特點，又可以實現完全恢復，待解決的問題是如何減小像素擴展度。

定理2（判別定理） 設 ( ΓQual, ΓForb)為通用存取結構，若m

證明 若以 m為像素擴展度的方案是無損分享的，則m0不是無損分享方案的最小像素擴展度，與已知條件矛盾，定理2證畢。

推論1 對于像素擴展度為1的視覺密碼方案而言，若恢復操作為或運算，則該方案是有損分享的。

證明 對于恢復操作為或運算的視覺密碼而言，(2, 2)方案的m0最小，且m0=2。因此對所有視覺密碼方案均有 m0>1。根據定理 2，若 m=1，則m

由此可見，無損分享視覺密碼是一類重要的方案，而且m0是衡量秘密信息能否完全恢復的關鍵。

3 像素擴展度的優化算法

一般而言，直接計算m0難度較大，而m0表示的是基矩陣的列數，所以可以將復雜的基矩陣設計問題簡化為概率矩陣的最大公約數問題。根據像素擴展度m與最大公約數d的數學關系，建立以d最大化為目標、安全性和對比性為約束條件的整數規劃模型，然后利用基矩陣與概率矩陣之間的轉化算法，得到最優的像素擴展度及相應的基矩陣。本文設計的優化算法流程如圖1所示。

3.1 加密規則矩陣和概率矩陣

加密規則矩陣和概率矩陣是Hsu等[9]為了避開基矩陣而提出的概念。

定義 3 記 E = [eij]為加密規則矩陣， i ∈{1,2,…,2n},j∈ {1,2,…,n},eij∈ { 0,1}。E中各行向量均不相同，行向量 ei= ( ei1, ei2,… ,ein)表示第i種加密規則，即原圖像的1個像素按照 ei加密，生成第j共享份中對應的像素為eij。

定義4 記 C = [cij]為概率矩陣，i ∈ { 0,1}, j ∈{1,2,… ,2n},c ∈ [ 0,1]。其中， c 表示白像素選擇第j

ij0j條加密規則的概率，c1j表示黑像素選擇第j條加密規則的概率，且

生成共享份時，根據概率矩陣選擇加密規則。根據表1可知，當原像素為0（白像素）時，以c01=0.5的概率選擇e1＝(e11, e12)，以c04=0.5的概率選擇e4＝(e41, e42)，而e2和e3則不選擇；當原像素為1（黑像素）時，以c02=0.5的概率選擇e2＝(e21, e22)，以c03=0.5的概率選擇e3＝(e31, e32)，而e1和e4則不在選擇之列。通過上述步驟生成的共享份，其大小與原秘密圖像相等，故像素擴展度為1。在衡量方案安全性和對比性時，則根據一個像素為黑色的概率來判斷。

在安全性方面，禁止子集{1}和{2}無法得到原圖像的信息。T1中原白像素的加密效果為 F C01=，原黑像素的加密效果為 F C =11由于 F C = F C，因此從 T中無

圖1 優化算法流程

表1 基于加密規則矩陣和概率矩陣的(2, 2)門限視覺密碼

01111法分辨出原圖像的像素顏色。對T2的分析同理。

在對比性方面，需要確定授權子集{1,2}能夠恢復出原圖像。對T1+T2而言，原白像素對應的恢復效果為，原黑像素對應的恢復效果為，由于QC11＞QC01，因此從T1+T2中可以分辨出原圖像的像素顏色。

3.2 矩陣轉化算法

為了便于描述m與d之間的數學關系，本節首先介紹矩陣轉化算法。

定義5 記能被概率矩陣C中所有元素整除的有理數組成集合D，若d是D中的最大值，則稱d為C的最大公約數。

注：由于概率矩陣 C中的元素為[0, 1]的有理數，因此本文是在有理數范圍內討論最大公約數，與通常的自然數范圍不同。

矩陣轉化算法以加密規則矩陣E和概率矩陣C為算法輸入，以基矩陣B0和B1為算法輸出，具體步驟如下。

step1 找到C的最大公約數d。

step2 計算修正后的概率矩陣 ' d=C C 。

step3 將加密規則 ei(1 ≤ i ≤ 2n)的轉置重復次，并依次連接組成新的矩陣B0。

step4 將加密規則ei(1 ≤ i≤ 2n)的轉置重復次，并依次連接組成新的矩陣B1。

由矩陣轉化算法可知，若 ( E1, C1) ≠ (E2, C2)，則得到的基矩陣是不同的。由于根據基矩陣 B0和B1也可以計算出相應的E和C，因此可以設計以基矩陣為算法輸出，以E和C為算法輸出的逆算法，具體步驟如下。

step1 根據參與者人數n確定加密規則矩陣E。

step2 統計 B0中加密規則 ei(1 ≤ i ≤ 2n)出現的次數 c0'i。

step3 統計 B1中加密規則 ei(1 ≤ i ≤ 2n)出現的次數 c1'i。

step4 計算概率矩陣 C = C ' m。

定理 3 對一個視覺密碼方案而言，其基矩陣的像素擴展度 m與概率矩陣的最大公約數 d滿足m = 1 d。

證明 從矩陣轉換算法及其逆算法可知，C ' = C d且 C = C ' m，故定理3得證。

下面以(3, 3)門限方案為例，對矩陣轉化算法進行說明。加密規則矩陣，概率矩陣則C的最大公約數 d = 1 4，修正后的概率矩陣 C '=。將e的轉置重復次，i并依次連接組成新的矩陣將ei的轉置重復 c1'i次，并依次連接組成新的矩陣，基矩陣的像素擴展度 m = 4 。

3.3 整數規劃模型

設 Γ=(ΓQual, ΓForb)，且對于以Γ為存取結構的視覺密碼方案，其最優像素擴展度是以下整數規劃模型的解。

1) 規劃目標

由于像素擴展度 m = 1 d，因此求m的最小值等價于d的最大值。在視覺密碼方案設計過程中，d只隨概率矩陣C的變化而取不同的值，因此本模型的規劃目標是尋找到一個d最大的概率矩陣C。

2) 對比性約束條件

設 Q C0h( Q C1h)表示授權子集 Qh∈ΓQual(h∈{1,2,…,q})的所有共享份疊加后，原白（黑）像素呈現黑像素的概率。定義 O R ( E , X)(X = { x1, x2,… ,x } ∈ 2p)表示加密規則矩陣E中第 x, x ,… ,x列在

t12t或運算后得到的列向量，則 ( Q C0h, Q C1h)T=C×OR ( E , Qh)。對比性約束條件指授權子集能夠恢復秘密圖像，故 Q C1h- Q C0h＞0。

3) 安全性約束條件

設 F C0k(F C1k)表示禁止子集 Fk∈ΓForb(k∈{1,2,…,f})的所有共享份疊加后，原白（黑）像素呈現黑像素的概率，則 ( F C0k, F C1k)T=C×OR ( E,Fk)。安全性條件表示禁止子集無法獲取秘密圖像的任何信息，故 F C1k- F C0k= 0 。

4) 其他約束條件

由于d是概率矩陣C的最大公約數，因此 cij=nijd且n∈N(i∈ { 0,1},j∈ { 1,2,… ,2n})。另外由根據概率

ij矩陣的定義，可知和 cij∈ [ 0,1]。

4 實驗結果與分析

本文設計的像素擴展度優化算法適用于通用存取結構，下面從門限結構和通用存取結構2個方面進行實驗與分析，以說明本文算法的有效性。

1) 門限結構

按照像素擴展度的優化算法，計算(k,n)(2 ≤ k ≤ n ≤ 1 0)門限結構視覺密碼方案的最優像素擴展度，如表2所示。從計算結果可以看出：對于(n, n)門限結構，表2的結果與文獻[1]相同；對于(2, n)門限結構，表2的結果與文獻[2]相同；對于(k, n)(2 ＜ k ＜ n ≤ 1 0)門限結構，表2的結果與文獻[3]相同。因此本文提出的優化算法對于(k, n)門限結構是有效的。

表2 (k, n)門限結構方案的像素擴展度

2) 通用存取結構

設 P = { 1,2,3,4}， ΓQual= { {1,2},{2,3}, {1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}}， ΓForb={{1,3},{1,4},{2,4},{3,4},{1},{2},{3},{4}}，則 ( ΓQual, ΓForb)是通用存取結構。根據文獻[4]的累積矩陣方法，計算得到的基矩陣為根據本文方法，計算的基矩陣為m=4，比文獻[4]的方法更優，因此本文方法對于通用存取結構是有效的。本方案對應的原圖像、共享份和恢復圖像如圖2所示。

圖2 本文方案的實驗效果

從圖2分析可知，直接疊加共享份得到的 S '能夠完全恢復出原圖像 S。需要說明的是，對于不同的授權子集，函數R是不同的。比如對于{1, 2}，，則

最后從通用存取結構、像素擴展度、相對差、信息損失和恢復計算復雜度等5個方面將本文方案與前人方案進行對比，具體結果如表3所示。其中，m0≤m1, m2，0＜ Q C1h- Q C0h＜ 1 。分析表3可知：本文方案在保證原圖像完全恢復的情況下，能夠有效減小像素擴展度，且不增加恢復過程的計算復雜度。

表3 方案綜合比較

5 結束語

在研究秘密圖像恢復質量的基礎上，本文給出了無損分享視覺密碼的定義，保持了恢復簡單優點，同時實現了原圖像的完全恢復。針對無損分享方案中的像素擴展問題，將像素擴展度 m0的求解問題轉化為計算概率矩陣的最大公約數 d，進而設計了像素擴展度的優化算法，包括整數規劃模型和矩陣轉化算法2部分。本文取得的計算結果只考慮了或運算的情況，對于其他的算子如 XOR等，尚有待進一步的研究。

[1] NAOR M, SHAMIR A. Visual cryptography[A]. Cryptology-Eurocrypt’94[C]. 1994. 1-12.

[2] BLUDNO C, SANTIS A D, STINSON D R, et al. Graph decomposition and secret sharing schemes[J]. Journal of Cryptology, 1995, (8):39-64.

[3] DROSTE S. New results on visual cryptography[A]. Cryptography-CRYPTO’ 96[C]. 1996. 401-415.

[4] ATENIESE G, CARLO B, SANTIS A D, et al. Visual cryptography for general access structures[J]. Information and Computation, 1996, (12):86-106.

[5] HAJIABOLHASSAN H, CHERAGHI A. Bounds for visual cryptography schemes[J]. Discrete Applied Mathematics, 2010, (158): 659-665.

[6] YANG C. New visual secret sharing schemes using probabilistic method[J]. Pattern Recognition Letters, 2004, (25):481-494.

[7] 白璟霖. 以隨機亂數為基礎的影像機密分享[D]. 銘傳大學, 2005.BAI J L. Image Secret Sharing based Upon Random Numbers[D].Ming Chuan University, 2005.

[8] HOU Y C, TU S F. A visual cryptographic technique for chromatic images using multi-pixel encoding method[J]．Journal of Research and Practice in Information Technology, 2005, 37(2):179-191.

[9] HSU C S, TU S F, HOU Y C. An optimization model for visual cryptography schemes with unexpanded shares[A]. ISMIS[C]. Springer-Verlag Berlin Heidelberg, 2006. 58-67.