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

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

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

0 引言

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

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

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

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

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

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

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

將定義1 擴(kuò)展為一般存取結(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:對(duì)于所有X′?X，X′? ΓQual}。

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

(1) 任意合格集 X={i1,i2,…iq}可以通過疊加分享圖像重構(gòu)原秘密圖像。定義為：對(duì)于任意的M∈C0，i1,i2,…,ip行的布爾或運(yùn)算的結(jié)果V滿足H(V)≤(m-h)；但是對(duì)于任意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 基于取反運(yùn)算的一般存取結(jié)構(gòu)可視密碼方案

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

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

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

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

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是一個(gè)基于完美的黑度可視密碼方案的Γ0的基本矩陣，其像素?cái)U(kuò)展，灰度值為1-1/m。

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

輸入：

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

分發(fā)過程：

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

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

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

重構(gòu)過程：

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

(2) 計(jì)算U=T×A。

(3) 在U中的每m個(gè)子像素間進(jìn)行OR運(yùn)算得到U′。

輸出：

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

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

有 4個(gè)參與者參與重構(gòu)秘密圖像，其中集合{1,2}和{2,3,4}具有合格可以恢復(fù)出秘密。令Q2={2,3,4}，計(jì)算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)。計(jì)算 U=T×A得到，U0=(0,0,0,0,0,0)及U1=(0,0,1,1,1,1)。再經(jīng)過m個(gè)子像素間的OR運(yùn)算得到，當(dāng)原秘密像素為白時(shí)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.