基于边缘计算的支持多密钥的加密图像检索

李颖莹，马建峰，苗银宾

（1.西安电子科技大学网络与信息安全学院，陕西 西安 710071；2.陕西省网络与系统安全重点实验室，陕西 西安 710071）

1 引言

随着图像设备如数码相机、智能手机迅速更新换代，以及各种图像应用层出不穷，图像数据呈爆炸式增长趋势，大大增加了用户本地数据计算和存储负担。资源受限的用户借助云计算服务将数据外包至云服务器。但是在万物互联的时代，仅依靠以云计算为代表的集中式计算模式不足以支持海量数据处理，不能有效解决服务负载、传输带宽等问题，无法满足数据实时性处理需求。因此，以边缘计算为代表的分布式计算模式应运而生，为海量移动设备提供最近端服务，相比以云计算为代表的集中式计算模式节省了大量计算、传输和存储成本。但另一方面，外包至边缘计算节点的图像数据由于脱离了用户的实际掌控而面临隐私泄露问题。为此，用户将加密后的图像数据外包至边缘计算节点。尽管加密算法能在一定程度上保证图像数据安全，但会影响图像检索在密文上的应用。

传统的明文图像检索主要采用基于文本的图像检索（TBIR,text-based image retrieval）和基于内容的图像检索（CBIR,content-based image retrieval）2 种方法。其中，基于文本的图像检索方法是用文本对图像进行人工标记，受人为主观影响导致查询准确率低。基于内容的图像检索方法用图像本身的颜色、纹理和形状信息客观描述图像内容，大大提高了查询准确率。目前，如何在密文上应用明文CBIR 技术是加密图像检索研究的重点之一。Lu 等[1-2]提出基于CBIR 的加密图像检索方案，并用同态加密算法保护图像特征向量；Zhang 等[3]利用同态加密和属性基加密技术实现大规模加密图像检索；Xia 等[4]基于词袋模型和地球移动距离设计了一个安全CBIR 方案。尽管基于同态加密和可搜索加密技术可以实现加密图像检索[5-7]，但是如果将这些支持单密钥的传统图像检索方案直接应用到实际多密钥场景中，查询用户必须生成多个陷门。例如，在电子医疗系统中，医生想要查询其他3 个医院的医疗图像库。如图1(a)所示，这3 个医院的医疗图像库由各自密钥加密，通过系统认证的医生需要发送3 个查询请求才能达到检索目的。当系统中医院数目增多时，医生实现检索目的所需的计算开销和通信开销随之增多。如果医生只需要生成一个查询请求就可以检索其他所有医院的医疗图像库，如图1(b)所示，用户只需生成一个查询陷门即可查询不同密钥加密的图像集，这将大大减小用户的计算与通信开销。

然而，已有的加密图像检索方案[1-2,4-12]大多不支持多密钥加密图像检索，仅有的支持多密钥加密图像检索的方案[3,13]由于涉及复杂的安全多方计算和同态加密技术，导致实用性受到影响。因此，需要设计一种支持多密钥的加密图像检索方案，解决以下关键问题：1)所有外包至边缘服务器的数据都应进行加密，使服务器无法根据密文获取明文相关信息；2)每个图像查询用户应该以尽可能低的开销查询不同密钥加密的图像，以便实现云端数据共享；3)检索结果应满足查询要求，检索时间应满足实时性需求，以保证方案的准确性和高效性。

图1 方案背景比较

为解决以上问题，本文基于局部敏感哈希算法、安全近邻算法及代理重加密等技术提出了基于边缘计算的支持多密钥的加密图像检索方案。局部敏感哈希算法在生成索引时将相似图像映射到同一个桶中，能有效减小图像检索时间，保证方案的高效性。安全近邻算法利用随机向量分裂和可逆矩阵加密向量，可快速实现图像相似度的安全计算，保证方案的安全性和准确性。代理重加密技术能够帮助代理服务器进行不同加密密钥密文之间的转换，将拥有者加密的密文转换成查询用户可解密的形式，以此减少多拥有者/多密钥场景下查询用户的开销。边缘计算具有低时延、高可用、高实时的优势，能克服云计算模式中因数据迁移、网络传输造成过多带宽资源消耗的不足，为用户提供高质量服务。本文基于这些算法和技术提出基于边缘计算的、支持多密钥的加密图像检索方案，其具有以下特点。

