基于错误学习的自适应等级可搜索加密方案

张 恩，侯缨盈，李功丽，李会敏，李 钰

(1.河南师范大学 计算机与信息工程学院，河南 新乡 453007；2.“智慧商务与物联网技术”河南省工程实验室，河南 新乡 453007)

0 引言

随着云计算与大数据时代的到来，越来越多的数据拥有者将海量数据存储在云端以节省本地资源，同时还利用云计算强大的计算能力对数据进行检索操作。不仅如此，企业或机构还在云端建立自己的分等级系统，在保证用户可以对数据高效搜索的同时，还能对不同用户进行等级控制，使不同等级的用户只能检索到其所属等级下的信息数据，但是存储在云端的数据随时可能会泄露给云服务提供商，此类用户隐私数据泄漏造成的安全问题层出不穷，并给用户造成严重的后果，因此，如何在享受云计算带来便捷服务的同时，保护用户隐私数据的安全性是目前亟待解决的关键问题。

为了保护数据的安全性，数据拥有者通常在数据外包给云服务器之前对其进行加密；但是加密后如何对密文域进行操作成为一项新的挑战。可搜索加密技术，把共享给用户的密文数据连同加密关键字列表同时上传至云服务器，用户产生关键词陷门，利用该陷门直接对云服务器上的密文进行关键词搜索，无需将密文文件下载至本地先解密再进行搜索，从而在实现隐私数据保护的前提下，有效地提高了对云上数据的操作速度，并且释放了用户的本地资源空间。这一技术是目前密码学领域中的热点研究内容，在工业、医疗、物联网等方面具有广泛的应用。

Boneh等[1]首次提出公钥可搜索加密(Public Key Encryption with Keyword Search, PEKS)理论并给出几种具体的构造方案，此后公钥可搜索加密技术有了很多新的发展。董晓蕾等[2]围绕可搜索加密的新理论、新方法和新技术，针对可搜索加密的模式、安全性、表达能力和搜索效率等方面进行综述，并指出该领域当前研究中需要解决的问题及发展趋势。文献[3-6]分别针对移除安全信道、抵抗离线关键词攻击、取消身份证书以及对多密钥加密文件搜索与验证的问题作出了一定贡献，但是，以上方案仅适用于单用户环境，并不能满足现今实际生活对多用户环境下可搜索加密方案的需求。苗银宾等[7]针对多数据拥有者场景，提出一种多数据拥有者认证的密文检索方案。该方案结合线性秘密共享与可搜索加密技术，使得数据用户只有得到多个数据拥有者的授权才能解密返回的结果；但是，该方案基于双线性Diffie-Hellman问题，不能有效抵抗量子攻击。白平等[8]针对云环境中信息检索过程可能存在伪造查询结果以及密钥泄露的问题，构造了一种支持用户撤销的可验证密文检索方案。该方案通过对关键词签名以及运用验证算法和用户撤销算法对检索结果进行验证，通过重加密机制实现了用户撤销，从而保证了系统的安全性；然而，该方案基于判定性Diffie-Hellman问题构造，同样不能有效抵抗量子攻击。

在多用户场景下，可搜索加密技术也有很多新的发展，Wang等[9]提出的方案优点在于通过使用基于属性的分层加密模型，从而提供细粒度的访问控制和完整的授权。Lee等[10]提出的方案优点在于将数据分为数据共享和关键词搜索两层，从而实现分层的可搜索加密。Wang等[11]提出的方案优点在于通过定义基于ID分层的可搜索加密方案，从而实现对后代的关键词搜索。文献[9-11]不仅适用于多用户环境，并且实现了不同定义的分层可搜索加密，避免了所有用户共享的内容是相同的，对不同用户的权限进行区分，但是，当不同情景下需要对访问控制粒度有所改变，例如对某一(或多个)层级用户或者文件更新时，需要对某一个(或多个)等级进行大规模添加或删除，以上方案都不能灵活实现该功能。

