基于區域遞增式彩色視覺密碼的柵格地圖多級分存算法研究

房禮國，付正欣，胡浩，沈剛，郁濱

（信息工程大學，河南 鄭州 450001）

1 引言

地理空間數據作為國家基礎建設、社會經濟發展和科學技術研究的支撐性成果，在經濟建設、國防工程等領域不可或缺，也對國家發展起著不可估量的作用[1]。其中，柵格地理數據是國家空間數據基礎設施的重要內容，也是社會、經濟、物流、通信等領域建設發展過程中的空間位置基礎。

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

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

上述方法在處理時將柵格地圖數據的內容看作一個整體，恢復時也是整體恢復，然而在現實生活中，柵格地圖數據中不同內容反映信息的重要程度往往不同，迫切需要一種方法，依據柵格地圖數據內容信息的敏感程度，對其進行篩選，將涉密信息（如作戰態勢、反恐行動部署、重要基礎設施分布等）進行保護，同時參與解密的共享份數量不同，恢復的柵格地圖數據內容也不同。

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

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

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

2 基本概念

為便于論文后續描述，表1 給出文中所用到的符號及其含義。

表1 文中所用到的符號及其含義

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

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

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

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

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

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

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

圖1 涉密柵格地圖數據分層

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

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

定義3彩色像素的異或運算（⊕）是指像素的顏色值按位進行異或運算，計算式為

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

定義 5[18]若滿足以下3個條件，稱(ΓQual,ΓForb)為強存取結構。

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

2)ΓForb單調遞減，即?F∈ΓForb且F′?F?P，F′∈ΓForb。

3)ΓQual∪ΓForb=2P。

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

推論1[18]對于(k,k)門限存取結構，存在一個完全恢復的XCVCS。

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

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

3 方案設計

由于區域遞增式視覺密碼的像素擴展度與存取結構密切相關，本節首先給出存取結構優化算法，為減小像素擴展度打下基礎，然后設計一種XCVCS，結合圖像分層的思想，構造XRICVCS，最后提出基于XRICVCS 的柵格地圖數據分存模型，并給出具體應用流程。

3.1 存取結構優化算法

定理1 給出了一個完全恢復XCVCS 存在的充要條件，然而，對于任意一個存取結構，并不總是滿足該充要條件。本文考慮先劃分存取結構的Γ0，使劃分后的每個部分滿足定理1 的條件，再對劃分后的每個部分分別構造完全恢復XCVCS。基于上述思想，本節設計了一種完全恢復(k,n)-XCVCS 的構造算法，下面先給出共享份區域劃分的概念。

假設某存取結構的最小授權集合Γ0被劃分成d個子存取結構，每個子存取結構都滿足定理1 的條件。則本節共享份區域劃分方法中，生成的所有共享份均劃分成d個區域，各區域互不相交，且面積與秘密圖像相同，顯然，每個共享份的面積是原始秘密圖像的d倍。互不相交的d個區域相鄰地排列在共享份中，各區域與Γ0劃分出的子存取結構互相對應。

接下來，給出任意通用存取結構的最小授權集合Γ0的劃分算法，如算法1 所示。

算法1最小授權集合Γ0的劃分算法

輸入通用存取結構(ΓQual,ΓForb)的最小授權集合Γ0

輸出d個最小授權集合

步驟1初始設置l=1。

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

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

步驟4若Γ0≠?，則隨機選取Γ0中另一個元素X2，將X2從Γ0中移到Q，否則轉到步驟7。

步驟5若Γ0≠?，則從Γ0中隨機選取另一個元素X3，將X3從Γ0中移到Q，否則轉到步驟7。

步驟6令(ΓQual,ΓForb)為Γ0對應的通用存取結構，如果Γ0中任意奇數個最小授權子集異或得到集合，轉到步驟5；否則將X3從Q移到F中，轉到步驟7。

步驟7令。

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

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

算法1 的步驟6 確保該算法輸出的每個最小授權集合都滿足任意奇數個子集異或得到的集合仍屬于其對應的授權集合，使劃分后的每個最小授權集合滿足定理1，即每個最小授權集合均存在一個完全恢復的XCVCS。

根據算法1 可以將任意存取結構劃分成最小授權集合的組合。

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

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

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

圖2 (3,5)和(3,6)門限存取結構下的共享份區域劃分

3.2 XCVCS 的共享份生成算法

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

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

輸入參與者人數k(k≥2)，大小為a×b的彩色秘密圖像SI

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

步驟1i表示行計數器，令i=0。

步驟2j表示列計數器，令j=0。

