郁 濱 胡 浩 陳武平 沈 剛

?

一種共享份分塊構(gòu)造的異或區(qū)域遞增式視覺(jué)密碼方案

郁 濱①胡 浩*①陳武平②沈 剛①

①(信息工程大學(xué) 鄭州 450001)②(信息保障技術(shù)重點(diǎn)實(shí)驗(yàn)室 北京 100072)

該文依據(jù)授權(quán)子集的個(gè)數(shù)將共享份劃分若干塊，按照共享份分塊構(gòu)造的設(shè)計(jì)思路，結(jié)合(,)異或單秘密視覺(jué)密碼的加密矩陣，構(gòu)造了異或區(qū)域遞增式視覺(jué)密碼的秘密分享與恢復(fù)流程。與現(xiàn)有方案相比，該方案可以實(shí)現(xiàn)解密區(qū)域圖像的完全恢復(fù)，且明顯減小了共享份的大小。

視覺(jué)密碼；區(qū)域遞增；密級(jí)；分塊構(gòu)造；異或運(yùn)算；完全恢復(fù)

1 引言

多秘密視覺(jué)密碼方案(Multi-secret Visual Cryptography Scheme, MVCS)主要用來(lái)分享多幅獨(dú)立的秘密圖像，與MVCS不同，區(qū)域遞增式視覺(jué)密碼方案(Region Incrementing Visual Cryptography Scheme, RIVCS)將一幅秘密圖像劃分為多個(gè)區(qū)域，不同區(qū)域具有不同的圖像，區(qū)域恢復(fù)數(shù)量與參與者人數(shù)有關(guān)，參與者人數(shù)越多，恢復(fù)區(qū)域的數(shù)目越多，只有當(dāng)參與者全部到齊時(shí)才能恢復(fù)所有區(qū)域。在實(shí)際應(yīng)用中，可以依據(jù)圖像內(nèi)容信息的敏感程度，將圖像劃分多個(gè)密級(jí)區(qū)域，對(duì)于高密級(jí)區(qū)域，需要更多參與者共同完成秘密恢復(fù)。因此，利用RIVCS區(qū)域遞增式的解密特性能夠有效保護(hù)秘密圖像中的不同敏感信息，可以廣泛地應(yīng)用于信息的分級(jí)管理、多級(jí)訪問(wèn)控制和身份認(rèn)證等方面，有效拓展了視覺(jué)密碼的應(yīng)用領(lǐng)域[10]。

文獻(xiàn)[5]于2009年首次提出一種存取結(jié)構(gòu)為(2,)的區(qū)域遞增式視覺(jué)密碼方案(OR-based RIVCS, ORIVCS)，將一幅秘密圖像劃分–1個(gè)區(qū)域，利用相應(yīng)的加密矩陣對(duì)各區(qū)域分別分享，共享份以透明膠片作為載體，疊加(相當(dāng)于或運(yùn)算)任意()個(gè)共享份可以恢復(fù)-1個(gè)區(qū)域的秘密信息，但僅限于3, 4和5。文獻(xiàn)[6]建立關(guān)于加密矩陣的線性規(guī)劃模型，設(shè)計(jì)了像素?cái)U(kuò)展度最優(yōu)的(2,)方案，將擴(kuò)展到任意正整數(shù)，但原黑白像素在恢復(fù)圖像中的顏色會(huì)產(chǎn)生反轉(zhuǎn)。文獻(xiàn)[7-9]通過(guò)拼接(,)單秘密或運(yùn)算視覺(jué)密碼方案[11](OR-based Visual Cryptography Scheme, OVCS)的加密矩陣設(shè)計(jì)了一種(,)-ORIVCS，突破了(2,)結(jié)構(gòu)的限制，同時(shí)解決了黑白像素顏色反轉(zhuǎn)失真問(wèn)題，但隨著和的擴(kuò)大，像素?cái)U(kuò)展度迅速增大，對(duì)比度也隨之降低，導(dǎo)致共享份的存儲(chǔ)和傳輸開(kāi)銷(xiāo)急劇增加，且秘密圖像的恢復(fù)效果逐漸模糊。

