云边协同下可排序的属性基可搜索加密方案

王 正，曹素珍，赵 晓，周大伟，邢丹丹

（西北师范大学 计算机科学与工程学院，兰州 730070）

0 概述

随着物联网和5G 技术的广泛应用［1-2］，现有云服务器的性能已不能满足互联网时代对海量数据的实时处理需求。边缘设备［3-4］以低时延、移动性支持等优势逐步成为解决上述问题的一种新途径。云服务器和边缘设备是半诚实的［5-7］，因此为保证用户数据的机密性，数据所有者（Data Owner，DO）通常将数据加密后再存储于云端或边缘设备，然而如何检索密文成为数据用户面临的一大难题。文献［8］提出可搜索加密（Searchable Encryption，SE）概念，有效解决了密文检索的难题。

在早期的SE 方案中常采用单关键字SE 方案［9］，但因存在大量的关键字索引重复问题，从而导致搜索效率不高。为了提高搜索的准确性，在后续的研究中用户搜索的关键字通常采取多关键字方案［10-12］。文献［13］提出一种多关键字SE 方案，通过匹配多关键字的索引和搜索陷门来提高搜索效率，但仍存在关键字与主题相关性不大的问题。文献［14］提出一种多关键字排序SE 算法，利用TF-IDF规则根据关键字相关的程度排序搜索结果，仅返回最满足用户需求的Top-k文件。上述文献无论是采用对称或非对称加密算法均无法满足数据共享时的细粒度访问控制需求。

文献［15］提出属性基可搜索加密（Attribute-Based Searchable Encryption，ABSE）概念，实现了外包加密数据上的安全搜索和细粒度访问控制。文献［16-17］提出一种基于密文策略的ABSE 方案（CPABSE），在CP-ABSE 方案中私钥与属性相关联，密文与访问结构相关联，使得访问密文的用户由数据所有者设定的访问策略决定，达到细粒度访问控制的效果。KP-ABSE［18］方案是将策略嵌入用户密钥，属性嵌入密文，但这两种ABSE 方案都可能存在访问策略泄露问题。文献［19］提出一种基于隐藏策略和外包解密的白盒可跟踪属性加密方案，基于LSSS访问结构，该方案采用策略隐藏的方式只对属性名进行公开，缺陷在于不支持对多关键字的搜索排序，搜索结果不精准。文献［20-21］提出一种基于边缘计算框架的高效密文索引检索方案，结合可搜索加密技术与边缘计算技术所定义的边缘缓存网络模型使密文检索更加安全高效。文献［22］提出IIoT 时代可持续边缘云网络的多关键词排序搜索隐私保护方案，但该方案无法满足大规模计算需求。

针对上述问题，本文提出云边协同下可排序的属性基可搜索加密方案，主要工作如下：

1）利用云边协同技术，将加密后的数据上传到云端，与其对应的加密索引上传到最近的边缘节点，提高了搜索效率，降低了用户的计算负担。

2）用户的属性由属性名和属性值组成，在构造访问结构时，用户仅通过公开的属性名进行陷门搜索匹配，从而使得未经授权的用户无法获取访问策略中的任何有效信息。

3）在密文检索阶段，可在排除无关关键字的情况下根据检索关键字的重要程度进行排序，最终返回与用户需求最相关的Top-k密文，实现了多关键字排序搜索。

4）利用在线/离线加密技术，数据所有者在上传密文之前先进行离线加密，降低客户端的计算成本。

1 预备知识

1.1 双线性映射

选择两个循环群G1、G2，p是它们的素数阶，定义一个双线性映射e：G1×G1→G2满足以下性质［23］：

1）双线性。对∀x,y∊G1,∀a,b∊，有e(xa,yb)=e(xb,ya)=e(x,y)ab成 立。

2）非退化性。∃x,y∊G1满足e(x,y) ≠1。

3）可计算性。对∀x,y∊G1，存在一个多项式时间算法有效计算e(x,y)。

1.2 访问结构