Shor[12]证明量子计算机可以在多项式时间内解决离散对数和质因数分解问题，这表明现有的公钥可搜索加密方案都将受到量子计算机的攻击。针对此问题，Regev[13]首先提出能够抵抗量子攻击的基于格上错误学习(Learning With Errors, LWE)的密码系统，从此LWE问题成为后量子时代的开端。由于基于格上难题构造的方案目前尚未找到量子多项式算法，因此可以有效抵抗量子攻击，并且格密码具有高效的实现，只需要在一个适当的模块上进行简单的加法和乘法操作。自格密码被提出至今，已有人提出了基于格的签名方案、密钥交换协议以及多密钥全同态方案[14-16]等，因此，格上的密码系统已经成为抗量子攻击可搜索加密工作的一种必然选择。

Gu等[17]和Hou等[18]首先将可搜索加密技术与抗量子算法结合，提出格上的PEKS方案，成为单用户环境下抗量子可搜索加密的基础方案；但该方案较为简单，无法适用于多用户环境。Zhang等[19]针对安全信道的设置并不实际，从而成功移除安全信道，优点在于通过指定服务器搜索及返回结果，安全性较高且实际可行；但该方案只考虑了单用户环境，不适用于多用户环境。Yang等[20]提出的方案不仅实现了格上模糊关键词搜索，优点在于利用广播加密技术将单用户环境拓展至多用户环境，对批量用户提供云服务；但方案中用户仅被区分为被授权与未授权，没有明确的等级划分，不能实现分等级的数据搜索。Zhang等[21]提出面向代理的基于身份加密的可搜索加密方案，优势在于通过授权代理代表原数据拥有者加密数据并将其外包给云服务器，从而减轻原数据拥有者的数据处理负担；但该方案是单用户环境的，并不适用于多用户环境。Xu等[22]提出多写入者格上可搜索加密方案，该方案允许用户直接使用他们的身份进行数据加密，从而降低密钥管理的复杂性。该方案的优点在于解决了多数据拥有者使用不同加密密钥加密数据带来的密钥管理复杂的问题，且首次实现了基于LWE的可搜索加密方案；但该方案主要针对多对一(多数据拥有者-单数据用户)场景，并未考虑多用户场景。

本文针对现有分等级的可搜索加密方案不能灵活添加与删除某一个或多个等级以及不能有效抵抗量子攻击的问题，提出一种基于LWE的自适应等级可搜索加密(Adaptive Hierarchical Searchable Encryption based on LWE, AHSE)方案。该方案利用格的多维特点并基于格上LWE困难问题构造，可以有效抵抗量子攻击。首先，通过设置条件键对用户进行明确的等级访问控制，使不同等级的用户可以搜索到其所属等级下对应的文件；其次，设计一种分段式索引结构，使所有用户仅共享一张索引表即可实现搜索操作，无需为每个文件分别建立索引后逐一搜索，从而提高搜索效率；并且，该结构中等级数目可由不同场景对等级粒度的需求自由设定，具有良好的自适应性；最后，方案中用户、文件以及它们所属等级都可灵活更改，适用于动态的云计算环境。

1 基础知识

1.1 格相关知识

1)整数格。

设a1,a2,…,am∈Rm是m个线性独立无关向量，A=[a1,a2,…,am]∈Rm×m表示由m个线性无关向量组组成的m×m维矩阵，m维满秩格L可以由A生成，定义为：

其中：a1,a2,…,am称为格的基向量。

2)高斯分布。

3)错误学习(LWE)问题。

LWE问题允许重复向挑战预言机Ψ进行查询。如果一个敌手能够准确分辨该实例来自Ψ0或Ψ1的优势|Pr[AΨ0=1]-Pr[AΨ1=1]|是不可忽略的，则存在一个多项式时间敌手可以解决判定性LWE问题。

1.2 格密码算法

2 AHSE方案设计

2.1 方案模型定义

一个公司内部的数据加密后放在服务器端，所有合法用户通过可搜索加密技术搜索不同的关键词来获取所需数据。该公司中，所有合法成员都可以作为数据拥有者对数据进行共享操作(场景如图1所示)。该公司将其内部合法用户分为N个等级，其中N可以根据需要的等级粒度自由设定。本文假定N=3，分别为顶层管理者、管理人员和普通员工。该公司的普通员工为第三等级用户，只能访问搜索少量的数据；管理人员为第二等级用户，可访问搜索数据包含第三等级可见数据，但不是公司内部所有的数据；顶层管理者为第一等级用户，能看到公司内部所有数据，包含第二和第三等级的可见数据；非公司内部的员工不能看到企业内部的任何数据。根据该场景，基于LWE的分等级可搜索加密方案由5个必要的通信实体构成：

