高效隐私保护的多用户图像外包检索方案

王祥宇，马建峰，苗银宾

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

1 引言

随着数码相机、智能手机、医疗影像设备等成像设备的发展，图像数量呈爆炸性增长。从大规模图像数据集中检索特定的图像在疾病检测与诊断[1]、网上购物和社交网络[2]等许多实践领域受到越来越多的关注。

但是，每个图像由成千上万个特征点组成，大规模图像检索业务给许多公共服务组织或公司带来巨大的资源消耗。例如，即使患者已经离开，医院也需要存储患者的所有医疗图像；社交媒体平台需要将所有用户的照片存储在他们的相册中。随着云计算的发展，许多企业和组织目前更愿意在公有云平台上托管他们的数据和服务，这样既可以节省基础设施投入，也能更好地提供服务。但是，由于许多图像中包含敏感信息，将图像直接外包给公有云可能会导致隐私泄露甚至引起法律纠纷[3]。

为了解决这一问题，Shashank等[4]提出了一种基于内容的图像检索（CBIR, content-based image retrieval）方案，该方案保护了查询图像的隐私，但是图像数据集是未加密的，导致数据集内容直接暴露给云服务器。为此，Lu等[5]首次在加密图像域上构建了隐私保护的CBIR方案。该方案通过提取视觉词汇来表示图像，使用Jaccard相似度来评估2个图像之间的相似性，并采用保序加密和最小散列算法来保护视觉词的信息，但该方案仅适用于视觉词表示的图像检索算法，其准确度比基于Fisher向量的图像检索算法低 20%以上[6-7]。尽管基于同态加密的方案可以保证检索准确度，但是通常会产生很大的时间和存储开销[8-10]。为了实现高效准确的CBIR方案，Xia等[11]一方面采用安全k近邻（kNN，k-nearest neighbors）算法[12]来保护特征向量，使云服务器能够高效地对检索结果进行排序；另一方面在牺牲检索准确度的前提下使用局部敏感散列建立双层索引来提高检索效率。Yuan等[13]同样使用安全kNN算法来保护Fisher向量[6-7]，并通过K-means聚类算法提高大规模数据检索效率，该方案对加密图像的检索效率和准确率接近明文图像检索的性能。但是，由于安全kNN算法使用对称密钥加密，在多用户场景下，各个用户可以相互解密查询请求，这带来了极大的隐私泄露威胁。为此，Zhang等[14]使用一种多级同态加密协议设计了一个支持多用户的图像检索系统，每个用户使用不同的私钥加密查询请求，保证了隐私性，但是该方案带来了巨大的通信开销和计算开销。

为了实现一个高效隐私保护的多用户图像检索方案，需要解决以下关键挑战：1）所有图像特征向量都应加密，检索过程应以非交互方式完成，所有存储和大部分计算应外包给公有云平台，且要求公有云平台无法获取图像、特征向量和检索结果的隐私信息；2）每个用户应该持有不同的加密密钥，这样即使用户的请求被截取了，也无法获得请求内容；3）每个用户要能够对云端存储的所有图像进行检索，以便满足大规模数据共享的需求。

本文提出的方案很好地满足了以上需求，表 1显示了本文的方案与文献[13-14]方案的对比情况。可以看到，与这种方案相比，本文的方案具有更低的存储要求和计算量，同时还能满足多用户需求。

表1 3种方案的开销对比

2 系统模型、安全威胁模型及设计目标

2.1 系统模型

如图1所示，所提方案主要考虑5个实体：云服务器（CS，cloud server）、数据拥有者（DO，data owner）、检索用户（SU，search user）、密钥转换中心（KCC, key conversion center）和可信代理（TA,trusted agent）。

图1 系统模型

1）DO是图像数据的拥有者，在外包图像之前先把图像特征提取出来构建加密检索索引，然后把密文索引和使用对称加密算法（如AES）加密的图像一起提交到CS。

