具有理想對比度的一般存取結(jié)構(gòu)可視密碼方案

何文才 董昊聰 韓妍妍 劉培鶴 趙菲 商逸瀟

1 北京電子科技學(xué)院 北京 100070

2 西安電子科技大學(xué)通信工程學(xué)院 陜西 710071

0 引言

本文提出了一種基于一般存取結(jié)構(gòu)的可視密碼方案，應(yīng)用取反運算可獲得理想的對比度。該方案同時實現(xiàn)了重構(gòu)的圖像與原秘密圖像保持一致，沒有像素擴展。本文首先回顧介紹了Naor和Shamir提出的(k, n)可視密碼方案，并擴展到一般存取結(jié)構(gòu)的方案；然后構(gòu)造出基于一般存取結(jié)構(gòu)的可視密碼方案；最后證明了該方案的有效性及安全性，并給出了具體例子。

1 一般存取結(jié)構(gòu)的可視密碼方案

定義 1. 一般的(k, n)可視密碼方案是利用兩個n×m階的布爾矩陣集合C0和C1來構(gòu)造的。為了分享一個白像素，就從C0中隨機選擇一個矩陣；為了分享一個黑像素，就從C1中隨機選擇一個矩陣。所選的矩陣定義了n個分享圖像中的m個子像素的顏色。如果這個方案滿足如下條件，我們就稱其為一個可視密碼方案(前兩個稱為對比條件，第三個稱為安全條件)：

(1) 對于C0中的任何矩陣S，矩陣S中任意k行或操作的結(jié)果向量V滿足H(V)≤(m-h)；

(2) 對于C1中的任何矩陣S，矩陣S中任意k行或操作的結(jié)果向量V滿足H(V)≥(m-l)；

(3) 當(dāng)參數(shù)q≤k-1時，對于任意集合{i1,i2,…iq}∈{1,...,n}，提取集合C0和集合C1中每個矩陣的i1,i2,…iq行，構(gòu)成兩個新的矩陣集合，那么獲得的兩個矩陣集合以同樣的頻率包含相同的矩陣(由 Ct(t=0,1)中的每一矩陣在第i1,i2,…iq行上的限制得到的q×m階布爾矩陣集合是相同的)。

前面兩個條件意味通過人眼觀察任意k個分享的疊加可以獲得秘密圖像的信息，而第三個條件則保證了在少于k個分享的條件下，攻擊者不能獲得秘密圖像的任何信息，這就表示(k, n)可視密碼方案是安全的。

將定義1 擴展為一般存取結(jié)構(gòu)，設(shè)參與者集合為P={1,...,n}，2P表示集合 P的所有子集的集合，將其劃分為合格集和禁止集，只有合格集可以恢復(fù)出秘密。設(shè)ΓQual?2P和ΓForb?2P，且ΓQual∩ΓForb=φ，其中ΓQual中的元素稱為合格集，ΓForb中的元素稱為禁止集，則(ΓQual,ΓForb)稱為方案的一般存取結(jié)構(gòu)。最小合格集定義為Γ0={X∈ΓQual:對于所有X′?X，X′? ΓQual}。

定義2. 設(shè)(ΓQual,ΓForb)是n個參與者的存取結(jié)構(gòu)，兩個由n×m的布爾矩陣構(gòu)成的集合C0和C1構(gòu)成一個(ΓQual,ΓForb)-VCS，如果存在像素擴展m和兩個整數(shù)h和l (h> l) 滿足：

(1) 任意合格集 X={i1,i2,…iq}可以通過疊加分享圖像重構(gòu)原秘密圖像。定義為：對于任意的M∈C0，i1,i2,…,ip行的布爾或運算的結(jié)果V滿足H(V)≤(m-h)；但是對于任意M∈C1有 H(V)≥ (m-l)。

(2) 任意禁止集 X={i1,i2,…iq}無法得到關(guān)于秘密圖像的任何信息。定義為：選取Ct(t=0,1)的 i1,i2,…,ip行構(gòu)成的p×m的布爾矩陣構(gòu)成的集合Dt是不可區(qū)分的，即它們以相同的頻率包含相同的矩陣。

