房礼国，付正欣，胡浩，沈刚，郁滨

（信息工程大学，河南 郑州 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 实现栅格地图数据的多级分存。实验表明，本文方案能够有效解决栅格地图数据的多级分存问题，在共享份像素扩展度大大降低的同时，实现了栅格地图数据的完全恢复。