2）CS拥有大量的存储空间和计算资源，为用户提供存储和计算服务。

3）SU根据所需检索的图像内容生成检索请求提交给KCC，并从CS得到检索结果。

4）KCC是独立的第三方，拥有一定的计算能力，为其他实体提供密钥转换服务，包括索引和查询请求的转换。

5）TA是可信的第三方，给系统中的各个实体分配密钥。

2.2 安全威胁模型

在提出的方案中，CS和KCC是“好奇而诚实”的，即CS和KCC将遵循给定的协议来执行服务，但它可能会分析用户的数据以获取额外的敏感信息。DO和SU被认为是诚实的，并且不会与CS及KCC“勾结”。KCC是独立的第三方，其不会与任何一方“合谋”。这些假设与大多数关注公共云中加密数据检索的现有相关工作一致[12-15]。根据云服务器的可用信息，在数据的隐私保护方面考虑以下 2种威胁模型。

1）已知密文模型。CS只能访问所有加密的图像，加密的可检索索引和加密的检索请求。CS不能对图像数据集进行学习，可检索索引中的特征向量信息对CS也是保密的。

2）已知背景模型。在这个更强的威胁模型中，CS拥有已知密文模型中的所有信息[12-15]。另外，CS可以提取数据集中特定加密图像的统计信息，如检索频率，甚至可以获知数据集中的一些图像，但是不知道图像的明文-密文对。

2.3 设计目标

1）高效性。系统必须满足高效性，即具备很低的通信和计算开销，同时具有高准确度。

2）多用户。系统必须支持多个用户同时对云服务器的图像集进行安全检索，即在检索过程中，用户无法获取其他用户的请求信息，也无法获得索引内容。但是，用户可以对CS上的所有图像进行检索，这使本文方案可以实现大规模多源数据共享。

3）隐私保护。为了保证用户数据的隐私不被泄露给云服务器，必须满足下列隐私需求。

① 图像安全性：提出的方案必须保证原始图像数据集对CS保持机密，同时对SU是可用的。这可以使用对称加密（即AES等）来解决，下文中不再叙述。

② 索引和请求机密性：必须保证CS不能通过索引或请求来推断出图像的内容注1本文不考虑访问权限的控制问题，即假设对于所有检索到的结果，SU都可以解密。访问控制可以通过基于属性的加密技术在所提方案上进行扩展。。

③ 查询请求的不可链接性：在检索过程中，攻击者不应该能够判断2个或多个检索是否来自同一个检索请求。

3 图像检索方案设计

本节首先提出一种高效的单用户图像检索方案。随后，为了支持多用户图像检索，提出了一个多用户密钥转换协议，从而实现多用户图像检索。表2定义了要使用到的符号，另外定义2个描述符。

表2 符号含义

定义 1对任意表示最接近x的整数，

定义2对任意向量/矩阵表示其中元素绝对值的最大值。

3.1 单用户图像检索方案

在图像检索方案中，使用主成分分析（PCA，principal components analysis）[15]算法对图像的Fisher矢量[6-7]进行降维，作为相似度匹配的依据，并使用欧式距离来衡量相似度。为了实现数据隐私保护，引入了隐私保护的欧氏距离比较技术[16]。通过该技术，可以以一种安全的方式比较2个加密向量与同一向量之间欧氏距离的大小。该技术的细节在图像检索方案中进行介绍。

单用户图像检索方案主要包括4个算法：密钥生成（KeyGen）、索引生成（IndexBuild）、查询生成（QueryGen）和图像检索（ImSearch），具体如下。

1）KeyGen算法。TA随机选择一个2m×2m的可逆矩阵M，并生成加密密钥 S K={M，M-1}，然后通过安全信道将SK分发给DO和SU，其中M-1为M的逆矩阵。