盡管以上RIVCS在存取結(jié)構(gòu)方面不斷拓展，但像素?cái)U(kuò)展度大、恢復(fù)效果不佳的問(wèn)題沒(méi)有得到有效解決[12]，事實(shí)上，現(xiàn)有方案主要依靠構(gòu)造精簡(jiǎn)的加密矩陣來(lái)降低像素?cái)U(kuò)展度，對(duì)于原始圖像中各區(qū)域的分享本質(zhì)上仍是單秘密OVCS，在秘密恢復(fù)時(shí)，利用達(dá)到恢復(fù)門(mén)限值的區(qū)域被解密，未達(dá)到恢復(fù)門(mén)限值的區(qū)域無(wú)法解密實(shí)現(xiàn)區(qū)域遞增式顯示的效果。因而RIVCS的加密矩陣是OVCS加密矩陣的組合，導(dǎo)致加密矩陣的規(guī)模始終較大。文獻(xiàn)[11]提出的最優(yōu)的(,)-OVCS，像素?cái)U(kuò)展度為，對(duì)比度為。顯然隨著參與者人數(shù)的增加，即使是最優(yōu)方案的參數(shù)也急劇變差，因而OVCS的恢復(fù)不佳直接制約了RIVCS恢復(fù)效果的提高。

為了改善單秘密方案的恢復(fù)效果，文獻(xiàn)[13]將異或運(yùn)算引入視覺(jué)密碼，給出了基于XOR運(yùn)算的視覺(jué)密碼方案(XOR-based VCS, XVCS)的定義，其(,)方案的像素?cái)U(kuò)展度為1且對(duì)比度為1，可以實(shí)現(xiàn)秘密圖像的完全恢復(fù)，遠(yuǎn)遠(yuǎn)優(yōu)于(,)-OVCS。在實(shí)際應(yīng)用中， XOR運(yùn)算在解密時(shí)需要借助于計(jì)算機(jī)或光學(xué)設(shè)備。隨著具有簡(jiǎn)單計(jì)算能力的智能終端如手機(jī)、PAD等的日益普及，為執(zhí)行XOR運(yùn)算提供了一種有效途徑?？紤]到“XOR”和“OR”運(yùn)算的計(jì)算機(jī)復(fù)雜度的階數(shù)相等，因而XOR運(yùn)算可以很好地平衡解密運(yùn)算和方案的參數(shù)。然而，由于XOR運(yùn)算存在反轉(zhuǎn)特性，文獻(xiàn)[17]指出上述基于XOR運(yùn)算的方案只能用于分享一幅秘密圖像，運(yùn)用到現(xiàn)有矩陣拼接設(shè)計(jì)法中，會(huì)產(chǎn)生部分區(qū)域無(wú)法正確恢復(fù)的問(wèn)題，因而不能直接應(yīng)用于RIVCS。

針對(duì)上述問(wèn)題，本文依據(jù)共享份分塊構(gòu)造的設(shè)計(jì)思路，依據(jù)授權(quán)子集的個(gè)數(shù)將共享份劃分成若干部分，分多次生成共享份的不同部分，各部分的構(gòu)造之間獨(dú)立，對(duì)于解密區(qū)域利用單秘密XVCS進(jìn)行構(gòu)造，對(duì)于未解密區(qū)域填充隨機(jī)數(shù)實(shí)現(xiàn)遮蓋，可以解決XOR運(yùn)算不適用于RIVCS的問(wèn)題，在此基礎(chǔ)上，設(shè)計(jì)了一種異或區(qū)域遞增式視覺(jué)密碼方案(XOR-based Region Incrementing Visual Cryptography Scheme, XRIVCS)的秘密分享與恢復(fù)流程，最后對(duì)方案的有效性進(jìn)行了理論證明和實(shí)驗(yàn)驗(yàn)證。

