基于Simhash的安全密文排序检索方案

doi:10.11772/j.issn.1001-9081.2019020269

计算机应用 ›› 2019, Vol. 39 ›› Issue (9): 2623-2628.DOI: 10.11772/j.issn.1001-9081.2019020269

基于Simhash的安全密文排序检索方案

李珍^1,2, 姚寒冰^1,2, 穆逸诚¹

1. 武汉理工大学计算机科学与技术学院, 武汉 430063;
2. 交通物联网技术湖北省重点实验室(武汉理工大学), 武汉 430070

收稿日期:2019-02-18 修回日期:2019-03-29 发布日期:2019-04-25 出版日期:2019-09-10
通讯作者: 李珍
作者简介:李珍(1994-),女,河南商丘人,硕士研究生,主要研究方向:信息安全;姚寒冰(1976-),男,湖北武汉人,副教授,博士,主要研究方向:信息安全;穆逸诚(1998-),男,湖北武汉人,主要研究方向:信息安全。
基金资助:
内河航运技术湖北省重点实验室基金资助项目（NHHY2017003）；交通物联网技术湖北省重点实验室基金资助项目（2017Ⅲ028-002）。

Secure ranked search scheme based on Simhash over encrypted data

LI Zhen^1,2, YAO Hanbing^1,2, MU Yicheng¹

1. College of Computer Science and Technology, Wuhan University of Technology, Wuhan Hubei 430063, China;
2. Hubei Key Laboratory of Transportation Internet of Things(Wuhan University of Technology), Wuhan Hubei 430070, China

Received:2019-02-18 Revised:2019-03-29 Online:2019-04-25 Published:2019-09-10
Supported by:
This work is partially supported by the Fund of Hubei Key Laboratory of Inland Shipping Technology (NHHY2017003), the Fund of Hubei Key Laboratory of Transportation Internet of Things (2017Ⅲ028-002).

摘要/Abstract

摘要：

针对密文检索中存在的计算量大、检索效率不高的问题，提出一种基于Simhash的安全密文排序检索方案。该方案基于Simhash的降维思想构建安全多关键词密文排序检索索引（SMRI），将文档处理成指纹和向量，利用分段指纹和加密向量构建B+树，并采用"过滤-精化"策略进行检索和排序，首先通过分段指纹的匹配进行快速检索，得到候选结果集；然后通过计算候选结果集与查询陷门的汉明距离和向量内积进行排序，带密钥的Simhash算法和安全k近邻（SkNN）算法保证了检索过程的安全性。实验结果表明，与基于向量空间模型（VSM）的方案相比，基于SMRI的排序检索方案计算量小，能节约时间和空间成本，检索效率高，适用于海量加密数据的快速安全检索。

关键词: 密文检索, 排序检索, Simhash, 隐私保护, 安全k近邻

Abstract:

Concerning the large computation and low search efficiency in ciphertext retrieval, a secure ranked search scheme based on Simhash was proposed. In this scheme, a Secure Multi-keyword Ranked search Index (SMRI) was constructed based on the dimensionality reduction idea of Simhash, the documents were processed into fingerprints and vectors, the B+ tree was built with the segmented fingerprints and encrypted vectors and the "filter-refine" strategy was adopted to searching and sorting. Firstly, the candidate result set was obtained by matching the segmented fingerprints to perform the quick retrieval, then the top-k results were ranked by calculating the Hamming distance and the vector inner product between candidate result set and query trapdoor, and the Simhash algorithm with secret key and the Secure k-Nearest Neighbors (SkNN) algorithm ensured the security of the retrieval process. Simulation results show that compared with the method based on Vector Space Model (VSM), the SMRI-based ranked search scheme has lower computational complexity, saves time and space cost, and has higher search efficiency. It is suitable for fast and secure retrieval of massive ciphertext data.

Key words: ciphertext retrieval, ranked search, Simhash, privacy-preserving, Secure k-Nearest Neighbors (SkNN)

中图分类号:

TP391

李珍, 姚寒冰, 穆逸诚. 基于Simhash的安全密文排序检索方案[J]. 计算机应用, 2019, 39(9): 2623-2628.

LI Zhen, YAO Hanbing, MU Yicheng. Secure ranked search scheme based on Simhash over encrypted data[J]. Journal of Computer Applications, 2019, 39(9): 2623-2628.

参考文献

