具有隐私保护的完整性可验证的关键字搜索方案

刘雪艳 芦婷婷 杨晓涛

(西北师范大学数学与统计学院 兰州 730070)

1 引言

随着大数据和云计算时代的到来，越来越多的个人和企业将大量私有数据上传到云中，从而节省本地存储和管理成本。为了保证数据的机密性和隐私性，数据属主需要将数据加密后再上传到云中，传统的明文搜索不适用于当前需求。2000年，Song等人[1]提出了可搜索加密(Searchable Encryption, SE)的概念，实现了不解密密文情况下对密文的快速检索。2004 年，Boneh等人[2]首次提出了公钥可搜索加密的概念，随后，具有连接关键词[3,4]、模糊关键词[5]、动态关键字[6,7]、子集关键字[8]等功能的公钥可搜索加密方案也相继被提出。但是在实际应用中，数据拥有者往往无法预先确定所有访问者的信息，但是又希望能控制共享数据的访问权限，并且实现一对多的通信模式，显然传统的公钥可搜索加密和基于身份的可搜索加密技术已经不能解决这一难题，而基于属性关键字搜索(Attribute-Based Keyword Search, ABKS)的加密机制引起众多学者的关注。

基于属性关键词搜索加密机制是一对多的公钥加密搜索方式：数据属主可以使用自己定义的访问结构加密关键字和共享信息，属性集满足访问结构的用户才能获得搜索授权和解密操作。文献[9]在属性加密方案[10]的基础上提出基于属性的密文检索方案，该方案实现了快速关键字搜索，但没有对搜索结果进行验证。Ameri等人[11]在密钥策略属性加密方案[12]的基础上提出一个密钥策略的可搜索加密方案，该方案在搜索令牌中加入时间戳，只能提取在指定时间间隔内生成的密文。Miao 等人[13,14]提出了一种可验证的关键字搜索方案，通过对每个密文文档设置签名，由第三方审计检验返回密文的正确性，但是该方案密文大小与属性的个数成正比，导致搜索时间随属性的增加而增加。Ballard等人[15]提出动态的关键字搜索方案，采用Merkle 树实现数据的完整性认证，但是，该认证方法不支持多关键字搜索。为解决上述问题，文献[7]提出完整性验证的多关键字搜索方案，减少了计算量。文献[16]提出支持属性撤销的关键字搜索方案，该方案将繁重的代理重加密工作交给授权中心，造成授权中心的瓶颈。随后一些支持代理重加密等特点的关键字搜索方案相继被提出[17,18]，但是由于将访问结构和索引一起发送给云服务器，导致访问结构信息泄露问题。文献[19]提出了隐藏访问结构的ABKS方案，并支持属性撤销，但该方案只适合单个关键字的搜索。还出现了一些具有其它特色的搜索方案[20,21]，但这些方案都没有考虑关键字搜索。

本文将关键字搜索技术与ABE技术结合，提出具有隐私保护的完整性可验证的关键字搜索方案，实现了细粒度的搜索授权，主要工作有：(1)方案采用了一个有序多值属性访问结构和有序多值属性集，固定每个属性的位置，减少参数及相关计算，提高了方案的效率；(2)方案采用倒序索引结构和Merkle哈希树生成数据认证树，实现对云服务器返回密文的完整性认证，防止云服务器对数据的恶意篡改和返回不正确的结果；(3)为了防止访问结构泄露和保护用户身份隐私性，采用hash及对运算实现对访问结构的隐藏；(4)外包解密技术减少了用户侧的计算开销。

2 准备工作

2.1 判定性DL(Decisional Linear)假设

2.2 有序多值属性访问结构

2.3 Merkle 哈希树

2.4 倒序索引结构与数据认证树

表1 属性值

图1 Merkel树

3 可实现隐私保护的关键字搜索方案

3.1 系统模型

图2 倒序索引列表

图3 数据认证

图4 系统模型

本文方案主要有4个实体(如图4)：数据属主(DO)，数据用户(DU)，授权中心(TA)，云服务器(CSP)。TA是可信的，为系统产生公钥和主密钥，并为用户产生私钥，用户的私钥与自身属性相关。DO决定访问策略并加密对称钥，建立关键字索引，为每个关键字建立密文认证树，将索引、认证树、密文文档发送给云服务器。CSP是诚实又好奇的，它会诚实地遵守协议但又试图解密文档，CSP分为存储服务器和解密服务器。存储服务器存储和管理数据属主上传的关键字索引、加密文档，并通过判断用户上传的门限值提供相应的检索服务。DU收到密文，将其外包给解密服务器进行部分解密，并检验返回密文与外包解密的正确性。

3.2 方案描述

图5 访问结构的隐藏

图6 用户属性集的转化

4 正确性分析与安全性证明

4.1 正确性分析

4.2 安全性证明

5 性能分析

5.1 理论分析

5.2 实验分析

本小节对本方案和文献[13,19]的密钥生成算法、门限生成算法、搜索和解密算法进行了实验仿真。仿真平台Windows 10，AMD A8-6410 APU with AMD Randeon R5 Graphics 2.00 GHz，内存为8 GB，代码库PBC(Paring-Based Cryptography[22])，使用大素数为512位。从图7-图10可以看出，本文方案与文献[13]方案在密钥生成、门限生成、搜索阶段效率几乎持平，但是在解密阶段效率高很多，而相比文献[19]的各个阶段，本文方案是高效的。图11和图12分别给出本文方案在属性个数变化时多关键字情形下，门限生成时间与搜索时间，从图中可以得出，门限生成与属性个数和各关键字个数无关，而搜索阶段仅与关键字个数有关，其余两个方案不支持多关键字搜索。

6 结束语

本文就不可信云环境下，提出具有隐私保护的完整性可验证的ABKS方案。方案提出有序多值属性访问结构和有序多值属性集，固定每个属性的位置，减少参数及相关计算，提高了方案的效率；采用Hash和对运算实现访问结构的隐藏，保护了访问结构的安全性与用户身份的隐私性；在密钥生成时计算具体属性取值的哈希值，从而达到区别多值属性取值的不同；同时，采用倒序索引结构和Merkle树建立数据认证树，实现对云服务器返回密文的完整性认证并确保外包解密的正确性，防止云服务器对数据的恶意篡改和返回不正确的结果。此外，充分利用云的计算能力，支持外包解密以降低用户侧的计算量。安全性分析和实验表明，本文方案可实现云中共享数据的可验证性、关键字不可区分性和关键字不可链接性，且是高效的。在未来工作中，将探索云存储中的关键字的更新和文件的删除和添加。

表2 功能比较

表3 通信开销比较

表4 计算开销比较

图7 密钥生成阶段

图8 门限生成阶段

图9 搜索阶段

图10 解密阶段

图11 多关键字搜索阶段

图12 多关键字门限生成阶段