设P={P1,P2,…,Pn}表示参与者的集合，令2P={A|A⊆{P1,P2,…,Pn}}，集合A⊆2P是单调的，当且仅当对于任意子集B,C⊆P，如果B∊A且B⊆C，则C∊A。若A是P={P1,P2,…,Pn}中的非空子集（单调的），即则 称A是一个 访问结构（单调的）。对于任意集合D，若D∊A，则D为授权集，否则为非授权集［24］。

1.3 线性秘密共享方案

定义P上的一个线性秘密共享方案π，满足如下条件［25］：

2）每个线性秘密共享方案都有一个l×n的生成矩阵M，且存在单射函数ρ：{1,2,…,l} →P把M的每一行(i=1,2,…,l)映射到参与者ρ(i)。考虑向量v=(s,v2,v3,…,vn)，s∊是共享秘 密值，选 择随机数v2,v3,…,vn∊隐藏共享秘密值s，则Mv是共享秘密份额，其中λi=(Mv)i是共享秘密值s的第i个秘密份额。

1.4 TF-IDF 规则

TF-IDF 用来评估指定关键字对于文档集合中某一篇文档的重要程度［26］，值越大，说明该关键字w在文档f中的重要程度越靠前。TF 是计算指定关键字w在查询文档f中出现的次数，IDF 是该关键词出现在所有文档中的数据集合。根据下述拆分规则计算Top-k文件。

拆分规则：基于随机的n维二进制向量P计算n维向量Q，利用P将Q拆分为两个随机向量(Q′,Q″)，如式（1）所示：

1.5 困难问题假设

困难问题假设具体如下：

1）DBDH 假设。设一个循环群G，p是它的素数阶，g是G的一个生成元。随机选择a,b,c,z∊Zp，给定多元组，如果不存在一种算法能够在多项式时间内以不可忽略的概率区分(g,ga,gb,gc,z)，则DBDH 假设成立。

2）q-parallel DBDH 假设。选择两个乘法循环群G1、G2，p是它们的素数阶，g是G1的一个生成元。随机选择q+2 个元素x,a,b1,b2,…,bq∊Zp，计算：

1.6 符号描述

文中使用的一些符号和变量如表1 所示。

表1 符号和变量描述Table 1 Description of symbols and variables

2 属性基可搜索加密方案

2.1 系统模型

所提方案的系统主要包括5 类实体，分别是授权机构（Authorization Attribute，AA）、云服务提供商（Cloud Service Provider，CSP）、边缘节点（Edge Node，EN）、数据所有者和数据用户（Data User，DU）。

该方案由一个受信任的AA 公开发布全局参数并对主密钥保密，DO 将加密文件上传到CSP 存储，将相应的关键字索引上传到最近的EN。DU 根据访问策略生成搜索陷门发送给最近的EN，EN 接收到搜索陷门后先对CSP 中存储的数据进行搜索，CSP搜索出符合的文件返回给EN，EN 利用用户生成的部分解密密钥对其进行部分解密，将Top-k文件返回给用户解密，最后得到共享的数据文件。系统模型及流程如图1 所示。

图1 系统模型及流程Fig.1 System model and procedure

该模型在现实应用中可适应于大部分实际场景，如智能电网。假设电力运营公司使用该模型使某市的各小区之间可相互共享一些电网用户数据。电网用户查看自己相关的数据时只需要简单的身份注册，受信任的授权机构根据其基本信息分发可解密本人数据的属性密钥。电网用户根据属性设置访问策略，系统将其转换为一个矩阵并将其嵌入密文后上传云服务器，相应的关键字索引上传到最近的边缘节点。管理人员等其他想要访问数据的电网查询者需要受信任的授权机构审核其身份信息并为其分发属性密钥，在系统中输入相关关键字，当属性满足电网用户设置的访问策略时，则可解密搜索结果，否则无权查看，这在一定程度上保护了数据隐私。

1）AA。AA 是一个完全受信任的实体，由它生成全局参数和系统主密钥，当用户想要查询时，可以根据其属性集生成对应的用户私钥。

