董 晨 張皓宇 季姝廷 李 磊

1(天津理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院天津市智能計(jì)算及軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室 天津 300384)2(天津市大數(shù)據(jù)管理中心 天津 300221)

0 引 言

作為一種秘密共享技術(shù)，視覺密碼[1](Visual Cryptography,VC)具有理論安全和恢復(fù)簡(jiǎn)單的特點(diǎn)。它將秘密分享為若干雜亂無章的共享份，恢復(fù)時(shí)將足夠數(shù)量的共享份疊加，自提出以來，便引起眾多學(xué)者的重視和研究興趣[2-4]。

在視覺密碼的早期研究中，方案主要采用透明膠片為介質(zhì)，因而其恢復(fù)操作只能是疊加，亦即布爾二元運(yùn)算中的“或”運(yùn)算。無論是Naor等[1]最早給出視覺密碼的(n,n)方案，還是Droste等[5]通過設(shè)計(jì)加密矩陣給出相對(duì)差為1/m(m為加密矩陣列數(shù))的(k,n)方案，都存在像素?cái)U(kuò)展度較大、外形比例失真和相對(duì)差較小的問題，需要進(jìn)一步對(duì)視覺密碼方案參數(shù)進(jìn)行優(yōu)化。為此，Hou等[6]提出了一種多點(diǎn)加密技術(shù)，對(duì)秘密圖像逐行進(jìn)行掃描，每分享m個(gè)黑(白)像素就使用了加密矩陣的所有列，實(shí)現(xiàn)了秘密圖像的不擴(kuò)展分享與恢復(fù)，雖然恢復(fù)圖像的外形比例不失真，但該方案的相對(duì)差沒有得到實(shí)質(zhì)性提高。

另一種實(shí)現(xiàn)像素不擴(kuò)展的方法是隨機(jī)柵格法，文獻(xiàn)[7]設(shè)計(jì)了基于隨機(jī)柵格(Random Grid,RG)的視覺密碼(RG-based VC,RGVC)，共享份是與原始圖像尺寸相同的光柵，通過將共享份進(jìn)行“或”疊加，通過黑白區(qū)域的光通量不同來顯現(xiàn)秘密信息。由于RGVC只借助隨機(jī)函數(shù)來實(shí)現(xiàn)秘密共享[8]，因此共享過程不依賴加密矩陣是RGVC的優(yōu)勢(shì)，可以有效減小加密矩陣的存儲(chǔ)開銷。依據(jù)該思路，Shyu[9]基于二元運(yùn)算的3種函數(shù)fequ、fran和fcom設(shè)計(jì)了一種(2,2)方案的秘密分享算法。此后，Chen等[10]、Guo等[11]和Hu等[12]相繼設(shè)計(jì)了存取結(jié)構(gòu)為(2,n)、(n,n)和(k,n)的RGVC改進(jìn)方案。Shen等[13]分析了RGVC方案到加密矩陣方案的變換，指出隨機(jī)柵格是加密矩陣的算法表示。事實(shí)上，RGVC方案是加密矩陣方案的一個(gè)特例，同樣存在恢復(fù)效果不佳的問題，因此設(shè)計(jì)更優(yōu)的加密矩陣方案成為當(dāng)前主流的研究思路。

