房禮國(guó)，付正欣，胡浩，沈剛，郁濱

（信息工程大學(xué)，河南 鄭州 450001）

1 引言

地理空間數(shù)據(jù)作為國(guó)家基礎(chǔ)建設(shè)、社會(huì)經(jīng)濟(jì)發(fā)展和科學(xué)技術(shù)研究的支撐性成果，在經(jīng)濟(jì)建設(shè)、國(guó)防工程等領(lǐng)域不可或缺，也對(duì)國(guó)家發(fā)展起著不可估量的作用[1]。其中，柵格地理數(shù)據(jù)是國(guó)家空間數(shù)據(jù)基礎(chǔ)設(shè)施的重要內(nèi)容，也是社會(huì)、經(jīng)濟(jì)、物流、通信等領(lǐng)域建設(shè)發(fā)展過程中的空間位置基礎(chǔ)。

我國(guó)十分重視柵格地圖數(shù)據(jù)的安全問題，并對(duì)此制定配套的法律、法規(guī)，如《中華人民共和國(guó)測(cè)繪法》《地圖管理?xiàng)l例》《地圖審核管理規(guī)定》《測(cè)繪地理信息領(lǐng)域重要信息系統(tǒng)商用密碼應(yīng)用規(guī)劃（2016－2020 年）》等，以上法律、法規(guī)為柵格地圖數(shù)據(jù)的安全保護(hù)提供有力支撐。但是，僅靠法律、法規(guī)很難保證柵格地圖數(shù)據(jù)的安全，急需安全可靠的技術(shù)手段來為柵格地圖數(shù)據(jù)提供安全保護(hù)。

目前，柵格地圖數(shù)據(jù)安全保護(hù)主要采用以下3 種方法。一是基于混沌系統(tǒng)的圖像加密，利用混沌系統(tǒng)的偽隨機(jī)性、初值敏感性和參數(shù)可控性等特點(diǎn)對(duì)圖像加密，當(dāng)維數(shù)低時(shí)，映射參數(shù)和變量較少，算法的抗攻擊能則較差，安全性不高；當(dāng)維數(shù)增加時(shí)，密鑰敏感性增強(qiáng)，安全性得到提高[2]。二是基于位置變換的圖像置亂方法，利用Hilbert 曲線、仿射變換、Arnold 矩陣變換等方法對(duì)像素值位置進(jìn)行變換；利用維吉尼亞算法對(duì)像素的位置進(jìn)行交叉換位操作，使圖像中每個(gè)像素值發(fā)生變化，從而實(shí)現(xiàn)柵格圖像加密[3]。三是基于秘密共享的圖像分存方法，如Naor 等[4]于1994 年提出的視覺密碼方法，恢復(fù)圖像存在像素膨脹和對(duì)比度失真問題。

上述方法在處理時(shí)將柵格地圖數(shù)據(jù)的內(nèi)容看作一個(gè)整體，恢復(fù)時(shí)也是整體恢復(fù)，然而在現(xiàn)實(shí)生活中，柵格地圖數(shù)據(jù)中不同內(nèi)容反映信息的重要程度往往不同，迫切需要一種方法，依據(jù)柵格地圖數(shù)據(jù)內(nèi)容信息的敏感程度，對(duì)其進(jìn)行篩選，將涉密信息（如作戰(zhàn)態(tài)勢(shì)、反恐行動(dòng)部署、重要基礎(chǔ)設(shè)施分布等）進(jìn)行保護(hù)，同時(shí)參與解密的共享份數(shù)量不同，恢復(fù)的柵格地圖數(shù)據(jù)內(nèi)容也不同。

區(qū)域遞增式視覺密碼方案（RIVCS,region incrementing visual cryptography scheme）[5-14]作為視覺密碼[15-17]的一個(gè)重要研究方向，由Wang 等[5]于2009 年首次提出，通過將一幅圖像中的內(nèi)容按秘密等級(jí)高低劃分成多個(gè)區(qū)域。對(duì)每個(gè)區(qū)域單獨(dú)進(jìn)行加密，秘密恢復(fù)時(shí)，區(qū)域逐級(jí)進(jìn)行解密?；謴?fù)的秘密信息的等級(jí)數(shù)和參與者數(shù)目相關(guān)，當(dāng)參與者較多時(shí)，其恢復(fù)出的區(qū)域也較多，只有當(dāng)所有參與者同時(shí)參與時(shí)才可恢復(fù)出全部秘密信息，這種分享策略保護(hù)了秘密圖像中的敏感信息，實(shí)現(xiàn)了對(duì)秘密信息的分級(jí)保護(hù)，可以解決上述問題。