1)多密钥场景。提出了一种多密钥场景下的加密图像检索方案，查询用户仅需生成一个查询陷门即可对不同密钥加密的图像进行检索，比传统方案更实用，用户计算负担更小。

2)访问控制。实现了对图像查询用户的访问控制，边缘服务器重加密图像加密密钥后，用户只能用合法分配的私钥解密。密钥中心为每个查询用户分发不同的私钥，即使其他用户窃取查询结果，也不能解密出明文。

3)高安全性。在用图像特征向量的内积表示图像之间的相似度时，所提方案在特征向量中加入了冗余项，以此提高了服务器端相似度计算的安全性。

2 相关工作

密文检索主要涉及文本领域和图像领域。关于文本检索的多密钥场景，Yin 等[14]利用随机密钥为不同数据建立索引，同时用户选择其他随机密钥生成陷门而不影响密文匹配，减少了密钥管理复杂度，但不支持细粒度访问控制。Sun 等[15]利用属性基加密和代理重加密技术设计了支持细粒度访问控制的密文检索方案，且支持数据用户的属性撤销，避免了用户与拥有者直接交互。不同于密钥和数据一一对应，Miao等[16]针对共享型数据的多密钥场景，利用多重签名技术提出了高效可验证的关键字检索方案，可抵抗选择关键字攻击，后来又扩展到连接多关键字模型[17]，提出既支持连接多关键字又可进行结果验证的高效检索方案，能够抵抗离线关键字猜测攻击。

上述方案都是针对文本检索的研究，图像不像文本那样可用关键字进行准确唯一标记，从而导致基于关键字的密文检索方案无法直接应用于图像领域。Lu 等[1]提出了基于CBIR 的加密图像检索方案，允许图像进行相似性匹配，但是没有考虑明文图像和加密图像之间的距离变化。针对这一问题，Lu 等[8]采用了保序加密和Min-hash 方案，但是该方案局限于用视觉单词描述图像特征。Zhang 等[9]利用同态加密性质解决了距离变化问题，并用欧氏距离作为图像相似性度量，然而同态的使用大大增加了方案计算开销。为减小计算开销，Xia 等[10]基于图像的全局特征利用局部敏感哈希算法构建索引，实现了高效的加密图像检索。Yuan 等[11]基于多项式性质提出了支持访问控制的加密图像检索方案，并设计了安全k-means 外包算法。

尽管以上方案实现了加密图像检索，甚至具有高效率和访问控制功能，但是这些方案均针对单密钥场景，无法满足实际需求中的多密钥场景。Liang等[12]针对多个查询用户设计了多密钥非对称内积加密算法，为不同查询用户分发不同密钥，同时利用全局优化和高斯分布提高密钥安全性和空间利用率，但是该方案不支持在多个密钥加密的图像集上检索。Shen 等[13]和Zhang 等[3]分别利用安全多方计算和多密钥同态加密提出了支持多拥有者-多用户的加密图像检索方案，尽管前者通过简化欧氏距离计算方法，后者借助并行计算模式来减小计算开销，但方案的实用性仍受计算和通信开销影响。为减小开销，王祥宇等[18]通过设计轻量级密钥转换协议来实现多用户加密图像检索方案。此外，文献[19-21]提出了多密钥背景下的可搜索加密方案，但是尚未实现图像检索。

针对已有方案绝大多数不支持多密钥加密的图像检索或者多密钥加密的图像检索方案效率较低的问题，本文结合局部敏感哈希算法、安全近邻算法和代理重加密技术，利用边缘计算模式数据就近处理原则，提出基于边缘计算的支持多密钥的图像检索方案。表1 给出了本文方案与其他方案的比较。从表1 可以看出，本文方案能同时满足多密钥场景、访问控制、已知背景攻击安全和高效率这4 个要求。

表1 本文方案与其他方案的比较

3 预备知识