綜上所述，盡管現(xiàn)有方案在像素?cái)U(kuò)展度方面得到了優(yōu)化，但始終存在恢復(fù)圖像相對(duì)差低的問題。本質(zhì)上，該類方案用“或”運(yùn)算執(zhí)行像素疊加，從代數(shù)結(jié)構(gòu)上講，其操作都屬于半群結(jié)構(gòu)，使得像素?zé)o法實(shí)現(xiàn)完全恢復(fù)，特別地，對(duì)于表示白像素的0而言，其代數(shù)結(jié)構(gòu)不存在逆元，是限制恢復(fù)效果進(jìn)一步改善的根本原因。為了突破基于透明膠片疊加的運(yùn)算介質(zhì)對(duì)方案的影響，Biham等[14]提出了基于偏振光的視覺密碼，恢復(fù)像素的顏色不再是共享份對(duì)應(yīng)像素“或”運(yùn)算的結(jié)果，而是由共享份偏振方向的平行“或”正交來決定，該操作可以表示為“異或”(XOR)運(yùn)算，具有像素?cái)U(kuò)展度小和相對(duì)差大的特點(diǎn)，但方案依賴特定的光學(xué)設(shè)備，恢復(fù)過程較為復(fù)雜。隨著現(xiàn)代科學(xué)技術(shù)的發(fā)展，具有計(jì)算能力的智能終端在現(xiàn)實(shí)應(yīng)用中日益普及，為實(shí)現(xiàn)“異或”操作提供了簡(jiǎn)便途徑，Tuyls等[15]首次給出基于XOR視覺密碼的定義，并實(shí)現(xiàn)了(n,n)方案的完全恢復(fù)，但該方案的分享算法不適用于一般的(k,n)存取結(jié)構(gòu)。郁濱等[16]結(jié)合(n,n)“異或”方案的加密矩陣，提出了共享份分塊構(gòu)造的設(shè)計(jì)思路，可以實(shí)現(xiàn)相對(duì)差的無失真恢復(fù)，但疊加圖像的外形比例存在失真。

針對(duì)以上問題，本文設(shè)計(jì)基于奇偶列的加密矩陣構(gòu)造方法，在圖像分享時(shí)，通過改進(jìn)多行掃描、多點(diǎn)加密技術(shù)，構(gòu)造出一種基于“異或”的(k,n)秘密分享算法，在實(shí)現(xiàn)恢復(fù)圖像外形比例不失真的前提下，提高了相對(duì)差，最后，通過理論和實(shí)驗(yàn)驗(yàn)證方案安全性和對(duì)比性。

1 基本概念

設(shè)共享集合為K={i1,i2,…,in}，定義授權(quán)集合為Q(Q?K且|Q|≥k)，禁止集合為P(P?K且|P|

定義1稱兩個(gè)n×m布爾矩陣為元素的集合C0和C1構(gòu)成一個(gè)(k,n)“異或”視覺密碼方案，其中C0表示分享白像素的映射空間，C1表示分享黑像素的映射空間，在分享白(黑)像素時(shí)從C0(C1)中隨機(jī)選取一個(gè)矩陣S0(S1)，對(duì)應(yīng)n個(gè)共享份各自的m個(gè)子像素，則矩陣S0、S1滿足下列兩個(gè)條件:

1) 安全性條件：當(dāng)X?P時(shí)，H(V(X,S0,⊕))=H(V(X,S1,⊕))。

2) 對(duì)比性條件：當(dāng)X?Q時(shí)，H(V(X,S1,⊕))-H(V(X,S0,⊕))>0。

安全性條件表明當(dāng)參與者人數(shù)小于k時(shí)，禁止集合P中的參與者無法獲得秘密圖像的任何信息。對(duì)比性條件表明當(dāng)參與者人數(shù)等于k時(shí)，授權(quán)集合Q中的參與者通過共享份“異或”運(yùn)算可以實(shí)現(xiàn)秘密恢復(fù)。評(píng)價(jià)視覺密碼方案有兩個(gè)重要參數(shù)：像素?cái)U(kuò)展度m和相對(duì)差α。

定義2設(shè)(k,n)-VCS加密矩陣為S0和S1，任取S0(或S1)中k行，當(dāng)S0中此k行的任意列向量l中含有奇數(shù)個(gè)“1”(或S1中k行的任意列向量l′中含有偶數(shù)個(gè)“1”)時(shí)，則稱向量l(l′)為矩陣S0(或S1)的多余列。將l(l′)的k行中所含有“1”的個(gè)數(shù)記為r。