2）CSP。CSP 是一个诚实但好奇的半可信实体，会好奇云上存储的数据但会诚实地执行任务。在该系统中，允许系统中的合法用户上传或访问存储其上的密文数据。

3）EN。EN 用于存储密文索引，当从DU 接收搜索陷门时，诚实地执行搜索算法，并将搜索结果发送到CSP。在获得从CSP 返回的加密文件后，协助DU进行部分密文解密操作，并根据TF-IDF 规则计算并返回给用户最符合要求的Top-k文件。

4）DO。根据DO 设定的访问策略对数据和关键字进行加密后上传到EN。

5）DU。每个DU 计算搜索陷门并发送到边缘节点进行匹配查询，生成部分解密密钥发送到边缘节点以供对返回的搜索结果进行部分解密操作。

2.2 安全模型

所提方案的安全模型通过攻击者A 和挑战者C之间的模拟游戏定义。若攻击者A 在多项式时间算法内不能以不可忽略的优势在游戏中获胜，则该方案具有选择关键字攻击（IND-CKA）安全性。

1）初始化。挑战者C 调用SetUp 算法，通过安全参数λ计算得全局参数GP和系统主密钥KM。

2）查询阶段1。攻击者A 向挑战者C 请求对应属性集SA的私钥和待查询关键字的集合W′的搜索陷门。

3）挑战。攻击者A 向挑战者C 发送两个大小相同的关键字w1、w2，攻击者A 提供访 问策略(M,ρ)，挑战者C 随机选择b∊{0,1}，利用wb生成加密关键字索引Iwb返回给攻击者A。

4）查询阶段2。攻击者A 重复进行查询阶段1，查询更多与w1、w2不同的关键字集合的搜索陷门。

5）猜测阶段。攻击者A 输出b的一个猜想b'∊{0,1}，若b=b'，则攻击者A 获胜，攻击者A 成功的优势为

2.3 算法描述

算法描述具体如下：

1）设 置SetUp(1λ) →(GP,KM)。AA 执行该 算法，输入安全参数λ，输出全局参数GP，主密钥KM。

2）密钥生成KeyGen(GP,KM,S)→(KS)。AA执行该算法，输入全局参数GP，根据主密钥KM和用户的属性集S生成用户的属性密钥KS。

3）加密。加密包括离线加密和在线加密。

（1）离线加密Offline.Enc(GP) →(CP)。在没有确定关键字集合以及访问策略之前，DO 空闲时执行该算法，输入全局参数GP，根据用户属性S及选择的秘密值s输出中间密文CP，用于在线加密。

（2）在线加密Online.Enc(GP,CP,F,W,A(M,ρ)) →(CT,Iw)。DO 执行该算法，输入全局参数GP，离线加密时生成的中间密文CP，明文文件集F，关键字集合W，访问策略A(m,ρ)，输出对数据加密生成的加密密文CT和对关键字加密生成的加密索引Iw，并根据TF-IDF 规则计算索引向量Iw。

4）陷门生成Trapdoor(GP,KS,q) →(Tq)。DU 执行该算法，输入用户私钥KS和在关键字集合中随机选择的待搜索关键字q，生成查询陷门用于密文搜索。同时，根据TF-IDF 规则计算查询向量与在线加密时生成的索引向量一同用于Top-k文件的分数排序计算。

5）密文搜索Search(GP,CT,Iw,Tq)→(CT/⊥)。CSP执行该算法，输入查询陷门Tq和关键字索引Iw，检测其能否成功匹配，若能则继续验证，否则终止。

6）验证Verify。验证返回结果的正确性，并根据TF-IDF 规则计算并返回给用户需要的Top-k文件。

7）转换Transform(GP,KS) →(KP)。由DU 执行该算法，输入DU 的私钥KS，输出边缘节点的部分解密密钥KP，用于协助密文的部分解密。

8）部分解密密文E.Dec(GP,KP,CT) →(CPT)。EN执行该算法，输入全局参数GP和边缘节点的部分解密密钥KP，对所得的Top-k文件密文进行部分解密，输出部分解密密文CPT。

