解密区域完美恢复的区域递增式视觉密码方案构造

胡 浩 郁 滨 沈 刚 张学思



解密区域完美恢复的区域递增式视觉密码方案构造

胡 浩*郁 滨 沈 刚 张学思

(信息工程大学 郑州 450001)

为了优化区域递增式视觉密码的恢复效果，该文通过为共享份添加身份标识，并结合随机数，构造了单个参与者持有多个共享份的异或单秘密视觉密码方案，在此基础上，设计了异或区域递增式视觉密码的秘密分享与恢复算法。对于解密区域利用异或单秘密方案进行分享，对于未解密区域，通过填充随机数实现秘密遮盖。实验结果表明，该方案可以实现解密区域图像的完美恢复，且有效减小了共享份的存储与传输开销。

视觉密码；图像秘密分享；区域递增；密级；异或运算；完美恢复

1 引言

多秘密视觉密码方案(Multi-secret Visual Cryptography Scheme, MVCS)主要用来分享多幅独立的秘密图像，与MVCS不同，区域递增式视觉密码方案[5](Region Incrementing VCS, RIVCS)将一幅秘密图像划分为多个区域，不同区域具有不同的图像，区域恢复的数量与参与者人数有关，参与者人数越多，恢复区域的数目越多，在信息的分级管理、多密级访问控制领域有着广阔的应用前景。

文献[5]设计了存取结构为(2,)的基于或运算(OR)的区域递增式视觉密码方案(OR-based RIVCS, ORIVCS)，将一幅秘密图像划分个区域，共享份以透明胶片作为载体，秘密恢复时叠加(相当于OR运算)任意个共享份可以解密个区域的秘密信息，但参与者人数仅局限于3, 4, 5。文献[6]建立加密矩阵的线性规划模型，并构造了像素扩展度最优的(2,)方案，但模型计算复杂度随着的增加呈指数级增长。文献[7-9]通过拼接基于或运算的(,)单秘密方案(OR-based VCS, OVCS)的加密矩阵，突破了(2,)结构的限制，提出了像素扩展度优化的(,)-ORIVCS加密矩阵的设计方法，但恢复图像的色彩存在反转失真问题。文献[10]实现了恢复图像的不同区域对比度相等，解决了现有方案与传统黑白二值视觉密码不兼容的问题，但像素扩展度仍需进一步优化。

上述方案主要依靠构造精简的加密矩阵来降低像素扩展度，各区域加密矩阵本质上是单秘密方案[11]加密矩阵的线性组合，因而随着和的增加，矩阵规模迅速增加，像素扩展度急剧增大，恢复图像的效果也随之降低。为了减小像素扩展度，文献[12]提出了基于随机栅格(Random Grid, RG)的视觉密码，共享份是大小与原图像相等的光栅，将它们叠加在一起，利用白黑区域的光通量不同来显示秘密图像，在此基础上，文献[13,14]给出了多种(,)-ORIVCS的构造方法。随机栅格可以有效控制像素扩展，但该类方案的恢复图像中，原秘密图像黑白像素以一定的概率被正确恢复，因此恢复图像的信息熵存在损失。

通过梳理以上研究成果不难发现，现有方案着重于研究如何降低像素扩展度，对于如何提高恢复效果未能给出有效的解决方案，本质上此类构造方法主要局限于OR运算，由于OR运算的特点，致使黑像素(1)没有逆元，半群的代数结构导致原始白像素(0)无法被正确恢复。为了改善单秘密OVCS的恢复效果，文献[15]将异或运算(XOR)引入视觉密码，给出了基于异或运算的视觉密码方案(XOR-based VCS, XVCS)[16]的定义，并设计了(,)-XVCS，利用，提高了白像素的恢复概率。

文献[17]利用XOR运算的{0,1}群中0作为单位元的性质，设计了一种XRIVCS，当所有共享份叠加时，白像素的恢复概率为1，但黑像素无法完美恢复。文献[18]分析了OR运算和XOR运算的特性，指出由于XOR运算存在奇偶特性(奇数个1的运算结果为1，偶数个1的运算结果为0)，即偶数个黑像素进行运算后恢复成白像素，导致原始黑像素的颜色产生反转，因而很难直接应用到目前RIVCS的构造方法中。

