EN中文

地理科学 >

2025 , Vol. 45 >Issue 4: 699 - 710

DOI: https://doi.org/10.13249/j.cnki.sgs.20231149

研究方法与探索

一种矢量地图同态加密域可逆水印方法

  • 吴柏燕 , 1, 2 ,
  • 柳范硕 1, 2 ,
  • 刘曦 , 3, *
展开
  • 1.湖南科技大学地理空间信息技术国家地方联合工程实验室，湖南 湘潭 411201
  • 2.湖南科技大学地球科学与空间信息工程学院，湖南 湘潭 411201
  • 3.地理信息安全与应用湖南省工程研究中心，湖南 长沙 410000
刘曦。E-mail:

吴柏燕（1980—），女，湖南衡阳人，副教授，博士，主要从事地理空间信息安全研究。E-mail:

收稿日期: 2023-08-23

  修回日期: 2023-12-09

  网络出版日期: 2025-04-17

基金资助

地理信息安全与应用湖南省工程研究中心开放课题(HNGISA2024004)

湖南省自然科学基金项目(2025JJ80231)

版权

版权所有，未经授权，不得转载、摘编本刊文章，不得使用本刊的版式设计。
收起

A reversible watermarking algorithm in homomorphic encrypted domain for vector map data

  • Wu Baiyan , 1, 2 ,
  • Liu Fanshuo 1, 2 ,
  • Liu Xi , 3, *
Expand
  • 1. National-local Joint Engineering Laboratory of Geo-spatial Information Technology, Hunan University of Science and Technology, Xiangtan 411201, Hunan, China
  • 2. School of Earth Sciences and Spatial Information Engineering, Hunan University of Science and Technology, Xiangtan 411201, Hunan, China
  • 3. Hunan Engineering Research Center of Geographic Information Security and Application, Changsha 410000, Hunan, China

Received date: 2023-08-23

  Revised date: 2023-12-09

  Online published: 2025-04-17

Supported by

Open Research Project of Hunan Engineering Research Center for Geographical Information Security and Application(HNGISA2024004)

Natural Science Foundation of Hunan Province(2025JJ80231)

Copyright

Copyright reserved © 2025.
Fold

摘要

加密技术可防止非授权用户浏览数据。可逆水印技术可用于对数据的一致性或来源进行认证，并可无损恢复原始数据。针对矢量地图数据的安全保护问题，结合加密技术和可逆水印技术，提出一种基于非对称公钥同态加密的矢量地图加密域可逆水印方法。所提算法，基于加密算法的同态特性，在地图数据密文域中实现了基于改进直方图平移的可逆水印嵌入机制。对3个不同类型的地图数据进行算法实验，实验结果验证了本文算法的可行性和有效性。通过对3个地图数据的水印嵌入性能的分析及与相关明文域和密文域矢量地图可逆水印算法的比较，发现本文算法具有更大的水印容量，更好的水印透明性及更安全的数据加密效果，是一种针对矢量地图的理想的非对称同态加密域可逆水印方案。

关键词： 矢量地图; 可逆水印; 非对称同态加密; 加密域水印; 直方图平移

本文引用格式

吴柏燕 , 柳范硕 , 刘曦 . 一种矢量地图同态加密域可逆水印方法[J]. 地理科学, 2025 , 45(4) : 699 -710 . DOI: 10.13249/j.cnki.sgs.20231149

Abstract

Encryption serves as a safeguard against unauthorized access to data by unauthorized users. Reversible watermarking, on the other hand, can be employed to authenticate the integrity and origin of data, while enabling the lossless recovery of the original data. In light of the security requirements for vector map data protection, this study combines encryption and reversible watermarking techniques to present a novel reversible vector map watermarking algorithm within the asymmetric homomorphic encrypted domain. By capitalizing on the homomorphic characteristics of the encryption algorithm, the proposed approach devises a reversible watermark embedding mechanism grounded in an improved histogram shifting method, which is directly executed within the ciphertext domain. Upon decryption of the ciphertext map with a private key, the watermark can be retrieved from the resultant plaintext map. Subsequently, the original map can be restored through the implementation of inverse histogram shifting. The algorithm is implemented and evaluated using 3 distinct map datasets. The experimental results validate the feasibility and efficacy of the proposed algorithm. Through a comprehensive analysis of the watermarking performance on these 3 map datasets, along with a comparison with existing reversible watermarking algorithms in both the plaintext and ciphertext domains for vector maps, it is demonstrated that the proposed algorithm exhibits a larger payload capacity, higher imperceptibility, and a more secure encryption effect. Thus, it represents a practical and viable reversible watermarking solution in the asymmetric homomorphic encryption domain for vector maps.

Key words： vector map; reversible watermarking; asymmetric homomorphic encryption; watermarking in encrypted domain; histogram shifting