1)可信中心(Trust Authority，TA)。TA为系统所有合法用户颁发公私钥对，且与代理服务器交互，生成数据拥有者与用户之间的代理重加密转换键。

2)数据拥有者(Data Owner, DO)。DO对文件进行加密后上传至服务器，对关键词进行可搜索加密后构建分段式索引表并上传至代理搜索服务器。

3)数据用户(Data User, DU)。DU确定需要的文件所对应的关键词，利用自己的公私钥对为该关键词生成陷门(搜索令牌)，发送至代理搜索服务器，等待返回结果。

图1 AHSE方案模型Fig. 1 Model of AHSE scheme

4)存储服务器(Storage Service, SS)。SS负责存储数据拥有者的加密后的文件数据，并在搜索成功后，为合法用户返回指定文件。

5)代理搜索服务器(Proxy Search Server, PSS)。PSS负责存储数据拥有者的索引表，并在搜索时对用户的关键词陷门与索引表进行匹配，根据匹配结果，找到对应的文件。

本文建立的模型中，首先由TA为DO和DU分配独立的公私钥对，由DO将加密数据上传至SS，将加密的索引上传至PSS；其次，DU搜索文件时，确定文件所对应的关键词，并对该关键词生成陷门，发送至PSS；然后，PSS将关键词陷门与关键词索引表进行匹配，找到匹配关键词后对DU进行等级匹配，将该等级能读取到的文件标识符发送给SS；最后，SS返回给DU在该权限下的有效文件。

2.2 核心算法定义

本文设计的基于LWE的分等级可搜索加密方案，由参数生成、密钥生成、条件键生成、重加密转换键生成、可搜索加密、陷门生成以及搜索测试等7个算法构成。

1)ParaGen(1n)。输入一个安全参数n，输出系统的公共参数P、主公钥Mpk和主私钥Msk。

2)KeyGen(P,Mpk,Msk,i)。输入系统的公共参数P、主公钥Mpk、主私钥Msk，每个合法用户的唯一身份标识符i，为每个用户生成一个秘密值Ri，输出每个用户的公私钥对(PKi,SKi)。系统内部保存Ri，用于重加密转换键生成阶段构造转换键。

3)ConKeyGen(P,v,t)。输入公共参数P，一个条件向量v和与该条件匹配的断言向量t，输出每一个等级条件项Con并公开，同时输出为每个用户生成的条件键Conkey通过以(PKi,RKc′)的形式创建用户等级控制列表CL(Control List)，并发送至PSS。

4)ReKeyGen(PKi,PKj)。输入TA保存的Pki、PKj对应的秘密值Ri、Rj，输出代理重加密转化键RKi → j。

5)PEKS(P,PKi,w,Con)。输入系统公共参数P、数据拥有者的公钥PKi、关键词w以及等级条件项Con，输出关键词分段式索引结构表I。

6)TrapGen(PKj,SKj,w)。输入私钥SKj和用户查找的关键词w，输出w的陷门e。

7)Test(C,e,RKi → j)。输入用户的关键词陷门e、可搜索密文C以及重加密转换键RKi → j，输出该用户所属等级下对应的文件。

2.3 安全模型构建

本文基于LWE的分等级可搜索加密方案可以通过以下安全游戏建立安全模型。

初始化阶段 初始化系统公共参数P，生成主公钥Mpk与主私钥Msk。

密钥生成阶段 模拟器B运行密钥生成算法KeyGen，生成用户i的密钥对(PKi,SKi)，并将PKi发送给敌手A。

阶段1 敌手A有能力自适应地发出多次查询，但每次只能查询一个问题。

私钥查询 敌手A适应性地多次查询用户私钥，如果查询的用户为条件控制列表内合法用户，模拟器B将该用户的私钥发送给敌手A；若不是合法用户，则拒绝查询。

