云环境下安全的可验证多关键词搜索加密方案

张键红，武梦龙，王晶，刘沛，姜正涛，彭长根

（1.北方工业大学信息学院，北京 100144；2.贵州大学公共大数据国家重点实验室，贵州 贵阳 550025；3.京东集团财税创新部，北京 100176；4.中国传媒大学计算机与网络空间安全学院，北京 100024）

1 引言

作为云计算的一种重要服务[1]，云存储[2]为解决企业和个人的海量数据存储提供了一个途径，使用户能够摆脱沉重的本地数据计算和管理负担。然而，将大量敏感数据（如财务文档、电子医疗记录等）以明文形式存储在远程不可信云服务提供商（CSP,cloud service provider）上，会给用户的数据隐私安全带来潜在隐患。为此，在数据外包给远程服务器之前，数据拥有者需要对数据进行加密。这样能够抵制不可信CSP 的数据泄露，从而实现外包数据的隐私安全[3-5]。然而，加密却破坏了明文间消息的关联性，给数据的搜索带来极大困难。为了解决这个问题，对称可搜索加密（SSE,symmetric searchable encryption）技术[6]被提出，它允许数据所有者根据指定关键词进行搜索。尽管对称可搜索加密能够实现较高的搜索效率，但是并不能提供公开可验证性。为了解决该问题，Boneh 等[7]提出了基于公钥的可搜索加密方案，该方案是一种单关键词可搜索加密。由于该方案只能对单关键词进行搜索，因此搜索精度不高，还可能会返回一些不相关的结果。为了节省带宽和计算资源，缩小查询范围，可搜索加密（SE,searchable encryption）应该支持多关键词搜索，才能避免返回不必要的加密文件。

Golle 等[8]首次提出了基于连接关键词的可搜索加密方案，在该方案中，关键词的陷门长度与加密文档的数量呈线性关系，使搜索的通信开销过高、实用性较低。为了解决该问题，Ballard 等[9]构造了一种基于双线性映射的多关键词可搜索加密方案，在该方案中，尽管关键词陷门具有固定长度，但是搜索每个文档需要执行2 次双线性映射运算，使方案的计算耗费巨大。Ryu 等[10]提出了一个高效的、基于双线性映射的多关键词可搜索加密方案，在该方案中，关键词陷门具有固定长度，能够降低计算开销。Cao 等[11]利用内积相似性问题提出了一种可排序的多关键词搜索加密方案。该方案能够对搜索结果进行相关度排序，提高了搜索结果的匹配精度。但每一次搜索请求时，存储服务器都需要遍历所有文档索引，使服务器计算负担较重。

理论上，CSP 应该诚实地根据协议规定来保障外包数据的机密性和完整性。然而，在现实中，为了降低管理负担和计算压力，云服务器可能会返回不正确或不完整的搜索结果。这意味着数据所有者的外包数据可能存储在一个不可信的云服务器上。因此，为了保证搜索结果的正确性，可搜索方案应该提供完整性验证机制[12-14]。同时，为了不削弱云存储的优势，应使结果验证的计算开销尽可能小。为了实现以上功能，Miao 等[15]提出了一种新的高效多关键词可搜索加密方案，该方案不仅能实现多关键词搜索，还能实现密文的完整性验证。尽管该方案被证明是安全的，但是该方案不能抵制搜索模式的隐私泄露。已知2 个搜索令牌T=(T1,T2)和T′=(T'1,T'2)，云服务器能够通过判定关系式是否成立来确定这2 次的搜索关键词是否一样。

实现文件的前向安全性和搜索模式的隐私性是搜索加密方案亟须解决的2 个问题，现有大多数搜索方案都不满足这2 种特性。前向安全性能够确保云服务器不能了解新插入文件的相关信息，也就是说，云服务器不能利用已有的搜索陷门来测试新插入文件是否包含对应的关键词。搜索模式的隐私性能够确保云服务器不能区分数据用户2 次提交的搜索陷门是否对应于相同的关键词。这2 个问题的存在给现有可搜索加密方案带来巨大安全隐患。此外，为了确保云端服务器上外包文件的安全性，应该将公开审计技术[16-17]扩展到SE 方案中来提升方案的安全性。为了解决以上问题，基于分级身份加密、哈希链技术和带密钥的哈希函数[18-19]，本文在云环境下设计了一种高效的可验证多关键词可搜索加密方案，该方案不仅能实现对多关键词搜索，也能实现对云端密文的完整性验证；此外，还能实现搜索模式的隐私保护和文件的前向安全性。