本文方案主要运用基于双线性对的代理重加密技术解决多密钥转换问题，应用局部敏感哈希算法提高检索速度，其中哈希函数属于p稳态局部敏感哈希函数。本节分别介绍代理重加密和局部敏感哈希的相关定义。

定义1双线性对[22]。设G,GT是2 个阶为素数p的乘法循环群，g是G的一个生成元。双线性对e:G×G→GT有以下性质。

1)可计算性。存在一个有效算法可计算e。

2)双线性。对任意u,v∈G和a,b∈Zp，都有e(ua,vb)=e(u,v)ab。

3)非退化性。e(g,g)≠ 1。

定义2代理重加密[23]。一个代理重加密方案由算法KeyGen、ReKey、Encrypt、ReEncrypt、Decrypt构成。

1)(pki,ski)←KeyGen(1κ)。输入安全参数κ，为用户i输出公私钥对(pki,ski)。

2)rkA→B←ReKey(pkA,skA,pkB,skB)。输 入Alice 的公私钥对(pkA,skA)和Bob 的公私钥对(pkB,skB)，输出代理重加密密钥rkA→B，其中，Alice为委托者，Bob 为被委托者。

3)ci←Encrypt(pki,m)。输入用户i的公钥pki和消息m，输出密文ci。

4)cB←ReEncrypt(rkA→B,cA)。输入代理重加密密钥rkA→B和Alice 的密文cA，输出Bob 可解密的密文cB。

5)m←Decrypt(ski,ci)。输入用户i的公钥ski和密文ci，输出消息m或错误符号⊥表示ci不合法。

定义3p稳态局部敏感哈希[24-25]。给定距离R、cR，概率值P1、P2，其中c＞ 1，P1＞P2，称函数族H 是(R,cR,P1,P2)敏感。对任意2 个d维向量u,v∈Rd和任意函数h∈H。

此处，函数h为p稳态局部敏感哈希函数，形如，其中，a是每维服从p稳态分布的d维向量，b是一个服从[0,r)均匀分布的实数，r是一个常数。

4 系统模型、威胁模型及安全目标

4.1 系统模型

本文方案包括4 个实体，即密钥生成中心、图像拥有者、图像查询用户和边缘服务器，系统模型如图2 所示。完全可信的密钥生成中心负责系统初始化和密钥分配，图像拥有者将加密图像、加密密钥密文和加密索引上传到边缘服务器存储，查询用户将查询陷门发送给边缘服务器，边缘服务器则根据陷门匹配加密索引获取候选图像集列表，然后重加密候选图像集对应的密钥密文，最后将密钥和候选图像集作为检索结果返回给查询用户。

图2 系统模型

1)密钥生成中心。为图像拥有者和查询用户生成密钥。如图2 中①所示。

2)图像拥有者。加密图像集和图像加密密钥，计算转换密钥，构建加密索引，最后将加密图像、加密密钥密文和加密索引上传给边缘服务器。如图2 中②所示。

3)图像查询用户。加密查询图像的特征向量，生成查询陷门发送给边缘服务器。如图2 中③所示。

4)边缘服务器。根据查询用户发送的陷门和拥有者发送的加密图像、加密索引进行查询，对图像加密密钥进行重加密，最后将搜索结果和重加密密钥密文返回给用户。如图2 中④～⑨所示。另外，图2 中⑩表示没有密钥的非法用户即使窃取检索结果也不能解密出明文。

4.2 威胁模型

在本文方案中，假设边缘服务器是半可信的，即服务器会诚实且正确地执行协议，同时也会积极获取加密图像的明文信息。此外，假设图像拥有者和查询用户是可信的，且查询用户和服务器之间不会相互合作。根据服务器可获得的知识将攻击模型总结为以下2 种。

已知密文攻击模型[26]。服务器只知道从图像拥有者端外包而来的加密图像集和加密索引以及来自图像查询用户的查询陷门。

已知背景攻击模型[27]。与已知密文攻击模型相比，服务器拥有更多背景知识，如额外获得一些查询陷门对应的明文、图像明文等。

4.3 安全目标