關(guān)于上述定義的三點(diǎn)補(bǔ)充說明：

1)m表示原始圖像中的一個(gè)像素在分享圖像中擴(kuò)大的子像素的個(gè)數(shù)，也就是原始圖像經(jīng)過擴(kuò)展后在面積上失真的倍數(shù)。像素?cái)U(kuò)展度越大所需的存儲(chǔ)空間就越大，即代表其在面積上的失真也會(huì)越大。

2)α是恢復(fù)圖像中代表黑像素的向量漢明重量最小值l與代表白像素的向量漢明重量最大值h之差與像素?cái)U(kuò)展度m之比，即：α=(l-h)/m，其中α∈[0,1]，當(dāng)α=0時(shí)代表黑白像素的灰度值相等，完全不能辨別出原圖像，即無法識(shí)別秘密信息；當(dāng)α=1時(shí)代表恢復(fù)圖像中黑白像素完美恢復(fù)，是最理想的情況。

3) 定義2給出多余列的概念，用于后續(xù)算法2中加密矩陣的構(gòu)成。

2 方案設(shè)計(jì)

本節(jié)構(gòu)造一種外形比例不失真的(k,n)“異或”視覺密碼方案的秘密分享和恢復(fù)流程，并對(duì)方案的有效性進(jìn)行證明。

2.1 秘密分享流程

為進(jìn)一步優(yōu)化視覺密碼相關(guān)參數(shù)，本文通過添加奇偶列的方法構(gòu)造加密矩陣，通過融合多行掃描和多點(diǎn)加密技術(shù)，構(gòu)造(k,n)方案的秘密圖像分享流程如圖1所示，通過該流程生成的共享份不存在像素?cái)U(kuò)展。

算法1秘密圖像分享算法

輸入：秘密圖像S。

輸出：共享份SI1，SI2，…，SIn。

Step1讀取原始秘密圖像S中的各像素信息。

Step3計(jì)算這m個(gè)像素中黑像素的個(gè)數(shù)，記為b，用eb代表已經(jīng)完成掃描的像素中含有b個(gè)黑像素的掃描序列的個(gè)數(shù)，其中b=(0,1,…,m)，初始時(shí)定義eb=0。

Step5將這m個(gè)像素按掃描順序依次標(biāo)記為向量Plj=(Vl1，Vl2，…,Vlm),(l=1,2,…,m),用l標(biāo)記完成掃描序列的個(gè)數(shù)，j表示當(dāng)前掃描到的像素在Plj標(biāo)記向量中的位置，初始化l=1,j=1。

Step7判斷是否j=m。若是，則返回Step 2，重新掃描；若不是，則令j=j+1，進(jìn)行下一個(gè)像素的處理。

Step9輸出生成的共享份SI1，SI2，…，SIn，算法結(jié)束。

關(guān)于算法1的三點(diǎn)補(bǔ)充說明：

1) Step 2-Step 4實(shí)現(xiàn)秘密圖像的多行掃描，按行列順序依次將秘密圖像以m個(gè)像素為單位進(jìn)行劃分，并計(jì)算各m個(gè)像素中黑像素個(gè)數(shù)；

3) Step 4中加密矩陣設(shè)計(jì)是算法的核心環(huán)節(jié)，本文提出一種基于奇偶列的加密矩陣構(gòu)造方法，具體如算法2所示。

加密矩陣的構(gòu)造流程如圖2所示。

圖2 加密矩陣構(gòu)造流程

算法2加密矩陣構(gòu)造算法

輸入：門限結(jié)構(gòu)(k,n)，n≥k≥2。

輸出：加密矩陣(C0，C1)。

Step1對(duì)于所有偶數(shù)p(0≤p≤k)，若2p≤k，則令q=p；否則，令q=n+p-k，將所有含q個(gè)“1”的n維列向量的組合添加到矩陣C0中。

