结合半张量积压缩感知的可验证图像加密

温文媖，洪宇坤，方玉明*，张玉书，万征

1. 江西财经大学信息管理学院， 南昌 330000； 2. 南京航空航天大学计算机科学与技术学院， 南京 210000

0 引 言

大数据时代，获取和处理海量数据已经成为推动各个领域技术进步的源动力。其中最广泛的数据获取来源便是物联网，现代物联网时刻产生大量的多媒体数据，数据在物联网中不断流动(Wei等，2018)。这些数据有相当一部分由传感器采集而来，各种传感器设备负责采集各种类型的数据，包括图像、视频、音频等。然而传感器有两个关键问题需要解决:一是实现以有限的算力和存储空间进行数据的采集和传输，以降低传感器的功耗；二是在传输过程中确保数据的安全和完整性，以避免敏感数据被非法用户窃取和破坏。

对于第1个问题，压缩感知(compressive sensing,CS)是一种很好的解决办法。压缩感知作为一种新兴的数据采集方式，利用信号的稀疏性在采样的同时进行压缩。Candes等人(2006)指出，在一定条件下，压缩感知能够以远低于奈奎斯特-香农(Nyquist-Shannon)采样定理(Shannon,1949)所要求的采样频率下限进行信号采集，其采样结果仍然能够以极高精度恢复出原始信号。在压缩感知中，计算复杂度从采样端转移到重构端，因为计算复杂度在采样端是线性的，而在重构端，复杂度是非线性的。因此，运用压缩感知技术可以在传感器端有效降低采样时的资源开销，同时也很好地适应了传感器有限的储存资源。而计算资源丰富的云服务器可以进行计算复杂度相对较高的重构任务。

对于第2个问题，由于压缩感知的特性使得信号在压缩的同时加密成为可能。在压缩感知的采样阶段需要构建一个随机测量矩阵进行采样，如果将随机矩阵当作密钥便可以把压缩感知框架看做是一个对称密码系统。其中原始图像、测量矩阵和采样结果可以分别看做密码系统中的明文、密钥和密文。Rachlin和Baron(2008)证明了压缩感知的密码系统虽然不能满足香农定义的完美隐私性，但该方法仍然可以提供一个计算的安全性。基于此项研究，众多研究者提出了基于压缩感知的加密框架。Zhang等人(2018)首次提出了一种低成本保密的物联网多图像处理压缩感知技术，该技术将压缩感知、混沌卷积、混沌采样和单值扩散相结合，实现了良好的保密性。Mangia等人(2018)设计了一种基于等级的压缩感知方法，以确保最佳的压缩性能，防止纯密文图像被已知明文攻击。Wang等人(2019)在压缩图像上提出了一种有效的可加同态聚合方法。Luo等人(2019)根据蔡氏电路系统、压缩感知和Haar小波提出了一种新的图像压缩加密方案。然而，上述工作均存在能耗高的问题，主要体现在对大尺寸图像进行采样时需要一个非常大的测量矩阵，这将占用很大的存储空间。Chen等人(2012)提出了一种新的矩阵计算方法——半张量积，该方法允许尺寸不匹配的矩阵相乘。Xie等人(2016)证明了半张量积可以用于压缩感知。受此工作的启发，本文在压缩感知中采用了半张量积，可节省大量测量矩阵的存储空间。

此外，攻击者可能在传输过程进行篡改，有时候这种篡改给接收者带来的误导可能比没收到信息更严重(Li等，2019b)。所以需要一种方式来让接收者确认信息的完整性。消息验证码的出现解决了这一问题，传统的完整性验证方法中，首先通过对原始消息进行压缩映射得到一定长度的序列值，如Hash值，验证时再对待验证消息按照同样的映射方法再次生成同长度的序列值，然后跟原始的序列进行对比从而得出数据是否完整的结论。然而传统方法在CS框架中是无效的，原因如下：假设在传统方法中原始消息产生的序列值为hash(x)，而接收端生成的序列值为hash(x*)，其中x*代表可能被破坏了的消息。只要x与x*不同，则消息验证算法产生的序列值便完全不同。在压缩感知框架中，传输的是测量值而非原始信号，所以接收端收到的是测量值，需要用重建算法恢复出原始信号，而压缩感知只能让重建的信号和原始信号近似，而无法做到完全相同，所以接收端生成的消息验证序列和接收到的验证序列完全不同。Wu和Ruland(2018)提出了一种基于压缩感知的消息验证码，充分利用压缩感知框架生成验证序列。该方法可以容忍重建信息和原始信息的少量差异，但是没有考虑物联网背景下的资源受限情况，生成并存储校验序列会消耗占用很多的计算存储资源。