作为地理空间信息的主要载体之一，矢量地图数据在各个领域中得到广泛应用。随着互联网和云计算的发展和普及，矢量地图经常需要在互联网或云端进行传播和存储。网络环境下，矢量地图的安全性问题显得比以往任何时候更加突出和急迫。矢量地图的加密技术和数字水印技术作为保护矢量地图内容安全的2大主要技术[1]，得到大家的广泛关注。根据数字水印在矢量地图保护中的用途，可以大致将矢量地图水印算法分为2类。一类水印算法通过在数据中嵌入鲁棒水印，实现矢量地图数据的版权保护[2-5]；另一类水印算法通过在数据中嵌入脆弱或半脆弱水印，实现对地图数据的来源或内容一致性进行验证[6-9]。本文提出的水印算法属于第二类。随着互联网技术和云计算技术的快速发展和普及，水印隐藏者通常将水印服务部署于第三方服务器或云端。为了在地图数据中嵌入水印，数据所有者先基于数据用户的公钥将地图加密成密文，然后将密文数据发送给第三方水印隐藏者。水印隐藏者直接在密文地图中嵌入水印后将含水印密文地图发送给数据用户。数据用户用自己的私钥解密密文，得到含水印明文地图。对于具有高精度需求的地图数据，在提取水印后还需无损恢复原始地图数据。在上述过程中，涉及到矢量地图的加密域可逆水印算法。
可逆水印算法可以无损恢复原始数据，近年来引起了许多学者的研究兴趣[10-12]。根据水印嵌入机制的不同，已有矢量地图的明文域可逆水印方法大致可分为以下4类。第一类水印方法通过可逆地修改数据的最低有效位来嵌入水印[13]；第二类水印方法，将水印载体空间按一定规则划分成不同水印区域。每个水印区域代表相应的水印信息。水印的嵌入通过将水印载体可逆地映射到相应水印区域来实现[14-21]；第三类水印方法通过直方图平移实现水印的可逆嵌入[22]；第四类水印方法基于差值扩大的机制实现水印的可逆嵌入[23-26]。在这4类可逆水印方法中，基于直方图平移的水印嵌入方法实现简单，更适合在加密域中实现。不过，在基于直方图平移的可逆水印方法中，水印嵌入率往往较低，影响了直方图平移在可逆水印中的广泛应用。本文提出一种同态加密域中的改进直方图平移方法，在加密域中基于直方图平移实现可逆水印嵌入的同时，提升水印嵌入率。
对加密域可逆水印方法的研究，目前主要集中于图像等多媒体数据。对矢量图形，尤其是矢量地图的加密域可逆水印方法的研究还很少见。Jang等[27]提出了一种矢量地图加密标记方法。不过，该方法先标记后加密的特性使得其应用场景受限。Ren等和Li等提出了加密操作和水印操作可交换的密码水印算法[28-31]，可实现在矢量地图的密文域中嵌入鲁棒水印，不过算法着重考虑加密和水印的可交换性，没有考虑水印的可逆性。Peng等[32]提出了一个基于实数可逆映射模型的二维工程图加密域可逆信息隐藏算法。该算法加密图形后，基于实数映射模型实现密文域的可逆信息隐藏，在不可见性、安全性、容量等方面均达到了较好的平衡，但只能在密文域提取水印数据。2020年Peng等[33]又提出了一种二维工程图加密域可逆水印算法。该算法先加密图形节点的极角，然后在加密后的极角中嵌入水印，由此生成了一种加密域可分离的鲁棒可逆水印算法。
上述针对二维矢量图形的加密域水印算法中，图形数据的加密都是基于对称加密，存在密钥管理与传递问题。与已有研究工作不同，本文构建基于非对称同态公钥加密的矢量地图可逆水印算法，实现在地图数据的非对称同态加密域中嵌入可逆水印。

1 矢量地图同态加密域可逆水印方法

非对称同态公钥加密允许不可信第三方在没有私钥的情况下直接对密文进行运算，避免了第三方在运算过程中需要解密密文而造成数据安全问题。Paillier加密算法是一种典型的非对称同态公钥加密算法，通过公钥加密机制保证密文的安全性[34]。利用Paillier加密算法的同态特性，可以在地图数据的密文域中实现可逆水印的嵌入。首先，数据所有者用授权用户的公钥对地图坐标进行加密。并将密文地图发送给第三方水印隐藏者。然后，水印隐藏者基于改进的直方图扩展平移方法，于密文坐标中嵌入水印，形成含水印密文地图。最后，在接收端，授权数据用户用自己的私钥解密密文地图，得到含水印明文地图。从含水印明文地图中提取水印，验证数据来源和数据完整性，并恢复原始地图。算法框架如图1所示。
图1 算法框架示意图

(n,g)为公钥

Fig. 1 The algorithm framework

对所有地图坐标根据小数点后的保留位数进行整数化。设整数化后的地图顶点$ x $坐标序列为$ {x}_{0},\cdots ,{x}_{i},\cdots ,{x}_{N-1} $ ，$ y $坐标序列为$ {y}_{0},\cdots ,{y}_{i},\cdots ,{y}_{N-1} $，N为地图顶点数量。下面以$ x $坐标序列为例，阐述算法的基本原理。对于$ y $坐标序列，算法原理和过程相同。

1.1 地图数据加密