9）解 密Dec(KS,CPT,Kτ) →(m)。DU 执行该 算法，输入DU 的私钥KS，并利用中间解密密钥中包含的转换因子Kτ，对步骤8）得到的部分解密密文CPT解密后，获得所需明文m。

2.4 方案构造

方案构造具体如下：

1）系统建立。先初始化系统，输入安全参数λ，设置全局参数U={1,2,…,N}，设两个乘法循环群G1、G2，p是它们 的素数 阶，设定双 线性对e：G1×G1→G2，其中，g是G1的生成元，并选择哈希函数H：{0,1}*→。AA 随机选择α,β,μ∊，计算e(g,g)α、gβ、gμ。对于每个属性i∊U，AA 随机选择ai∊，计算。最后生成系统的全局参数GP和主密钥KM，如式（2）所示：

其中：GP由AA 公开；KM由AA 秘密保存。

3）离线加密。在没有确定关键字集合以及访问策略之前先进行离线计算。DO 选择秘密值，计算密文，如式（4）所示：

4）在线加密。设l×n的访问矩阵Ml×n，其中对∀i∊[1,l]，Mi是矩阵M的第i行，定义函数ρ将第i行映射到 相应的 属性名ai，ρ：ρ(i) →ai。最后将{Ml×n,ρ}以明文的形式作为访问结构。

（1）数据加密

②计算λi=Ml×n×v。

（3）生成索引向量。DO 根据拆分规则式（1）设置索引向量与关键字索引一同作为密文索引发送到EN。

5）查询

（1）生成查询陷门。DU 选择关键字集合W，随机选择q，计算查询陷门如式（5）所示：

（2）生成查询向量。DU 根据拆分规则式（1）设置查询向量将其与查询陷门一起发送到EN。

6）密文搜索。EN 检测查询陷门与关键字索引能否成功匹配，验证等式e(IWj,T1)e(I1,T3)=e(I2×I3,T2)是否成立，若成立则使用式（6）计算索引向量和查询向量的相关分数：

将计算得到的相关分数结果排序，仅返回Top-k文件密文CT，否则输出⊥。

9）明文。DU 收到EN 返回的部分解密密文CPT后，计算明文m=并输出。

3 正确性与安全性证明

3.1 正确性证明

1）关键字匹配正确性

检查式（7）是否成立来判断用户生成的陷门和密文对应的关键字是否匹配：

综上，关键字匹配的正确性得证。

2）解密密文正确性

边缘节点接收到DU 的部分解密密钥后计算部分解密密文。边缘节点辅助解密的正确性证明如下：

根据上述可得解密密文的正确性证明如下：

综上，解密密文的正确性得证。

3.2 安全性证明

定理1若多项式时间内的算法允许攻击者A以可忽略的优势获胜，则该方案具有IND-CKA 安全性。

1）初始化。输入安全参数λ，选择一个循环群G1，p是它的素数阶，g是G1的生成元，随机选择α,β,μ∊和哈希函数H：{0,1}*→，挑战者 C 调 用SetUp(1λ) →(GP,KM)算法。最后生成系统的全局参数GP和主密钥KM，GP由AA公开，KM由AA秘密保存。

2）查询阶段1。查询阶段1 包括私钥查询和陷门查询。

4）查询阶段2。攻击者A 重复进行查询阶段1，查询更多与w1、w2不同的关键字集合的搜索陷门。

5）猜测阶段。攻击者A 输出b的一个猜想b'∊{0,1}，若b'=b，则攻击者A 输出b'=b的概率为，若b'≠b，则攻击者A 输出b'≠b的概率为因此攻击者A 成功的优势如下：

由于攻击者A 成功的优势是可忽略的，因此所提方案是安全的，证毕。

4 性能分析

4.1 功能分析

为了证明所提方案的有效性，进行在线/离线加密、策略隐藏、搜索结果排序等方面的比较实验，比较方案选择文献［12-14，19］方案，比较结果如表2 所示，其中，√表示具备该功能，×表示不具备该功能。

表2 功能比较Table 2 Function comparison

