無損分享視覺密碼研究

郁濱，付正欣

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

1 引言

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

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

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

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

針對像素?cái)U(kuò)展與信息損失的問題，本文給出了無損分享的定義，指出無損分享視覺密碼的最優(yōu)像素?cái)U(kuò)展度是區(qū)分無損分享與有損分享的關(guān)鍵，并設(shè)計(jì)了矩陣轉(zhuǎn)化算法和整數(shù)規(guī)劃模型，實(shí)現(xiàn)了一種像素優(yōu)化算法，可以在保持恢復(fù)計(jì)算復(fù)雜度的條件下實(shí)現(xiàn)完全恢復(fù)。

2 無損分享

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

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

QualForb

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

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

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

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

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

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

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

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

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

定理2（判別定理） 設(shè) ( ΓQual, ΓForb)為通用存取結(jié)構(gòu)，若m

證明 若以 m為像素?cái)U(kuò)展度的方案是無損分享的，則m0不是無損分享方案的最小像素?cái)U(kuò)展度，與已知條件矛盾，定理2證畢。

推論1 對于像素?cái)U(kuò)展度為1的視覺密碼方案而言，若恢復(fù)操作為或運(yùn)算，則該方案是有損分享的。

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

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

3 像素?cái)U(kuò)展度的優(yōu)化算法

一般而言，直接計(jì)算m0難度較大，而m0表示的是基矩陣的列數(shù)，所以可以將復(fù)雜的基矩陣設(shè)計(jì)問題簡化為概率矩陣的最大公約數(shù)問題。根據(jù)像素?cái)U(kuò)展度m與最大公約數(shù)d的數(shù)學(xué)關(guān)系，建立以d最大化為目標(biāo)、安全性和對比性為約束條件的整數(shù)規(guī)劃模型，然后利用基矩陣與概率矩陣之間的轉(zhuǎn)化算法，得到最優(yōu)的像素?cái)U(kuò)展度及相應(yīng)的基矩陣。本文設(shè)計(jì)的優(yōu)化算法流程如圖1所示。

3.1 加密規(guī)則矩陣和概率矩陣

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

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

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

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

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

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

圖1 優(yōu)化算法流程

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

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

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

3.2 矩陣轉(zhuǎn)化算法

為了便于描述m與d之間的數(shù)學(xué)關(guān)系，本節(jié)首先介紹矩陣轉(zhuǎn)化算法。

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

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

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

step1 找到C的最大公約數(shù)d。

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

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

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

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

step1 根據(jù)參與者人數(shù)n確定加密規(guī)則矩陣E。

step2 統(tǒng)計(jì) B0中加密規(guī)則 ei(1 ≤ i ≤ 2n)出現(xiàn)的次數(shù) c0'i。

step3 統(tǒng)計(jì) B1中加密規(guī)則 ei(1 ≤ i ≤ 2n)出現(xiàn)的次數(shù) c1'i。

step4 計(jì)算概率矩陣 C = C ' m。

定理 3 對一個(gè)視覺密碼方案而言，其基矩陣的像素?cái)U(kuò)展度 m與概率矩陣的最大公約數(shù) d滿足m = 1 d。

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

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

3.3 整數(shù)規(guī)劃模型

設(shè) Γ=(ΓQual, ΓForb)，且對于以Γ為存取結(jié)構(gòu)的視覺密碼方案，其最優(yōu)像素?cái)U(kuò)展度是以下整數(shù)規(guī)劃模型的解。

1) 規(guī)劃目標(biāo)

由于像素?cái)U(kuò)展度 m = 1 d，因此求m的最小值等價(jià)于d的最大值。在視覺密碼方案設(shè)計(jì)過程中，d只隨概率矩陣C的變化而取不同的值，因此本模型的規(guī)劃目標(biāo)是尋找到一個(gè)d最大的概率矩陣C。

2) 對比性約束條件

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

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

3) 安全性約束條件

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

4) 其他約束條件

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

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

4 實(shí)驗(yàn)結(jié)果與分析

本文設(shè)計(jì)的像素?cái)U(kuò)展度優(yōu)化算法適用于通用存取結(jié)構(gòu)，下面從門限結(jié)構(gòu)和通用存取結(jié)構(gòu)2個(gè)方面進(jìn)行實(shí)驗(yàn)與分析，以說明本文算法的有效性。

1) 門限結(jié)構(gòu)

按照像素?cái)U(kuò)展度的優(yōu)化算法，計(jì)算(k,n)(2 ≤ k ≤ n ≤ 1 0)門限結(jié)構(gòu)視覺密碼方案的最優(yōu)像素?cái)U(kuò)展度，如表2所示。從計(jì)算結(jié)果可以看出：對于(n, n)門限結(jié)構(gòu)，表2的結(jié)果與文獻(xiàn)[1]相同；對于(2, n)門限結(jié)構(gòu)，表2的結(jié)果與文獻(xiàn)[2]相同；對于(k, n)(2 ＜ k ＜ n ≤ 1 0)門限結(jié)構(gòu)，表2的結(jié)果與文獻(xiàn)[3]相同。因此本文提出的優(yōu)化算法對于(k, n)門限結(jié)構(gòu)是有效的。

表2 (k, n)門限結(jié)構(gòu)方案的像素?cái)U(kuò)展度

2) 通用存取結(jié)構(gòu)

設(shè) 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)是通用存取結(jié)構(gòu)。根據(jù)文獻(xiàn)[4]的累積矩陣方法，計(jì)算得到的基矩陣為根據(jù)本文方法，計(jì)算的基矩陣為m=4，比文獻(xiàn)[4]的方法更優(yōu)，因此本文方法對于通用存取結(jié)構(gòu)是有效的。本方案對應(yīng)的原圖像、共享份和恢復(fù)圖像如圖2所示。

圖2 本文方案的實(shí)驗(yàn)效果

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

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

表3 方案綜合比較

5 結(jié)束語

在研究秘密圖像恢復(fù)質(zhì)量的基礎(chǔ)上，本文給出了無損分享視覺密碼的定義，保持了恢復(fù)簡單優(yōu)點(diǎn)，同時(shí)實(shí)現(xiàn)了原圖像的完全恢復(fù)。針對無損分享方案中的像素?cái)U(kuò)展問題，將像素?cái)U(kuò)展度 m0的求解問題轉(zhuǎn)化為計(jì)算概率矩陣的最大公約數(shù) d，進(jìn)而設(shè)計(jì)了像素?cái)U(kuò)展度的優(yōu)化算法，包括整數(shù)規(guī)劃模型和矩陣轉(zhuǎn)化算法2部分。本文取得的計(jì)算結(jié)果只考慮了或運(yùn)算的情況，對于其他的算子如 XOR等，尚有待進(jìn)一步的研究。

[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] 白璟霖. 以隨機(jī)亂數(shù)為基礎(chǔ)的影像機(jī)密分享[D]. 銘傳大學(xué), 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.