基于4.2 节定义的威胁模型，本文安全目标主要是防止半可信服务器从图像密文集、索引集、密钥密文集、陷门和内积计算结果中获取有效信息。

1)图像隐私。服务器从加密图像集中不能解密明文图像，也不能获取明文图像相关信息。

2)索引隐私。服务器不能解密加密索引表，更不能解密索引表中的特征向量。

3)密钥隐私。服务器在进行重加密操作时，不能获取拥有者和查询用户的私钥，也不能解密图像加密密钥。

4)陷门隐私。服务器根据陷门无法得知查询图像的明文信息，也不能判断陷门之间的关系。

5)内积计算隐私。服务器从加密向量内积计算结果中无法知道明文向量内积值，同时应用统计分析也不能获取任何明文信息。

5 支持多密钥的加密图像检索方案

由于不同拥有者的图像加密密钥不同，致使查询用户不能用同一个陷门查询图像集。如果将支持单密钥的传统图像检索方案直接应用于实际多密钥场景，会为用户带来额外开销；而且传统云计算模式在数据存储、传输方面消耗大量带宽资源，无法满足实时处理数据的需求。为解决这些问题，本节提出基于边缘计算的支持多密钥的加密图像检索方案。方案利用代理重加密技术实现图像加密密钥的密文转换，应用局部敏感哈希算法提高检索速度，再用安全近邻算法提高检索精度和安全性，基于边缘计算模式节约数据在服务器和终端设备之间的传输链路资源。

5.1 方案定义

在对本文方案进行详细描述之前，给出方案定义。首先，定义方案中用到的符号，如表2 所示。

表2 符号定义

其次，定义本文方案主要包含的7 种算法。

1)(G,Γ,k,sk,pk)←KeyGen(1κ)。给定安全参数κ，密钥生成中心输出系统参数G 和Γ、图像加密密钥k、私钥sk 和公钥pk。

2)C←ImgEnc(k,M)。图像拥有者用加密密钥k加密明文图像M，输出密文图像C。

3)Λ←KeyTrans(k,pk,sk)。图像拥有者将图像加密密钥k加密成k′，并生成转换密钥TKUID，输出重加密密钥Λ。

4)I←IndexGen(Γ,M)。图像拥有者用参数Γ对明文图像M的特征向量进行预处理并加密特征向量，输出加密索引I。

5)TD ←TrapdoorGen(Γ,mq)。图像查询用户利用参数Γ对查询图像mq的特征向量进行预处理并加密特征向量，输出查询陷门TD。

6)R←Search(C,Λ,I,TD)。边缘服务器根据查询陷门TD 匹配索引集I，在图像密文集C中搜索符合查询要求的密文，将密文结果对应的拥有者密钥k′重加密成，输出检索结果R。

7)M′←ImgDec(R,sk)。图像查询用户用自己的私钥sk 解密出图像加密密钥，进一步解密出明文图像。

5.2 方案描述

本节从7 个阶段描述本文方案的具体步骤，即密钥生成阶段KeyGen、图像加密阶段ImgEnc、密钥转换阶段KeyTrans、索引生成阶段IndexGen、陷门生成阶段TrapdoorGen、检索阶段Search 和图像解密阶段ImgDec。其中，除密钥生成阶段外其他6个阶段流程如图3 所示。

5.2.1 密钥生成阶段

(G,Γ,k,sk,pk)←KeyGen(1κ)。密钥生成中心输入参数κ，输出双线性对参数和秘密参数，其中，s为一个d+1 维随机二值向量，A1和A2为2个(d+1)×(d+1)维随机可逆矩阵，为λ个哈希函数，为局部敏感哈希函数族，为L个哈希表的加密函数。密钥生成中心为拥有者分配图像加密密钥和公私钥对(sko,pko)，满足，为u个用户分配公私钥对，身份为UID 的用户分配到公私钥对，满足。需要说明图像拥有者知道查询用户的公私钥。

图3 方案执行流程

5.2.2 图像加密阶段

C←ImgEnc(k,M)。图像拥有者利用图像加密密钥ki将明文图像集Mi加密成密文图像集Ci，将w个不同密钥加密的密文图像集发送给边缘服务器存储。