Wang 等[5]將一幅秘密圖像劃分成n-1 個(gè)區(qū)域，疊加任意2≤t≤n個(gè)共享份，由低密級(jí)向高密級(jí)依次顯示t-1 個(gè)區(qū)域的秘密信息，隨著參與者人數(shù)的增多，秘密信息被逐區(qū)域按級(jí)解密，但僅給出了n=3,4,5 時(shí)(2,n)方案的加密基矩陣。Shyu 等[6]通過分析RIVCS 的本質(zhì)，設(shè)計(jì)了一種線性規(guī)劃模型求解(2,n)-RIVCS 的最優(yōu)像素?cái)U(kuò)展度，將n擴(kuò)展到任意正整數(shù)，但模型計(jì)算復(fù)雜度較高，隨著n的增加，方案構(gòu)造花費(fèi)時(shí)間呈指數(shù)級(jí)增長(zhǎng)。以上2 種方案的恢復(fù)圖像均存在反色問題，即在秘密恢復(fù)時(shí)，背景區(qū)域的顏色比圖像的顏色要深，導(dǎo)致恢復(fù)效果不佳，為此，Yang 等[7]通過矩陣拼接的方法設(shè)計(jì)了一種可以糾正反色問題的(k,n)-RIVCS，疊加任意k≤t≤n個(gè)共享份，解密出(t-k+1)級(jí)秘密信息。Li等[8-9]利用整數(shù)線性規(guī)劃方程組求解加密矩陣，構(gòu)造了各解密區(qū)域具有等值相對(duì)差的方案，不但解決了恢復(fù)圖像的反色問題，且與傳統(tǒng)視覺密碼方案更兼容。Anju 等[10]結(jié)合誤差擴(kuò)散和排列編碼方法，設(shè)計(jì)了可應(yīng)用于灰度秘密圖像的區(qū)域遞增視覺密碼方案，但像素?cái)U(kuò)展度較高。為了優(yōu)化像素?cái)U(kuò)展度，Wang等[11]提出了一種基于隨機(jī)柵格的(2,3)多區(qū)域分享視覺密碼方案（RGRIVCS,random-grid-based RIVCS），該方案的設(shè)計(jì)不依賴基矩陣，利用分享函數(shù)fequ、fran和fcom生成共享份，實(shí)現(xiàn)了恢復(fù)圖像不存在像素?cái)U(kuò)展，但僅適用于分享二級(jí)秘密信息。Zhong 等[12]在總結(jié)已有研究成果的基礎(chǔ)上，以(k,k)-RGVCS 為基本單元，設(shè)計(jì)了 2 種(k,n)-RGRIVCS 的構(gòu)造算法，顯著提高了分享秘密的等級(jí)數(shù)。為了進(jìn)一步提高解密區(qū)域圖像的恢復(fù)，Hu 等[13]通過矩陣拼接消減法，實(shí)現(xiàn)了解密圖像中的白像素實(shí)現(xiàn)了完全恢復(fù)，在此基礎(chǔ)上設(shè)計(jì)自適應(yīng)區(qū)域分配算法，將現(xiàn)有方案由(k,n)門限結(jié)構(gòu)拓展到任意存取結(jié)構(gòu)，豐富了現(xiàn)有方案的應(yīng)用場(chǎng)景。為實(shí)現(xiàn)解密區(qū)域的完全恢復(fù)，胡浩等[14]通過為共享份添加身份標(biāo)識(shí)，并結(jié)合隨機(jī)數(shù)，構(gòu)造了單個(gè)參與者持有多個(gè)共享份的異或單秘密視覺密碼方案，但僅適用于黑白二值圖像?？傮w來看，目前區(qū)域遞增式視覺密碼的研究主要針對(duì)二值圖像展開，且普遍存在像素?cái)U(kuò)展度高、對(duì)比度低、存取結(jié)構(gòu)簡(jiǎn)單的問題，無法適用于柵格地圖數(shù)據(jù)的分存。

