指定使用者的多服务器多关键字可搜索加密方案

窦凤鸽，曹素珍，马佳佳，丁晓晖，王彩芬

（1.西北师范大学 计算机科学与工程学院，兰州 730070；2.深圳技术大学 大数据与互联网学院，广东 深圳 518118）

0 概述

随着云计算技术［1-2］的发展，越来越多的用户将数据存储在云上，由于云服务器不能保证数据的安全以及用户的私密性，因此将数据加密后再发送到云［3］成为数据属主（Data Owner，DO）普遍采用的方法，但是该过程中数据使用者将面临密文搜索的难题［4-5］。为解决该问题，2000 年SONG 等［6］提出一种可搜索加密技术。

2004 年，BONEH 等［7］提出首个基于关键字搜索的公钥加密方案，该方案在通信过程中需要安全通道，导致通信代价较大。2020 年，RHEE 等［8］提出指定测试者的可搜索公钥加密方案，其在随机预言机模型下证明了陷门的不可区分性是抗关键字猜测攻击（Keyword Guessing Attack，KGA）的充分条件。2014 年，PENG 等［9］提出带有关键字搜索的无证书公钥加密方案，但该方案存在内部关键字猜测攻击（Inside Keyword Guessing Attack，IKGA）问 题。2017 年，HUANG 等［10］提出基于关键字搜索的公钥认证可搜索加密方案，该方案可以对数据属主的身份进行认证。2018 年，MA 等［11］提出工业物联网环境下无证书可搜索加密方案，但其不能抵抗IKGA。2020 年，YANG 等［12］对文献［11］方案进行改进，改进后的方案可抵抗IKGA，但其只支持单关键字搜索。2019 年，WANG 等［13］设计的抗IKGA 的 可搜索 加密方案中以非确定性算法生成搜索陷门，使得方案满足陷门不可区分性和密文不可区分性，但其存在证书管理问题。2019 年，LU 等［14］提出的无证书公钥可搜索加密方案解决了证书管理问题且能抵抗IKGA，但其只支持单关键字搜索。文献［15-16］中无双线性对的可搜索加密方案均提高了计算效率，但都不能支持多关键字搜索，且文献［16］方案存在证书管理及密钥托管问题。2020 年，CHI 等［17］提出的云辅助医疗物联网下的公钥认证可搜索加密方案仅支持单关键字搜索。文献［18］中基于身份的动态可搜索加密方案存在密钥托管问题。可以看出，上述方案都是基于单关键字搜索而设计的。2020 年，LUO等［19］提出的基于连接关键字的实用化可搜索加密方案，解决了搜索结果不精确的问题，但其存在证书管理及密钥托管问题。上述所提方案都是基于单服务器所设计，存储和搜索都在一个服务器上完成，且没有对数据使用者身份的合法性进行验证。

针对上述方案单关键字搜索结果不精确和单服务器检索效率低等问题，本文提出一种基于无证书且指定使用者的多服务器多关键字可搜索加密方案。该方案使用多服务器来降低服务器负荷，采用多关键字技术使得搜索结果更精确。利用搜索服务器（Search Server，SS）对用户身份的合法性进行验证，通过用户身份及搜索服务器私钥来验证用户是否为指定使用者，若身份合法，则存储服务器（Cloud Server，CS）根据关键字返回相应密文，数据使用者使用私钥解密密文以获得明文。

1 预备知识

1.1 双线性映射

假设q是一个大素数，G1和G2是2 个阶为q的循环群。若映射e：G1×G1→G2满足以下属性，则称其为双线性映射［20］：

1.2 困难问题假设

计算的双线性Diffie-Hellman（Computational Bilinear Diffie-Hellman，CBDH）问题［21］定义为：给定双线性对e：G1×G1→G2，四元组（g，ga，gb，gc）∈G1，其中为未知数，则计算e（g，g）abc是困难的。

2 加密方案框架

2.1 系统模型

本文所提方案包含5 个不同的实体，分别为密钥生成中心（Key Generation Center，KGC）、存储服务器、搜索服务器、数据属主、数据用户（Data User，DU），系统模型如图1 所示。

图1 本文方案系统模型Fig.1 The system model of the scheme in this paper

5 个实体的具体功能如下：

1）KGC：生成系统的公共参数以及数据属主、数据用户、搜索服务器的部分私钥。

2）数据属主：首先将文档集密文C={C1,C2,…,Cn}和相对应的文件索引集I={I1,I2,…,In}上传到存储服务器，其次将关键字密文和对应的文件索引集I={I1,I2,…,In}上传到搜索服务器。

3）数据用户：生成搜索陷门TW并发送给搜索服务器进行验证搜索，同时对搜索结果进行解密。

4）存储服务器：存储数据属主上传的文档密文和对应的文件索引集。

5）搜索服务器：对数据用户的身份进行验证，若为指定使用者，则根据数据用户发送的搜索陷门TW′和数据属主上传的密文CW进行验证，若验证成功，将对应的（文件索引Ii(1≤i≤n)，用户身份ID）发送给存储服务器，存储服务器返回对应的密文给数据用户；否则，说明数据用户不是指定使用者，向其返回终止符“⊥”。

2.2 形式化定义

在形式上，本文所提方案由以下7 个算法组成：

2.3 安全模型

由于本文方案是在无证书密码体制下所提出的，因此应考虑2 个不同类型的敌手：

