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

齊向東 姜 博 尹乃瀟

1(網(wǎng)神信息技術(shù)(北京)股份有限公司 北京 100015)2(中國(guó)信息通信研究院 北京 100191)

0 引 言

作為一種新的秘密共享技術(shù)，可視密碼(visual cryptography)由Naor等[1]在1994年歐洲密碼學(xué)年會(huì)上提出。由于其安全性相當(dāng)于“一次一密”，且特別適用于低計(jì)算開(kāi)銷(xiāo)的使用環(huán)境，因此一經(jīng)提出就引起不少學(xué)者的重視和研究興趣[2-9]。自提出以來(lái)，可視密碼的研究?jī)?nèi)容主要涉及存取結(jié)構(gòu)、方案參數(shù)優(yōu)化及彩色圖像等方面，并取得了豐碩的研究成果。但以上的研究都沒(méi)有考慮欺騙者的存在，為了進(jìn)一步豐富和完善可視密碼的理論體系，部分學(xué)者開(kāi)始對(duì)可視密碼中的欺騙問(wèn)題進(jìn)行研究。

顏浩等[9]提出了一種可防止欺騙的方案，雖然能夠發(fā)現(xiàn)一個(gè)欺騙者，但該方案在恢復(fù)秘密圖像時(shí)，仍然存在著驗(yàn)證圖像的重影，影響秘密圖像的恢復(fù)。張舒等[10]提出了一種無(wú)重影的可防欺騙可視密碼方案，可以在不影響秘密恢復(fù)的情況下解決驗(yàn)證圖像的重影問(wèn)題。但是，以上兩種方案僅可以抵制單獨(dú)欺騙行為，而對(duì)部分參與者聯(lián)合進(jìn)行共謀欺騙的行為未作考慮。共謀欺騙是指部分參與者聯(lián)合起來(lái)進(jìn)行欺騙，特別是針對(duì)基于加密矩陣的可視密碼方案，欺騙者能夠利用已有共享份，在恢復(fù)秘密信息時(shí)，推測(cè)基礎(chǔ)，并據(jù)此偽造特殊共享份，使其他誠(chéng)實(shí)參與者的共享份疊加后恢復(fù)出事先設(shè)計(jì)好的欺騙信息。

Horng等[11]提出了兩種方案，分別通過(guò)提供驗(yàn)證圖像和增加加密矩陣行數(shù)的方法，可以在一定程度上抵抗有多個(gè)參與者參加的共謀欺騙行為。王益?zhèn)サ萚12]提出的一種(k′，k，n)可防欺騙可視密碼(cheating prevention visual cryptography)方案，能抵抗少于k′人的共謀欺騙。Wu等[13]通過(guò)在加密矩陣中增加冗余列，提出了一種可免疫欺騙的(2，n)可視密碼方案，阻止了共謀欺騙行為的發(fā)生。但該方案的擴(kuò)展度和對(duì)比度較差，有待進(jìn)一步優(yōu)化，且局限于(2，n)方案。Praveen等[14]提出了一種可驗(yàn)證的可視密碼方案，通過(guò)引入一個(gè)用于驗(yàn)證的驗(yàn)證方，可以驗(yàn)證每個(gè)共享份的真實(shí)性，進(jìn)而有效抵御共謀攻擊。

上述方案都通過(guò)改進(jìn)加密矩陣，實(shí)現(xiàn)了矩陣的不可推測(cè)性，進(jìn)而達(dá)到了防欺騙的目的，但都存在像素?cái)U(kuò)展度大的不足。針對(duì)此問(wèn)題，本文采用分享過(guò)程避免利用統(tǒng)一的加密矩陣的思想，通過(guò)對(duì)每列像素隨機(jī)采用不同像素?cái)U(kuò)展度的加密矩陣進(jìn)行加密，構(gòu)造了一種防共謀欺騙可視密碼方案。對(duì)方案的有效性進(jìn)行了理論證明和實(shí)驗(yàn)驗(yàn)證，結(jié)果表明該方案能夠?qū)崿F(xiàn)防共謀欺騙功能，且參與者不需要持有額外的驗(yàn)證共享份，同時(shí)優(yōu)化了恢復(fù)圖像的像素?cái)U(kuò)展度，減小了共享份存儲(chǔ)和傳輸開(kāi)銷(xiāo)。