陷门查询 敌手A可以适应性地多次查询关键词所对应的陷门。选取任意关键词w∈{0,1}*，适应性地向挑战者询问w所对应的陷门Tw。

挑战阶段 敌手A选择两个目标关键词w0、w1和目标身份i*作为挑战对象，发送给模拟器B。其中，目标身份i*的私钥要求在第一阶段未被查询过，对目标关键词w0和w1的要求为不能选择A之前询问过的关键词，即w≠w0，w≠w1。模拟器B随机选取b∈{0,1}，并将对应的密文I=(C1,C2,{Con})发送给敌手A令其挑战。

阶段2 敌手A继续适应性地向模拟器B询问任何满足条件w′≠w0，w′≠w1的关键词所对应的陷门。

猜测阶段 敌手A最终输出b′∈{0,1}，如果b=b′，则定义敌手A赢得了这场游戏。

在这场游戏中，定义敌手A赢得这场游戏的优势为ε=|Pr[b′=b]-1/2|，如果ε可以忽略，则称AHSE方案是抵抗选择关键词攻击的。

3 分段式索引结构

现有带索引的可搜索加密方案虽然在搜索效率上有一定的提升，但并未实现对多用户分等级控制的功能，而现有具有访问控制的可搜索加密方案，通常使用属性加密对用户进行访问控制，搜索时需对每一个文件先进行用户身份的逻辑判断后再匹配关键词，操作略为复杂，而对于分等级的应用场景来说，等级数目可灵活定义，以及等级可以灵活添加与删除的索引结构尤为重要，因此，本文针对分等级的应用场景设计一种分段式索引结构(如图2)，具有以下特点：

图2 分段式索引结构Fig. 2 Segmented index structure

①该索引结构具有分等级搜索功能，明确划分了文件所属的等级范围，使不同等级的用户在进行关键词搜索过程中，即使匹配到同一个关键词，也能返回不同等级下对应的文件。

②该索引结构具有良好的适应性。不同应用场景对访问控制的粗细粒度需求不同，等级数目可以自由设置，有良好的适应性。

③该索引结构设置清晰简洁，文件的更新与删除操作具有独立性，可单一修改而不影响其他文件的访问控制，因此，该结构操作简单灵活，易于维护，适用于动态环境。

④该索引结构能够实现不同等级用户共享同一张索引表，在有效的等级权限控制前提下，无需对每个文件进行逐一搜索，从而可以减少搜索时间，提高搜索效率；并且，该索引结构基于反向索引构造，具有亚线性的搜索效率。

⑤该索引表中的关键词密文、等级控制项与条件键都基于LWE困难问题构建，能够有效保证数据安全性。

3.1 索引表的建立、更新与删除

分段式索引表采用邻接表构建。DO对文档集合建立文件标识符{id1,id2,…,idn}(n为文件总数)。从文件中提取k个关键词，表示为{w1,w2,…,wk}，对其进行加密，即{Enc(w1),Enc(w2),…,Enc(wk)}。建立一个数组，存放每个关键词的加密信息以及等级控制项Con1,Con2,Con3,…(根据实际需要的等级数量设置Con的数目)。对于每一个不同的等级，由此等级控制项Con作为链表头节点，用指针链接该等级下控制的关键词所对应的文件，从而完成索引表的建立。

当用户发送的关键词陷门匹配到某一关键词时，用户被分配的条件键与该关键词所对应的每一个Con控制项进行匹配，当找到该条件键可以匹配的控制项后，按照该控制项的指针读取文件。当不同级别的用户同时匹配到同一个关键词时，由控制项控制不同用户级别，控制相应的指针指向不同的文件节点，从而实现了不同级别的用户可以搜索到不同范围的文件。

更新与删除：当对索引表进行更新时，DO首先判断该文件所属条件控制项，并根据该级别指针的索引插入到链表中对应位置(如图3中在第一等级下添加文件id11,id12,id14，在第二等级添加文件id9,id13,id15)；若需删除文件，首先判断文件是否是控制项指针指向的文件，如果是，则将该指针指向需要删除的下一个文件，并将需要删除文件的前一个文件指针指向需要删除文件的下一个文件；否则，直接将需要删除的文件前一个文件指针指向需要删除文件的下一个文件即可(如图3中在第二等级下删除文件id7)。

