具有理想对比度的一般存取结构可视密码方案

何文才 董昊聪 韩妍妍 刘培鹤 赵菲 商逸潇

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.