1 基本概念

根據(jù)參與者人數(shù)可將可視密碼中的欺騙行為劃分為以下兩種情況。

(1) 單個(gè)成員的欺騙行為。即在恢復(fù)秘密信息時(shí)，某個(gè)參與者有意出示了一份假的共享份，使共享份在疊加時(shí)不能恢復(fù)出秘密圖像。而且欺騙者在騙取到一定量的共享份后就可以得到秘密信息，從而導(dǎo)致秘密信息的泄露。

(2) 多個(gè)成員的共謀欺騙行為。即在普通可視密碼方案中，多個(gè)參與者在互相疊加共享份得到秘密圖像的基礎(chǔ)上，可以分析出其余成員的共享份的構(gòu)成，從而能夠制造出一些假的共享份，使假的共享份與其余成員的共享份疊加得到另外的欺騙圖像，而非原始秘密圖像。

下面舉一個(gè)共謀欺騙的實(shí)例。S0和S1為一普通(2,3)可視密碼方案的加密矩陣。

該方案中，當(dāng)兩個(gè)共享成員共謀時(shí)，就可以推測(cè)出第三個(gè)成員的共享份，進(jìn)而偽造共享份進(jìn)行欺騙。具體過(guò)程如圖1所示。

圖1 一個(gè)共謀欺騙的實(shí)例

2 方案設(shè)計(jì)

本文利用擴(kuò)展度不同的普通(k,n)門(mén)限可視密碼方案，隨機(jī)選取不同擴(kuò)展度的加密矩陣對(duì)尺寸為h×w的秘密圖像S的每列像素進(jìn)行加密，實(shí)現(xiàn)不同像素?cái)U(kuò)展度之差的最大值不超過(guò)2。這樣既能防止推測(cè)出其他共享份的內(nèi)容，同時(shí)不影響人類(lèi)視覺(jué)系統(tǒng)的辨別。

2.1 秘密分享

由于加密矩陣是秘密分享的核心，首先介紹加密矩陣的構(gòu)造方法，如算法1所示。

算法1加密矩陣構(gòu)造算法

輸入：門(mén)限值k,n，n≥k≥2

輸出：加密矩陣S0,S1

Step1構(gòu)造擴(kuò)展度為a的(k,n)門(mén)限可視密碼方案[1]加密矩陣S0、S1。

Step2構(gòu)造擴(kuò)展度為a+1的(k,n)門(mén)限可視密碼方案加密矩陣M0、M1，滿(mǎn)足：

或

Step3構(gòu)造擴(kuò)展度為a+2的(k,n)門(mén)限可視密碼方案加密矩陣B0、B1，滿(mǎn)足：

以加密矩陣為核心，設(shè)計(jì)秘密分享流程如圖2所示，具體步驟如算法2所示。

圖2 秘密圖像分享流程

算法2秘密分享算法

輸入：秘密圖像S，門(mén)限值k,n，n≥k≥2

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

Step1將秘密圖像S的像素逐列標(biāo)記為：C1,C2,…,Cw。

Step2對(duì)第Ci列的像素進(jìn)行加密，1≤i≤w。

Step3隨機(jī)選取像素?cái)U(kuò)展值a+1，a+2。

Step4用對(duì)應(yīng)的加密矩陣對(duì)Ci列中的黑白像素逐個(gè)進(jìn)行加密。

Step5判斷所有像素列是否都處理完畢，若是則該步驟結(jié)束，否則轉(zhuǎn)至Step2。

Step6生成和輸出共享份P1,P2,…,Pn，算法結(jié)束。

2.2 秘密恢復(fù)

