盧錦元， 郁 濱

(信息工程大學(xué)電子技術(shù)學(xué)院，河南鄭州 450004)

秘密共享是當(dāng)前密碼技術(shù)研究的一個(gè)重點(diǎn)和熱點(diǎn)，它為密鑰的管理和保護(hù)提供了一種安全的手段，廣泛地應(yīng)用于密鑰分發(fā)、存取控制、安全多方計(jì)算等方面。最早的(k，n)門限秘密共享方案由文獻(xiàn)[1，2]分別獨(dú)立地提出。視覺密碼(visual cryptography)作為一種新的秘密共享技術(shù)由文獻(xiàn)[3]提出，憑借其安全、解密簡單的特點(diǎn)，引起了廣大學(xué)者的研究興趣。文獻(xiàn)[4]將視覺密碼方案擴(kuò)展到通用存取結(jié)構(gòu)，把參與者分為授權(quán)子集和禁止子集2個(gè)集合，使得秘密信息的分享適用于任意參與者組合，大大拓展了其應(yīng)用范圍。此后，視覺密碼的研究主要圍繞參數(shù)優(yōu)化[5，6]、彩色圖像[7，8]及多秘密分享[9，10]等方面展開。

與其它秘密共享技術(shù)一樣，視覺密碼中也存在著欺騙問題。其欺騙行為，按欺騙者身份劃分，有內(nèi)部欺騙和外部欺騙2種;按欺騙者人數(shù)劃分，則有單獨(dú)欺騙和共謀欺騙2種。文獻(xiàn)[11]提出了2種信息驗(yàn)證的方案，用來檢測恢復(fù)圖像是否受到非法篡改，但只適用于(2，2)門限結(jié)構(gòu)。對(duì)于(k，n)結(jié)構(gòu)，可通過結(jié)合(k，n)和(k-1，n)視覺密碼方案，來構(gòu)造防欺騙方案[12]，該方案能夠檢測出k個(gè)參與者中的一個(gè)欺騙者，但其缺陷在于恢復(fù)秘密圖像時(shí)，存在驗(yàn)證圖像的重影。文獻(xiàn)[13]對(duì)其進(jìn)行了改進(jìn)，通過結(jié)合原始(k，n)和改進(jìn)的(k-1，k-1)視覺密碼方案，構(gòu)造了一種更為簡單、消除了驗(yàn)證圖像的重影、可以清晰地恢復(fù)秘密信息的可防欺騙方案，但是沒有考慮多個(gè)欺騙者合作的共謀欺騙情況。

針對(duì)共謀欺騙行為，文獻(xiàn)[14]提出了2種方案。第1種通過增加驗(yàn)證份來實(shí)現(xiàn)各參與者之間的互相檢驗(yàn)，但是每個(gè)參與者除了需要保管自己的共享份外，還得另外保管一個(gè)驗(yàn)證份，增加了參與者的負(fù)擔(dān);第2種方案利用(2，n+l)方案來代替(2，n)方案，使得共謀欺騙者推測其它共享份結(jié)構(gòu)的難度增大，但是該方案要求秘密圖像由2個(gè)互補(bǔ)部分組成，否則無法抵抗特殊欺騙，例如用欺騙圖像B冒充秘密圖像P。文獻(xiàn)[15]構(gòu)造了一種基于非強(qiáng)存取結(jié)構(gòu)的(k′，k，n)可防欺騙視覺密碼方案，該方案能抵抗少于k′人的共謀欺騙，對(duì)更多欺騙者的共謀則無能為力。

