一种支持动态可验证的密文检索方案

杜瑞忠，王 一，田俊峰

(1.河北大学 网络空间安全与计算机学院，河北 保定 071002；2.河北大学 河北省高可信信息系统重点实验室，河北 保定 071002)

云存储是当下一种主流的在线存储方式，免去了用户本地存储的硬件与管理开销。但是数据脱离了用户的物理控制，导致数据安全受到巨大威胁。为了解决云存储的数据安全问题，学者们提出了可搜索加密作为安全搜索的核心技术。

可搜索加密[1-4]是一种支持用户在密文中进行关键字检索的新技术，主要解决云存储环境下如何利用不可信的服务器实现基于关键字的安全搜索，使用户能够将加密的数据存储到云中，并通过密文域执行关键字搜索，有选择地从云中检索感兴趣的文档，为用户节省了大量开销。然而以上方案全是假定服务器是诚实、好奇的实体，但在现实世界中，云服务器可能因为外部攻击或者内部配置错误，返回错误或者不完整结果，从而对用户进行欺骗。考虑到以上问题，可验证搜索加密方案[5-9]进入到学者视野，这些方案使得用户可以对结果进行验证，进而判断服务器是否为恶意服务器。

但是数据集并不是一成不变的静态环境，如何在动态环境下对结果进行验证，成为学者需要考虑的首要问题。文献[10]将时间戳引入到验证过程中，实现了在文档动态环境下的验证，但是其搜索复杂度超过了线性时间。随后，研究人员通过将索引对应的消息认证码(Message Authentication Codes，MAC)存储在树形结构中[11-12]，通过对根节点的验证来实现对结果的验证。但是，每一次更新需要重新计算树上所有相关节点，对数据拥有者来说计算开销巨大，并且以上方案是在单用户模型下实现，仅包括数据拥有者与服务器两个实体。

在动态可搜索加密方案中，前向安全和后向安全是两个重要的安全属性，可以确保在更新数据时不会发生信息泄漏。文献[13]首先提出了关于前向安全和后向安全的概念。随后，学者们在具有前向安全的搜索加密方案[14]的基础之上，设计了一种可验证的前向隐私搜索加密方案[15]。后向安全作为动态搜索加密方案中一个重要的安全属性，在文献[16]中首次被提出，并在文中对后向安全给出了形式化的定义。但是，以上方案不能很好地解决一对多模型下的访问控制问题。

随着区块链的兴起，因其不可篡改的性质，逐渐进入大家的视野。2017年，LI等[17]提出了一种基于区块链的可搜索加密方案，但是该方案把加密数据和索引全部上传到区块链中，增大了存储开销。HU等[18]提出了更加完善的搜索加密过程，并且实现了索引的动态更新。但是此方案并没有对云服务器更新之后的数据进行验证，无法保证用户得到正确结果。2019年，CHEN等[19]将区块链下可搜索加密应用到具体场景中。同年，JIANG等[20]使用椭圆曲线加密函数，实现了数据拥有者和用户之间的秘密授权，但是该方案同样没有保证用户得到正确结果。LI等[21]将时间锁技术和区块链相结合，实现了单关键字的加密搜索，但是对于大量数据上传到区块链中仍然存在困难。最近，CHEN等[22]在其方案中实现了前向和后向安全，但是并没有很好解决一对多模型下授权访问问题。李涵等[23]将验证过程交由区块链处理，但是其方案仅考虑了前向安全，并且对于云服务器是否诚实删除文档没有进行考虑。

基于以上问题，笔者提出了一种基于区块链的动态可验证密文检索方案，旨在解决动态环境下可搜索加密的数据隐私和结果正确性问题。主要贡献如下：

(1) 通过利用以太坊中的智能合约，将搜索和更新操作交给智能合约执行，以确保返回结果的正确性。此过程同时支持前向和后向安全，保证数据更新时不会泄漏任何相关信息。

(2) 利用以太坊外部账户的基本特性，提出了一种新的授权访问模型。通过将授权信息加密打包进一笔交易的方式，完成了一对多模型下的授权访问。并且在这种模型下，攻击者无法通过更新之前的陷门获得数据更新后的任何信息。

(3) 将该方案部署到本地私有网络(Ganache)中，对大量真实数据集进行分梯度实验。实验结果分析表明，该方案在索引生成、搜索效率以及验证时间具有一定优势。

1 预备知识

1.1 区块链及相关知识

以太坊是一种基于区块链的分布式可计算平台，其支持图灵完备的编程语言。以太坊的安全性主要依靠解决困难问题(或者说是区块)，矿工会通过解决困难问题来获得奖励，保证了以太坊中的任何操作都是透明且可靠的。而智能合约作为以太坊中的一部分，也随之提出。