本文綜合考慮上述因素，采用柵格地圖數(shù)據(jù)分層的思想，將其中的涉密數(shù)據(jù)區(qū)分為不同柵格圖層，依據(jù)柵格地圖中涉密數(shù)據(jù)的密級(jí)高低，關(guān)聯(lián)密級(jí)區(qū)域和其訪問權(quán)限，可以實(shí)現(xiàn)依據(jù)權(quán)限的多級(jí)分存。針對(duì)目前RIVCS 的不足，結(jié)合基于異或的彩色視覺密碼方案（XCVCS,XOR-based color visual cryptography scheme）的設(shè)計(jì)思想，自主設(shè)計(jì)了一種適合柵格地圖數(shù)據(jù)分存的區(qū)域遞增式彩色視覺密碼方案（XRICVCS,XOR-based region incrementing color visual cryptography scheme），在此基礎(chǔ)上提出基于XRICVCS 的柵格地圖數(shù)據(jù)分存模型，并給出了具體應(yīng)用流程，最后對(duì)方案的有效性進(jìn)行了理論證明，同時(shí)針對(duì)實(shí)際柵格地圖數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)驗(yàn)證。本文方案解決了傳統(tǒng)視覺密碼方案存在的像素?cái)U(kuò)展度大、恢復(fù)圖像視覺效果差的問題，在構(gòu)造視覺密碼方案之前先對(duì)用戶存取結(jié)構(gòu)優(yōu)化，再基于異或運(yùn)算實(shí)現(xiàn)，構(gòu)造方法簡(jiǎn)單，同時(shí)避免了生成和保存加密矩陣產(chǎn)生的額外開銷。

2 基本概念

為便于論文后續(xù)描述，表1 給出文中所用到的符號(hào)及其含義。

表1 文中所用到的符號(hào)及其含義

柵格地圖數(shù)據(jù)中常見的涉密要素及其屬性信息包括以下幾類。

1)水庫(kù)庫(kù)容和大壩的高度、河寬、水深、流速等屬性。

2)涉密單位的地理位置、分布特征、編制、部署等。

3)交通樞紐的地理位置、分布和特征，橋梁、隧道的位置、長(zhǎng)度、寬度、高度、性質(zhì)、載重量、運(yùn)輸能力、周圍地形狀況等。

4)地形景觀與特征、圖幅的最高點(diǎn)、主要山峰等制高點(diǎn)的地理位置等。

5)國(guó)防工程的地理位置、分布特征等。

定義1[1]柵格地圖數(shù)據(jù)分層。將柵格地圖數(shù)據(jù)D中的上述涉密要素分為點(diǎn)要素、線要素和面要素3 類，對(duì)各要素的涉密等級(jí)進(jìn)行標(biāo)識(shí)，用1,2,3,…,m表示，數(shù)字越大表明該要素的涉密程度越高。把涉密等級(jí)相同的柵格地圖數(shù)據(jù)D合并為一個(gè)圖層，原數(shù)據(jù)被分為m個(gè)圖層D1,D2,…,Dm，后續(xù)對(duì)m個(gè)圖層進(jìn)行分存處理，如圖1 所示。本文利用ArcGIS生成分層?xùn)鸥駡D，采用矢量數(shù)據(jù)和影像底圖，根據(jù)不同的分層要求將部分矢量圖層和影像底圖導(dǎo)出為柵格圖，如將目標(biāo)圖層＜機(jī)場(chǎng)，航線，道路＞與影像底圖疊加導(dǎo)出為柵格目標(biāo)圖。

圖1 涉密柵格地圖數(shù)據(jù)分層

本文秘密分享在24 位RGB 顏色模型下進(jìn)行，與其他方法不同的是，本文將每個(gè)像素的24 位顏色作為一個(gè)整體，不分區(qū)分RGB 的3 個(gè)通道。本文的像素運(yùn)算使用異或方法，2 個(gè)相同的24 位顏色異或后結(jié)果為·，任意顏色與·異或結(jié)果是該顏色本身。本文中黑色（即24 位全為0 的顏色）用0 表示。

定義2C=(c1,c2,…,)為24 位RGB 模型中所有顏色的集合。

定義3彩色像素的異或運(yùn)算（⊕）是指像素的顏色值按位進(jìn)行異或運(yùn)算，計(jì)算式為

定義4[14]共享份的異或運(yùn)算是指共享份中對(duì)應(yīng)彩色像素的顏色值分別進(jìn)行異或運(yùn)算，即Su⊕Sv=Su(i,j)⊕Sv(i,j)。

定義 5[18]若滿足以下3個(gè)條件，稱(ΓQual,ΓForb)為強(qiáng)存取結(jié)構(gòu)。

1)ΓQual單調(diào)遞增，即?Q∈ΓQual且Q?Q′?P，Q′∈ΓQual。

2)ΓForb單調(diào)遞減，即?F∈ΓForb且F′?F?P，F(xiàn)′∈ΓForb。

3)ΓQual∪ΓForb=2P。

