基于Paillier同态公钥加密系统的可逆信息隐藏算法

张敏情， 李天雪， 狄富强， 柯 彦

(武警工程大学 密码工程学院 网络与信息安全武警部队重点实验室 陕西 西安 710086)

0 引言

多数隐写算法在嵌入数据后会造成原始载体的永久性失真，这在一些对数据认证要求较高的领域里是不允许的，例如云环境下的隐私保护、军事作战地图传输等[1].而可逆信息隐藏技术(reversible data hiding，RDH)克服了这一缺点，其中基于密文域可逆信息隐藏(reversible data hiding in encrypted domain，RDH-ED)越来越得到人们的重视[2-4].传统的RDH-ED算法基于流加密，通过翻转像素的LSB(least significant bit)嵌入信息，并在解密后利用相邻像素的相关性提取数据和恢复原始载体[5].文献[6-7]实现秘密数据的提取和原始图像恢复的可分离，即合法的接收者可根据密钥的不同进行提取和解密操作.在满足可分离的要求下，基于像素直方图扩展的RDH-ED方法得到广泛关注，数据隐藏阶段使用伪随机密钥选择多个单独像素，通过直方图漂移嵌入秘密数据可有效提高嵌入率.文献[8]提出一种基于图像分块加密的RDH-ED新方案，适用于当前所有基于直方图漂移的可逆信息算法，但是同一个子块中每个像素利用相同的伪随机流进行异或加密，其安全性不高；文献[9]则通过对原始载体进行分块，子块内进行Josephus变换和利用子块直方图漂移隐藏数据，载体加密安全性也不高.

以上RDH-ED算法采用流加密系统进行加密，对密钥管理的难度较大，而且不能对密文信号进行处理.为解决以上问题并保证在原始图像解密后低失真的情况下，提高其嵌入容量，本文提出了一种基于Paillier同态公钥加密系统的RDH-ED方法[10].实验数据显示，标准图像库中图像嵌入数据的最大平均嵌入率为0.128 bpp，而且在直接解密情况下可以无损恢复原始图像，提取正确率达100%.

1 相关知识

1.1 Paillier同态加密系统

c=gmrnmodn2,

本文算法将利用定理1提取加密域中嵌入的数据.

1.2 游程编码压缩

游程编码压缩(run length coding)是一种与资料性质无关的无损数据压缩技术，其原理是用一个整数对(L，R)表示一个游程序列，游程序列是指连续出现且相等的数字序列.在对图像数据进行编码时，沿一定方向排列的具有相同灰度值的像素可看成是连续符号，用字串代替这些连续符号.定长RLC是指游程序列长度R所占用的比特位数固定，RLC-u′位元表示法是定长RLC的一种无损压缩方法，即利用u′个比特位来储存整数，例如u′=8，对连续的二进制序列11111100000000000001100000进行RLC-u′位元表示法压缩，结果为6 180 502 150.本文将利用RLC-u′位元表示法压缩灰度图像的高位位平面H.

2 基于同态公钥加密系统的可逆信息隐藏算法

2.1 算法总体框架

图1 基于同态公钥加密系统的可逆信息隐藏算法框架Fig.1 Framework of reversible data hiding algorithm based on homomorphic public key encryption system

2.2 图像分割

设8位灰度图像I的大小为M×N，图像I的像素记为Ii,j，Ii,j可用二进制表示为{bi,j,0，bi,j,1，bi,j,2，bi,j,3，bi,j,4，bi,j,5，bi,j,6，bi,j,7}，则有

其中{0≤Ii,j≤2551≤i≤M，1≤j≤N}，⎣·」表示向下取整，则图像I可用M×N矩阵表示为

图像的位平面分割过程如图2(a)所示，图像拥有者将I按位由高到低的顺序分解为2个不同的位平面，记前x个比特(即bi,j,0，bi,j,1，…，bi,j,x-1)所代表的元素组合成的高位位平面为H；记最后y个比特(即bi,j,x，bi,j,x+1，…，bi,j,7)所代表的元素组合成的低位位平面为L，x+y=8.hi,j、li,j分别表示上2个位平面矩阵中的元素，且有hi,j∈[0,2x-1]，li,j∈[0,2y-1]，则有

高位位平面H和低位位平面L可以分别表示为

图2 图像的位平面分割与重构过程Fig.2 The bit-plane segmentation and reconstruction process of the image

2.3 图像重构

图像的重构过程如图2(b)所示，具体步骤如下.

Step 1： 按从上到下、从左到右扫描H中所有元素，并把这些元素组合成一个数据串S；

