一种无安全信道的模糊关键字搜索加密方案

曹永明

(河海大学计算机与信息学院,江苏 南京 211100)

0 引 言

随着可搜索公钥加密[1]技术的不断发展，用户获得了在加密数据上检索数据的能力,很多带关键字搜索的公钥加密(Public key Encryption with Keyword Search, PEKS)方案也被相继提出[2-3]。目前，大多数PEKS方案的主要缺陷是仅仅支持精确的关键字检索，不具备一定的关键字搜索的容错能力。

可搜索加密技术已经得到了广泛的研究。可搜索加密的第一个构造是由Song等人[4]提出的。为了实现更高的效率，Chang等人[5]和Curtmola等人[6]都提出了基于“索引”的方法，为整个数据文件集合建立一个哈希索引表。在每个索引表中，都包含一个关键字的陷门和一个加密文件的标识符集合，这些数据标识符与数据文件中包含的关键字相对应。

2004年，Boneh等人[7]首次提出了带关键字搜索的公钥加密。在文献[7]的基础上，Waters等人[8]提出了一个加密日志的关键字搜索方案，让用户可以对已经加密的信息进行审查。

由于PEKS方案无法支持模糊关键字搜索，Li等人[9]第一次提出模糊关键字检索的方案。该方案中的模糊关键字集合采用通配符技术进行构造。当用户进行查询时，用查询的关键字与关键字集合进行匹配，将可能包含查询关键字的文件集合返回。2011年，字典型模糊关键字集合由Liu等人[10]提出，虽然这种方法使得模糊关键字的数量得到了降低，但同时也降低了查询的准确率。Wang等人[11]在2012年进一步研究了模糊关键字检索方案，将树结构应用到关键字索引结构中，并且给出了安全性验证。Chuah等人[12]提出了支持多关键字的模糊搜索模型，该模型中加入了分层树的结构，使得关键字搜索的效率更高。该方案还可以对文件集合和索引进行更新，但是由于该方案基于布隆过滤器，所以无法进行删除操作，并且查询准确性无法得到保障。在2013年，Zhou等人[13]和Wang等人[14]分别提出了不同的模糊关键字搜索方法，其中文献[13]给出了可排序模糊关键字搜索方案，文献[14]提出了一种可验证的模糊关键字搜索方案。在2015年，Wang等人[15]提出了一种基于非双线性对的模糊关键字搜索方案，在2017年，Zhu等人[16]在模糊关键字的基础上又添加了访问控制的功能，将模糊关键字加密搜索的应用场景再一次进行了拓宽。

文献[17]方案的PEKS是不可区分的，因此该方案可能会受到关键字选择攻击。为了信息传输的安全性，Boneh等人[7]提出了一种无安全信道的公钥加密搜索方案。该方案仅支持精确的关键字搜索，在文献[1,17]研究的基础上，本文提出一种无安全信道的模糊关键字搜索方案，如图1所示。

图1 本文方案架构图

本文方案主要包括6个构造步骤，前3个步骤是由第三方可信机构执行，产生公共参数、服务器公私钥和数据拥有者的公私钥。数据拥有者执行加密算法，将数据文件加密，将密文和加密数据上传到服务器中保存。

用户进行关键字搜索时，将包含关键字的陷门发送给服务器，服务器执行测试算法，将搜索结果返回给用户，且不泄露任何关键字信息。

本文方案不仅支持模糊关键字搜索，且不需要安全信道进行数据传输,这大大提高了系统的可用性与安全性。

1 双线性对

设G1和G2是定义在相同的素数阶p上的乘法循环群，g是G1的生成元。双线性映射：e:G1×G1=G2，有以下性质：

2)可计算性：对于∀U,V∈G1，能够有效地计算e(U,V)。

3)非退化性：∃U,V∈G1，有e(U,V)≠1。

2 方案构造

本文方案的具体构造如下：

1)Setup(k)。产生素数阶群q≥2k的2个组g1=