所提可验证多关键词可搜索加密方案本质上是一种连接关键词搜索。具体而言，本文的主要研究工作可概括如下。

1) 多关键词搜索。本文所提方案允许数据拥有者对多个关键词进行搜索。

2) 搜索结果的完整性验证。本文所提方案满足搜索结果完整性验证，通过结果验证机制，能够防止CSP 返回不准确的搜索结果。

3) 标准模型下的安全性。通过形式化安全分析，本文所提方案能够在标准安全模型下被证明是安全的，能够抵制抗密钥猜测攻击（KGA,keyword guesswork attack），安全分析表明，本文所提方案是有效的、安全的。

4) 搜索模式隐私保护。本文所提方案能够阻止云服务器通过搜索陷门来猜测关键词的具体信息。

5) 前向安全性。在本文所提方案中，云服务器不能利用已有陷门信息来测试新插入的密文文件是否包含相应的关键词，但仍能利用更新后的陷门信息对原有密文文件和新插入密文文件进行搜索。

2 云环境下多关键词可搜索加密系统

本节将介绍云环境下多关键可搜索加密的系统模型、威胁模型，然后给出最终的安全设计目标。

2.1 系统模型

一个云环境下的多关键词可搜索加密系统包含云服务器、数据拥有者、用户和审计者4 类实体。其系统模型如图1 所示。

图1 系统模型

云服务器。云服务器具有丰富的存储空间和强大的计算能力，负责为用户存储数据和执行文件搜索服务。

数据拥有者。数据拥有者希望把数据文件加密后外包到远程云服务器上。

用户。数据使用者需要经数据拥有者授权，并向云服务器提交关键词搜索请求以获取相关文件。

审计者。审计者负责对外包到云服务器的数据进行完整性验证。

2.2 设计目标

为了确保能够对密文进行有效的搜索，本文所提方案的主要目标具体如下。

1) 支持多关键词搜索。为了能够准确地定位相应密文，所提方案应该同时支持多关键词搜索。

2) 抗关键词猜测攻击。当关键词空间较小时，攻击者能够发动关键词猜测攻击，为此，要确保所提方案能够抵制攻击者的猜测攻击。

3) 密文的完整性。确保在不可信云服务器上存储的密文不能被云服务篡改，以确保密文的完整性。

4) 前向安全性。确保不可信云服务器不能通过已有搜索令牌，来获得新插入文件的任何信息。然而，能够利用新的搜索令牌来搜索满足搜索关键词的所有文件。

5) 搜索模式的隐私性。云服务不能通过2 个搜索令牌来判定所对应的关键词是否一样。

2.3 算法定义

一个多关键词可验证搜索加密方案包括以下几个算法。

Setup(1k)→(Para)。这是一个确定性算法，输入一个安全参数k，输出系统公开参数Para。

KeyGen(Para)→（PKD,SKD,PKC,SKC）。该算法是一个概率算法，输入系统公开参数Para，输出数据拥有者的密钥对（PKD,SKD）和云服务器的密钥对（PKC,SKC）。

Enc(Para,PKD,SKD,PKC,F,W)→{SigF,IF,π}。该算法是一个概率算法，输入系统公共参数Para、数据拥有者的密钥对（PKD,SKD）、云服务器的公钥PKC以及关键词集W和文件集F，输出签名集SigF、索引集IF和报头π。

TrapdoorGen(Para,SKD,W′,L)→{T}。该算法是一个概率算法，输入系统参数、数据拥有者的私钥SKD和关键词集W′以及关键词的位置信息L，输出搜索令牌{T}。

Insert(Para,PKD,SKD,PKC,F,W)→{SigF,IF,π}。该算法是一个概率算法，输入公共系统参数Para、数据拥有者的密钥对（PKD,SKD）以及关键词集W和新插入的文件集F，输出签名集SigF、索引集IF和报头π。

Search(Para,T,L,IF,SKC)→(C′,FID′)。该算法是一个概率算法，输入系统参数Para、云服务器的私钥SKC、索引集IF、关键词的位置信息L和搜索令牌T，云服务器调用该算法来进行文件匹配，最后，返回满足条件的密文C′和文件标识FID。

Verify(Para,C′,FID′)→1/0。该算法是一个交互式算法，需要审计者与云服务器执行一个交互过程，与远程数据完整审计方案中的审计过程一样，如果通过验证返回1；否则，返回0。

2.4 安全模型