针对上述问题，本文通过给共享份添加身份标识，分享过程避开加密矩阵，直接结合随机数生成共享份，恢复过程依据身份标识出示对应共享份，构造了单个参与者持有多个共享份的单秘密XVCS。在此基础上，结合不同授权子集完成RIVCS的共享份的赋值过程，对于任意授权子集对应解密区域利用XVCS进行分享，对于未解密区域，通过填充随机数实现遮盖，能够保持各区域分享的独立性，从而克服XOR运算产生的像素反转。实验结果表明，本文设计的基于异或运算的区域递增式视觉密码方案(XOR-based RIVCS, XRIVCS)能够实现解密区域图像的完美恢复，且进一步降低共享份的存储及传输开销。

2 基本概念

为方便描述，文中所用符号及含义见表1。

表1主要符号及其含义

定义1[19]记参与者集合，称能够恢复秘密图像的参与者集合为授权子集，记为，不能恢复秘密图像的参与者集合为禁止子集，记为，满足,，且。记，称为最小授权集合。(,)门限结构是一类特殊的存取结构，满足。

不同于以往方案[17]，本文提出的方案中单个参与者持有多个共享份，每个共享份有不同的标识，秘密恢复时，不同参与者依据恢复集合出示对应标识的共享份来完成秘密恢复，下面给出参与者持有多个共享份的XRIVCS的定义。

定义2 设表示参与者总数，表示秘密恢复门限值，满足，秘密图像划分了个区域,,，即。(,)是参与者集合上的门限结构，设表示参与者持有的标识为的共享份，,，记任意参与者集合，函数＝为秘密恢复函数，表示对中参与者持有的标识为的共享份进行XOR运算，若一个(,)-XRIVCS成立，则满足以下2个条件：

其中，条件(1)是安全性条件，保证当参与者人数小于个时，得不到秘密图像的任何信息。条件(2)是对比性条件，表明个参与者最多可以恢复区域R。若中解密区域图像与原始图像完全一致，称该方案的解密区域是完美恢复的。

关于定义2的两点补充说明：

(1)考虑到严格的视觉密码方案，在秘密恢复前应该对共享份的真实性进行认证，因而在秘密恢复时，参与者可以提前知道恢复集合，能够依据恢复集合来判别出示某个共享份，因此参与者持有多个共享份的分享方式是合理的。

(2)本文方案成立的前提条件是每个参与者都是可信的，因此不单独考虑欺骗者存在的情形，这也是大部分视觉密码方案设计的前提，故单个参与者持有多个共享份的设计方法不会降低方案的安全性。

定义3 设单个共享份的像素扩展度为，单个参与者持有共享份数量为，则单个参与者持有共享份的像素扩展度总和(Total Size Expansion, TSE)满足。

若秘密图像尺寸大小一定，则TSE和可用来衡量方案的存储和传输开销，TSE值越小，表明保存共享份所需的存储空间越小，值越小，表明秘密恢复时，占用通信带宽资源产生的传输开销越小。

3 方案设计

由于区域递增式视觉密码是在单秘密分享视觉密码的基础上构造的，因此，本节先给出一种单秘密(,)-XVCS的共享份生成算法，在此基础上，设计XRIVCS的秘密分享与恢复流程。

3.1 XVCS的共享份生成算法

定义空白共享份尺寸大小与秘密图像相同，依次为每个最小授权子集中的参与者分发标识为的共享份，利用秘密图像和随机数共同完成空白共享份填充过程，算法步骤如下。

输入：,值，秘密图像(),。

图1 集合K中参与者的共享份赋值方法

步骤3 输出步骤1和步骤2生成的所有共享份，分发给对应参与者，算法结束。

在上述算法中，有以下两点需要说明：

(1)当XOR运算的共享份数目达到个时即可恢复秘密图像，当时，文献[15]认为取中的个参与者即可恢复秘密图像，因此不需要直接计算中所有的共享份。

(2)与文献[11]方案相比，本节XVCS中单个参与者持有多个共享份，当参与者数量达到恢复门限值时，依据恢复集合，出示相应标识的共享份来完成秘密恢复，而文献[11]中单个参与者只持有一个共享份。

3.2 XRIVCS的秘密分享与恢复流程

在3.1节的基础上，本节给出XRIVCS的设计流程，基本思想是依次遍历区域

(1)秘密分享流程 秘密分享流程如图2所示，具体步骤如下。

图2 (k,n)-XRIVCS的秘密分享流程

步骤2 初始化与大小相等的空白共享份，对于区域,，利用3.1节提出的XVCS的构造方法进行赋值，对于区域，利用随机数序列赋值；