Step 2： 对S利用RLC-u′位元表示法游程压缩，得到压缩后的数据串S′，且S′中的整数对为(Left，Right)，有Left，Right∈[0，2u′-1]，因此不会溢出；

Step 4： 统计L中的元素D，记其坐标信息为D_map，利用同Step 3相同的方法处理D_map，其长度记为LD_map，此过程即是记录在L中嵌入秘密数据的位置；

为防止重构过程中出现H溢出问题，对S和D_map执行Step 2后，再执行Step 3，可有效避免位置溢出问题.

2.4 图像加密

chi,j=E(hi,j,ri,j)=ghi,j·rnmodn2，cli,j=E(li,j,ri,j)=gli,j·rnmodn2.

注意：由定理1，当g的阶满足是n的非零整数倍时，c=E(m，r)是双射，这就保证对m加密有唯一值和其对应，目的是可逆提取，使接收者接收到嵌入秘密数据的密文图像后，可直接在密文数据中提取数据.

2.5 数据嵌入与提取

2.5.1数据嵌入 首先把秘密信息W分成n组，记为w1，w2，w3，…，wn，每组占用连续的y个比特，分别为wt1，wt2，…，wty，可以表示为

式中：t是W被分割的第t组，t∈[1,n]且为整数.对wt进行Paillier同态公钥加密，加密结果cwt可以表示为

cwt=E(wt,r)=gwt·rnmodn2.

若第n组占用比特数不足y个就以0填充，提取的时候舍掉即可.

数据嵌入者将密文图像分割成HE和LE，用公钥K1加密共享参数D，由定理1知，D对应的密文数据cD是唯一的. 因此，嵌入者可找到LE中与cD相等的元素，并通过同态相乘：

2.5.2数据提取与载体恢复

1) 直接在密文域中提取.对于2个互质的整数y和z，存在一个整数ζ满足：y·ζ=1modz，则ζ称为模乘法逆元,利用此特性可以实现模除法运算.假设一个整数x

提取完成后，再根据嵌入秘钥K即可恢复原始秘密数据.

3) 明文中提取.在解密过程中100%恢复H，但是对于I只是利用私钥解密，而没有还原L中的D元素.因此，这个解密过程得到的是类似原始图像I″，其低位位平面为L″，根据H中的位置信息D_map提取数据，则

3 实验及结果分析

为检验算法性能，采用Matlab2015b软件进行仿真实验，测试图像来自USC-SIPI图像库.

3.1 嵌入率分析和峰值信噪比

Baboon等9幅图像在不同x值下的载体最大嵌入率如表1所示，当x∈{1,6,7}时图像的嵌入率为0，这是由于图像重构阶段高位位平面压缩效果不佳造成的，H不足以存储对其进行压缩产生的S，因此不能嵌入秘密数据，所以嵌入率为0；x∈[2,5]时，随着高位位平面每个元素所占用比特位的增加，图像嵌入率呈不断减小趋势，这是因为随着x的增加，H中相邻元素间的相关性有所减小，导致压缩冗余空间变小，所存储的D元素的位置信息变少，而且低位位平面L中每个元素所占比特数减少，嵌入数据的D元素一次嵌入的比特数也随之减少，所以嵌入率会相对变小.但是，当x∈{2,3}时，部分图像(如F16，Splash等)在x=2时的嵌入率低于x=3时的嵌入率，这是因为图像载体具有较好的平滑度，当x=3时H压缩效果较好，能预留出足够供D元素的位置信息填充的冗余空间.

表1 不同x值下的载体最大嵌入率Tab.1 The maximum embedding rate of the different x bpp

表2 文献[5]和文献[6]算法的最大嵌入率Tab.2 The maximum embedding rate of literature [5] and [6] bpp

文献[5] 和文献[6]算法的最大嵌入率如表2所示，并与表1进行了对比，发现在秘密数据嵌入率方面，以Lena图为例，本文算法中Lena图在x=3时的最大嵌入率为0.139 bpp，而文献[5]和文献[6]算法中最大嵌入率仅为0.002 6 bpp和0.049 9 bpp，本文算法中最大平均嵌入率为0.128 bpp，而文献[5]和文献[6]算法的最大平均嵌入率分别为0.002 9 bpp和0.022 0 bpp，本文算法在嵌入率方面要优于文献[5]和文献[6]算法. 在直接解密与提取后再解密两种情况下，PSNR都是无穷大，可知在这两种情况下图像都可100%恢复.