在加密地图数据前，首先生成水印密钥。基于式（1）计算坐标差值。
$ {d}_{i}={x}_{i}-{x}_{i-1} $
式中，$ i=\mathrm{1,2},\cdots ,N-1 $；d是坐标差值。统计差值直方图的峰值，记为$ {d}_{peak} $。记整数化后的地图精度容忍度为$ \tau $。选择一区间阈值，记为$ T $，且满足$ 1\leqslant T\leqslant \tau $。$ \left({d}_{peak},T\right) $保存为水印密钥。
地图坐标的加密基于Paillier加密算法完成。Paillier算法是一种典型的基于RSA的概率公钥密码算法。基于Paillier算法原理，选择2个大素数$ p $和$ q $，然后计算$ n=pq $以及$ \lambda =lcm\left(p-1,q-1\right) $，$ lcm $为求最小公倍数函数。另外，选择随机整数$ g\in {Z}_{{n}^{2}}^{*} $，且满足$ \mathit{gcd}\left[L\left(g^{\lambda}mod\ n^2\right),\ n\right]=1 $，$ gcd $为求最大公约数函数，mod为取模运算符，$ L\left(x\right)=(x-1)/n $ ，则Paillier公钥$ {p}_{k} $为$ \left(n,g\right) $，私钥$ {s}_{k} $为$ \left(p,q,\lambda \right) $。
坐标加密：地图坐标$ {x}_{i}\in {Z}_{n} $，随机数$ {r}_{i}\in {Z}_{n}^{*} $。其中，$ {Z}_{n}=\left\{\mathrm{0,1},\cdots ,n-1\right\} $，$ {Z}_{n}^{*}\subset {Z}_{n} $，由$ {Z}_{n} $中与$ n $互质的整数组成。$ {x}_{i} $对应密文记为$ E\left({x}_{i},{r}_{i}\right) $，给定公钥$ \left(n,g\right) $，密文坐标如式（2）计算。
$ E\left(x_i,r_i\right)=g^{x_i}\times r_i^nmod\ n^2 $
地图数据加密操作由数据所有者执行。生成地图密文后，数据所有者将密文地图和水印密钥$ \left({d}_{peak},T\right) $上传到水印隐藏者。

1.2 密文域可逆水印的嵌入

基于Paillier算法的同态特性，在密文域执行以下数据操作完成水印的可逆嵌入：①计算坐标差值；②差值直方图扩展平移，为水印腾出嵌入空间；③直方图平移嵌入水印；④计算含水印密文坐标。具体原理在下面进行阐述。

1.2.1 Paillier算法的同态特性

密文域可逆水印的嵌入依赖于Paillier算法的同态特性的支持。Paillier算法的同态特性简述如下。给定2个密文$ E\left(x_i\right)=g^{x_i}\times r_i^n\; mod\; n^2 $和$ E\left(x_j\right)=g^{x_j}\times r_j^n\; mod\; n^2 $及常数$ k $，可以得到Paillier的以下同态性质：
$ E\left(x_i\right)\times E\left(x_j\right)=g^{x_i+x_j}\times\left(r_ir_j\right)^n\; mod\; n^2=E\left(x_i+x_j\right) $
$ E\left(x_i\right)\times E\left(x_j\right)^{-1}=g^{x_i-x_j}\times r_{ij}^n\; mod\; n^2=E\left(x_i-x_j\right) $
$ E\left(x_i\right)\times g^k\; mod\; n^2=g^{x_i+k}\times r_i^n\; mod\; n^2=E\left(x_i+k\right) $
$ E\left(x_i\right)^k\; mod\; n^2=g^{kx_i}\times\left(r_i^k\right)^n\; mod\; n^2=E\left(kx_i\right) $

1.2.2 密文域可逆水印的嵌入