5.2.3 密钥转换阶段

Λ←KeyTrans(k,pk,sk)。图像拥有者首先将图像加密密钥ki加密成，其中，εi为随机数，F为双线性对，即F=e(g,g)。接着为UID 的用户计算转换密钥，则ki对应的重加密密钥为。最后，w个重加密密钥组成发送给边缘服务器。

5.2.4 索引生成阶段

I←IndexGen(Γ,M)。索引生成阶段分两步完成，第一步为生成未加密的索引表，第二步为加密索引表。

1)生成未加密的索引表。对于图像集Mi中每幅图像mi,t，先提取特征向量，其中t∈[1,ni]，ni为Mi所含图像总数。然后将λ个哈希函数h1,h2,…,hλ作用于向量fi,t，得到λ个哈希值。接着将L个ψ(⋅)作用于fi,t，构造L个哈希表，即为未加密索引表，表中每个桶的值为，其中j∈[1,L]，b∈[1,Ni,j]，Ni,j为第j个哈希表中桶的数目。如表3 所示，图像mi,t的特征向量fi,t和其相应图像信息标识符ID(mi,t)共同存储在哈希表中。第j个表有Ni,j个哈希桶，同一个哈希桶中的图像是相似的。

2)加密索引表。用函数ϕ(⋅)加密桶值，用文献[28]中安全近邻算法加密特征向量。具体地，将d维图像特征向量扩展成维向量，再根据随机二值向量s将分裂成两部分。分裂规则为，对于时，有；否则，为随机赋予正值，使其满足。接着用随机可逆矩阵和分别乘，可得加密后的特征向量。表4 给出加密后的第j个哈希表。L个加密后的哈希表构成索引表Ii。拥有者将w个Mi生成的索引表发送给边缘服务器。

表3 第j个哈希表

表4 加密后的第j个哈希表

5.2.5 陷门生成阶段

TD ←TrapdoorGen(Γ,mq)。与索引生成阶段类似，查询用户首先提取查询图像mq的特征向量，然后用ψj(⋅)计算桶值BKTj，，用ϕ(⋅)加密桶值为。接着用户将fq扩展为，对于l∈[1,d+1]，若，则为随机赋予正值，使其满足；否则，。再随机选取正数δ∈R+，用分别乘以，得到加密查询向量。最后和用户身份UID 组成陷门,UID}发送给边缘服务器，由边缘服务器进行检索。

5.2.6 检索阶段

R←Search(C,Λ,I,TD)。检索阶段分两步完成，第一步为计算相似度，第二步为重加密密钥。

1)计算相似度。边缘服务器接收到查询陷门TD 后，首先在索引表里找到与陷门桶值相同的桶，桶里面的图像即为候选图像集。然后计算候选图像集的特征向量与查询图像特征向量之间的内积值，计算过程如式(1)所示。

边缘服务器依次计算候选列表中每幅图像mi,t与查询图像mq的内积值，根据内积值大小排序选出前r个最相似的加密图像。

2)重加密密钥。边缘服务器根据r个加密图像对应的密钥密文及用户身份UID 对应的转换密钥TKUID计算，计算过程如式(2)所示。

边缘服务器将r个加密图像和对应的重加密密钥作为检索结果返回给查询用户。

5.2.7 图像解密阶段

M'←ImgDec(R,sk)。收到检索结果的查询用户用其合法私钥skUID计算加密密钥，如式(3)所示。

得到图像加密密钥ki，用来解密出相应明文图像。若用户无合法私钥skUID，则不能解密重加密密钥密文，更不能解密图像密文。

本节介绍的方案主要利用代理重加密技术完成密钥转换，借助局部敏感哈希算法提高检索效率，应用安全近邻算法计算内积提高检索精度，其中内积计算方法只能保证唯密文安全，不可抵抗已知背景攻击。如若敌手获得一组明密文对(f,f′)和一组陷门明密文对，以及明文图像子集P，计算内积，由此获得随机数δ取值，进而可判断检索结果中其他图像与查询图像明文之间的关系。针对这一问题，下面对此方案（基础方案）做出改进，使其能够抵抗已知背景攻击。

