基于聚类索引的多关键字排序密文检索方案
|
摘要
为了提高密文检索的效率和精度,提出基于聚类索引的多关键字排序密文检索方案.首先利用改进的Chameleon算法对文件向量聚类,聚类过程中通过记录关键字位置对文件向量进行降维处理.其次,提出适合聚类索引的检索算法,使得在查询过程中可以排除大量与查询向量无关的文件向量,减少了不必要的计算消耗.再次,在聚类过程中引入杰卡德相似系数来计算文件向量之间的相似度以及设定合适的阈值提高聚类质量.在真实数据集上进行了实验,理论分析和实验结果表明:在保障数据隐私安全的前提下,该方案较传统的密文检索方案有效地提高了密文检索的效率与精度.
Data owners prefer to outsource documents in an encrypted form for the purpose of privacy preserving. But existed encrypting technologies make it difficult to search for encrypted data, which limit the availability of outsourced data. This will make it even more challenging to design ciphertext search schemes that can provide efficient and reliable online information retrieval. In order to improve the efficiency and precision of ciphertext retrieval, we propose a multi-keyword ciphertext retrieval scheme based on clustering index. Firstly, the improved Chameleon algorithm is used to cluster the file vectors during which the file vectors are dimensioned by recording the position of the key words. Secondly, a retrieval algorithm suitable for clustering index is proposed, which makes it possible to eliminate a large number of file vectors irrelevant to the query vector in the query process, and reduce unnecessary consumption. Finally, in the clustering process, Jaccard similarity coefficient is introduced to calculate the similarity between the file vectors and to set the appropriate threshold to improve the quality of the cluster. The theory analysis and experimental results show that the scheme can effectively improve the efficiency and precision of ciphertext retrieval under the premise of guaranteeing the privacy and security of data.
Data owners prefer to outsource documents in an encrypted form for the purpose of privacy preserving. But existed encrypting technologies make it difficult to search for encrypted data, which limit the availability of outsourced data. This will make it even more challenging to design ciphertext search schemes that can provide efficient and reliable online information retrieval. In order to improve the efficiency and precision of ciphertext retrieval, we propose a multi-keyword ciphertext retrieval scheme based on clustering index. Firstly, the improved Chameleon algorithm is used to cluster the file vectors during which the file vectors are dimensioned by recording the position of the key words. Secondly, a retrieval algorithm suitable for clustering index is proposed, which makes it possible to eliminate a large number of file vectors irrelevant to the query vector in the query process, and reduce unnecessary consumption. Finally, in the clustering process, Jaccard similarity coefficient is introduced to calculate the similarity between the file vectors and to set the appropriate threshold to improve the quality of the cluster. The theory analysis and experimental results show that the scheme can effectively improve the efficiency and precision of ciphertext retrieval under the premise of guaranteeing the privacy and security of data.
引文
[1]Dong Xiaolei, Zhou Jun, Cao Zhenfu. Research progress of searchable encryption[J]. Journal of Computer Research and Development, 2017, 54(10): 2107- 2120 (in Chinese)(董晓蕾, 周俊, 曹珍富. 可搜索加密研究进展[J]. 计算机研究与发展, 2017, 54(10): 2107- 2120)
[2]Song Xiaodong, Wagner D, Perrig A. Practical techniques for searches on encrypted data[C] //Proc of the 21st IEEE Symp on Security and Privacy 2000. Piscataway, NJ: IEEE, 2000: 44- 55
[3]Liesdonk P V, Sedghi S, Doumen J, et al. Computationally efficient searchable symmetric encryption[C] //Proc of VLDB Conf on Secure Data Management. Berlin: Springer, 2010: 87- 10
[4]Curtmola R, Garay J, Kamara S, Ostrovsky R. Searchable symmetric encryption: Improved definitions and efficient constructions[C] //Proc of the 13th ACM Conf Computer and Communications Security. New York: ACM, 2006: 79- 88
[5]Cao Ning, Wang Cong, Li Ming, et al. Privacy-preserving multi-keyword ranked search over encrypted cloud data[J]. IEEE Transactions on Parallel & Distributed Systems, 2013, 25(1): 222- 233
[6]Sun Wenhai, Wang Bing, Cao Ning, et al. Verifiable privacy-preserving multi-keyword text search in the cloud supporting similarity-based ranking[J]. IEEE Transactions on Parallel & Distributed Systems, 2014, 25(11): 3025- 3035
[7]Chen Xiaofeng, Huang Xinyi, Li Jin, et al. New algorithms for secure outsourcing of large-scale systems of linear equations[J]. IEEE Transactions on Information Forensics & Security, 2014, 10(1): 69- 78
[8]Li Hongwei, Yang Yi, Luan T H, et al. Enabling fine-grained multi-keyword search supporting classified sub-dictionaries over encrypted cloud data[J]. IEEE Trans-actions on Dependable & Secure Computing, 2016, 13(3): 312- 325
[9]Xia Zhihua, Wang Xinhui, Sun Xingming, et al. A sucure and dynamic multi-keyword ranked search scheme over encrypt cloud data[J]. IEEE Transactions on Parallel and Distributed System, 2016, 27(2): 951- 963
[10]Tian Xue, Zhu Xiaojie, Shen Peisong, et al. Fast cryptographic retrieval based on similar query tree[J]. Journal of Software, 2016, 27(6): 1566- 1576 (in Chinese)(田雪, 朱晓杰, 申培松, 等. 基于相似查询树的快速密文检索方法[J]. 软件学报, 2016, 27(6): 1566- 1576)
[11]Wang Chong. R-tree index method based on Chameleon clustering algorithm[D]. Harbin: Harbin Institute of Technology, 2017 (in Chinese)(王冲. 基于Chameleon聚类算法的R树索引方法研究[D]. 哈尔滨: 哈尔滨工大学, 2017)
[12]Chen Chi, Zhu Xiaojie, Shen Peisong, et al. An efficient privacy-preserving ranked keywords search method[J]. IEEE Transactions on Parallel & Distributed Systems, 2016, 27(4): 951- 963
[13]Yang Yang, Yang Shulüe, Ke Min. Ranked fuzzy keyword search based on simhash over encrypted cloud data[J]. Chinese Journal of Computers, 2017, 40(2): 431- 444 (in Chinese)(杨旸, 杨书略, 柯闽. 加密云数据下基于Simhash的模糊排序搜索方案[J]. 计算机学报, 2017, 40(2): 431- 444)
[14]Witten I H, Moffat A, Bell T C. Managing gigabytes: Compressing and indexing documents and images[J]. IEEE Transactions on Information Theory, 1995, 41(6): 79- 80
[15]Yang Jun, Liu Zheli, Li Jin, et al. Multi-key searchable encryption without random oracle[J]. Intelligent Networking and Collaborative Systems, 2014, 30(1): 179- 190
[16]Hui Zhen, Feng Dengguo, Zhang Min, et al. A secure index against statistical analysis attacks[J]. Computer Research and Development, 2017, 54(2): 295- 304 (in Chinese)(惠榛, 冯登国, 张敏, 等. 一种可抵抗统计攻击的安全索引[J]. 计算机研究与发展, 2017, 54(2): 295- 304)
[17]Red Hat. CentOS-7-x86_64-DVD-1708. iso[OL]. [2017-01-28]. http://is oredirect.centos.org/centos/7/isos/x86_64/CentOS-7-x86_64-DVD-1708.iso
[18]Jason R. 20_newsgroups. tar. gz[DB/OL]. [2017-01-29]. http://download.cs dn.net/index.php/mobile/source/download/bukaohuaxue/851012
[19]Apache. Lucene3[OL]. [2017-09-28]. http://Jakarta.apache.org/lucene
[2]Song Xiaodong, Wagner D, Perrig A. Practical techniques for searches on encrypted data[C] //Proc of the 21st IEEE Symp on Security and Privacy 2000. Piscataway, NJ: IEEE, 2000: 44- 55
[3]Liesdonk P V, Sedghi S, Doumen J, et al. Computationally efficient searchable symmetric encryption[C] //Proc of VLDB Conf on Secure Data Management. Berlin: Springer, 2010: 87- 10
[4]Curtmola R, Garay J, Kamara S, Ostrovsky R. Searchable symmetric encryption: Improved definitions and efficient constructions[C] //Proc of the 13th ACM Conf Computer and Communications Security. New York: ACM, 2006: 79- 88
[5]Cao Ning, Wang Cong, Li Ming, et al. Privacy-preserving multi-keyword ranked search over encrypted cloud data[J]. IEEE Transactions on Parallel & Distributed Systems, 2013, 25(1): 222- 233
[6]Sun Wenhai, Wang Bing, Cao Ning, et al. Verifiable privacy-preserving multi-keyword text search in the cloud supporting similarity-based ranking[J]. IEEE Transactions on Parallel & Distributed Systems, 2014, 25(11): 3025- 3035
[7]Chen Xiaofeng, Huang Xinyi, Li Jin, et al. New algorithms for secure outsourcing of large-scale systems of linear equations[J]. IEEE Transactions on Information Forensics & Security, 2014, 10(1): 69- 78
[8]Li Hongwei, Yang Yi, Luan T H, et al. Enabling fine-grained multi-keyword search supporting classified sub-dictionaries over encrypted cloud data[J]. IEEE Trans-actions on Dependable & Secure Computing, 2016, 13(3): 312- 325
[9]Xia Zhihua, Wang Xinhui, Sun Xingming, et al. A sucure and dynamic multi-keyword ranked search scheme over encrypt cloud data[J]. IEEE Transactions on Parallel and Distributed System, 2016, 27(2): 951- 963
[10]Tian Xue, Zhu Xiaojie, Shen Peisong, et al. Fast cryptographic retrieval based on similar query tree[J]. Journal of Software, 2016, 27(6): 1566- 1576 (in Chinese)(田雪, 朱晓杰, 申培松, 等. 基于相似查询树的快速密文检索方法[J]. 软件学报, 2016, 27(6): 1566- 1576)
[11]Wang Chong. R-tree index method based on Chameleon clustering algorithm[D]. Harbin: Harbin Institute of Technology, 2017 (in Chinese)(王冲. 基于Chameleon聚类算法的R树索引方法研究[D]. 哈尔滨: 哈尔滨工大学, 2017)
[12]Chen Chi, Zhu Xiaojie, Shen Peisong, et al. An efficient privacy-preserving ranked keywords search method[J]. IEEE Transactions on Parallel & Distributed Systems, 2016, 27(4): 951- 963
[13]Yang Yang, Yang Shulüe, Ke Min. Ranked fuzzy keyword search based on simhash over encrypted cloud data[J]. Chinese Journal of Computers, 2017, 40(2): 431- 444 (in Chinese)(杨旸, 杨书略, 柯闽. 加密云数据下基于Simhash的模糊排序搜索方案[J]. 计算机学报, 2017, 40(2): 431- 444)
[14]Witten I H, Moffat A, Bell T C. Managing gigabytes: Compressing and indexing documents and images[J]. IEEE Transactions on Information Theory, 1995, 41(6): 79- 80
[15]Yang Jun, Liu Zheli, Li Jin, et al. Multi-key searchable encryption without random oracle[J]. Intelligent Networking and Collaborative Systems, 2014, 30(1): 179- 190
[16]Hui Zhen, Feng Dengguo, Zhang Min, et al. A secure index against statistical analysis attacks[J]. Computer Research and Development, 2017, 54(2): 295- 304 (in Chinese)(惠榛, 冯登国, 张敏, 等. 一种可抵抗统计攻击的安全索引[J]. 计算机研究与发展, 2017, 54(2): 295- 304)
[17]Red Hat. CentOS-7-x86_64-DVD-1708. iso[OL]. [2017-01-28]. http://is oredirect.centos.org/centos/7/isos/x86_64/CentOS-7-x86_64-DVD-1708.iso
[18]Jason R. 20_newsgroups. tar. gz[DB/OL]. [2017-01-29]. http://download.cs dn.net/index.php/mobile/source/download/bukaohuaxue/851012
[19]Apache. Lucene3[OL]. [2017-09-28]. http://Jakarta.apache.org/lucene