为此，根据压缩感知特性，本文提出一种级联混沌系统驱动的数据采集传输框架。该框架具有低能耗、高安全、可认证等特点，可以很好地解决上述问题。首先使用级联混沌系统来构建测量矩阵和验证矩阵，测量矩阵以压缩感知的方式进行采样得到观测值矩阵。验证矩阵进一步处理得到消息验证码，对观测值矩阵使用Arnold置乱方法得到最终的加密图像。仿真结果证实了所提方法的安全性和可用性。本文的贡献总结如下：

1)提出了一个面向物联网的新型数据采集传输框架,半张量积引入到压缩感知使该框架有着低能耗、高安全性的特点，设计的身份验证机制则使系统有了可验证性；

2)考虑传统压缩感知方法需要设计并存储大量不同尺寸的测量矩阵，将半张量积引入到压缩感知，克服了矩阵乘法的维数限制，且只需用较小的测量矩阵测量，使信息采集端所需的存储空间大大减小；

3)建立了适用于压缩感知的认证机制，使接收者可以识别出篡改信息并且容忍由压缩感知恢复阶段带来的误差。

1 系统理论基础

1.1 压缩感知

压缩感知(CS)理论基于信号的稀疏性或可压缩性实施压缩性地采样，通过解决欠定方程系统精确地重构出原始的信号。假定1维信号x∈RN，能够在一个N×N的正交矩阵Ψ的作用下稀疏化。稀疏过程表示为

x=Ψs

(1)

式中，s是一个长度为N的向量。如果s包含至多K个非零元，那么称之为K-稀疏。在CS理论中，通过实施大小为M×N(M

y=Φx=ΦΨs=Θs

(2)

式中，y是测量值，Θ=ΦΨ称为压缩感知的感知矩阵。采样时使用的是测量矩阵Φ，而重构时使用的是传感矩阵Θ。

为了保证能够有效地从测量值y重构出原始信号x，传感矩阵需要满足约束等距性(restricted isometry property, RIP)。

当测量矩阵满足约束等距性(RIP)条件时，求解最优化问题，即

(3)

1.2 半张量积

半张量积是介于传统矩阵乘法与张量积乘法之间的一种新型矩阵乘法运算(Cheng等，2007)。当两个矩阵A和B满足A的列数和B的行数成倍数关系时，两者之间可以进行半张量积乘法。

假设A∈Rm×n,B∈Rp×q，如果n是p的因数或p是n的因数,则有

(4)

设n为p的因数(p=nt),aij∈A，bij∈B，则展开式(4)得到

(5)

式中，Bij(i=1,2,…,n;j=1,2,…,q)是长度为t的列向量，表示将矩阵B的第i列划分为n块的结果。

对于定义中所示的A和B，如果n=p，则A×B=AB，即半张量积退化为传统矩阵乘积。

1.3 消息验证机制

通过压缩感知恢复信息并不总是与原始信息完全相同，可以在压缩采样同时额外构造一个验证矩阵。通过验证矩阵的传感直接产生验证值yMAC，即yMAC=ΦMACx。MAC表示消息认证码(message authentication code)。但是，压缩感知采集到的信号是实数或浮点数据，得到的数据量会太大。

本文采用值排序的方法来进一步提取和压缩构造出验证值。值排序方法R(·)是指排序的数字顺序。值排序方法有以下特点：

2)R(y)=R(ay+c)，其中a和c均为常数。

(6)

1.4 Arnold变换

