一种防共谋欺骗的可视密码方案

齐向东 姜 博 尹乃潇

1(网神信息技术(北京)股份有限公司 北京 100015)2(中国信息通信研究院 北京 100191)

0 引 言

作为一种新的秘密共享技术，可视密码(visual cryptography)由Naor等[1]在1994年欧洲密码学年会上提出。由于其安全性相当于“一次一密”，且特别适用于低计算开销的使用环境，因此一经提出就引起不少学者的重视和研究兴趣[2-9]。自提出以来，可视密码的研究内容主要涉及存取结构、方案参数优化及彩色图像等方面，并取得了丰硕的研究成果。但以上的研究都没有考虑欺骗者的存在，为了进一步丰富和完善可视密码的理论体系，部分学者开始对可视密码中的欺骗问题进行研究。

颜浩等[9]提出了一种可防止欺骗的方案，虽然能够发现一个欺骗者，但该方案在恢复秘密图像时，仍然存在着验证图像的重影，影响秘密图像的恢复。张舒等[10]提出了一种无重影的可防欺骗可视密码方案，可以在不影响秘密恢复的情况下解决验证图像的重影问题。但是，以上两种方案仅可以抵制单独欺骗行为，而对部分参与者联合进行共谋欺骗的行为未作考虑。共谋欺骗是指部分参与者联合起来进行欺骗，特别是针对基于加密矩阵的可视密码方案，欺骗者能够利用已有共享份，在恢复秘密信息时，推测基础，并据此伪造特殊共享份，使其他诚实参与者的共享份叠加后恢复出事先设计好的欺骗信息。

Horng等[11]提出了两种方案，分别通过提供验证图像和增加加密矩阵行数的方法，可以在一定程度上抵抗有多个参与者参加的共谋欺骗行为。王益伟等[12]提出的一种(k′，k，n)可防欺骗可视密码(cheating prevention visual cryptography)方案，能抵抗少于k′人的共谋欺骗。Wu等[13]通过在加密矩阵中增加冗余列，提出了一种可免疫欺骗的(2，n)可视密码方案，阻止了共谋欺骗行为的发生。但该方案的扩展度和对比度较差，有待进一步优化，且局限于(2，n)方案。Praveen等[14]提出了一种可验证的可视密码方案，通过引入一个用于验证的验证方，可以验证每个共享份的真实性，进而有效抵御共谋攻击。

上述方案都通过改进加密矩阵，实现了矩阵的不可推测性，进而达到了防欺骗的目的，但都存在像素扩展度大的不足。针对此问题，本文采用分享过程避免利用统一的加密矩阵的思想，通过对每列像素随机采用不同像素扩展度的加密矩阵进行加密，构造了一种防共谋欺骗可视密码方案。对方案的有效性进行了理论证明和实验验证，结果表明该方案能够实现防共谋欺骗功能，且参与者不需要持有额外的验证共享份，同时优化了恢复图像的像素扩展度，减小了共享份存储和传输开销。

1 基本概念

根据参与者人数可将可视密码中的欺骗行为划分为以下两种情况。

(1) 单个成员的欺骗行为。即在恢复秘密信息时，某个参与者有意出示了一份假的共享份，使共享份在叠加时不能恢复出秘密图像。而且欺骗者在骗取到一定量的共享份后就可以得到秘密信息，从而导致秘密信息的泄露。

(2) 多个成员的共谋欺骗行为。即在普通可视密码方案中，多个参与者在互相叠加共享份得到秘密图像的基础上，可以分析出其余成员的共享份的构成，从而能够制造出一些假的共享份，使假的共享份与其余成员的共享份叠加得到另外的欺骗图像，而非原始秘密图像。

下面举一个共谋欺骗的实例。S0和S1为一普通(2,3)可视密码方案的加密矩阵。

该方案中，当两个共享成员共谋时，就可以推测出第三个成员的共享份，进而伪造共享份进行欺骗。具体过程如图1所示。

图1 一个共谋欺骗的实例

2 方案设计

本文利用扩展度不同的普通(k,n)门限可视密码方案，随机选取不同扩展度的加密矩阵对尺寸为h×w的秘密图像S的每列像素进行加密，实现不同像素扩展度之差的最大值不超过2。这样既能防止推测出其他共享份的内容，同时不影响人类视觉系统的辨别。

