Computer Engineering and Applications ›› 2018, Vol. 54 ›› Issue (13): 78-83.DOI: 10.3778/j.issn.1002-8331.1706-0283

Previous Articles     Next Articles

Fast keyword query technique in encrypted databases

ZHANG Man1, XIAN Hequn1,2, ZHANG Shuguang1   

  1. 1.College of Computer Science and Technology, Qingdao University, Qingdao, Shangdong 266071, China
    2.Key Laboratory of Network Assessment Technology, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
  • Online:2018-07-01 Published:2018-07-17


张  曼1,咸鹤群1,2,张曙光1   

  1. 1.青岛大学 计算机科学技术学院,山东 青岛 266071
    2.中国科学院 信息工程研究所中国科学院网络测评技术重点实验室,北京 100093

Abstract: In order to ensure the data security of sensitive information, users usually encrypt data before sending them to the cloud, which increases the 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 procedure, the client calculates trapdoors and sends it to the server, the server then executes the query according to the trapdoors. A multi-keywords query can be converted into single keyword query problems by concatenating trapdoors of multiple keywords, with the same time complexity. In addition, valid trapdoors can only be generated with secret keys by owners and the trapdoors don’t leak any sensitive information. This scheme does not rely on fully trusted database service providers. 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 with TPC-H developing performance data. Experimental results show that the scheme very efficient in query execution.

Key words: Bloom filter, encrypted database, keyword query, Pseudo-Random Functions

摘要: 为保证敏感信息的数据安全,用户通常会将其加密后存储到云端数据库,这为数据库管理及后续使用增加了难度。提出一种安全查询方案,在不暴露敏感信息的情况下可获得符合查询条件的结果集。使用伪随机函数和Bloom过滤器,对敏感信息的关键词集合进行预处理,在数据库中生成相应的索引数据结构,支持不固定数量的关键词查询与高效的数据更新。查询时,客户端计算出关键词相应的陷门并将其发送给服务器,服务器使用陷门执行查询,将多关键词计算出的陷门进行串接,可将多关键词查询问题转换成单关键词查询问题,并且不提高时间复杂度。此外,有效的陷门只能由拥有密钥的用户产生,陷门不会泄露任何敏感信息,故该方案不依赖完全可信的数据库服务提供商。与现有的采用特殊双层结构的加密方式相比,提高了查询效率,解决了加密数据库处理用户查询请求时的敏感信息泄露问题,且允许用户对敏感信息采用不同的加密方式,具有很强的兼容性。使用TPC-H的数据库测试方案和测试数据进行实验,实验结果证明了算法具有较高的执行效率。

关键词: Bloom过滤器, 加密数据库, 关键词查询, 伪随机函数