[1] 冯登国,张敏,张妍,等.云计算安全研究[J].软件学报,2011,22(1):71-83.(FENG D G, ZHANG M, ZHANG Y, et al. Study on cloud computing security[J]. Journal of Software, 2011, 22(1):71-83.)
[2] SONG D X, WAGNER D, PERRIG A. Practical techniques for searches on encrypted data[C]//Proceedings of the 2000 IEEE Symposium on Security and Privacy. Piscataway, NJ:IEEE, 2000:44-55.
[3] GOH E. Secure indexes[EB/OL].[2018-12-16]. https://eprint.iacr.org/2003/216.pdf.
[4] KUZU M, ISLAM M S, KANTARCIOGLU M. Efficient similarity search over encrypted data[C]//Proceedings of the IEEE 28th International Conference on Data Engineering. Piscataway, NJ:IEEE, 2012:1156-1167.
[5] KRISHNA C R, MITTAL S A. Privacy preserving synonym based fuzzy multi-keyword ranked search over encrypted cloud data[C]//Proceedings of the 2016 International Conference on Computing, Communication and Automation. Piscataway, NJ:IEEE, 2016:1187-1194.
[6] WANG J, YU X, ZHAO M. Privacy-preserving ranked multi-keyword fuzzy search on cloud encrypted data supporting range query[J]. Arabian Journal for Science and Engineering, 2015, 40(8):2375-2388.
[7] YAO H, XING N, ZHOU J, et al. Secure index for resource-constraint mobile devices in cloud computing[J]. IEEE Access, 2016, 4:9119-9128.
[8] LI X, CUI Y, ZHOU M, et al. Efficient multi-keyword fuzzy search on encrypted data in cloud storage[C]//Proceedings of the 2017 4th International Conference on Information Science and Control Engineering. Washington, DC:IEEE Computer Society, 2017, 1:288-294.
[9] CAO N, WANG C, LI M, et al. Privacy-preserving multi-keyword ranked search over encrypted cloud data[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(1):222-233.
[10] LI H, YANG Y, LUAN T H, et al. Enabling fine-grained multi-keyword search supporting classified sub-dictionaries over encrypted cloud data[J]. IEEE Transactions on Dependable and Secure Computing, 2016, 13(3):312-325.
[11] WONG W K, CHEUNG D W, KAO B, et al. Secure kNN computation on encrypted databases[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2009:139-152.
[12] XIA Z, WANG X, SUN X, et al. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data[J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(2):340-352.
[13] ZHU X, DAI H, YI X, et al. MUSE:an efficient and accurate verifiable privacy-preserving multi-keyword text search over encrypted cloud data[J]. Security and Communication Networks, 2017, 2017(2):No.1923476.
[14] CHEN L, SUN X, XIA Z, et al. An efficient and privacy-preserving semantic multi-keyword ranked search over encrypted cloud data[J]. International Journal of Security and its Applications, 2014, 8(2):323-332.
[15] 杨宏宇,王玥.云存储环境下的多关键字密文搜索方法[J].计算机应用,2018,38(2):343-347.(YANG H Y, WANG Y. Multi-keyword ciphertext search method in cloud storage environment[J]. Journal of Computer Applications, 2018, 38(2):343-347.)
[16] CHARIKAR M S. Similarity estimation techniques from rounding algorithms[C]//Proceedings of the 34th Annual ACM Symposium on Theory of Computing. New York:ACM, 2002:380-388.
[17] MANKU G S, JAIN A, das SARMA A. Detecting near-duplicates for Web crawling[C]//Proceedings of the 16th International Conference on World Wide Web. New York:ACM, 2007:141-150.
[18] 杨旸,杨书略,柯闽.加密云数据下基于Simhash的模糊排序搜索方案[J].计算机学报,2017,40(2):431-444.(YANG Y, YANG S L, KE M. Ranked fuzzy keyword search based on Simhash over encrypted cloud data[J]. Chinese Journal of Computers, 2017, 40(2):431-444.)

基于Simhash的安全密文排序检索方案

Secure ranked search scheme based on Simhash over encrypted data

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李卓, 宋子晖, 沈鑫, 陈昕. 边缘计算支持下的移动群智感知本地差分隐私保护机制[J]. 计算机应用, 2021, 41(9): 2678-2686.
[2]	秦静, 安雯, 季长清, 汪祖民. 无线体域网隐私保护机制研究综述[J]. 计算机应用, 2021, 41(4): 970-975.
[3]	刘向宇, 夏国平, 夏秀峰, 宗传玉, 朱睿, 李佳佳. 个性化时空数据隐私保护[J]. 计算机应用, 2021, 41(3): 643-650.
[4]	张恩, 李会敏, 常键. 可验证的隐私保护k-means聚类方案[J]. 计算机应用, 2021, 41(2): 413-421.
[5]	陈锦宇, 刘兆伟. 基于改进投票证明共识协议的车联网系统[J]. 计算机应用, 2021, 41(1): 170-176.
[6]	马敏耀, 刘卓, 徐艺, 吴恋. 隐私保护整数区间位置关系判定问题[J]. 计算机应用, 2020, 40(9): 2657-2664.
[7]	吕佳玉, 竺智荣, 姚志强. 云计算环境下的双通道数据动态加密策略[J]. 计算机应用, 2020, 40(8): 2268-2273.
[8]	马敏耀, 吴恋, 刘卓, 徐艺. 隐私保护整数点和区间关系判定问题[J]. 计算机应用, 2020, 40(7): 1983-1988.
[9]	龙洋洋, 陈玉玲, 辛阳, 豆慧. 基于联盟区块链的安全能源交易方案[J]. 计算机应用, 2020, 40(6): 1668-1673.
[10]	杨洋, 王汝传. 增强现实中基于位置安全性的LBS位置隐私保护方法[J]. 计算机应用, 2020, 40(5): 1364-1368.
[11]	拜亚萌, 满君丰, 张宏. 基于区块链的电子健康记录安全存储模型[J]. 计算机应用, 2020, 40(4): 961-965.
[12]	罗惠雯, 龙士工. 基于用户感兴趣区域的地理不可区分性的位置扰动算法[J]. 计算机应用, 2020, 40(3): 760-764.
[13]	刘向宇, 陈金梅, 夏秀峰, Singh Manish, 宗传玉, 朱睿. 防止暴露位置攻击的轨迹隐私保护[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 479-485.
[14]	张梅舒, 徐雅斌. 多维数值型敏感属性数据的个性化隐私保护方法[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 491-496.
[15]	金鑫, 王涛春, 吕成梅, 王成田, 陈付龙, 赵传信. 移动群智感知中原始数据隐私保护算法[J]. 计算机应用, 2020, 40(11): 3249-3254.