2 基本概念

為方便描述，文中所用符號(hào)及函數(shù)的含義見(jiàn)表1。

表1 本文所用符合及其含義

定義2[12]記參與者集合為，稱(chēng)能夠恢復(fù)秘密圖像的參與者集合為授權(quán)子集，不能恢復(fù)秘密圖像的參與者集合為禁止子集。記表示所有授權(quán)子集的集合，表示所有禁止子集的集合，則,，且,，稱(chēng)為參與者集合之上的存取結(jié)構(gòu)。(,)門(mén)限結(jié)構(gòu)是一類(lèi)特殊的存取結(jié)構(gòu)，滿(mǎn)足,。

定義3[13]稱(chēng)兩個(gè)以布爾矩陣為元素的集合和，組成一個(gè)(,)-XVCS。是分享白像素的映射空間，是分享黑像素的映射空間，在分享白(黑)像素時(shí)從中隨機(jī)選取一個(gè)矩陣，對(duì)應(yīng)個(gè)共享份各自的個(gè)子像素。滿(mǎn)足以下兩個(gè)條件。

條件(1)是對(duì)比性條件，表明當(dāng)參與者人數(shù)等于個(gè)時(shí)，通過(guò)異或運(yùn)算能夠恢復(fù)秘密圖像。條件(2)是安全性條件，表明當(dāng)參與者人數(shù)小于個(gè)時(shí)，得不到秘密圖像的任何信息。表示恢復(fù)圖像中原白像素對(duì)應(yīng)子像素塊的最大漢明重量，表示恢復(fù)圖像中原黑像素對(duì)應(yīng)子像素塊的最小漢明重量。m稱(chēng)為像素?cái)U(kuò)展度，表示1個(gè)原像素被分享成為共享份中的個(gè)子像素，其越小越好。稱(chēng)為對(duì)比度，表示恢復(fù)圖像與原圖像在視覺(jué)上的差別，其越大越好。當(dāng)=1且=1時(shí)，恢復(fù)圖像相對(duì)于原圖像無(wú)失真，稱(chēng)該視覺(jué)密碼方案是完全恢復(fù)的。令為-XVCS的加密矩陣集合，則由所有漢明重量為偶數(shù)的維列向量組成，由所有漢明重量為奇數(shù)的維列向量組成。

定義4 記表示參與者總數(shù)，表示秘密恢復(fù)門(mén)限值，滿(mǎn)足，秘密圖像S劃分了個(gè)區(qū)域。

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

基本思想是分次生成共享份的各個(gè)部分，然后將各部分進(jìn)行拼接得到最終的共享份，拼接的方式不受限制，既可以是行向拼接，也可以是縱向拼接，或者按矩形拼接，各部分的位置和順序也不受限制。秘密恢復(fù)方法與以往RIVCS相同，只需要將滿(mǎn)足條件的共享份異或運(yùn)算就可以恢復(fù)對(duì)應(yīng)密級(jí)區(qū)域。

3.1 秘密分享流程

圖1 共享份生成流程

具體步驟如表2所示。

表2共享份生成算法

3.2 秘密恢復(fù)流程

則在恢復(fù)圖像()中能夠顯示相應(yīng)密級(jí)區(qū)域。

4 有效性證明

引理1[13](,)-XVCS的加密矩陣集合由所有漢明重量為偶數(shù)的維列向量組成，由所有漢明重量為奇數(shù)的維列向量組成。

命題1 若秘密圖像中各密級(jí)區(qū)域大小相等，則(,)-XRIVCS的像素?cái)U(kuò)展度為