步骤4 输出步骤1-步骤3生成的所有共享份，分发给对应参与者，算法结束。

关于上述算法的补充说明：

步骤2是算法的核心，通过对解密区域和未解密区域单独进行加密，保持各部分分享的独立性，在实现区域递增式显示的前提下，可以解决像素叠加时由于异或运算产生的颜色反转问题。

4 有效性证明

命题1 (,)-XRIVCS中单个参与者持有共

证明 由3.2节可知(,)-XRIVCS通过(,) - XVCS, (+1,)-XVCS,,(,)-XVCS构造，对于(,)-XVCS，不妨设最小授权子集，参与者1持有的共享份数量为，由3.1节共享份生成算法可得等于包含了参与者1的的数量，即集合的组合数，由于>，故，因而参与者1持有的共享份总数。证毕

5 实验与分析

5.1方案有效性分析

本方案主要针对黑白二值图像，由于彩色和灰度图像中像素的色度阶数大于2，因此不能直接应用于本方案。以(2,3)-XRIVCS为例，对本文方案进行仿真实验，并与文献[6,10]的实验结果进行比较。实验图像如图3(a)所示，划分了2个大小不相等的区域，其中，1=“”,2=“”。初始化与大小相等的空白共享份，记为参与者的标识为的共享份中区域R对应部分，按照3.2节秘密分享流程，可以得到图3所示的实验结果。

图3 (2, 3)区域递增式视觉密码方案的实验结果

由图3所示实验结果分析可知：

(1)单个共享份(图3(c, d, e))是杂乱无章的，无法得到任何区域的秘密信息；2个相同标识的共享份进行异或运算后，区域1实现了完美恢复，而区域2是杂乱无章的(图3(f))；3个相同标识的共享份进行异或运算后，区域1和2都实现了完美恢复(图3(g))，此时恢复图像与原图像完全一致，与预期结果相同。

(2)在安全性方面，由于秘密图像中各区域划分大小不必相等，参与者无法预先知道秘密区域划分情况，因此无法根据恢复区域占共享份的大小比例来推测其他信息，确保了方案的安全性。

(3)在恢复效果方面，文献[6]对各区域利用不同矩阵单独进行分享，带来了恢复图像色彩反转失真的问题(图3(h,i)中背景颜色比和的颜色深)，且不同恢复区域对比度不相等，与典型黑白二值视觉密码方案不兼容[10]；文献[10]克服了色彩反转失真问题，且不同恢复区域的对比度相等，但恢复图像整体偏暗；本方案不同解密区域的对比度均为1(图3(f,g))，实现了解密区域图像的完美恢复，显然本方案的恢复效果最优。

5.2对比度分析

对比度可以用来衡量恢复图像的视觉效果，对比度越高，则恢复图像越清晰，反之，则越模糊。在考虑恢复图像不存在信息熵损失时，本文与文献[8]中基于OR运算的最优方案的对比度比较见表2，从表中可以看出，对于不同,值，本方案中恢复区域的对比度均为1，可以实现解密图像的完美恢复。文献[8]的对比度最大值为1/2，且随着参与者人数的增多，恢复图像的对比度逐渐降低，直接影响了恢复图像的视觉效果。

表2本文方案与文献[8]的对比度比较

注：“-”表示该项不存在

5.3像素扩展度分析

TSE值可以用来衡量共享份的存储开销，在恢复图像不存在信息损失的前提下，本节给出本方案与文献[5-8]的TSE值比较结果。从表3可以看出，当，对于不同的值，本方案的TSE值要明显小于文献[5-8]；当时，可以看出值越大，本文方案的优化效果越明显，(3,5)方案中，本文的TSE值为11，文献[8]为20，保存共享份的存储开销是文献[8]的55%, (4,5)方案中，本文的TSE值为5，文献[8]为20，存储开销是文献[8]的25%，说明本方案的优化效率得到提高。

表3本文方案与文献[5~8]的TSE值比较

注：“-”表示该项不存在

5.4方案性能综合比较

本方案与其他区域递增式视觉密码方案综合比较见表4。

表4本文方案与其他区域递增式视觉密码方案的比较

注：为(,)-OVCS的像素扩展度