6 改进方案

为使本文方案能够抵抗已知背景攻击，对相似度计算方法进行改进，在特征向量中添加部分冗余项，其他步骤不变。虽然添加冗余项会影响检索精度，但为提高安全性，本文方案可以适当妥协。下面对需改动的阶段进行说明，对无影响的ImgEnc、KeyTrans 和ImgDec 阶段不予说明。

KeyGen将d+1维随机二值向量s扩充成d+α+1维，(d+1)×(d+1)维随机可逆矩阵A1和A2也扩充成(d+α+1)×(d+α+1)维，另外增加α维随机向量η组成冗余项。其余参数不变。

I ndexGen 针对特征向量加密过程，将d维特征向量扩展成d+α+1维向量，其中。随机分裂和矩阵加密步骤与基础方案一致，得出加密后的向量。

TrapdoorGen针对查询图像qm的特征向量加密过程，将d维特征向量扩展成，其中β为α维的随机二值向量。后续随机分裂和矩阵加密步骤与基础方案一致，得到加密后的查询向量。

Search向量内积计算形式变化为

由式(4)可以看出，改进方案中内积计算结果比基础方案多出了冗余项βηT。这将提高内积计算结果的安全性，7.1 节会给出具体分析。

7 方案分析

本节将分析所提方案的安全性及理论性，同时使用真实数据集进行实际性能测试。

7.1 安全性分析

本文方案能够达到所提的安全目标，具体分析如下。

1)图像隐私。本文采用传统对称密钥加密算法加密图像，图像隐私的安全性依赖于加密算法，安全的加密算法能有效防止图像隐私泄露。

3)密钥隐私。虽然服务器根据重加密密钥可以控制查询用户的访问，但是从中解密出图像拥有者私钥sko和图像查询用户私钥skUID依赖于离散对数困难问题的解决。没有skUID的服务器无法从计算结果FεiskUID中获得图像加密密钥k。同样，没有被授权的用户因为没有合法的公私钥也无法解密出图像加密密钥。

4)陷门隐私。与索引隐私相同，只要不泄露随机向量s和随机矩阵A1、A2，查询向量就不会被泄露。另外，随机数δ的引入保证了陷门之间没有关联，使边缘服务器无法通过陷门判断每次查询图像是否相同。

5)内积计算隐私。虽然边缘服务器根据计算结果可知图像间的相似度，但是由于δ和βηT的存在无法恢复出图像之间的距离。另外，为体现冗余项的干扰作用，2 个冗余项βηT有相同取值的可能性应小于，即对每一个fi,t，βηT至少有2γ个不同取值。而βηT的总数不大于，其中|β|为β中1出现的次数。当值最大。即，当α=2γ，|β|=γ时，有，因此每个fi,t至少含有2γ个冗余项，每个fq从中随机选取一半的冗余项。为尽可能不影响排序结果的精确性，βηT应服从正态分布。令随机向量η的每一维ηi服从均匀分布，可知均值和方差分别为μ′和。根据中心极限定理，对于γ个独立同分布随机变量ηi，其和近似服从正态分布。令，也就是，有βηT服从正态分布N(μ,σ2)。此时，方案的精确性和安全性随σ2变化而变化，σ2越大，安全性越高，精确度越低；σ2越小，安全性越低，精确度越高。更具体的证明可参考文献[29]。此外，根据内积计算形式，可以证明在已知背景攻击模型下对于多项式时间敌手，加密图像集和查询陷门是安全的。

定理1对于多项式时间敌手，内积计算在已知背景攻击模型下可保证加密图像集和陷门安全。

在已知背景攻击模型中，敌手可接触加密图像集、加密索引表和陷门集，获取其他背景知识，如一组明密文对和陷门明密文对，以及明文图像子集。假设敌手为，其中，为加密向量集，为陷门集，为明文向量集，为一组明密文对，为一组陷门明密文对。需要说明的是，即使敌手知道加密特征向量集C，也无法知道P中明文特征向量对应的密文形式，更无法得知P和C之间的对应关系。

证明图像向量之间的相似度可由式(5)度量。

