具有理想對比度的一般存取結構可視密碼方案

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

1 北京電子科技學院 北京 100070

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

0 引言

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

1 一般存取結構的可視密碼方案

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

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

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

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

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

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

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

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

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

2 基于取反運算的一般存取結構可視密碼方案

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

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

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

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

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

矩陣L0和L1的過程如下：

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

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

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

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

輸入：

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

分發過程：

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

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

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

重構過程：

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

(2) 計算U=T×A。

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

輸出：

重構的秘密圖像U′

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

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

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

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

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

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

Viet和 Kurosawa曾經提出了基于取反運算的一般存取結構可視密碼方案，但該方案是基于完美的黑度可視密碼方案構造的，并且只能實現近于理想的對比度。而相比Hu和Tzeng提出的方案，本方案具有以下優點：

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

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

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

3 結論

根據本文提出的方案構造的基本矩陣L0，L1和A如下：

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

有 4個參與者參與重構秘密圖像，其中集合{1,2}和{2,3,4}具有合格可以恢復出秘密。令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)。再經過m個子像素間的OR運算得到，當原秘密像素為白時U′0=0，當原秘密

[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.