2 基于取反運算的一般存取結(jié)構(gòu)可視密碼方案

如上文所述，僅僅應(yīng)用或(OR)運算幾乎不能構(gòu)造出一般存取結(jié)構(gòu)的具有理想對比度的可視密碼方案。本文構(gòu)造了一個基于一般存取結(jié)構(gòu)的可視密碼方案，為了獲得理想的對比度，除取反(NOT)運算之外，我們使用了另外兩種基本的布爾運算：與(AND)運算和異或(XOR)運算。疊加分享圖像 t1和t2其實是在t1和t2之間進行了1次OR運算。而結(jié)合OR和NOT運算，我們可以得到AND運算和XOR運算。具體表示為：

由此可得，1次AND運算相當(dāng)于進行了1次OR運算和3次NOT運算，而1次XOR運算相當(dāng)于進行了3次OR運算和4次NOT運算。為表示方便，下文中直接采用了AND和XOR運算。

首先定義了一個可視密碼方案的最小存取結(jié)構(gòu)Γ0。然后構(gòu)造另一個基本矩陣來生成分發(fā)給參與者的輔助分享圖像(Auxiliary Shadows,AS)。本文構(gòu)造的方案需要借助該分享圖像來獲得理想的對比度，并實現(xiàn)了秘密圖像無失真的重構(gòu)。

本文方案采用了Naor和Shamir提出的(k, k)-VCS作為基本單位來構(gòu)造最小存取結(jié)構(gòu) Γ0。假設(shè)其中對于1≤p≤t，構(gòu)造一個

n×2kp-1維的矩陣,i∈ {0,1}。采用(k, k) -VCS來構(gòu)造基本

矩陣L0和L1的過程如下：

(1) 構(gòu)造L0。的第pi行是(kp, kp) -VCS中基本矩陣S0的第i行，中其他行的元素全部為1。

(2) 構(gòu)造 L1。與 L0的構(gòu)造類似，的第pi行是(kp, kp)-VCS中基本矩陣S1的第i行，中其他行的元素全部為1。

引理 1. L0和L1是一個基于完美的黑度可視密碼方案的Γ0的基本矩陣，其像素擴展，灰度值為1-1/m。

采用上面的定義，對于1≤p≤t，構(gòu)造一個n×2kp-1維的矩陣Mp。矩陣Mp中pi行的元素為1，其他行的元素全部為0。由此，基本輔助矩陣方案的具體執(zhí)行過程如下：

輸入：

(1) n個參與者的集合具有最小的存取結(jié)構(gòu)Γ0。

分發(fā)過程：

分發(fā)者首先要將分享圖像ti分成個子圖像塊ti,p并且每個子圖像塊包含一個秘密圖像。對于，在子圖像塊ti,p中的白或黑像素由和中的n×2kp-1維矩陣來表示。分發(fā)者為了表示一個白(黑)像素，需進行以下操作：

(2) 對于每個參與者i，如果si,j=0(si,j=1)，則子圖像塊tip為白(黑)像素。

(3) 對于每個參與者i，如果ai,j=0(ai,j=1)，則子圖像塊Aip為白(黑)像素。

重構(gòu)過程：

(1) 對所有的分享圖像tj進行XOR運算得到圖像T，對所有分享圖像Aj進行AND運算得到A。其中，j=1,…,kp。

(2) 計算U=T×A。

(3) 在U中的每m個子像素間進行OR運算得到U′。

輸出：

重構(gòu)的秘密圖像U′

引理2. Naor和Shamir提出的(k, k)-VCS是一個基于取反運算可獲得理想對比度的可視密碼方案。

定理 1.令Γ=(P,Q,F)是一個具有 n個參與者集合的存取結(jié)構(gòu)。由基本矩陣S0，S1和A構(gòu)成的基于取反運算的可視密碼方案可實現(xiàn)理想的對比度以及重構(gòu)的圖像與原秘密圖像保持一致，沒有像素擴展。