定理 1[18]設(shè)(ΓQual,ΓForb)為在參與者集合P={1,2,…,n}上的一個(gè)強(qiáng)存取結(jié)構(gòu)，其中，最小授權(quán)子集，存在一個(gè)完全恢復(fù)的(Γ0,ΓForb)-XCVCS 的充要條件是滿足∈ΓQual，其中為Γ0中任意奇數(shù)個(gè)最小授權(quán)子集異或所得的集合。

推論1[18]對(duì)于(k,k)門限存取結(jié)構(gòu)，存在一個(gè)完全恢復(fù)的XCVCS。

定義6(k,n)是參與者集合P上的門限結(jié)構(gòu)，設(shè)Ti表示參與者i持有共享份，1 ≤i≤n，記任意參與者集合X=i1,i2,…,ix，函數(shù)R(X)＝為秘密恢復(fù)函數(shù)，表示X中參與者將所持有的共享份進(jìn)行XOR 運(yùn)算，若滿足以下2 個(gè)條件，則存在一個(gè)(k,n)-XRICVCS。

條件1)是安全性條件，確保小于k個(gè)參與者無法得到秘密圖像的任何信息。條件2)是對(duì)比性條件，當(dāng)參與者人數(shù)等于j+k-1 個(gè)時(shí)，最多可以恢復(fù)區(qū)域Rj，若Rj中解密區(qū)域的圖案與原圖像中的圖案一致，稱該方案的解密區(qū)域完全恢復(fù)。

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

由于區(qū)域遞增式視覺密碼的像素?cái)U(kuò)展度與存取結(jié)構(gòu)密切相關(guān)，本節(jié)首先給出存取結(jié)構(gòu)優(yōu)化算法，為減小像素?cái)U(kuò)展度打下基礎(chǔ)，然后設(shè)計(jì)一種XCVCS，結(jié)合圖像分層的思想，構(gòu)造XRICVCS，最后提出基于XRICVCS 的柵格地圖數(shù)據(jù)分存模型，并給出具體應(yīng)用流程。

3.1 存取結(jié)構(gòu)優(yōu)化算法

定理1 給出了一個(gè)完全恢復(fù)XCVCS 存在的充要條件，然而，對(duì)于任意一個(gè)存取結(jié)構(gòu)，并不總是滿足該充要條件。本文考慮先劃分存取結(jié)構(gòu)的Γ0，使劃分后的每個(gè)部分滿足定理1 的條件，再對(duì)劃分后的每個(gè)部分分別構(gòu)造完全恢復(fù)XCVCS?；谏鲜鏊枷耄竟?jié)設(shè)計(jì)了一種完全恢復(fù)(k,n)-XCVCS 的構(gòu)造算法，下面先給出共享份區(qū)域劃分的概念。

假設(shè)某存取結(jié)構(gòu)的最小授權(quán)集合Γ0被劃分成d個(gè)子存取結(jié)構(gòu)，每個(gè)子存取結(jié)構(gòu)都滿足定理1 的條件。則本節(jié)共享份區(qū)域劃分方法中，生成的所有共享份均劃分成d個(gè)區(qū)域，各區(qū)域互不相交，且面積與秘密圖像相同，顯然，每個(gè)共享份的面積是原始秘密圖像的d倍?；ゲ幌嘟坏膁個(gè)區(qū)域相鄰地排列在共享份中，各區(qū)域與Γ0劃分出的子存取結(jié)構(gòu)互相對(duì)應(yīng)。

接下來，給出任意通用存取結(jié)構(gòu)的最小授權(quán)集合Γ0的劃分算法，如算法1 所示。

算法1最小授權(quán)集合Γ0的劃分算法

輸入通用存取結(jié)構(gòu)(ΓQual,ΓForb)的最小授權(quán)集合Γ0

輸出d個(gè)最小授權(quán)集合

步驟1初始設(shè)置l=1。

步驟2令集合Q=F=?。

步驟3隨機(jī)選取Γ0中元素X1，將X1從Γ0移到Q。

步驟4若Γ0≠?，則隨機(jī)選取Γ0中另一個(gè)元素X2，將X2從Γ0中移到Q，否則轉(zhuǎn)到步驟7。

步驟5若Γ0≠?，則從Γ0中隨機(jī)選取另一個(gè)元素X3，將X3從Γ0中移到Q，否則轉(zhuǎn)到步驟7。

步驟6令(ΓQual,ΓForb)為Γ0對(duì)應(yīng)的通用存取結(jié)構(gòu)，如果Γ0中任意奇數(shù)個(gè)最小授權(quán)子集異或得到集合，轉(zhuǎn)到步驟5；否則將X3從Q移到F中，轉(zhuǎn)到步驟7。