其中，δ和Tβη均未知，且加密后的特征向量不会泄露明文特征向量信息，即使已知明文向量集P，敌手在多项式时间内也无法暴力破解。因此在已知背景攻击模型下，敌手无法获得加密数据集和陷门的明文形式。

证毕。

需要说明的是，为了实现高效加密图像检索方案，有必要泄露最少的信息给边缘服务器。例如边缘服务器很容易知道在同一个哈希桶中的图像是相似的，同样也知道检索结果里的图像是相似的。如果想要避免这些信息泄露，可以采用文献[30]中的方案。但考虑到其复杂度过高，效率低下，且远未达到实用程度，本文暂不解决这些问题。

7.2 性能分析

下面分别从理论和实际性能2 个方面与文献[13]方案（MIPP,multiple image owners with privacy protection）对比，论证本文方案（基础方案、改进方案）的可行性。理论分析涉及计算开销和存储开销。实际性能主要对KeyGen、KeyTrans、IndexGen、Search 这4 个阶段以及检索精度进行仿真实验。

7.2.1 计算开销分析

表5 给出了3 种方案的理论计算开销对比。本文主要考虑了几种比较耗时的密码运算，即群Zp指数运算、群G指数运算、群GT指数运算、双线性对运算E、哈希运算H、矩阵运算M′、M′以及MIPP 中群指数运算Gq和加法运算。另外，图像加解密采用传统对称加解密算法，在此不予分析。

表5 中，w表示图像拥有者个数，d表示提取出的特征向量维数，d′表示基础方案中加密特征向量维数，d′表示改进方案中加密特征向量维数，n表示图像总数，L表示哈希表个数，λ表示哈希函数个数，r′表示检索结果中来自不同密钥加密的图像种类，符号“—”表示不存在。

由表5 可看出，在KeyGen 阶段，密钥生成时间随图像加密密钥个数增加而增加，方案改进前后向量维数增多使密钥生成时间也增多。在KeyTrans阶段，密钥转换时间受密钥个数影响，密钥个数越多，密钥转换时间越多。但方案改进前后，该阶段计算开销保持一致。在IndexGen 阶段，索引生成时间与图像总数呈正相关，特别是改进方案中矩阵维数增加，因此改进方案的索引生成时间比基础方案多。在TrapdoorGen 阶段，考虑一个用户的一次查询，陷门生成时间主要受矩阵计算、哈希计算以及特征向量维数影响。在Search 阶段，计算开销主要受向量维数或加密密钥个数影响。根据以上几个阶段的分析，改进方案比基础方案计算开销增大或者保持一致，主要是因为特征向量维数增大，但以此为代价可换来安全性的提高。由于MIPP 没有进行密钥转换，因此只列出了其他4 个阶段。可以看出，MIPP 每个阶段的计算开销与群指数运算密切相关，而本文方案只有2 个阶段的开销受群指数运算影响。

7.2.2 存储开销分析

表6 中，w表示图像拥有者个数，d表示提取出的特征向量维数，d′表示基础方案中加密特征向量维数，d′′表示改进方案中加密特征向量维数，n表示图像总数，L表示哈希表个数，符号“—”表示不存在。

表5 3 种方案的理论计算开销对比

表6 3 种方案的理论存储开销对比

由表6 可以看出，在KeyGen 阶段，需要存储公私钥、图像加密密钥以及系统秘密参数。假设用户个数为1，存储开销随图像拥有者个数和特征向量维数增加而增加。在KeyTrans 阶段，存储开销随图像拥有者个数增长而增长。该阶段存储开销在方案改进前后不变。在IndexGen 阶段，索引存储开销和图像总数呈正相关。当给定图像个数时，图像特征向量的维数会影响索引存储开销。在TrapdoorGen 阶段，考虑一个用户的一次查询，陷门存储开销主要受向量维数影响。根据以上4 个阶段的存储开销分析可以看出，改进方案比基础方案的存储开销大是由特征向量维数增加造成的，但增加的维数与图像明文特征向量维数对比可以忽略。与MIPP 对比，本文方案存储开销受较多因素影响，但从后续实验可看出本文方案存储开销是可接受的。