图3 不同等级下文件的更新与删除操作Fig. 3 Update and deletion of files at different levels

3.2 等级的自适应性

分段式索引结构中等级控制项Con的数量具有自适应性。为了简化描述，本文假定系统内的合法成员有三个级别，即N=3，对应图2中具有3个等级控制项Con1、Con2、Con3。在实际的应用场景中，可以根据实际需要的等级数量设置N的大小，即粒度可调节。图4展示了等级控制项的更新与删除，只需更新删除对应的等级控制项与其所带的指针即可。显然，该结构可以实现任意数目的等级控制项，因此具有良好的自适应性。

图4 等级控制项的自适应性Fig. 4 Adaptability of hierarchical control item

4 AHSE方案实现

本文提出基于LWE的自适应等级可搜索加密方案，包括参数生成、密钥生成、条件键生成、重加密转换键生成、可搜索加密、陷门生成以及搜索测试7部分，本章展示其具体构造，并在每部分后附上对应的伪码。

算法1 ParaGen。

输入：n,q;

TA do:

A,TRA← TrapGen(q,n)

Mpk←A,Msk←TRA

算法2 KeyGen。

输入：P,Mpk,Msk,i;

For eachDUi,TA do:

算法3 ConKeyGen。

输入：P,v,t;

输出：Con,CL。

TA do:

Definev=(V1,V2,…,Vl),t=(T1,T2,…,Tl),

for each level,TA do:

DefineCon=At·Sv

PublishCon

for eachDUi,TA do:

CreatCL← (PKi,Conkey′)

SendCLto PSS

算法4 ReKeyGen。

输入：PKi,PKj;

输出：RKi → j。

TA do:

算法5 REKS。

输入：P,PKi,w,Gv;

输出：I=(C1,C2,{Con})。

DO do:

ComputeC1←sTARi,C2←sTH(w)

Define File correspond withCon

Creat IndexI=(C1,C2,{Con})

算法6 TrapGen。

输入：PKj,SKj,w;

输出：e。

DU do:

u←H(w)

e← SamplePre(PKj,SKj,u,σ)

sendeto PSS

7)Test(C,e,RKi → j)。代理服务器PSS输入来自PKj发送的陷门，执行以下步骤：

①查找请求搜索的用户是否在访问权限控制列表CL中，如果不存在，直接返回⊥，拒绝服务；如果存在，则找到并提取其对应的条件键Conkey′，执行下一步。

②代理服务器为其请求代理重加密转换键RKi → j，对用户发送的陷门以及关键词密文进行匹配，计算η=C2-C1·RKi → j·e，如果|η|≤q/4，则输出1(“yes”)，否则输出0(“no”)，并执行下一步。

③在索引表中匹配到关键词后执行条件键匹配，计算α=β·Conkey′的文件，等式成立则根据满足匹配的条件项所带头指针地址返回有效的文件。

算法7 Test。

输入：C,e,RKi → j;

输出：File。

PSS do:

if (exit(DUi))

returnConkey′

else return ⊥

requestRKi → j

computeη←C2-C1·RKi → j·e

if |η|≤q/4

output 1

else output 0

ifα==β·Conkey′

returnFile

5 正确性与安全性证明

5.1 正确性证明

本文方案中，每个用户拥有独立的条件键，即使一些用户级别相同，但由于Sc是随机选取的，因此每个用户条件键Conkey′是不同的，保证了每个用户的条件键的随机性，从而使得仅从条件键分析不出用户的等级，保护了用户的权限级别隐私，其正确性为：

[V1G|V2G|…|VlG]·

本方案中，代理服务器收到数据用户发来的关键词陷门e后，查询该用户是否为合法用户，然后为该用户搜索分段式索引结构表，从而进行关键词匹配测试δ=C2-C1·RKi → j·e，其正确性为：

sTH(w)=C2

根据文献[24]中参数相关定义，在|δ|≤q/4时，输出1(“yes”)；否则输出0(“no”)。

5.2 安全性证明