步驟7令。

步驟8若F≠?，則令Γ0=F，l=l+1，轉(zhuǎn)到步驟2。

步驟9若F=?，則令d=l，輸出，算法結(jié)束。

算法1 的步驟6 確保該算法輸出的每個(gè)最小授權(quán)集合都滿足任意奇數(shù)個(gè)子集異或得到的集合仍屬于其對(duì)應(yīng)的授權(quán)集合，使劃分后的每個(gè)最小授權(quán)集合滿足定理1，即每個(gè)最小授權(quán)集合均存在一個(gè)完全恢復(fù)的XCVCS。

根據(jù)算法1 可以將任意存取結(jié)構(gòu)劃分成最小授權(quán)集合的組合。

因此，將共享份劃分成3 個(gè)區(qū)域，這3 個(gè)區(qū)域相鄰地分布在共享份中，具體位置如圖2(a)所示。

以(3,6)門限存取結(jié)構(gòu)為例，Γ0={Q?=3}可以被劃分成以下4 個(gè)部分

因此，將一個(gè)共享份劃分成4 個(gè)相鄰的區(qū)域，4 個(gè)區(qū)域在共享份中的位置如圖2(b)所示。

圖2 (3,5)和(3,6)門限存取結(jié)構(gòu)下的共享份區(qū)域劃分

3.2 XCVCS 的共享份生成算法

基于文獻(xiàn)[13]的構(gòu)造方法，提出了一種改進(jìn)的(k,k)-XCVCS 構(gòu)造方法，如算法2 所示。

算法2改進(jìn)的(k,k)-XCVCS

輸入?yún)⑴c者人數(shù)k(k≥2)，大小為a×b的彩色秘密圖像SI

輸出k個(gè)大小為a×b的共享份S1,S2,…,Sk

步驟1i表示行計(jì)數(shù)器，令i=0。

步驟2j表示列計(jì)數(shù)器，令j=0。

步驟3利用0-1 隨機(jī)數(shù)發(fā)生器生成k-1個(gè)顏色c1,c2,…,ck-1，每個(gè)顏色由24 位0-1 隨機(jī)數(shù)序列構(gòu)成。

步驟4計(jì)算ck=c1⊕c2⊕ …⊕ck-1⊕SI(i,j)。

步驟5將c1,c2,…,ck中的顏色依次分配給共享份S1,S2,…,Sk中對(duì)應(yīng)坐標(biāo)位置的像素。

步驟6令j=j+1，若j＜b，轉(zhuǎn)到步驟3；否則轉(zhuǎn)到步驟7。

步驟7令i=i+1，若i＜a，轉(zhuǎn)到步驟2；否則分享流程結(jié)束。

通過該秘密分享過程，對(duì)彩色秘密圖像SI 中的每個(gè)像素顏色進(jìn)行分享，得到共享份S1,S2,…,Sk。

3.3 XRICVCS 的共享份生成和恢復(fù)算法

依據(jù)定義6 可知，當(dāng)參與者人數(shù)增加時(shí)，顯示區(qū)域的數(shù)量隨之增加，對(duì)于區(qū)域R1?R2?…?Rj，1≤j≤r，至少需要k-1+j個(gè)共享份參與恢復(fù)。為減小共享份的像素?cái)U(kuò)展度，利用3.1 節(jié)的存取結(jié)構(gòu)優(yōu)化算法，將所有的最小授權(quán)集合Γ0=分別劃分為，1≤lj≤dj，共劃分為d=個(gè)存取結(jié)構(gòu)。其中，共享份區(qū)域生成算法如算法 3 所示，(k,n)-XRICVCS 的共享份生成過程如算法4 所示，秘密恢復(fù)算法如算法5 所示。

算法3共享份區(qū)域生成算法

輸入?yún)⑴c者集合P={1,2,…,n}，解密區(qū)域R1?R2?…?Rj對(duì)應(yīng)圖層合成的秘密圖像S，授權(quán)集合

輸出共享份

步驟1選取中任意子集Qt，運(yùn)用3.2 節(jié)(k-1+j,k-1+j)-XCVCS 算法生成共享份。

步驟2將Qt從中刪除，，判斷是否為空，如果為空，則算法結(jié)束，輸出共享份。

步驟3判斷中是否存在Qu，Qu中至少有一個(gè)參與者在前面的過程中已分配共享份，如果不存在，則轉(zhuǎn)到步驟1。

步驟4判斷Qu中是否所有參與者已分配共享份，如果是，則轉(zhuǎn)到步驟6。