證明 本文方案的像素?cái)U(kuò)展度與秘密圖像中各區(qū)域大小所占比例有關(guān)，這里僅考慮各區(qū)域大小相等的情況。設(shè)秘密圖像S的大小為，對(duì)于(,)門(mén)限結(jié)構(gòu)，S被劃分了個(gè)區(qū)域，則單個(gè)區(qū)域的大小為。由秘密分享流程可知，方案依據(jù)授權(quán)子集分塊構(gòu)造共享份的各部分，其中授權(quán)子集生成部分的大小與相等，即。對(duì)于包含了個(gè)參與者的授權(quán)子集，滿(mǎn)足此條件的集合的個(gè)數(shù)為。因此，共享份的像素?cái)U(kuò)展度為

5 實(shí)驗(yàn)與分析

下面給出本文方案的一個(gè)實(shí)例，以(2,3)- XRIVCS為例，依據(jù)方案流程進(jìn)行實(shí)驗(yàn)仿真，秘密圖像S包含兩個(gè)區(qū)域1=和2=。

需要(2, 2)-XVCS, (3, 3)-XVCS的加密矩陣集合。

按照秘密分享與恢復(fù)流程，生成的共享份和恢復(fù)的秘密圖像如圖2所示，分析實(shí)驗(yàn)結(jié)果可知：

圖2 (2, 3)-RIVCS的實(shí)驗(yàn)效果

(1)單個(gè)共享份是雜亂無(wú)章的，無(wú)法看到任何區(qū)域的秘密信息；

(2)任意2個(gè)共享份進(jìn)行XOR運(yùn)算后，區(qū)域1實(shí)現(xiàn)了完全恢復(fù)；

(3)3個(gè)共享份進(jìn)行XOR運(yùn)算后，區(qū)域1和2都實(shí)現(xiàn)了完全恢復(fù)，與預(yù)期結(jié)果相同。

本文方案與其他區(qū)域遞增式視覺(jué)密碼方案的比較見(jiàn)表3和表4。

表3本文方案與文獻(xiàn)[5-8]的像素?cái)U(kuò)展度比較

注：-表示不存在。

表4本文方案與其他區(qū)域遞增式視覺(jué)密碼方案的比較

注：N為否，Y為是，-為無(wú)具體表達(dá)式。

(1)在存取結(jié)構(gòu)方面，文獻(xiàn)[8]和本文方案適用于任意(,)門(mén)限結(jié)構(gòu)，應(yīng)用范圍更豐富。

(2)在顏色失真方面，文獻(xiàn)[7, 8]和本文方案不存在顏色反轉(zhuǎn)失真，因而恢復(fù)圖像可以正確顯示原始圖像顏色的真實(shí)信息。

(3)在恢復(fù)算法方面，本文方案適用于XOR運(yùn)算，由于XOR運(yùn)算不違背視覺(jué)密碼恢復(fù)簡(jiǎn)單性的原則，隨著具有簡(jiǎn)單計(jì)算能力的智能終端的普及，基于XOR運(yùn)算的方案使用將更加方便，應(yīng)用前景更加廣闊。

(4)在完全恢復(fù)方面，本文方案在實(shí)現(xiàn)區(qū)域遞增式顯示效果的前提下，能夠完成各區(qū)域圖案的完全恢復(fù)，因此恢復(fù)效果最佳。

6 結(jié)束語(yǔ)

本文對(duì)區(qū)域遞增式視覺(jué)密碼進(jìn)行了研究，給出了一種解密區(qū)域完全恢復(fù)方案的構(gòu)造方法，并對(duì)方案的有效性進(jìn)行了理論證明。本文方案通過(guò)對(duì)共享份進(jìn)行分塊構(gòu)造，并結(jié)合異或單秘密視覺(jué)密碼方案的加密矩陣，設(shè)計(jì)了秘密圖像的分享和恢復(fù)流程，為區(qū)域遞增式視覺(jué)密碼的研究提供了一條新思路。

參考文獻(xiàn)

[1] 付正欣, 郁濱, 房禮國(guó). 一種新的多秘密分享視覺(jué)密碼[J]. 電子學(xué)報(bào), 2011, 39(3): 712-718.