2）IndexBuild算法。首先，对于每一个图像，DO首先提取出特征向量将其使用同样比例→化为整数（例如，同时乘以10 000）。然后，DO将扩展为2m维，如式（1）所示。

其中，α1, α2,…,αm-1∈ℤp是由DO随机选择的整数，整数p代→表数值范围。完成扩展之后，DO对每一个索引进行加密，如式（2）所示。

新增长点是发展新经济培育新动能、激发新活力过程中的主要着力点是支撑经济的高成长性领域。近年来，新能源汽车、无人驾驶等研究、生产实现“爆炸式”增长，是汽车行业的新增长点，也带动了相关技术、产业链相关行业的发展，孕育产生巨大的新动能。“大众创业、万众创新”带动新经济蓬勃发展，引领服务业、高新技术产业、中小微企业和民营企业等释放新动能。此外，还有共享单车、网络零售、跨境电商等新业态新模式，通过新技术的应用，形成新增长点，带来新动能。

为了在多用户图像检索场景下满足用户隐私需求，要保证不同的DO/SU无法解析其他DO/SU的索引内容/查询内容，因此他们持有的密钥应该不同。与此同时，要保证每一个SU能够对CS中存储的所有索引进行检索。由于使用对称加密方案，CS接收到的查询与索引必须使用相同密钥加密才能完成欧式距离比较。为了满足以上需求，设计了一个多用户密钥转换协议。

3.2 多用户密钥转换协议

3.2.1 密钥分配

首先，TA随机选择一个2m×2m的可逆矩阵M，则加密密钥SK={M，M-1}，其中M-1为M的逆矩阵。对于每一个数据拥有者DOi，生成用户密钥MOi以及转换密钥M'Oi，满足M=MOi M'Oi。同样地，对于每一个检索用户SUi，生成用户密钥MUi以及转换密钥M'Ui，满足M-1=M'UiMUi。通过安全信道，将MOi、MUi分发给对应的DOi、SUi，将转换密钥M'Oi、M'Ui分发给密钥转换中心KCC。

3.2.2 密钥转换协议

图2 密钥转换协议

转换完成后，KCC把转换后的密文索引发送给CS 。

4 方案安全性分析

本节对提出方案的安全性进行分析。首先，定义并证明本文所使用加密方案的安全性；然后，根据第3节中提出的隐私需求对本文的图像检索方案进行安全性分析；最后，分析多用户密钥转换协议的安全性。

4.1 安全性定义

本文提出的图像检索系统中使用的加密方案由 Yuan等[16]基于误差学习（LWE，learning with error）问题[17]提出，安全性已经得到证明。下面简要回顾该方案的安全性证明，以便进行后续的方案安全性分析。

定义3LWE问题：给定一个维数m≥2，模上的概率分布χ。给定的任意多个抽样

其中，误差εi∈χ。以不可忽略的概率恢复矢量在计算上是不可行的。

推论1若LWE问题是困难的，则对于一个敌手来说，从本文使用的加密方案加密的或中恢复明文在计算上是不可行的。

证明在本文的加密方案中，每一个索引的加密方式为

由于索引和请求的加密方式类似，因此简便起见，只使用来进行证明。在都是都是2m维的向量，他们与M的乘积可以认为是4m2次2m维的向量内积

1）已知密文模型。在这个模型下，由于 CS只能得到加密索引和加密请求的访问权，根据推论 1，CS从其中恢复明文是计算不可行的。

2）已知背景模型。Yao等[18]对安全kNN这类欧式距离保持算法提出了线性分析攻击。该攻击能够成功的前提是CS要获得足够多的明-密文对。在已知背景模型下，CS虽然能获得一些明文图像样本，但他并不知道明-密文对。即使CS获得一些图像的明文密文对，本文中使用的特征提取算法参数及PCA的降维参数是不公开的，因此CS无法从图像中得出对应的特征向量，因此无法完成线性分析攻击。

4.2 图像检索方案安全性