本文AHSE方案依赖于LWE假设。为了证明AHSE的安全性，需要证明如果有攻击者可以破坏AHSE的安全性，那么实际上可以利用一个敌手A来解决LWE问题。由于没有一种概率多项式时间(Probability Polynomial Time， PPT)算法能够以不可忽略的概率解决LWE问题，则表明本文方案是抵抗选择关键词攻击的。

定理1 在随机预言机模型下，假定存在一个PPT敌手A可以以不可忽略的概率优势成功攻破选择关键词攻击游戏，那么可以构造一个PPT算法B可以以不可忽略地概率优势ε成功解决LWE问题。

证明 假设A是一个可以以不可忽略的优势攻破本文方案的敌手。构造一个模拟器B，通过一个随机预言机Ψ，决定输出的样本是从LWE分布中选取(Ψ0)或从均匀随机的分布中选取(Ψ1)。模拟器B模拟挑战者C并与敌手A交互，进行选择关键词攻击游戏的具体过程如下。

阶段1 敌手每次只能查询一个问题，自适应地多次发出以下查询：

陷门查询 敌手A可以自适应地向模拟器B询问对于用户i任意关键词对应的陷门(假定PKi的私钥都已经被查询)。模拟器B通过SamplePre算法构造陷门ei，如果生成成功，挑战者C将ei发送给敌手A；否则终止操作。

阶段2 敌手A继续像阶段1一样发出关键词陷门查询，但仍然不能查询A所要挑战的关键词w0和w1对应的陷门，且目标身份i*的私钥依旧不能在第一阶段被查询过。

猜测阶段 敌手A最终输出猜测b′∈{0,1}。如果b=b′，那么模拟器B输出1，判定A赢得了这场游戏；否则输出0。定义1中定义了敌手A在游戏中的优势为|Pr[b=b′]-1/2|，且随机预言机的采样有以下两种情况：

1)当随机预言机Ψη输出为η=0时，为真实的LWE实例，敌手A的概率优势为ε，其中，η=0，Pr[b=b′|η=0]=1/2+ε。模拟器B攻破判定性LWE问题的概率为Pr[η′=η|η=0]=1/2+ε。

2)当随机预言机Ψη输出为η=1时，为均匀随机采样，敌手A没有概率优势，其中，η=1，Pr[b≠b′|η=1]=1/2。模拟器B攻破判定性LWE问题的概率为Pr[η′=η|η=1]=1/2。

挑战密文的分布在统计上接近真实的安全环境，因为C*是使用判定性LWE实例构造的。如果LWE实例是真实的，则挑战密文C*的分布将与LWE游戏中的分布相同。如果LWE实例是随机的元素，那么C*中的元素也是随机的。从上面的证明可以看出，如果对手A能够打破这个方案，那么挑战者C也可以利用模拟器B的算法攻破LWE问题。已得出模拟器B的优势为ε/2，且定义概率优势ε是不可忽略的，从而得出结论，该算法可以以ε/2的概率攻破LWE困难问题。又已知LWE困难问题是不可攻破的，因此，结论矛盾，前提假设不成立，即，得以证明ε为可忽略的概率，因此，敌手A只能以可以忽略的优势赢得选择关键词攻击游戏，该方案的安全性得以证明。

6 分析与比较

6.1 功能性分析

本文选出近年来可搜索加密领域与本文较为相关的文献[17]方案、文献[18]方案、文献[9]方案、文献[10]方案、文献[19]方案、文献[20]方案，与其功能比较如表1所示。从表中直观看出，本文AHSE方案在多用户环境下实现了公钥可搜索加密、代理重加密、访问控制以及抗量子攻击的功能。具体的分析如下。

表1 不同方案的功能比较 Tab. 1 Function comparison of different schemes

文献[9]、[10]这两个方案考虑到了访问控制，都采用属性加密进行访问控制。与其不同的是，AHSE采用自适应的等级进行访问控制，并且，属性加密虽然在细粒度的访问控制上十分有效，但是同一属性的用户私钥以及同一属性加密的密文之间有一定的联系，也就是说，在属性需要撤销更新的情况下，与该属性相关的密文以及用户的私钥不能保证独立性，可能均需要更新，因此实际操作时较为繁琐。本文AHSE中的用户具有独立的私钥，条件键由系统控制，某一用户动态更新时，不会对其他用户的私钥造成影响。另外，文献[9]方案与文献[10]方案未考虑抗量子攻击。