2.1 秘密分享

由于加密矩阵是秘密分享的核心，首先介绍加密矩阵的构造方法，如算法1所示。

算法1加密矩阵构造算法

输入：门限值k,n，n≥k≥2

输出：加密矩阵S0,S1

Step1构造扩展度为a的(k,n)门限可视密码方案[1]加密矩阵S0、S1。

Step2构造扩展度为a+1的(k,n)门限可视密码方案加密矩阵M0、M1，满足：

或

Step3构造扩展度为a+2的(k,n)门限可视密码方案加密矩阵B0、B1，满足：

以加密矩阵为核心，设计秘密分享流程如图2所示，具体步骤如算法2所示。

图2 秘密图像分享流程

算法2秘密分享算法

输入：秘密图像S，门限值k,n，n≥k≥2

输出：共享份P1,P2,…,Pn

Step1将秘密图像S的像素逐列标记为：C1,C2,…,Cw。

Step2对第Ci列的像素进行加密，1≤i≤w。

Step3随机选取像素扩展值a+1，a+2。

Step4用对应的加密矩阵对Ci列中的黑白像素逐个进行加密。

Step5判断所有像素列是否都处理完毕，若是则该步骤结束，否则转至Step2。

Step6生成和输出共享份P1,P2,…,Pn，算法结束。

2.2 秘密恢复

秘密恢复如图3所示，依据(k,n)门限原理，从生成的n个共享份P1,P2,…,Pn中任取k个，采用二元或运算进行图像叠加，即可恢复出原秘密图像。

图3 秘密图像恢复示意图

3 方案有效性证明

共谋欺骗成功与否关键在于共谋者根据恢复出的秘密图像及已有共享份能否推断出被欺骗者共享份中黑白子像素的分布。在该方案中，由于对每列像素随机地选取扩展度不同的加密矩阵进行加密，故共谋欺骗者在恢复出秘密图像的基础上，对原秘密图像每一列像素的扩展度是不确知的，则对共享份中原秘密图像每列像素对应的子像素块的位置和大小也是不确知的，因此通过改变共享份中黑白像素的分布来达到欺骗的目的是不可能的。具体证明如下：

不失一般性，指定共谋欺骗者为A1,A2,…,Ak，假设他们联合起来对参与者Ak+1进行欺骗。为达到欺骗的目的，A1,A2,…,Ak必须能够推断出Ak+1所持有共享份Pk+1上黑白子像素的分布。为此，A1,A2,…,Ak必须知道秘密图像S每列像素的像素扩展度以及所采用的加密矩阵。

4 实验分析

以(2，3)方案为例，不妨设参与者人数为3，恢复门限值为2，结合像素扩展度为3和4的(2,3)方案[1]，并与文献[13-14]方案进行对比分析。

首先，分别构造像素扩展度为3、4、5的(2,3)门限可视密码方案加密矩阵如下：

其次，依据2.2节秘密分享与恢复流程，得到实验结果如图4所示。

图4 (2，3)方案的实验结果

像素扩展度是评价可视密码方案的关键指标，对于防欺骗可视密码方案而言，是否需要额外的验证共享份影响方案的存储和传输开销。表1给出了本文方案与现有方案的性能综合对比。

表1 方案性能综合比较

可以看出，文献[13]虽然不需要额外验证共享份，但其像素扩展度最大。本文像素扩展区间为(a+1,a+2)，小于文献[14]的像素扩展度，且参与者不需要持有额外的验证共享份。同时，本文方案基于加密矩阵设计，在保证方案安全性的前提下实现简便。

5 结 语

本文提出了一种防共谋欺骗可视密码方案，该方案以列为单位，随机选取不同扩展度的加密矩阵完成分享过程，通过加入随机性增加共享份生成的不确定性，增加了欺骗者的推测难度，从而达到了防共谋欺骗的目标。本文方案中，共享份中各相邻像素列的扩展度可能不同，导致恢复出来的图像存在一定程度的失真，如何进一步优化恢复效果是后续研究重点。