1）A1（恶意的内部服务器或外部攻击者）无法访问KGC 的主密钥，但能替换用户公钥。

2）A2（诚实但好奇的拥有主密钥的KGC）能为用户生成部分私钥，但不允许替换公钥。

本文方案的安全模型由以下游戏定义，该游戏在挑战者C和敌手A1、A2之间分别进行：

Game：挑战者C执行算法Setup 产生KGC 的主密钥s和系统的公共参数params。如果敌手A=A1，则返回params；如果A=A2，则返回params 和s。

Hash 询问：敌手A进行4 个Hash 询问，挑战者C返回相应的Hash 值；PartialPrivateKey 询问：敌手A对身份IDI进行部分私钥询问时，挑战者C向A返回相应的部分私钥；Secret-Value-query 询问：敌手A对身份IDI进行秘密值询问时，挑战者C计算相应的秘密值给A；PublicKey-query 询问：敌手A对身份IDI进行公钥询问时，挑战者C计算相应的公钥给A；Reaplace-PublicKey 询问：敌手A=A1可以替换任何用户的公钥；Trapdoor-query 询问：敌手A对身份IDI的关键字w进行陷门询问时，挑战者C计算相应的陷门给A。

Challenge 阶段：A输出挑战关键字(w0,w1)，挑战者C随机选择b∈{0,1}，并返回密文Cwb。

More-Trapdoor 询 问：A可以对 其他关键字wi进行陷门询问，但wi∉{w0,w1}。

Guess 阶段：A输出猜测值b′∈{0,1}，如果b′=b，则赢得游戏。如果A在上述游戏中获胜的优势AAdv=2|Pr[b=b']-1/2|是可忽略的，则称方案是抗IKGA 语义安全的。

3 方案实现

3.1 方案的具体描述

方案的具体描述如下：

3.2 方案的正确性分析

方案的正确性分析具体如下：

4 安全性证明

定理1如果CBDH 问题是困难的，则本文方案在随机预言机模型下抵抗关键字猜测攻击是语义安全的。

定理1 由以下2 个引理可以证明：

引理1若存在敌手A1能够在t时间内以ε的优势攻破本文方案，则存在一个算法C能够在O(t)时间内以的概率解决CBDH 问题。其中：q1、qP和qT分别表示对H1、PartialPrivateKey 和Trapdoor 询问的最大查询数。

证明已知(g,ga,gb,gc)求解e(g,g)abc为CBDH问题实例。算法C模拟游戏中的挑战者与敌手A1进行如下交互：C输入安全参数l执行Setup 算法生成参 数 params={G1,G2,e,q,g,PPub,H1,H2,H3,H4}，其中，PPub=ga，再随机选择IDI作为挑战者身份，最后向敌手A1发送公共参数params。

引理2若存在敌手A2能够在t时间内以ε的优势攻破本文方案，则存在算法C能够在O(t)时间内以的概率解决CBDH 问题。

证明已知(g,ga,gb,gc)求解e(g,g)abc为CBDH问题实例。算法C模拟游戏中的挑战者与敌手A2进行如下交互：C输入安全参数l执行Setup 算法生成params={G1,G2,e,q,g,PPub,H1,H2,H3,H4}。其 中，PPub=gs，设置PKIDI=ga，PKDO=gb，再随机选择IDI作为挑战者身份，最后向敌手A2发送params。

5 性能分析

将本文方案与文献［8］方案、文献［10］方案、文献［13］方案在计算开销、功能及效率方面进行性能对比。其中：Tp表示双线性对运算的运行时间；TE表示指数运算的运行时间；TM表示点乘运算的运行时间。从表1 可以看出，本文方案在关键字加密及搜索验证阶段的性能优于其他3 个方案，且其在支持多服务器多关键字搜索的同时能够抵抗IKGA，安全性高于对比方案。

表1 4 种方案的性能对比结果Table 1 Performance comparison results of four schemes

在以笔记本电脑（Windows 7（64 位）处理器IntelⓇCoreTMi5CPU@2.3 GHz）为实验平台、Visual C++6.0 为编译软件的环境下，基于0.4.7 的PBC 库，将本文方案与文献［8］方案、文献［10］方案的关键字加密及搜索验证阶段进行效率对比分析，关键字个数选取为［1，10，20，30，40，50］，对比结果如图2、图3 所示。

图2 关键字加密阶段的效率分析Fig.2 Efficiency analysis of keyword encryption stage

图3 搜索验证阶段的效率分析Fig.3 Efficiency analysis of search verification stage

从图2 可以看出，本文方案和文献［8］方案、文献［10］方案的运行时间在关键字加密阶段均随着关键字个数的增加而增加，但本文方案所使用时间明显低于其他2 个方案。从图3 可以看出，3 种方案的运行时间在搜索验证阶段均随着查询关键字个数的增加而不断增加，即使本文方案添加了多服务器，但效率还是高于其他2 个方案。因此，本文方案在综合性能上具有明显优势。

6 结束语

本文在无证书密码体制下提出一种指定使用者的多服务器多关键字可搜索加密方案，该方案使用多服务器提高用户检索密文的速度，采用多关键字技术使搜索结果更加精确，搜索服务器可以验证数据用户身份的合法性。本文在随机预言机模型下证明了该方案能够抵抗内外关键字猜测攻击，同时，理论分析和实验结果表明，本文方案具有较高的运算效率。下一步将在标准模型下探索实现更加高效并指定使用者的多服务器多关键字可搜索加密方案。