门限视觉密码方案的组构造方法.doc

第10期费如纯等：门限视觉密码方案的组构造方法87门限视觉密码方案的组构造方法费如纯1,2，王丽娜1，张焕国1（1. 武汉大学 计算机学院，湖北 武汉 430072；2. 辽宁科技学院 信息工程系，辽宁 本溪 117022）摘 要：提出了视觉密码的组构造向量的概念和基于组构造向量构造基础矩阵的方法，获得了组构造向量的通解，进而获得了成组的视觉密码方案的通解。利用组构造向量，任何人都可以根据公式简单有效地构造出视觉密码方案。另外，还对d=m的方案和既约的方案进行了研究。组构造向量的概念及其通解还为视觉密码的进一步研究提供了很有价值的思路。关键词：视觉密码；基础矩阵；组构造向量；像素扩张；对比度中图分类号：TP309 文献标识码：A 文章编号：1000-436X(2008)10-0082-06Group construction method of threshold visual cryptography schemesFEI Ru-chun2,1, WANG Li-na1, ZHANG Huan-guo1(1. School of Computer, Wuhan University, Wuhan 430072; China;2. Department of Information Engineering, Liaoning Institute of Science and Technology, Benxi 117022, China)Abstract: The concept of group construction vector for visual cryptography was proposed, and the method based on group construction vector was presented for constructing basic matrices. The complete solutions of group construction vector and that of grouped visual cryptography schemes were obtained. Using the group construction vectors, everyone can construct visual cryptography schemes simply and effectively according to the formulas. The schemes with d=m and irreducible schemes also were researched. The concept and the complete solutions of group construction vector can also present very valuable ideas for the further research on visual cryptography. Key words: visual cryptography; basic matrix; group constructing vector; pixel expansion; contrast1 引言收稿日期：2008-06-21；修回日期：2008-09-21基金项目：国家自然科学基金资助项目（60743003）；湖北自然科学基金资助项目（2007ABA089）；教育部科学技术研究重点项目（108087）；国家自然科学重大研究计划基金资助项目（90718006）Foundation Items: The National Natural Science Foundation of China (90718006, 60743003); The Natural Science Foundation of Hubei Province (2007ABA089); The Science and Technology Research Program of Education Ministry of China (108087); The Major Research Plan of the National Natural Science Foundation of China (90718006)1994年，Naor和Shamir1提出了视觉密码学，其基本思想是将机密的黑白二值图像通过适当的算法隐藏到n个（n2）非机密的分享图像中，在每一个分享图像上都有伪随机分布的黑点和白点，持有不足k个（2kn）图像的人无论用什么方法，都无法分析出原始机密图像的信息；但如果将任意k个分享图像打印在透明胶片上并叠合在一起观看，利用人的视觉系统就能够解密恢复出原始的机密图像信息。视觉密码可看成是密钥分享方案在图像分享领域的一种延伸，除具有完善的安全性外，还具有隐蔽性、简单性、通用性和可靠性。此后，视觉密码学的研究受到广泛关注217。众多研究者对视觉密码模型、构造方法、结构性质、参数的界进行了研究117，获得了较多的研究成果。即使如此，在视觉密码领域还存在一些问题亟待解决。视觉密码现有的多种构造方法基本上都是依据研究者扎实的数学根基获得的经验性解，是特解，有的构造方法还相当复杂。对视觉密码结构性质、参数的界的研究还很不充分，尤其是还没有获得关于像素扩张的最大下界和对比度的最小上界的一般结论。关于视觉密码的最优构造，目前还只针对几种特殊情况进行了研究。本文对基于Naor-Shamir模型的视觉密码的构造方法进行研究，提出了组构造向量的概念，以及基于组构造向量构造成组的基础矩阵的方法。本文获得了组构造向量的通解，进而获得了成组的基础矩阵的通解，实际上也就获得了成组的视觉密码方案的通解。利用组构造向量，任何人只需要简单的数值代入就可以构造出满足要求的视觉密码方案。另外，本文还对d=m的方案和既约的方案进行了讨论。组构造向量的概念及其通解还为视觉密码的进一步研究提供了很有价值的思路。2 组构造向量及其通解2.1 Naor-Shamir模型假设图像仅包含黑点和白点，且每个点分开处理。每个原始像素都出现在n个share中，每个share由m个黑或白的子像素构成。最终结构可以用nm布尔矩阵G=gij来表示，当且仅当第i个share的第j个子像素是黑点时gij =1。当把第i1, i2, ir个share重叠在一起时，看到的效果是G中第i1, i2, ir行“布尔或”的结果，其灰度级是H(V)/m。如果H(V)d则像素为黑，如果H(V)dm则像素为白。(k, n)视觉秘密分享方案包含2个nm布尔矩阵集合C0和C1。要分享白点，用户在C0中随机选择一个矩阵；要分享黑点，用户在C1中随机选择一个矩阵，选择的矩阵定义了n个share的m个子像素的颜色。C0和C1需要满足如下条件：1) 对于C0中的任意S，n行中的任意k行的“或”向量V满足H(V)dm。2) 对于C1中的任意S，n行中的任意k行的“或”向量V满足H(V)d。3) 对于任意i1, i2,iq1,2,n（q0(1)证明在、中任选k行构成的子矩阵D0、Dn中，只有D0、Dnk具有全0列，并且Di的全0列数为（0ink），则任选S0和S1的k行构成2个子矩阵的全0列数之差为，该值必须大于0才能满足对比度条件。证毕。定理2 设S0和S1是一个(k, n)门限视觉密码方案的成组的基础矩阵，它们的组构造向量为x=(x0, , xn)，则有安全性条件=0（0jk1）(2)证明对于任意p行（1pk-1），的该p行中含的组数为（0jin-p+j），又因为在、中的该p行可能含，所以S0和S1的该p行中的组数之差为，根据Naor-Shamir模型的安全性条件，有如下p+1个等式成立：=0（0jp）(3)又因为S0和S1必须具有相同的列数，所以有=0(4)对于式(3)，当p=s时（2sk-1），有=0和=0（0js-1），得=0（0js1）正好是p=s1时的式(3)，则p=s1时的等式隐含在p=s时的等式中，而式(4)相当于p=0时的等式(3)，因此，安全性条件简化为p=k1时的式(3)即为式(2)。证毕。2.4 组构造向量的计算方法定理1和定理2分别给出了组构造向量的对比度条件和安全性条件，其中对比度条件是一个nk+1元不等式，安全性条件是包含k个方程的n元线性方程组，此方程组对应的矩阵形式具有极强的规律性，因此可以推导出组构造向量通解的简易计算方法。将定理2规定的安全性条件改写为矩阵形式，得(5)上述方程组的系数矩阵是行满秩的，可以以x0、x1、xnk为相对自由变元（仅受1个不等式约束），再使用k个方程构成的方程组求解剩余的k个变元xnk+1、xn。再将式(5)等价转换为式(6)(6)这里的矩阵A=aij和矩阵B=bij满足：1) 如果ij，则aij=0；如果ij，则aij=。2) 如果jin2k+1，则bij=；如果jin2k+1，则bij=0。矩阵A是一个上三角矩阵，并且当ij时，aij=；所以，其逆矩阵也是一个上三角矩阵。采用数学归纳法，可得定理3。定理3 设U=，则U=uij。满足：如果ij则uij=0，否则uij=。定理4设S=sij=，则sij= （1ik，1jn-k+1）。证明令h=nk，分2种情况证明= （1ik，1jh+1）即可。情况1：如果ij，证明= =。1) 可以验证，当h=0或j=1时，结论成立。2) 假设当h=v时（v0），结论成立；则当h=v+1时，仅考虑j1的情况，经过数学归纳，可得，等式也成立，情况1得证。情况2：如果i1的情况，经过数学归纳，可得，等式也成立，情况2得证。证毕。根据定理1、定理4及式(6)，可以得到定理5。定理5 (k, n)门限视觉密码方案的组构造向量x有无穷多解(7)3 视觉密码方案3.1 基础矩阵及参数定理6 设x=(x0, xn)是一个(k, n)门限视觉密码方案的一个组构造向量，则可以构造成组的基础矩阵S0和S1如下(8)像素扩张m及对比度分别为(9)S0和S1各取任意k行的“或”向量的Hamming重量分别为h0和h1（h1是方案的阈值d）h0=，d=h1=(10)其中，c0、cn、d0、dn均为非负整数，并且(c0, , cn)(d0, dn)=x。证明S0和S1的构成形式(8)是显然成立的。S0的列数为，S1的列数为，而 =0，则像素扩张m的表达式成立。根据定理1，对比度的表达式及式(10)成立。证毕。如果要构造一个(k, n)门限视觉密码方案，可以首先根据定理5求出一个组构造向量x，再根据定理6选择适当的参数构造基础矩阵S0和S1。在进行机密图像分享处理时，如果坐标为(x, y)的机密像素为p，1in，表示矩阵的随机列置换运算，则M=的第i行作为第i个分享图像的坐标为(x, y)的像素。设n=4，k=3，则组构造向量x=(x0, x1, x2, x3, x4)满足如下条件据此获得一个组构造向量x=(2, 1, 0, 1, -2)，可选c=(2, 0, 0, 1, 0)，d=(0, 1, 0, 0, 2)，进一步获得基础矩阵S0和S1，可以看出，S0包含2组Hamming重量为0的列（c0=2）和1组Hamming重量为3的列（c3=1），S1包含1组Hamming重量为1的列（d1=1）和2组Hamming重量为4的列（d4=2）。3.2 d=m的方案视觉密码方案的对比度参数基本反映叠合图像的视觉效果。一般来说，对比度越大，视觉效果越好，但并非绝对。对比度相差不大的2个视觉密码相比较，叠合的黑像素的灰度级h1/m越大（黑像素越黑），叠合图像的视觉效果越好。下面，对m=d=h1（即黑像素不包含白子像素）的(k, n)视觉密码进行讨论。定理7 一个(k, n)门限视觉密码方案的参数d=m，则其组构造向量x有满足如下条件的无穷多解(11)成组的基础矩阵S0和S1构造如下其中，c0、cn、d0、dn均为非负整数，(c0, , cn)(d0, , dn)=x并且(d0, , dnk)=(0, , 0)。证明根据式(10)，h1=m等价于(d0, dnk)=(0, 0)。如果存在xi0（0ink），则ci0等价于0，符合对比度条件。证毕。3.3 既约的方案定义5 令S0和S1是一个(k, n)门限视觉密码方案的基础矩阵，如果满足如下条件1) 不存在A，使得S0=R0A和S1=R1A；2) 不存在u1，使得S0=uR0和S1=uR1。则称该方案为既约的方案。对于既约的方案，不能有同时存在于S0和S1的列；同时，所有n维向量在S0中的列数和在S1中的列数不能存在大于1的公约数。定理8 既约的(k, n)门限视觉密码方案的组构造向量x有满足如下条件的无穷多解(12)成组的基础矩阵S0和S1构造如下：(13)其中，、是向量x中所有正整数元素，、是向量x中所有负整数元素。证明对于任意y0, 1n，设h=H(y)，如果xh0，则y仅存在于S0；如果xh1使得S0=uR0和S1=uR1，则将R0和R1作为新的基础矩阵。视觉密码具有简单性的突出优点，对已构造好的视觉密码方案的应用几乎不需要密码学知识，但使用已有文献的典型构造方法来构造视觉密码方案并非一个简单的过程。采用本文所提出的构造方法，即使不掌握视觉密码及相关数学知识的人也可以通过简单的代数式求值构造出门限视觉密码方案，构造过程简单且高效。本文所提出的构造方法严格遵循Naor-Shamir模型的安全性条件，因此不存在安全缺陷，在安全性方面与已有构造方法相当。4 结束语本文提出的视觉密码的组构造方法非常简单有效，获得了成组的视觉密码方案的通解，在此基础上，任何人只需要按照公式代入一些数值就可以构造出视觉密码方案的特解。本文还对d=m的方案和既约的方案进行了很有价值的研究。组构造向量的概念及其通解还为视觉密码的进一步研究提供了很有价值的思路。今后，我们还将沿着这个思路继续研究下去，获得多种模型的视觉密码（可以不成组）的通解，并对视觉密码结构性质、参数的界及最优构造展开研究，使视觉密码构造理论更加系统化。参考文献：1NAOR M, SHAMIR A. Visual cryptographyA. Advances in Cryptology- Eurocrypt 94, LNCS 950C. Berlin, Springer-Verlag, 1995. 1-12.2ATENIESE G, BLUNDO C, SANTIS A D, et al. Visual cryptography for general access structuresJ. Information and Computation, 1996, 129(2): 86-106.3ATENIESE G, BLUNDO C, SANTIS A D, et al. Extended capabilities for visual cryptographyJ. Theoretical Computer Science, 2001, 250(1-2): 143-161.4BLUNDO C, DARCO P, SNATIS A D, et al. Contrast optimal threshold visual cryptography schemesJ. SIAM Journal on Discrete Mathematics, 1998, 16(2):224-261.5BLUNDO C, SANTIS A D. Visual cryptography schemes with perfect reconstruction of black pixelsJ. Journal for Computers & Graphics, 1998, 12(4): 449-455.6BLUNDO C, SANTIS A D, NAOR M. Visual cryptography for gray level ImagesJ. Information Processing Letters, 2000, 75(6): 255-259.7YANG C N, LAIH C S. New colored visual secret sharing schemeJ. Designs, Codes, and Cryptography, 2000, 20(3): 325-335.8BLUNDO C, BONIS A D, SANTIS A D. Improved schemes for visual cryptographyJ. Designs, Codes and Cryptography, 2001, 24: 255-278.9TZENG W G, HU C M. A new approach for visual cryptographyJ. Designs, Codes and Cryptography, 2002, 27(3): 207-227.10VIET D Q, KUROSAWA K. Almost ideal contrast visual cryptography with reversingA. LNCS 2964C. 2004. 353-365.11CIMATO S, PRISCO R D, SANTIS A D. Probabilistic visual cryptography schemesJ. The Computer Journal, 2006, 97-107.12SHYU S J. Efficient visual secret sharing scheme for color imagesJ. Pattern Recognition, 2006, 39(5): 866-880.13YANG C N, CHEN T S. Reduce shadow size m aspect ratio invariant visual secret sharing schemes u