Step2對(duì)于所有奇數(shù)p(0≤p≤k)，若2p≤k，則令q=p；否則，令q=n+p-k，將所有含q個(gè)“1”的n維列向量的組合添加到矩陣C1中。

Step3依據(jù)定義2，在C0和C1中添加多余列：1) 將C1中的多余列用Step 1和Step 2的方法添加到C0中，生成新的C0；2) 將C0中的多余列添加到C1中，生成新的C1。

Step4判斷C0、C1中的多余列是否相等，若相等，則該步驟結(jié)束，否則轉(zhuǎn)到Step 1。

Step5生成和輸出加密矩陣C0、C1，算法結(jié)束。

2.2 秘密恢復(fù)流程

秘密恢復(fù)如圖3所示，依據(jù)(k,n)門限原理，從生成的n個(gè)共享份SIi(i=1,2,…,n)中任取k個(gè)，采用“異或”操作進(jìn)行疊加，即可恢復(fù)出原秘密圖像。

圖3 秘密恢復(fù)流程

3 方案有效性證明

依據(jù)定義1，本節(jié)分別從安全性和對(duì)比性兩個(gè)方面對(duì)方案的有效性進(jìn)行形式化證明。

引理1[1]：在(k,k)-VCS中，加密矩陣C0(k×k)中任意一列1的個(gè)數(shù)為偶數(shù)，C1(k×k)中任意一列1的個(gè)數(shù)為奇數(shù)。

定理2(安全性) 當(dāng)X?P時(shí)，H(V(X,C0,⊕))=H(V(X,C1,⊕))。