步驟3利用0-1 隨機數發生器生成k-1個顏色c1,c2,…,ck-1，每個顏色由24 位0-1 隨機數序列構成。

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

步驟5將c1,c2,…,ck中的顏色依次分配給共享份S1,S2,…,Sk中對應坐標位置的像素。

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

步驟7令i=i+1，若i＜a，轉到步驟2；否則分享流程結束。

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

3.3 XRICVCS 的共享份生成和恢復算法

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

算法3共享份區域生成算法

輸入參與者集合P={1,2,…,n}，解密區域R1?R2?…?Rj對應圖層合成的秘密圖像S，授權集合

輸出共享份

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

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

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

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

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

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

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

輸入參與者集合P={1,2,…,n}，解密區域R1?R2?…?Rj對應的圖層，1≤j≤r，不同區域對應的授權集合，1≤lj≤dj，共d=個存取結構

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

步驟1在d個存取結構中選取未處理過的={Q1,Q2,…,Qt}。

步驟2合并得到授權子集中參與者集合，Q=；禁止子集中參與者集合，F=P-Q。

步驟3運用算法3（共享份區域生成算法）生成授權子集Q中參與者持有的共享份區域，禁止子集F中參與者持有的共享份隨機賦值。得到。

步驟4判斷d個存取結構是否均已處理完成，如果否，則轉到步驟1。

步驟5將每個參與者對應的d個共享份連接生成最終共享份，,1≤k≤n，輸出共享份T1,T2,...,Tn。

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

算法5秘密恢復算法

3.4 有效性證明

視覺密碼方案的有效性包括安全性和對比性兩方面。在本文方案中，安全性是指從禁止子集的共享份中不會得到任何秘密信息，對比性則是指授權子集的共享份通過XOR 運算可以恢復出對應區域的秘密圖像信息。下面從安全性和對比性2 個方面對XRICVCS 的有效性進行證明。

定理2當|X| ＜k時，無法恢復出任何區域的秘密信息。

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

證畢。

通過算法1 將存取結構劃分成d個子存取結構，每個子存取結構都滿足定理1 的條件，即每個子存取結構都存在一個完全恢復的視覺密碼方案，再利用算法2 為每個子存取結構生成對應區域的過渡共享份，然后通過算法3 中的共享份拼接方法，得到最終的共享份。

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

定理3當=j+k-1時，X中的參與者XOR運算標識為X的共享份可以完全恢復區域R1,R2,…,Rj。

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

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

證畢。

3.5 基于視覺密碼的柵格地圖數據多級分存

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

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

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

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

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

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

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

圖3 柵格地圖數據分發過程

柵格地圖數據恢復過程相對簡單，如圖4 所示，不同授權集合的用戶將對應的共享份進行異或疊加即可得到相應的柵格地圖數據。

4 實驗與結果分析

利用第3 節的算法構造(4,6)-XRICVCS，對實際的柵格地圖進行分存實驗，并對實驗結果進行分析，從而驗證方案的可行性和有效性。

4.1 實驗

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

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

圖4 柵格地圖數據恢復過程

圖5 本文(4,5)-XRICVCS 實驗效果

4.2 對比分析

表2 是本文方案與相關他區域遞增式視覺密碼方案的對比結果。

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

2)在方案的構造方法方面，文獻[5-8,13]基于加密矩陣設計，隨著參與者人數的增加，矩陣規模急劇增大，像素擴展度激增。文獻[14]和本文方案利用隨機數對授權集合進行優化，構造方法簡單，同時避免了生成和保存加密矩陣產生的額外開銷。

表2 本文方案與相關方案的對比結果

3)在恢復算法方面，文獻[13-14]和本文方案利用異或運算，由于或運算和異或運算的復雜度階數相等，因此本文方案保持了原有方法計算復雜低的優勢。

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

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

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

表3 文獻[13]與本文方案的存儲開銷比較

5 結束語

本文結合柵格地圖數據分存的應用實際，針對目前RIVCS 的不足，自主設計了一種適合柵格地圖數據分存的XRICVCS，對方案的有效性進行理論證明，并提出基于XRICVCS 的柵格地圖數據分存模型。在實際應用過程中，先對柵格地圖數據分層處理，將其中的涉密數據區分為不同柵格圖層，再對用戶存取結構進行優化，最后利用自主設計的XRICVCS 實現柵格地圖數據的多級分存。實驗表明，本文方案能夠有效解決柵格地圖數據的多級分存問題，在共享份像素擴展度大大降低的同時，實現了柵格地圖數據的完全恢復。