文献[20]方案、文献[19]方案分别是2017年和2018年提出的可搜索加密方案，二者均可抗量子攻击，实现关键词搜索功能，但二者均未考虑访问控制问题。文献[20]方案使用了可搜索广播加密的方式，实现了多用户数据共享，但对于用户的访问只是粗粒度地分为数据共享与非共享两种。文献[19]方案中考虑的是单用户场景，本文引入代理服务器，使代理服务器利用代理重加密转换键，从而将方案拓展为多用户搜索场景。

6.2 性能分析

根据不同文献中出现的算法，定义psf表示运行Pre-image Sample Function目标图像采样算法的计算成本，tg表示运行TrapGen陷门生成算法的计算成本，sb表示运行SampleBasis短基生成算法的计算成本，sp表示运行SamplePre预采样算法的计算成本，bd表示运行NewBasisDel新的格基生成算法的计算成本。mul仅表示矩阵之间乘法的计算成本，add表示矩阵之间加法的计算成本。由此，可以计算出AHSE的公钥、私钥、陷门以及密文的存储开销分别为mnlogq、m2logq、mlogq和(m+1) logq。公私钥生成、密文生成、陷门生成以及关键词陷门匹配测试的计算开销分别是1tg、2mul+1add、1sp、2mul+1add。

文献[17]、[18]方案为单用户基于格密码的可搜索加密方案，AHSE方案为多用户基于格密码的方案。表2与表3为文献[17]、[18]方案与AHSE方案的存储开销和计算开销。可以看出，在存储开销方面，AHSE方案的公钥、私钥、陷门以及密文的大小与文献[17]、[18]方案相当。计算开销方面，AHSE方案在公私钥生成、密文生成、陷门生成阶段与文献[17]方案、文献[18]方案相当，而关键词匹配搜索阶段，计算开销略有增加，主要由AHSE从单用户拓展至多用户，使用代理重加密转换技术所致。文献[19]方案没有细粒度的访问控制，仅分为数据共享与非共享两种，可以看出，本文AHSE在实现了自适应等级的访问控制下，计算开销与存储开销性能表现优于该方案。文献[20]方案考虑的仅为单用户场景，而本文将方案拓展为多用户搜索场景。可以从表2和表3看出，AHSE在具有良好的访问控制下，存储开销与计算开销方面表现良好。最后，文献[21]方案针对数据拥有者设计了代理，即减轻原始数据所有者的数据处理负担，但比较数据可以看出，本文AHSE方案不仅适用于多用户，并且在计算及存储开销方面表现优于该方案。

表2 不同方案的存储开销比较 Tab. 2 Memory overhead comparison of different schemes

表3 不同方案的计算开销比较 Tab. 3 Computation overhead comparison of different schemes

对于带有访问控制的密文搜索方案，AHSE中使用分段式索引结构，搜索时间复杂度为Ο(K)，而其他现有带访问控制的可搜索加密方案[25-27]的搜索时间复杂度为Ο(MN)。其中，K为本文索引中使用的关键词个数，N为所有文件个数，M为每个文件中的关键词个数。如果所有文件的关键词都不相同，则K=MN；但是，在实际情况中，特定应用场景或某一领域数据库文件数据相关性较大，不同文件的关键词重复率较高，即K≪MN，因此本搜索方案可以有效提高搜索效率。

7 结语

针对现有分等级可搜索加密方案不能有效抵抗量子攻击以及不能灵活添加与删除某一个或多个等级的问题，本文提出一种基于LWE的自适应等级可搜索加密方案，通过构造简单灵活的条件键，为用户分配不同的等级，实现有效的等级访问控制；同时本文设计一种分段式索引结构，其等级具有良好的自适应性，能够灵活添加与删除，满足了加密数据库、云医疗等系统对不同粒度访问控制的需求；并且，该方案中用户和文件的更新、删除以及等级变动易于操作，适用于动态环境。最后，本文并未考虑格上多对多应用场景，以及更灵活的多关键词可搜索加密技术，但它们是实际生活对可搜索加密技术的同等需求，同样是下一步将要研究的方向。