本文算法基于密文域差值直方图的扩展平移进行可逆水印的嵌入。水印嵌入主要由以下4步完成。
步骤1：密文域计算坐标差值。
基于式（7）在密文域计算坐标差值，得到坐标差值的密文。$ {x}_{i-1}' $为前一个含水印坐标，$ {x}_{0}'={x}_{0} $。
$ E\left(d_i\right)=E\left(x_i\right)\times E\left(x_{i-1}'\right)^{-1}\; mod\; n^2 $
步骤2：密文域差值直方图扩展平移，腾出水印嵌入空间。
传统直方图平移嵌入水印的方法中，仅对峰值右边的直方图右移一个单位，从而腾出水印嵌入空间（图2b）。这时水印容量等于峰值的频数。为了提升水印容量，本文对峰值所在的特定区间[dpeak−T, dpeak+T]扩大2倍进行扩展，扩展后的对应区间为[dpeak−2T, dpeak+2T]。同时，对区间[dpeak−T, dpeak+T]两边的直方图向外平移$ T $个单位，如图2c所示。这时水印容量等于直方图扩展平移前区间[dpeak−T, dpeak+T−1]上所有直方图的频数之和。
图2 差值直方图扩展平移

Fig. 2 Difference histogram expanding and shifting

在进行直方图扩展平移前，先根据差值密文$ E\left({d}_{i}\right) $判断差值$ {d}_{i} $所在的区间。如果$ {d}_{i} < {d}_{peak}-T $，则将$ {d}_{i} $左移$ T $个单位变为$ {d}_{i}' $；如果$ {d}_{i} > {d}_{peak}+T $，则将$ {d}_{i} $右移$ T $个单位变为$ {d}_{i}' $；如果$ {d}_{i}\in \left[{d}_{peak}-T,{d}_{peak}+T\right] $，则将$ \left({d}_{i}-{d}_{peak}\right) $扩展2倍变为$ {d}_{i}' $。基于3个已知密文E(di)、E(dpeak−T)、E(dpeak+T)，可以在密文域进行$ {d}_{i} $所在区间的判断。因密文域两数大小的比较不是本文的研究重点，这里不对密文域两数大小的比较算法进行详述。
上述密文域差值直方图的扩展平移如式（8）进行，$ {d}_{i}' $的直方图如图2c所示，频数为0的直方图提供了水印嵌入空间。
$ \left\{\begin{array}{l}E\left(d_i'\right)=\left\{\left[E\left(d_i\right)\times E\left(d_{peak}\right)^{-1}\; mod\; n^2\right]^2\; mod\; n^2\right\}\times E\left(d_{peak}\right)\; mod\; n^2\; \ \ \ \ \ \ \ \; d_i\in\left[d_{peak}-T,d_{peak}+T\right] \\E\left(d_i'\right)=E\left(d_i\right)\times E\left(T\right)\; mod\; n^2\ \ \ \ \ \ \ d_i > d_{peak}+T \\E\left(d_i'\right)=E\left(d_i\right)\times E\left(T\right)^{-1}\; mod\; n^2\ \ \ \ \ \ \ d_i < d_{peak}-T\end{array}\right. $
式（8）的密文域操作相当于以下明文域操作。
$ \left\{\begin{array}{l}d_i'=2\left(d_i-d_{peak}\right)+d_{peak}\ \ \ \ \ \ \ \ \ \ \ \ \ d_i\in\left[d_{peak}-T,d_{peak}+T\right] \\ d_i'=d_i+T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \; d_i > d_{peak}+T \\ d_i'=d_i-T\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ d_i < d_{peak}-T\end{array}\right. $
步骤3：密文域直方图平移嵌入可逆水印。
如果$ {d}_{i}'\in [{d}_{peak}-2T,{d}_{peak}+2T) $，则在$ {d}_{i}' $中嵌入水印比特位$ b $（$ b $为0或1），嵌入方法如式（10）所示。
$ \left\{ {\begin{array}{*{20}{l}}{ E\left(d_i''\right)=E\left(d_i'\right)\times g^b\; mod\; n^2 }&{ d'_i\in d_{peak}-2T,\ d_{peak}+2T) }\\{ E\left(d''_i\right)=E\left(d'_i\right) }&{ d'_i\notin[d_{peak}-2T,\ d_{peak}+2T) }\end{array}} \right. $
式（10）的密文域操作相当于以下明文域操作。
$ \left\{\begin{array}{*{20}{l}}d''_i=d'_i+b & \ \ \; d'_i\in\left[d_{peak}-2T,d_{peak}+2T\right) \\ d''_i=d'_i & \ \ \; d'_i\notin\left[d_{peak}-2T,d_{peak}+2T\right)\end{array}\right. $
$ {d}_{i}'' $的直方图如图3所示。标0的直方图含水印位0，标1的直方图含水印位1。
图3 $ {d}_{i}'' $的直方图

统计差值直方图的峰值，记为dpeak，T为区间阈值，下同

Fig. 3 Histogram of $ {d}_{i}'' $

步骤4：密文域生成含水印坐标。
含水印差值最终要隐藏于坐标中，形成含水印坐标。水印隐藏者根据式（12）在密文域完成该操作。
$ E\left(x_i'\right)=E\left(x_{i-1}'\right)\times E\left(d_i''\right)mod\; n^2 $
从$ {d}_{1} $开始，按照上述4个步骤，依序逐个处理每个坐标，最终得到含水印密文地图，从而完成密文域可逆水印的嵌入。

1.3 地图解密、水印提取及原始地图恢复

数据用户获取含水印地图密文和水印密钥$ \left({d}_{peak},T\right) $后，可用自己的私钥对地图数据进行解密，然后利用水印密钥从解密后的地图数据中提取出水印，并可恢复原始地图。给定私钥$ \left(p,q,\lambda \right) $及含水印密文坐标$ E\left({x}_{i}'\right) $，含水印明文坐标基于式（13）计算得到。
$ x_i'=\dfrac{L\left[E\left(x_i'\right)^{\lambda}mod\; n^2\right]}{L\left(g^{\lambda}mod\; n^2\right)}mod\; n^2 $
式中，$ L\left(x\right)=(x-1)/n $。
解密得到含水印明文地图后，水印的提取和原始数据的恢复按以下步骤进行，从$ {x}_{N-1}' $开始，逆序逐个坐标进行处理：
1）计算差值：差值计算公式如式（14）所示。
$ {d}_{i}''={x}_{i}'-{x}_{i-1}' $
2）提取水印：令待提取水印比特位为$ b $，根据水印嵌入原理，$ b $根据式（15）提取。
$ b=\left|d_i''-d_{peak}\right|mod\; 2\; \ \ \ \ \; d_i''\in[d_{peak}-2T,d_{peak}+2T) $
3）原始坐标恢复：首先基于差值直方图扩展平移的逆过程将$ {d}_{i}'' $恢复成原始差值$ {d}_{i} $，恢复方法如式（16）。然后根据式（17）恢复原始坐标。
$ \left\{\begin{array}{l}d_i=d_i''-T\; \ \ \ \; d_i''-d_{peak}\geqslant2T \\ d_i=d_{peak}+floor\left(\dfrac{d_i''-d_{peak}}{2}\right)\; \ \ \ \; 0\leqslant d_i''-d_{peak}\leqslant2T-1 \\ d_i=d_{peak}-ceiling\left(\dfrac{d_{peak}-d_i''}{2}\right)\; \ \ \ -2T\leqslant d_i''-d_{peak}\leqslant-1 \\ d_i=d_i''+T\; \ \ \ d_i''-d_{peak}\leqslant-2T-1\end{array}\right. $
式中，$ floor\left(\right) $为向下取整函数，$ ceiling\left(\right) $为向上取整函数。
$ {x}_{i}={x}_{i-1}'+{d}_{i} $

2 实验结果与分析

所提算法基于地图顶点坐标间的差值直方图的扩展平移，将可逆水印嵌入在顶点坐标间的差值中。因此，地图顶点的空间分布的疏密程度对水印算法的性能有影响。为了分析这种影响及验证所提算法的有效性，选取了顶点空间分布疏密程度显著不同的3个地图数据作为实验数据。所选3个实验数据分别是路网数据、居民地数据和兴趣点POI数据。3个数据的具体情况如表1所示。顶点的疏密程度按X方向和Y方向分别表示。用相对平均间距来表示，即用顶点平均间距与精度容忍度的比值来表示。相对平均间距越小，表示顶点越密集。
表1 3个测试数据集信息

Table 1 Information of 3 test datasets

数据集顶点数比例尺精度容忍度X方向顶点相对间距Y方向顶点相对间距
路网数据1091811∶10万10 m0.8260.538
居民地数据57461∶1万1 m1.9960.818
POI数据10121∶5万5 m6.4714.368
文献[26]提出了一种针对矢量地图数据的明文域可逆水印算法。与本文算法一样，基于地图顶点的坐标差值构建可逆水印模型。因此，后面的算法性能分析特将文献[26]作为比较算法。目前，关于矢量地图加密域可逆水印算法的文献还比较少。文献[33]是最近的针对矢量图形的加密域可逆水印算法。不同的是，文献[33]基于对称加密，可逆水印基于顶点极角的量化索引调制（QIM）方法嵌入。本文算法基于非对称同态加密，可逆水印基于差值直方图扩展平移嵌入。在后面的算法性能分析中，同时将文献[33]作为加密域的对比算法。为了便于比较，将文献[33]中的水印嵌入强度固定为s=1。

2.1 实验结果可视化

3 个实验数据的实验结果如图4所示。实验过程为：先对原始地图（图4a-c）进行加密，得到密文地图（图4d-f）。然后在地图密文域中嵌入可逆水印，得到含水印密文地图（图4g-i）。在地图解密及水印提取阶段，先对含水印地图密文进行解密，得到含水印明文地图（图4j-l）。从含水印明文地图中提取水印并恢复原始地图（图4m-o）。
图4 实验结果可视化

Fig. 4 Visualization of experiment results

2.2 水印容量分析

这里使用嵌入率来衡量和评价水印算法的水印容量。嵌入率如下定义：
$ \mathrm{嵌}\mathrm{入}\mathrm{率}=\dfrac{\mathrm{嵌}\mathrm{入}\mathrm{的}\mathrm{比}\mathrm{特}\mathrm{数}}{\mathrm{总}\mathrm{的}\mathrm{顶}\mathrm{点}\mathrm{数}} $
分别对矢量路网数据、居民地数据和POI数据实施文献[26]、文献[33]和本文算法，统计到的最大水印嵌入率如图5所示。
图5 水印嵌入率比较

Fig. 5 Comparison of embedding rate

从图5中可看出，文献[26]和本文算法的最大水印嵌入率要高于文献[33]。这是因为文献[26]和本文算法在地图顶点的x坐标和y坐标中分别嵌入了水印，相当于每个可嵌入顶点中嵌入了2个比特。而文献[33]是以顶点为单位嵌入水印，每个顶点嵌入一个比特。虽然文献[26]和本文算法都是基于坐标差值嵌入水印，但是本文算法的嵌入率要明显高于文献[26]。
从图5中也可看出，文献[26]对路网数据的水印嵌入率较大，但对POI数据的嵌入率较小（<1）。这是因为水印嵌入在差值小的顶点中。路网数据的顶点间相关性较强，顶点图上分布密度较大，因而顶点间差值绝对值都较小，即差值的峰值直方图靠近零轴。说明水印的可嵌入顶点数量多，因而水印嵌入率大。而POI数据顶点相关性较弱，顶点图上分布较稀疏，因而顶点间差值绝对值都较大，也即差值的峰值直方图远离零轴。说明水印的可嵌入顶点数量少，因而水印嵌入率小。也就是说文献[26]适合顶点图上分布密度较大，顶点差值直方图峰值靠近零轴的地图数据类型。而本文算法对顶点差值直方图峰值的分布没有要求。对顶点图上分布较稀疏，顶点差值直方图峰值远离0值的数据类型（比如本文中的POI数据），也可能拥有较高的水印嵌入率。这说明，相对文献[26]来说，本文算法适用的数据类型更广泛，水印嵌入率更大。

2.3 水印透明性分析

矢量地图水印的透明性可以采用含水印地图与原始地图之间的顶点均方根误差（RMSE）来评价。不过RMSE虽然反映了含水印地图顶点坐标的绝对偏差水平，但仍然不能合理地比较不同比例尺的含水印地图数据的水印透明性。比如，对于2个比例尺分别为1∶100万和1∶1万的含水印地图数据，即使它们的RMSE相同，也不能说这两个含水印地图的水印透明性相同。很明显，具有相同RMSE的1∶100万和1∶1万的含水印地图数据，1∶100万的含水印地图的水印透明性要远远好于1∶1万的含水印地图的水印透明性。因此，为了更合理地比较矢量地图水印的透明性，本文对RMSE进行了改进，定义相对均方根误差（R−RMSE），如式（19）所示。
$ R-RMSE=\sqrt{\dfrac{{\displaystyle\sum} _{i=0}^{N-1}{\left(\dfrac{{d}_{i}}{\tau }\right)}^{2}}{N}} $
式中，$ {d}_{i} $为含水印顶点与原始顶点之间的绝对偏差，$ \tau $为地图精度容忍度。
R−RMSE在RMSE的基础上引入了地图精度容忍度$ \tau $，使得不同比例尺的含水印地图的水印透明性可以通过R−RMSE的大小来比较。R−RMSE越小，水印透明性越好。
将文献[26]、文献[33]及本文算法应用于3个测试数据集，分别计算各含水印地图的R−RMSE。不同水印嵌入率下，3个算法应用于3个测试数据集的R−RMSE的变化曲线如图6所示。
图6 水印透明性比较

Fig. 6 Comparison of watermark imperceptibility

图6显示，文献[26]应用于路网数据的水印透明性要好于其他2个测试数据，应用于POI数据的水印透明性是最差的。这进一步验证了文献[26]更适合顶点图上分布较密集的地图数据类型，对于顶点图上分布较稀疏的POI数据，水印透明性要差很多。从图6可看出，本文算法应用于3个测试数据的水印透明性都要比文献[26]好很多。特别对于POI数据，本文算法得到的水印透明性与路网数据的水印透明性差不多，显著优于文献[26]。这进一步说明本文算法对不同类型的地图数据都有较好的水印性能。文献[33]对3个测试数据的水印透明性都差不多，说明文献[33]的算法其水印性能不受地图特征的影响，与图5反映的算法特点相一致。综合来看，在测试的3个算法中，本文算法在拥有更高的水印嵌入率的同时，拥有更好的水印透明性。

2.4 水印可逆性分析

为了分析3个算法的水印可逆性，计算从含水印明文地图中恢复的地图数据与原始地图数据之间的相对均方根误差（R−RMSE），计算结果如表2所示。
表2 恢复数据与原始数据之间的相对均方根误差

Table 2 R−RMSE between recovered data and original data

数据集文献[26]文献[33]本文算法
路网数据00.748e-130
居民地数据00.843e-130
POI数据00.694e-130
表2中的计算结果显示，文献[26]和本文算法恢复的数据与原始数据的相对均方根误差都为0。文献[33]的相对均方根误差虽然不为0，但非常小，可以认为原始数据也得到了恢复。不过，表2表明文献[26]和本文算法的水印可逆性要好于文献[33]。这是由水印可逆性的机制决定的。在文献[26]和本文算法中，水印嵌入时，原始差值比特位左移一位，腾出低位用于嵌入水印比特。恢复数据时，只要将含水印差值比特位右移回低位即可无损恢复原始数据。在这个过程中没有精度损失。而在文献[33]的算法中，水印的可逆性通过建立可逆映射来实现。即嵌入水印时，根据建立的映射，将原始水印载体映射到含水印的水印载体；恢复数据时，再根据逆映射，将含水印的水印载体映射回原始水印载体，从而恢复原始数据。基于实数的可逆映射，在映射和逆映射的运算过程中，存在浮点数运算的精度损失问题，这也是表2中文献[33]的相对均方根误差不为0的原因。

2.5 加密算法的性能分析

本文算法基于Paillier加密算法对地图数据进行加密。加密算法的效率如表3所示。从表3可看出，虽然Paillier加密算法的时间效率比文献[33]中的HMAC-SHA256加密算法的时间效率低，但仍能满足实际应用需求。
表3 数据加解密运行时间/ms

Table 3 Running time of data encryption and decryption/ms

操作文献[33]算法本文算法
路网数据居民地数据POI数据路网数据居民地数据POI数据
加密4872632203156469234
解密4712362112073563219
Paillier算法的密钥长度达到2 048 bit，密钥空间大小为$ {2}^{2048} $，远远大于密钥空间安全要求$ {2}^{100} $，因此具有较强的抗穷举攻击能力。Paillier加密算法的安全性可参见文献[34]。这里主要对Paillier加密算法应用于矢量地图数据的加密效果进行分析。对于原始明文地图，由于空间要素的空间聚集性，顶点分布往往很不均匀。而对于加密后的密文地图，由于加密的随机性，密文顶点的分布会变得均匀。一般认为，加密后密文顶点分布越均匀，矢量地图的加密效果越好。
为了定量比较密文地图的顶点空间分布的均匀程度，定义顶点的空间分布指数$ \sigma $[28]。σ计算方法如下：以$ m\times n $规则格网覆盖整个矢量图层。然后计算落在每个格网内的顶点数量$ {N}_{i}(i=\mathrm{1,2},\cdots ,m\times n) $。$ \bar {N} $为平均每个格网内的顶点数量。$ \sigma $根据式（20）计算得到。$ \sigma $越小，说明顶点空间分布越均匀。
$ \sigma =\sqrt{\dfrac{{\displaystyle\sum} _{i=1}^{m\times n}{({N}_{i}-\bar {N})}^{2}}{m\times n}} $
分别计算加密前后明文地图和密文地图的顶点空间分布指数$ \sigma $。3个测试数据的计算结果如表4所示。
表4 3个测试数据加密前后顶点空间分布指数σ

Table 4 σ of 3 test datasets before and after encryption

数据集 加密前 加密后 加密后
文献[33] 本文算法
路网数据 1045.64 78.45 39.36
居民地数据 127.32 20.51 13.79
POI数据 46.24 6.32 4.82
从表4容易看出，加密后的顶点空间分布指数与加密前相比，急剧降低。说明加密前不均匀分布的顶点在加密后变成了相当程度的均匀分布。图4也证实了这点。这说明本文加密算法应用于矢量地图具有很好的加密效果。并且从表4也可以看出，本文算法加密后的顶点空间分布指数比文献[33]算法加密后的空间分布指数要低，说明本文算法的加密效果要好于文献[33]的算法。

3 结语

本文提出一种基于Paillier加密算法的2D矢量地图非对称同态加密域可逆水印算法。首先，数据所有者基于明文地图生成水印密钥，并基于Paillier算法，利用数据用户的公钥加密地图顶点坐标，得到密文地图。然后，水印隐藏者基于Paillier的同态性，在密文域中改进传统直方图平移方法，实现在坐标差值中嵌入可逆水印，得到含水印密文地图。水印隐藏者的整个水印嵌入操作都在密文域中实现。最后，数据用户用自己的私钥解密含水印密文地图，得到含水印明文地图。并在明文域中实现水印的提取和原始地图数据的恢复。
本文提出的可逆水印算法属于脆弱水印算法。该算法将水印嵌入在坐标差值中。因地图平移不改变顶点坐标差值的大小，因此算法对地图平移攻击鲁棒。但对地图缩放、旋转等其它会影响顶点坐标差值大小的水印攻击方式，不具有鲁棒性。本文可逆水印算法可用于对地图数据的来源或内容一致性进行验证。
仿真实验结果验证了本文算法的有效性。实验结果的性能分析表明，本文算法与同类对比算法相比，在水印容量及水印透明性方面均有显著提升。与最近提出的矢量图形加密域可逆水印算法[33]相比，本文算法的水印可逆性及数据加密效果更优。并且，与现存算法基于对称加密不同，本文算法基于非对称加密，不存在密钥管理困难问题。在云计算大数据背景下，矢量地图的非对称同态加密域可逆水印技术在地图隐私保护和数据安全上有广阔的应用前景，本文算法具有很好的理论研究意义和实用价值。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
朱长青, 任娜, 徐鼎捷. 地理信息安全技术研究进展与展望[J]. 测绘学报, 2022, 51(6): 1017-1028.

DOI

Zhu Changqing, Ren Na, Xu Dingjie. Geo-information security technology: Progress and prospects. Acta Geodaetica et Cartographica Sinica, 2022, 51(6): 1017-1028.

DOI

[2]
Xi Xu, Zhang Xinchang, Sun Ying et al. Topology-preserving and geometric feature-correction watermarking of vector maps[J]. IEEE Access, 2020, 8: 33428-33441.

DOI

[3]
Yan Haowen, Zhang Liming, Yang Weifang. A normalization-based watermarking scheme for 2D vector map data[J]. Earth Science Informatics, 2017, 10(4): 471-481.

DOI

[4]
Yang Chengsong, Zhu Changqing, Wang Yingying et al. A robust watermarking algorithm for vector geographic data based on QIM and matching detection[J]. Multimedia Tools and Applications, 2020, 79: 30709-30733.

DOI

[5]
Peng Yuwei, Lan Hai, Yue Mingliang. Multipurpose watermarking for vector map protection and authentication[J]. Multimedia Tools and Applications, 2018, 77(6): 7239-7259.

[6]
侯翔, 闵连权, 杨辉. 利用地理坐标网分块的矢量地图脆弱水印方案[J]. 计算机辅助设计与图形学学报, 2018, 30(11): 2042-2048.

Hou Xiang, Min Lianquan, Yang Hui. A fragile watermarking scheme for vector map data using geographic graticule block-wise method. Journal of Computer-Aided Design & Computer Graphics, 2018, 30(11): 2042-2048.

[7]
侯翔, 闵连权, 唐立文. 定位篡改实体组的矢量地图脆弱水印算法[J]. 武汉大学学报(信息科学版), 2020, 45(2): 309-316.

Hou Xiang, Min Lianquan, Tang Liwen. Fragile watermarking algorithm for locating tampered entity groups in vector map data. Geomatics and Information Science of Wuhan University, 2020, 45(2): 309-316.

[8]
Wang Nana, Bian Jilong, Zhang Han. RST invariant fragile watermarking for 2d vector map authentication[J]. International Journal of Multimedia and Ubiquitous Engineering, 2015, 10(4): 155-172.

DOI

[9]
王奇胜, 朱长青, 符浩军. 利用数据点定位的矢量地理数据数字水印算法[J]. 测绘学报, 2013, 42(2): 310-316.

Wang Qisheng, Zhu Changqing, Fu Haojun. The digital watermarking algorithm for vector geographic databased on point positioning. Acta Geodaetica et Cartographica Sinica, 2013, 42(2): 310-316.

[10]
Wang Nana, Zhao Xiangjun, Zhang Han. Block-based reversible fragile watermarking for 2D vector map authentication[J]. International Journal of Digital Crime and Forensics, 2015, 7(3): 60-80.

DOI

[11]
Lin Zixing, Peng Fei, Long Min. A reversible watermarking for authenticating 2D vector graphics based on bionic spider web[J]. Signal Processing: Image Communication, 2017, 57: 134-146.

DOI

[12]
Qiu Yinguo, Duan Hongtao. A novel multi-stage watermarking scheme of vector maps [J]. Multimedia Tools and Applications, 2021, 80(1): 877-897.

[13]
Peng Fei, Chen Li, Long Min. A reversible watermark scheme for 2D vector map based on reversible contrast mapping[J]. Security and Communication Networks, 2013, 6(9): 1117-1125.

DOI

[14]
Wang Nana, Men Chaoguang. Reversible fragile watermarking for locating tampered blocks in 2D vector maps[J]. Multimedia Tools and Applications, 2013, 67(3): 709-739.

DOI

[15]
Wang Nana. Reversible fragile watermarking for locating tampered polylines/polygons in 2D vector maps[J]. International Journal of Digital Crime and Forensics, 2016, 8(1): 1-25.

DOI

[16]
Lin Zixing, Peng Fei, Long Min. A low-distortion reversible watermarking for 2D engineering graphics based on region nesting[J]. IEEE Transactions on Information Forensics and Security, 2018, 13(9): 2372-2382.

DOI

[17]
Peng Fei, Lin Zixing, Zhang Xiang et al. A semi-fragile reversible watermarking for authenticating 2D engineering graphics based on improved region nesting[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2021, 31(1): 411-424.

DOI

[18]
Wang Nana, Zhang Han, Men Chaoguang. A high capacity reversible data hiding method for 2D vector maps based on virtual coordinates[J]. Computer-Aided Design, 2014, 47: 108-117.

DOI

[19]
Xiao Di, Hu Shulei, Zheng Hongying. A high capacity combined reversible watermarking scheme for 2D CAD engineering graphics[J]. Multimedia Tools and Applications, 2015, 74: 2109-2126.

DOI

[20]
Wang Nana. Reversible watermarking for 2D vector maps based on normalized vertices[J]. Multimedia Tools and Applications, 2017, 76: 20935-20953.

DOI

[21]
Wang Nana, Kankanhalli Mohan. 2D vector map fragile watermarking with region location[J]. ACM Transactions on Spatial Algorithms and Systems, 2018, 4(4)12.1-12.25.

[22]
Peng Fei, Liu Yan, Long Min. Reversible watermarking for 2D CAD engineering graphics based on improved histogram shifting[J]. Computer-Aided Design, 2014, 49: 42-50.

DOI

[23]
Wang Xiaotong, Shao Chengyong, Xu Xiaogang et al. Reversible data-hiding scheme for 2D vector maps based on difference expansion[J]. IEEE Transactions on Information Forensics and Security, 2007, 2(3): 311-320.

DOI

[24]
Wang Nana, Men Chaoguang. Reversible fragile watermarking for 2D vector map authentication with localization[J]. Computer-Aided Design, 2012, 44(4): 320-330.

DOI

[25]
Peng Fei, Lei Yuzhou, Long Min et al. A reversible watermarking scheme for two-dimensional CAD engineering graphics based on improved difference expansion[J]. Computer-Aided Design, 2011, 43(8): 1018-1024.

DOI

[26]
孙鸿睿, 李光强, 朱建军. 改进的差值扩张和平移矢量地图可逆水印算法[J]. 武汉大学学报(信息科学版), 2012, 37(8): 1004-1007.

Sun Hongrui, Li Guangqiang, Zhu Jianjun. Improved reversible watermarking algorithm for vector map based on difference expansion and shifting. Geomatics and Information Science of Wuhan University, 2012, 37(8): 1004-1007.

[27]
Jang Bong Joo, Lee Suk Hwan, Lee Eung Joo et al. A crypto-marking method for secure vector map[J]. Multimedia Tools and Applications, 2017, 76(14): 16011-16044.

DOI

[28]
Ren Na, Zhu Changqing, Tong Deyu et al. Commutative encryption and watermarking algorithm based on feature invariants for secure vector map[J]. IEEE Access, 2020, 8: 221481-221493.

DOI

[29]
Ren Na, Tong Deyu, Cui Hanchuan et al. Congruence and geometric feature-based commutative encryption-watermarking method for vector maps[J]. Computers and Geosciences, 2022, 159: 1-14.

[30]
Ren Na, Zhao Ming, Zhu Changqing et al. Commutative encryption and watermarking based on SVD for secure GIS vector data[J]. Earth Science Informatics, 2021, 14: 2249-2263.

DOI

[31]
Li Yu, Zhang Liming, Wang Xiaolong et al. A novel invariant based commutative encryption and watermarking algorithm for vector maps[J]. ISPRS International Journal of Geo-information, 2021, 10(11): 1-18.

[32]
Peng Fei, Lin Zixing, Zhang Xiang et al. Reversible data hiding in encrypted 2D vector graphics based on reversible mapping model for real numbers[J]. IEEE Transactions on Information Forensics and Security, 2019, 14(9): 2400-2411.

DOI

[33]
Peng Fei, Jiang Wenyan, Qi Ying et al. Separable robust reversible watermarking in encrypted 2D vector graphics[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2020, 30(8): 2391-2405.

DOI

[34]
Paillier Pascal. Public-key cryptosystems based on composite degree residuosity classes[C]. Prague: Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques, 1999: 233-238.

Options
文章导航

/

〈 〉