张曼;咸鹤;张曙光
【摘 要】为保证敏感信息的数据安全,用户通常会将其加密后存储到云端数据库,这为数据库管理及后续使用增加了难度.提出一种安全查询方案,在不暴露敏感信息的情况下可获得符合查询条件的结果集.使用伪随机函数和Bloom过滤器,对敏感信息的关键词集合进行预处理,在数据库中生成相应的索引数据结构,支持不固定数量的关键词查询与高效的数据更新.查询时,客户端计算出关键词相应的陷门并将其发送给服务器,服务器使用陷门执行查询,将多关键词计算出的陷门进行串接,可将多关键词查询问题转换成单关键词查询问题,并且不提高时间复杂度.此外,有效的陷门只能由拥有密钥的用户产生,陷门不会泄露任何敏感信息,故该方案不依赖完全可信的数据库服务提供商.与现有的采用特殊双层结构的加密方式相比,提高了查询效率,解决了加密数据库处理用户查询请求时的敏感信息泄露问题,且允许用户对敏感信息采用不同的加密方式,具有很强的兼容性.使用TPC-H的数据库测试方案和测试数据进行实验,实验结果证明了算法具有较高的执行效率.%In order to ensure the data security of sensitive information, users usually encrypt data before sending them to the cloud, which increases t he difficulty for database management and queries on the encrypted data. This paper proposes a security query scheme which can obtain eligible query results without revealing sensitive information. Pseudo random functions and Bloom filters are employed to pre-process keywords of sensitive information to generate the corresponding index data structure. This scheme supports various number of keywords-query and efficient data update. In a query proce-dure, the client calculates trapdoors and sends it to the server, the server then executes the query according to the trap-doors. A multi-keywords query can be converted into single keyword query problems by concatenating trapdoors of multi-ple keywords, with the same time complexity. In addition, valid trapdoors can only be generated with secret keys by own-ers and the trapdoors don’t leak any sensitive information. This scheme does not rely on fully trusted database service pro-viders. Compared with existing special double layer structure encryption methods, this scheme improves the efficiency and avoids revealing sensitive information during searching on the encrypt database. This scheme has strong compatibility, for it allows the user to encrypt sensitive information with various encryption method. The experiment is carried w
ith TPC-H developing performance data. Experimental results show that the scheme very efficient in query execution.
【期刊名称】《计算机工程与应用》
【年(卷),期】2018(054)013
【总页数】7页(P78-83,141)
【关键词】Bloom过滤器;加密数据库;关键词查询;伪随机函数
【作 者】张曼;咸鹤;张曙光
【作者单位】青岛大学 计算机科学技术学院,山东 青岛 266071;青岛大学 计算机科学技术学院,山东 青岛 266071;中国科学院 信息工程研究所中国科学院网络测评技术重点实验室,北京 100093;青岛大学 计算机科学技术学院,山东 青岛 266071
【正文语种】中 文
【中图分类】TP309
1 引言
随着云计算的迅速发展以及用户对本地存储空间的要求不断提升，云计算能够为用户提供强大而便捷的数据存储、处理、和共享服务，这种新兴的计算模式迅速获得企业、服务商和用户的青睐。更多的用户选择把本地海量信息迁移至服务器，其中可能含有一些敏感数据。半可信的数据库服务提供商（DataBase Service Provider，DBSP）成为了新的安全威胁。Hacigumus等人[1]2002年最早提出“DAS 模型”（Database As a Service），DAS模型是云存储中的一种新型数据库应用体系。在DAS模型中，数据所有者将数据交由DBSP管理，数据库以服务的形式提供。DBSP负责用户数据的存取、管理和查询服务，这意味着DBSP可在无访问控制的情况下获取用户数据。因此，DAS模型的最大安全威胁来自于内部的数据管理者，而并非数据库的外部攻击者。在这种不可信的环境中，使用数据库加密可以充分保护数据安全，但在查询时需对密文逐一解密，导致查询性能急剧下降。云计算/云服务模式的普及与应用受到安全性和隐私性问题的制约[2]。为保证信息的安全性，用户通常会将敏感数据加密，将其以密文的形势存储在另一个可信域。但是密文形式的存储方式会给数据的操作与管理带来额外的负担，传统的关系数据库查询语言无法直接执行。因此，在保证不泄露敏感信息的同时，如何在加密数据库快速关键词查询成为了一个研究
热点。
可搜索加密（Searchable Encryption，SE）是近年来发展的一种支持用户在密文上进行关键词查的密码学原语，它能够为用户节省大量的存储和计算开销[3]，保证隐私泄漏的最小化。同一时期，Hacigumus[4]等人提出，用户在存储明文数据到第三方服务器之前要先对明文数据进行加密；并且首次提出桶划分的思想，提高查询效率。2004年，Hore[5]等人对加密数据的桶划分技术进行了进一步研究，针对数据库的范围查询提出了一种保护隐私的索引方案。但上述方法缺少对桶地址进行保护，攻击者容易利用穷举攻击暴力获取用户的数据。文献[6]最先提出借助ORAM（Oblivious RAM）隐藏用户访问数据的访问模式，让攻击者无法对用户所访问的信息进行穷举分析。Curtmola[7]等提出基于安全索引的SSE方案，具有更高的安全性，可以隐藏访问模式和搜索模式，但需要引入第三方IS服务器。在此期间，也涌现出了一些对密文查询结果进行匹配度排序的相关研究，Wong[6]提出了存储在不可信服务器上加密数据的k邻近查询；Cao等人[8]通过对每一个文档建立索引向量，可以返回匹配度较高的前n个文件。也有研究者提出结果可验证的方案，Wang[9]等人使用反向索引，利用顺序保持加密技术对文件的关键词频率进行加密，支持用户对返回的结果进行验证。Sun等人[10]借助多维B树和余弦相似性测量，提出了一种精确可验证的安
全多关键词密文搜索方案。Raykova等人[11]提出借助Bloom过滤器构建安全的匿名数据库搜索方案，以此解决共享者之间如何确认共享数据的问题。此外，Chang[12]等人和Curtmola[7]等人提出，利用伪随机技术构建关键词索引和查询请求，虽然效率较Song等人[13]有所提高，但当数据更新时需要重构整个索引。Vimercati等人[14]提出一种将访问控制和可搜索加密相融合的方案，能够解决安全泄露问题，但性能较低。
近几年，Raluca分析DAS模型面临的两种威胁，提出CryptDB方案[15]。Boneh[16]等利用代数结构构建非对称可搜索加密方案，即PEKS方案。李晋国等人[17]首次提出了融合具有高编码效率的Huffman编码和具有数据存储优势的Bloom过滤器，实现了DAS模式下保护隐私的模糊关键字查询处理。Lu[18]给出一种可隐藏搜索模式的对称可搜索加密方案，将明文中出现的单词进行分组，搜索结果相同的单词分为一组，同组单词生成相同的陷门，从而使敌手无法区分。
目前的方案中，有些方案需借助第三方，对用户加密方式的选择存在限制；有些方案在安全性和查询效率方面有待提升。本文提出一种支持用户安全查询的高效方案，该方案支持数据所有者以及被授权对象（以下统称为用户）进行不固定数量的关键词并集查询。本文
的贡献：首次利用Bloom过滤器在数据库中构建索引数据结构，提高了查询效率；支持用户对敏感字段进行任何形式的加密，实用性强；不依赖任何可信/非可信第三方。
2 预备知识
2.1 Bloom过滤器
Bloom过滤器是一种存储有效的向量型数据结构，通常由多个比特位组成的特殊向量阵列构成。Bloom过滤器可用于判别单个元素和指定集合之间的隶属关系。具体做法如下：
（1）初始化长度为m的Bloom过滤器，各个比特位的初始值设为0。
（2）选取k个独立同分布的映射函数{ }ƒ1,ƒ2,…,ƒk，使得映射函数将任意元素映射到向量阵列相应比特位是等概率的[19]。
（3）对含有τ个元素的集合S={ }x1,x2,…,xτ中每个向量阵列中对应的比特位的值设置为1。
（4）如果要判断某个元素item是否属于S，需要判k个比特位是否都为1。若任意一个位置为0，则item一定不在S中，反之item以较大的概率在S中。
显然，Bloom过滤器存在误判的情况。一般的，设已知条件为：
2.2 安全索引
安全索引是经过特定算法计算出的数据结构，作为数据库表的一列存储。本文提出的安全索引与数据库中的索引不同。安全索引的意义是保障云端数据库查询安全。当用户对云端数据库查询时，将加密后的查询条件与安全索引比较，从而判断记录是否符查询条件，保障数据库查询时安全。