Arnold变换(也称Cat映射)，可以把图像中各像素点的位置进行置换，使其达到加密的目的(Khalili和Asatryan，2013；Li等，2019a)。Arnold映射具有如下形式

(7)

式中，(xi,yi)是原始图像的坐标，(xi+1,yi+1)是置乱后图像坐标。在Arnold映射中，k1和k2是从正整数中随机选取置乱参数，通常k1和k2被设为1。除了k1和k2外，还有一个参数k3，主要用于控制方程式(7)的执行次数，在式(7)中并没有出现。

给定Arnold映射式(7)，对其进行逆操作得到

(8)

由此可知，只需要把置乱后的坐标(xi+1,yi+1)代入式(8)，可以恢复出原始图像坐标(xi,yi)。

2 基于半张量压缩感知的可验证图像加密方法

本文可验证加密方法首先采用并行压缩感知对原始信息进行采样，同时生成消息验证码。进一步，对压缩采样后的密文图像进行Arnold置乱得到最终的加密图像。本文算法框架图如图1所示。

图1 本文加密方法框架图Fig.1 Overall architecture of the proposed cryptosystem

2.1 加密过程

首先，利用级联混沌系统生成的测量矩阵和验证矩阵，测量矩阵用于对图像信号压缩采样，得到测量值，验证矩阵用于生成图像信号对应的消息认证码MAC。再使用Arnold置乱测量值矩阵进一步得到最终密文信号，与此同时由验证矩阵生成消息验证码一同在公共信道传输，将由级联混沌系统生成的测量矩阵、验证矩阵以及Arnold置乱的参数的初始种子作为密钥在安全信道上传输。

设原始图像为P，大小为N×N，压缩感知测量矩阵大小为M×N。其中，M=1/2N，即压缩率为0.5。

1) 分别将密钥cm，cp,cn作为初始参数代入到级联混沌系统 (Millerioux等，2008；Li等，2021；Zhou等，2015)，即

(9)

式中,v1∈[3.57,4],v2∈(1,2]。依次迭代(1 000+M×N)次，(1 000+MMAC×N)次和1 003次。这里M、MMAC和N分别代表图像压缩后的高度、验证矩阵的高度和原始图像高度。对3组迭代均丢弃前1 000个迭代值以防止初始项的干扰，第3组成为Arnold置乱的参数。重新排列xn，yn得到混沌序列

(10)

(11)

2)对LM进一步处理，令变换x′i=1-2×xi，则测量矩阵φM以及验证矩阵φMAC可以表示

(12)

(13)

3)利用测量矩阵φM图像信号P进行压缩感知，得到观测值矩阵P1以及消息验证矩阵PMAC，即

P1=φM×P

(14)

PMAC=φMAC×P

(15)

4)采用值顺序提取算法对验证矩阵PMAC处理，得到消息验证码MAC=R(PMAC)。

5)级联一组观测信号P1,P2,…,Pt，使之成为与原始图像大小一样的新图像信号P′，级联方法本文选择简单的堆叠，具体操作是

(16)

6)利用Arnold变换式(8)对堆叠后的图像信号P′进一步置换，得到最终加密图Pen。

2.2 解密过程

解密过程本质上是加密过程的逆过程。解密过程中，授权用户拥有安全密钥及其解密算法。首先，利用Arnold变换将接收到的密文图像Pen恢复成堆叠的信号P′，再把堆叠的信号分成各个观测信号P1,P2,…,Pt。将安全密钥代入级联混沌系统生成相应的混沌序列，用混沌序列生成测量矩阵以及身份验证矩阵，再通过重建算法把观测信号恢复成稀疏信号，利用稀疏矩阵把稀疏信号恢复成原始图像。最后将恢复出的原始信号经过消息验证矩阵以及值排序算法得到接收端的身份验证码，计算两者的差值，若其差值在允许范围内，则认为恢复出的图像为原始图像，否则视为遭受篡改。解密步骤为

1)对于接收到的最终加密图Pen，用逆Arnold变换式(8)对压缩信号进行解密，得到堆叠后的图像信号P′。

2)对P′分割，得到待重建的一组信号P1,P2,…,Pt。

