一種防共謀欺騙的可視密碼方案

齊向東 姜 博 尹乃瀟

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 結 語

本文提出了一種防共謀欺騙可視密碼方案，該方案以列為單位，隨機選取不同擴展度的加密矩陣完成分享過程，通過加入隨機性增加共享份生成的不確定性，增加了欺騙者的推測難度，從而達到了防共謀欺騙的目標。本文方案中，共享份中各相鄰像素列的擴展度可能不同，導致恢復出來的圖像存在一定程度的失真，如何進一步優化恢復效果是后續研究重點。