由表2 可知，除文献［19］方案外的其他方案都支持多关键字搜索，从而提高了方案对文件检索的准确性，特别是文献［14］方案和所提方案可以对搜索后得到的文件进行Top-k排序，但只有所提方案在加密时引入了在线/离线加密机制，因而实现了较低的计算开销。此外，在所提方案中，运用边缘节点辅助解密的设计，密文在被DU 解密之前会被EN 部分解密，大大减少了DU 的计算开销，减轻了客户端负担。文献［19］方案引入外包辅助加/解密的技术，虽降低了客户端的成本，但外包密钥的生成和验证需要额外的开销导致效果不理想。文献［12-13］方案并未实现对访问策略的隐藏，对用户的敏感信息有巨大的安全隐患。相比较而言，所提方案不仅可满足多关键字的密文排序搜索，以及实现策略隐藏和细粒度访问控制，同时与其他方案相比，在降低用户开销方面具有更好的性能。

4.2 计算与存储开销分析

将所提方案与文献［12-14，19］方案在计算、存储开销方面进行对比，结果如表3 和表4 所示，其中，分别表 示中元素 的长度，n1、n2分别表示访问策略中的属性个数、与用户相关的属性个数，i表示关键字集中关键字的个数，E1、E2表示G1、G2上的群指数运算，P表示双线性对运算。

表3 计算开销比较Table 3 Computational cost comparison

表4 存储开销比较Table 4 Storage cost comparison

对于计算开销的比较，所提方案在加/解密阶段采用了在线/离线加密技术，与其他方案相比开销较低。对于存储开销的比较，因为云服务器的存储容量不受限，所以所提方案并不考虑云中的密文存储开销。由于用户的密钥长度只与属性相关，因此在所有方案中用户只存储其长度随n2增加而线性增加的属性。虽然当属性较少时所提方案需要的存储空间较大，但是当属性数随着n2线性增加时，所提方案的密钥存储开销低于其他方案。以上表明，所提方案在计算和存储开销方面较其他方案有一定优势。

4.3 性能仿真分析

为了更准确地评估方案的实际性能，实验平台配置在Intel®CoreTMi5-8250U CPU @ 160 GHz 8.00 GB RAM 的笔记本上，基于Java 配对加密库（JPBC），采用Type A 型素数阶椭圆曲线y2=x3+x进行仿真实验。为了方便定量分析，假定关键字集中关键字的数量为50，属性数量的取值范围为［10，50］，当属性数量取值为10、20、30、40、50 时，各方案在加密和陷门生成阶段的计算时间随属性数量的变化情况分别如图2 和图3 所示。

图2 各方案加密阶段的计算时间比较Fig.2 Comparison of computing time in encryption stage of each scheme

图3 各方案陷门生成阶段的计算时间比较Fig.3 Comparison of computing time in trapdoor generation stage of each scheme

由图2 和图3 可知，各方案的加密和陷门生成时间都与属性数量成线性正比关系，所提方案在加密和陷门生成阶段的计算时间相比于次优的文献［12］方案降低了10%和25%。在加密阶段，虽然当属性数量较少时所提方案的计算时间不是最少，但随着属性数量的增加计算时间一直少于其他方案。在陷门生成阶段，与其他方案相比，所提方案的计算时间一直保持在最低的常数级水平。

实验结果分析表明，所提方案不仅实现了高效的多关键字搜索和密文的访问控制，而且具有更好的性能和实用价值。

5 结束语

本文提出云边协同下可排序的属性基可搜索加密方案。采用在线/离线加密和边缘节点辅助计算，在确定访问策略前进行预加密，通过将加密后的数据上传到云端，与其对应的加密索引上传到最近的边缘节点来降低用户的计算负担。将关键字拆分成关键字名和关键字值，用户只能通过公开的关键字名进行匹配，保证了方案安全性。在实现多关键字搜索的情况下对关键字的重要程度进行排序，提高了搜索效率。分析与对比结果表明，所提方案满足IND-CKA 安全性，并且与同类方案相比更具高效性。后续将进一步加强所提方案的搜索效率及实用性。