證明：文獻[8]中已證明利用基本矩陣S0和S1，直接疊加分享圖像tp, 其中p=1,…,kp，i∈Qp可以構(gòu)造出安全的可視密碼方案。同樣，基于取反運算的可視密碼方案和傳統(tǒng)的可視密碼方案一樣安全。基本矩陣A仍然也得不到有關(guān)秘密的任何信息，因為在分享子圖像Aj(j=1,…,kp)中不存在任何的秘密信息。

利用前面介紹的方法構(gòu)造一個基于取反運算適用于一般存取結(jié)構(gòu)的可視密碼方案，令不失一般性，令Γ0={Q1,…,Qt}且X=Q1，其中X表示合格集中的一個子集。對于一般存取結(jié)構(gòu)Γ=(P,Q,F)，以L0，L1和A為基本矩陣的可視密碼方案，秘密圖像經(jīng)過U=T×A運算及在U中的每m個子像素間進行OR運算得到。根據(jù)引理2得到：

由此得知，當(dāng)原像素為白像素時，運算后得到的m個子像素均為白，經(jīng)OR運算后結(jié)果為白；當(dāng)原像素為黑像素時，運算后得到的m個子像素中至少有個黑像素，經(jīng)OR運算后結(jié)果為黑，因此原秘密圖像可以被無失真的恢復(fù)。

例1具體說明了對于一般存取結(jié)構(gòu)可獲得理想對比度的可視密碼方案的構(gòu)造方法。

Viet和 Kurosawa曾經(jīng)提出了基于取反運算的一般存取結(jié)構(gòu)可視密碼方案，但該方案是基于完美的黑度可視密碼方案構(gòu)造的，并且只能實現(xiàn)近于理想的對比度。而相比Hu和Tzeng提出的方案，本方案具有以下優(yōu)點：

(1) 原秘密圖像可以被無失真的重構(gòu)而不是黑像素部分重構(gòu)；

(2) 執(zhí)行更少的OR和XOR運算次數(shù)。本方案過程中需要執(zhí)行1次OR運算和3次NOT運算，而文獻[12]中方案需要進行4次OR運算和4次NOT運算；

(3) 本文方案構(gòu)造的輔助矩陣A中主要為黑子像素，所以分享子圖像中以黑像素為主，不會泄露任何的秘密信息，具有更強的隱蔽性。

3 結(jié)論

根據(jù)本文提出的方案構(gòu)造的基本矩陣L0，L1和A如下：

本文提出了一種基于取反運算的一般存取結(jié)構(gòu)可視密碼方案，該方案借助輔助分享圖像并應(yīng)用簡單的布爾運算實現(xiàn)了理想的對比度。本文方案適用于一般存取結(jié)構(gòu)，且不局限基于完美的黑度可視密碼方案的構(gòu)造，執(zhí)行較少的運算次數(shù)，實現(xiàn)了秘密圖像可以被無失真的重構(gòu)，并且沒有像素擴展。

有 4個參與者參與重構(gòu)秘密圖像，其中集合{1,2}和{2,3,4}具有合格可以恢復(fù)出秘密。令Q2={2,3,4}，計算T=XOR(XOR(t2,t3),t4)和A=AND(AND(t2,t3),t4)，得到L0=(1,0,0,0,0,0)，L1=(0,1,1,1,1,1)和 A=(0,0,1,1,1,1)。計算 U=T×A得到，U0=(0,0,0,0,0,0)及U1=(0,0,1,1,1,1)。再經(jīng)過m個子像素間的OR運算得到，當(dāng)原秘密像素為白時U′0=0，當(dāng)原秘密

[1] BLAKLEY G. Safeguarding cryptographic keys [C] // Proc.AFIPS 1979 Natl. Conf. New York.1979.

[2] SHAMIR A. How to share a secret [J]. Comm. ACM.1979.

[3] NAOR M, SHAMIR A. Visual cryptography [C] // Advances in Cryptology-Proceedings of Eurocypto’ 94, Lecture Notes in Computer Science, Springer-Verlag, New York, 1995.

[4] ATENIESE G, BLUNDO C, DE SANTS A, et a1. Constructions and bounds for visual cryptography [C] // Proceedings of the 23rdInternational Colloquium on Automata, Languages and Programming (ICALP’96). Berlin: Springer.1996.