(1)在设计方法方面，文献[6,8,10,17]基于加密矩阵设计，由于构造矩阵的约束条件复杂，随着参与者人数的增加，矩阵规模迅速增大，导致像素扩展度急剧增加。文献[13,14]基于随机栅格实现了像素不扩展，但恢复图像的信息熵存在损失。本方案中不同区域的分享过程独立，基于授权集合，利用随机数设计，构造方法简单，不存在像素扩展，降低了共享份的存储开销，避免了构造和保存加密矩阵产生的额外开销。同时由于“异或”运算相当于3次“或”运算和4次“非”运算，因而相比或运算，异或运算并没有增加恢复操作的计算复杂度的阶数。

(2)在色彩失真方面，文献[8, 10, 14, 17]和本方案的恢复图像不存在色彩反转失真，因而可以正确显示原始图像颜色的真实信息。文献[10,14]和本方案中不同解密区域的对比度相等，与传统黑白视觉密码方案兼容。

(3)在完美恢复方面，文献[17]仅当所有共享份叠加时，能够实现白像素的完美恢复，而本方案进一步实现了所有解密区域图像的完美恢复。

(4)在传输开销方面，单个共享份的像素扩展度用来衡量方案的传输开销，文献[6,8,10,17]中单个共享份的像素扩展度随着参与者人数的增加而迅速增大，在秘密恢复过程中，共享份的传输开销大。文献[13,14]和本方案中单个共享份不存在像素扩展，在网络通信带宽受限的应用环境中，可以有效降低传输开销。

(5)在存储开销方面，共享份的像素扩展度之和用来衡量方案的存储开销，文献[6,8,10,17]的像素扩展度为单秘密方案的共享份像素扩展度之和(删除其中的冗余列)。文献[13,14]的存储开销最小，但损失了恢复图像的细节信息。本方案中单个参与者持多个共享份，共享份像素扩展度总和较小，在存储资源匮乏的应用环境中，能够有效降低共享份的存储开销，并确保恢复图像不存在信息损失。

6 结束语

本文对区域递增式视觉密码进行了研究，给出了一种解密区域完美恢复的实现方案，并对方案的有效性进行了理论证明和实验验证。通过为共享份添加身份标识，分享过程避开加密矩阵，直接利用随机数生成共享份，恢复过程依据身份标识出示对应共享份，构造了单个参与者持有多个共享份的单秘密视觉密码方案，在此基础上设计的区域递增式视觉密码方案，保持了各区域分享的独立性，解决了异或运算产生的像素反转问题，进一步降低了像素扩展度并提高了秘密图像的恢复效果，为区域递增式视觉密码的研究提供了一条新思路。

参考文献

[1] 李鹏, 马培军, 苏小红, 等. 多重门限的图像秘密共享方法[J].电子学报, 2012, 40(3): 518-524. doi: 10.3969/j.issn.0372-2112. 2012.03.018.

LI Ping, MA Peijun, SU Xiaohong,Multi-threshold image secret sharing scheme[J]., 2012, 40(3): 518-524. doi: 10.3969/j.issn.0372-2112.2012.03.018.

[2] 付正欣, 沈刚, 郁滨, 等. 一种可完全恢复的门限多秘密视觉密码方案[J]. 软件学报, 2015, 26(7): 1757-1771. doi: 10.13328 /j.cnki.jos.004611.

FU Zhengxin, SHEN Gang, YU Bin,Threshold multi- secret visual cryptography scheme with perfect recovery[J]., 2015, 26(7): 1757-1771. doi: 10.13328/ j.cnki.jos.004611.

[3] BIN Y and GANG S. Multi-secret visual cryptography with deterministic contrast[J]., 2014, 72(2): 1867-1886. doi: 10.1007/s11042-013-1479-8.

[4] SHYU S J and JIANG H W. General constructions for threshold multiple-secret visual cryptography schemes[J]., 2013, 8(5): 733-743. doi: 10.1109/TIFS.2013.2250432.

[5] WANG R Z. Region incrementing visual cryptography[J]., 2009, 16(8): 659-662. doi: 10.1109/LSP.2009.2021334.

[6] SHYU S J and JIANG H W. Efficient construction for region incrementing visual cryptography[J]., 2012, 22(5): 769-777. doi: 10.1109/TCSVT.2011.2180769.

[7] YANG C N, SHIH H W, CHU Y Y,New region incrementing visual cryptography scheme[C]. Proceedings of the International Conference on Image Processing, Computer Vision, and Pattern Recognition in Conjunction with WORLDCOMP, Las Vegas, USA, 2011: 323-329.