智能合约是部署在区块链上的一些特殊脚本代码，即使其创建者也无法进行修改，并且可以根据内容自动执行。发布智能合本质上就是将一笔交易发布到区块链中，区块链中所有矿工会进行工作，当挖出包含此智能合约的区块时，区块链中的所有节点都会保存此智能合约。而矿工也会得到奖励，奖励由gaslimit×gasprice决定，其中，gaslimit为发送方可以支出的最多燃料，gasprice为发送方为每个燃料支付的费用。由于每个节点都会存储智能合约，所有存储的数据和智能合约的已执行计算对任何用户都是透明且不可篡改的。对于所有需要在可信环境下进行的操作，理论上都可以使用智能合约来执行。

1.2 外部账户

外部账户(Externally Owned Account，EOA)也叫账户，以太坊中外部账户由密钥生成，可以调用智能合约和发送交易，也可以存放以太币。每个账户都有一个地址，这个地址由私钥和公钥所控制。私钥先经过椭圆曲线数字签名算法得出对应公钥，然后公钥进行Keccak-256哈希运算，截取最后20字节即为账户地址。账户每次发起的交易，都会显示发送方地址和接收方地址。

1.3 聚合消息认证码

由于以太坊中gaslimit的限制，普通消息认证码的存储开销太大且效率低下，并不适用于智能合约。因此，可以通过减少MAC数量的方式，降低智能合约中消息认证码相关计算量，从而实现提高搜索效率和避免超过gaslimit的目的。基于以上思想，聚合消息认证码(Aggregate MACs，AMAC)被引入到文中。举例而言，给定两个数据消息认证码对(m1，δ1)和(m2，δ2)，其中，δi=Auth(K，mi)。将两个消息认证码进行异或操作，得到聚合消息认证码，

φ=δ1⊕δ2。

(1)

当对这两条数据(m1，m2)进行验证时，只需对φ进行验证即可。

文中符号说明如表1所示

表1 符号定义

2 系统模型

2.1 系统简介

图1 方案模型图

系统模型主要由4个部分组成。数据拥有者(Data Owner，DO)，云服务器(Cloud Server，CS)，区块链系统(Blockchain)，以及数据用户(Data Users，DU)，如图1所示。

(1) 数据拥有者：主要负责将明文数据加密，并提取加密索引和AMAC。将密文数据上传到云服务器，加密索引和AMAC上传到智能合约中，用户请求搜索时，对数据用户进行授权并发送授权信息。

(2) 云服务器：主要负责密文数据的存储，并根据数据用户上传的加密索引集合下发密文数据集合。

(3) 区块链系统：主要负责接收并存储数据拥有者发送过来的加密索引以及AMAC，接收数据用户上传的陷门，并根据陷门进行查询，将查询结果下发到数据用户。

(4) 数据用户：向数据拥有者请求授权后得到授权信息，并将授权信息上传到区块链中。根据查询结果，请求云服务器下发密文数据，最后进行本地验证。

2.2 安全目标

(1) 机密性：由于本方案中索引存储在智能合约中，对任何实体而言都是透明且公开的，所以需要预先对索引进行加密，避免外部攻击者可以获得有关索引的任何有效信息。

(2) 前向与后向安全：在动态搜索加密方案中，需要支持前向与后向安全，才可以保护数据发生更新时不泄露有关索引信息。其中，前向安全指的是当添加了包含先前搜索的关键字的文档时，攻击者无法通过之前的陷门获取有关该文档的相关信息。后向安全是指当一篇之前增加的文档被删除后，这篇文档不会在后续的搜索过程中泄露相关信息。

(3) 可验证性：由于恶意云服务器可能返回错误结果，所以需要保证返回结果的可验证性。可验证性意味着当返回的结果是错误时，该结果以及对应的证据无法通过验证。

2.3 威胁模型

由于区块链的公开性，其中存储的数据和智能合约的计算是公开的，根本没有隐私可言。因此，可能存在攻击者通过分析区块链中存储的数据或交易信息来获取敏感信息。此外，云服务器可能由于某些原因无法执行数据拥有者发出的更新操作，并将错误结果返回给数据用户。其中包括以下情况：

(1) 数据拥有者添加了一个文档，但是云服务器没有执行添加操作。当数据用户搜索该文档中包含的关键字时，云服务器选择伪造一篇文档将其返回给数据用户。

(2) 数据拥有者会更新某篇文档的内容，但云服务器并没有执行更新操作。当数据用户搜索此文档中包含的关键字时，云服务器将更新之前的文档返回给数据用户。