步驟5根據(jù)部分參與者已分配的共享份，為其他參與者生成共享份。設(shè)Qi={A1,…,Ax,B1,…,By}，(1≤x,y≤n-1)，其中參與者A1,…,Ax的共享份TA1,…,TAx已經(jīng)生成，而參與者B1,...,By的共享份TB1,...,TBy尚未構(gòu)造。隨機(jī)生成與秘密圖像規(guī)模相等的共享份TB1,…,TB(y-1)，最后計(jì)算TBy=S⊕TA1⊕…⊕TAx⊕TB1⊕ …⊕TB(y-1)。

步驟6將Qu從中刪除，，判斷是否為空，如果不為空，則跳轉(zhuǎn)到步驟3；否則算法結(jié)束，輸出共享份。

算法4(k,n)-XRICVCS 的秘密分享算法

輸入?yún)⑴c者集合P={1,2,…,n}，解密區(qū)域R1?R2?…?Rj對(duì)應(yīng)的圖層，1≤j≤r，不同區(qū)域?qū)?yīng)的授權(quán)集合，1≤lj≤dj，共d=個(gè)存取結(jié)構(gòu)

輸出共享份T1，T2,...,Tn

步驟1在d個(gè)存取結(jié)構(gòu)中選取未處理過的={Q1,Q2,…,Qt}。

步驟2合并得到授權(quán)子集中參與者集合，Q=；禁止子集中參與者集合，F(xiàn)=P-Q。

步驟3運(yùn)用算法3（共享份區(qū)域生成算法）生成授權(quán)子集Q中參與者持有的共享份區(qū)域，禁止子集F中參與者持有的共享份隨機(jī)賦值。得到。

步驟4判斷d個(gè)存取結(jié)構(gòu)是否均已處理完成，如果否，則轉(zhuǎn)到步驟1。

步驟5將每個(gè)參與者對(duì)應(yīng)的d個(gè)共享份連接生成最終共享份，,1≤k≤n，輸出共享份T1,T2,...,Tn。

顯然，算法4 生成的n個(gè)共享份T1,T2,...,Tn的大小是秘密圖像的d倍。

算法5秘密恢復(fù)算法

3.4 有效性證明

視覺密碼方案的有效性包括安全性和對(duì)比性兩方面。在本文方案中，安全性是指從禁止子集的共享份中不會(huì)得到任何秘密信息，對(duì)比性則是指授權(quán)子集的共享份通過XOR 運(yùn)算可以恢復(fù)出對(duì)應(yīng)區(qū)域的秘密圖像信息。下面從安全性和對(duì)比性2 個(gè)方面對(duì)XRICVCS 的有效性進(jìn)行證明。

定理2當(dāng)|X| ＜k時(shí)，無法恢復(fù)出任何區(qū)域的秘密信息。

證明設(shè)X=(i1,i2,…,ix)，對(duì)于參與者it持有的共享份，Q∈ΓQ，1≤t≤x＜q，? 為隨機(jī)生成的共享份區(qū)域。由算法4 中共享份賦值方法可知，分為下列2 種情況來考慮。

證畢。

通過算法1 將存取結(jié)構(gòu)劃分成d個(gè)子存取結(jié)構(gòu)，每個(gè)子存取結(jié)構(gòu)都滿足定理1 的條件，即每個(gè)子存取結(jié)構(gòu)都存在一個(gè)完全恢復(fù)的視覺密碼方案，再利用算法2 為每個(gè)子存取結(jié)構(gòu)生成對(duì)應(yīng)區(qū)域的過渡共享份，然后通過算法3 中的共享份拼接方法，得到最終的共享份。

由算法4 的秘密分享流程可知，本文方案共享份由隨機(jī)數(shù)與單秘密視覺密碼[4]共享份拼接而成，因此其安全性基于隨機(jī)數(shù)與單秘密視覺密碼[4]，利用信息熵理論證明了單個(gè)共享份的信息量為零，即通過推理1 可知，3.2 節(jié)每個(gè)子結(jié)構(gòu)都滿足定理2中小于k個(gè)共享份無法恢復(fù)任何秘密信息，即方案的安全性可以保證。

定理3當(dāng)=j+k-1時(shí)，X中的參與者XOR運(yùn)算標(biāo)識(shí)為X的共享份可以完全恢復(fù)區(qū)域R1,R2,…,Rj。

證明由算法4 可知，=j+k-1對(duì)應(yīng)的秘密信息為R1?…?Rj。

顯然，對(duì)于任意X=(i1,…,ij+k-1)，⊕=R1?…?Rj。

證畢。

3.5 基于視覺密碼的柵格地圖數(shù)據(jù)多級(jí)分存