[8] YANG C N, SHIH H W, WU C C,out ofregion incrementing scheme in visual cryptography[J]., 2012, 22(5): 799-810. doi: 10.1109/TCSVT.2011.2180952.

[9] YANG C N, LIN Y C, and WU C C. Region-in-region incrementing visual cryptography scheme[C]. Proceedings of 12th International Workshop on Digital-Forensics and Watermarking, Auckland, New Zealand, 2013: 449-463. doi: 10.1007/978-3-642-40099-5_37.

[10] 李吉亮, 李顺东, 王道顺. 区域递增视觉密码的构造[OL]. http://wenku.it168.com/huiyi/2349, 2014.

LI Jiliang, LI Shundong, and Wang Daoshun. Construction of region incrementing visual cryptography[OL]. http:// wenku.it168.com/huiyi/2349, 2014.

[11] NAOR M and SHAMIR A. Visual cryptography[C]. Proceedings of the Advances in Cryptology-Eurocrypt’94, Berlin, 1995: 1-12. doi: 10.1007/BFb0053419.

[12] SHYU S. Image encryption by multiple random grids[J]., 2009, 42(7): 1582-1596.doi:10.1016/j. patcog.2008.08.023.

[13] WANG R Z, LAN Y C, LEE Y K,Incrementing visual cryptography using random grids[J]., 2010, 283(21): 4242-4249. doi: 10.1016/j.optcom.2010.06.042.

[14] ZHONG G S and WANG J J. Region incrementing visual secret sharing scheme based on random grids [C]. Proceedings of IEEE International Symposium on Circuits and Systems, Los Alamitos, 2013: 2351-2354. doi: 10.1109/ISCAS.2013. 6572350.

[15] TUYLS P, HOLLMANN H D L, LINT J H V,XOR- based visual cryptography schemes[J].,, 2005, 37(1): 169-186. doi: 10.1007/s10623-004- 3816-4.

[16] OU D, SUN W, and WU X T. Non-expansible XOR-based visual cryptography scheme with meaningful shares[J]., 2015, 108: 604-621. doi: 10.1016/j.sigpro.2014.10. 011.

[17] HAO H, GANG S, FU Z X,. General construction for XOR-based visual cryptography and its extended capability [J]., 2016, 1-29.doi: 10.1007/s11042-016-3250-4.

[18] YANG C N and WANG D S. Property analysis of XOR based visual cryptography[J]., 2014, 24(2): 189-197. doi: 10.1109/TCSVT.2013.2276708.

[19] ATENIESE G, BLUNDO C, SANTIS A D,. Visual cryptography for general access structures[J]., 1996, 129(2): 86-106. doi: 10.1006/inco. 1996.0076.

Region Incrementing Visual Cryptography Scheme with Decrypt Regions Perfectly Recovered

HU Hao YU Bin SHEN Gang ZHANG Xuesi

(,450001,)

In order to optimize the recovery quality of Region Incrementing Visual Cryptography Scheme (RIVCS), by adding identities for shares and combing the random numbers, an XOR-based single-secret sharing Visual Cryptography Scheme (XVCS) with individual participant holding multi-share is designed. On basis of this, the secret sharing and recovering algorithms for XOR-based RIVCS (XRIVCS) are designed. For the decrypt regions, XVCS is used to share, and for the not decrypt regions, the random numbers are filled to keep the secret. The experimental results show that, the proposed scheme can realize the perfect recovery of decrypt regions, and decrease the storage and transmission cost effectively.

Visual cryptography; Image secret sharing; Region incrementing; Security levels; XOR operation; Perfect recovery

TP309.7

A

1009-5896(2016)10-2647-07

10.11999/JEIT151448

2015-12-22；改回日期：2016-05-26；网络出版：2016-07-14

胡浩 wjjhh_908@163.com

国家自然科学基金(61070086)，信息保障技术重点实验室开放基金(KJ-13-107)

The National Natural Science Foundation of China (61070086), The Foundation of Science and Technology on Information Assurance Laboratory of China (KJ-13-107)

胡浩： 男，1989年生，博士生，研究方向为视觉密码和网络安全态势感知.

郁滨： 男，1964年生，教授，博士生导师，主要研究方向为视觉密码和信息安全.

沈刚： 男，1986年生，博士生，研究方向为视觉密码.

张学思： 女，1990年生，助理工程师，主要研究方向为信息安全.