下面根据3.3节提出的隐私保护需求从三方面对图像检索方案进行分析。

1）图像安全性：本文提出的方案中，原始图像数据集是使用AES进行加密的，故图像的安全性可以得到很好的保证。

4.3 多用户密钥转换协议安全性

在多用户密钥转换协议中，加密密钥SK被分解成用户密钥和转换密钥，分别分配给 DO/SU和KCC。在本文方案中，KCC与系统中的其他实体是不共谋的，所以DO/SU和KCC都无法获得SK。这样，在索引生成/查询生成阶段，DO/SU使用用户密钥对数据进行加密，每个由于用户密钥是相互独立的，即使用户截获了其他人的检索索引也无法将其解密从而获得原始数据。另外，KCC只有转换密钥，同样无法解密用户的索引/查询请求。最后，由于CS存储的索引和收到的查询请求都是用SK加密的，因此CS可以对所有图像进行检索，满足功能需求。

5 方案性能分析

本节对提出的多用户图像外包检索方案的性能进行分析。为了对方案性能进行仿真，本文使用Python实现了本文提出的方案。为了更好地进行性能比较，同样用Python实现了SEIS[11]作为对比方案。测试环境为Ubuntu 16.04 LTS 操作系统，3.3 GHz Intel Core（TM）处理器，4 GB RAM。本文使用著名的INRIA Holidays数据集[15]进行准确度测试，该数据集同样用于很多其他图像检索工作的仿真[6-7,11,14]。这里设提取的Fisher向量的维度为4 096。

5.1 检索准确度

为了验证方案的检索准确度，选择了文献[18-19]这2个明文图像检索方案和SEIS作为对比方案。这里采用的准确度测试指标为应用广泛的平均精度（MAP，mean average precision）[19]。

图3 不同特征维度下检索准确度对比

从图 3可以看出，本文方案与文献[18-19]这2种明文方案的准确度接近。由于本文方案与SEIS采用相同的特征向量提取方式，因此准确度相同。可以看到，当特征向量维度小于512时，准确度增长明显，特征向量维度大于512时，准确度趋于平缓。因此，推荐使用大于512的特征向量维度。

5.2 存储和通信开销分析

本文方案的存储开销以及通信开销与已有方案的对比如表3所示。

表3 存储和通信开销对比

1）存储开销：定义|e|为索引或查询向量中元素的位宽，一般为64 bit。假设有n个图像存储在云服务器中，每个图像的索引向量为m维。在本文提出的方案中，每个索引向量会被扩展为 2m维向量并加密，由于多密钥方案并没有对云端存储的索引做改变，所以单用户和多用户方案的索引存储开销均为2mn|e|。而在SEIS方案中，每个索引向量除了被扩展为2m维向量，在加密过程中还被分裂成2个，因此存储开销为4mn|e|。

2）通信开销：在单用户和多用户方案中，检索请求都被加密为2m维向量。不同的是，单用户方案的请求直接发送到CS进行检索；而多用户方案中的请求需要先发送到 KCC进行密钥转换，然后再发送给 CS。因此，单用户方案的通信开销为2mn|e|，而多用户方案为4mn|e|。由于SEIS方案中每个查询请求被加密为2个2m维向量，所以SEIS方案的通信开销为4mn|e|。

综上所述，本文提出的2种方案存储开销均优于SEIS，只有SEIS的一半。单用户方案的通信开销为SEIS的一半，多用户方案的通信开销与SEIS相同。

5.3 计算开销分析

本节对比本文提出的方案和 SEIS的各个算法的算法复杂度，然后对它们的运行时间进行仿真。为了方便描述，使用 DOT2m来定义2个2m维向量的内积操作，即：给定2个向量和它们之间的一个内积操作为由于计算开销与 DOT操作相比十2m分微小，忽略单个的加法操作和取模操作。为了实现满足多用户检索需求，在单用户方案基础上加入了密钥转换协议，为了更好地比较单用户与多用户方案的计算开销，使用KeyTrans算法来指代密钥转换过程。