另外，由于以上方案都是參與者之間互相檢測，隨著參與者人數(shù)的增多，必然導(dǎo)致方案操作的復(fù)雜，因此文獻(xiàn)[16]提出了一種基于可信第3方的可驗(yàn)證視覺密碼方案，其中可信第3方只負(fù)責(zé)檢驗(yàn)參與者的真?zhèn)?，不參加秘密圖像的恢復(fù)，從而簡化了方案的操作過程。同時(shí)，通過對(duì)每個(gè)共享份進(jìn)行真實(shí)性檢驗(yàn)，能夠有效防止共謀欺騙。但該方案仍存在2點(diǎn)不足:①與以往大多數(shù)視覺密碼方案一樣，利用代數(shù)結(jié)構(gòu)為半群的“或”操作來恢復(fù)圖像，造成相對(duì)差較小，且白像素始終無法完全恢復(fù);②采用將秘密矩陣和驗(yàn)證矩陣并置的方式構(gòu)造基礎(chǔ)矩陣，導(dǎo)致像素?cái)U(kuò)展度增大，恢復(fù)效果不佳。為改善恢復(fù)效果，可改變視覺密碼的代數(shù)結(jié)構(gòu)，用“異或”代替“或”操作，突破半群結(jié)構(gòu)，設(shè)計(jì)基于異或的視覺密碼[17]。文獻(xiàn)[18]利用反轉(zhuǎn)操作對(duì)其進(jìn)行了實(shí)現(xiàn)，設(shè)計(jì)了相對(duì)差趨于理想的方案，該方案在假設(shè)存在一個(gè)黑像素完全恢復(fù)(k，n)方案的條件下，進(jìn)行多輪(k，n)方案共享份生成操作，最終，每個(gè)參與者獲得與操作輪數(shù)相等數(shù)量的共享份，在解密過程中引入反轉(zhuǎn)操作實(shí)現(xiàn)秘密圖像的恢復(fù)。文獻(xiàn)[19]對(duì)其進(jìn)行了改進(jìn)，通過改變共享份的生成方式，能夠在有限輪的操作下，實(shí)現(xiàn)完全理想的相對(duì)差，但仍然存在著各參與者保存共享份數(shù)目過多的不足。

綜上所述，本文提出了一種基于群結(jié)構(gòu)的可驗(yàn)證視覺密碼方案。方案在分享秘密圖像時(shí)，通過改變共享份生成方式，實(shí)現(xiàn)了像素不擴(kuò)展;在分享驗(yàn)證圖像時(shí)，通過引入代數(shù)結(jié)構(gòu)為群的異或操作，實(shí)現(xiàn)了驗(yàn)證圖像的無失真恢復(fù)。實(shí)驗(yàn)結(jié)果表明，本方案的圖像恢復(fù)效果較以前方案有很大改善。

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

首先給出方案定義，其次，結(jié)合定義設(shè)計(jì)方案分享及恢復(fù)流程，最后，對(duì)方案的有效性進(jìn)行證明。

1.1 方案定義

不失一般性，設(shè)參與者集合為P={P1，P2，…，Pn}，可信第3方為Pn+1;秘密圖像S的存取結(jié)構(gòu)為()，其中l(wèi)={Pi1，Pi2，…，Pik};基礎(chǔ)矩陣為C0、C1;生成的共享份為Si(i=1，2，…，n)。第3方擁有與S大小相等的n張驗(yàn)證圖像Vi，生成的驗(yàn)證份為 Ti。記V(X，M)表示矩陣M中X的分量所在行相“或”得到的行向量，H(V)表示V的漢明重量。

(3)參與者Pi與驗(yàn)證方Pn+1可恢復(fù)Vi，形式化描述為Vi=Si⊕Ti，其中，“⊕”表示異或操作。

(4)各參與者及其組合不可恢復(fù)Vi，形式化描述為Sj(j=1，2，…，n)與Vi相互獨(dú)立。

其中，條件(1)、(3)為對(duì)比性條件，保證了恢復(fù)圖像和驗(yàn)證圖像的合法恢復(fù);條件(2)、(4)為安全性條件。條件(2)保證了中參與者得不到秘密圖像的任何信息;條件(4)則保證了在第3方不到場的情況下，無法進(jìn)行驗(yàn)證圖像的恢復(fù)。

1.2 方案流程

該方案中，對(duì)于秘密圖像采用普通視覺密碼方案來分享，例如(k，n)方案，但共享份生成方式有所不同，原方案中是以整個(gè)基礎(chǔ)矩陣為單位來對(duì)像素進(jìn)行分享的，本方案則以基礎(chǔ)矩陣的一列為單位，一個(gè)像素對(duì)應(yīng)一列，不存在像素?cái)U(kuò)展;驗(yàn)證圖像的分享利用異或操作來完成。

1.2.1 分享流程

對(duì)于秘密圖像，分享流程如圖1所示，具體步驟如下:

(1)根據(jù)秘密圖像S中像素點(diǎn)取值c，選擇對(duì)應(yīng)的基礎(chǔ)矩陣C c，將其進(jìn)行隨機(jī)列交換后得到n×m維矩陣M。

(2)隨機(jī)選取M中某一列M j(j=1，2，…，m)，如果該列的第i(i=1，2，…，n)個(gè)元素Mj[i]為0/1，則第i個(gè)共享份對(duì)應(yīng)位置的像素點(diǎn)顏色為白/黑色。

(3)對(duì)原圖像中各像素點(diǎn)逐一重復(fù)步驟(1)、(2)直至所有像素點(diǎn)處理完。

(4)輸出共享份Si。

圖1 秘密圖像分享流程圖

分享驗(yàn)證圖像時(shí)，將各參與者的共享份Si與其驗(yàn)證圖像Vi相異或，生成驗(yàn)證份Ti，即Ti= Si⊕Vi(i=1，2，…，n)，分享流程圖如圖2所示。

圖2 驗(yàn)證圖像分享流程圖

1.2.2 恢復(fù)流程

(1)秘密圖像恢復(fù)。將授權(quán)集中的共享份疊加即可，即S=Si1+Si2+…+Sik，其中，“+”表示或操作。

(2)驗(yàn)證圖像恢復(fù)。將共享份Si與其驗(yàn)證份Ti相異或即可，即Vi=Si⊕Ti(i=1，2，…，n)。

1.3 有效性證明

(1)滿足定義證明。首先，方案中秘密圖像的分享采用的是普通視覺密碼方案，如(k，n)-VCS，滿足定義第(1)、(2)條;其次，方案利用驗(yàn)證份和共享份相異或來恢復(fù)驗(yàn)證圖像，滿足定義第(3)條;最后，各參與者擁有的共享份，在分享驗(yàn)證圖像之前已經(jīng)產(chǎn)生，與驗(yàn)證圖像相互獨(dú)立，從參與者所持有的共享份中得不到驗(yàn)證圖像的任何信息，滿足定義第(4)條。

(2)完全恢復(fù)證明。驗(yàn)證圖像的分享和恢復(fù)均由異或操作來完成，而異或運(yùn)算在二值域上是群結(jié)構(gòu)，其中的每個(gè)元素都存在逆元，它使驗(yàn)證圖像的分享及恢復(fù)過程互逆。分享過程中，當(dāng)Vi為白時(shí)Si和Ti中對(duì)應(yīng)像素點(diǎn)取值相等，否則相反。在驗(yàn)證時(shí)，通過將Si和Ti相異或來恢復(fù)驗(yàn)證圖像，而異或操作中，兩分量相同時(shí)，恢復(fù)全白，反之則恢復(fù)全黑，因此，黑白像素得以完全恢復(fù)。

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

2.1 實(shí)驗(yàn)結(jié)果

不妨設(shè)參與者集合P={P1，P2，P3，P4}，驗(yàn)證方為P5，秘密圖像S的存取結(jié)構(gòu)為(2，4)門限結(jié)構(gòu)，其基礎(chǔ)矩陣為:

圖3 秘密圖像及驗(yàn)證圖像

圖4 各共享份及驗(yàn)證份

圖5 恢復(fù)效果對(duì)比圖

從圖5可以看出，與以往方案相比，本文方案恢復(fù)效果有很大改善。各共享份與原圖像大小相等，不存在像素?cái)U(kuò)展，而且驗(yàn)證圖像實(shí)現(xiàn)了無失真恢復(fù)。

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

對(duì)于視覺密碼而言，像素?cái)U(kuò)展度和相對(duì)差是2個(gè)重要的參數(shù)，可以用來評(píng)價(jià)方案的優(yōu)劣。表1是本文方案與文獻(xiàn)[16]方案的一個(gè)參數(shù)對(duì)比。其中，m、h、l分別為(ΓSQual，ΓSForb)-VCS中像素?cái)U(kuò)展度、黑像素的黑度、白像素的黑度;n為參與者人數(shù)。

表1 本文方案與文獻(xiàn)[16]方案參數(shù)對(duì)比

由表1可知，本文方案在2個(gè)參數(shù)上都有顯著改善，特別是驗(yàn)證圖像的2個(gè)參數(shù)均為最優(yōu)值。