(3) 云服务器并未按照数据拥有者的要求删除某篇文档。当数据用户搜索此文档中包含的关键字时，云服务器将本应删除的文档返回给了数据用户。

3 系统描述

3.1 初始化阶段

Setup(λ)→Para，SK：输入安全参数λ，生成公开参数和本地参数。安全哈希函数包含以下函数(h1，h2，h3，h4，h5，H1，H2，H3，G)，其中，h1：{0，1}λ→{0，1}2λ，h2：{0，1}λ→{0，1}λ+logNmax，h3：{0，1}λ×{0，1}logNmax→{0，1}2λ，h4：{0，1}λ×{0，1}logNmax→{0，1}2λ，h5：{0，1}λ×{0，1}2λ-logNmax→{0，1}2λ以及H1：{0，1}*×{0，1}*→{0，1}2λ-logNmx，H2：{0，1}λ-1→{0，1}2λ，H3：{0，1}λ-1→{0，1}λ，G：{0，1}*×{0，1}*→{0，1}λ-1；随后生成伪随机置换函数P：{0，1}λ×{0，1}λ→{0，1}λ(P-1为P的反函数)。最后，广播公开参数Para={h1，h2，h3，h4，h5，H1，H2，H3，P，P-1}，数据拥有者初始化一个映射空集Map，将本地参数SK={G，Map}保存在本地。

3.2 更新数据阶段

如图2所示，为了节约存储成本和保护索引中文档标识符数量，笔者采用了打包技术，将DB(wi)addition和DB(wi)deletion中的文档标识符打包进块。

图2 打包索引图

(2)

算法1数据更新算法。

输入：打包索引数据库PDB：{OP，PID，W，AM}；安全哈希函数(h1，h2，h3，h4，h5，H1，H2，H3，G)；伪随机置换函数{P，P-1}以及本地状态映射Map。

输出：存储到智能合约中的映射集合EDB。

① For eachwi∈W

③ if Map[wi]=⊥ then

⑤ end if

⑨ 数据拥有者更新保存在本地的映射图Map；

在本算法中，c为版本指针，用来指示关键字wi的更新状态次数。从表面来看，更新的数据以键值的方式存储在区块链中，并且各自密文之间彼此无关。但是包含相同关键字的密文之间具有隐藏关系，如图3所示。其中最近更新状态依次指向之前的更新状态，并且每个更新状态还对应着本次全部的更新索引。

图3 隐藏关系图

3.3 授权阶段

用户检查最近区块中的交易，并检查地址是否为数据拥有者，若是，则用自己私钥SKuser解密获得授权信息Q={Twi，c，Kf，Km}。

3.4 搜索阶段

Search(Para，Twi，EDB)→RI，α：输入公共参数Para，数据用户调用智能合约并发送陷门Twi，随后智能合约执行算法2。

算法2数据搜索算法。

输入：安全哈希函数(h1，h2，h3，h4，h5，H1，H2，H3，G)；伪随机置换函数{P，P-1}；查询关键字生成的陷门Twi；存储在智能合约的映射集合EDB。

输出：打包索引集合RI；AMAC结果α。

① 智能合约初始化一个空集RI，将α置为0；

② keywi=H2(Twi)；

③ valwi=EDB[keywi]；

⑥ While EDB[keylen]≠⊥ do

⑦ vallen=EDB[keylen]；

⑨ Forj=1 to m do

经过搜索算法过程，智能合约将RI和α存储在日志中并发布出去。

3.5 解密阶段

3.6 验证阶段

Verify(I，Km，α)→ 0 or 1：用户上传I到云服务器，云服务器根据I，将对应的密文文档集合发送给用户。随后用户在本地计算密文文档集合的AMAC，

α+=δ1⊕δ2…⊕δi。

(3)

如果α+=α，则输出1，代表通过验证环节，密文文档集合正确并进行解密；否则输出0，意味着没有通过验证环节。

4 安全分析

4.1 适应安全

采用文献[22]的安全模型，在有状态的模拟器和攻击者之前采用模拟游戏。游戏中的泄露函数定义为，

L=(LSetup，LUpdate，LAuthorization，LSearch) ，

(4)

定义1将本文方案定义为Ⅱ= (Setup，Update，Authorization，Search)，S代表模拟器，A表示攻击者。随后定义了以下两个游戏。

只要文中方案Ⅱ对所有攻击者存在以下公式，即可满足自适应安全定义。

(5)

其中，negl(λ)为可以忽略函数。

定理1如果P是一个安全的伪随机置换函数，并且所有安全的哈希函数具有抗冲突性质，那么文中的方案Ⅱ是自适应安全的。