定義7設(shè)基于多級(jí)視覺密碼的柵格地圖數(shù)據(jù)分存模型是一個(gè)五元組M=＜D,Y,P,E,S＞。

1)D=D0∪D1∪D2∪…∪Dm。柵格地圖數(shù)據(jù)的空間要素集合，其中D0表示公開的柵格地圖數(shù)據(jù)集合，D1,D2,…,Dm表示涉密柵格地圖數(shù)據(jù)集合。

2)Y＝D→{D0,D1,D2,…,Dm}，表示從柵格地圖數(shù)據(jù)集合中選取涉密數(shù)據(jù)的過程。

3)P={1,2,…,n}為用戶集合，其冪集記為2P，授權(quán)子集ΓQ中的用戶集合能夠恢復(fù)出柵格地圖數(shù)據(jù)，禁止子集ΓF中的用戶集合不能恢復(fù)柵格地圖數(shù)據(jù)，則ΓQ?2P，ΓF?2P，且ΓQ∩ΓF=?，稱Γ=(ΓQ,ΓF)為用戶集合P之上的存取結(jié)構(gòu)。記Γ0={K∈ΓQ:?K′?K?K′?ΓQ}，稱Γ0為最小授權(quán)集合。

4)E＝D→S表示基于多級(jí)視覺密碼的柵格地圖數(shù)據(jù)分存過程。

5)S={S1,S2,…,Sn}表示柵格地圖數(shù)據(jù)經(jīng)視覺密碼加密后生成的共享份集合。

柵格地圖數(shù)據(jù)分發(fā)過程如圖3 所示。柵格地圖數(shù)據(jù)首先對(duì)柵格地圖數(shù)據(jù)D進(jìn)行涉密數(shù)據(jù)選取，將原始數(shù)據(jù)分為m個(gè)圖層D1,D2,…,Dm；再根據(jù)用戶需求，劃分用戶存取結(jié)構(gòu)，將m個(gè)圖層D1,D2,…,Dm對(duì)應(yīng)到相應(yīng)的存取結(jié)構(gòu)；依據(jù)劃分好的存取結(jié)構(gòu)，選用本文設(shè)計(jì)的XRICVCS 方案對(duì)數(shù)據(jù)進(jìn)行分存處理，生成共享份；最后將共享份分發(fā)給用戶。至此，數(shù)據(jù)分發(fā)過程完畢。

圖3 柵格地圖數(shù)據(jù)分發(fā)過程

柵格地圖數(shù)據(jù)恢復(fù)過程相對(duì)簡(jiǎn)單，如圖4 所示，不同授權(quán)集合的用戶將對(duì)應(yīng)的共享份進(jìn)行異或疊加即可得到相應(yīng)的柵格地圖數(shù)據(jù)。

4 實(shí)驗(yàn)與結(jié)果分析

利用第3 節(jié)的算法構(gòu)造(4,6)-XRICVCS，對(duì)實(shí)際的柵格地圖進(jìn)行分存實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，從而驗(yàn)證方案的可行性和有效性。

4.1 實(shí)驗(yàn)

首先對(duì)柵格地圖的涉密數(shù)據(jù)進(jìn)行選取，此處將原始數(shù)據(jù)分為 2 個(gè)等級(jí)。再對(duì)(4,6)-XCVCS、(5,6)-XCVCS和(6,6)-XCVCS的存取結(jié)構(gòu)進(jìn)行優(yōu)化，得到優(yōu)化后的存取結(jié)構(gòu)={{1234},{1235},{1246},{1256} }，={{1345},{1346},{2345},{2346}}，={{1356},{1456},{2356},{2456}},={{1236},{1245}}，={{3456}}，={{12345},{12346}}，={{12356},{12456} }，={{13456},{23456} }，={{123456}}。最后根據(jù)第3 節(jié)設(shè)計(jì)的方案，利用算法3 和算法4，分別生成9 個(gè)共享份區(qū)域，并為每個(gè)參與者拼接成共享份T1、T2、T3、T4、T5和T6。

實(shí)驗(yàn)效果如圖5 所示。其中，D為原始的柵格地圖，D1、D2和D3為分級(jí)數(shù)據(jù)，T1、T2、T3、T4、T5和T6為生成的共享份。從圖5 中可以看出，任意少于4 個(gè)共享份疊加XOR 后均為無意義的噪聲圖像，不包含D1、D2和D3的任何信息；任意4 個(gè)共享份疊加XOR 得到D1的全部信息；5 個(gè)共享份疊加XOR 得到D1和D2的信息；6 個(gè)共享份疊加XOR得到D1、D2和D3的信息（由于篇幅原因，未列出所有實(shí)驗(yàn)圖片）。實(shí)驗(yàn)表明，本文方案實(shí)現(xiàn)了柵格地圖數(shù)據(jù)的多級(jí)分存。