对于一个关键词可搜索加密而言，关键词的空间相对较小，这使许多可搜索加密方案易遭受字典攻击和离线关键词猜测攻击。此外，在一个可搜索加密方案中，由于不可信云服务器拥有密文和搜索陷门信息，它是一个攻击性较强的内部敌手。因而，对于一个可搜索加密方案，如果能够抵抗不可信云服务器的安全攻击，那么该方案就是安全的。下面，给出云服务器关键词猜测攻击的安全模型定义。

定义1安全模型。令k是一个安全参数，A 是一个多项式时间攻击者，敌手A 与挑战者C之间的交互游戏定义如下。

系统建立阶段。C输入一个安全参数k来调用Seup 算法和KeyGen 算法，产生系统公开参数Para、数据拥有者密钥对（PKD,SKD）以及云服务器的密钥对（PKC,SKC），发送(Para,PKD,PKC,SKC)给敌手A。

阶段1

陷门询问阶段。敌手A 能够自适应地选择一个关键词集{w1,…,wd}发布陷门询问。C 调用TapdoorGen 算法产生陷门（d0,d1），并把它返回给敌手A。

插入询问。敌手A 能够自适应地选择一个文件F和相应的关键集W来发起插入询问，C能够利用公共参数Para 和(PKD,PKC)产生一个密文集、索引集和签名集，并把它们返回给敌手A。

挑战阶段。敌手A选择2个含有m个元素的关键词集(W*0,W*1)发起挑战。C随机选择一个比特b∈{0,1}，并调用Enc 算法来产生搜索索引I*b。最后，C发送I*b给敌手A。

阶段2

陷门询问阶段。像阶段1 的挑战阶段一样，敌手A 能够自适应地选择关键词集{w1,…,wd}发布陷门询问。限制条件为关键词集(W*0,W*1)不能被发布陷门询问。

猜测阶段。A 返回一个猜测的比特b′∈{0,1}。当b′=b时，敌手赢得该游戏。敌手A 能够赢得该游戏的优势定义为=Pr[b′=b]−1/2。

3 具体方案构造

为了方便理解方案的设计，表1 总结了本文所用符号。

表1 本文所用符号

3.1 系统建立阶段（Setup）

输入一个安全参数k，该阶段调用setup(1k)算法输出一组双线对密码参数（G1,G2,e,p,g1,g2），其中G1和G2是2 个阶为p的乘法循环群，p是一个大素数，e:G1×G1→G2是一个双线性对映射，g1和g2是群G1的2 个随机生成元。H1:{0,1}*→G1，H2:{0,1}*→Zp和f:{0,1}*→Zp是3个密码哈希函数。然后，随机选择r0∈Zp和hi∈Gl（i=0,1,…,l），其中l表示一个文件所包含关键词的最大个数。最后，系统公开参数被公布为

3.2 密钥产生（KeyGen）

对于数据拥有者，它随机选择一个数d∈Zp作为密钥，并计算其公钥PKD=。对于云服务器而言，它也随机选择一个数c∈Zp作为密钥，并计算其公钥

最后，数据拥有者和云服务器分别保存相应的私钥SKD=d和SKC=c。此外，数据拥有者还要选择一个随机数θ∈Zp秘密保存，并且计算一个哈希链（f1,f2,…,fχ），其中fi=f(fi−1(θ))和f0=（f θ）。

3.3 加密和认证标签产生（Enc）

在该阶段，数据拥有者不仅需要对多个关键词加密来建立搜索索引，还需要产生外包文件集F的认证标签。其具体过程如下。

1) 为了方便陈述，假设首次外包文件集F0中包含n个文件，并且每个文件都包含m个关键词，即F0={F01,…,F0n}，W={w1,…,wm}。

2) 选择一个安全的对称加密算法 Enc=（Ek,Dk），并计算文件F0j的密文C0j=Ek(F0j)，i=1,…,n。

3) 随机选择sb∈Zp计算

3.4 文件插入（Insert）

令Fi表示第i次插入的文件集，为了表述方便，不妨设该文件集也包括n个文件，并且每个文件都包含m个关键词，即Fi={Fi1,…,Fin}，W={w1,…,wm}。为了插入该文件集，数据拥有者计算如下。

1)利用安全对称加密算法Enc=(Ek,Dk)来计算文件Fij的密文Cij=Ek(Fij)，i=1,…,n。

2) 然后，随机选择sb∈Zp计算

作为签名公钥。接着，对于文件集Fi中的文件，即对于j=1,…,n，计算每个文件Fij的认证标签

3.5 陷门产生阶段（TrapdoorGen）

3.6 搜索阶段（Search）