Fu Zheng-xin, Yu Bin, and Fang Li-guo. A new multi-secret sharing visual cryptography[J]., 2011, 39(3): 712-718.

[2] 付正欣, 郁濱, 房禮國(guó). 基于壓縮算法的存取式多秘密視覺(jué)密碼[J]. 電子與信息學(xué)報(bào), 2013, 35(5): 1055-1062.

Fu Zheng-xin, Yu Bin, and Fang Li-guo. The access-based multi-secret visual cryptography with compression algorithm[J].&, 2013, 35(5): 1055-1062.

[3] Yu B and Shen G. Multi-secret visual cryptography with deterministic contrast[J]., 2014, 72(2): 1867-1886.

[4] Shyu S J and Jiang H W. General constructions for threshold multiple-secret visual cryptography schemes[J]., 2013, 8(5): 733-743.

[5] Wang R Z. Region incrementing visual cryptography[J]., 2009, 16(8): 659-662.

[6] Shyu S J and Jiang H W. Efficient construction for region incrementing visual cryptography[J]., 2012, 22(5): 769-777.

[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, LasVegas, 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.

[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 (LNCS 7809) 449-463.

[10] Chen Y C, Tsai D S, and Horng G. A new authentication based cheating prevention scheme in Naor-Shamir’s visual cryptography[J]., 2012, 23(8): 1225-1233.

[11] Naor M, and Shamir A. Visual cryptography[C]. Proceedings of the Advances in Cryptology-Eurocrypt’94, Berlin, 1995 (LNCS 950): 1-12.

[12] Ateniese G, Blundo C, Santis A D,.. Visual cryptography for general access structures[J]., 1996, 129(2): 86-106.

[13] Tuyls P, Hollmann H D L, Lint J H V,.. XOR-based visual cryptography schemes[J]., 2005, 37(1): 169-186.

[14] Wang D S, Zhang L, Ma N,.. Two secret sharing schemes based on Boolean operations[J]., 2007, 40(10): 2776-2785.

[15] Liu F, Wu C, and Lin X. Step construction of visual cryptography schemes[J]., 2010, 5(1): 27-38.

[16] Wu X and Sun W. Random grid-based visual secret sharing with abilities of OR and XOR decryptions[J]., 2013, 24(1): 48-62.

[17] Yang C and Wang D S. Property analysis of XOR based visual cryptography[J]., 2014, 24(2): 189-197.

XOR-based Region Incrementing Visual Cryptography Scheme with Share Block Construction

Yu Bin①Hu Hao①Chen Wu-ping②Shen Gang①

①(,450001,)②(,100072,)

By designing the block construction for each share, which is divided into several blocks according to the number of qualified sets, the secret sharing and recovering algorithms of the XOR-based region incrementing visual cryptography are designed with the encoding matrices of the (,) XOR-based single secret sharing visual cryptography. Comparing with the existing schemes, the proposed scheme realizes the perfect recovery of decoded regions in secret image, and the sizes of shares are also decreased efficiently.

Visual cryptography; Region incrementing; Security level; Block construction; XOR operation; Perfect recovery

TP309.7

A

1009-5896(2015)08-1978-06

10.11999/JEIT141385

胡浩 wjjhh_908@163.com

2014-10-31收到，2015-02-04改回，2015-05-11網(wǎng)絡(luò)優(yōu)先出版

國(guó)家自然科學(xué)基金(61070086)和信息保障技術(shù)重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金(KJ-13-107)資助課題

郁濱： 男，1964 年生，博士，教授，博士生導(dǎo)師，研究方向?yàn)橐曈X(jué)密碼和網(wǎng)絡(luò)安全.

胡浩： 男，1989 年生，碩士生，研究方向?yàn)橐曈X(jué)密碼.

陳武平： 男，1964 年生，博士，高級(jí)工程師，研究方向?yàn)樾畔踩?

沈剛： 男，1986 年生，博士生，研究方向?yàn)橐曈X(jué)密碼.