和g2，P是g1的一个随机生成器，双线性对e:g1×g1=g2。指定哈希函数h1:{0,1}*→g1，h2:g2→{0,1}k。返回cp=(q,g1,g2,e,P,h1,h2,Kw)。其中Kw表示关键字空间的描述。

编辑距离为d，数据发送者为关键字wi构建一一对应的索引，使用通配符技术建立模糊关键字索引集合Swi,d。集合Swi,d中的元素是使用通配符表示的关键字，通配符的个数就是编辑距离的大小。在加密算法中，数据拥有者对w′i∈Swi,d进行加密。

5)Trapdoor(cp,skServ,w′)。Tw′=ah1(w′)，输出Tw′作为陷门。

6)Test(cp,Tw′,pkSender,M)。如果计算h2(e(BQP-1+Tw′,U))=V成立，则输出“正确”，表示匹配成功,返回文件索引f；如果不成立则返回“错误”。

3 安全性分析

3.1 正确性分析

下面是验证过程的正确性：

在本文方案的验证阶段，首先计算k的值：

k=(e(Q,B)e(h1(w′i),A))x

=e(xQ,bP)e(xh1(w′i),aP)

(1)

然后计算e(BQP-1+Tw′,U)的值，即：

e(BQP-1+Tw′,U)=e(BQP-1,U)e(Tw′,U)

=e(xQ,bP)e(xh1(w′),aP)

(2)

如果式(1)和式(2)中的w′i=w′，则搜索验证通过，服务器将返回含有待搜索模糊关键字的索引文件。

3.2 安全性分析

定义1BDH问题。

定义2BDH假设。

本文方案的密文不可伪造是基于BDH的困难性问题。在本文方案的Encrypt算法中，将(aP,bP)嵌入到公钥中，并且对于带加密的关键字，使用服务器公钥和发送者的公钥进行加密运算。由于HASH函数h2的不可逆性，将随机数x嵌入到加密密文中，因此，攻击者无法对密文进行伪造。

本文方案的陷门满足陷门不可伪造安全性。陷门的安全使得外部攻击者对搜索信息一无所知。因为待搜索的关键字嵌入在了HASH函数h1(w′)中。将h1(w′)和服务器私钥a相结合可得陷门Tw′=ah1(w′)。由于外部攻击者无法获得服务器的私钥，因此外部攻击者无法对陷门进行伪造，实现了陷门的不可伪造性。

本文方案在进行密文传输时不需要额外的安全信道来保证信息的安全性。将服务器私钥和陷门算法相结合，即使外部攻击者截取了陷门Tw′，但是无法获取到服务器的私钥，因此外部攻击者无法获得陷门与关键字之间的对应关系，对于陷门中的内容一无所知，因此确保了陷门在公共信道上传输的安全性。

4 性能分析

将本文方案与之前的方案进行对比，结果如表1所示。

表1 各方案的特征对比

通过对比发现，本文方案和文献[19]方案在功能和安全性上有着相同的特性，下面将本文方案与其他2种方案的效率进行对比。在算法执行过程中，主要运算有指数运算、双线性对运算和乘法操作，其中双线性对运算的代价较高。本文使用tP、tE和tM分别表示指数操作、双线性映射和乘法操作,效率对比如表2所示。

表2 本文方案与其他方案效率对比

方案加密阶段和验证阶段的效率对比如图2和图3所示。

图2 加密算法计算效率对比

图3 验证算法计算效率对比

通过分析表明，本文方案在具有相同功能的方案中具有优秀的性能表现。在测试和解密阶段，本文方案也拥有较为明显的效率优势。

5 结束语

本文提出了一种无安全信道的模糊关键字加密搜索方案，并验证了该方案的安全性。针对大多数可搜索加密方案需要安全信道的缺点，本文提出的方案不需要安全信道的特点大大增加了系统的使用场景，在效率分析阶段，本文对比了具有相同功能的无安全信道的模糊关键字加密搜索方案，通过对比发现，在具有相同功能的方案之中，本文方案有着更高的执行效率。