当接收到用户提交的搜索令牌T=(d0,d1,fχ−i)和位置信息L后，云服务器执行搜索算法，如算法1所示，其具体步骤如下。

3.7 验证阶段（Verify）

该阶段的目的是验证外包在云端的密文是否被云服务器篡改。为此，审计者需要与云服务器执行一个交互过程，具体步骤如下。

4 安全性分析

本节将对本文所提方案的正确性和安全性进行分析。为了方便理解，首先，回顾一下本文方案所基于的数学难题——基于截断决定性双线性Diffie-Hellman 安全假设（truncated decisionalq-augmentedbilinear Difffie-Hellmanexponent(q-ABDHE)problem）[19]。已知一组元素，判断关系式是否成立是一个困难问题。

正确性对于整个协议，如果每个实体都能按照协议规定正确地执行协议，那么，式(17)和式(20)一定成立。这就意味着，授权用户一定能获取满足关键词的相应密文。

因为对于式(17)，依据算法1 可知

因此，当式(17)成立时，这就意味着有效的搜索令牌一定能匹配到满足条件的密文文件。

对于式(20)，依据算法1 可知

这意味着，如果所返回的密文没有被篡改，那么，式(20)一定成立。

定理1在q-ABDHE 假设下，本文所提方案能够安全地抵制KGA。

插入询问。当敌手用一个含有n个文件集F和关键词集W进行文件插入询问时，C执行3.4 节中的文件插入算法来得到以下密文

来猜测出与之对应的关键词。因此，本文所提方案能够实现搜索模式的隐私保护。证毕。

定理3在离散对数安全假设下，不可信服务器不能在外包密文被篡改情况下，产生一个证明信息Prof，使其通过审计者的验证。

证明因为本文中采用的完整性验证方案是基于Shacham 和Waters 的远程数据完整验证方案[12]。而该方案在安全模型下被证明是安全抵制云服务器的篡改和删除攻击，因而，本文所提方案也能够抵制相应攻击。

定理4在哈希函数的单向性条件下，本文所提方案能够实现前向安全性。

证明在本文所提方案中，采用哈希链来实现文件的前向安全性。在第i次文件插入时，哈希链中的哈希值fχ−i被嵌入文件密文中，即

当第i次文件被插入以后，用户的搜索令牌是T=(d0,d1,fχ−i)，其中嵌入了哈希链中的fχ−i哈希值，这使云服务器仅能搜索第i次插入文件集。为了实现对第i次插入前的文件进行搜索，云服务器需要计算

然后，利用T=(d0,d1,fχ−i+1)来搜索第i−1 次插入的文件集。依次类推，云服务器能够搜索第i次前所有满足关键词集的所有文件。

然而，对于云服务器，尽管它拥有第i次文件插入前的搜索令牌，例如，第i−1 次文件插入后的搜索令牌为T=(d0,d1,fχ−i+1)，它仍然不能利用(d0,d1,fχ−i+1)来对新插入的文件进行搜索，因为新插入文件的密文中嵌入了哈希值fχ−i，由于哈希函数f的单向性，云服务器不能通过哈希值fχ−i+1来获得fχ−i。因而，它不能通过式(21)来判断搜索令牌是否匹配新插入的文件，从而实现了方案的前向安全性。

5 效率分析

本节将从理论角度来对所提方案的效率和功能进行分析。为了更好地说明本文所提方案的性能，本节将通过与3 种多关键词搜索加密方案[13-15]比较来分析本文所提方案性能。为了简化分析，在下文的分析中，仅考虑耗时的密码运算。令E 表示在群G1或G2中的指数运算，M 表示乘法运算，P表示对运算，H1表示一个比特串映射到群G1中元素的map2point 运算。表3 给出了本文所提方案与文献[13-15]方案的效率比较，其中，n表示文件的个数，m表示关键词集中的元素个数，l表示所询问的关键词个数，d表示返回的搜索结果，“___”表示不具有该功能，search model 表示搜索模式是否满足隐私性，leak 表示不满足，anonymity表示满足。forward security 表示方案是否满足前向安全性。

表3 几种方案的效率比较

从表3可知，就算法KeyGen、Trapdoor和Search而言，与其他2 种方案相比，本文所提方案和文献[15]方案具有更小的计算开销。就Enc 算法而言，本文所提方案是所有方案中计算量最小的方案，这是因为在本文所提方案中最耗时的对运算独立于文件和关键词个数，对运算不会随着关键词的数量和文件的数量的增加而增多。同时，从表3 中可以发现，本文所提方案和文献[15]方案在效率上基本一致。在陷门产生阶段，本文所提方案比文献[15]方案需要较多的计算量。然而，本文所提方案能够实现搜索模式的隐私保护，具体原因在定理2 中被分析。但是文献[15]方案不能实现搜索模式的隐私保护，因为在文献[15]方案中，搜索令牌T=(T1,T2)具有如下形式