3)对接收到的密钥cm，cp，执行加密过程的步骤1)—2)，得到测量矩阵φM以及验证矩阵φMAC。

4)利用压缩感知的重建算法式(3)对观测信号P1进行重构，得到稀疏信号s1；再将稀疏信号s1与小波变换矩阵Ψ相乘，即Ψ×s1为重建的原始信号P1re。

5)对重建的信号P1re执行加密过程的步骤3)—4)，得到恢复端的消息验证码MAC1re。

值得注意的是，对待重建P2,…,Pt信号，分别重复上述加密过程的步骤3)—5)，即可得到其在恢复端的消息验证码MAC2re,…,MACtre，最终将这些消息认证码级联得到恢复信号的消息认证码MACre。

6)计算原始信号的消息验证码MAC和恢复信号的验证码MACre的差值，如果满足式(6)，则认为接收到的信息没有被篡改，否则，视为遭受篡改。

3 性能测试与分析

本文的模拟测试是MATLAB2018a软件在一台带有AMD Radeon TM R7 350和2 GB内存的计算机上进行的。为充分证明所提算法的安全性和有效性，本文从密钥空间分析、密钥敏感性分析、直方图分析、相关性分析、图像熵分析等方面进行模拟测试。

3.1 密钥空间分析

对于一个优秀的加密算法，能够抵抗暴力攻击是有必要的(Wen等，2015)。最有效的抵抗暴力破解的方法是增加密钥空间。对所提出的加密方法，有3个密钥：生成测量矩阵和验证矩阵的参数cm、cp，生成Arnold置乱参数的cn。这3个密钥均由级联混沌系统的种子生成，密钥空间大小均为1016。因此，本文加密方法的密钥空间约为1048，这足以抵御暴力破解攻击。

3.2 密钥敏感性分析

密钥敏感性是密码系统有效性的重要指标(Guesmi等，2016)。图2显示了本文方法的密钥敏感性。在其中一个参数引入10-16的微小变化，而其他参数保持不变的情况下，图2(a)—(e)展示了Cameraman图像相应的恢复结果。从图2可知，一个微小的干扰将导致原始图像完全不可恢复。

图2 正确和错误密钥恢复的图像Fig.2 The images recovered with correct keys and wrong keys((a) correct key; (b) wrong key cm; (c) wrong key k1; (d) wrong key k2; (e) wrong key k3)

为更客观地验证，本文采用均方误差(mean squared error, MSE)来评估这些密钥的敏感性，计算为

(17)

式中，i=1,…,N,j=1,…,N,y(i,j)表示恢复的图像像素，x(i,j)是原始图像像素，N×N表示原始图像的大小。表1分别列出了原始图像、利用正确的密钥恢复的图像以及混沌系统的种子略微改变10-16的恢复图像计算出的均方误差。结果表明，利用正确密钥恢复的图像MSE较小，即恢复效果较好。密钥经过10-16扰动后，恢复的图像均方误差非常大，这表明无法从扰动图像中获得有用信息。

表1 正确和错误密钥恢复的图像的MSETable 1 MSE for correct and wrong keys

至于密钥cp，因其构成的是验证矩阵，对图像的加密解密没有影响，故不适合用上述方法证明密钥敏感性。本文对正确密钥cp产生的消息验证码和错误密钥cp产生的消息验证码，利用式(6)，分别和原始消息验证码做了对比，结果如表2所示。

表2 正确和错误密钥恢复的消息验证码Table 2 MAC for correct and wrong keys

3.3 图像熵分析

图像熵的概念源于香农从热力学，香农用信息熵的概念来描述信息的不确定性。信息熵是随机性的度量，有多种变体(王国胤 等，2002)。其中，图像熵应用于图像领域，它是一种统计类型的特征，反映了图像的平均信息量，定义为

(18)

表3 图像熵分析Table 3 Image entropy analysis

3.4 相关性分析