计算复杂度对比如表4所示。在本文的方案中，IndexBuild过程的算法复杂度为 2mnDOT2m，如式（2）所示，在加密过程中每个索引向量都需要内积一个2m×2m矩阵，这相当于进行了 2mDOT2m操作，那么加密n个索引花费 2mnDOT2m操作。在 SEIS中，每个索引向量首先被分裂成2个向量，然后2个向量分别内积2m×2m矩阵进行加密，因此加密n个索引花费 4mnDOT2m操作。如式（4）所示，QueryGen过程中的加密方式与IndexBuild中类似，单用户方案需要 2mDOT2m操作来进行查询加密，而SEIS需要 4mDOT2m操作。值得注意的是，为了实现满足多用户检索需求，多用户方案加入了KeyTrans过程。如式（9）和式（11）所示，每转换一个索引（查询）该算法执行 2mDOT2m操作，因此多用户方案同样需要 4mDOT2m操作。ImSearch过程中，如式（5）所示，CS使用查询向量→对每一个索引）进行内积操作，在本文方案中，算法复杂度为nDOT2m操作。由于在加密时进行了向量分裂，SEIS的算法复杂度为 2nDOT2m。

表4 计算复杂度对比

图4绘制了特征维数从128到4 096，图像数量为20 000时，IndexBuild算法的运行时间。可以看到，所有方案的运行时间都随着维度的增长而增长。单用户方案运行时间约为SEIS的一半，多用户方案运行时间与SEIS类似，这与理论分析一致。从图 5可以看出，当特征向量维度为 512时，各种方案IndexBuild的运行时间随着图像数量的增加线性增长。其中，单用户方案的运行时间约为SEIS的一半，多用户方案运行时间与SEIS类似。

图4 不同特征维度下IndexBuild运行时间

图6绘制了特征向量维度从128到4 096时，QueryGen算法的运行时间。从图中可以看到，所有方案的运行时间都随着维度的增长而增长。本文的单用户方案运行时间约为SEIS的一半，多用户方案运行时间与SEIS类似，查询生成时间小于150 ms，可以满足高效性需求。

图5 不同图像数量下IndexBuild运行时间

图6 不同特征维度下QueryGen运行时间

从图7可以看出，当特征向量维度为512时，各种方案 ImSearch的运行时间随着图像数量的增加线性增长。与IndexBuild一样，单用户方案的运行时间约为SEIS的一半。因为密钥转换导致的时间消耗，多用户方案运行时间与 SEIS类似，对10万个图像的检索时间不到200 ms。

图7 不同图像数量下ImSearch运行时间

图8绘制了特征维数从128到4 096，图像数量为10 000时，ImSearch算法的运行时间。可以看到，所有方案的运行时间都随着维度的增长而增长。单用户方案运行时间约为 SEIS的一半，多用户方案运行时间与SEIS类似。

图8 不同特征维度下ImSearch运行时间

6 结束语

为了高效地解决多用户图像检索系统的隐私保护问题，本文首先提出了一种高效隐私保护的单用户图像检索方案。该方案可以达到与明文方案接近的检索准确度，与 SEIS相比，其存储开销、通信开销和计算开销均降低了一半。另外，为了满足多用户图像检索需求，本文提出了一个多用户密钥转换协议。通过该协议，数据拥有者或检索用户可以使用自己独有的密钥加密检索索引或请求，保证了索引或请求的隐私性。同时，检索用户可以对云服务器上的所有图像进行检索，保证了大规模多源数据的共享。严格的安全性分析表明本文方案可以满足用户隐私保护需求。基于真实数据集上的实验验证了本文方案的高效性，使用本文提出的方案对10万张图像进行检索的时间不到200 ms。因此，本文所提方案在实际的多用户场景中是可行的和高效的。