圖4 柵格地圖數(shù)據(jù)恢復(fù)過程

圖5 本文(4,5)-XRICVCS 實(shí)驗(yàn)效果

4.2 對(duì)比分析

表2 是本文方案與相關(guān)他區(qū)域遞增式視覺密碼方案的對(duì)比結(jié)果。

1)在存取結(jié)構(gòu)方面，文獻(xiàn)[7-8,13-14]和本文方案可應(yīng)用于任意的(k,n)門限結(jié)構(gòu)，應(yīng)用范圍更廣。

2)在方案的構(gòu)造方法方面，文獻(xiàn)[5-8,13]基于加密矩陣設(shè)計(jì)，隨著參與者人數(shù)的增加，矩陣規(guī)模急劇增大，像素?cái)U(kuò)展度激增。文獻(xiàn)[14]和本文方案利用隨機(jī)數(shù)對(duì)授權(quán)集合進(jìn)行優(yōu)化，構(gòu)造方法簡(jiǎn)單，同時(shí)避免了生成和保存加密矩陣產(chǎn)生的額外開銷。

表2 本文方案與相關(guān)方案的對(duì)比結(jié)果

3)在恢復(fù)算法方面，文獻(xiàn)[13-14]和本文方案利用異或運(yùn)算，由于或運(yùn)算和異或運(yùn)算的復(fù)雜度階數(shù)相等，因此本文方案保持了原有方法計(jì)算復(fù)雜低的優(yōu)勢(shì)。

4)在支持的圖像類型方面，僅本文方案支持真彩色圖像，可利用于柵格地圖數(shù)據(jù)的分存。

5)在完全恢復(fù)方面，文獻(xiàn)[13]僅實(shí)現(xiàn)白像素的完全恢復(fù)，文獻(xiàn)[14]實(shí)現(xiàn)黑白二值的完全恢復(fù)，本文方案則實(shí)現(xiàn)真彩圖像的完全恢復(fù)。

6)在存儲(chǔ)開銷方面，表3 給出了文獻(xiàn)[13]與本文方案在像素?cái)U(kuò)展度上的比較，其中，括號(hào)外的像素?cái)U(kuò)展度來自文獻(xiàn)[13]，括號(hào)內(nèi)的像素?cái)U(kuò)展度為本文方案，由表3 可知，本文方案能獲得像素不擴(kuò)展或較小的擴(kuò)展度，以（3,5）方案為例，依據(jù)3.1 節(jié)存取結(jié)構(gòu)劃分算法，Γ0={ {123},{124},{125},{134},{135},{145},{234},{235},{245} }，可以被劃分成3 個(gè)優(yōu)化的存取結(jié)構(gòu)：={ {123},{124},{125} }，={ {134},{234},{135},{235} }和={ {245},{345},{145} }，因此生成的TSE=3，目前文獻(xiàn)[13]給出的最優(yōu)擴(kuò)展度為8，可以看出，本文方案的共享份尺寸較小，有效降低了共享份的存儲(chǔ)和傳輸帶寬開銷。

表3 文獻(xiàn)[13]與本文方案的存儲(chǔ)開銷比較

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

本文結(jié)合柵格地圖數(shù)據(jù)分存的應(yīng)用實(shí)際，針對(duì)目前RIVCS 的不足，自主設(shè)計(jì)了一種適合柵格地圖數(shù)據(jù)分存的XRICVCS，對(duì)方案的有效性進(jìn)行理論證明，并提出基于XRICVCS 的柵格地圖數(shù)據(jù)分存模型。在實(shí)際應(yīng)用過程中，先對(duì)柵格地圖數(shù)據(jù)分層處理，將其中的涉密數(shù)據(jù)區(qū)分為不同柵格圖層，再對(duì)用戶存取結(jié)構(gòu)進(jìn)行優(yōu)化，最后利用自主設(shè)計(jì)的XRICVCS 實(shí)現(xiàn)柵格地圖數(shù)據(jù)的多級(jí)分存。實(shí)驗(yàn)表明，本文方案能夠有效解決柵格地圖數(shù)據(jù)的多級(jí)分存問題，在共享份像素?cái)U(kuò)展度大大降低的同時(shí)，實(shí)現(xiàn)了柵格地圖數(shù)據(jù)的完全恢復(fù)。