在游戏G2中，维护一个列表SL，其中，SL[w，c]=stc，而不是通过P(Kc，stc-1)生成stc。在更新环节，当需要stc时，游戏随机选取一个字符串stc={0，1}λ。因为伪随机置换函数是安全的，所以非常简单得出G2和G1是不可区分的。

|Pr[G2=1]=Pr[G1=1]| 。

(6)

在游戏G3中，将所有安全哈希函数转化为随机预言机，并维护一个列表用来存储每个预言机的输入与输出。举例而言，给定一个输入x，随机预言机随机选取一个字符串y=h1(x)作为输出，然后将其插入到列表h1-L。因为哈希函数具有抗冲突性，所以得出G3和G2是无法区分的。

|Pr[G3=1]=Pr[G2=1]| 。

(7)

在游戏G4中，在更新环节并没有使用G(wi，c)生成Tagwi，而是采用一个随机字符串Tagwi={0，1}λ。同时游戏需要维护一个列表，用来响应攻击者A的授权查询，其中列表存储的为(wi，Tagwi，c)。如果攻击者可以区分，则可以得出

|Pr[G4=1]-Pr[G3=1]|≤Pr[Bad] ，

(8)

其中，Bad表示攻击者A可以区分随机字符串和Tagwi的概率，这个概率为2-λ+negl(λ)。攻击者最多进行次q1=poly(λ)猜测，其中，poly( )不是特性多项式。随后，通过以上公式可以得出Pr[Bad]≤q12-λ+q1negl(λ)。可以看出，概率为可忽略的函数，因此得出G4和G3在计算上是不可区分的。

在最后一个游戏中，模拟器使用泄露函数从攻击者A的视角进行模拟，其中泄露函数包含搜索模式和更新历史。从攻击者的角度来看，G5和G4的行为是一样的。通过以上分析可以得出，G5和G4是无法区分的。

(9)

通过以上分析，可以得出

(10)

因为Pr[Bad]是可以忽略的函数，所以笔者提出的方案满足自适应安全。

4.2 前向安全

4.3 后向安全

4.4 可验证性

文中方案的验证方法与文献[12]的类似，因此给出如下定义。

定义2定义一个可验证搜索加密方案为Ⅱ=(Setup，Update，Authorization，Search)。其中，A表示攻击者，实验Forge可以表示为如下：

证明：假设攻击者A可以找到(C*，w，α*)∉R。如果攻击者A可以得到Verify(C*，w，Km，α*)=1，需要满足以下条件：

攻击者A可以找到一个元组{C*，w，δ*}，并非通过消息认证码生成公式δi=Auth(fi，Km)输出的，但是可以通过验证公式Verify(C*，w，Km，α*)=1。定义如果攻击者A成功地完成本次实验，则等价于可以伪造一个消息认证码通过验证，这种通过的概率定义可以表示为Pr[ForgeA Ⅱ]。因为，本方案中消息认证码生成函数是安全的，所以攻击者可以伪造消息认证码通过验证的概率为可以忽略的。根据以上等式可以得出

(11)

综上所述，本方案满足可验证性定义，证明完毕。

5 性能分析

5.1 功能对比

将文中方案与上述文献对比，如表2中所示。

表2 功能对比

文献[12]方案支持动态更新，并对更新结果可以进行验证，但此方案只能在单用户模型下进行，并且每次更新时也需要对Merkle Hash Trees更新，增加了数据拥有者的计算开销。文献[11]方案可以支持数据拥有者-云服务器-用户模式下搜索加密，但是需要在这三者之间同步时间戳链，即使数据没有进行更新，也需要定时发送证据到云服务器上。对于少量更新时，为维护时间戳链产生了许多额外开销，并且每次更新需要查找Merkle Patricia Tree，对叶子节点进行更新。对于文献[11]和文献[12]，每次搜索过程还需要对验证所需要的证据进行搜索，更新过程需要先完成对证据的搜索，然后再对证据进行更新。

文献[18-20，22]都是基于区块链平台下进行，将搜索过程放入到智能合约中。文献[19]是在静态环境下进行，并不支持动态更新操作。文献[18]与文献[20，22]均支持动态更新，但是对于用户从云服务器中下载的数据正确性，和云服务器中数据是否及时更新没有考虑。文献[18]虽然在增强方案中提到支持一对多模型，但没有对如何进行授权和用户上传搜索信息进行说明。文献[20]中只有增加和删除操作，并没有考虑对原始数据的更新。