7.2.3 实际性能

为测试本文方案的实际性能，基于Corel100 数据集[31]，从每一类中分别取20、40、60、80、100幅图像组成2 000、4 000、6 000、8 000、10 000 幅图像，并提取图像的CLD 特征[32]。实验环境为PC机（i5-4590 主频3.3 GHz，内存为4 GB，操作系统为Win7 64b），实验工具采用Python2.7。图4～图8展示了本文方案在KeyGen、KeyTrans、IndexGen、Search 这4 个阶段以及检索精度上与MIPP 的比较。由于本文着重研究加密图像检索方法，而不是图像加密方法，且陷门生成本质上为索引生成n=1 的情况，因此文中没有测试 ImgEnc、ImgDec 和TrapdoorGen 这3 个阶段的开销。

在KeyGen 阶段，假设一个拥有者对应一个加密密钥，从图4(a)可看出，MIPP 的时间开销增幅最大。基础方案和改进方案的时间开销非常接近，说明特征向量维数变化对时间开销影响很小。特别地，当用户个数分别为1 和10 时，改进方案生成50 个密钥所需时间分别为1.7 s 和1.9 s 左右。图4(b)中本文方案存储开销增长缓慢。特别地，当用户个数分别为1 和10 时，改进方案生成50 个密钥所需存储空间分别为243 KB 和251 KB 左右。虽然维数增多导致开销增长，但同时也提高了方案的安全性。

图4 KeyGen 阶段

图5 KeyTrans 阶段

在KeyTrans 阶段，仅考虑本文方案开销，如图5所示，特征向量维数变化不影响基础方案和改进方案的开销。随着用户数增加，需要的转换密钥相应增加。特别地，当用户个数分别为1 和10 时，转换50 个密钥所需时间分别为8 s 和68 s 左右，所需存储空间分别为160 KB 和1 400 KB 左右。为实现多密钥场景，密钥转换时间和存储开销随密钥个数增多是不可避免的。但这只是一次性操作，相比于图像加密所带来的巨额开销是可接受的。

在IndexGen 阶段，如图6 所示，时间开销和存储开销随图像总数增多而增加。本文方案索引生成时间开销明显少于MIPP，存储开销增加是因为存储了加密向量。方案改进前后增长趋势接近，说明向量维数增加带来的影响很小。特别地，当图像总数为10 000 幅时，方案改进前后生成索引所需时间分别约为117 ms 和123 ms，所需存储空间分别约为10.5 MB 和11.5 MB。

图6 IndexGen 阶段

在Search 阶段，仅考虑检索时间开销，如图7所示。方案改进前后的时间开销很接近，说明向量维数变化不会明显影响检索时间。随图像总数增加，检索时间增长趋势不明显，这是因为局部敏感哈希有效缩短了检索时间。随着拥有者数量增多，导致服务器需要做更多的密钥转换，本文方案时间开销多于MIPP。尽管如此，本文方案在多密钥场景下搜索10 000 幅图像仅耗时0.26 s，这是可接受的。

图7 Search 阶段

图8 检索精度

综上所述，虽然本文方案时间开销和存储开销受图像加密密钥个数和用户个数影响较大，但是对于实现多密钥场景来说，这是不可避免的。同时，为了提高方案安全性，加入冗余项之后的改进方案比基础方案性能稍有恶化，但是依然在可接受的范围内。因此，本文方案在实际应用中是可行的。

8 结束语

本文针对边缘计算环境下的图像隐私安全问题，借助于边缘计算低时延、高可用、高实时的优势，设计了一种支持多密钥的加密图像检索方案。应用局部敏感哈希算法对图像进行了预处理，提高了检索速度。利用安全近邻算法加密图像特征，使边缘服务器可以直接计算图像之间的相似度并排序，提高了检索精度。同时利用代理重加密技术进行密钥转换，管理用户访问不同加密密钥加密的图像集。方案分析表明，本文方案达到了安全目标，可抵抗已知背景攻击，并且在实际应用中是可行的。进一步研究工作将会结合实际需求对方案的查询功能进行扩展。