基于異或的外形比例不失真(k,n)視覺密碼方案

董 晨 張皓宇 季姝廷 李 磊

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

0 引 言

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

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

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

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

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

1 基本概念

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

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

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

2) 對比性條件：當X?Q時，H(V(X,S1,⊕))-H(V(X,S0,⊕))>0。

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

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

關于上述定義的三點補充說明：

1)m表示原始圖像中的一個像素在分享圖像中擴大的子像素的個數(shù)，也就是原始圖像經過擴展后在面積上失真的倍數(shù)。像素擴展度越大所需的存儲空間就越大，即代表其在面積上的失真也會越大。

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

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

2 方案設計

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

2.1 秘密分享流程

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

算法1秘密圖像分享算法

輸入：秘密圖像S。

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

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

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

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

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

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

關于算法1的三點補充說明：

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

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

加密矩陣的構造流程如圖2所示。

圖2 加密矩陣構造流程

算法2加密矩陣構造算法

輸入：門限結構(k,n)，n≥k≥2。

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

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

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

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

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

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

2.2 秘密恢復流程

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

圖3 秘密恢復流程

3 方案有效性證明

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

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

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

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

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

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

定理3(對比性) 當X?Q時,H(V(X,S1,⊕))-H(V(X,S0,⊕))>0。

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

4 實驗分析

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

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

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

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

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

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

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

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

(a) 本文恢復效果(b) 文獻[12]恢復效果

5 結 語

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