由于文献[11-12]是一般化验证方案，其中并没有包含具体完整的可搜索加密方案，所以无法知道其是否支持前向与后向安全。文献[18]方案没有涉及到数据更新，所以也就无法定义其是否支持前向与后向安全。文献[18，20]方案中，均不支持前向与后向安全。虽然文献[22]考虑了前向与后向安全，但由于其陷门构造使用公钥加密，没有很好的解决授权问题。

从功能上分析，该方案不仅实现了一对多模型下授权访问功能，而且对于云服务器不诚实更新数据情况，用户可以进行本地验证。在保证以上功能的同时，也支持前向与后向安全，大大提高了数据的安全性。

5.2 实验分析对比

该方案实验环境为64 bit windows 操作系统，Intel®Core(TM) i5-4570 CPU 3.20 GHz、内存16 GB。文中使用Enron Email数据集作为原始数据集，提取出6 560篇文档作为测试数据集。实验中，智能合约使用solidity语言，与智能合约交互语言为javascript语言。数据拥有者方面使用python对数据集提取关键字并生成索引，利用160-bit ECC对授权信息进行加密。智能合约部署到本地测试网络Ganache对其进行性能测试。实验中，安全哈希函数基于SHA256构造，伪随机置换函数使用AES (CBC模式，128-bit密钥)，并且MAC生成算法采用HMAC-SHA256，加密文档集合则使用AES对称加密算法。

由于文献[11-12]并不是具体的可验证搜索加密方案，且实验平台不是基于区块链，所以选择基于智能合约且与近两年的文献[18，20，22]进行了对比。实验从3个方面进行对比：索引生成时间、搜索时间和验证时间。在每一个数量级进行50次反复试验，求出时间开销的平均值，保证实验结果的准确性。

图4 索引加密时间

首先，在索引加密的时间成本方面，将笔者提出的方案与其他方案进行了比较。如图4所示，索引加密时间随着关键字数量的增加而增加。由于笔者提出的方案与其他方案相比增加了验证功能，因此有必要在索引加密阶段添加AMAC的计算和加密。其次，由于图4仅显示了文献[18，20]中的方案初始数据集上传部分，而本方案中将初始数据集也看作一次数据更新，并增加了前向和后向安全。综合上述原因，本方案在索引加密阶段会比文献[18，20]中的方案计算代价略高。随着关键字数量的增加，笔者提出方案的索引加密时间比文献[22]中的方案更加高效。造成这种差异的主要原因是文献[22]中的方案没有使用打包操作，并且所有索引都需要加密，这将导致巨大的开销。

如图5所示，随着匹配索引数量的增加，文中方案的搜索算法的时间成本比其他方案更低。此结果的主要原因是，文献[18，20]方案在执行搜索操作时，需要对原始数据索引和更新数据索引分别进行搜索，搜索结果中的每个文档标识符还需要依次进行额外的哈希运算，检查其是否删除从而返回最终结果。由于文献[22]中每条索引只对应一个文档标识符，所以在搜索过程中需要对所有索引进行搜索，而本方案只需要对打包索引进行搜索即可，显著提高了搜索效率。

由于文献[18，20，22]中并没有对返回结果的验证，所以将本方案与文献[11-12]进行验证时间方面的对比。如图6所示，文中方案在验证时间开销明显低于其他方案，主要原因在于，文中方案只需要本地进行一次哈希运算和异或运算即可。对于文献[12]来说，除了对返回结果进行哈希运算外，还需要对返回路径上的节点进行运算，进而对Merkle Hash Trees的根节点进行验证。文献[11]除了对Merkle Patricia Tree的根节点进行验证外，还需要对认证标志进行新鲜度验证。并且文献[11]中的方案在实际应用中，会存在百毫秒级别的验证延迟，这种延迟主要是由更新间隔造成的，对于用户体验并不是很好。

图5 搜索时间

图6 验证时间

6 结束语

在可搜索加密的基础上，笔者将区块链与可搜索加密相结合，提出了一种基于区块链的动态可验证密文检索方案。文中方案主要应用于需要确保数据绝对安全的私有云环境，例如机密机构的数据库。通过以太坊账户的特性，可以实现一对多环境下的授权访问控制。依靠以太坊的特性，解决了恶意服务器返回结果的正确性问题。并且针对云服务器不更新数据问题，文中方案通过引入聚合消息认证码技术，创新性地解决了数据更新时对返回结果的验证。文中方案还支持前向和后向安全，确保了数据更新时不会泄露任何隐私。同时针对方案中索引生成、检索和验证3个方面进行了实验测试。测试结果显示本方案具有较高的效率。

接下来的工作将会针对可搜索加密如何在区块链环境下，实现多关键字和关键字排序等更加灵活的查询方式，让用户得到更加准确的返回结果。