證明：根據(jù)(k,n)方案的加密矩陣構(gòu)造方法，C0(C1)中任取k行產(chǎn)生的多余列將以同樣數(shù)目添加到C1(C0)中去，將C0(C1)中任取k行產(chǎn)生的所有多余列和從C1(C0)添加過來的所有多余列合并在一起生成加密矩陣C0(C1)的相同列，通過添加多余列來保證加密矩陣C0(C1)的任意k行由引理1中的矩陣C0(k×k)(C1(k×k))相同列構(gòu)成。故C0、C1任意k行中相同列所包含的列向量相同，由于相同列具有相同的漢明重量，在只考慮任意k行時(shí)可以忽略。對(duì)于C0(C1)取k行剩余的偶數(shù)(奇數(shù))列，滿足C0(k×k)(C1(k×k))矩陣的特性。任取p(p

則在指定擴(kuò)展位置，對(duì)于奇數(shù)列p有SUM1或SUM2種將C0(p×p)(C1(p×p))擴(kuò)展為基本C0(k×k)(C1(k×k))矩陣的組合方式，利用組合數(shù)學(xué)可以證明SUM1=SUM2[5]，此處不再贅述。

同樣反過來，可以推導(dǎo)出C0、C1中任意p(p

定理3(對(duì)比性) 當(dāng)X?Q時(shí),H(V(X,S1,⊕))-H(V(X,S0,⊕))>0。

證明：如果X?Q，則存在參與者個(gè)數(shù)大于等于門限值k。當(dāng)參與者個(gè)數(shù)等于k時(shí)，(C0,C1)中任意k行包含(C0(k×k),C1(k×k))及相同列，由于相同列無論是“異或”還是“或”疊加所得到的漢明重量相等，不影響漢明重量差。則對(duì)于C0(k×k)(C1(k×k))中的偶數(shù)(奇數(shù))列，H(V(X,C1(k×k),⊕))-H(V(X,C0(k×k),⊕))=2k-1>0，即參與者個(gè)數(shù)為k時(shí)秘密圖像可恢復(fù)。當(dāng)參與者個(gè)數(shù)大于k時(shí)，任取其中k個(gè)共享份“異或”疊加即可恢復(fù)圖像，滿足定義1中的對(duì)比性條件。

4 實(shí)驗(yàn)分析

下面以圖4黑白秘密圖像S為例，采用(4,5)門限結(jié)構(gòu)對(duì)方案有效性進(jìn)行實(shí)驗(yàn)驗(yàn)證。首先利用2.1節(jié)算法2構(gòu)造(4,5)方案的加密矩陣如下：

(a) 秘密圖像S(b) 共享份SI1

(e) 共享份SI4(f) 共享份SI5圖4 秘密圖像與共享份

利用2.1節(jié)算法1生成共享份SI1、SI2、SI3、SI4、SI5,如圖4所示，基于2.2節(jié)恢復(fù)流程得到疊加圖像如圖5所示，依據(jù)第1節(jié)相對(duì)差計(jì)算公式得到方案參數(shù)如表1所示。可以看出，共享份圖像完全雜亂無章，不會(huì)泄露原秘密圖像S的任何信息，當(dāng)少于4個(gè)共享份進(jìn)行疊加時(shí)，也無法恢復(fù)秘密信息，驗(yàn)證方案的安全性。當(dāng)不少于4個(gè)共享份進(jìn)行“異或”運(yùn)算時(shí)，可以顯示秘密信息，驗(yàn)證方案的對(duì)比性，即必須滿足(k,n)門限條件時(shí)才可完成秘密恢復(fù)。

(a) SI1⊕SI2(b) SI2⊕SI3⊕SI4

(c) SI1⊕SI2⊕SI3⊕SI4(d) SI1⊕SI2⊕SI3⊕SI4⊕SI5圖5 不同數(shù)量共享份疊加效果

表1 方案參數(shù)比較

將本文與文獻(xiàn)[12,16]進(jìn)行對(duì)比，恢復(fù)效果比較如圖6所示?？梢钥闯?，文獻(xiàn)[12]的恢復(fù)圖像雖然不存在像素?cái)U(kuò)展但恢復(fù)效果不佳，由于文獻(xiàn)[12]設(shè)計(jì)受限于“或”運(yùn)算，導(dǎo)致恢復(fù)圖像的相對(duì)差為1/8，而本文中4個(gè)共享份進(jìn)行恢復(fù)時(shí)的相對(duì)差為8/15，恢復(fù)效果明顯優(yōu)于文獻(xiàn)[12]；文獻(xiàn)[16]基于“異或”運(yùn)算設(shè)計(jì)，雖然能實(shí)現(xiàn)秘密區(qū)域的完美恢復(fù)，但恢復(fù)圖像較原始圖像S在外形尺寸上存在較大失真，像素?cái)U(kuò)展為2.5，特別地，當(dāng)k、n值逐漸增大時(shí)，像素?cái)U(kuò)展度m迅速增加，不便于共享份圖像的傳輸和存儲(chǔ)。綜上，本文方案在實(shí)現(xiàn)外形比例不失真的前提下，明顯提高相對(duì)差，折中考慮像素?cái)U(kuò)展度和相對(duì)差，使方案關(guān)鍵參數(shù)得到優(yōu)化。

(a) 本文恢復(fù)效果(b) 文獻(xiàn)[12]恢復(fù)效果

5 結(jié) 語

本文提出的(k,n)“異或”視覺密碼方案，通過添加奇偶列的方法構(gòu)造加密矩陣，在秘密分享時(shí)利用多行掃描、多點(diǎn)加密逐像素點(diǎn)進(jìn)行加密，恢復(fù)圖像實(shí)現(xiàn)外形比例不失真，且增大相對(duì)差，優(yōu)化共享份圖像的存儲(chǔ)和傳輸開銷，并改善秘密圖像的恢復(fù)效果。但本文方法無法實(shí)現(xiàn)秘密圖像的完美恢復(fù)，與原始圖像相比，恢復(fù)圖像相對(duì)差仍存在一定的失真，如何進(jìn)一步優(yōu)化是后續(xù)研究重點(diǎn)。