图3(a)和(b)分别是以Lena和Baboon图像为载体直接解密，得到的嵌入率和PSNR关系图，并与文献[5]、[6]、[13]算法进行了对比.当x=4时，以Lena图为例，本文算法在嵌入率和PSNR方面的性能明显优于文献 [5]和文献[6]算法，在嵌入率不超过0.04 bpp的情况下，本文算法与文献[13]算法在PSNR方面的性能相似，但是当嵌入率超过0.04 bpp时，本文算法PSNR值高于文献[13]算法，在此情况下嵌入率最高能达0.071 bpp；当x等于3或2时，如图3(a)所示，在嵌入率不超过0.04 bpp的情况下，本文算法的PSNR值小于文献[13]算法的PSNR值，这是因为随着x的减小，低位位平面中D元素一次嵌入数据的比特位数增加，所以对原始像素的破坏增加.因此，在此情况下本文算法在PSNR方面不如文献[13]算法，但是嵌入率得到了提高，x=3和x=2时的最大嵌入率约等于0.126 bpp，而其对应的PSNR值分别是42.93 dB和35.03 dB，这是因为在x=3时一次性改变L中5 bit数据嵌入信息，在x=2时一次性改变L中6 bit数据嵌入信息，所以在嵌入率相等时x=2条件下PSNR值会变小.如图3(b)所示，图像载体Baboon的嵌入率与PSNR的对比试验，其结果分析与Lena图相似.

图3 嵌入率和PSNR的关系((a)、(b))及提取正确率散点图(c)Fig.3 The relationship between embedding rate and PSNR ((a), (b)) and scatter plot of extracted correct rate (c)

3.2 提取正确性分析

在一个码字集合中，定义任意两个码字之间对应位上码元取值不同的位数，为这两个码字之间的汉明距离，即

3.3 安全性分析

本算法在图像重构阶段，根据高位位平面H的压缩与填充，预先就相当于对原始图像的像素进行了一次重构，破坏了原始图像相邻像素间的相关性.而后进行Paillier同态公钥加密后，由于在嵌入端不需要使用私钥即可通过同态乘法嵌入数据，而私钥是通过安全渠道传递给合法的接收者，非法敌手无法获取私钥.因此，携密图像在传输过程中的安全性得到了保障，敌手在仅有私钥的情况下仅能解密图像而不能提取秘密数据.综上所述，本算法确保了秘密数据的安全性.

4 结束语

本算法采用像素位平面分割，而后利用Paillier同态公钥加密系统进行密文域上可逆信息隐藏，该算法保证在解密能100%恢复原始图像的前提下提高了嵌入容量，平均最高嵌入率可达0.128 bpp.理论与实验结果表明，提取与加密载体恢复实现了可分离操作.但是由于本算法是对2个位平面分别进行加密，因此算法复杂度有所增加，这也是今后需要对本算法进行改进的地方.

[1] 柯彦，张敏情，苏婷婷.基于R-LWE的密文域多比特可逆信息隐藏算法[J].计算机研究与发展，2016，53(10):2307-2322.

[2] HSU C Y,LU C S,PEI S C. Image feature extraction in encrypted domain with privacy-preserving SIFT[J].IEEE transaction on image processing,2012,21(11):4593-4607.

[3] HONG W,CHEN T S, WU H Y.An improved reversible data hiding in encrypted images using side match[J].IEEE signal processing letters,2012,19(4):199-202.

[4] LIAO X, SHU C W.Reversible data hiding in encrypted images based on absolute mean difference of multiple neighboring pixels[J].Journal of visual communication and image representation,2015, 28:21-27.

[5] ZHANG X P.Reversible data hiding in encrypted image[J].IEEE signal processing letters,2011,18(4):255-258.

[6] ZHANG X P.Separable reversible data hiding in encrypted image[J].IEEE transactions on information forensics and security,2012,7(2):826-832.

[7] WU X T,SUN W.High-capacity reversible data hiding in encrypted images by prediction error[J].Signal processing,2014,104(6):387-400.

[8] HUANG F J, HUNAG J W, SHI Y Q.New framework for reversible data hiding in encrypted domain[J].IEEE transactions on information forensics and security,2016,11(12):2777-2789.

[9] YIN Z X, ABEL A, ZHANG X P,et al. Reversible data hiding in encrypted image based on block histogram shifting[C]//IEEE International Conference on Acoustics, Speech and Signal Processing. Shanghai, 2016:2129-2133.

[10] GOLDWASSER S, MICALI S. Probabilistic encryption[J]. Journal of computer and system sciences 1984,28(2):270-299.

[11] PAILLIER P. Public-key cryptosystems based on composite degree residuosity classes[C]// Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques. Prague, 1999:223-238.

[12] DONALD E K. The art of computer programming[M]. Boston: Addison-Wesley,1997.

[13] ZHANG W M, MA K D, YU N H. Reversibility improved data hiding in encrypted images[J]. Signal processing,2014,94(1): 118-127.