秘密恢復(fù)如圖3所示，依據(jù)(k,n)門(mén)限原理，從生成的n個(gè)共享份P1,P2,…,Pn中任取k個(gè)，采用二元或運(yùn)算進(jìn)行圖像疊加，即可恢復(fù)出原秘密圖像。

圖3 秘密圖像恢復(fù)示意圖

3 方案有效性證明

共謀欺騙成功與否關(guān)鍵在于共謀者根據(jù)恢復(fù)出的秘密圖像及已有共享份能否推斷出被欺騙者共享份中黑白子像素的分布。在該方案中，由于對(duì)每列像素隨機(jī)地選取擴(kuò)展度不同的加密矩陣進(jìn)行加密，故共謀欺騙者在恢復(fù)出秘密圖像的基礎(chǔ)上，對(duì)原秘密圖像每一列像素的擴(kuò)展度是不確知的，則對(duì)共享份中原秘密圖像每列像素對(duì)應(yīng)的子像素塊的位置和大小也是不確知的，因此通過(guò)改變共享份中黑白像素的分布來(lái)達(dá)到欺騙的目的是不可能的。具體證明如下：

不失一般性，指定共謀欺騙者為A1,A2,…,Ak，假設(shè)他們聯(lián)合起來(lái)對(duì)參與者Ak+1進(jìn)行欺騙。為達(dá)到欺騙的目的，A1,A2,…,Ak必須能夠推斷出Ak+1所持有共享份Pk+1上黑白子像素的分布。為此，A1,A2,…,Ak必須知道秘密圖像S每列像素的像素?cái)U(kuò)展度以及所采用的加密矩陣。

4 實(shí)驗(yàn)分析

以(2，3)方案為例，不妨設(shè)參與者人數(shù)為3，恢復(fù)門(mén)限值為2，結(jié)合像素?cái)U(kuò)展度為3和4的(2,3)方案[1]，并與文獻(xiàn)[13-14]方案進(jìn)行對(duì)比分析。

首先，分別構(gòu)造像素?cái)U(kuò)展度為3、4、5的(2,3)門(mén)限可視密碼方案加密矩陣如下：

其次，依據(jù)2.2節(jié)秘密分享與恢復(fù)流程，得到實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 (2，3)方案的實(shí)驗(yàn)結(jié)果

像素?cái)U(kuò)展度是評(píng)價(jià)可視密碼方案的關(guān)鍵指標(biāo)，對(duì)于防欺騙可視密碼方案而言，是否需要額外的驗(yàn)證共享份影響方案的存儲(chǔ)和傳輸開(kāi)銷(xiāo)。表1給出了本文方案與現(xiàn)有方案的性能綜合對(duì)比。

表1 方案性能綜合比較

可以看出，文獻(xiàn)[13]雖然不需要額外驗(yàn)證共享份，但其像素?cái)U(kuò)展度最大。本文像素?cái)U(kuò)展區(qū)間為(a+1,a+2)，小于文獻(xiàn)[14]的像素?cái)U(kuò)展度，且參與者不需要持有額外的驗(yàn)證共享份。同時(shí)，本文方案基于加密矩陣設(shè)計(jì)，在保證方案安全性的前提下實(shí)現(xiàn)簡(jiǎn)便。

5 結(jié) 語(yǔ)

本文提出了一種防共謀欺騙可視密碼方案，該方案以列為單位，隨機(jī)選取不同擴(kuò)展度的加密矩陣完成分享過(guò)程，通過(guò)加入隨機(jī)性增加共享份生成的不確定性，增加了欺騙者的推測(cè)難度，從而達(dá)到了防共謀欺騙的目標(biāo)。本文方案中，共享份中各相鄰像素列的擴(kuò)展度可能不同，導(dǎo)致恢復(fù)出來(lái)的圖像存在一定程度的失真，如何進(jìn)一步優(yōu)化恢復(fù)效果是后續(xù)研究重點(diǎn)。