因此，对于 2 个搜索令牌T=(T1,T2)和T′=(T′1,T′2)，如果它们包含同一组关键词集，那么，云服务器可以通过验证

来判定这2 个搜索令牌T和T′是否包含同样的关键词。从而泄露了搜索模式的相关统计信息。此外，文献[15]方案也不能抵制恶意云服务器的离线猜测攻击，对于含有n个元素的关键词集，云服务器能够以概率猜测出相应的关键词集。当关键词空间相对较小、搜索关键词个数较多时，云服务器能够以较大概率猜测出关键词。此外，文献[15]方案不支持文件的前向安全性，这使云服务能够利用已有的搜索令牌来搜索新插入文件是否包含相应关键词，从而泄露新插入文件的相关信息。

本文所提方案通过引入一个带密钥的哈希函数来有效地抵制恶意云服务器的离线关键词猜测攻击，因为云服务器不知道密钥θ，使它不可能产生一个，所以能够阻止云服务器的离线关键词猜测攻击。此外，为了实现前向安全性，本文所提方案采用一个哈希链，然后借助哈希链的单向性来实现本文所提方案的前向安全性。

综上所述，本文所提方案在陷门产生阶段尽管计算量比文献[15]方案大，但也优于文献[13-14]方案，并且所增加的计算量是由计算力丰富的云服务器完成的，而没有增加用户的任何计算负担。此外，就方案的功能而言，本文所提方案不仅能实现搜索模式的隐私保护和文件前向安全性，还能抵制云服务器的离线关键词猜测攻击。而文献[15]方案不能实现搜索模式的隐私性和插入文件的前向安全性，也不能抵制云服务器的离线关键词猜测攻击。通过牺牲一点计算代价换取方案的功能增强和安全性增强是值得的。这就意味着，本文所提方案就综合性能而言是4 种方案中最好的。

6 实验分析

为了评估本文所提方案的实际性能，本文实验在一台1.5 GHz 主频、Broadcom BCM2711 处理器、2 GB 内存、Raspbian 操作系统的树莓派上进行。每个算法运行100 次，最后，通过取平均数来得到以下所有实验数据。

在加密阶段，4 种方案的计算开销与关键词个数和文件个数呈线性相关，如图2 和图3 所示。同时，由图2 和图3 可知，本文所提方案与文献[15]方案对应的直线斜率都低于文献[13-14]方案所对应的直线斜率，这意味着本文所提方案和文献[15]方案在计算开销上优于文献[13-14]方案。

图2 n=2 000 时加密阶段的计算开销

在陷门产生阶段，本文所提方案与文献[13-15]方案都与关键词的个数呈线性关系，如图4 所示。由于在文献[15]方案中，所有关键词只是进行加法运算，而加法的计算开销几乎可以忽略，所以在图4中，文献[15]方案的计算量几乎呈一条水平直线。尽管在陷门产生阶段，本文所提方案的计算开销劣于文献[15]方案的计算开销，但本文所提方案仍优于文献[13-14]方案。

图3 m=200 时加密阶段的计算开销

图4 陷门产生阶段的计算开销

在搜索阶段，本质上，本文所提方案与文献[13-15]方案的计算开销都与关键词个数呈线性关系，如图5 所示。

图5 搜索阶段的计算开销

然而，在文献[15]方案和本文所提方案中，与关键词数量相关的运算只有乘法运算，而乘法运算具有较低的计算开销，因此，在图5 中，文献[15]方案和本文所提方案几乎呈一条水平直线。同时，由图5 可知，本文所提方案的计算效率也优于文献[13-15]方案。

7 结束语

本文提出了一种新的可验证多关键词可搜索加密方案，它既能支持密文的完整性验证，又能支持多关键词搜索，同时，还支持文件的前向安全性和搜索模式的隐私保护。与以往的可搜索加密方案相比，本文所提方案能够在标准模型下被证明是安全的，且能够抵制不可信云服务器的离线猜测攻击，并且该方案是一种基于公钥环境下支持文件前向安全的可搜索加密方案。在未来的研究工作中，将探索设计有效地支持更丰富语义表达的密文搜索方案。