具有良好的置乱效果是判断一个图像加密系统有效性的重要标准，可以通过计算图像相邻像素之间的相关性来评价其置乱效果。为评估本文加密方案的置乱效果，从原始图像中随机选取3 000对相邻像素，分别从水平、垂直和对角线方向进行分析。图3 (a)—(c)和(d)—(f)分别表示相邻像素在水平方向、垂直方向和对角线方向上的明文Cameraman与其对应的密文图像的相关性。可以清楚地看到，明文图像的相邻像素有很强的相关性，而相应的密文图像的像素之间的相关性已经完全被打乱。这说明本文加密方案具有良好的置乱效果。

此外，为量化本文方案的加密效果，计算了明文图像和密文图像的相关系数

(19)

图3 明文图像及其密文图像相关性分析Fig.3 Correlation analysis of plain image and cipher image((a) plain image in horizontal direction; (b) plain image in vertical direction;(c) plain image in diagonal direction; (d) cipher image in horizontal direction; (e) cipher image in vertical direction; (f) cipher image in diagonal direction)

表4 明文图像和密文图像相邻像素值的相关性系数Table 4 Correlation coefficients of adjacent pixel values of plain and cipher images

3.5 身份验证分析

对于身份验证功能，对图像进行篡改攻击来验证，即对于原始图像的一部分内容进行篡改，使其和恢复出来的图像进行对比。图4(a)是256×256像素的原始图像，图4 (b)(c)(d)分别表示被50×50像素，80×80像素，100×100像素的Bird篡改的图像。从表5可以得出，未被篡改的图像身份验证值在20以内，而被篡改的图像的身份验证值则超过100，并且随着篡改范围的增大，身份验证值也有增大的趋势。这表明本文身份验证方案能有效应对篡改攻击。

3.6 压缩率分析

本文考虑了压缩率对重建图像质量的影响，并利用不同的原始图像来验证压缩和恢复效果。本文压缩率指密文图像和原始图像的大小比值。图5展示了原始图像和不同压缩率下图像的恢复效果，在视觉效果上，即使压缩率在0.125以下，其图像内容仍然可以辨认。

图4 原始图像和篡改图像Fig.4 Original image and tampered images ((a)plain image; (b) tampered size with 50×50 pixel; (c)tampered size with 80×80 pixel; (d) tampered size with 100×100 pixel)

表5 身份验证分析Table 5 Identity verification analysis

此外，利用峰值信噪比(peak signal to noise ratio, PSNR)来定量描述图像之间的差异，计算为

(20)

图5 原始图像和在不同压缩率下的恢复图像Fig.5 Original images and the restored images under different compression ratio ((a) plain images; (b) compression ratio 0.5; (c) compression ratio 0.25; (d) compression ratio 0.125)

式中，x(i,j)和y(i,j)分别为原始图像和重构后的图像像素值，N1×N2为图像大小。重构图像的峰值信噪如图6所示，随着压缩率的降低，图像的峰值信噪比有所下降。

图6 压缩率(CR)和峰值信噪比(PSNR)的相关性Fig.6 The relationships between PSNR and CR

图7列出了不同压缩率和不同篡改率下得到的身份验证值。可以看出，一旦图像的部分信息被篡改，其消息验证值便会大大上升；压缩率减小时，计算出的消息验证值也会增大，但总体没有被篡改图像的消息验证值大。这说明本文方法对于篡改信息较为敏感。

图7 压缩率和篡改范围对消息验证值的关系Fig.7 Relationship between compression rate and tampering range to message verification value

4 结 论

本文构建了一种基于半张量积压缩感知的图像加密方法，并且在采样过程中通过计算消息验证码来验证该方法的防篡改能力。同时，利用级联混沌系统作为密钥生成器增强了安全性。从密钥空间分析、密钥敏感性分析、图像熵分析、直方图分析、相关性分析、身份验证分析、压缩率分析等方面进行测试，结果表明本文方法具有较好的加密效果，并具备较好的识别篡改能力。

机器学习是一种实现人工智能的方式,是近几年的热点研究领域，目前机器学习在很多领域已有成熟的应用。本文方法目前还是利用经验来控制消息验证码的阈值，接下来的工作将考虑用机器学习的方法自动设置阈值，以达到减小人工工作量和自适应的目的。