3 結(jié)束語

本文提出了一種基于群結(jié)構(gòu)的可驗(yàn)證視覺密碼方案，該方案以基礎(chǔ)矩陣的列為單位對(duì)秘密圖像的像素進(jìn)行分享，同時(shí)，通過代數(shù)結(jié)構(gòu)為群的異或操作，將驗(yàn)證圖像的分享及恢復(fù)過程設(shè)計(jì)成互逆。仿真實(shí)驗(yàn)表明，本方案具有像素不擴(kuò)展、驗(yàn)證圖像無失真恢復(fù)的特點(diǎn)。

本文初稿首次刊登于《計(jì)算機(jī)技術(shù)與應(yīng)用進(jìn)展?2010》

[1] Sham ir A.H ow to share a secret[J].Comm unicationsof the ACM，1979，22(11):612-613.

[2] Blakley G R.Safeguarding cryptographic keys[C]//Proc A FIPS，1979:313-317.

[3] Naor M，Shamir A.Visual cryptog raphy[J].Lectu re Notes in Compu ter Science:Advances in Cryptology-Eu rocrypt' 94，1995，950:1-12.

[4] A teniese G，Carlo B，Santis A D，et al.V isual cryptography for generalaccess structures[J].Information and Computation，1996，(12):86-106.

[5] Blundo C，De Santis A，Stinson D R.On the con trast in visual cryptog raphy schem es[J].Journal of Cryptography，1999，12(4):261-289.

[6] Fang Liguo，Yu Bin.Research on pixel expansion of(2，n) visual th reshold scheme[C]//1st International Symposium on Pervasive Compu ting and Applications P roceedings(SPCA 06)，Ningbo，China，2006:856-860.

[7] Cimato S，De Prisco R，De Santis A.Optimal colored th reshold visual cryp tography schemes[J].Designs，Codes and C ry ptog raphy，2005，35(3):311-335.

[8] Ng F Y，W ong DS.On the security ofa visual cryptography scheme for color images[J].Pattern Recognition，2009，42 (5):929-940.

[9] Yu B，F(xiàn)u Z X，F(xiàn)ang L G.A modified mu lti-secret sharing visual cryptography scheme[C]//In ternational Conference on Compu tational Intelligence and Security，2008: 351-354.

[10] Fu Z X，Yu B.Research on rotation visual cryptography scheme[C]//2009 In ternational Symposium on Information Engineering and Electronic Commerce，Ternopil，U-kraine，2009:533-536.

[11] 陳玲慧.視覺化密碼之研究及其應(yīng)用[R].臺(tái)北:臺(tái)灣行政院科學(xué)委員會(huì)，1999.

[12] 郭 潔，顏 浩，劉 妍，等.一種可防止欺騙的可視密碼分享方案[J].計(jì)算機(jī)工程，2005，31(6):126-128.

[13] 徐曉輝，郁 濱.無重影的可防欺騙視覺密碼方案[C]//計(jì)算機(jī)技術(shù)與應(yīng)用進(jìn)展(CICAS2007)，2007:1335-1339.

[14] Gw oboa H，Tzungher C，Dushiau T.Cheating in visual cryp tography[J].Designs，Codesand Cryptography，2006，38:219-236.

[15] 王益?zhèn)ィ?濱.一種(k′，k，n)可防欺騙視覺密碼方案[C]//全國第 19屆計(jì)算機(jī)技術(shù)與應(yīng)用學(xué)術(shù)會(huì)議(CACIS08)，2008:492-496.

[16] Yu B，F(xiàn)ang L G，Xu X H.A verifiab le visual cryptography scheme[C]//CIS2008，Suzhou，China，2008:347-350.

[17] TuylsP，H ollmann H D L，Vanlin t J H，et al.XOR-based visual cryptography schemes[J].Designs，Codes and Cryptography，2005，37:169-186.

[18] V iet D Q，Ku rosaw a K.A lmost ideal contrast visual cry ptog raphy w ith reversing[J].Lectu re Notes in Computer Science，2004，2964:353-365.

[19] Cimato S A，Santis D，F(xiàn)errara A L，et al.Idealcon trastvisual cryptog raphy schem es w ith reversing[J].Information Process Letters，2005，93(4):199-206.