盧錦元， 郁 濱

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

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

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

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

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

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

1 方案設計

首先給出方案定義，其次，結合定義設計方案分享及恢復流程，最后，對方案的有效性進行證明。

1.1 方案定義

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

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

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

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

1.2 方案流程

該方案中，對于秘密圖像采用普通視覺密碼方案來分享，例如(k，n)方案，但共享份生成方式有所不同，原方案中是以整個基礎矩陣為單位來對像素進行分享的，本方案則以基礎矩陣的一列為單位，一個像素對應一列，不存在像素擴展;驗證圖像的分享利用異或操作來完成。

1.2.1 分享流程

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

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

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

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

(4)輸出共享份Si。

圖1 秘密圖像分享流程圖

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

圖2 驗證圖像分享流程圖

1.2.2 恢復流程

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

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

1.3 有效性證明

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

(2)完全恢復證明。驗證圖像的分享和恢復均由異或操作來完成，而異或運算在二值域上是群結構，其中的每個元素都存在逆元，它使驗證圖像的分享及恢復過程互逆。分享過程中，當Vi為白時Si和Ti中對應像素點取值相等，否則相反。在驗證時，通過將Si和Ti相異或來恢復驗證圖像，而異或操作中，兩分量相同時，恢復全白，反之則恢復全黑，因此，黑白像素得以完全恢復。

2 實驗與分析

2.1 實驗結果

不妨設參與者集合P={P1，P2，P3，P4}，驗證方為P5，秘密圖像S的存取結構為(2，4)門限結構，其基礎矩陣為:

圖3 秘密圖像及驗證圖像

圖4 各共享份及驗證份

圖5 恢復效果對比圖

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

2.2 實驗分析

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

表1 本文方案與文獻[16]方案參數(shù)對比

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

3 結束語

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

本文初稿首次刊登于《計算機技術與應用進展?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] 陳玲慧.視覺化密碼之研究及其應用[R].臺北:臺灣行政院科學委員會，1999.

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

[13] 徐曉輝，郁 濱.無重影的可防欺騙視覺密碼方案[C]//計算機技術與應用進展(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屆計算機技術與應用學術會議(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.